La méthode de décomposition de Givens procède de la même idée de base que celle de Householder, mais en remplaçant les symétries par des rotations. Elle a la réputation d'être un peu plus complexe mais plus stable sur le plan calculatoire, c'est à dire plus fiable pour les sytèmes mal conditionnés.

Rappel sur les rotations

Les rotations sont, par définition, les endomorphismes orthogonaux positifs.
Soit F un sous-espace de dimension 2 de E et soit F son orthogonal.
Considérons une base orthonormale (a1,a2) de F complétée en une base orthonormale (a1,a2,...,an) de E au moyen d'une base orthonormale (a3,...,an) de F.
Alors l'application dont la matrice relativement à (a1,a2,...,an) est:
cos θ -sin θ 0 .. 0
sin θ cos θ 0 .. 0
0 0 1 .. 0
. . 0 .. .
0 0 0 .. 1
est un endomorphisme orthogonal qui s'appelle la 'rotation dans le plan F autour de F ' .

Elle opère, dans le plan F une rotation 'usuelle' alors que tous les vecteurs de F sont invariants.
Evidemment, quand la dimension est 3, F est une droite vectorielle, on retrouve la rotation autour d'un axe.
Nous aurons besoin aussi du résultat suivant: L'application t → eit définit une bijection de [0, 2 π[ sur le cercle unité.
Cela veut dire qu'à chaque couple (c,s) vérifiant c2 +s2=1, on peut associer un réel θ ∈ [0, 2 π[, tel que:
c= cos(θ)
s= sin(θ)

Annulation d'un coefficient par rotation:

Le résultat suivant constitue le fondement de la méthode de décomposition QR de Givens.
Soit A une matrice régulière d'ordre n. Par produit à gauche avec une matrice de rotation telle que ci-dessus convenablement choisie on peut 'annuler' le coefficient d'indices q,p de A.
Plus précisément si A=(ai,j)1≤i,j≤n il existe une matrice G du type ci-dessus, telle que:
Si GA= (bi,j)1≤i,j≤n on ait bq,p=0.
Posons ;
c p , q , A = 1   si     a pp = a qp = 0           a pp a pp 2 + a qp 2   sinon
et
s p , q , A = 0   si     a pp = a qp = 0           a qp a pp 2 + a qp 2   sinon
Soit la matrice de rotation G(p,q,A) avec p < q:
1 0 0 0 0 0 0
0 1 0 0 0 0 0
0 0 c(p,q,A) s(p,q,A) 0 0
0 0 1 0 0
0 0 -s(p,q,A) c(p,q,A) 0 0
0 0 0 0 0 1 0
0 0 0 0 0 0 1
le coefficient d'indice q,p du produit est -s(p,q,A)ap,p+c(p,q,A)aq,p=0

Algorithme de Givens

On commence par faire les multiplications :
G(2,1,A)A=A(2,1) qui aura un 0 en position 2,1
puis G(3,1,A(2,1))A(2,1) qui aura des zéros en positions 2,1 et 3,1
et ainsi de suite jusqu'à:
G(n,1,A(n-1,1))A(n-1,1)=A(n,1) dont la première colonne sera nulle sauf le premier élément. Après on continue avec
G(3,2,A(n,1))=A(2,2)
...........
G(n,2,A(n-1,2))A(n-1,2)=A(n,2) qui aura des zéros sous la diagonale pour les deux premières colonnes.
et ainsi de suite, la forme des matrices G(p,q,X) et l'ordre des multiplications assurant que les zéros acquis ne sont pas perdus.
On arrive à la fin à
G(n,n-1,A(n,n-2))=A(n,n-1) qui doit être triangulaire.
Ainsi si G désigne la matrice :
p = n 1 1 q = n p + 1 G q , p , A q , p
G est orthogonale comme produit de rotations et GA est triangulaire.
D'où nous tirons A=t GR qui est la décomposition cherchée.

Café Python

Voici une implémentation de l'algorithme de factorisation QR par la méthode de Givens.