Ecrit par Adrien le Novembre 30, 2000 at 11:50:08:
En réponse à: Gradient conjugue écrit par Aurelie le Novembre 29, 2000 at 04:29:15:
: En combien d'iterations converge la methode du gradient conjugue? En principe, n maximum, je crois, mais comment le prouver??
La preuve n'est pas évidente, surtout par forum interposé.
L'idée sous jacente est qu'au fur et à mesure de la méthode, on construit une base de vecteurs dans laquelle on exprime la solution approchée.
(Une solution qui minimise une certaine erreur). Après n itérations, on a donc construit une base de dimension n, comme notre espace, et la solution approchée doit donc être la solution exacte.
Le mieux est de trouver un bon livre/cours d'analyse numérique (dans une bibliothèque) ou ce sera démontré.
Il faut toutefois faire attention :
On a la solution exacte après n itérations, pour autant qu'on ne fasse pas d'erreurs d'arrondis, ce qui n'est presque jamais le cas quand on travaille sur un vrai système avec un ordinateur.
Enoutre quand n est très grand (parfois 1 000 000 ou plus) on ne veut pas attendre de faire autant d'itérations, d'autant plus que les dernières itérations n'apportent pas un grand gain par rapport
à la solution déjà calculée. En pretique, on va donc arreter les itérations après un certain temps (typiquement quand le résidu r=b-A*x est petit en norme, ou que deux solutions successives sont très proches)
Voilà.
Bon travail.
Adrien.