Discussion :

[membreComplexe12]

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

[Franck Dernoncourt]

http://fr.wikipedia.org/wiki/Algorit...de_convergence ?

[membreComplexe12]

en fait je n'ai pas vraiment compris ces notions et sur wiki je trouve que c'est un peu compliqué pour un débutant...

1°) par exemple on a pour la dichotomie:

Xn+1 - Xn = ecartOrigine/2^n

J'ai bien compris comment obtenir ceci mais j'ai pas trop compris pourquoi on dit que la convergence est lineaire ?

par le "n" n'a pas de puissance ?


2°) pour newton:

pour newton on dit que la convergence est quadratique car le "n" est au carré dans la relation donnée par Xn+1 - Xn ??

[davly]

je n'ai pas étudier la vitesse de convergence des algo, mais leur complexité,
il est vrai de dire que la dichotomie est logarithmique et que l'algo de newton quadratique.

j'ai l'impression que tu peux donc lié cela a la compléxité moyenne de l'algo.
La compléxité moyenne correspond à l’ordre de grandeur des itérations de ton algo.

- si t'a un tableau de n élément avec des indices, tu as un indices, tu sais donc ou le récupérer c'est de compléxité 1.

- maintenant si tu n'as pas l'indice, tu dois le parcourir entièrement, on parlera ici de compléxité linéaire, compléxité n.

- si maintenant tu fais une recherche par dichotomie (en supposant que ton tableau est trié bien sur), tu vas couper le tableau autant de fois que possible en 2 jusqu’à avoir l’élément, t'aura moins que le linéaire.. compléxité logarithmique.

- si tu veux trier ton tableau, l’algorithme glouton est quadratique, tu fais un double parcour pour tout ranger.. compléxité n².

c'était des exemple pour illustrer maintenant pour démontrer, je me rappelle plus trop de formules, c'est long et pénible a lire, essaye de voir ce que tu peux avoir sur le net.

j’espère que ça pourra t'aider à comprendre le principe.

[membreComplexe12]

oui ça à l'air lié ces choses...

je vais voir sur le net ce que je trouve là dessus.


merci en tout cas :-)

[Franck Dernoncourt]

oui ça à l'air lié ces choses...

Heu, pas tellement :

• la complexité computationnelle se penche sur l'ordre de grandeur du nombre d'unités de calcul à réaliser pour arriver à la fin d'un algorithme ;
• la vitesse de convergence étudie l'évolution d'une suite (au sens mathématique).

Dans certains cas particuliers, l'étude de la vitesse de convergence peut certes éclairer la complexité computationnelle, mais c'est rare ! Et le calcul de la complexité computationnelle ne sert à rien pour déterminer la vitesse de convergence.