[선형대수학] 연립방정식과 Echelon Form 문제풀이

Systems in Triangular and Echelon Form

 

1. Determine the pivot and free variables in each of the following systems:

(a)

$$ \begin{split} 2x _ {1} -3x _ {2} -6  x _ {3} -5  x _ {4} +2  x _ {5} =  7 \\  x _ {3} +3 x _ {4} -7  x _ {5} =  6\\ x _ {4} -2  x _ {5} =  1 \end{split}$$

(b)

$$ \begin{split} 2x-6y +7z=1\\4y+3z=8\\ -2z=4 \end{split}$$

(c)

$$ \begin{split} &x+2y-3&z&=2\\2&x+3y+&z&=4\\3&x+4y+5&z&=8\end{split}$$

 

(sol)

(a) In echelon form, the leading unknowns are the pivot variables, and the others are the free variables. Here $ x _ {1} ,~x _ {3} ,~x _ {4} $ are the pivot variables, and $ x _ {2} $ and $ x _ {5} $ are the free variables.

(b) The leading unknowns are $ x,~y,~z $, so they are the pivot variables. There are no free variables (as in any triangular system).

(c) The notion of pivot and free variables applies only to a system in echelon form.

 

2. Solve each of the following systems:

(a) $\begin{split} &x+2&y-4&z&=-&4\\2&x+5&y-9&z&=-&10\\3&x-2&y+3&z&=&11\end{split} $

(b) $\begin{split}&x+2&y-3&z=-&1\\-3&x+&y-2&z=-&7\\5&x+3&y-4&z=&2\end{split} $

(c) $\begin{split}&x+2&y-3&z=&1 \\2&x+5&y-8&z=&4\\3&x+8&y-13&z=&7 \end{split}$

 

sol) (a) $ ( 2,~-1,~1) $ (b) no solution (c) $ x=-3-t,~y=2+2t $, $ z=t $

 

3. Solve using the condensed format:

$ \begin{split} &2y&+3&z=3\\ x+&5y&+&z=4\\ 4x+&8y&-3&z=35 \end{split} $

 

sol) $ ( 2,~3,~-1) $

 

4. Consider the system

$$\begin{split} x+2&y&+&z=3\\a&y&+5&z=10\\2x+7&y&+a&z=b \end{split}$$

(a) Find those values of $ a $ for which the system has a unique solution.

(b) Find those pairs of values $ ( a,~b) $ for which the system has more than one solution.

 

sol) Reduce the system to echelon form. That is, eliminate $ x $ from the third equation by the operation "Replace $ L _ {3} $ by $ -2L _ {1} +L _ {3} $" and then eliminate $ y $ from the third equation by the operation "Replace $ L _ {3} $ by $ -3L _ {2} +aL _ {3} $ " This yields

$$ \begin{split}x+2&y+&z&=3\\ a&y+5&z&=10\\ 3&y+( a-2)&z&=b-6 \end{split}$$

and then

$$\begin{split} x+2y+&z=3\\ ay+5&z=10\\ (a^{2}-2a-15)&z=b-6 \end{split} $$

Examine the last equation $ ( a ^ {2} -2a-15)z=ab-6a-30 $.

(a) The system has a unique solution if and only if the coefficient of z is not zero; that is, if

$ a ^ {2} -2a-15= ( a-5) ( a+3) \neq 0 $ or $ a \neq 5 $ and $ a \neq -3 $

(b) The system has more than one solution if both sides are zero. The left-hand side is zero when $ a=5 $ or $ a=-3 $. When $ a=5 $, the right-hand side is zero when $ 5b-60=0 $, or $ b=12 $. When $ a=-3 $, the righthand side is zero when $ -3b-12=0 $ or $ b=-4 $. Thus, $ ( 5,~12) $ and $ \left ( -3,~-4 \right ) $ are the pairs for which the system has more than one solution.

 

5. Reduce each of the following matrices to row canonical form(reduced echelon form):

(a) $ A= \left[ \matrix {2 & 2 & -1 & 6 & 4\\4 & 4 & 1 & 10 & 13\\8 & 8 & -1 & 26 & 23} \right] $ (b) $ B= \left[ \matrix {5 & -9 & 6\\0 & 2 & 3\\0 & 0 & 7} \right] $

sol) (a)

