선형대수)LU분해와 가우스 소거법 : 행렬 L은 왜 그렇게 만들어질까?
1)가우스 소거법
연립방정식을 풀 때, 우리는 보통 미지수를 하나씩 소거해 나가며 해를 구한다.
이를 가우스 소거법이라하고 선형대수에서도 이 방법이 사용된다.
만약 x+y+z=6 2x+3y-z=5 2x+3y+3z=17가 있으면 목표는 미지수 x, y, z를 구하는 것일 것이다.
선형 대수에서는 연립방정식을 어떻게 풀까 다음과 같은 선형연립방정식이 있다고 해보자.
[ 1 1 1| 6] R1
[ 2 3 -1| 5] R2
[ 2 3 3| 17] R3즉위 행렬을 증강 행렬 [A|b]형태로 본다.
먼저 1열의 미지수를 없애기 위해 R1을 기준으로 아래 행들을 제거한다.
각 식을 R1, R2, R3이라 한다면 R1과 R2 그리고 R1과 R3으로 말이다.
R1과 R3(R3-2R1), R3과 R1(R3-2R1) 으로 소거를 진행하는 과정은 다음과 같다.
R'2: [2 3 -1 | 5] - 2*[1 1 1 | 6] = [0 1 -3| -7] (R2-2*R1) L[2][1]에 기록
R'3: [2 3 3 | 17] - 2*[1 1 1 | 6] = [0 1 1| 5] (R3-2*R1) L[3][1]에 기록이제 식 R2 위치에 R'2를, R3위치에 R'3을 두면 다음과 같다.
[ 1 1 1| 6] R1
[ 0 1 -3| -7] R'2
[ 0 1 1| 5] R'3가 되고 다음 단계로 2열을 기준으로 소거해준다. R'2와 R'3으로 소거를 진행하는 과정은 다음과 같다.
R''3: [ 0 1 1 | 5] - [ 0 1 -3 | 7] = [0 0 4| 12] (R'3-R'2) L[3][2]에 기록이 빼준 식을 R''3이라 하고 R1과 R'2와 R3으로 행렬을 둔다면 최종적으로 얻는 상삼각행렬은 다음과 같다.
[ 1 1 1| 6] R1
[ 0 1 -3| -7] R'2
[ 0 0 4| 12] R''3이제 R''3을 통해 역방향 대입으로 해를 구할 수 있다.
z=12/4=3
y=-3*z=-7 > y-9=-7 > y=2
x+y+z=6 > x+2+3=6 >x=1
즉, 해는 x=1, y=2, z=3이라는 것을 알 수 있다.
이와 같이 소거 과정에서 각 열의 첫 번째로 남아있는 피벗행을 기준으로 아래 행들을 제거하는
행 연산을 통해 상삼각형태로 바꾸고 마지막 행부터 역순으로 해를 구하는 방식을 가우스 소거법이라 한다.
2)LU분해
이제 LU분해에 대해 알아보자. LU분해는 행렬 A를 행렬 L와 행렬 U의 곱으로 분해하는 방법이다.
A=LU
아까 방정식으로 구한 행렬의 경우 대각성분의 아랫쪽 항들이 모두 0인 행렬로 이를 상삼각행렬(Upper triangular matrix)이라 부르고 대각성분의 윗쪽 항들이 모두 0인 행렬로 이를 하삼각행렬(Lower triangular matrix)이라 한다.
즉, 행렬 A를 행렬 L (Lower triangular matrix)와 행렬 U (Upper triangular matrix)의 곱으로 분해하는 것이 LU분해이다.
 |
 |
