행렬 분해(Decomposition)  I

  (이상구교수의 강의 자료를 백명국조교가 정리한 내용입니다.)

 LU-분해

정의 1.1 만일 행렬이 기본 행연산(elementary row operation)에 의해서 단위행렬(identity matrix)로 변환되면 그 행렬을 기본행렬(elementary matrix)이라 하고 아래와 같은 형태의 행렬은 차수(order)가 인 기본 하삼각(elementary lower triangular)행렬 이라 한다.

 만약, 위처럼  번째 열(column)에서 0이 아닌 원소들이 나타나면 행렬 는

    = +

여기서, 는 차수(order)가 인 항등행렬, = (0, 0, ... ,0, , ... , ), 는 번째 단위벡터 (0, ... , 0, 1, 0, ... , 0)이다.

 만일 = ( : lower triangle, : upper triangle)이면, = 의 방정식 문제는 = 로 변환된다.

그러면 = 는 전방대치법(forward substitution)으로 = 는 후방대치법(back substitution)으로 쉽게 구할 수 있다.

따라서 주어진 문제 = 는 쉽게 풀어진다.

 일반적으로 " 행교환(row interchange)을 하지 않고 Gauss 소거법(Elimination)을 진행 " 시켰다고 생각하면,

아래와 같은 이유로 로 쓸 수 있다. 행렬 를 Gauss 소거법을 통하여 행사다리꼴(Row Echlon Form)로 변환하면 상삼각(upper triangle) 행렬 U를 얻는다. 이 는 에 하삼각행렬인 기본행렬(elementary matrix)들을 곱함으로써 얻어진다. 즉 … = 이 되고 = [ … ]이다. 더구나 … 와 이의 역행렬 도 모두 하삼각 행렬이다.

 일반적으로, 해집합에 영향을 미치지 않으므로 필요한 행(row) 교환을 마친 후 Gauss 소거법을 쓰면 된다.(즉, , 는 치환행렬)

보조정리 1.1 벡터 ()를 아래와 같이 정의하자.

  , ( 0 )

그러면 는 의 상수배가 되도록 하는 가 존재한다.

증명) 를 다음과 같이 정의하자.

  그러면 는 = 이 되도록 하는

기본 하삼각(elementary lower triangular) 행렬이 된다.

정의 1.2 벡터 , 0 에 대하여 원소 = -( = 2, 3, ... , n)를 배수(multipliers) 라 한다.

1.1 피봇팅(Pivoting) 없는 Gaussian 소거법

는 에 기본 하삼각 행렬을 곱하여 얻은 행렬이다.

  = 라고 하자.

Step 1: 기본행렬 은 =의 첫 번째  열(column)에서 (1, 1) 성분의 아래가 이 되도록 하는 행렬이라 하자. 즉,

 이고 은 다음과 같은 행렬이다.

  배수(multipliers)는   = - ( =2, 3, ... , )이 된다.

Step 2: 기본행렬 는 = 의 두 번째  열(column)에서 (2, 2) 성분의 아래가 이 되도록 하는 행렬이라 하자.

먼저 다음과 같은 차수(order)가 ()인 기본행렬 을 구한다.

배수(multipliers)는 = - (=3.4 ... , )가 되고,

는 가 된다.

그러면 = 는 다음과 같이 두 번째  열(column)의 (2, 2) 성분의 아래가 이 된다.

Step : = 가 되는 기본행렬 는 번째 열(column)의 (, ) 성분의 아래가 이 된다. 는 두 단계를 거치는데, 우선 차수(order) 의 아래와 같은  기본행렬 을 구한다음 를 표현한다.

=,   

배수(multipliers)는 = - ( = +1, ... , )가 된다.

Step -1 : (-1)단계에서의, 는 아래와 같은 상삼각 행렬이다.