$ A \sim  \left[ \matrix {1 & 1 & 0 & 0 & \frac {3} {2} \\0 & 0 & 1 & 0 & 2\\0 & 0 & 0 & 1 & \frac {1} {2} } \right] $

(b)

$ B \sim  \left[ \matrix {1 & 0 & 0\\0 & 1 & 0\\0 & 0 & 1} \right] $

 

 

Elementary Matrices, Applications

 

6. Let $ e _ {1} ,~e _ {2} ,~e _ {3} $ denote, respectively, the elementary row operations

"Interchange rows $ R _ {1} $ and $ R _ {2} $" "Replace $ R _ {3} $ by $ 7R _ {3} $" "Replace $ R _ {2} $ by $ -3R _ {1} +R _ {2} $"

sol) Find the corresponding three-square elementary matrices $ E _ {1} ,~E _ {2} ,~E _ {3} $. Apply each operation to the $ 3 \times 3 $ identity matrix $ I _ {3} $ to obtain

$ E _ {1} = \left[ \matrix {0 & 1 & 0\\1 & 0 & 0\\0 & 0 & 1} \right] $, $ E _ {2} = \left[ \matrix {1 & 0 & 0\\0 & 1 & 0\\0 & 0 & 7} \right] $, $ E _ {3} = \left[ \matrix {1 & 0 & 0\\-3 & 1 & 0\\0 & 0 & 7} \right] $

 

7. Write each of the following matrices as a product of elementary matrices:

(a) $ A= \left[ \matrix {1 & -3\\-2 & 4} \right] $ (b) $ B= \left[ \matrix {1 & 2 & 3\\0 & 1 & 4\\0 & 0 & 1} \right] $ (c) $ C= \left[ \matrix {1 & 1 & 2\\2 & 3 & 8\\-3 & -1 & 2} \right] $

The following three steps write a matrix $ M $ as a product of elementary matrices:

Step 1. Row reduce $ M $ to the identity matrix $ I $, keeping track of the elementary row operations.

Step 2. Write down the inverse row operations.

Step 3. Write $ M $ as the product of the elementary matrices corresponding to the inverse operations. This gives the desired result.

If a zero row appears in Step 1, then $ M $ is not row equivalent to the identity matrix $ I $ , and M cannot be written as a product of elementary matrices.

(a) (1) We have

$$ A= \left[ \matrix {1 & -3\\-2 & 4} \right]  \sim \left[ \matrix {1 & -3\\0 & -2} \right]  \sim  \left[ \matrix {1 & -3\\0 & 1} \right]   \sim \left[ \matrix {1 & 0\\0 & 1} \right] =I $$

where the row operations are, respectively,

"Replace $ R _ {2} $ by $ 2R _ {1} +R _ {2} $" "Replace $ R _ {2} $ by $ - \frac {1} {2} R _ {2} $" "Replace $ R _ {1} $ by $ 3R _ {2} +R _ {1} $"

(2) Inverse operations:

"Replace $ R _ {2} $ by $ -2R _ {1} +R _ {2} $" "Replace $ R _ {2} $ by $ -2R _ {2} $" "Replace $ R _ {1} $ by $ -3R _ {2} +R _ {1} $"

(3) $ A= \left[ \matrix {1 & 0\\-2 & 1} \right] \left[ \matrix {1 & 0\\0 & -2} \right] \left[ \matrix {1 & -3\\0 & 1} \right] $

(b) (1) We have

$$ B= \left[ \matrix {1 & 2 & 3\\0 & 1 & 4\\0 & 0 & 1} \right]   \sim \left[ \matrix {1 & 2 & 0\\0 & 1 & 0\\0 & 0 & 1} \right]   \sim \left[ \matrix {1 & 0 & 0\\0 & 1 & 0\\0 & 0 & 1} \right] =I $$

where the row operations are, respectively,

"Replace $ R _ {2} $ by $ -4R _ {3} +R _ {2} $" "Replace $ R _ {1} $ by $ -3R _ {3} +R _ {1} $" "Replace $ R _ {1} $ by $ -2R _ {2} +R _ {1} $"

(2) Inverse operations:

"Replace $ R _ {2} $ by $ 4R _ {3} +R _ {2} $" "Replace $ R _ {2} $ by $ 3R _ {3} +R _ {1} $" "Replace $ R _ {1} $ by $ 2R _ {2} +R _ {1} $"

