행렬 분할

수학적 선형대수의 수학적 계율에서 행렬 분할은 주어진 행렬을 행렬의 합 또는 차이로 나타내는 식이다. 많은 반복적 방법(예: 미분방정식 시스템의 경우)은 삼지각 행렬보다 일반적인 행렬을 포함하는 행렬 방정식의 직접 해법에 의존한다. 이러한 행렬 방정식은 행렬 분할로 쓰여질 때 종종 직접적이고 효율적으로 해결될 수 있다. 그 기술은 Richard S에 의해 고안되었다. 1960년 ^[1]바르가

정규 스플릿

우리는 행렬 방정식을 풀려고 한다.

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

(1)

여기서 A는 주어진 n × n 비성격 행렬이고, k는 주어진 n 성분들의 열 벡터다. 매트릭스 A를 나눠서

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

(2)

여기서 B와 C는 n × n 행렬이다. 임의 n × n 매트릭스 M의 경우, M이 음이 아닌 항목이 있으면 M ≥ 0을 쓰고, M이 양의 항목만 있으면 M > 0을 쓴다. 마찬가지로, 매트릭스 M₁ - M이₂ 음이 아닌 항목이 있으면 M₁ ≥ M을₂ 쓴다.

정의: A = B - C는 B가⁻¹ 0이고 C가 0이면 A가 정기적으로 분할되는 것이다.

형태에 대한 행렬 방정식이

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

(3)

여기서 g는 주어진 열 벡터로서 벡터 x에 대해 직접 해결할 수 있다. (2)가 A의 규칙적인 분할을 나타낸다면 반복적인 방법

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

(4)

여기서 x는⁽⁰⁾ 임의 벡터로서 수행될 수 있다. 동등하게, 우리는 양식으로 (4)를 쓴다.

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

(5)

(2)가 A의 정규 분리를 나타내는 경우 행렬 D = BC에는⁻¹ 음수가 아닌 항목이 있다.^[2]

A⁻¹ > 0이면 $if{\displaystyle }$(${\displaystyle D\mathbf{}}$) ${\displaystyle \rho (\mathbf {D})}<$ 1>,$$ 여기서 $\rho {\displaystyle }$(${\displaystyle D\mathbf{})}$ ${\displaystyle \rho (\mathbf {D} )$는 D의 스펙트럼 반경을 나타내며$$, 따라서 D는 수렴 행렬이다. 그 결과 반복법(5)은 반드시 수렴한다.^[3][4]

또한 행렬 B가 대각 행렬이 되도록 분할(2)을 선택한 경우(대각 입력이 모두 0이 아니므로 B는 반드시 반전 가능해야 함), B는 선형 시간(시간 복잡성 참조)으로 반전될 수 있다.

매트릭스 반복 방법

많은 반복적 방법은 행렬 분할이라고 설명할 수 있다. 행렬 A의 대각선 항목이 모두 0이 아닌 경우 행렬 A를 행렬 합으로 표현함

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

(6)

여기서 D는 A의 대각선 부분이고, U와 L은 각각 엄격히 위쪽과 아래쪽 삼각형 n × n 행렬로 되어 있는데, 그러면 우리는 다음과 같은 것을 얻게 된다.

자코비 방법은 행렬 형태로 분할하여 나타낼 수 있다.

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

(7)

가우스-세이델 방법은 행렬 형태로 분할로 나타낼 수 있다.

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

(8)

연속적인 과완화 방법은 행렬 형태로 분할로 나타낼 수 있다.

${\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][10]

(9)

예

정기분할

등식 (1)에서 다음을 수행하십시오.

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

(10)

자코비 방법에 사용되는 분할(7)을 적용하자: B가 A의 모든 대각선 원소로 구성되도록 A를 분할하고, C는 부정된 A의 모든 비대각 원소로 구성되도록 한다.(물론 이것이 매트릭스를 두 개의 행렬로 분할하는 유일한 유용한 방법은 아니다) 우리는 가지고 있다.

${\displaystyle {\begin{aligned}&\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{aligned}}}$

(11)

${\displaystyle {\begin{aligned}&\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{aligned}}}$

${\displaystyle {\begin{aligned}\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{정렬}}}$

B⁻¹ ≥ 0과 C ≥ 0이므로 분할(11)은 정규 분할이다. A⁻¹ > 0 이후 스펙트럼 반지름 ρ${\displaystyle }$(${\displaystyle D\mathbf{}}$) ${\displaystyle \rho (\mathbf {D} )}$ $$< 1. (D의 대략적인 고유값은 ${\displaystyle {\lambda }_{}}$ i ${\displaystyle {}_{}}$- ${\displaystyle 0.4599820}$,${\displaystyle \mathrm{}}$- 0${\displaystyle .33997859}$, 0${\displaystyle \mathrm{.7997679이다.}}$${\displaystyle \putda _{i}\ 약 -0.4599820,-0.3397859,0.7997679.$$\}\}$ 따라서 행렬 D는 수렴되고 방법(5)은 반드시 문제에 수렴한다(10). 유의할 점은 A의 대각선 원소는 모두 0보다 크고, A의 대각선 원소는 모두 0보다 작으며, A는 엄격히 대각선적으로 우세하다는 것이다.^[11]

문제에 적용되는 방법(5)을 선택한 다음(10) 양식을 취한다.

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

방정식(12)에 대한 정확한 해법은

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

(13)

방정식(12)에 대한 처음 몇 개의 반복 값은 x⁽⁰⁾ = (0.0, 0.0, 0.0)로 시작하는 아래 표에 나열되어 있다.^T 표에서 그 방법이 다소 느리기는 하지만 분명히 해법(13)으로 수렴되고 있음을 알 수 있다.

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

자코비법

위에서 설명한 바와 같이, 자코비법(7)은 위에서 설명한 특정 정기 분할(11)과 동일하다.

가우스-사이델법

문제의 매트릭스 A(10)의 대각선 항목은 모두 0이 아니므로, 매트릭스 A를 분할(6)으로 표현할 수 있다.

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

그러면 우리는

${\displaystyle {\begin{ligned}&\mathbf {(D-L)^{-100}{120}{\begin{pmatrix}20&0\5&0\&30\13&0\&24\end{pmatrix},\end{ligned}}}}}}}}}}}}$

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

