salut tous,
je voudrais savoir comment on demontre la vitesse de convergence des algorithmes ? j'ai par exemple entendu que newton à une vitesse quadratique, la dichotomie logarithmique...
pourriez vous me dire comment faire pour demontrer ceci et eventuellement me donner un exemple pour les methodes que j'ai cité ci dessus ?
je vous remercie d'avance pour votre aide
L'idée c'est de minorer l'écart entre la valeur théorique et la valeur à l'étape n (en fonction éventuellement de l'écart entre la valeur théorique et le point de départ de l'algorithme):
Par exemple pour la dichotomie, on a (de façon triviale):
La convergence est donc linéaire (on gagne une décimale (binaire) à chaque itération)
Pour la méthode de Newton, on peut trouver une démonstration de la convergence quadratique ici :
http://fr.wikipedia.org/wiki/M%C3%A9...on#Convergence
merci bcp tryss pour ta reponse mais étant débutant j'ai besoin de plus de details stp car j'aimerai etre capable de bien comprendre la demarche pour l'appliquer à plusieurs algo.
=> pour la dichotomie
=> on a pour l'itération 0
=> l'itération n
=> l'itération n+1
si je prends par exemple:mais du coup je ne vois pas comment tu as trouvé ta relation...
et je n'ai pas compris ton explication car je ne vois pas grand chose de lineaire puis le "n" est dans un exposant .... pour moi la relation "f(n)" n'est pas lineaire ...
=> pour N-R
j'avais vu la demo sur wiki mais je ne l'ai pas comprise car comme tu le vois je n'ai meme pas compris celle de la dichotomie...
merci pour ton aide
Quant à la méthode de Newton elle a une vitesse en
si tu as plus de details en effet ça m'intéresse(tu peux m'envoyer par MP par exemple)
sinon pour la dichotomie mon raisonnement est pas bon ?
j'ai reçu ton MP mais lorsque je veux t'envoyer un MP pour te donner mon adresse ça me dit que tu as trop de message dans ta boite dde reception et que je ne peux donc pas de contacter...Envoyé par indian58
Quant à la méthode de Newton elle a une vitesse en
Sinon, en attendant si quelqu'un peut me donner plus d'info sur les demonstration ci dessus ça serait cool
ps: pour la dicho je pense que mon raisonnement est pas mal mais je trouve pas comme Tryss...
pour NR je pense que ça doit etre similaire comme demarche mais pouvez vous me donenr les etapes s'il vous plait ?
merci beaucoup
Normalement, c'est maintenant bon pour ma boîte de mp.
Pour ta démo, tu pourrais l'expliciter, stp?
en fait je voudrais comprendre comment on s'y prend pour démontrer la vitesse de convergence (et eventuellement la stabilité).
=> d'apres ce que tryss ma dit j'ai compris qu'il fallait faire:
Xn-Xo et étudier le resultat qui sera une fonction de "n" mais en faisant ceci pour la dichotomie (cf. mon message plus haut) je ne trouve pas le resultat anoncé par Tryss
Oui, et c'est pour ça que j'aimerais connaître ta démonstration en détail, pour savoir où se trouvent tes éventuelles erreurs.
Pour les mp, c ok?
1°) j'ai bien reçu ton mail, merci.
2°) en refaisant la demo pour la dochotomie j'aii compris mon erreur:
=> ce que je me dis c'est qu'il faut voir comment évolue la suite
=> du coup pour étudier la suite j'étudie f(n+1) - f(n)
j'ai donc:
=> pour l'iteration
=> pour l'iteration
=> si je fais la soustraction des deux termes j'ai donc la relation qui me lit Xn+1 à Xn est c'est:
par contre je n'arrive pas à comprendre pourquoi on parle de convergence lineaire car le "n" est dans une puissance => ce n'est donc pas lineaire ?
Bonne remarque, c'est linéaire dans le sens où le nombre de décimales correctes (de ta valeur approchée) augmente d'un cran à chaque itération; par opposition à par exemple à la méthode de Newton qui est quadratique, où le nombre de décimales correctes double à chaque itération.
merci pour cette reponse,
qu'appel tu le nombre de decimal correct, je ne comprend pas ...
pourrais tu me donner un exemple numerique concret stp car je ne comprends pas cette historie de linearité
par exemple si L=12 et je suis à iteration 1 j'ai:
X=6
par exemple si L=12 et je suis à iteration 2 j'ai:
X=3
qu'es ce qui est lineaire dans cette exemple ?
Il s'agit de ta somme partielle (de 0 à N).Le nombre de décimales correctes correspond au nombre des premières décimales identiques à celles de la somme de la série infine (i.e. la somme que tu veux calculer et approcher avec ta somme partielle).
1°) je crois que je comprends mieux à présent. merci beaucoup
=> on dit que Newton raphson à une convergence quadratique car le "n" est au carré ?
2°) aurais tu un exemple de demonstration pour N-R comme j'ai fais avec la dichotomie ?
=> j'ai regardé sur wiki et j'ai pas trop compris la demo
1) Le "n" n'est pas au carré mais en 2^n!! (cf mon tipe) ce qui signifie que le nombre de décimales correctes double.
2) Tu fais la même chose que pour la dicho en utilisant Taylor-Lagrange, sinon j'imagine que wikipedia est ton amie.
merci pour ton aide
A+
je viens d'essayer pour Newton à demontrer comme pour la dichotomie mais je n'y arrive pas:
ensuite remplace le Xn qui apparait par son itération de Newton (cf cidessus), et ça me permet de simplifier des données et d'avoir:
à présent je ne sais plus quoi faire...
Il faut que tu utilises taylor lagrange à l'ordre 2.
en effet j'ai vu que wiki a utilisé ceci mais je n'avais pas compris pourquoi vu que l'algo est tronqué à l'ordre 1 ...
