이 절에서는 가우스 소거법을 사용하여 행렬을
삼각화 할 것이다.
Definition
5.2.1
|
다음과 같은 형태의 행렬을 order가 n인 elementary
lower triangualr 행렬이라 한다.

만약, 위처럼 k번째 column에서
0 이 아닌 원소들이
나타나면 행렬 E는 ,
E
= I +
여기서, I 는 order가 n인 단위행렬,
= (0, 0, ... ,0, , ... , , 는 k번째 단위벡터.
|
만일 A = LU ( L: lower triangle, U
: upper triangle)이면, Ax = b의 방정식 문제는 LUx
= b 로 변환된다. 그러면 Ly = b는 전방대치법으로
Ux = y는 후방 대치법으로 쉽게 구할 수 있다. 따라서
주어진 문제 Ax = b는 용이하게 풀어진다.
행렬 A의 Row Echlon Form은 upper
triangle 이다. 그런데 U는 elementary matrix를 곱함으로써
얻어진다. 즉 이 되고 이다. 더구나 와 이들의 역행렬도 모두 lower triangle이다. 따라서 " row interchange는
안하고 Gauss 소거법을 진행 " 시켰다고 생각하면
A = LU로 쓸 수 있다.
|
Example
5.2.0
|
다음 방정식의 해를 구하여라.

, , 이라 하면,
따라서
로 분해할 수 있다. 따라서 주어진 문제는
에서 이고
에서 이 된다.
|
Lemma
5.2.1
|
, ( ) 그러면 Ea가 의 multiple이 되는 E가 존재한다.
Proof: E를 다음과 같이 정의하자.
그러면 E는
가 되는 elementary lower triangle 행렬이다.
|
Definition
5.2.2
|
원소 (i = 2, 3, ... , n)를 multipliers라 한다.
|
5.2.1 Gaussian Elimination without Pivoting
는 에 elementary lower triangular 행렬을 연산한 것이다.
Set A = 
Step 1: Elementary행렬 은 = A의 첫 번째 column에서 (1 , 1) entry 아래가 0 이 되도록 하는 행렬이라
하자.
즉, 이고 은 다음과 같은 행렬이다,
multipliers는 (i =2,3 ... , n)가 된다
Step 2: Elementary행렬 는 = A의 두번째 column에서 (2 , 2) entry 아래가 0 이 되도록 하는 행렬이라
하자.
먼저 다음과 같은 order가 (n-1)인 elementary행렬
을 구한다.
multipliers는 (i=3.4...,n)가 된다
그러면 는 다음과 같이 두번째 column의 (2 , 2) entry 아래가 0 이 된다.

Step k : 가 되는 Elementary행렬 는 k번째 column의 (k , k) entry 아래가 0 이 된다. 는 두 단계의 step를 갖는데, 우선 order n-k+1의 아래와 같은 elementary행렬 을 구한다음 를 표현한다.
, 
multipliers는 (i = k+1, ... , n)가 된다
Step n-1 : (n-1)단계에서의, 는 아래와 같은 upper triangular 행렬이다.


, 라 하자. 그러면 가 된다. 는 unit lower triangular행렬이므로 이 존재한다. 라 하자. 그러면 식 는 로 변형된다. 이 factorization을 LU분해라 한다.
|
Definition
5.2.3
|
을 pivots라 부르고, 위 에서의 LU분해을 Gaussian elimination without
row interchanges라 한다. 이것은 일반적으로 Gaussian
elimination without pivoting라 한다.
|
Theorem
5.2.1
|
A는 모든 leading principal minor가 0
이 아닌 행렬이라 하자. 그러면 A는 유일하게 LU분해된다 :
A=LU, L은 unit lower triangular이고 U는 upper
triangular
|
Example
5.2.1
|
다음을 LU분해 하여라

Step1: Cpmpute . multipliers : 


Step2: Cpmpute . multipliers : 

. 따라서,
이고
이다.
|
1. 각 elementary 행렬 는 에 의해서 유일하게 결정된다.
2. , 그러면
(a) (i = 1, 2, 3, ... , k ; j = 1, 2, ... , n) (k번째 row까지)
(b) (i = k+1, k+2, ... , n ; j = k+1, k+2, ... , n) (n-k번째
row부터)
3. 가 결정되면 A를 대치한다.
4. 이런 단계를 반복하면 (n-1)단계에서는
가 된다.
|
ALGORITHM
5.2.1
|
Gaussian elimination without pivoting를
사용한 Triangularization
For k = 1, 2, 3 ... (n-1);
1. multipliers로 부터
( i = k+1, k+2, ... , n )
2. (i = k+1, ... n: j = k+1, ... , n)
|
Difficulties with Gaussian
Elimination without Pivoting
다음 행렬에 Gaussian Elimination
without Pivoting을 적용하면,

첫단계에서 multiplier 이고
따라서,
이 되어 문제가 발생한다. 그 이유는 ;
으로 0 에 근사하다. 이것은 pivot가 작으면 큰 multiplier가 되기 때문이다.
이런한
것을 방지하기 위해 row interchange 한다. 다음의
행렬에 대해서 동일한 계산을 해보자.

Gaussian elimination에 의해,

이 경우 pivot에 의하면 이 되므로
가 된다.
|
5.2.2 Gaussian Elimination with
Partial Pivoting
위의 예제에서 보았드시 row interchange를 함으로써 pivot을
크게 할 수 있다. 따라서 elimination을 하기전에 가능한한
pivot을 크게 하는 작업이 선행되어야 한다. 이러한 방법은 column entry에서
적당한 pivot을 고른다고 하여 partial pivoting이라 부른다.
(차후에 complete pivoting 방법을 소개할 것이다) 그러나, multipliers가
크다고 해서 반드시 instability한 것은 아니다.
Example
5.2.2
|
partial pivoting을 사용하여, 다음 행렬이 MA
= U가 되도록 하는 M과 U을 구하여라.

우선 pivot entry는 1이고, = 2이다.






|
ALGORITHM
5.2.2
|
Gaussian elimination without Complete pivoting를
사용한 Triangularization
For k = 1, 2, 3 ... (n-1);
1. 는 . 만약 이면 중단.
2. ( 와 k번째의 rows을 interchange) ( j = k, k+1, ... , n)
3. ( i = k+1, k+2, ... , n )
4. (i = k+1, ... n: j = k+1, ... , n)
|
5.2.3 Gaussian Elimination with
Complete Pivoting
Theorem
5.2.3
|
A는 모든 leading principal minor가 0
이 아닌 행렬이라 하자. 그러면 A는 유일하게 LU분해된다 :
A=LU, L은 unit lower triangular이고 U는 upper
triangular
|
Gaussian Elimination with Complete
Pivoting은 k번째 step에서 pivots을 (k-1)번째 rows 아래 submatrix의
모든 entries중에서 결정 하는 것이다. 따라서 만약에 pivot이 가 ( k, k )에 위치이면 row는 r과 k번째를 column은 s와 k번째를 각각 interchange
한다. 는 Gaussian elimination without Partial pivoting의 에 k번째와 s번째의 column을 interchange하는 permutation행렬 를 뒤쪽에 곱하는 형태가 된다. 즉,
이다.
(n -1)단계에서 라 하자. 그러면,


여기서 , 라 하자. 그러면 U = MAQ가 된다.
또한, 유사한 방법으로 PAQ = LU가
된다.
|
Example
5.2.5
|
complete pivoting을 사용하여, 다음 행렬을 triangularize
하여라.

Step1 : k = 1. pivot entry는 이고
, , 따라서,
, 
Step2 : k = 2. pivot entry는 이고
, ,
, 따라서,

PAQ = LU
|
ALGORITHM
5.2.2
|
Gaussian elimination without Complete pivoting를
사용한 Triangularization
For k = 1, 2, 3 ... (n-1);
1. 와 는 . 만약 이면 중단.
2. ( 와 k번째의 rows을 interchange) ( j = k, k+1, ... , n)
3. ( 와 k번째의 columns을 interchange) ( j = 1, 2 ... , n)
4. ( i = k+1, k+2, ... , n )
4. (i = k+1, ... n: j = k+1, ... , n)
|
|