Réflexions

E désigne un espace euclidien de dimension finie.
Nous rappelons ce qu'est une symétrie orthogonale par rapport à un sous espace F.
L'espace E est somme directe de F et F tout vecteur x s'écrit donc de façon unique x=y+z avec y ∈ F et z ∈ F.
L'application x → y-z possède les propriétés suivantes:
C'est une application orthogonale, s*=s-1.
Elle est involutive sos=Id
Donc en définitive:
s=s*=s-1
Dans le cas particulier où F est un hyperplan nous appellerons une telle symétrie une 'réflexion' .
Le premier résultat important concernant les réflexions est le suivant:
x et y étant deux vecteurs de même norme non nulle. Il existe une et une seule réflexion transformant x en y.
Il est clair que la réflexion cherchée est exactement la réflexion par rapport à l'hyperplan H orthogonal au vecteur x-y.

Produits tensoriels

Soit W un vecteur colonne de ℝn , alors le produit matriciel WtW est une matrice carrée d'ordre n que nous noterons W⊗W .
W⊗W est clairement symétrique
Le coefficient d'indice i,j est wi wj.
Considérons le cas particulier où W est de norme euclidienne 1 (||W||=1) alors dans ce cas :
(W⊗W)(W⊗W)=W⊗W.
Il suffit pour le voir d'utiliser la définition du produit et le fait que W est de norme 1.
Toujours dans le cas où ||W||=1. L'application S donnée par:
S=I-2W⊗W vérifie:
S=S-1=S*
S(W)=-W
Pour la première partie, il suffit pour le voir de calculer le produit S2 et d'utiliser la propriété précédente.
Pour la seconde partie l'égalité résulte de la définition de W⊗W et du fait que W est de norme 1.
En conclusion:
S est la symétrie orthogonale par rapport à l'hyperplan H=W.
Nous pouvons maintenant combiner cela avec la première partie:
Si x et y sont deux vecteurs de même norme non nulle, la réflexion transformant x en y est I-2W⊗W où W est le vecteur (x-y)/||x-y||.

Factorisation de Householder

Nous avons maintenant tous les outils nécessaires pour donner l'algorithme de décomposition QR de Householder.
Soit A une matrice carrée régulière d'ordre n.
On désigne par U1,...,Un les vecteurs colonnes de la matrice A.
(e1,...,en) désigne la base canonique de ℝn. Nous affirmons que:
Il existe une réflexion H1 tel que le vecteur H1A(e1)=H1U1 ait toutes ses coordonnées nulles sauf la première.
Il suffit d'appliquer ce qui précède avec x=U1 et y=kαe1 où α=||U1|| et k = +/- 1.
En pratique nous prendrons toujours k du signe opposé de la première coordonnée de U1. Il existe donc une réflexion H1 telle que: H1 A soit de la forme:
x . . . .
0 A1
.
0
Appliquons maintenant l'hypothèse de récurrence à la matrice A1 d'ordre n-1. Nous avons une factorisation A1=Q1R1 avec Q1 orthogonale.
Ce que nous pouvons encore écrire tQ1A1=R1.
De cette écriture nous pouvons déduire: tQ1'A1'=R1' où:
∀ M, M' est la matrice obtenue en bordant M par la ligne (1,0, .. ,0) au dessus et par la colonne t (1,0, ... ,0) à gauche. On peut alors écrire:
H1A=A1'+ M où M a toutes ses lignes nulles sauf la première.
En multipliant par tQ1'
tQ1'H1 A=R1'+tQ1'M
Vu la forme de tQ1' on peut affirmer que tQ1'M comporte des zéros partout sauf sur la première ligne.
De sorte que:
R1'+ tQ1'M est triangulaire
et,
tQ1'H1 est orthogonale comme produit de deux matrices orthogonales.
Le théorème est donc démontré par récurrence sur le rang de A.

Café Python

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