= ,   = … 라 하자. 그러면 =가 된다. 는 단위 하삼각(unit lower triangular) 행렬이므로 이 존재한다. = 라 하자. 그러면 식 = 는 =로 변형된다. 이 행렬분해(factorization)를 분해 라 한다.

정의 1.3 , , … , 을 피봇(pivots)이라 부르고, 위에서 시행한 분해를 행교환 없는 가우스 소거법(Gaussian elimination without row interchanges)이라 한다. 이것은 일반적으로 피봇팅 없는 가우스 소거법(Gaussian elimination without pivoting)이라 한다.

= = ( … )이고 = - 이므로 은 다음과 같다. 는 차수(order)가 인 항등행렬, = (0, 0, ... , , ... , )이고 는 번째 단위벡터이며

이 되므로, 은 역행렬을 계산하지 않고도 구할 수 있다.

정리 1.1 행렬 의 모든 선도 주축 소행렬식(leading principal minors)이 이 아닌 ×행렬이라 하자. 그러면 는 유일하게 로 분해된다. 즉 , 은 하삼각(lower triangular) 행렬이고 는 상삼각(upper triangular) 행렬이다.

예제 1.1 다음을 분해 하여라.

Step1: 배수(multipliers)를 계산하면: =-2, =-

Step2: 배수(multipliers)들을 계산하면: =-1

 = 따라서,

이고 이다.

LU 분해(Factorization)의

존재성과 유일성(Existence and Uniqueness)

 행렬의 분해가 존재하기 위해서는 피봇(pivot) 성분이 이 아니어야 한다. 매우 간단한 예로서 는 행을 교환하지 않으면 로의 분해가 존재하지 않는다. 따라서,

det() = ( = 1, 2, ... , )

라는 조건을 만족해야 분해는 항상 존재한다. 뿐만 아니라 이런 분해는 유일하다.

  = = 라고 가정하자. 그러면 는 비가역(nonsingular) 행렬 이므로,

 det(A) = det(U) = det()det(U),   det(A) = det(U) = det()det(U)

이 되어 , , , 역시 비가역 행렬이 된다. 따라서 = 그런데 은 하삼각 행렬의 두 곱이므로 역시 하삼각행렬이 되고, 이와 같은 논리에 의하여 은 상삼각 행렬이 된다. 따라서 상삼각 행렬과 상삼각 행렬이 일치하기 위해서는 단위행렬이 되어야 한다.

그러므로 = = 이 되어 = , = 가 된다.     

Algorithm 1.1 피봇팅(pivoting) 없는 가우스 소거법을 사용한 삼각화(triangularization)

= 1, 2, 3, ... , ( -1)에 대하여;

1. 배수(multipliers)로 부터

( = +1, +2, ... , )

2. ( = +1, ... : j = +1, ... , )

*    기호 " "는 왼쪽 값에 오른쪽 값을 대입함을 나타냄.

피봇팅(pivoting) 없는 가우스 소거법의 제한성

다음 행렬에 피봇팅 없는 가우스 소거법(Gaussian Elimination without Pivoting)을 적용하면,

첫 단계에서 multiplier = - 이고

  따라서,

이 되어 문제가 발생한다.

그 이유는 = 0.0001으로 0에 근사하다. 이것은 피봇이 작으면 큰 배수(multiplier)가 되기 때문이다. 이러한 것을 방지하기 위해 행교환(row interchange)을 한다. 다음의 행렬에 대해서도 동일한 계산을 해보자.

가우스 소거법에 의해,

이 경우 피봇팅에 의하여 = 1이 되므로

가 된다.

1.2 부분 피봇팅(Partial pivoting)에 의한 가우스 소거법

 앞절의 예제에서 보았듯이 행교환을 함으로써 피봇을 크게 할 수 있다. 따라서 소거를 하기 전에 가능한 한 피봇을 크게 하는 작업이 선행되어야 한다. 이러한 방법은 열중에서 적당한 피봇을 고른다고 하여 부분 피봇팅(partial pivoting) 이라 부른다.

