4. 소거법과 $A=LU$
기본적인 문제 $Ax = b$ 의 해를 구하기 위해, 대수적으로 방정식을 단순화 하여 문제를 해결하는 법을 알아본다.
$n$ x $n$ 행렬 $A$ 와 $n$ x $1$ 열벡터 $b$ 가 있을때, $x_1$ ~ $x_{n-1}$ 까지 소거해 $A_n x_n = b_n$ 을 얻고, 차례로 $x_2$, $x_1$ 을 구할 수 있다.
이 과정을 랭크가 1인 행렬 관점에서 소거법을 살펴보면, 위의 과정은 행렬 $lu^*$ 를 제거하는 과정이다. 행렬 $A$는 랭크가 1 인 행렬들의 합이고 이는 $A=LU$로 표현할 수 있다. ( $L$ : 하삼각행렬, $U$ : 상삼각행렬 )
$A=LU$는 행교환이 없는 소거법 행렬의 표현으로, 대수학적 접근이다. ( 연립방정식 )
EX) $ \begin{bmatrix} 1 & -2 \\ 2 & 3 \\ \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 1 \\ 9\end{bmatrix} $
- 대수학적 접근 풀이.
$x-2y=1$ , $2x+3y=9$ 두 방정식을 연립해서 풀면, 두개의 직선이 만나는점 $x=3$, $y=1$ 의 해를 구할수 있고,
미지수 $x$ 를 제거하면 위의 식이 $ \begin{bmatrix} 1 & -2 \\ 0 & 7 \\ \end{bmatrix}\begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 1 \\ 7 \end{bmatrix} $ 이 된다.
이 방법은 $n=2$ 에서는 시각화하기 쉬웠지만, $n$ 이 높아질수록 시각화와 해를 찾기 어려워진다.
- 열 관점에서의 풀이.
$Ax$ 은 $A$의 열들의 일차결합이다. 따라서 $A$ 열들의 일차결합으로 $b$를 구한다.
$x=3$ , $y=1$ 이라는 계수가 구해진다.
열들의 일차결합으로 푸는 경우에 해를 찾기 쉬워진다. 해가 하나 존재하려면, $A$에는 $n$개의 독립인 열들을 가져야한다.
즉 모든 열이 일차독립이라는 말은, $Ax=0$ 의 유일한 해는 $x=0$ 이다. 라는 말과 동일하다.
소거법을 이용한 $Ax=b$ 풀이
$Ax=0$ 의 해가 $x=0$ 으로 유일하다면, 열의 일차결합이 $b$가 되는 유일한 $x$ 를 구할 수 있다.
- 첫번째 추축을 정하고, 방정식을 이용해서 추축아래를 모두 0 으로 제거한다.
- 2 ~ $n$ 열 까지 상삼각행렬 $U$를 찾을 때까지 계속 진행한다.
- 추축은 0 이 될수 없고, $n$개의 추축은 주 대각선 위에 있다.
- 마지막까지 진행한 행렬이 상삼각행렬 $U$ 이다.
이런 방식의 소거법은 많은 곱셈과 덧셈을 수행하게 된다. 이를 해결하는 법이 $A=LU$ 이다.
$A=LU$ 분해
원래 행렬 $A$는 소거법 마지막에 구한 $U$ 와 어떤 관계가 있을까?
소거법을 할때, 매 행에 $l_{21} = \frac{a_{21}}{a_{11}}$, $l_{31} = \frac{a_{31}}{a_{11}}$, ... 들을 곱해 소거함으로써 4 x 4 문제를 3 x 3 문제로 축소한다. 즉 랭크가 1 인 행렬 $l_1u_1^*$ 를 분리한다.
$ A = l_1u_1^* + \begin{bmatrix} 0 & \cdots \\ \vdots & A_2 \\ \end{bmatrix} $
$ l_1u_1^* = \text{[1 row]}\begin{bmatrix} 1 & l_{21} & \cdots & l_{n1} \\ \end{bmatrix}^* $
이후 위와 비슷하게 랭크가 1 인 행렬 $l_iu_i^*$ 를 분리한다.
$ l_iu_i^* = \text{[i row]}\begin{bmatrix} 0 & \cdots & 1 & \cdots & l_{ni} \\ \end{bmatrix}^* $
이 랭크가 1 인행렬들을 모아보면,
$A = l_1u_1^* + \cdots + l_nu_n^* = \begin{bmatrix} 1 & 0 & \cdots & 0 \\ l_{21} & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots\\ 1_{n1} & 1_{n2} & \cdots & 1 \\ \end{bmatrix} U = LU$
소거법은 행렬 $A=LU$ 를 하삼각행렬 $L$ 과 상삼각행렬 $U$의 곱으로 분해한다.
- $n-1$ 개의 방정식에서 $x_1$을 제거하여 문제의 크기를 $n$ 에서 $n-1$으로 줄인다.
- $i$ 행 ( 추축행 ) 의 배수를 뺐고, 제거한 행렬의 랭크는 1 이다.
- $n$ 단계 이후, 전체 행렬 $A$는 $n$ 개의 랭크 1 행렬들의 합이다.
- 그 합은 $L$ 과 $U$의 곱셈이다.
$Ax=b$ 의 해법
$Ax=b$ 의 해를 구하기위해해서 $b$ 를 $A$의 열에 추가한 새로운행렬 $ \begin{bmatrix} A & b \\ \end{bmatrix} $ 으로 취급한다.
$ \begin{bmatrix} A & b \\ \end{bmatrix} = \begin{bmatrix} LU & b \\ \end{bmatrix} $ 행렬에 소거법을 진행하여
$ \begin{bmatrix} U & L^{-1}b \\ \end{bmatrix} = \begin{bmatrix} U & c \\ \end{bmatrix} $ $A$ 를 상삼각행렬 $U$ 로 소거하는 단계중 $b$ 느 $c$ 로 바뀐다.
$Ax=b$ 에서 소거법을 통해 역대입법 back subsitution 을 적용가능한 $Ux=c$ 를 얻는다.
$Ax=b$ 는 $Lc=b$ 와 $Ux=c$ 으로 나뉘어진다. 소거법으로 $c$ 를 얻고 대입법으로 $x$ 를 얻는다.
결국 $x=U^{-1}c = U^{-1}L^{-1}b = A^{-1}b $ 인 해를 구할 수 있다.
여기서 모든 단계에서 추축은 0 이 아니어야 한다. 행렬 하삼각행렬 $L$ 의 원소는 추축으로 나뉘기 때문이다.
그래서 기존 행렬의 행 순서대로 말고 행을 추축으로 지정하기위해서 치환행렬 $P$ 를 도입한다.
행교환(치환)
코드로 구현할때, 보통 추축 지정은 가장 큰수로 지정한다. 가장 큰수로나눠야 오차가 적기 때문이다.
1 열의 추축행을 1 행이 아니라 다른 행으로 지정하고 소거법을 진행하면, $A_1$ 의 위치는 오른쪽아래가 아니라 다른 쪽에 위치하게 된다. 따라서 추축에 따라 행을 치환한 행렬 $PA$ 를 만들고, $PA=LU$ 를 만든다.
모든 $n$ x $n$ 가역행렬 $A$ 는 $PA=LU$ 를 만족한다. 이때 $P$ 는 치환행렬이다.
EX) 1 행을 1 행으로, 2 행을 2 행으로, 3 행을 3 행으로 $ P_{123} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} $
EX) 3 행을 1 행으로, 1 행을 2 행으로, 2 행을 1 행으로 $ P_{312} = \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ \end{bmatrix} $
모든 치환행렬의 역행렬은 $P^T$ 이고, 행교환은 $Ax=b$ 양변에 곱해져 $b$ 에도 적용된다. 컴퓨터에서는 행을 변경하지 않고, 치환행렬을 기억한다.
$n$ x $n$ 치환행렬은 $n!$ 개 있고, 만일 $A$ 에 종속인 행이 존재하면, 중간에 추축이 0 이 되어 소거법을 멈추게 된다.
https://jamboard.google.com/d/1a-sJf4RLP-UUd1ZwFA3KCWiouy8Lf0rrP8wojgBkjG0
로그인 - Google 계정
하나의 계정으로 모든 Google 서비스를 Google 계정으로 로그인
accounts.google.com