[KOCW 선형대수] 3강. LU분할

3강. LU분할¶

1.4 Matrix Notation and multiplication

⎧⎩⎨⎪⎪2u+v+w=5 4u−6v=−2 −2u+7v+2w=9 $$\begin{array}{l}\mathrm{}\mathrm{}\\ \mathrm{}\mathrm{}\mathrm{}\\ \mathrm{}\mathrm{}\mathrm{}\mathrm{}\\ \end{array}$$

⎡⎣⎢⎢2 4 −21−67102⎤⎦⎥⎥⎡⎣⎢⎢uvw⎤⎦⎥⎥=⎡⎣⎢⎢5−29⎤⎦⎥⎥$$\begin{array}{ccc}\mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\end{array}\begin{array}{c}\\ \\ \end{array}\begin{array}{c}\mathrm{}\\ \mathrm{}\\ \mathrm{}\end{array}$$

이를 Coefficient Matrix라고도 부른다 (계수만 가져와서)

u⎡⎣⎢⎢24−2⎤⎦⎥⎥+v⎡⎣⎢⎢1−67⎤⎦⎥⎥+w⎡⎣⎢⎢102⎤⎦⎥⎥=⎡⎣⎢⎢5−29⎤⎦⎥⎥$$\mathbf{}\begin{array}{c}\mathrm{}\\ \mathrm{}\\ \mathrm{}\end{array}\mathbf{}\begin{array}{c}\mathrm{}\\ \mathrm{}\\ \mathrm{}\end{array}\mathbf{}\begin{array}{c}\mathrm{}\\ \mathrm{}\\ \mathrm{}\end{array}\begin{array}{c}\mathrm{}\\ \mathrm{}\\ \mathrm{}\end{array}$$

이를 Ax=b$$ 의 형태로 볼 수 있다. Ax$$는 A$$의 열에 대한 Combination이다.

Coefficients는 x$$의 성분에 해당한다.

bi=∑nj=1aijxij${}_{}\underset{\mathrm{}}{\overset{}{}}{}_{}{}_{}$ => sigma-notation

Elimentary matrix in elimination steps

E21=⎡⎣⎢⎢1 −l21 0010001⎤⎦⎥⎥$$\mathbf{}\mathbf{}\begin{array}{ccc}\mathrm{}& \mathrm{}& \mathrm{}\\ {}_{\mathrm{}}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\end{array}$$

이 식을 통해 Gaussian elimination을 할 수 있는데, −l21${}_{\mathrm{}}$이 방정식에 곱해져서 이전에 했던 Forward Elimination Step을 구현할 수 있다. ( 식에서 식을 빼줘야하기 때문에 -가 붙음)

E31=⎡⎣⎢⎢1 0 −l31010001⎤⎦⎥⎥$$\mathbf{}\mathbf{}\begin{array}{ccc}\mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\\ {}_{\mathrm{}}& \mathrm{}& \mathrm{}\end{array}$$

E32=⎡⎣⎢⎢1 0 001−l32001⎤⎦⎥⎥$$\mathbf{}\mathbf{}\begin{array}{ccc}\mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& {}_{\mathrm{}}& \mathrm{}\end{array}$$

E21A=⎡⎣⎢⎢2 0 −21−871−22⎤⎦⎥⎥$${\mathbf{}}_{\mathbf{}}\mathbf{}\begin{array}{ccc}\mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\end{array}$$

위의 결과는 Gaussian elimination의 결과이다. (l21${}_{\mathrm{}}$ 이용한 것)

E21A=⎡⎣⎢⎢1 −2 0010001⎤⎦⎥⎥⎡⎣⎢⎢  A⎤⎦⎥⎥$${\mathbf{}}_{\mathbf{}}\mathbf{}\begin{array}{ccc}\mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\end{array}\begin{array}{ccc}& & \\ & & \\ & & \end{array}$$

의 결과이다. l21${}_{\mathrm{}}$이 -2인 이유는 식 (1) x -2 + 식 (2)를 통해 식 (2)의 u$$를 없애기 위해서이다.

1.5 Triangular Factors & Row Exchanges

Ax=⎡⎣⎢⎢2 4 −21−67102⎤⎦⎥⎥⎡⎣⎢⎢u v w⎤⎦⎥⎥=⎡⎣⎢⎢5 −2 9⎤⎦⎥⎥=b$$\mathbf{}\mathbf{}\begin{array}{ccc}\mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\end{array}\begin{array}{c}\\ \\ \end{array}\begin{array}{c}\mathrm{}\\ \mathrm{}\\ \mathrm{}\end{array}$$

* step 1 : row2 - $l_{21}$ * row1      => row2'
* step 2 : row3 - $l_{31}$ * row1      => row3'
* step 3 : row3' - $l_{32}$ * row2'

