Divisione matrice - Matrix splitting

Nella disciplina matematica dell'algebra lineare numerica , una suddivisione di matrici è un'espressione che rappresenta una data matrice come somma o differenza di matrici. Molti metodi iterativi (ad esempio, per sistemi di equazioni differenziali ) dipendono dalla soluzione diretta di equazioni matriciali che coinvolgono matrici più generali delle matrici tridiagonali . Queste equazioni matriciali possono spesso essere risolte in modo diretto ed efficiente se scritte come suddivisione di matrici. La tecnica è stata ideata da Richard S. Varga nel 1960.

Spaccature regolari

Cerchiamo di risolvere l' equazione della matrice

${\displaystyle \mathbf {A} \mathbf {x} =\mathbf {k},}$

( 1 )

dove A è una data matrice n × n non singolare e k è un dato vettore colonna con n componenti. Dividiamo la matrice A in

${\displaystyle \mathbf {A} =\mathbf {B} -\mathbf {C},}$

( 2 )

dove B e C sono matrici n × n . Se, per una matrice arbitraria n × n M , M ha elementi non negativi, scriviamo M ≥ 0 . Se M ha solo elementi positivi, scriviamo M > 0 . Analogamente, se la matrice M ₁ − M ₂ ha elementi non negativi, scriviamo M ₁ ≥ M ₂ .

Definizione: A = B − C è una divisione regolare di A se B ⁻¹ ≥ 0 e C ≥ 0 .

Assumiamo che equazioni matriciali della forma

${\displaystyle \mathbf {B} \mathbf {x} =\mathbf {g},}$

( 3 )

dove g è un dato vettore colonna, può essere risolto direttamente per il vettore x . Se ( 2 ) rappresenta una suddivisione regolare di A , allora il metodo iterativo

${\displaystyle \mathbf {B} \mathbf {x} ^{(m+1)}=\mathbf {C} \mathbf {x} ^{(m)}+\mathbf {k},\quad m=0 ,1,2,\ldots ,}$

( 4 )

dove x ⁽⁰⁾ è un vettore arbitrario, può essere eseguito. Equivalentemente, scriviamo ( 4 ) nella forma

${\displaystyle \mathbf {x} ^{(m+1)}=\mathbf {B} ^{-1}\mathbf {C} \mathbf {x} ^{(m)}+\mathbf {B} ^ {-1}\mathbf {k},\quad m=0,1,2,\ldots}$

( 5 )

La matrice D = B ⁻¹ C ha elementi non negativi se ( 2 ) rappresenta una suddivisione regolare di A .

Si può dimostrare che se A ⁻¹ > 0 , allora < 1, dove rappresenta il raggio spettrale di D , e quindi D è una matrice convergente . Di conseguenza, il metodo iterativo ( 5 ) è necessariamente convergente . ${\displaystyle \rho (\mathbf {D} )}$${\displaystyle \rho (\mathbf {D} )}$

Se, inoltre, si sceglie lo sdoppiamento ( 2 ) in modo che la matrice B sia diagonale (con gli elementi diagonali tutti diversi da zero, poiché B deve essere invertibile ), allora B può essere invertito in tempo lineare (vedi Complessità ).

Metodi iterativi di matrice

Molti metodi iterativi possono essere descritti come suddivisione di matrici. Se gli elementi diagonali della matrice A sono tutti diversi da zero, ed esprimiamo la matrice A come somma matriciale

${\displaystyle \mathbf {A} =\mathbf {D} -\mathbf {U} -\mathbf {L},}$

( 6 )

dove D è la parte diagonale di A , e U e L sono rispettivamente matrici strettamente triangolari superiori e inferiori n × n , allora abbiamo la seguente.

Il metodo Jacobi può essere rappresentato in forma matriciale come una scissione

${\displaystyle \mathbf {x} ^{(m+1)}=\mathbf {D} ^{-1}(\mathbf {U} +\mathbf {L})\mathbf {x} ^{(m) }+\mathbf {D} ^{-1}\mathbf {k} .}$