문제(10)에 적용된 가우스-세이델 방법(8)이 형태를 취한다.

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

(15)

등식 (15)에 대한 처음 몇 개의 반복은 x⁽⁰⁾ = (0.0, 0.0, 0.0)로 시작하는 아래 표에 나열되어 있다.^T 표에서 보면 위에서 설명한 자코비법보다 다소 빠른 속도로 그 방법이 분명히 해법(13)으로 수렴되고 있음을 알 수 있다.

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

연속 과완화법

Ω = 1.1로 한다. 연속적인 과완화 방법에 대해 문제 (10)에 있는 행렬 A의 분할 (14)을 사용하여 다음과 같이 한다.

${\displaystyle {\begin{aigned}&\mathbf {(D-\omega L)^{-1}={\frac {1}{12}{\gin{pmatrix}2&0&0\\0\0}\0}.55&3&0\\1.441&0.66&2.4\end{pmatrix},\end{정렬}}}$

${\displaystyle {\begin{aligned}&\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{aligned}}}$

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

문제(10)에 적용된 연속적인 과완화 방법(9)이 형태를 취한다.

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

등식 (16)에 대한 처음 몇 개의 반복은 x⁽⁰⁾ = (0.0, 0.0, 0.0)로 시작하는 아래 표에 나열되어 있다.^T 표에서 보면 위에서 설명한 가우스-세이델 방법보다 약간 빠른 속도로 그 방법이 분명히 용액(13)으로 수렴되고 있음을 알 수 있다.

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

참고 항목

• 주제 분할 연산자 목록
• 행렬 분해
• M 매트릭스
• 슈틸트제스 행렬

메모들

참조

• Burden, Richard L.; Faires, J. Douglas (1993), Numerical Analysis (5th ed.), Boston: Prindle, Weber and Schmidt, ISBN 0-534-93219-3.
• Varga, Richard S. (1960). "Factorization and Normalized Iterative Methods". In Langer, Rudolph E. (ed.). Boundary Problems in Differential Equations. Madison: University of Wisconsin Press. pp. 121–142. LCCN 60-60003.
• Varga, Richard S. (1962), Matrix Iterative Analysis, New Jersey: Prentice-Hall, LCCN 62-21277.