식 (2)와 (3)의 u$$를 먼저 제거해주고, 그 다음 step 3에서 v$$를 제거하고 있다.

여기서 참고하자면 Eab${}_{}$ 라는 것은 b$$의 식을 이용해서 a$$식을 바꾸겠다는 것이다.

결국, 결과는 "Upper Triangular Matrix"(U)로 나온다.

E32E31E21A=⎡⎣⎢⎢2 0 01−801−21⎤⎦⎥⎥$${\mathbf{}}_{\mathbf{}}{\mathbf{}}_{\mathbf{}}{\mathbf{}}_{\mathbf{}}\mathbf{}\begin{array}{ccc}\mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\end{array}$$

오른쪽 위에만 숫자가 있는 Upper Triangular(U) 모양으로 나왔다. ( Pivot ≠ 0 )

Gauss Elimination을 하면 아래와 같이 정리된다.

⎧⎩⎨⎪⎪2u+v+w=5 −8v−2w=−12 w=2$$\begin{array}{l}\mathrm{}\mathrm{}\\ \mathrm{}\mathrm{}\mathrm{}\\ \mathrm{}\end{array}$$

이는 다시 행렬로 표현하면 다음과 같다.

Ux=⎡⎣⎢⎢2 0 01−801−21⎤⎦⎥⎥⎡⎣⎢⎢u v w⎤⎦⎥⎥=⎡⎣⎢⎢5 −12 2⎤⎦⎥⎥=c$$\mathbf{}\mathbf{}\begin{array}{ccc}\mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\end{array}\begin{array}{c}\\ \\ \end{array}\begin{array}{c}\mathrm{}\\ \mathrm{}\\ \mathrm{}\end{array}$$

x$$는 Ux=c$$에서 back-substitution하면 구할 수 있다. ( w,v,u 순으로 구함 )

Matrix에 Inverse를 해주면

A=E−121E−131E−132U${}_{\mathrm{}}^{\mathrm{}}{}_{\mathrm{}}^{\mathrm{}}{}_{\mathrm{}}^{\mathrm{}}$

위와 같은 모양으로 나온다.

E−121E−131E−132${}_{\mathrm{}}^{\mathrm{}}{}_{\mathrm{}}^{\mathrm{}}{}_{\mathrm{}}^{\mathrm{}}$는 ( 3x3 역행렬을 통해 직접 구하면 나온다 )

E−121E−131E−132=⎡⎣⎢⎢1 l21 l3101l32001⎤⎦⎥⎥$${\mathbf{}}_{\mathbf{}}^{\mathbf{}\mathbf{}}{\mathbf{}}_{\mathbf{}}^{\mathbf{}\mathbf{}}{\mathbf{}}_{\mathbf{}}^{\mathbf{}\mathbf{}}\begin{array}{ccc}\mathrm{}& \mathrm{}& \mathrm{}\\ {}_{\mathrm{}}& \mathrm{}& \mathrm{}\\ {}_{\mathrm{}}& {}_{\mathrm{}}& \mathrm{}\end{array}$$

⎡⎣⎢⎢1 2 0010001⎤⎦⎥⎥⎡⎣⎢⎢1 0 −1010001⎤⎦⎥⎥⎡⎣⎢⎢1 0 001−1001⎤⎦⎥⎥=⎡⎣⎢⎢1 2 −101−1001⎤⎦⎥⎥=L$$\begin{array}{ccc}\mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\end{array}\begin{array}{ccc}\mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\end{array}\begin{array}{ccc}\mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\end{array}\begin{array}{ccc}\mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\end{array}$$

A=LU$$ (L은 Lower Triangular Matrix를 의미한다/ 그래서 LU분할!)

대각선 아래있는 성분들은 곱셈에 사용이 된다 l21,l31,l32${}_{\mathrm{}}{}_{\mathrm{}}{}_{\mathrm{}}$ Elimination의 과정을 잘 기록되어있다. ( 앞에서는 연산을 위해 다 -처리가 되어 있었음 )

Triangular Factorization(descomposition = 인수분해 )

A=LU$$를 row changes없이 만들기!

U$$의 대각선 성분이 Pivot이 된다

Ax=b$$, first Lc=b$$, then Ux=c$$

(1) Factor : A$$에서 L$$과 U$$를 찾는다. (2) Solve : L$$과 U$$에서 Solution x$$를 찾는다.

• U$$는 DU$$로도 나타낼 수 있다. (D = Diagnoal Matrix : Pivots의 matrix)

U=⎡⎣⎢⎢⎢⎢d1 0 0 0ad200bdd30cefd4⎤⎦⎥⎥⎥⎥$$\mathbf{}\begin{array}{cccc}{}_{\mathrm{}}& & & \\ \mathrm{}& {}_{\mathrm{}}& & \\ \mathrm{}& \mathrm{}& {}_{\mathrm{}}& \\ \mathrm{}& \mathrm{}& \mathrm{}& {}_{\mathrm{}}\end{array}$$