(3) $ B= \left[ \matrix {1 & 0 & 0\\0 & 1 & 4\\0 & 0 & 1} \right] \left[ \matrix {1 & 0 & 3\\0 & 1 & 0\\0 & 0 & 1} \right] \left[ \matrix {1 & 2 & 0\\0 & 1 & 0\\0 & 0 & 1} \right] $

(c) (1) First row reduce C to echelon form. We have

$ C= \left[ \matrix {1 & 1 & 2\\2 & 3 & 8\\-3 & -1 & 2} \right] $$ \sim \left[ \matrix {1 & 1 & 2\\0 & 1 & 4\\0 & 2 & 8} \right] $$ \sim \left[ \matrix {1 & 1 & 2\\0 & 1 & 4\\0 & 0 & 0} \right] $

In echelon form, C has a zero row. ‘“STOP” The matrix $ C $ cannot be row reduced to the identity matrix $ I $, and $ C $ cannot be written as a product of elementary matrices. (We note, in particular, that $ C $ has no inverse.)

 

8. Find the inverse of (a) $ A= \left[ \matrix {1 & 2 & -4\\-1 & -1 & 5\\2 & 7 & -3} \right] $

(b) $ B= \left[ \matrix {1 & 3 & -4\\1 & 5 & -1\\3 & 13 & -6} \right] $

(a) Form the matrix $ M=[A,I] $ and row reduce $ M $ to echelon form:

$ M= \left[ \matrix {1 & 2 & -4 & 1 & 0 & 0\\-1 & -1 & 5 & 0 & 1 & 0\\2 & 7 & -3 & 0 & 0 & 1} \right] $$ \sim  \left[ \matrix {1 & 2 & -4 & 1 & 0 & 0\\0 & 1 & 1 & 1 & 1 & 0\\0 & 3 & 5 & -2 & 0 & 1} \right] $$ \sim \left[ \matrix {1 & 2 & -4 & 1 & 0 & 0\\0 & 1 & 1 & 1 & 1 & 0\\0 & 0 & 2 & -5 & -3 & 1} \right] $

In echelon form, the left half of M is in triangular form; hence, A has an inverse. Further reduce M to row canonical form:

$$ M\sim \left[ \matrix {1 & 2 & 0 & -9 & -6 & 2\\0 & 1 & 0 & \frac {7} {2} & \frac {5} {2} & - \frac {1} {2} \\0 & 0 & 1 & - \frac {5} {2} & - \frac {3} {2} & \frac {1} {2} } \right]  \sim \left[ \matrix {1 & 0 & 0 & -16 & -11 & 3\\0 & 1 & 0 & \frac {7} {2} & \frac {5} {2} & - \frac {1} {2} \\0 & 0 & 1 & - \frac {5} {2} & - \frac {3} {2} & \frac {1} {2} } \right] $$

The final matrix has the form $ [I,~A ^ {-1} ] $; that is, $ A ^ {-1} $ is the right half of the last matrix. Thus,

$$ A ^ {-1} = \left[ \matrix {-16 & -11 & 3\\ \frac {7} {2} & \frac {5} {2} & - \frac {1} {2} \\- \frac {5} {2} & - \frac {3} {2} & \frac {1} {2} } \right] $$

(b) Form the matrix $ M=[B,~I] $ and row reduce $ M $ to echelon form:

$$ M= \left[ \matrix {1 & 3 & -4 & 1 & 0 & 0\\1 & 5 & -1 & 0 & 1 & 0\\3 & 13 & -6 & 0 & 0 & 1} \right] \sim \left[ \matrix {1 & 3 & -4 & 1 & 0 & 0\\0 & 2 & 3 & -1 & 1 & 0\\0 & 4 & 6 & -3 & 0 & 1} \right] \sim \left[ \matrix {1 & 3 & -4 & 1 & 0 & 0\\0 & 2 & 3 & -1 & 1 & 0\\0 & 0 & 0 & -1 & -2 & 1} \right] $$

In echelon form, M has a zero row in its left half; that is, B is not row reducible to triangular form. Accordingly, B has no inverse.

 

9. Prove Theorem 3.17: Let $ A $ be a square matrix. Then the following are equivalent:

(a) $ A $ is invertible (nonsingular).

(b) $ A $ is row equivalent to the identity matrix $ I $.

(c) $ A $ is a product of elementary matrices.

pf)

Suppose $ A $ is invertible and suppose $ A $ is row equivalent to matrix $ B $ in row canonical form. Then there exist elementary matrices $ E _ {1} ,~E _ {2} ,~ \cdots ,~E _ {s} $ such that $ E _ {s} \cdots E _ {2} E _ {1} A=B $. Because $ A $ is invertible and each elementary matrix is invertible, $ B $ is also invertible. But if $ B \neq I $, then $ B $ has a zero row; whence $ B $ is not invertible. Thus, $ B=I $, and (a) implies (b).

If (b) holds, then there exist elementary matrices $ E _ {1} ,~E _ {2} ,~ \cdots ,~E _ {s} $ such that $ E _ {s} \cdots E _ {2} E _ {1} A=I $. Hence, $ A ^ {-1} = ( E _ {s} \cdots E _ {2} E _ {1} ) ^ {-1} =E _ {1} ^ {-1} E _ {2} ^ {-1} \cdots E _ {s} ^ {-1} $. But the $ E _ {i} ^ {-1} $are also elementary matrices. Thus (b) implies (c).

If (c) holds, then $ A=E _ {1} E _ {2} \cdots E _ {s} $. The $ E _ {i} $ are invertible matrices; hence, their product A is also invertible. Thus, (c) implies (a). Accordingly, the theorem is proved.

 

10. Prove Theorem 3.18: If $ AB=I $, then $ BA=I $, and hence $ B=A ^ {-1} $.

pf)

Suppose $ A $ is not invertible. Then $ A $ is not row equivalent to the identity matrix $ I $, and so A is row equivalent to a matrix with a zero row. In other words, there exist elementary matrices $ E _ {1} ,~E _ {2} ,~ \cdots ,~E _ {s} $ such that $ E _ {s} \cdots E _ {2} E _ {1} A $ has a zero row. Hence, $ E _ {s} \cdots E _ {2} E _ {1} AB=E _ {s} \cdots E _ {2} E _ {1} $, an invertible matrix, also has a zero row. But invertible matrices cannot have zero rows; hence $ A $ is invertible, with inverse $ A ^ {-1} $. Then also,

$ B=IB= ( A ^ {-1} A)B=A ^ {-1} ( AB)=A ^ {-1} I=A ^ {-1} $

 

11. Prove Theorem 3.19: B is row equivalent to A (written $ B \sim A $) if and only if there exists a nonsingular matrix $ P $ such that $ B=PA $.

pf)

If $ B \sim A $, then $ B=e _ {s} \left ( \cdots \left ( e _ {2} \left ( e _ {1} \left ( A \right ) \right ) \right ) \right ) =E _ {s} \cdots E _ {2} E _ {1} A=PA $ where $ P=E _ {s} \cdots E _ {2} E _ {1} $ is nonsingular.

Conversely, suppose $ B=PA $, where $ P $ is nonsingular. $ P $ is a product of elementary matrices, and so $ B $ can be obtained from $ A $ by a sequence of elementary row operations; that is, $ B SIM A $. Thus, the theorem is proved.

 

Lu Factorization

행렬 $ A $를 두 개의 삼각 행렬(triangular matrices)의 곱으로 표현하는 방법을 알아보자. 다음의 $ 3 \times 3 $ 행렬 $ A $를 가우스 소거(Gauss elimination)법을 적용하자.

$ A= \left[ \matrix {2 & 4 & -2\\4 & 9 & -3\\-2 & -3 & 7} \right] $

$ R _ {2} $를 $ -2R _ {1} +R _ {2} $로 바꾸면

$ \left[ \matrix {2 & 4 & -2\\0 & 1 & 1\\-2 & -3 & 7} \right] $

$ R _ {3} $를 $ R _ {1} +R _ {3} $로 바꾸면

$ \left[ \matrix {2 & 4 & -2\\0 & 1 & 1\\0 & 1 & 5} \right] $

$ R _ {3} $를 $ -R _ {2} +R _ {3} $로 바꾸면

$ \left[ \matrix {2 & 4 & -2\\0 & 1 & 1\\0 & 0 & 4} \right] =U $