다음은 부분 피봇팅의 의한 가우스 소거법의 첫 단계와 ( -1)번째 단계이다.

Step 1 : 열중에서 가장 큰 원소를 라 하자.

  다른 행은 변하지 않고 1번째와 번째의 행을 교환하는 치환행렬을    이라 하자.
은  행렬 의 1 번째와 번째의 행을 교환한다.
= 의 첫 번째 열에서 (1, 1)아래가 모두 이 되도록       행렬 을 구하자.

Step -1 : 행렬 은 상삼각 행렬이다. 를, =라 하자. 그러면,

여기서 라 하자. 그러면 =가 된다. 그리고, , 라 하면 =가 된다.

예제 1.2 부분 피봇팅을 사용하여, 다음 행렬이 = 가 되도록 하는 과 을 구하여라.

우선 피봇의 성분의 값은 1이므로 = 2이다.

,

Algorithm 1.2 부분 피봇팅(Partial pivoting)에 의한 가우스 소거법을 사용한 삼각화(triangularization)

= 1, 2, 3, ... ,(-1)에 대하여;

1. 는 ||=|| () 만약 = 0이면 중단.

2. (와 번째의 행을 교환) ( = , +1, ... , )

3. ( = +1, +2, ... , )

4. ( = +1, ... : = +1, ... , )

1.3 완전 피봇팅(Complete pivoting)에 의한 가우스 소거법

정리 1.2 [D, p128]A는 × 행렬이라 하자. 그러면 는 완전 피봇팅에 의한 가우스 소거법에 의하여 로 변환된다. 는 상삼각 행렬, 는 치환행렬이며 은 하삼각의 치환행렬이다.

 즉, 완전피봇팅에 의한 가우스 소거법(Gaussian Elimination with Complete Pivoting) 은 번째 단계에서 피봇을 (-1)번째 행 아래 부분행렬(submatrix)의 모든 성분 중에서 결정하는 것이다. 따라서 만약에 피봇 가 (, )에 위치이면 행은 과 번째를 열은 와 번째를 각각 교환한다.

는 완전피봇에 의한 가우스 소거법의 에 번째와 번째의 열교환을 하는 치환(permutation)행렬 를 뒤쪽에 곱하는 형태가 된다. 즉,

이다.

(-1)단계에서 = 라 하자. 그러면,

여기서 , 라 하자, 그러면 = 가 된다. 따라서 ==가 된다.

예제 1.3 완전 피봇팅을 사용하여, 다음 행렬을 삼각화 하여라.

Step1 : = 1. 피봇 성분은 이고

, , 따라서,

,

Step2 : = 2. 피봇 성분은 이고

  ,

,   따라서,

=

Algorithm 1.3 완전 피봇팅(Complete pivoting)에 의한 가우스 소거법을 사용한 삼각화(triangularization)

  = 1, 2, 3 ... (-1)에 대하여;

 1. 와 는 || = {||:(, )}, 만약 = 0이면 중단.

 2. (와 번째의 행을 교환) ( = , +1, ... , )

 3. (와 번째의 열을 교환) ( = 1, 2 ... , )

 4. ( = +1, +2, ... , )

 5. ( = +1, ..., : = +1, ... , )

 References

[D] Biswa Nath Datta, Numerical Linear Algebra and Applications, An International Thomson Publishing Company, (1995)

[FDFH] J. D. Foley, A. Van Dam, S. K. Feiner, and J. F. Hughes. Computer Graphics-Principles and Practice. Addison-Wesley Publishing Company, Inc, (1992)

[PB] Maria Petrou, Panagiota Bosdogianni, Image Processing, John Wiley&Sons, (1999)

[Z] Drmav C. Zlatko, New accurate algorithms for singular value decomposition of matrix triplets. SLAM J. Matrix Anal. Appl. 21 (2000), 1026-1050