WikiMath

Motivations

Le procédé d'orthonormalisation consiste à prendre une base $(b_1, ..., b_n)$ de l'espace vectoriel considéré, et à la transformer en une base orthonormée $(e_1, ..., e_n)$ :

• les vecteurs sont deux à deux orthogonaux,
• ils sont de norme égale à 1.

Ce procédé se généralise immédiatement à toute famille libre $(b_1, ..., b_k)$ qui peut ainsi être transformée en une famille (libre) orthonormée $(e_1, ..., e_k)$ engendrant le même espace.

En fait, on peut montrer que $(e_1, ..., e_k)$ est l'unique famille orthonormée engendrant le même espace que $(b_1, ..., b_k)$, telle que $<e_i,b_i>>0$ (produit scalaire strictement positif, i.e. les vecteurs "pointent dans la même direction").

Finalement, la méthode de Gram-Schmidt consiste à former une famille orthonormale en "redressant", puis en normant, progressivement chacun des vecteurs fournis, pour les rendre orthogonaux aux vecteurs déjà formés.

L'Algorithme

Le principe de cette orthonormalisation se comprend aisément :

1. On divise $b_1$ par sa norme, ce qui donne $e_1$ :

$e_1 = \frac{b_1}{||b_1||}$

1. On annule la composante de $b_2$ suivant $e_1$, pour que le résultat soit orthogonal à $e_1$, puis on divise le résultat par sa norme :

$e_2 = \frac{b_2 - <b_2,e_1> e_1}{||b_2-<b_2,e_1> e_1||}$

1. On annule la composante de $b_3$ suivant $e_1$ et $e_2$, pour que le vecteur résultant soit bien orthogonal à ces deux vecteurs, et on divise le résultat par sa propre norme :

$e_3 = \frac{b_3 - <b_3,e_1> e_1 - <b_3,e_2> e_2}{||b_3 - <b_3,e_1> e_1 - <b_3,e_2> e_2 e_1||}$

1. On continue jusqu'à épuiser tous les vecteurs $b_i$...

$e_i = \frac{b_i - \sum_{j=1}^{i-1} <b_i,e_j> e_j}{||b_i - \sum_{j=1}^{i-1} <b_i,e_j> e_j||}$

Gram-Schmidt et sympy

Montrons comment réaliser le procédé d'orthonormalisation de Gram-Schmidt avec python-sympy.

Préliminaires

Commençons par définir trois vecteurs à orthonormaliser :

  >>> from sympy import *
  >>> B1 = Matrix((2,1,2)).reshape(3,1)
  >>> B2 = Matrix((12,-6,0)).reshape(3,1)
  >>> B3 = Matrix((-3,-3,18)).reshape(3,1)

Avant toutes choses, vérifions que l'on a bien une base. Nous allons former une matrice avec ces trois vecteurs, puis nous assurer que le déterminant de cette matrice est bien non nul :

  >>> M=B1.row_join(B2).row_join(B3)
  >>> M
  [2, 12, -3]
  [1, -6, -3]
  [2,  0, 18]
  >>> M.det()
  -540

Ces vecteurs forment donc bien une base !

Fonction prédéfinie

Pour orthonormaliser façon Gram-Schmidt en sympy :

  >>> GramSchmidt([B1,B2,B3], orthog = True)
  [ [2/3]
  [1/3]
  [2/3], [ 2/3]
  [-2/3]
  [-1/3], [-1/3]
  [-2/3]
  [ 2/3] ]

Si on a juste besoin d'orthogonaliser (pas normer), ne pas mettre le paramètre orthog :

  >>> GramSchmidt([B1,B2,B3])
  [ [2]
  [1]
  [2], [ 8]
  [-8]
  [-4], [ -5]
  [-10]
  [ 10] ]

Le produit scalaire entre vecteurs s'obtient avec la méthode dot, et la norme avec norm. On peut donc vérifier que l'on a bien une base orthogonale non normée :

  >>> (u,v,w) = GramSchmidt([B1,B2,B3])
  >>> u.dot(v) 
  0
  >>> u.dot(w)
  0
  >>> v.dot(w) 
  0
  >>> u.norm()
  3

A la main

On a tout ce qu'il faut pour orthonormaliser à la main. Commençons par calculer le premier vecteur $e_1$ de la nouvelle base (c'est $b_1$ divisé par sa norme) :

  >>> e1 = B1/B1.norm()
  >>> e1
  [2/3]
  [1/3]
  [2/3]
  >>> e1.norm()
  1

Continuons le procédé, en suivant l'algorithme ci-dessus. On vérifiera, à chaque étape, la norme, et le produit scalaire avec les autres vecteurs :

  >>> e2 = B2-B2.dot(e1)*e1
  >>> e2 = e2/e2.norm()
  >>> e2
  [ 2/3]
  [-2/3]
  [-1/3]
  >>> e2.norm()
  1
  >>> e1.dot(e2)
  0
  >>> e3 = B3-B3.dot(e1)*e1-B3.dot(e2)*e2
  >>> e3 = e3/e3.norm()
  >>> e3
  [-1/3]
  [-2/3]
  [ 2/3]
  >>> e3.norm()
  1
  >>> e3.dot(e1)
  0
  >>> e3.dot(e2) 
  0

On a donc réussi, en appliquant le procédé d'orthonormalisation de Gram-Schmidt, à transformer la base

$\left(\begin{array}{c} 2 \\ 1 \\ 2 \end{array}\right), \left(\begin{array}{c} 12 \\ -6 \\ 0 \end{array}\right), \left(\begin{array}{c} -3 \\ -3 \\ 18 \end{array}\right)$

en la base orthonormée :

$\left(\begin{array}{c} \frac{2}{3} \\ \frac{1}{3} \\ \frac{2}{3} \end{array}\right), \left(\begin{array}{c} \frac{2}{3} \\ -\frac{2}{3} \\ -\frac{1}{3} \end{array}\right), \left(\begin{array}{c} -\frac{1}{3} \\ -\frac{2}{3} \\ \frac{2}{3} \end{array}\right)$

Travaux pratiques

1. Faire le même travail avec numpy.
2. Faire une fonction qui reçoit une liste de vecteurs en entrée, et qui les orthonormalise.
3. Faire en sorte que votre fonction puisse normaliser, ou non.