154
5 Systèmes linéaires
Cette technique est connue sous le nom d’algorithme de Thomas. Son
coût est de l’ordre de n opérations.
La commande spdiags de MATLAB permet de construire une matrice tridiagonale en ne stockant que les diagonales non nulles. Par
exemple, les lignes suivantes :
b = ones (10 ,1); a =2* b; c =3*b ;
T = spdiags ([ b a c ] , -1:1 ,10 ,10);
donnent la matrice tridiagonale T ∈ R
10×10 dont les éléments valent 2
sur la diagonale principale, 1 sur la première sous-diagonale et 3 sur la
première sur-diagonale.
Remarquer que T est définie de manière creuse, ce qui signifie que
seuls les éléments non nuls sont stockés.
Quand un système est résolu avec la commande \, MATLAB détecte
le type de matrice (en particulier si elle est stockée sous forme creuse)
et sélectionne l’algorithme de résolution le plus approprié. Par exemple,
quand A est tridiagonale et stockée sous forme creuse, c’est l’algorithme
de Thomas qui est utilisé par la commande \ de MATLAB (voir la
Section 5.8 pour une discussion sur cette commande).
5.7 Systèmes sur-déterminés
Un système linéaire Ax=b avec A∈ R
m×n est dit sur-déterminé si m >
n, et sous-déterminé si m < n.
Un système sur-déterminé n’a généralement pas de solution, à moins
que le second membre b ne soit un élément de l’image de A, définie par
Im(A) = {z ∈ R
m : z = Ay pour y ∈ R
n
}.
(5.36)
Pour un second membre b quelconque, on peut chercher un vecteur x
∗
∈
R
n qui minimise la norme euclidienne du résidu, c’est-à-dire
Φ(x
∗ ) = Ax
∗
− b
2
2 ≤ ≤Ay − b
2
2 = Φ(y)
∀y ∈ R
n . (5.37)
Quand il existe, le vecteur x
∗ est appelé solution au sens des moindres
carrés du système sur-déterminé Ax=b.
Comme on l’a fait dans la Section 3.6, on peut trouver la solution
de (5.37) en écrivant que le gradient de Φ s’annule en x
∗ . On trouve,
avec des calculs similaires, que x
∗ est en fait solution du système linéaire
carré n × n
A
T Ax
∗ = A
T
b
(5.38)
qu’on appelle système d’équations normales. Ce système (5.38) est inversible si A est de rang maximal (c’est-à-dire rang(A) = min(m,n), où le
rang de A, noté rang(A), est la taille de la matrice carrée extraite de A
5 Systèmes linéaires
Cette technique est connue sous le nom d’algorithme de Thomas. Son
coût est de l’ordre de n opérations.
La commande spdiags de MATLAB permet de construire une matrice tridiagonale en ne stockant que les diagonales non nulles. Par
exemple, les lignes suivantes :
b = ones (10 ,1); a =2* b; c =3*b ;
T = spdiags ([ b a c ] , -1:1 ,10 ,10);
donnent la matrice tridiagonale T ∈ R
10×10 dont les éléments valent 2
sur la diagonale principale, 1 sur la première sous-diagonale et 3 sur la
première sur-diagonale.
Remarquer que T est définie de manière creuse, ce qui signifie que
seuls les éléments non nuls sont stockés.
Quand un système est résolu avec la commande \, MATLAB détecte
le type de matrice (en particulier si elle est stockée sous forme creuse)
et sélectionne l’algorithme de résolution le plus approprié. Par exemple,
quand A est tridiagonale et stockée sous forme creuse, c’est l’algorithme
de Thomas qui est utilisé par la commande \ de MATLAB (voir la
Section 5.8 pour une discussion sur cette commande).
5.7 Systèmes sur-déterminés
Un système linéaire Ax=b avec A∈ R
m×n est dit sur-déterminé si m >
n, et sous-déterminé si m < n.
Un système sur-déterminé n’a généralement pas de solution, à moins
que le second membre b ne soit un élément de l’image de A, définie par
Im(A) = {z ∈ R
m : z = Ay pour y ∈ R
n
}.
(5.36)
Pour un second membre b quelconque, on peut chercher un vecteur x
∗
∈
R
n qui minimise la norme euclidienne du résidu, c’est-à-dire
Φ(x
∗ ) = Ax
∗
− b
2
2 ≤ ≤Ay − b
2
2 = Φ(y)
∀y ∈ R
n . (5.37)
Quand il existe, le vecteur x
∗ est appelé solution au sens des moindres
carrés du système sur-déterminé Ax=b.
Comme on l’a fait dans la Section 3.6, on peut trouver la solution
de (5.37) en écrivant que le gradient de Φ s’annule en x
∗ . On trouve,
avec des calculs similaires, que x
∗ est en fait solution du système linéaire
carré n × n
A
T Ax
∗ = A
T
b
(5.38)
qu’on appelle système d’équations normales. Ce système (5.38) est inversible si A est de rang maximal (c’est-à-dire rang(A) = min(m,n), où le
rang de A, noté rang(A), est la taille de la matrice carrée extraite de A