일 때, 다음과 같이 나타낼 수 있다.

U=⎡⎣⎢⎢⎢⎢d1 0 0 00d20000d30000d4⎤⎦⎥⎥⎥⎥⎡⎣⎢⎢⎢⎢⎢1 0 0 0ad1100bd1dd110cd1ed1fd11⎤⎦⎥⎥⎥⎥⎥=DU$$\mathbf{}\begin{array}{cccc}{}_{\mathrm{}}& \mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& {}_{\mathrm{}}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& {}_{\mathrm{}}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}& {}_{\mathrm{}}\end{array}\begin{array}{cccc}\mathrm{}& \frac{}{{}_{\mathrm{}}}& \frac{}{{}_{\mathrm{}}}& \frac{}{{}_{\mathrm{}}}\\ \mathrm{}& \mathrm{}& \frac{}{{}_{\mathrm{}}}& \frac{}{{}_{\mathrm{}}}\\ \mathrm{}& \mathrm{}& \mathrm{}& \frac{}{{}_{\mathrm{}}}\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\end{array}$$

위와 같이 표현할 수 있는데, 여기서 D를 Diagnoal Matrix라고 부르는 것이다.

따라서 A=LU=LDU$$로 둘 다 가능하다. D$$는 거듭제곱을 수행할 때 유용하게 작용한다.

Dn=⎡⎣⎢⎢⎢⎢d1n 0 0 00d2n0000⋱0000dnn⎤⎦⎥⎥⎥⎥$$\mathbf{}\mathbf{}\begin{array}{cccc}{{}_{\mathrm{}}}^{}& \mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& {{}_{\mathrm{}}}^{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& & \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}& {{}_{}}^{}\end{array}$$

• LDU$$ factorization 과 LU$$ factorization은 행렬 A$$에 대해 unique하다 ( 조합이 두 가지 이상 안나옴)

Row Exchange and Permutation Matrices

• zero in the Pivot position

[0324][uv]=[b1b2]$$\begin{array}{cc}\mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}\end{array}\begin{array}{c}\\ \end{array}\begin{array}{c}{}_{\mathrm{}}\\ {}_{\mathrm{}}\end{array}$$

=> Exchange Rows 의 결과는 다음과 같다. (P21${}_{\mathrm{}}$은 2행, 1행 순서바꾼다는 것)

{3u+4v=b22v=b1$$\begin{array}{l}\mathrm{}\mathrm{}{}_{\mathrm{}}\\ \mathrm{}{}_{\mathrm{}}\end{array}$$

• Permutation

P=[0110]$$\mathbf{}\begin{array}{cc}\mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}\end{array}$$

PA=[3042]=Pb=[b2b1]$$\mathbf{}\mathbf{}\begin{array}{cc}\mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}\end{array}\mathbf{}\mathbf{}\begin{array}{c}{}_{\mathrm{}}\\ {}_{\mathrm{}}\end{array}$$

Permutation matrix P$$는 I$$와 같은 수의 행을 가져야 한다. 또한 어느 행,열을 골라도 항상 1개의 1이 있어야 한다.

I=⎡⎣⎢⎢1 0 0010001⎤⎦⎥⎥,P21=⎡⎣⎢⎢0 1 0100001⎤⎦⎥⎥,P31=⎡⎣⎢⎢0 0 1010100⎤⎦⎥⎥$$\mathbf{}\begin{array}{ccc}\mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\end{array}\mathbf{}\mathbf{}\begin{array}{ccc}\mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\end{array}\mathbf{}\mathbf{}\begin{array}{ccc}\mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\end{array}$$

P32=⎡⎣⎢⎢1 0 0001010⎤⎦⎥⎥,P32P21=⎡⎣⎢⎢0 0 1100010⎤⎦⎥⎥≠P21P32=⎡⎣⎢⎢0 1 0001100⎤⎦⎥⎥$$\mathbf{}\mathbf{}\begin{array}{ccc}\mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\end{array}{\mathbf{}}_{\mathbf{}}{\mathbf{}}_{\mathbf{}}\begin{array}{ccc}\mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\end{array}{\mathbf{}}_{\mathbf{}}{\mathbf{}}_{\mathbf{}}\begin{array}{ccc}\mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}\end{array}$$

P$$행렬간의 교환법칙은 성립하지 않는다.

그리고 P−1=PT${}^{\mathrm{}}{}^{}$ 이다. ( 원래대로 되돌리는 것이다 )

(1) Non - Singular cases면

PA=LU$$ 이고, 따라서 A=PTLU${}^{}$ 가 성립한다.

(2) Singular cases면, P$$가 존재하지 않고, Elimination에 실패한다.