Podział macierzy

W matematycznej dyscyplinie numerycznej algebry liniowej podział macierzy jest wyrażeniem, które reprezentuje daną macierz jako sumę lub różnicę macierzy. Wiele metod iteracyjnych (na przykład dla układów równań różniczkowych ) zależy od bezpośredniego rozwiązania równań macierzowych obejmujących macierze bardziej ogólne niż macierze trójdiagonalne . Te równania macierzowe często można rozwiązać bezpośrednio i wydajnie, gdy są zapisywane jako podział macierzy. Technika została opracowana przez Richarda S. Vargę w 1960 roku.

Regularne podziały

Staramy się rozwiązać równanie macierzowe

${\ Displaystyle \ mathbf {A} \ mathbf {x} = \ mathbf {k}}$

 

 

 

 

()

gdzie A to dana macierz nieosobliwa n × n , a k to dany wektor kolumnowy z n składnikami. Podzieliliśmy macierz A na

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

 

 

 

 

()

00 gdzie B i C to macierze n × n . Jeśli dla dowolnej macierzy n × n M , M ma wpisy nieujemne, piszemy M ≥ . Jeśli M ma tylko dodatnie wpisy, piszemy M > . Podobnie, jeśli macierz M ₁ − M ₂ ma wpisy nieujemne, piszemy M ₁ ≥ M ₂ .

00 Definicja: A = B − C jest regularnym podziałem A, jeśli B ⁻¹ ≥ i C ≥ .

Zakładamy, że równania macierzowe postaci

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

 

 

 

 

()

gdzie g jest danym wektorem kolumnowym, można rozwiązać bezpośrednio dla wektora x . Jeśli ( 2 ) reprezentuje regularne dzielenie A , to metoda iteracyjna

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

 

 

 

 

()

gdzie x ⁽⁰⁾ jest dowolnym wektorem, można przeprowadzić. Równoważnie piszemy ( 4 ) w postaci

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

 

 

 

 

()

Macierz D = B ⁻¹ C ma wpisy nieujemne, jeśli ( 2 ) reprezentuje regularne dzielenie A .

0 Można wykazać, że jeśli ZA ^-1 > , to ${\ Displaystyle \ rho (\ mathbf {D})}$ <1, gdzie ${\ Displaystyle \ rho (\ mathbf {D})}$ reprezentuje promień widmowy D , a zatem D jest macierzą zbieżną . W konsekwencji metoda iteracyjna ( 5 ) jest koniecznie zbieżna .

Jeśli dodatkowo podział ( 2 ) zostanie wybrany w taki sposób, że macierz B jest macierzą diagonalną (wszystkie elementy na przekątnej są niezerowe, ponieważ B musi być odwracalna ), to B można odwrócić w czasie liniowym (patrz Złożoność czasowa ).

Macierzowe metody iteracyjne

Wiele metod iteracyjnych można opisać jako dzielenie macierzy. Jeśli przekątne wpisów macierzy A są wszystkie niezerowe i wyrażamy macierz A jako sumę macierzy

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

 

 

 

 

()

gdzie D jest ukośną częścią A , a U i L są odpowiednio ściśle górnymi i dolnymi trójkątnymi macierzami n × n , to mamy następujące.

Metodę Jacobiego można przedstawić w postaci macierzowej jako podział

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

 

 

 

 

()

Gaussa – Seidela można przedstawić w postaci macierzy jako podział

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

 

 

 

 

()

Metodę sukcesywnej nadmiernej relaksacji można przedstawić w postaci macierzowej jako rozszczepienie

${\ 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} .}$

 

 

 

 

()

Przykład

Regularne dzielenie

W równaniu ( 1 ) niech

${\ Displaystyle \ mathbf {A} = {\ rozpocząć {pmatrix} 6&-2&-3 \\-1&4&-2\\-3&-1&5\end {pmatrix}}, \ quad \mathbf {k} = {\ rozpocząć {pmacierz}5\\-12\\10\koniec {pmacierz}}.}$

 

 

 

 

()

Zastosujmy podział ( 7 ), który jest używany w metodzie Jacobiego: dzielimy A w taki sposób, że B składa się ze wszystkich diagonalnych elementów A , a C składa się ze wszystkich pozadiagonalnych elementów A , zanegowanych . (Oczywiście nie jest to jedyny użyteczny sposób podziału macierzy na dwie macierze.) Mamy

