Orthogonale matrix

Voordelen

Numerieke analyse maakt gebruik van veel van de eigenschappen van orthogonale matrices voor numerieke lineaire algebra, en ze ontstaan op natuurlijke wijze. Het is bijvoorbeeld vaak wenselijk om een orthonormale basis voor een ruimte te berekenen, of een orthogonale verandering van bases; beide hebben de vorm van orthogonale matrices. Het hebben van determinant ±1 en alle eigenwaarden van grootte 1 is van groot voordeel voor de numerieke stabiliteit. Een van de implicaties is dat het voorwaardengetal 1 is (wat het minimum is), zodat fouten niet worden vergroot bij vermenigvuldiging met een orthogonale matrix. Veel algoritmen gebruiken om deze reden orthogonale matrices zoals Householder reflecties en Givens rotaties. Het is ook handig dat een orthogonale matrix niet alleen inverteerbaar is, maar dat zijn inverse in principe gratis beschikbaar is, door het uitwisselen van indexen.

Permutaties zijn essentieel voor het succes van veel algoritmen, waaronder het werkpaard Gaussische eliminatie met partiële pivotering (waarbij permutaties de pivotering doen). Ze verschijnen echter zelden expliciet als matrices; hun speciale vorm maakt een efficiëntere representatie mogelijk, zoals een lijst van n indices.

Ook algoritmen die gebruik maken van Householder en Givens matrices gebruiken meestal gespecialiseerde methoden voor vermenigvuldiging en opslag. Zo heeft een Givens rotatie slechts invloed op twee rijen van een matrix die wordt vermenigvuldigd, waardoor een volledige vermenigvuldiging van orde n3 verandert in een veel efficiëntere orde n. Wanneer door het gebruik van deze reflecties en rotaties nullen in een matrix worden geïntroduceerd, is de vrijgekomen ruimte voldoende om voldoende gegevens op te slaan om de transformatie te reproduceren, en om dat op een robuuste manier te doen. (In navolging van Stewart (1976) slaan we geen rotatiehoek op, die zowel duur als slecht is.)

Ontbindingen

Een aantal belangrijke matrixontbindingen (Golub & Van Loan 1996) hebben betrekking op orthogonale matrices, waaronder met name:

QR-decompositie M = QR, Q orthogonaal, R bovendriehoekig Singuliere waardedecompositie M = UΣVT, U en V orthogonaal, Σ diagonaalmatrix Eigendecompositie van een symmetrische matrix (decompositie volgens de spectrale stelling) S = QΛQT, S symmetrisch, Q orthogonaal, Λ diagonaal Poolse ontbinding M = QS, Q orthogonaal, S symmetrisch positief-half-eindig

Voorbeelden

Bedenk een stelsel lineaire vergelijkingen dat overgedetermineerd is, zoals dat kan voorkomen bij herhaalde metingen aan een natuurkundig verschijnsel om experimentele fouten te compenseren. Schrijf Ax = b, waarbij A m × n is, m > n.Een QR-decompositie herleidt A tot bovendriehoekige R. Bijvoorbeeld, als A 5 × 3 is dan heeft R de vorm

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

Het lineaire kleinste kwadraten probleem is om de x te vinden die ||Ax – b| minimaliseert, wat gelijk staat aan het projecteren van b op de deelruimte die door de kolommen van A wordt opgespannen. Aangenomen dat de kolommen van A (en dus R) onafhankelijk zijn, wordt de projectie-oplossing gevonden uit ATAx = ATb. Nu is ATA vierkant (n × n) en inverteerbaar, en ook gelijk aan RTR. Maar de onderste rijen nullen in R zijn overbodig in het product, dat dus al in onder-driehoekige boven-driehoekige verbeelde vorm is, zoals in Gaussische eliminatie (Cholesky-ontleding). Hier is orthogonaliteit belangrijk, niet alleen om ATA = (RTQT)QR te herleiden tot RTR, maar ook om een oplossing mogelijk te maken zonder numerieke problemen uit te vergroten.

In het geval van een lineair stelsel dat onderbepaald is, of een anderszins niet-inverteerbare matrix, is singuliere-waardeontleding (SVD) evenzeer nuttig. Met A gefactureerd als UΣVT wordt voor een bevredigende oplossing gebruik gemaakt van de Moore-Penrose pseudoinverse, VΣ+UT, waarbij Σ+ slechts elke niet-nul diagonaalaanduiding vervangt door zijn reciproke. Stel x in op VΣ+UTb.

