Recherche de fonction récursive et convergente

[Natrem]

Bonjour,

Premièrement je tiens à souligner que je ne suis pas certain de la catégorie, mais mon problème doit bien rentrer dans un domaine quelconque étudié dans une certaine section des études supérieures.

Je suis étudiant en informatique (actuellement en stage au Québec) et cela fait plusieurs semaines que je suis coincé sur un projet personnel. Il concerne la fabrication d'un "modèle de calcul" permettant de gérer les déplacements de personnages (et autres) dans l'espace, dans un environnement client-serveur. Je ne peux pas utiliser un "point de départ" et effectuer tous mes calculs à partir de là, je dois utiliser les données de l'itération précédente (voire celle d'avant) pour calculer les valeurs courantes. Mon soucis concerne l'actualisation des valeurs de position, vitesse et accélération. En effet il faut que j'obtienne des valeurs égales pour des calculs basés sur les mêmes événements (qui apparaissent aux mêmes instants) mais avec des fréquences différentes.

Je pense que les difficultés que je rencontre viennent principalement de mon incapacité à poser le problème clairement, il m'est compliqué de déduire une équation ou quelque chose de ce type.

En appliquant les formules simples de déplacements dans l'espace cela fonctionne :


avec correspondant au temps écoulé depuis l'itération n,
la vitesse à l'itération n,
la position à l'itération n,
l'accélération (peut varier mais ce n'est pas le problème évoqué ici).
Ce modèle fonctionne, par exemple :
avec , ,

Première façon : , , on obtient
,
,
Deuxième façon : , on obtient
,

On peut observer que, malgré les intervalles de temps différents entre les calculs, le résultat reste le même.

Je voudrais maintenant insérer dans ce modèle une atténuation, que l'on peut comparer aux frictions de l'air, du sol etc. Cela dépend donc de la vitesse.

Je suis arrivé à caractériser la solution à mon problème comme ceci : je cherche une fonction utilisée pour remplacer le calcul suivant dans le modèle décrit précédemment :
Elle devrait respecter les conditions suivantes :
Pour , on a

et , étant un nombre représentant la valeur vers laquelle converge la fonction F pour un a donné et un assez grand. J'aimerais aussi pouvoir ajouter un paramètre à la fonction permettant de contrôler la "rapidité de convergence".

J'espère avoir été assez clair, je sais que mon post ici est entaché de mes connaissances en programmation, malgré ma tentative d'exprimer ceci le plus mathématiquement et complètement possible. Je cherche donc la formule qu'est la fonction F, que je considère comme extrinsèquement récursive et convergente. N'hésitez pas à poser des questions.

Merci d'avance,
Natrem

[eriadrim]

Bonjour,

Tout d'abord, sur les première équations que tu as trouvé :
Normalement l'accélération, c'est une variation de vitesse divisé par une variation de temps, donc pour moi :



Même chose pour la position :



Tu as dit aussi que l'accélération peut varier, donc il est important de le prendre en compte dans tes équations de la vitesse, surtout si tu veut ensuite faire une atténuation. En reprenant l'idée que tu as eu sur les positions, on obtiendrait donc :



Ensuite, tu parles de la nature de l'atténuation comme étant une force de frottement (si j'ai bien compris). Ce genre de force peut être déterminé, mais elle dépend de l'ordre de grandeur de ta vitesse. C'est sur cette force que tu pourras insérer un paramètre qui feras "converger" ta fonction plus rapidement. Tu obtiendras à partir de là une relation de récurrence entre et

J'espère t'avoir un peu aidé :lol3:

[Natrem]

Merci d'avoir pris la peine de répondre.

Pour la variation de temps, je pense qu'on parle de la même chose sous une notation différente, j'avais bien mis

correspondant au temps écoulé depuis l'itération n

Pour les variations d'accélération, ce ne serait que ponctuel. Mon système actuel marche pour des changements d'accélération discrets ; par exemple je peux estimer que devient 15 au lieu de 10 à la prochaine itération du temps écoulé T.