${\ Displaystyle {\ rozpocząć {wyrównane} i \ mathbf {B} = {\ rozpocząć {pmatrix} 6 i 0 i 0 \\ 0 i 4 i 0 \\ 0 i 0 i 5 \ koniec {pmatrix}},\quad \mathbf {C} ={\begin{pmatrix}0&2&3\\1&0&2\\3&1&0\end{pmatrix}},\end{wyrównane}}}$

 

 

 

 

()

${\ Displaystyle {\ rozpocząć {wyrównane} i \ mathbf {A ^ {-1}} = {\ Frac {1} {47}} {\ rozpocząć {pmatrix} 18 i 13 i 16 \\ 11 i 21 i 15 \\ 13 i 12 i 22 \ koniec {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{wyrównane}}}$

${\ Displaystyle {\ rozpocząć {wyrównane} \ mathbf {D} = \ mathbf {B ^ {-1} C} = {\ rozpocząć {pmatrix} 0 i {\ Frac {1} {3}} i {\ 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\\[4pkt]2\end{pmacierz}}.\end{wyrównane}}}$

000 Ponieważ B ⁻¹ ≥ i C ≥ , rozszczepienie ( 11 ) jest rozszczepieniem regularnym. Ponieważ ZA ^-1 > promień widmowy $0,7997679$ Przybliżone własne to - . ${\ Displaystyle \ lambda _ {i} \ około -0,4599820, -0,3397859,0,7997679.}$ ) Zatem macierz D jest zbieżna, a metoda ( 5 ) koniecznie jest zbieżna dla problemu ( 10 ). Zauważ, że wszystkie elementy diagonalne A są większe od zera, wszystkie elementy pozadiagonalne A są mniejsze od zera, a A jest ściśle diagonalnie dominujące .

Metoda ( 5 ) zastosowana do problemu ( 10 ) przybiera wtedy postać

${\ Displaystyle \ mathbf {x} ^ {(m + 1)} = {\ rozpocząć {pmatrix} 0 i {\ 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,\ldokropki }$

 

 

 

 

()

Dokładnym rozwiązaniem równania ( 12 ) jest

${\ Displaystyle \ mathbf {x} = {\ rozpocząć {pmatrix} 2 \\ -1 \\ 3 \ koniec {pmatrix}}.}$

 

 

 

 

()

Kilka pierwszych iteracji dla równania ( 12 ) wymieniono w poniższej tabeli, zaczynając od x ⁽⁰⁾ = (0,0, 0,0, 0,0) ^T . Z tabeli widać, że metoda wyraźnie zbiega się do rozwiązania ( 13 ), choć raczej powoli.

${\ Displaystyle x_ {1} ^ {(m)}}$	${\ Displaystyle x_ {2} ^ {(m)}}$	${\ Displaystyle x_ {3} ^ {(m)}}$
0,0	0,0	0,0
0,83333	-3.0000	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

Metoda Jacobiego

Jak stwierdzono powyżej, metoda Jacobiego ( 7 ) jest taka sama, jak określony powyżej regularny podział ( 11 ).

Metoda Gaussa-Seidela

Ponieważ wszystkie przekątne wpisów macierzy A w zadaniu ( 10 ) są niezerowe, możemy wyrazić macierz A jako podział ( 6 ), gdzie

${\ Displaystyle \ mathbf {D} = {\ rozpocząć {pmatrix} 6&0&0 \\0&4&0\\0&0&5\end {pmatrix}}, \ quad \mathbf {U} = {\ rozpocząć {pmatrix} 0&2&3\\0&0&2\\0&0&0 \end{pmacierz}},\quad \mathbf {L} ={\begin{pmacierz}0&0&0\\1&0&0\\3&1&0\end{pmacierz}}.}$

 

 

 

 

()

Mamy wtedy

${\ Displaystyle {\ rozpocząć {wyrównane} i \ mathbf {(DL) ^ {- 1}} = {\ Frac {1} {120 }}{\begin{pmacierz}20&0&0\\5&30&0\\13&6&24\end{pmacierz}},\end{wyrównane}}}$

${\ Displaystyle {\ rozpocząć {wyrównane} & \ mathbf {(DL) ^ {-1} U} = {\ Frac {1} {120}}} {\ rozpocząć {pmatrix} 0 i 40 i 60 \\ 0 i 10 i 75 \\ 0 i 26 i 51 \ koniec { pmatrix}},\quad \mathbf {(DL)^{-1}k} ={\frac {1}{120}}{\begin{pmatrix}100\\-335\\233\end{pmatrix}} .\end{wyrównane}}}$

Metoda Gaussa-Seidela ( 8 ) zastosowana do problemu ( 10 ) przybiera formę

${\ Displaystyle \ mathbf {x} ^ {(m + 1)} = {\ Frac {1} {120}} {\ rozpocząć {pmatrix} 0 i 40 i 60 \\ 0 i 10 i 75 \\ 0 i 26 i 51 \ koniec {pmatrix}} \ mathbf {x } ^{(m)}+{\frac {1}{120}}{\begin{pmatrix}100\\-335\\233\end{pmatrix}},\quad m=0,1,2,\ kropki }$

 

 

 

 

()

Kilka pierwszych iteracji dla równania ( 15 ) wymieniono w poniższej tabeli, zaczynając od x ⁽⁰⁾ = (0,0, 0,0, 0,0) ^T . Z tabeli widać, że metoda wyraźnie zbiega się do rozwiązania ( 13 ), nieco szybciej niż opisana powyżej metoda Jacobiego.

${\ 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

Metoda sukcesywnej nadmiernej relaksacji

Niech ω = 1,1. Wykorzystując podział ( 14 ) macierzy A w problemie ( 10 ) dla metody kolejnej nadmiernej relaksacji, mamy

${\ Displaystyle {\ rozpocząć {wyrównane} i \ mathbf {(D- \ omega L) ^ {- 1}} = {\ Frac {1}{12}}{\begin{pmacierz}2&0&0\\0,55&3&0\\1,441&0,66&2,4\end{pmacierz}},\end{wyrównane}}}$

${\ Displaystyle {\ rozpocząć {wyrównane} i \ 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{pmacierz}},\end{wyrównane}}}$

${\ Displaystyle {\ rozpocząć {wyrównane} & \ mathbf {\ omega (D- \ omega L) ^ {- 1} k} = {\ Frac {1} {12}} {\ rozpocząć {pmatrix} 11 \\ - 36,575\\25,6135\end{pmacierz}}.\end{wyrównane}}}$

Metoda sukcesywnej nadmiernej relaksacji ( 9 ) zastosowana do problemu ( 10 ) przybiera formę

${\ Displaystyle \ mathbf {x} ^ {(m + 1)} = {\ Frac {1} {12}} {\ rozpocząć {pmatrix} -1,2 i 4,4 i 6,6 \\ -0,33 i 0,01 i 8,415 \ \-0,8646&2,9062&5,0073\end{pmatrix}}\mathbf {x} ^{(m)}+{\frac {1}{12}}{\begin{pmatrix}11\\-36,575\\25,6135 \end{pmacierz}},\quad m=0,1,2,\ldots }$

 

 

 

 

()

Kilka pierwszych iteracji dla równania ( 16 ) wymieniono w poniższej tabeli, zaczynając od x ⁽⁰⁾ = (0,0, 0,0, 0,0) ^T . Z tabeli widać, że metoda ewidentnie zbiega się do rozwiązania ( 13 ), nieco szybciej niż opisana powyżej metoda Gaussa-Seidela.

${\ 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

Zobacz też

• Lista tematów podziału operatorów
• Dekompozycja macierzy
• macierz M
• Macierz Stieltjesa

Notatki

•   Ciężar, Richard L.; Faires, J. Douglas (1993), Analiza numeryczna (wyd. 5), Boston: Prindle, Weber and Schmidt, ISBN 0-534-93219-3 .
•   Varga, Richard S. (1960). „Faktoryzacja i znormalizowane metody iteracyjne”. W Langer, Rudolph E. (red.). Problemy brzegowe w równaniach różniczkowych . Madison: University of Wisconsin Press . s. 121–142. LCCN 60-60003 .
•   Varga, Richard S. (1962), Matrix Iterative Analysis , New Jersey: Prentice-Hall , LCCN 62-21277 .