1.4 소거법과 A = LU분해, Cholesky분해

1.4 소거법과 A = LU

핵심: rank 1인 행렬의 관점에서 소거법을 살펴보는 것.
즉, 기존 행렬인 A는 rank = 1인 행렬들의 합으로 볼 수 있다.

ex.

 

 

1.4 .1 소거법을 이용한 Ax = b의 풀이

R³공간에서 세 평면이 만나는 것을 시각화하는 것은 쉽지 않다.
Rⁿ공간에서 초평면(hyperplane) n개가 한 점에서 만남을 시각화 하는 것도 쉽지 않다.

But! 열벡터의 일차결합은 훨씬 쉽다!!

 - 행렬 A에서는 반드시 3 or n개의 일차독립인 벡터가 있어야 한다.
 - 이 열들은 반드시 R³의 동일한 평면 or Rⁿ의 동일한 초평면에 있지 않아야 한다.
이를 아래와 같은 문장으로 해석가능하다.
일차독립인 열  Ax = 0의 유일해는 영벡터 x = 0이다.

즉, 일차독립은 모든 열에 0을 곱해야하는 경우만 열들의 결합이 0벡터가 됨을 의미한다.

if, 해가 유일: 열벡터의 일차결합이 b가 되는 유일한 결합을 소거법으로 Ax = b의 해를 구할 수 있다.




이때, 소거법은 열 하나하나에 순서대로 적용해 상삼각행렬 U를 찾을 때까지 계속 진행한다.

1행은 변하지 않는다.
이후 1행에 수를 곱해 A의 2, 3, 4행에서 곱한 결과를 뺀다.

다만, 곱셈과 덧셈을 분리하는 이런류의 계산은 높은 계산량을 요구한다.
따라서 이를 위한 해결책이 바로 A = LU이다.

 

 

 

1.4 .2  A = LU 분해

소거법은 행렬 A를 A = LU라는 L(하삼각행렬)과 U(상삼각행렬)의 곱으로 분해하는 것이다.

 

 

 

1.4 .3  Ax = b의 해법

Ax = b의 해를 구하려면 이 방정식 양변에 동일한 변환을 가해야 한다.

직접적인 방법: b를 열에 추가한 행렬 [A  b]를 다루는 것
A에 수행하는 소거법(AL⁻¹ = U)의 단계를 b에도 똑같이 적용한다.
 - [A  b] = [LU  b]에서 시작해 소거법을 적용하면
 - [U  L⁻¹b] = [U  c] 즉, Ux = c를 얻는다.

 Ax = b는 Lc = b와 Ux = c로 나누어 진다.
소거법으로 c를 얻은 후 대입법으로 x를 구한다.
즉, x = U⁻¹c = U⁻¹L⁻¹b = A⁻¹b

 

 

 

 

1.4 .4 행 교환(치환)

모든 n×n 가역행렬(invertible matrix) A는 PA = LU를 만족한다.
이때, P는 치환행렬이다.


Ex.

 

 

cf. Cholesky's Decomposition  (for. symmetric matrix)

1. A가 대칭행렬 이다.
2. 행렬식의 값이 Positive 이다
   
   위의 조건에 대해 LU분해의 결과, 아래와 같다.