Matrice ortogonale

BeneficiModifica

L’analisi numerica sfrutta molte delle proprietà delle matrici ortogonali per l’algebra lineare numerica, ed esse sorgono naturalmente. Per esempio, è spesso desiderabile calcolare una base ortonormale per uno spazio, o un cambio ortogonale di basi; entrambi prendono la forma di matrici ortogonali. Avere determinante ±1 e tutti gli autovalori di grandezza 1 è di grande beneficio per la stabilità numerica. Un’implicazione è che il numero di condizione è 1 (che è il minimo), quindi gli errori non sono amplificati quando si moltiplica con una matrice ortogonale. Molti algoritmi usano matrici ortogonali come le riflessioni di Householder e le rotazioni di Givens per questa ragione. È anche utile che, non solo una matrice ortogonale è invertibile, ma il suo inverso è disponibile essenzialmente gratis, scambiando gli indici.

Le permutazioni sono essenziali per il successo di molti algoritmi, incluso il cavallo di battaglia dell’eliminazione gaussiana con pivoting parziale (dove le permutazioni fanno il pivoting). Tuttavia, raramente appaiono esplicitamente come matrici; la loro forma speciale permette una rappresentazione più efficiente, come una lista di n indici.

Similmente, gli algoritmi che usano le matrici di Householder e Givens usano tipicamente metodi specializzati di moltiplicazione e memorizzazione. Per esempio, una rotazione Givens influenza solo due righe di una matrice che moltiplica, cambiando una moltiplicazione completa di ordine n3 in una molto più efficiente di ordine n. Quando l’uso di queste riflessioni e rotazioni introduce degli zeri in una matrice, lo spazio liberato è sufficiente per memorizzare dati sufficienti a riprodurre la trasformazione, e a farlo in modo robusto. (Seguendo Stewart (1976), non memorizziamo l’angolo di rotazione, che è sia costoso che mal gestito.)

DecomposizioniModifica

Un certo numero di importanti decomposizioni di matrici (Golub & Van Loan 1996) coinvolgono matrici ortogonali, tra cui specialmente:

Decomposizione QR M = QR, Q ortogonale, R triangolare superiore Decomposizione del valore singolare M = UΣVT, U e V ortogonali, Σ matrice diagonale Eigendecomposizione di una matrice simmetrica (decomposizione secondo il teorema spettrale) S = QΛQT, S simmetrica, Q ortogonale, Λ diagonale Decomposizione polare M = QS, Q ortogonale, S simmetrica positiva-semidefinita

EsempiModifica

Consideriamo un sistema sovradeterminato di equazioni lineari, come potrebbe accadere con misure ripetute di un fenomeno fisico per compensare gli errori sperimentali. Scrivi Ax = b, dove A è m × n, m > n.Una decomposizione QR riduce A al triangolo superiore R. Per esempio, se A è 5 × 3 allora R ha la forma

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

Il problema lineare dei minimi quadrati è quello di trovare la x che minimizza ||Ax – b|||, che è equivalente a proiettare b nel sottospazio attraversato dalle colonne di A. Assumendo che le colonne di A (e quindi R) siano indipendenti, la soluzione di proiezione si trova da ATAx = ATb. Ora ATA è quadrata (n × n) e invertibile, e anche uguale a RTR. Ma le file inferiori di zeri in R sono superflue nel prodotto, che è quindi già in forma fattorizzata inferiore-triangolare superiore-triangolare, come nell’eliminazione gaussiana (decomposizione di Cholesky). Qui l’ortogonalità è importante non solo per ridurre ATA = (RTQT)QR a RTR, ma anche per permettere la soluzione senza ingrandire i problemi numerici.

Nel caso di un sistema lineare che è sottodeterminato, o di una matrice altrimenti non invertibile, la decomposizione dei valori singolari (SVD) è altrettanto utile. Con A fattorizzata come UΣVT, una soluzione soddisfacente utilizza la pseudoinversa di Moore-Penrose, VΣ+UT, dove Σ+ sostituisce semplicemente ogni voce diagonale non nulla con il suo reciproco. Imposta x a VΣ+UTb.