위 행렬은 선행 성분(leading component)을 $ 1 $로 만들어주지 않은 행 사다리꼴(row-echelon form)로 상삼각행렬(upper triangular matrix)이다. 지금까지 한 기본행연산을 기본행렬(elementary matrices)로 나타내면 다음과 같습니다.

$ E _ {1} = \left[ \matrix {1 & 0 & 0\\-2 & 1 & 0\\0 & 0 & 1} \right] $, $ E _ {2} = \left[ \matrix {1 & 0 & 0\\0 & 1 & 0\\1 & 0 & 1} \right] $, $ E _ {3} = \left[ \matrix {1 & 0 & 0\\0 & 1 & 0\\0 & -1 & 1} \right] $

$ E _ {3} E _ {2} E _ {1} A=U $

기본행렬은 각각 가역행렬이므로

$ A=E _ {1} ^ {1-1} E _ {2} ^ {1-1} E _ {3} ^ {-1} U $

$ E _ {1} ^ {-1} = \left[ \matrix {1 & 0 & 0\\2 & 1 & 0\\0 & 0 & 1} \right] $, $ E _ {2} ^ {-1} = \left[ \matrix {1 & 0 & 0\\0 & 1 & 0\\-1 & 0 & 1} \right] $, $ E _ {3} ^ {-1} = \left[ \matrix {1 & 0 & 0\\0 & 1 & 0\\0 & 1 & 1} \right] $

 

기본행렬 $ E _ {i} $와 기본행렬의 역행렬 $ E _ {i} ^ {-1} $ 모두 대각 성분이 $ 1 $인 하삼각행렬(lower triangular matrices)이다. 대각 성분이 모두 $ 1 $인 하삼각행렬끼리의 곱의 결과는 똑같이 대각 성분이 모두 $ 1 $인 하삼각행렬이 된다.

$ E _ {1} ^ {-1} E _ {2} ^ {-1} E _ {3} ^ {-1} = \left[ \matrix {1 & 0 & 0\\2 & 1 & 0\\0 & 0 & 1} \right] \left[ \matrix {1 & 0 & 0\\0 & 1 & 0\\-1 & 0 & 1} \right] \left[ \matrix {1 & 0 & 0\\0 & 1 & 0\\0 & 1 & 1} \right] $$ = \left[ \matrix {1 & 0 & 0\\2 & 1 & 0\\-1 & 1 & 1} \right] =L $

(참고) $ E _ {3} E _ {2} E _ {1} $의 역행렬을 구하기 위해 먼저

$ E _ {3} E _ {2} E _ {1} = \left[ \matrix {1 & 0 & 0\\-2 & 1 & 0\\1 & -1 & 1} \right] $

곱하지 말고 위의 각각의 성분에 대입하면 된다. ($ -2,~1,~-1 $에 대해 각각 $ 2 $행 $ 1 $열에 $ -2 $를, $ 3 $행 $ 1 $열에 $ 1 $을, $ 3 $행$ 2 $열에 $ -1 $을 대입하면 된다.)

또, $ E _ {3} E _ {2} E _ {1} $의 역행렬은 $ -2,~1,~-1 $의 부호를 바꾸어 위에서 하던 방식으로 넣으면 된다.

 

따라서 다음과 같이 쓸 수 있습니다

$ A=LU $

 

확인해보자.

$ LU= \left[ \matrix {1 & 0 & 0\\2 & 1 & 0\\-1 & 1 & 1} \right] \left[ \matrix {2 & 4 & -2\\0 & 1 & 1\\0 & 0 & 4} \right] = \left[ \matrix {2 & 4 & -2\\4 & 9 & -3\\-2 & -3 & 7} \right] =A $

 

행렬을 하삼각행렬(대각 성분이 모두 $ 1 $)과 상삼각행렬의 곱으로 나타내는 것을 LU 분해(LU factorization or LU decomposition)라고 한다. LU 분해는 소거 과정에서 행교환이 필요 없는 경우 항상 가능하다.

 