Het geval van een vierkante inverteerbare matrix is ook interessant. Stel bijvoorbeeld dat A een 3 × 3 rotatiematrix is die is berekend als de samenstelling van een groot aantal draaiingen. Zwevend komma komt niet overeen met het wiskundige ideaal van reële getallen, zodat A geleidelijk zijn werkelijke orthogonaliteit heeft verloren. Een Gram-Schmidt-proces zou de kolommen kunnen orthogonaliseren, maar het is niet de meest betrouwbare, noch de meest efficiënte, noch de meest invariante methode. De polaire decompositie ontbindt een matrix in een paar, waarvan er één de unieke orthogonale matrix is die het dichtst bij de gegeven matrix ligt, of één van de dichtstbijzijnde als de gegeven matrix singulier is. (De mate van overeenkomst kan worden gemeten aan de hand van elke matrixnorm die invariant is onder een orthogonale verandering van basis, zoals de spectrale norm of de Frobenius-norm). Voor een bijna orthogonale matrix kan een snelle convergentie naar de orthogonale factor worden bereikt met de “Newton’s methode” van Higham (1986) (1990), waarbij de matrix herhaaldelijk wordt gemiddeld met zijn inverse transpositie. Dubrulle (1994) harvtxt fout: geen doel: CITEREFDubrulle1994 (help) heeft een versnelde methode gepubliceerd met een handige convergentietest.

Bedenk bijvoorbeeld een niet-orthogonale matrix waarvoor het eenvoudige middelalgoritme zeven stappen vergt

→ ⋯ → {{{bmatrix}3&&&&&5 {{bmatrix}}}}8125&&&2.6875 {{bmatrix}}}rightarrow {{bmatrix}}0.8&&0.8\end{bmatrix}}}

en die de versnelling afvlakt tot twee stappen (met γ = 0,353553, 0,565685).

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

Gram-Schmidt levert een inferieure oplossing, blijkens een Frobenius-afstand van 8.28659 in plaats van de minimale 8.12404.

→ {Displaystyle {begin{bmatrix}3&&5eind{bmatrix}} 1&5393919&&0.393919\end{bmatrix}}}

RandomisatieEdit

Enkele numerieke toepassingen, zoals Monte Carlo methoden en exploratie van hoog-dimensionale data ruimtes, vereisen het genereren van uniform verdeelde willekeurige orthogonale matrices. In deze context wordt “uniform” gedefinieerd in termen van de Haar maat, die in essentie vereist dat de verdeling niet verandert als ze vermenigvuldigd wordt met een vrij gekozen orthogonale matrix. Orthogonaliseren van matrices met onafhankelijke uniform verdeelde willekeurige ingangen levert geen uniform verdeelde orthogonale matrices op, maar de QR-decompositie van onafhankelijke normaal verdeelde willekeurige ingangen wel, zolang de diagonaal van R alleen positieve ingangen bevat (Mezzadri 2006). Stewart (1980) verving dit door een efficiënter idee dat Diaconis & Shahshahani (1987) later veralgemeende als het “subgroep algoritme” (in welke vorm het net zo goed werkt voor permutaties en rotaties). Om een (n + 1) × (n + 1) orthogonale matrix te verkrijgen, neemt men een n × n en een uniform verdeelde eenheidsvector van dimensie n + 1. Construeer een Householder-reflectie uit de vector, en pas die dan toe op de kleinere matrix (ingebed in de grotere maat met een 1 rechtsonder).

Dichtstbijzijnde orthogonale matrixEdit

Het probleem om de orthogonale matrix Q te vinden die het dichtst bij een gegeven matrix M ligt, is verwant aan het Orthogonale Procrustes-probleem. Er zijn verschillende manieren om de unieke oplossing te vinden, waarvan de eenvoudigste is de singuliere waarde-ontleding van M te nemen en de singuliere waarden door enen te vervangen. Een andere methode drukt de R expliciet uit, maar vereist het gebruik van een matrix vierkantswortel:

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

Dit kan gecombineerd worden met de Babylonische methode om de vierkantswortel van een matrix te extraheren om een recurrentie te krijgen die kwadratisch convergeert naar een orthogonale matrix:

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