Anche il caso di una matrice quadrata invertibile è interessante. Supponiamo, per esempio, che A sia una matrice di rotazione 3 × 3 che è stata calcolata come composizione di numerose torsioni e giri. La virgola mobile non corrisponde all’ideale matematico dei numeri reali, quindi A ha gradualmente perso la sua vera ortogonalità. Un processo di Gram-Schmidt potrebbe ortogonalizzare le colonne, ma non è il metodo più affidabile, né il più efficiente, né il più invariante. La decomposizione polare fattorizza una matrice in una coppia, una delle quali è l’unica matrice ortogonale più vicina alla matrice data, o una delle più vicine se la matrice data è singolare. (La vicinanza può essere misurata da qualsiasi norma di matrice invariante sotto un cambio ortogonale di base, come la norma spettrale o la norma di Frobenius). Per una matrice quasi-ortogonale, una rapida convergenza al fattore ortogonale può essere ottenuta con un approccio “metodo di Newton” dovuto a Higham (1986) (1990), facendo ripetutamente la media della matrice con la sua trasposizione inversa. Dubrulle (1994) harvtxt errore: nessun obiettivo: CITEREFDubrulle1994 (help) ha pubblicato un metodo accelerato con un comodo test di convergenza.

Per esempio, si consideri una matrice non ortogonale per la quale il semplice algoritmo di mediazione richiede sette passi

→ → ⋯ → {displaystyle {begin{bmatrix}3&&5\end{bmatrix}}}diritto {begin{bmatrix}1.8125&&2.6875\end{bmatrix}}}diritto d’autore \punti \diritto d’autore {begin{bmatrix}0.8&&0.8\end{bmatrix}}}

e che l’accelerazione si riduce a due passi (con γ = 0.353553, 0.565685).

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

Gram-Schmidt produce una soluzione inferiore, indicata da una distanza Frobenius di 8.28659 invece del minimo di 8.12404.

→ {\displaystyle {begin{bmatrix}3& 1\code(01)7&5\end{bmatrix}\rightarrow {begin{bmatrix}0.393919&&0.393919\end{bmatrix}}}

RandomizationEdit

Alcune applicazioni numeriche, come i metodi Monte Carlo e l’esplorazione di spazi di dati ad alta dimensione, richiedono la generazione di matrici ortogonali casuali uniformemente distribuite. In questo contesto, “uniforme” è definito in termini di misura di Haar, che richiede essenzialmente che la distribuzione non cambi se moltiplicata per qualsiasi matrice ortogonale liberamente scelta. Ortogonalizzare matrici con voci casuali indipendenti uniformemente distribuite non porta a matrici ortogonali uniformemente distribuite, ma la decomposizione QR di voci casuali indipendenti normalmente distribuite lo fa, purché la diagonale di R contenga solo voci positive (Mezzadri 2006). Stewart (1980) ha sostituito questo con un’idea più efficiente che Diaconis & Shahshahani (1987) ha poi generalizzato come “algoritmo del sottogruppo” (in cui forma funziona altrettanto bene per permutazioni e rotazioni). Per generare una matrice (n + 1) × (n + 1) ortogonale, prendere una matrice n × n e un vettore unitario uniformemente distribuito di dimensione n + 1. Costruisci una riflessione Householder dal vettore, poi applicala alla matrice più piccola (incorporata nella dimensione più grande con un 1 in basso a destra).

Matrice ortogonale più vicinaModifica

Il problema di trovare la matrice ortogonale Q più vicina a una data matrice M è legato al problema di Procuste ortogonale. Ci sono diversi modi per ottenere la soluzione unica, il più semplice dei quali è prendere la decomposizione dei valori singolari di M e sostituire i valori singolari con uno. Un altro metodo esprime la R esplicitamente ma richiede l’uso di una radice quadrata della matrice:

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

Questo può essere combinato con il metodo babilonese per estrarre la radice quadrata di una matrice per dare una ricorrenza che converge ad una matrice ortogonale quadraticamente:

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}}