Note : 일반적으로 LU 분해는 소거 과정에서 행교환이 필요한 경우 가능하지 않다. 여기서 말하는 기본행렬은 소거 행렬(elimination matrix)로 행을 교환하는 순열 행렬(permutation matrix)은 취급하지 않는다. 순열 행렬은 하삼각행렬이 아니므로 순열 행렬이 끼어들어가면 기본행렬의 곱이 하삼각행렬이 되지 않기 때문이다. 따라서 지금은 일단 행교환이 필요 없는 경우만 생각하자.

 

LU 분해를 사용하여 연립 일차방정식의 해를 구해 보자.

$ A \overrightarrow {x} = \overrightarrow {b} $

$ A=LU $라 하면 $ LU \overrightarrow {x} = \overrightarrow {b} $이고 여기서 $ U \overrightarrow {x} = \overrightarrow {y} $로 치환하면

$ L \overrightarrow {y} = \overrightarrow {b} $

다음 두 step를 이용해 해를 구하자.

Step 1. $ L \overrightarrow {y} = \overrightarrow {b} $에서 $ \overrightarrow {y} $를 구한다.

Step 2. $ U \overrightarrow {x} = \overrightarrow {y} $에서 $ \overrightarrow {x} $를 구한다.

 

위의 행렬 $ A $로 만들어진 다음 연립방정식의 해를 $ LU $분해를 이용해서 구하자.

$ A \overrightarrow {x} = \left[ \matrix {2 & 4 & -2\\4 & 9 & -3\\-2 & -3 & 7} \right] \left[ \matrix {x _ {1} \\x _ {2} \\x _ {3} } \right] = \left[ \matrix {2\\8\\10} \right] = \overrightarrow {b} $

$ LU $분해하여 적으면

$ \left[ \matrix {1 & 0 & 0\\2 & 1 & 0\\-1 & 1 & 1} \right] \left[ \matrix {2 & 4 & -2\\0 & 1 & 1\\0 & 0 & 4} \right] \left[ \matrix {x _ {1} \\x _ {2} \\x _ {3} } \right] = \left[ \matrix {2\\8\\10} \right] $

 

Step 1.

$ L \overrightarrow {y} = \overrightarrow {b} $

$ \left[ \matrix {1 & 0 & 0\\2 & 1 & 0\\-1 & 1 & 1} \right] \left[ \matrix {y _ {1} \\y _ {2} \\y _ {3} } \right] = \left[ \matrix {2\\8\\10} \right] $ $\Leftrightarrow$ $\begin{cases} &~y_1 &&&=2\\&2y_1 +&y_2 &&=8\\&-y_1 +&y_2 +&y_3 &=10 \end{cases}$

$ \because $$ \overrightarrow {y} = \left ( 2,~4,~8 \right ) $

* $ \left[ \matrix {1 & 0 & 0\\2 & 1 & 0\\-1 & 1 & 1} \right] ^ {-1} = \left[ \matrix {1 & 0 & 0\\-2 & 1 & 0\\1 & -1 & 1} \right] $이므로

$ \left[ \matrix {y _ {1} \\y _ {2} \\y _ {3} } \right] = \left[ \matrix {1 & 0 & 0\\2 & 1 & 0\\-1 & 1 & 1} \right] ^ {-1} \left[ \matrix {2\\8\\10} \right] $

$ = \left[ \matrix {1 & 0 & 0\\-2 & 1 & 0\\1 & -1 & 1} \right] \left[ \matrix {2\\8\\10} \right] = \left[ \matrix {2\\4\\4} \right] $

를 이용하여 풀 수도 있다.

 

Step 2

$ U \overrightarrow {x} = \overrightarrow {y} $

$ \left[ \matrix {2 & 4 & -2\\0 & 1 & 1\\0 & 0 & 4} \right] \left[ \matrix {x _ {1} \\x _ {2} \\x _ {3} } \right] = \left[ \matrix {2\\8\\10} \right] $ $ \Leftrightarrow $ $  \begin {cases} 2 & x _ {1} +4 & x _ {2} -2 & x _ {3} & = & 2\\ & & x _ {2} + & x _ {3} & = & 8\\ & & ~~~~4 & x _ {3} & = & 10\end {cases}  $

$ \because $$ \overrightarrow {x} = \left ( -1,~2,~2 \right ) $

 

Example 1

$ LU $ 분해를 이용하여 다음의 연립 일차방정식의 해를 구하여라.

