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

 2. reduced된 문제를 푼다.

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

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

  는 에 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에 의하면 이 되므로

가 된다.

다음은 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)

Theorem 5.2.3

 A는 모든 leading principal minor가  0 이 아닌 행렬이라 하자. 그러면 A는 유일하게 LU분해된다 :

 A=LU, L은 unit lower triangular이고 U는 upper triangular

(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)

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이다.

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, . 그래서 ,

 따라서

Theorem 5.4.1 Householder QR Factorization Theorem

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

  행렬 ( 는 Householder 행렬)

 다음은 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

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

Example 5.4.4

s = min(2, 2)=2

Step1 :

따라서

Step2 :

,    이다.  따라서,

,  

Theorem 5.4.1 Hessenberg Reduction Theorem

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

Example 5.4.5

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

,   

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 : 는 다음과 같다.

 이므로

이 된다.

Theorem 5.5.1 Givens QR Factorization Theorem

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

 이라 하면 A = QR이 된다.

Theorem 5.5.2 QR Uniqueness Theorem

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

Example 5.5.6

의 R 구하여라.

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

 ,      

또 다음과 같은c, s를 구하도록 한다.

 ,      

Step 2 : 다음과 같은c, s를 구하도록 한다.

 ,      

여기서 얻은 upper triangular 행렬은 앞에서의 Householder method (Example 5.4.2)에 의해서 얻은값과 비교해 첫번째와 세번째 row의 부호만 다르다.

Example 5.5.7

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

 ,      

,   

Theorem 5.5.3 Implicit Q Theorem

   , (unreduced upper Hessenberg)을 만족하는 orthogonal matrices  P, Q의 첫번째 column이 동일하다고 하자. 그러면 , 는 를 만족하므로 , 는 essentialiy the same한다고 한다.

Example 5.5.8

Householder method 에 의해(Example 5.4.5),

  그리고 Givens method(Example 5.5.7)에 의해

Theorem 5.5.3에 의해서 ,  이라 하면 P와 Q는 첫 columns이 일치하다.

따라서 이 된다.  여기서 D = diag(1, -1, 1)

Example 5.6.1

Example 5.4.4에 결과에 의해,

이므로

이고 는

,   

Projection of Vector

m-vector b, vector 을 the projection of b onto R(A), is given by 유사하게,   , the projection of b onto the orthonomal complement of R(A)  is given by  

Note that   

Theorem 5.7.1 QR Column Pivoting Theorem

A를 rank(A) =  r 인   행렬이라 하자. 그러면 다음을 만족하는 의 permutation 행렬 P와 의 orthogonal 행렬 Q가 존재한다.

여기서 은 nonzero diagonal entries를 갖는 의 upper triangular 행렬이다.

Example 5.7.1

가 가장 큰 norm을 가지므로

,   ,    이므로

이므로  Rank(A) = 1이다. 따라서 column vector

이 된다.