Matrice orthogonale

AvantagesEdit

L’analyse numérique tire parti de nombreuses propriétés des matrices orthogonales pour l’algèbre linéaire numérique, et elles apparaissent naturellement. Par exemple, il est souvent souhaitable de calculer une base orthonormale pour un espace, ou un changement orthogonal de bases ; les deux prennent la forme de matrices orthogonales. Le fait d’avoir un déterminant de ±1 et toutes les valeurs propres de magnitude 1 est un grand avantage pour la stabilité numérique. L’une des implications est que le nombre de condition est 1 (qui est le minimum), de sorte que les erreurs ne sont pas amplifiées lors de la multiplication avec une matrice orthogonale. De nombreux algorithmes utilisent des matrices orthogonales comme les réflexions de Householder et les rotations de Givens pour cette raison. Il est également utile que, non seulement une matrice orthogonale soit inversible, mais que son inverse soit disponible essentiellement gratuitement, en échangeant les indices.

Les permutations sont essentielles au succès de nombreux algorithmes, y compris le cheval de bataille qu’est l’élimination gaussienne avec pivotement partiel (où les permutations font le pivotement). Cependant, elles apparaissent rarement explicitement sous forme de matrices ; leur forme spéciale permet une représentation plus efficace, comme une liste de n indices.

De même, les algorithmes utilisant les matrices de Householder et de Givens utilisent généralement des méthodes spécialisées de multiplication et de stockage. Par exemple, une rotation de Givens n’affecte que deux lignes d’une matrice qu’elle multiplie, transformant une multiplication complète d’ordre n3 en une multiplication d’ordre n, beaucoup plus efficace. Lorsque les utilisations de ces réflexions et rotations introduisent des zéros dans une matrice, l’espace libéré est suffisant pour stocker suffisamment de données pour reproduire la transformation, et le faire de manière robuste. (En suivant Stewart (1976), nous ne stockons pas d’angle de rotation, ce qui est à la fois coûteux et mal conduit.)

DécompositionsEdit

Un certain nombre de décompositions matricielles importantes (Golub & Van Loan 1996) font intervenir des matrices orthogonales, dont notamment :

Décomposition QR M = QR, Q orthogonale, R triangulaire supérieure Décomposition de la valeur singulière M = UΣVT, U et V orthogonales, Σ matrice diagonale Eigendécomposition d’une matrice symétrique (décomposition selon le théorème spectral) S = QΛQT, S symétrique, Q orthogonale, Λ diagonale Décomposition polaire M = QS, Q orthogonale, S symétrique positive-semidéfinie

ExemplesEdit

Envisagez un système d’équations linéaires surdéterminé, comme cela pourrait se produire avec des mesures répétées d’un phénomène physique pour compenser les erreurs expérimentales. Écrivez Ax = b, où A est m × n, m > n.Une décomposition QR réduit A au triangle supérieur R. Par exemple, si A est 5 × 3, alors R a la forme

R = . {\displaystyle R={\begin{bmatrix}\cdot &\cdot &\cdot \0&\cdot &\cdot \0&&\cdot \\0&&&&0\end{bmatrix}}.}

Le problème linéaire des moindres carrés consiste à trouver le x qui minimise ||Ax – b||, ce qui est équivalent à projeter b dans le sous-espace couvert par les colonnes de A. En supposant que les colonnes de A (et donc R) sont indépendantes, la solution de projection est trouvée à partir de ATAx = ATb. Maintenant, ATA est carré (n × n) et inversible, et également égal à RTR. Mais les rangées inférieures de zéros dans R sont superflues dans le produit, qui est donc déjà sous forme factorisée triangulaire inférieure-triangulaire supérieure, comme dans l’élimination gaussienne (décomposition de Cholesky). Ici, l’orthogonalité est importante non seulement pour réduire ATA = (RTQT)QR à RTR, mais aussi pour permettre une solution sans amplifier les problèmes numériques.

Dans le cas d’un système linéaire sous-déterminé, ou d’une matrice autrement non inversible, la décomposition en valeurs singulières (SVD) est également utile. Avec A factorisé comme UΣVT, une solution satisfaisante utilise le pseudo-inverse de Moore-Penrose, VΣ+UT, où Σ+ remplace simplement chaque entrée diagonale non nulle par sa réciproque. Fixez x à VΣ+UTb.