$ A \overrightarrow {x} = \left[ \matrix {2 & 1 & 1 & 0\\4 & 1 & 0 & 1\\-2 & 2 & 1 & 1} \right] \left[ \matrix {x _ {1} \\x _ {2} \\x _ {3} \\x _ {4} } \right] = \left[ \matrix {1\\-2\\7} \right] = \overrightarrow {b} $

$ A $를 위삼각행렬로 만들기 위해 필요한 기본행렬은 다음과 같다. (바로 알기 어려우면 직접 가우스 소거를 하여 찾자.)

$ R _ {2} $를 $ -2R _ {1} +R _ {2} $로 바꾸면

$ \left[ \matrix {2 & 1 & 1 & 0\\0 & -1 & -2 & 1\\-2 & 2 & 1 & 1} \right] $

$ R _ {3} $를 $ R _ {1} +R _ {3} $로 바꾸면

$ \left[ \matrix {2 & 1 & 1 & 0\\0 & -1 & -2 & 1\\0 & 3 & 2 & 1} \right] $

$ R _ {3} $를 $ 3R _ {2} +R _ {3} $로 바꾸면

$ \left[ \matrix {2 & 1 & 1 & 0\\0 & -1 & -2 & 1\\0 & 0 & -4 & 4} \right] =U $

기본행렬은 $ E _ {1} = \left[ \matrix {1 & 0 & 0\\-2 & 1 & 0\\0 & 0 & 1} \right] $, $ E _ {2} = \left[ \matrix {1 & 0 & 0\\0 & 1 & 0\\1 & 0 & 1} \right] $, $ E _ {3} = \left[ \matrix {1 & 0 & 0\\0 & 1 & 0\\0 & 3 & 1} \right] $

$ E _ {3} E _ {2} E _ {1} = \left[ \matrix {1 & 0 & 0\\-2 & 1 & 0\\1 & 3 & 1} \right] $

따라서 $ U= ( E _ {3} E _ {2} E _ {1} ) ^ {-1} = \left[ \matrix {1 & 0 & 0\\2 & 1 & 0\\-1 & -3 & 1} \right] $

 

$ LU $분해하여 적으면

$ \left[ \matrix {1 & 0 & 0\\2 & 1 & 0\\-1 & -3 & 1} \right] \left[ \matrix {2 & 1 & 1 & 0\\0 & -1 & -2 & 1\\0 & 0 & -4 & 4} \right] \left[ \matrix {x _ {1} \\x _ {2} \\x _ {3} \\x _ {4} } \right] = \left[ \matrix {1\\-2\\7} \right] = \overrightarrow {b} $

Step 1.

$ L \overrightarrow {y} = \overrightarrow {b} $

