5.1 A Computational Methodology in Numercial Linear Algebra

5.1 A Computational Methodology in Numercial Linear Algebra

대부분의 계산 알고리즘은 공통적으로 다음과 같은 구조로 나타낼 수 있다.

1. 우선 주어진 문제를 "reduced problem"로 바꾼다.

2. reduced된 문제를 푼다.

3. 마지막으로 reduced problem의 해를 처음의 문제의 해로써 표현한다.

예를들어, 3장에서 선형 방정식 Ax = b 의 해를 구할때 triangular로 변형한후 그방정식을 풀었다. 그리고 eigenvalue 계산에서 행렬 A를 Hessenberg 형태로 바꾸고 QR iterations을 한다.

5.2 Elementary Matrices and LU Factorization

이 절에서는 가우스 소거법을 사용하여 행렬을 삼각화 할 것이다.

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라 한다.

이고 이므로 L은 다음과 같다.

( 는 order가 n인 단위행렬, = (0, 0, ... ,0,, ... ,, 는 i번째 단위벡터. )

그러므로 L은 역행렬을 계산하지 않고 구할 수 있다.

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한 것은 아니다.

다음은 Gaussian Elimination with Partial Pivoting의 첫단계과 (n -1)단계이다.

Step 1 : column에서 가장 큰 원소을 이라 하자.

다른 row는 변하지 않고 1 번째와 번째의 row을 interchalge하는 permutation 행렬 이라 하자.

은 행렬 A의 1 번째와 번째의 row을 interchalge한다.

의 첫 번째 column에서 (1, 1)아래가 모두 0이 되도록 행렬 을 구하자.

Step n-1 : 행렬 은 upper triangular 행렬이다. U을,

라 하자. 그러면,

여기서 라 하자. 그러면 U = MA가 된다.

그리고, , 라 하면 PA=LU가 된다.

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)

5.3 Stability of Gaussian Elimination

Gaussian elimination 알고리즘의 stability는 reduced행렬 의 원소의 growth를 계산함으로써 더욱 이해하기가 용이하다.

Definition 5.3.1

행렬 A의 growth factor 는 의 가장 큰 값이다.

,여기서 ,

Example 5.3.1

(a) Gaussian elimination without pivoting에 의해

, 그러면

(b) Gaussian elimination without partial pivoting은

, 그러면

Growth Factor and Stability of Gaussian elimination without Pivoting

Gaussian elimination without pivoting의 은 특별한 경우(예를 들어, Symmetric Positive definite 행렬)를 제외하고는 비교적 크다고 할 수 있다. 나중에 보겠지만 Gaussian elimination without pivoting은 일반적으로 completely unstable algorithm이다.

5.4 Householder Transformations and Applications to QR Factorization and Hessenberg Reduction

Definition 5.4.1

다음과 같은 형태의 행렬을 Householder 행렬이라 한다.

(u:nonzero)

단위벡터 u로써 Householder행렬 H을 정의하므로 다음의 결과를 얻을 수 있다.

따라서 Householder 행렬의 eigenvalue의 값은 -1이다.

의 성질을 갖는 벡터 v 는 Householder 행렬에 의하여 다음과 같이 변환된다.

따라서 에 정의된 단위벡터 u와 orthogonal한 의 모든 벡터 v는 Householder 행렬의 eigenvector이며 이때의 eigenvalue 값은 1이다.

그러면 행렬 H의 eigenvalue와 eigenvector 값은 어떤것들이 있을까? 답은 유한개가 아니다. 왜냐면,

은 m - 1의 dimension을 갖는다. 따라서 subspace 는 m - 1 개의 벡터들로 구성 되어지며 이벡터는 H의 eigenvector이며 eigenvalue의 값은 1이다. 따라서 eigenvalue가 -1 경우의 eigenvector u와 함께 eigenvector(value)가 된다.

이상으로부터 다음의 Theorem을 얻을 수 있다.

Theorem 5.4.0

Householser 행렬은 eigenvector u에 대해 single eigenvalue -1과 eigenvector가 v (인 v)인 경우에 대해 (m-1)-fold의 eigenvalue 1을 갖는다.

Lemma 5.4.0

Householder행렬 H는 symmetric이고 orthogonal 이다.

proof : 이고,

가 되므로 symmetric이고 orthogonal 이다.

Lemma 5.4.1

