[KOCW-3] LU 분해

포스팅에 앞서 이 게시글은 Reference의 contents를 review하는 글임을 밝힌다.

 

 

 

 

「LU 분해(Fatorization, Composition)이란?」

LU 분해의 정의는 행렬을 하삼각행렬 L과 상삼각행렬 U의 곱으로 표현하는 수치해석학의 기술이다. 한마디로 '행렬의 인수분해'를 말한다.

앞선 포스트부터 우리가 집중하여 알아보고 있는 1차 연립방정식의 경우에서는 풀이를 수월하게 하기 위해 행렬로 변환하였을 때, 각 방정식을 소거할 수 있는 인수들의 행렬 L(Lower matrix)과 소거되어 결과로 표현된 행렬 U(Upper matrix)의 인수분해형태를 ‘LU분해’라고 부른다.

'L'은 단위행렬에 각 방정식 간의 소거 내용이 원소로 포함된 형태의 행렬이며 '원소행렬'이라고 부른다. 하삼각 행렬의 형태를 띠기 때문에 'Lower matrix'의 앞자를 따 'L'로, 'U'는 'L'로 인수분해된 행렬의 형태가 상삼각행렬의 형태를 띠기 때문에 'Upper matrix'의 앞자를 따 'U'로 불린다.

 

앞선 설명을 기반으로 아래의 예시로 들은 3개의 방정식을 보자.

1. 2u + v + w = 5
2. 4u - 6v =-2
3. -2u + 7v + 2 = 9

 

좌변에 대한 LU분해를 하기위하여 우변은 생각하지 않기로 한다.
좌변을 행 벡터 형식으로 나타내면 다음과 같다.

 

행 벡터 변환

 

이제 이 벡터에 대한 변환을 이어갈 것이다.
아래는 단위행렬과 원래의 행렬로 분리하여 표현한 식이다.

 

단위행렬×원래의 행렬

 

다음은 ①번째 원소인 'u'를 기준(Pivot)으로 [②번식 - 2×①번식]의 내용을 벡터에 포함하여 표현한 것이다.

 

2행 1열의 원소에 연산내용이 반영

 

위와 같은 원리로 ①번째 원소인 'u'를 기준(Pivot)으로 [③번식 + 1×①번식]의 내용을 벡터에 포함하여 표현한 것이다.

 

3행 1열의 원소에 연산내용이 반영

 

다음은 같은 원리로 진행되었지만, 주의할 점이 있다. ②번째 원소인 'v'를 기준(Pivot)으로 [③번식 + 1×②번식]의 내용을 벡터에 포함하여 표현한 것이다. 여기서 ②번식은 기존의 [4u-6v]가 아닌 소거에 의해 변화된 [-8v-2w]라는 것이다.

 

2행 2열의 원소에 연산내용이 반영

 

앞서 본 바와 같이 원래의 행렬에서 각 방정식의 소거 내용을 원소로 담고 있는 행렬 'L'을 계속해서 '원소 행렬'이라고 하였다. 그렇다면 '원소 행렬'은 정확히 어떤 의미를 가지고 있을까?

 

 

 

 

「원소 행렬이란?」

가우스 소거법에 의한 원래 행렬의 변화 내용이 담긴 행렬을 말한다. 원소 행렬은 'L'의 이름에서 알 수 있듯이 하삼각 행렬의 형태이며, 역행렬은 하삼각형L(주대각 제외)에 해당하는 원소들에 –1 곱한 행렬이다

아래의 예시의 예시를 보자.

 

행렬 A에 대한 원소 행렬 L

②번식 – 3×①번식
③번식 – 2×①번식 – 4×②번식(변형 2번식)

 

원소행렬과 원소행렬의 역행렬

 

원소 행렬은 곧 방정식 소거 내용의 'History'가 담긴 행렬이다.

 

이러한 LU분해를 통해서 L×I(단위행렬)와 LD(대각행렬)U와 같은 행렬들로 나누어서 행렬들의 특성을 더 깊이 살펴볼 수 있으며 이러한 내용들을 추후 다룰 예정이다.

행렬 'D'는 Diagonal matrix 즉, 대각행렬을 말한다. 대각행렬은 주대각선 성분을 제외한 모든 성분이 0인 정사각 행렬인 행렬을 말한다. 대각행렬은 행렬의 거듭제곱 연산에 있어 편리함을 제공한다는 장점이 있다.

 

 

 

 

「행 전환(Row exchange, Pivoting)이란?」

행 전환이란, 행렬의 행 사이의 행 배치 순서를 교환하는 것을 말하며, 통상 치환 행렬(Permutation matrix)을 통해 진행된다. 치환 행렬의 정의는 순서가 부여된 임의의 행렬을 의도된 다른 순서로 뒤섞는 연산 행렬을 말하는데, Permutation이라는 영단어에서 유추할 수 있듯이 행 배치전환 목적을 가진 단위행렬의 순서 전환 버전이라고 생각하면 쉽다. 이게 무슨 말이냐면,피봇팅(Pivoting)이 필요한 경우에 대상 행렬 A의 앞에 곱해주는 식으로 표현한다.

앞서 보았던 예시의 행렬을 보자.

 

행 벡터 변환

 

앞선 포스트에서 행렬에 대하여 가우스 조던 소거법을 진행하다 보면, 기준(Pivot)이 되는 원소가 조기에 소멸되는 경우가 있고, 이러한 경우에 방정식의 순서를 바꾸어 줌으로써 편리한 연산을 도모하는 방법이 피봇팅(Pivoting)이라고 하였다.

이러한 피봇팅을 하기 위해 대상이 되는 행렬에 식의 순서를 정해주는 행렬을 곱해주는데 이를 '치환 행렬'이라고 하는 것이다.

 

참고로 치환 행렬의역행렬은 치환행렬의 전치 행렬이다.

 

치환행렬과       그것의 전치행렬

 

이로서 가우스 소거에 대한 내용을 행렬의 인수분해 형태로 완벽하게 표현이 가능하다.

 

행렬A에 대한 LU 분해

 

 

 

 

「마무리」

LU 분해란, 하삼각 행렬L과 상삼각행렬 U의 곱으로 표현하는 '행렬의 인수분해'이다.

원소 행렬이란, 가우스 소거법에 의한 내용이 담긴 행렬이다.

행 전환이란, 피봇팅을 위한 행들의 배치전환을 말하며 이를 위하여 대상이 되는 행렬에 곱해지는 인자를 치환 행렬이라고 한다.

치환 행렬은 피봇팅을 위한 각 행의 순서위치정보가 녹아든 행렬이다.

 

 

 

 

「참고」

https://www.youtube.com/playlist?list=PLSN_PltQeOyjDGSghAf92VhdMBeaLZWR3

2013 2학기 선형대수[이상화 교수]