[수치해석 07] LU분해법과 역행렬

LU 분해법

 

하나의 행렬 A를 주대각성분이 1인 하삼각행렬 L, 상삼각행렬 U로 나누는 것

[A] = [L][U]

 

 

계수 [A]는 같고, 우변만 달라 여러 방정식의 해를 구해야 할때, 각 방정식의 해를 O(n^2)으로 구할 수 있다.

 

[A]{X} = {B1}

[A]{X} = {B2}

...

 

가우스 소거법을 이용한다.

 

해를 구하는 과정 

1. LU 분해 단계

[A]를 [L][U]꼴로 분해한다.

 

행렬에 대해 가우스 소거법을 적용하여 상삼각행렬을 만들고,

이때 발생하는 계수들로 하삼각행렬을 구성한다

 

 

저장공간 활용을 위해 다음과 같이 저장할 수 있다.

 

 

 

알고리즘

 

 

2. 대입 단계

[L] 과 [U] 를 이용하여 벡터 {B} 에 대한해 {X}를 구한다.

 

[A]{X} = {B}

⇒ [L][U]{X} = {B} : [A]를 [L][U]로 분해, 이 과정에서 D를 얻을 수 있다.

⇒ [U]{X} = {D} : [U]{X} = {D}로 치환

⇒ [L]{D} = {B} : 방정식의 근 {D}를 구한다. (D는 LU분해하는 과정에서 얻을 수도 있다.)

⇒ [U]{X} = {D} : 방정식의 근 {X}를 구한다.

 

1. [L]{D} = {B}의 해 {D}를 구한다. 이때, {D}는 상삼각행렬을 만들 때 함께 변환된 {B'}과 같다.

 

D는 확장행렬에서 구했으므로, 굳이 구할 필요 없어보인다.

 

2. [U]{X} = {D}의 해 {X}를 구한다. 이 결과는 원 방정식의 전진 소거 결과와 같다.

 

 

LU 분해법 알고리즘

 

소거 단계에서 생성된 인자 f 들은 행렬의 하부에 저장된다.

순서벡터 O를 이용하여 피벗화 결과의 순서를 추적한다.

요소들의 축척화된 값들이 피벗화에 사용된다.

피벗화 단계에서 대각선 항들을 탐색, 0에 가까우면 특이시스템이고, 에러로 처리한다.

 

순서벡터 O : 피벗팅을 수행할 때 각 행을 직접 바꾸는 대신, 해당 행을 바꿨다는 '표시'를 저장하는 벡터

 

 

 

 

 

Crout 분해

LU 분해의 결과로 A 행렬은 L과 U로 나뉜다.

이때 A 행렬의 각 원소는 L과 U의 행렬곱에 따라 a_ij = l_i1u_1j + l_i2u_2j + ... + l_inu_nj 꼴로 나타낼 수 있다.

 

예를 들어, a₁₁ = l₁₁u₁₁ + l₁₂u₂₁ + l₁₃u₃₁ + l₁₄u₄₁ = l₁₁*1 + 0 + 0 + 0 = l₁₁ 이다.

이런 방식으로 L과 U의 원소를 원래 식 A의 원소로 표현하는 것이 Crout 분해다.

 

값을 직접 구하면서 이해해보자.

 

l₁₁ = a₁₁

l₂₁ = a₂₁

l₃₁ = a₃₁

l₄₁ = a₄₁

(위에서 a₁₁을 구하듯이 구한다)

 

a₁₂ = l₁₁ u₁₂    ⇒     u₁₂ = a₁₂ / l₁₁

a₁₃ = l₁₁ u₁₃    ⇒     u₁₃ = a₁₃ / l₁₁

a₁₄ = l₁₁ u₁₄    ⇒     u₁₄ = a₁₄ / l₁₁

 

처음에 구한 값은 다음과 같다.

 

l₁₁ u₁₂  u₁₃  u₁₄

l₂₁  l₂₂  u₂₃  u₂₄

l₃₁  l₃₂   l₃₃  u₃₄

l₄₁  l₄₂   l₄₃   l₄₄

 

행에 대해서는 11~ 41을, 열에 대해서는  12 ~ 14를 구했다.

이렇게 구한 식은  내부 (3x3 크기) 다른 변수를 정의하는데 다시 사용된다.

 

a₂₂ = l₂₁u₁₂ + l₂₂    ⇒    l₂₂ = a₂₂ - l₂₁u₁₂

a₃₂ = l₃₁u₁₃ + l₃₂    ⇒    l₃₂ = a₃₂ - l₃₁u₁₃

a₄₂ = l₄₁u₁₄ + l₄₂    ⇒    l₄₂ = a₄₂ - l₄₁u₁₄

 

a₂₃ =  l₂₁u₁₃ + l₂₂u₂₃  ⇒    u₂₃ = (a₂₃ - l₂₁u₁₃) / l₂₂

a₂₄ =  l₂₁u₁₄ + l₂₂u₂₄  ⇒    u₂₄ = (a₂₄ - l₂₁u₁₄) / l₂₂

 

이번에 구한 영역은 다음과 같다.

 

l₁₁ u₁₂  u₁₃  u₁₄

l₂₁  l₂₂  u₂₃  u₂₄

l₃₁  l₃₂   l₃₃  u₃₄

l₄₁  l₄₂   l₄₃   l₄₄

 

이렇듯 Crout 분해법은 기존 A의 원소를 이용하여 L 및 U의 원소를 지정하는 방식의 분해법이며,

각 L 및 U의 원소는 아래 이미지에 언급된 공식에 따라 도출된다.

 

공식에 따라 나머지 값을 구해보면,

 

l₃₃ = a₃₃ - l₃₁u₁₃ - l₃₂u₂₃

l₄₃ = a₄₃ - l₄₁u₁₃ - l₄₂u₂₃

l₄₄ = a₄₄ - l₄₁u₁₄ - l₄₂u₂₄ - l₄₃u₃₄

 

(1부터 뒤 index-1까지 진행)

 

u₃₄ = (a₃₄ - l₃₁u₁₄ - l₃₂u₂₄) / l₃₃

 

(1부터 앞 index-1까지 진행)

 

장점

간결한 loop로 구현되며, 저장공간이 절약된다.

또한 [A]의 요소들이 분해과정에 한 번 사용된 후에는 다시 사용되지 않는다. ( L 및 U의 요소들이 대신 사용된다.)

[A]에 [L]과 [U]의 값을 저장할 수 있다.

 

 

 

역행렬

 

정사각행렬 [A]에 대해 곱이 [I] 가 되는 행렬.

 

 

우변에 단위벡터를 놓고 각각의 단위벡터에 대한 해를 구하여 열 단위로 구해보자. 

[A]{X} = {B} 꼴로 두는 것.