벡터 에 대하여 Hx가 의 상수배가 되는 Householder 행렬 H는 항상 존재한다.

proof : H를 다음과 같이 정의하면 Hx가 의 상수배가 된다.

with

ALGORITHM 5.4.1

Creating Zeros in a Vector with a Householder Matrix

Step 1 : , i = 1, 2, ... ,n

Step 2 : , i = 1, 2, ... ,n

Step 3 :

Step 4 :

Step 5 :

Example 5.4.1

가 되는 u를 찿아라, where

m = 4, . 그래서 ,

따라서

5.4.1 Householder Matrices and QR Factorization

Theorem 5.4.1 Householder QR Factorization Theorem

주어진 행렬A에 대하여, A = QR이 되는 orthogonal 행렬 Q와 upper triangular 행렬 R이 존재한다.

행렬 ( 는 Householder 행렬)

위에서의 QR을 행렬 A의 QR분해라 한다. linear systems의 해와, least-squares문제, eigenvalue, singular-value계산에서 사용된다.

다음은 Householder행렬을 사용하여 행렬 A의 QR분해를 한 것이다.

Step 1: Householder행렬 은 의 첫 번째 column에서 (1 , 1) entry 아래가 0 이 되도록 하는 행렬이라 하자.

즉, 이고 은 다음과 같은 행렬이다,

이라 하고,

Step 2: EHouseholder행렬 은 의 두 번째 column에서 (2 , 2) entry 아래가 0 이 되도록 하는 행렬이라 하자.

는 다음과 같이 구할 수 있다. 우선 Householder행렬

그리고

그러면 이라 할 수 있다.

Step k : k번째 단계에서의 다음과 같이 order가 n-k+1인 Householder 행렬은

Step n-1 : (n-1)단계에서의, 는 upper triangular R이 된다. 왜냐면,

, k = n-1, ... , 2

라 하자. 각 Householder 행렬는 orthogonal이므로 역시 orthogonal이 된다.

그러므로 가 된다.

Example 5.4.2

Step1 : k = 1

Construct :

따라서,

Step1 : k = 2

: upper triangle

: orthogonal

5.4.2 Householder QR Factorization of a Nonsquare Matrix

A를 행렬 이라 하자. s = min{n, m-1}단계를 거쳐서;

Example 5.4.4

s = min(2, 2)=2

Step1 :

따라서

Step2 :

, 이다. 따라서,

5.4.3 Householder Marrices and Reduction to Hessenberg Form

Theorem 5.4.1 Hessenberg Reduction Theorem

임의의 행렬 A는 항상 upper Hessenberg matrix 와 orthogonal similarity 하다 :

Example 5.4.5

n = 3이므로 한단계만 거치면 된다.

5.5 Givens Matrices and Application to QR Factorization and Hessenberg Reduction

Definition 5.5.1

다음과 같은 형태의 행렬을 Givens matrix라고 한다.

where

만약 라고 하면 Given matrix는 로 나타낼 수 있다. 일반적으로 를 Givens rotation or plane rotation in the ( i , j ) plane 라고 부른다. 그리고 이므로 이 된다.

만약, 이면 c와 s는 다음과 같이 구할 수 있다.

, 이고

에 의해서 가 된다.

Example 5.5.1

이면 c와 s는 다음과 같다.

, 이고,

이 된다.

ALGORITHM 5.5.3

Creating Zeros in a Specified Position of a Matrix Using Givens Rotations

Step 1 : 다음을 만족하는 을 구한다.

Step 2 : Overwrite A with A ; n = 1,2,3, ... ,n)

Example 5.5.1

을 이용하여 Creating a zero in the ( 2 , 1 ) position을 하여라.

Step 1: 우선 c, s를 구하도록 한다.

Step 2 : 는 다음과 같다.

이므로

이 된다.

5.5.1 Givens Rotations and Factorization

Theorem 5.5.1 Givens QR Factorization Theorem

주어진 행렬 A에 대하여, orthogonal matrices , s = min(n, m-1)가 존재한다. 여기서 이다.

이라 하면 A = QR이 된다.

5.5.2 Uniqueness in QR Factorization

Theorem 5.5.2 QR Uniqueness Theorem

행렬 A를 linearly independent column을 갖는 행렬이라 하자. 그러면 A = QR형태를 만족하며, orthonormal columns을 갖는 행렬 Q와 positive diagonal한 upper triangular 행렬 R이 각각 유일하게 존재한다.