Je cherche donc ma fameuse fonction F qui répond à mes deux critères décrits précédemment :
D'abord , un exemple de solution à cette contrainte serait .
Puis , un exemple de solution à cette contrainte serait avec un paramètre permettant de gérer la vitesse de convergence.
Malheureusement chacun de ces exemples ne répond pas à l'autre contrainte.

[eriadrim]

Effectivement j'avais mal lu pour la variation de temps ....

Sinon pour la fonction. Déjà on peut trouver certaine propriétés :

Si on prend , et on a :


et donc

Ensuite si tu fait tendre vers l'infini, tendra vers l'infini et tu obtiendras :



Je vais continuer de chercher d'autres propriétés qui pourrait être utiles :lol3:

[Natrem]

Encore merci pour ta réponse !

Effectivement ces propriétés me semblent valides, mais je ne vois pas quelle formule pourrait les avoir. Déjà si je pense qu'une division par une valeur proportionnelle à est impossible, à moins de diviser par , avec et une fonction (par exemple ). Mais ce genre de système complique selon moi beaucoup et n'aide vraiment pas à faire correspondre la première condition (critère d'égalité après récursivité).

[Ben314]

Salut,
J'ai un peu peur (mais pas la certitude...) que ton problème n'ait pas de solution...
Ce que tu fait, ça consiste (à mon sens) à vouloir discrétiser un problème au départ continu
La position et la vitesse de ton objet, normalement, c'est des fonction de t qui sont :
et
dans le cas d'un mouvement uniformément accéléré.
On vérifie aisément que cela implique que :
et
Ce qui signifie que ta discrétisation est EXACTEMENT égale à la fonction continue de départ (ce qui est extrêmement rare...)
Et cela explique que ta discrétisation continue à vérifier ce que la fonction de départ vérifie évidement, à savoir : (*)
Sauf que ta discrétisation n'est EXACTEMENT égale à la fonction de départ que... si la fonction de départ est un polynôme de degrés 2 (i.e. un mouvement uniformément accéléré).
Si le mouvement que tu veut discrétiser n'est pas de ce type (uniformément accéléré), il faut
- Soit que tu accepte que la relation (*) ne soit plus valable avec ta discrétisation (mais que les deux termes soient uniquement "assez proche" l'un de l'autre).
- Soit que tu commence par décrire quelle type de fonctions tu veut discrétiser PUIS chercher s'il y a moyen de les discrétiser de façon exacte (par exemple, pour les polynômes de degré 4, on peut "discrétiser de façon exacte" en manipulant 3 termes Pn, Vn, An au lieu des deux Pn et Vn dans le cas de polynômes de degrés 2)

[Natrem]

Les deux solutions me conviennent.
- Mon projet est basé sur un système client-serveur qui implique des transmissions réseau, ce qui implique un délai de transmission difficile à contrôler et compenser, ce qui entraîne des erreurs de valeurs dans ce modèle de calcul. Donc si les résultats (sans prendre en compte ces inexactitudes dues au délai de transmission) ne sont pas exacts mais très proches, cela fonctionnera selon moi, vu que des erreurs seront déjà forcément présentes. Mais je n'ai jusqu'ici pas trouvé de formule qui s'approche, surtout avec des différences de t élevées.
- Pour le deuxième "soit", je n'ai pas très bien compris ; tout ce que je sais c'est que je cherche cette fonction F qui me permettrait de faire marcher mon modèle de calcul que j'ai actuellement, mais je peux tout aussi bien changer complètement les formules. Idéalement si je pouvais juste avoir en entrée des paramètres correspondant à la direction voulue du déplacement, à l'inertie du corps et sa vitesse maximale, je ne me soucie pas des formules utilisées, tant qu'elles ne dépassent pas une complexité monstrueuse et que le résultat soit similaire au fonctionnement de la physique.

Merci encore pour vos réponses !

[Ben314]

Le deuxième "soit", c'est sans doute le plus important : pour que l'on puisse discrétiser le problème, il faudrait savoir précisément comment il est posé, c'est à dire savoir quelle propriétés tu attend de la fonction p(t) (position à l'instant t) vu comme une fonction continue de t (ensuite on pourra regarder quelle est la "meilleure" façon de discrétiser).