먼저 행렬 U를 구해보자. U를 구하는 방법은 가우스 소거방법과 같다.
따라서 앞서 구한 가우스 소거 과정을 통해 나온 행렬 U는 다음과 같다.
[ 1 1 1] R1
[ 0 1 -3] R'2=R3-2R1
[ 0 0 4] R''3=R'3-R'2이제 행렬 L을 구해보자. 행렬 L은 대각성분이 모두 1이고 가우스 소거과정에서 사용한 곱셈 계수들을 하삼각위치에 기록한다.
현재는 행렬이 3x3이니 행렬 L의 초기 상태는 다음과 같을 것이다.
[1 0 0]
[0 1 0]
[0 0 1]R'2=R3-2R1 ->L[2][1]=2
R'3=R'3-2R1 ->L[3][1]=2
R"3=R'3-R'2 ->L[3][2]=1
이렇게 되기에 이를 바탕으로 한 행렬 L은 다음과 같다.
[1 0 0] [ 1 0 0]
L=[2 1 0] [R'2 1 0]
[2 1 1] [R'3 R"3 1]정리하면
[ 1 1 1] [ 1 0 0] [ 1 1 1]
A=[ 2 3 -1] L=[ 2 1 0] U=[ 0 1 -3]
[ 2 3 3] [ 2 1 1] [ 0 0 4]이제 행렬 L과 행렬 U를 곱해보면 원래 행렬 A를 다시 얻을 수 있다.
[ 1 0 0] [ 1 1 1] [ 1 1 1]
LU=[ 2 1 0]ㆍ[ 0 1 -3]=[ 2 3 -1]=A
[ 2 1 1] [ 0 0 4] [ 2 3 3]가우스 소거법은 연립방정식을 직접 풀기 위한 방법이고 LU분해는 이 과정을 행렬 L에 기록하면서 행렬 곱의 형태로 일반화한 기법이다.
이 두 가지의 표현 방법을 보면 가우스 소거법에선 Ax=b라 하고 이를 LUx=b로 한 것이 LU분해이다.
여기서 계산 시엔 LU분해는 U행렬 과정을 L에 기록하기에 b는 쓰지 않는다는 점을 기억하자.
참고
질문 1: LU 분해 과정에서 L 행렬에 값을 넣는 위치는 어떻게 되는가?
한 번 위치를 기준으로 생각해보자.3x3행렬의 경우 LU분해시 다음과 같이 될 것이다.
[a₁₁ a₁₂ a₁₃] [1 0 0] [u₁₁ u₁₂ u₁₃]
A=[a₂₁ a₂₂ a₂₃] L=[l₂₁ 1 0] U=[0 u₂₂ u₂₃]
[a₃₁ a₃₂ a₃₃] [l₃₁ l₃₂ 1] [0 0 u₃₃]A행렬이 가우스 소거법에 의해 U행렬이 되려면 먼저 a₂₁, a₃₁가 0이 되어야한다.
이를 위한 R2는 R2-(a₂₁/a₁₁)R1 여기서 소거 계수 a₂₁/a₁₁를 k₁라하면 l₂₁에 k₁가 기록된다.
이를 위한 R3는 R3-(a₃₁/a₁₁)R1 여기서 소거 계수 a₃₁/a₁₁를 k₂라하면 l₃₁에 k₂가 기록된다.
그 후 A행렬은 다음과 같아진다.
[a₁₁ a₁₂ a₁₃]
A=[ 0 a'₂₂ a'₂₃]
[ 0 a'₃₂ a'₃₃]이제 a'₃₂를 0으로 만들자.
이를 위한 R3은 R3-(a'₃₂/a'₂₂)R2 여기서 소거 계수 a'₃₂/a'₂₂를 k₃라하면
l₃₂에 k₃가 기록된다.
[a₁₁ a₁₂ a₁₃]
A=[ 0 a'₂₂ a'₂₃]
[ 0 0 a''₃₃]이렇게 만들어진 A행렬이 U행렬이고 위치가 기록된 L은 다음과 같다.
[1 0 0]
L=[k₁ 1 0]
[k₂ k₃ 1]결국 L 행렬의 (i,j) 위치 (i>j)에는 U 행렬을 만들 때 i번째 행의 j열 요소를 0으로 만들기 위해 사용된 소거 계수(multiplier)를 기록한다.
즉, U에서 미지수가 사라지는 위치에 기록된다.
질문 2:최종 상삼각행렬의 경우 1열에 R1이 아닌 R2나 R3가 오거나 2열에 R'2가 아닌 R'3이 와도 되나요?
가우스 소거법에서는 연립방정식을 풀기 위해 행의 순서를 바꾸는 것에 문제가 없다.
이런 연립방정식 풀이에는 어떤 식을(or 행을) 1행에 둘지, 2행에 둘지 3행에 둘진 자유롭게 바꿀 수 있다.
중요한 목적은 계단형 행렬 즉, 상삼각행렬을 만드는 것이 중요하다.
하지만 LU분해에서는 행렬 A를 L(하삼각행렬)과 U(상삼각행렬)의 곱으로 표현한다.
이때 소거 과정에서 꼬리표처럼 행렬 L에 새겨지기에(어떤 행을 어떻게 조작했는지) 이를 바꾸면 문제가 생긴다.
만약 행의 순서를 바꾸면 소거 과정의 순서와 내용이 달라지기에 L행렬도 달라져야 하므로 LU분해가 아니게 된다.
만약 행의 순서를 바꿔야 계산이 된다면 분해하고자하는 A행렬의 행 순서를 미리 바꿔놓고 LU분해하는 경우가 되며 이를 PLU분해라 한다.
질문 3:미지수를 소거할 때, x를 먼저 없앤 다음 y보다 z를 먼저 없애면 안 되나요? 꼭 x > y > z 순서대로 소거해야 상삼각행렬이 되나요?
이는 보통 우리가 식을 계산할 때에 R2를 기준으로 R1가 아닌 R3이 더 계산하기 편하다면 이런 선택을 할 것이다.
하지만 가우스 소거법을 위해선 x > y > z 순서로 미지수를 소거해야 한다.
왜냐하면 아래와 같이 계단 모양의 상삼각행렬을 만드는 것이 목표이기 때문이다.
[* * *|*]
[0 * *|*]
[0 0 *|*]만약 x를 없앤 후 z를 없애고 y를 나중에 없앤다고 하면 어떻게 될까? 아래와 같이 될 것이다.
[x y z|n1]
[0 y z|n2]
[0 y 0|n3]3행의 경우 z가 중간에 없애고 y는 여전히 남아있는 상태가 된다. 지금은 계산하는 데에 문제가 없는 엉켜 있는 행렬이지만
이러면 차원이 만약 증가한다면 역방향 대입도 어려워지게 된다. 그래서 계단행렬 모양으로 만드는 것이다.
따라서 가우스 소거법은 본질적으로 정해진 순서대로 소거하는 것이 수치적으로 안정적이고 구현이 직관적이기 때문에 널리 쓰인다.
이러한 일관된 규칙성 덕분에, 가우스 소거법은 계산 알고리즘화 및 코드 구현에 매우 적합한 방식이 된다.
질문 4:행렬 L의 초기 상태가 왜 대각성분이 모두 1인가요?
이런 형태의 행렬을 항등 행렬 또는 대각 행렬이라고 한다. 표기는 보통 I로 한다.
AI=A이기에 항등 행렬이라 불린다. 이유는 곱하면 자기 자신이 나오기 때문이다.
I=
[1 0 0 ..0 0]
[0 1 0 ..0 0]
[0 0 . 0 0]
[0 0 0 . 0 0]
[0 0 0 . 0]
[0 0 0 ..1 0]
[0 0 0 ..0 1]