Transformations de Householder

Rappelons que toute symétrie hyperplane peut s’écrire sous la forme suivante : $H = Id-2\times N.N^t$ où $Id$ est la matrice identité en dimension $n$ et $N$ est un vecteur de taille $n$ et de norme euclidienne 1. Une telle matrice est appelée matrice de Householder.

Construction d’un matrice de Householder

  • Question : Étant donné deux vecteurs $U$ et $V$ de même norme, trouver comment choisir le vecteur $N$ pour que la matrice de symétrie $H_{U,V}$ alors obtenue envoie $U$ sur $V$. Écrire l’algorithme correspondant.

L’exemple suivant peut servir de test de fonctionnement :

U=np.array([[3],[4],[0]])
V=np.array([[0],[0],[5]])
H = np.array([[0.64, -0.48, 0.6], [-0.48, 0.36, 0.8], [0.6, 0.8, 0]])
# H(U)=V
print(H.dot(U))
#+end_src

[[0.]
 [0.]
 [5.]]

Application d’une matrice de Householder

  • Questions :
    1. Écrire une fonction optimisée qui calcule le produit d’une matrice de Householder par un vecteur.
    2. Étendre votre fonction pour qu’elle calcule le produit d’une matrice de Householder par un ensemble de vecteurs (ou de manière équivalente une matrice).

On fera attention d’écrire une fonction en complexité linéaire en exploitant le produit scalaire.

Etude de compléxité

  • Question : Comparer la complexité obtenue avec la complexité d’un produit matrice-matrice usuel.