Par exemple, si on considère qu'on a une "force de frottement" proportionnelle à la vitesse mais de direction opposée (ça ne colle pas trop avec la physique où c'est plutôt proportionnel au carré de la vitesse, mais... ça a le bon gout de pourvoir facilement se résoudre mathématiquement...)
Alors, sous forme continue, les fonction position, vitesse, accélération sont de la forme :
; ; où k est le "coef. de frottement" supposé connu.
Et on en déduit que :


(qui, à l'ordre 1, est évidement à peu prés égal à pour t petit.)


(qui, à l'ordre 2, est évidement à peu prés égal à pour t petit.)
Et, modulo de trimbaler 3 suites an, vn, pn et un coeff. k (=frottement) c'est une "discrétisation exacte" du problème continu de départ (i.e. ça va vérifier ton premier critère)

P.S. Par contre, tu risque d'avoir un problème "métaphysique" lorsque tu veut, pour des raisons extérieures, modifier l'accélération : elle n'est (évidement) plus constante et elle tend vers 0 (à cause des frottement). Si tu change directement le an (proche de 0) par une nouvelle valeur a', ça "redonne de l'élan" à l'objet en question qui risquait d'être déjà à vitesse quasi stabilisé...

[Natrem]

Je crois avoir compris une partie de ma confusion. Pour moi, l'accélération dont je parlais est constante, l'atténuation (ou frottement) était calculée à part, en fonction de la vitesse (au carré par exemple). Il serait plus judicieux que je considère cela comme une force ; pour mon objet en mouvement, je lui définis une force (appelée a dans mes posts précédents), ce qui permet d'obtenir une vitesse maximale (vers laquelle l'objet converge). C'est plus une valeur ajoutée constamment à la vitesse que la dérivée de cette dernière.

Je pense que je peux considérer l'accélération comme la somme de cette force et de l'atténuation (en fonction de la vitesse). De cette façon les deux s'annulent lorsque l'objet atteint sa vitesse stable.

Je ne comprend pas pourquoi exp() est utilisé ici. Serait-ce pour sa propriété de dérivabilité sans changement ?
Ce qui me parait aussi compliqué à utiliser dans les formules que tu as données, c'est qu'on se base toujours sur , alors que j’espérais pouvoir me baser sur . Ceci dit, si je considère comme la dernière fois que j'ai reçu une mise à jour de l'une des parties (client ou serveur), je devrai pouvoir implémenter cette méthode.

EDIT : De plus je ne comprend pas comment il est possible d'avoir une formule de non en fonction de ni ?
EDIT2 : J'ai essayé de tester ces formules, mais si je ne me base que sur et pas sur je viens de me rendre compte que mon premier système marche tout aussi bien finalement. Faut-il que je change mon modèle de calcul ou une fonction ne prenant que les valeurs de la dernière itération est-elle possible avec les contraintes spécifiées ?
EDIT3 : De plus avec ce modèle contenant des exp(), changer influe la limite de la vitesse, ce que je ne trouve pas très pratique.

[Natrem]

D'autres idées ?

Merci d'avance.

[Ben314]

Je ne comprend pas pourquoi exp() est utilisé ici. Serait-ce pour sa propriété de dérivabilité sans changement ?

Si on considère qu'un mobile est soumis à une force constante plus une "résistance au mouvement" proportionnelle à la vitesse, la formule "somme des forces = masse x accélération" donne une équation différentielle de la forme p''=cst - k.p' et c'est en résolvant cette équation différentielle qu'on obtient des exp(-kt).

Ce qui me parait aussi compliqué à utiliser dans les formules que tu as données, c'est qu'on se base toujours sur , alors que j’espérais pouvoir me baser sur . Ceci dit, si je considère comme la dernière fois que j'ai reçu une mise à jour de l'une des parties (client ou serveur), je devrai pouvoir implémenter cette méthode.

Dans les formule du post précédent, le "to" et le "t" sont absolument quelconques donc tu met effectivement ton à la place du et tu met à la place de pour que ça "colle" avec la façon dont ton bidule fonctionne (et tu n'as pas besoin de garder en mémoire les valeurs de p,v,a à l'instant "initial" ni les valeurs de alpha, beta et gamma : le seul truc à "garder", c'est le 'k').
Ca répond aussi à ta question un peu plus loin : tu peut tout à fait ne garder que les dernières valeurs (c'est ça l'intérêt des formules)

EDIT3 : De plus avec ce modèle contenant des exp(), changer influe la limite de la vitesse, ce que je ne trouve pas très pratique.

La façon dont je vois le truc, c'est qu'au départ de l'algo, tu donne une position, une vitesse et une accélération (plus la constante k qui ne va pas bouger), mais rien ne t'oblige à considérer que le moment où l'algo commence à tourner est l'instant t=0 (en fait tu t'en fout complètement de la valeur de t, tout ce que tu as à connaitre pour faire tourner l'algo, c'est les valeur de et les position, vitesse, accélérations à l'instant ).
Après, effectivement, tu peut déterminer la vitesse "limite" que finira par atteindre ton mobile en faisant un calcul utilisant sa vitesse actuelle et son accélération actuelle.
Plus précisément, dans les formules çi dessus, la "vitesse" limite, c'est le .
En fait, à n'importe quel moment t, tu as
Cela signifie que, si à un moment donné, tu veut changer la vitesse actuelle (ou l'accélération actuelle) sans changer la vitesse limite, il faut que tu te débrouille pour que où sont les vitesse/accélération AVANT le changement et sont les vitesse/accélération APRES le changement

[Natrem]

J'ai un peu mieux compris le principe, mais je vois toujours un problème. Si je ne me trompe pas, k, le "coeff de frottement" représente la force opposée à la vitesse, et donc indirectement la vitesse limite du mobile. Mais cette dernière dépend de l'accélération et de la vitesse actuelle, donc il faut que j'adapte k en fonction de la vitesse actuelle pour avoir une vitesse limite constante quelle que soit la vitesse/accélération actuelle ?

[Ben314]

Concernant ce type de problème, LA formule qui "fait tout", c'est
Dans laquelle est la vitesse limite du mobile, k le coeff. de frottement, la vitesse actuelle et .
Normalement, , ça sert à rien de le conserver dans le proccessus vu que tu peut le calculer quand tu veut à l'aide de la formule çi dessus.
Après, si à un moment donné tu veut modifier un des paramètres v,a ou k sans que cela change la vitesse limite, il faudra que tu en modifie au moins 2 des trois et, si les trois nouveaux sont v',a',k' il faudra que

Au niveau "physique" (mais je rappelle que ça colle pas trop avec le modèle usuel où la résistance est proportionnelle au carré de la vitesse), le coeff. k n'est pas censé changer au cours du temps : il correspond à la "pénétration dans l'air" du mobile (le fameux Cx pour une voiture) qui est normalement constant. Par contre, ce qui varie, c'est le 'v' (vitesse de la voiture) et surtout le 'a' qui correspond plus ou moins à la position de la pédale d'accélérateur.
Si tu roule à vitesse constante (donc v=vitesse limite et a=0) et qu'à un moment donné tu appuie sur la pédale d'accélérateur, tu change le 'a' mais pas le 'v' (à cet instant exact), mais 'v' va évoluer vers une nouvelle "vitesse limite" qui n'est pas la même que celle que tu avais avant de toucher à l'accélérateur.
Tout ça pour dire que le fait que la vitesse limite dépende de 'a', ben c'est... assez normal...

[Natrem]

Ce qui m'embêtait c'était le fait que 'a' corresponde à la pédale d'accélération. En fait c'est plus le résultat dans le temps de la position de la pédale, ce qui me perturbait. Ce que j'ai en entrée finalement c'est la position de cette pédale, et je pense pouvoir calculer a et k en fonction de cette valeur avec les formules ci-dessus.
Donc merci beaucoup, je vais essayer de travailler avec ces données là.

Pour la gouverne de ceux que ça intéresse, j'ai avec qui correspond à la vitesse limite voulue (arbitraire), la vitesse de convergence (arbitraire), , et l'accélération, la vitesse et la position lors de la dernière mise à jour de et/ou (voire , et/ou si besoin).
Les formules de , et sont données plus haut, telles que :