$ \left[ \matrix {1 & 0 & 0\\2 & 1 & 0\\-1 & -3 & 1} \right] \left[ \matrix {y _ {1} \\y _ {2} \\y _ {3} } \right] = \left[ \matrix {1\\-2\\7} \right] $ $ \Leftrightarrow $ $ \left\{ \begin {split}  &y_{1}& &&=&1\\2&y_{1}&+y_{2}& &=-&2\\-&y_{1}&-3y_{2}&+y_{3}&=&7\end {split}  \right . $

$ \because $$ \overrightarrow {y} = \left ( 1,~-4,~-4 \right ) $

 

Step 2

$ U \overrightarrow {x} = \overrightarrow {y} $

$ \left[ \matrix {2 & 1 & 1 & 0\\0 & -1 & -2 & 1\\0 & 0 & -4 & 4} \right] \left[ \matrix {x _ {1} \\x _ {2} \\x _ {3} \\x _ {4} } \right] = \left[ \matrix {1\\-4\\-4} \right] $ $\Leftrightarrow $ $ \left \{ \begin {split} 2x _ {1} &+  x _ {2} &+  x _ {3}   &&=  1 \\ &- x _ {2} &-2  x _ {3} &+  x _ {4}  &=  -4  \\ &&-4  x _ {3} &+4 x _ {4}  &= -4  \end {split} \right. $

역대입(back substitution)하여 해를 구하면

$ x _ {4} =t $

$ x _ {3} =t+1 $

$ x _ {2} =2-t $

$ x _ {1} =-1 $

$ \therefore $ $ \left[ \matrix {x _ {1} \\x _ {2} \\x _ {3} \\x _ {4} } \right] = \left[ \matrix {-1\\2\\1\\0} \right] +t \left[ \matrix {0\\-1\\1\\1} \right] $

 

$ LU $ 분해를 이용한 연립 일차방정식 풀이의 장점은 $ L $과 $ U $가 삼각행렬이기 때문에 해를 구하기가 쉽다는 점입니다. 그러나 $ LU $분해가 가우스 소거법만큼 복잡하다. 그런데 $ LU $분해가 유용할 때는 다음과 같이 계수들이 같고($ A $가 같음) $ b $가 다른 여려개의 system을 풀 때이다.

$ A \overrightarrow {x _ {i} } = \overrightarrow {b _ {i} } $ ($ i=1,2, \cdots ,n $)

가우스 소거법으로 풀려면 $ \overrightarrow {b _ {i} } $가 바뀔 때마다 가우스 소거를 해야 하는 번거로움이 있습니다. $ n $가 클 때는 $ A $를 $ LU $분해한 후 $ Ly _ {i} =b _ {i} $를 풀고 $ Ux_i =y_ i $를 푸는게 간단하다.

 

12. Find the LU factorization of (a) $ A= \left[ \matrix {1 & -3 & 5\\2 & -4 & 7\\-1 & -2 & 1} \right] $, (b) $ B= \left[ \matrix {1 & 4 & -3\\2 & 8 & 1\\-5 & -9 & 7} \right] $

(a) Reduce $ A $ to triangular form by the following operations:

"Replace $ R _ {2} $ by $ -2R _ {1} +R _ {2} $" "Replace $ R_3 $ by $ R_1 + R_3 $" and then "Replace $ R_3 $ by $ 5over 2 R_2 + R_3 $"

These operations yield the following, where the triangular form is $ U $:

$ A \sim \left[ \matrix {1 & -3 & 5\\0 & 2 & -3\\0 & 0 & - \frac {3} {2} } \right] $$ \sim  \left[ \matrix {1 & -3 & 5\\0 & 2 & -3\\0 & 0 & - \frac {3} {2} } \right] =U $ and $ L= \left[ \matrix {1 & 0 & 0\\2 & 1 & 0\\-1 & - \frac {5} {2} & 1} \right] $

The entries $ 2,~-1,~- \frac {5} {2} $ in $ L $ are the negatives of the multipliers $ -2,~1,~ \frac {5} {2} $ in the above row operations. (As a check, multiply $ L $ and $ U $ to verify $ A=LU $.)

 

(b) Reduce $ B $ to triangular form by first applying the operations "Replace $ R_2 $ by $ -2R_1 + R_2 $" and "Replace $ R_3 $ by $ 5R_1 + R_3 $" These operations yield

$$ B \sim  \left[ \matrix {1 & 4 & -3\\0 & 0 & 7\\0 & 11 & -8} \right] $$

Observe that the second diagonal entry is 0. Thus, B cannot be brought into triangular form without row interchange operations. Accordingly, $ B $ is not $ LU $-factorable. (There does exist a PLU factorization of such a matrix $ B $, where $ P $ is a permutation matrix, but such a factorization lies beyond the scope of this text.)

 

13. Find the LU factorization of the matrix $ A= \left[ \matrix {1 & 2 & 1\\2 & 3 & 3\\-3 & -10 & 2} \right] $.

Reduce A to triangular form by the following operations:

(1) "Replace $ R _ {2} $ by $ -2R _ {1} +R _ {2} $" (2) "Replace $ R_3 $ by $ 3R _ {1} +R _ {3} $" (3) "Replace $ R_3 $ by $ -4R _ {2} +R _ {3} $"

These operations yield the following, where the triangular form is $ U $:

$ A \sim  \left[ \matrix {1 & 2 & 1\\0 & -1 & 1\\0 & -4 & 5} \right] $$ \sim \left[ \matrix {1 & 2 & 1\\0 & -1 & 1\\0 & 0 & 1} \right] =U $ and $ L= \left[ \matrix {1 & 0 & 0\\2 & 1 & 0\\-3 & 4 & 1} \right] $

The entries $ 2,~-3,~4 $ in $ L $ are the negatives of the multipliers $ -2,~3,~-4 $ in the above row operations. (As a check, multiply $ L $ and $ U $ to verify $ A=LU $.)