Position du problème

Considérons à nouveau le système linéaire du chapitre 5 du support de cours. Soit $M$ un entier positif, et soit $N$ tel que $N=M^2$. Dans la section 11.3 du livre nous avons à résoudre un système linéaire $A\vec{x}=\vec{b}$, la matrice $A$ étant définie par la figure ci-dessous.

Cette matrice est clairement symétrique, de bande de demi-largeur $M+1$. D'après le théorème 11.1, elle est définie positive et nous pouvons utiliser l'algorithme du gradient conjugué pour résoudre le système linéaire. D'après le théorème 6.7, l'algorithme converge en au plus $N$ itérations. En pratique, nous constaterons qu'il faut de l'ordre de $M$ itérations, soit beaucoup moins que le résultat annoncé dans le théorème 6.7.

Considérons le cas où le $N$-vecteur $\vec{b}$ a pour coefficients

$$b_1 = 2, \quad b_i=i \quad i=2,\ldots,M-1,$$

$$b_M=2M+2, \quad b_{M(i-1)+1}=i \quad i=2,\ldots,M-1,$$

$$b_{M(M-1)+1}=2M+2, \quad b_{M(i-1)+M}=M+1+i \quad i=2,\ldots,M-1,$$

$$b_{N}=4M+4, \quad b_{M(M-1)+i}=M+1+i \quad i=2,\ldots,M-1,$$

les autres coefficients étant nuls. Nous pouvons alors vérifier que le $N$-vecteur $\vec{x}$ a pour coefficients

$$x_{M(i-1)+j} = i+j\qquad i,j=1,\ldots,M.$$

Nous utiliserons ce résultat pour valider les calculs.