Esiste un modo semplice per invertire una matrice triangolare (superiore o inferiore)?

Question

Sto cercando di implementare alcune operazioni di algebra lineare di base e una di queste operazioni è l'inversione di una matrice triangolare (superiore e / o inferiore). Esiste un algoritmo semplice e stabile per farlo?

Grazie.

Answer 1

Sì, usa sostituzione posteriore . Un algoritmo standard per invertire una matrice è quello di trovare la sua decomposizione LU (decomposizione in una matrice triangolare inferiore e una triangolare superiore), utilizzare la sostituzione secondaria sui pezzi triangolari e quindi combinare i risultati per ottenere l'inverso della matrice originale.

Answer 2

Non capovolgerlo se puoi. È uno dei comandamenti di base dell'algebra lineare numerica.

È molto più veloce e numericamente più stabile mantenere in memoria la matrice L stessa e calcolare

inv(L)b

con la sostituzione di ritorno ogni volta che è necessario fare qualcos'altro con inv (L).

Nota che l'algoritmo abituale per invertirlo richiede di risolvere i sistemi

inv(L)[1 0 0 ...],
inv(L)[0 1 0 ....],
inv(L)[0 0 1 ....]

e così via, quindi vedi che è molto più facile non invertire affatto.

Answer 3

Data una matrice triangolare inferiore L, backsubstitution consente di risolvere il sistema L x = b rapidamente per qualsiasi lato destro b.

Per invertire L, è possibile risolvere questo sistema per i lati destri e1 = (1,0, ..., 0), e2 = (0,1, ..., 0), ..., en = (0,0, ..., 1) e combina i vettori della soluzione risultante in un'unica matrice (necessariamente triangolare inferiore).

Se sei interessato a una soluzione a forma chiusa, gli elementi diagonali dell'inverso sono gli inversi degli elementi diagonali originali e la formula per il resto degli elementi dell'inverso diventa sempre più complicata mentre ti muovi sempre dalla diagonale.

Answer 4

Se stai parlando di singoli reali di precisione, dai un'occhiata al codice sorgente per le routine LAPACK STRTRI e STRTI2 .

Answer 5

Wow, questo è praticamente la metà dei contenuti di un corso di analisi numerica. Gli algoritmi standard lo faranno, e c'è un sacco di codice fisso qui . La fonte finale di questo e altri soliti problemi di analisi numerica è Ricette numeriche .