Le cas d’une matrice carrée inversible présente également un intérêt. Supposons, par exemple, que A soit une matrice de rotation 3 × 3 qui a été calculée comme la composition de nombreux tours et détours. La virgule flottante ne correspondant pas à l’idéal mathématique des nombres réels, A a progressivement perdu sa véritable orthogonalité. Un processus de Gram-Schmidt pourrait orthogonaliser les colonnes, mais ce n’est pas la méthode la plus fiable, ni la plus efficace, ni la plus invariante. La décomposition polaire divise une matrice en une paire, dont l’une est l’unique matrice orthogonale la plus proche de la matrice donnée, ou l’une des plus proches si la matrice donnée est singulière. (La proximité peut être mesurée par toute norme de matrice invariante sous un changement orthogonal de base, comme la norme spectrale ou la norme de Frobenius). Pour une matrice quasi-orthogonale, une convergence rapide vers le facteur orthogonal peut être obtenue par une approche de type « méthode de Newton » due à Higham (1986) (1990), en calculant de manière répétée la moyenne de la matrice avec sa transposée inverse. Dubrulle (1994) harvtxt error : no target : CITEREFDubrulle1994 (help) a publié une méthode accélérée avec un test de convergence pratique.

Par exemple, considérons une matrice non orthogonale pour laquelle l’algorithme de moyenne simple prend sept étapes

→ ⋯ → {\displaystyle {\begin{bmatrix}3&&5\end{bmatrix}}\rightarrow {\begin{bmatrix}1.8125&&2,6875\end{bmatrix}}\rightarrow {\cdots \rightarrow {\begin{bmatrix}0.8&&0.8\end{bmatrix}}}

et dont l’accélération se réduit à deux pas (avec γ = 0,353553, 0,565685).

→ {\displaystyle {\begin{bmatrix}3&&5\end{bmatrix}}\rightarrow {\begin{bmatrix}1.41421&&1.41421\end{bmatrix}}\rightarrow {\begin{bmatrix}0.8&&0.8\end{bmatrix}}}

Gram-Schmidt donne une solution inférieure, montrée par une distance de Frobenius de 8.28659 au lieu du minimum 8,12404.

→ {\displaystyle {\begin{bmatrix}3&&5\end{bmatrix}}\rightarrow {\begin{bmatrix}0.393919&&0.393919\end{bmatrix}}}

RandomizationEdit

Certaines applications numériques, telles que les méthodes de Monte Carlo et l’exploration d’espaces de données à haute dimension, nécessitent la génération de matrices orthogonales aléatoires uniformément distribuées. Dans ce contexte, « uniforme » est défini en termes de mesure de Haar, ce qui exige essentiellement que la distribution ne change pas si elle est multipliée par toute matrice orthogonale librement choisie. L’orthogonalisation de matrices avec des entrées aléatoires indépendantes uniformément distribuées ne donne pas de matrices orthogonales uniformément distribuées, mais la décomposition QR d’entrées aléatoires indépendantes normalement distribuées le fait, tant que la diagonale de R ne contient que des entrées positives (Mezzadri 2006). Stewart (1980) a remplacé cela par une idée plus efficace que Diaconis & Shahshahani (1987) a plus tard généralisé sous le nom d' »algorithme de sous-groupe » (sous quelle forme il fonctionne tout aussi bien pour les permutations et les rotations). Pour générer une matrice orthogonale (n + 1) × (n + 1), prenez une matrice n × n et un vecteur unitaire uniformément distribué de dimension n + 1. Construisez une réflexion de Householder à partir du vecteur, puis appliquez-la à la plus petite matrice (intégrée dans la plus grande dimension avec un 1 dans le coin inférieur droit).

Matrice orthogonale la plus procheEdit

Le problème de la recherche de la matrice orthogonale Q la plus proche d’une matrice M donnée est lié au problème de Procrustes orthogonal. Il existe plusieurs façons différentes d’obtenir la solution unique, la plus simple étant de prendre la décomposition en valeurs singulières de M et de remplacer les valeurs singulières par des uns. Une autre méthode exprime explicitement le R mais nécessite l’utilisation d’une racine carrée matricielle:

Q = M ( M T M ) – 1 2 {\displaystyle Q=M\left(M^{\mathrm {T} }M\right)^{-{\frac {1}{2}}}}

Ceci peut être combiné avec la méthode babylonienne d’extraction de la racine carrée d’une matrice pour donner une récurrence qui converge vers une matrice orthogonale de manière quadratique :

Q n + 1 = 2 M ( Q n – 1 M + M T Q n ) – 1 {\displaystyle Q_{n+1}=2M\left(Q_{n}^{-1}M+M^{\mathrm {T} }Q_{n}\right)^{-1}}