( 7 )

Il metodo di Gauss-Seidel può essere rappresentato in forma matriciale come una scissione

${\displaystyle \mathbf {x} ^{(m+1)}=(\mathbf {D} -\mathbf {L} )^{-1}\mathbf {U} \mathbf {x} ^{(m) }+(\mathbf {D} -\mathbf {L} )^{-1}\mathbf {k} .}$

( 8 )

Il metodo del successivo iper-rilassamento può essere rappresentato in forma matriciale come una scissione

${\displaystyle \mathbf {x} ^{(m+1)}=(\mathbf {D} -\omega \mathbf {L} )^{-1}[(1-\omega )\mathbf {D} + \omega \mathbf {U}]\mathbf {x} ^{(m)}+\omega (\mathbf {D} -\omega \mathbf {L})^{-1}\mathbf {k} .}$

( 9 )

Esempio

Divisione regolare

Nell'equazione ( 1 ), sia

${\displaystyle \mathbf {A} ={\begin{pmatrix}6&-2&-3\\-1&4&-2\\-3&-1&5\end{pmatrix}},\quad \mathbf {k} ={\begin {pmatrix}5\\-12\\10\end{pmatrix}}.}$

( 10 )

Applichiamo lo sdoppiamento ( 7 ) che si usa nel metodo Jacobi: dividiamo A in modo che B sia costituito da tutti gli elementi diagonali di A , e C costituito da tutti gli elementi fuori diagonali di A , negati . (Naturalmente questo non è l'unico modo utile per dividere una matrice in due matrici.) Abbiamo

${\displaystyle {\begin{allineato}&\mathbf {B} ={\begin{pmatrix}6&0&0\\0&4&0\\0&0&5\end{pmatrix}},\quad \mathbf {C} ={\begin{pmatrix} 0&2&3\\1&0&2\\3&1&0\end{pmatrix}},\end{allineato}}}$

( 11 )

${\displaystyle {\begin{allineato}&\mathbf {A^{-1}} ={\frac {1}{47}}{\begin{pmatrix}18&13&16\\11&21&15\\13&12&22\end{pmatrix}} ,\quad \mathbf {B^{-1}} ={\begin{pmatrix}{\frac {1}{6}}&0&0\\[4pt]0&{\frac {1}{4}}&0\\ [4pt]0&0&{\frac {1}{5}}\end{pmatrix}},\end{allineato}}}$

${\displaystyle {\begin{allineato}\mathbf {D} =\mathbf {B^{-1}C} ={\begin{pmatrix}0&{\frac {1}{3}}&{\frac {1 }{2}}\\[4pt]{\frac {1}{4}}&0&{\frac {1}{2}}\\[4pt]{\frac {3}{5}}&{\frac {1}{5}}&0\end{pmatrix}},\quad \mathbf {B^{-1}k} ={\begin{pmatrix}{\frac {5}{6}}\\[4pt] -3\\[4pt]2\end{pmatrix}}.\end{allineato}}}$

Poiché B ⁻¹ ≥ 0 e C ≥ 0 , la scissione ( 11 ) è una scissione regolare. Poiché A ⁻¹ > 0 , il raggio spettrale < 1. (Gli autovalori approssimati di D sono ) Quindi, la matrice D è convergente e il metodo ( 5 ) converge necessariamente per il problema ( 10 ). Nota che gli elementi diagonali di A sono tutti maggiori di zero, gli elementi fuori diagonale di A sono tutti minori di zero e A è strettamente diagonalmente dominante . ${\displaystyle \rho (\mathbf {D} )}$${\displaystyle \lambda _{i}\circa -0.4599820, -0.3397859,0.7997679.}$

Il metodo ( 5 ) applicato al problema ( 10 ) assume quindi la forma

${\displaystyle \mathbf {x} ^{(m+1)}={\begin{pmatrix}0&{\frac {1}{3}}&{\frac {1}{2}}\\[4pt] {\frac {1}{4}}&0&{\frac {1}{2}}\\[4pt]{\frac {3}{5}}&{\frac {1}{5}}&0\end {pmatrix}}\mathbf {x} ^{(m)}+{\begin{pmatrix}{\frac {5}{6}}\\[4pt]-3\\[4pt]2\end{pmatrix} },\quad m=0,1,2,\ldots }$

( 12 )

La soluzione esatta dell'equazione ( 12 ) è

${\displaystyle \mathbf {x} ={\begin{pmatrix}2\\-1\\3\end{pmatrix}}.}$

( 13 )

Le prime iterazioni per l'equazione ( 12 ) sono elencate nella tabella seguente, iniziando con x ⁽⁰⁾ = (0.0, 0.0, 0.0) ^T . Dalla tabella si vede che il metodo sta evidentemente convergendo alla soluzione ( 13 ), seppur piuttosto lentamente.

${\displaystyle x_{1}^{(m)}}$	${\displaystyle x_{2}^{(m)}}$	${\displaystyle x_{3}^{(m)}}$
0.0	0.0	0.0
0.83333	-30.000	2.0000
0.83333	-1.7917	1.9000
1.1861	-1,8417	2.1417
1.2903	-1,6326	2.3433
1.4608	-1.5058	2.4477
1.5553	-1.4110	2.5753
1.6507	-1.3235	2.6510
1.7177	-1.2618	2.7257
1.7756	-1.2077	2.7783
1.8199	-1.1670	2.8238

metodo Jacobi

Come affermato in precedenza, il metodo Jacobi ( 7 ) è lo stesso della suddivisione regolare specifica ( 11 ) dimostrata sopra.

Metodo di Gauss-Seidel

Poiché gli elementi diagonali della matrice A nel problema ( 10 ) sono tutti diversi da zero, possiamo esprimere la matrice A come la scissione ( 6 ), dove

${\displaystyle \mathbf {D} ={\begin{pmatrix}6&0&0\\0&4&0\\0&0&5\end{pmatrix}},\quad \mathbf {U} ={\begin{pmatrix}0&2&3\\0&0&2\\0&0&0 \end{pmatrix}},\quad \mathbf {L} ={\begin{pmatrix}0&0&0\\1&0&0\\3&1&0\end{pmatrix}}.}$

( 14 )

Abbiamo quindi

${\displaystyle {\begin{allineato}&\mathbf {(DL)^{-1}} ={\frac {1}{120}}{\begin{pmatrix}20&0&0\\5&30&0\\13&6&24\end{pmatrix }},\end{allineato}}}$

${\displaystyle {\begin{allineato}&\mathbf {(DL)^{-1}U} ={\frac {1}{120}}{\begin{pmatrix}0&40&60\\0&10&75\\0&26&51\end{ pmatrix}},\quad \mathbf {(DL)^{-1}k} ={\frac {1}{120}}{\begin{pmatrix}100\\-335\\233\end{pmatrix}} .\end{allineato}}}$

Il metodo di Gauss-Seidel ( 8 ) applicato al problema ( 10 ) assume la forma

${\displaystyle \mathbf {x} ^{(m+1)}={\frac {1}{120}}{\begin{pmatrix}0&40&60\\0&10&75\\0&26&51\end{pmatrix}}\mathbf {x } ^{(m)}+{\frac {1}{120}}{\begin{pmatrix}100\\-335\\233\end{pmatrix}},\quad m=0,1,2,\ ldot }$

( 15 )

Le prime iterazioni per l'equazione ( 15 ) sono elencate nella tabella seguente, iniziando con x ⁽⁰⁾ = (0.0, 0.0, 0.0) ^T . Dalla tabella si vede che il metodo sta evidentemente convergendo alla soluzione ( 13 ), un po' più velocemente del metodo Jacobi sopra descritto.

${\displaystyle x_{1}^{(m)}}$	${\displaystyle x_{2}^{(m)}}$	${\displaystyle x_{3}^{(m)}}$
0.0	0.0	0.0
0,8333	-2.7917	1.9417
0.8736	-1.8107	2.1620
1.3108	-1.5913	2.4682
1.5370	-1.3817	2.6459
1.6957	-1,2531	2.7668
1.7990	-1.1668	2.8461
1.8675	-1.1101	2.8985
1.9126	-1.0726	2.9330
1.9423	-1.0479	2.9558
1.9619	-1.0316	2.9708

Metodo di iper-rilassamento successivo

Lasciate ω = 1.1. Usando lo sdoppiamento ( 14 ) della matrice A nel problema ( 10 ) per il successivo metodo del sovrarilassamento, si ha

${\displaystyle {\begin{allineato}&\mathbf {(D-\omega L)^{-1}} ={\frac {1}{12}}{\begin{pmatrix}2&0&0\\0.55&3&0\\ 1.441&0.66&2.4\end{pmatrix}},\end{allineato}}}$

${\displaystyle {\begin{allineato}&\mathbf {(D-\omega L)^{-1}[(1-\omega)D+\omega U]} ={\frac {1}{12}}{ \begin{pmatrix}-1.2&4.4&6.6\\-0.33&0.01&8.415\\-0.8646&2.9062&5.0073\end{pmatrix}},\end{allineato}}}$

${\displaystyle {\begin{allineato}&\mathbf {\omega (D-\omega L)^{-1}k} ={\frac {1}{12}}{\begin{pmatrix}11\\- 36.575\\25.6135\end{pmatrix}}.\end{allineato}}}$

Il successivo metodo di iper-rilassamento ( 9 ) applicato al problema ( 10 ) assume la forma

${\displaystyle \mathbf {x} ^{(m+1)}={\frac {1}{12}}{\begin{pmatrix}-1.2&4.4&6.6\\-0.33&0.01&8.415\ \-0.8646&2.9062&5.0073\end{pmatrix}}\mathbf {x} ^{(m)}+{\frac {1}{12}}{\begin{pmatrix}11\\-36.575\\25.6135 \end{pmatrix}},\quad m=0,1,2,\ldots}$

( 16 )

Le prime iterazioni per l'equazione ( 16 ) sono elencate nella tabella seguente, iniziando con x ⁽⁰⁾ = (0.0, 0.0, 0.0) ^T . Dalla tabella si vede che il metodo sta evidentemente convergendo alla soluzione ( 13 ), leggermente più veloce del metodo di Gauss–Seidel sopra descritto.

${\displaystyle x_{1}^{(m)}}$	${\displaystyle x_{2}^{(m)}}$	${\displaystyle x_{3}^{(m)}}$
0.0	0.0	0.0
0,9167	-3.0479	2.1345
0.8814	-1.5788	2.2209
1.4711	-1.5161	2.6153
1.6521	-1,2557	2.7526
1.8050	-1,1641	2.8599
1.8823	-1.0930	2.9158
1.9314	-1.0559	2.9508
1.9593	-1.0327	2.9709
1.9761	-1.0185	2.9829
1.9862	-1.0113	2.9901

Guarda anche

• Elenco degli argomenti di suddivisione degli operatori
• Decomposizione della matrice
• matrice M
• matrice di Stieltjes

Appunti

Riferimenti

• onere, Richard L.; Faires, J. Douglas (1993), Analisi numerica (5a ed.), Boston: Prindle, Weber e Schmidt , ISBN 0-534-93219-3.
• Varga, Richard S. (1960). "Factorizzazione e metodi iterativi normalizzati". In Langer, Rudolph E. (a cura di). Problemi al contorno nelle equazioni differenziali . Madison: Pressa dell'Università del Wisconsin . pp. 121-142. LCCN  60-60003 .
• Varga, Richard S. (1962), Analisi iterativa della matrice , New Jersey: Prentice-Hall , LCCN  62-21277.