막 쓰는 선형대수 2 (소거)

모든 자료는 이곳에서 출처를 둠

저번에 작성한 시스템을 row와 column picture로 해석하는 방법을 기억하면서
이번에는 시스템의 해를 구하는 방법들에 대한 내용에 대해서 다룬다.

• 소거법 ( Elimination )
• 후방 대입법 ( Back-substitution )
• 소거 행렬 ( Elimination matrices )
  
  
  
  

소거법

어떠한 선형 시스템에 대한 해(solution)을 구하는 방법으로 소거법이 있다.

$x+2y+z=2$

$3x+8y+z=12$

$4y+z=2$

우리는 위처럼 미지수가 3개고 방정식이 3개 주어지는 경우, 이 방정식 모두를 만족하는 해를 찾기 위해 어느 하나의 식을 기준으로 상수를곱하고 더해주는 방식을 거쳐 미지수를 없애는 방식으로 해를 구하곤 한다.

소거법도 비슷한 방식을 거쳐 미지수들을 제거하는 방식이다.

　　　　　　　　　　　　　　　　　　　　$A$　　　 $x$　 $=　b$

시스템에서 $x+2y+z = 2$라는 식을 기준으로 잡았을 때, 기준식에서 제거하고 싶은 것이 무엇인지, 그에 따른 적절한 상수배를 하고 2번째 식과 더해주는 과정을 거친다.

제거하고 싶은 항이 $3x$이면 기준식에 $-3$을 곱해주어 빼주면 된다.
이 때, 기준식에서의 없애고자 하는 중심축의 원소를 pivot이라고 부른다.

소거법의 방향은 위에서 아래로, 왼쪽에서 오른쪽으로 방향으로 진행된다.
현재 pivot을 기준으로 아래의 모든 원소를 0으로 만들어줘야 하는데 세번째의 x원소는 0이므로 넘어가도 된다.

x에 관한 요소들이 전부 제거 되었으므로 다음 y축으로 넘어간다.
이 때 첫 번째 row와 두번째 column을 pivot으로 잡는다면 x요소들이 0이 아니게 될 것이다.
따라서 두 번째 pivot 값은 두 번째 식의 y축을 기준으로 한다.

$u$

모든 y축의 원소를 제거하고 소거가 완료 된다. 이 때 마지막 row의 z축 원소도 pivot에 속하며
형태가 pivot을 기준으로 아래 쪽 원소들이 모두 0의 값을 갖기 때문에 상삼각행렬(upper triangular matrix)라고 부른다. 이 행렬을 $u$라고 표시한다.

결국 소거법은 $u$를 구하기 위한 일련의 과정이다.


한가지 중요한 것은 상삼각행렬의 pivot 값이 0이 될 수 없다. pivot값이 0이 되면 소거법이 불가능 하다.
pivot값이 0여도 극복이 가능한 경우와 불가능한 경우로 나눠볼 수 있다.

1. 극복이 가능한 경우

두번째 row의 pivot이 되야하는 요소가 0이 되어 소거법이 불가능하다.
이럴 경우 3번째 row의 pivot column값이 0이 아니면 교환하여 소거법을 진행할 수 있다.

2. 극복이 불가능한 경우

마지막 row의 pivot값이 0이 되었는데, 적절하게 교환할 수 있는 row가 없는 경우 극복이 불가능하다.

후방대입법

후방대입법은 마지막 row의 방정식부터 해를 찾아 나가는 것을 말한다.
소거법을 통해 상삼각행렬의 형태를 만들었기 때문에 마지막 row부터 풀어나갈 수 있다.

위의 소거법은 $Ax=b$의 형태에서 소거법을 $A$에만 적용했다.
후방대입법을 적용하기 위해서는정확히는 $b$에도 적용을 하며 소거법을 진행해야 한다.

　　　　　　　　　　　　　　　　　　　　$A$　　　 $x$　 $=　b$

$u　　　　　c$

$b$를 시작으로 소거법을 적용하여 만든 column을 $c$라고 표시한다.
결과적으로 $Ax=b$를 $ux=c$형태로 바꿀 수 있다.

$\begin{bmatrix} 1 & 2 & 1\\ 0 & 2 & -2\\ 0 & 0 & 5 \\ \end{bmatrix} \begin{bmatrix} x\\ y\\ z\\ \end{bmatrix}= \begin{bmatrix} 2\\ 6\\ -10 \end{bmatrix}$

$u　　　　x　　　　 c$

$x+2y+z=2\\2y-2z=6\\5z=-10$

여기서 후방대입법을 적용하면 $u$의 마지막 row부터 z=-2, y=1, x=2라는 해를 구 할 수 있다.

소거행렬

앞서 적용한 소거법의 작업을 행렬의 형태로 표현할 수 있다.
이때 표현되는 행렬을 소거행렬(elimination matrices)라고 하며, 소거행렬과 시스템 A와의 행렬 곱의 과정을 이해해야 한다.

소거행렬을 만들기 전에 matrix와 column의 표현, row와 matrix의 표현을 알고 가자.

$\begin{bmatrix} 1 & 2 & 3\\ 1 & 2 & 3\\ 1 & 2 & 3 \end{bmatrix} \begin{bmatrix} 4\\ 5\\ 6 \end{bmatrix}= 4\begin{bmatrix} 1\\ 1\\ 1 \end{bmatrix}+ 5\begin{bmatrix} 2\\ 2\\ 2 \end{bmatrix}+ 6\begin{bmatrix} 3\\ 3\\ 3 \end{bmatrix}$

$A　　　 x$

matrix * column은 행렬의 column들과 벡터의 원소간의 선형결합으로 나타낼 수 있다.

$\begin{bmatrix} 4 & 5 & 6 \end{bmatrix} \begin{bmatrix} 1 & 1 & 1\\ 2 & 2 & 2\\ 3 & 3 & 3 \end{bmatrix}= 4\begin{bmatrix} 1 & 1 & 1 \end{bmatrix}+ 5\begin{bmatrix} 2 & 2 & 2\\ \end{bmatrix}+ 6\begin{bmatrix} 3 & 3& 3\\ \end{bmatrix}$

$x　　　　A$
row * matrix는 벡터의 원소와 행렬의 row들과의 선형결합으로 나타낼 수 있다.

위의 특징을 기억하며 소거행렬을 만들어 본다.

$\begin{bmatrix} 　　　　\\ \\ \\ \end{bmatrix} \begin{bmatrix} 1 & 2 & 1\\ 3 & 8 & 1\\ 0 & 4 & 1 \end{bmatrix}$

$E_{21}　　　　 A$

$E_{21}$에서 아랫첨자의 숫자는 없애려는 요소가 2행1열의 요소임을 뜻한다.
2행1열의 요소를 없애기 전에 $A$의 첫번 째 row와 세번째 row는 그대로 유지 되어야 한다.
$E_{21}$의 위의 row와 matrix의 표현을 상기하며, 첫번째 row와 $A$의 결과는 [ 1 2 1 ]이 그대로 유지되어야 한다.

$E_{21}$의 첫번째 row값과 $A$만 따로 빼서 본다면

$\begin{bmatrix} a&b&c \end{bmatrix} \begin{bmatrix} 1 & 2&1\\ 3&8&1\\ 0&4&1 \end{bmatrix}= a\begin{bmatrix} 1&2&1 \end{bmatrix}+ b\begin{bmatrix} 3&8&1 \end{bmatrix}+ c\begin{bmatrix} 0&4&1 \end{bmatrix}= \begin{bmatrix} 1&2&1 \end{bmatrix}$

위와 같은 결과가 나와야 한다. 따라서 a=1, b=0, c=0으로 표현할 수 있다.
$E_{21}$의 3번째 로우도 이처럼 [ 0 0 1 ]로 표현할 수 있다.

$\begin{bmatrix} 1&0&0\\ \\ 0&0&1\\ \end{bmatrix} \begin{bmatrix} 1 & 2 & 1\\ 3 & 8 & 1\\ 0 & 4 & 1 \end{bmatrix}$

$E_{21}　　　　 A$

$E_{21}$의 두번째 row는 $A$의 첫번째 row에 -3의 값을 곱하고 더해주는 계산을 한다.
이때, $A$의 3번째 row는 필요 없기 때문에 0으로 처리한다.

$\begin{bmatrix} -3&1&0 \end{bmatrix} \begin{bmatrix} 1 & 2&1\\ 3&8&1\\ 0&4&1 \end{bmatrix}= -3\begin{bmatrix} 1&2&1 \end{bmatrix}+ 1\begin{bmatrix} 3&8&1 \end{bmatrix}+ 0\begin{bmatrix} 0&4&1 \end{bmatrix}= \begin{bmatrix} 0&2&-2 \end{bmatrix}$

$\begin{bmatrix} 1&0&0\\ -3&1&0\\ 0&0&1\\ \end{bmatrix} \begin{bmatrix} 1 & 2 & 1\\ 3 & 8 & 1\\ 0 & 4 & 1 \end{bmatrix}$

$E_{21}　　　　 A$

이런 방식으로 $E_{32}$까지 진행하면

$\begin{bmatrix} 1&0&0\\ 0&1&0\\ 0&-2&1\\ \end{bmatrix} \begin{bmatrix} 1 & 2 & 1\\ 0 & 2 & -2\\ 0 & 4 & 1 \end{bmatrix}= \begin{bmatrix} 1&2&1\\ 0&2&-2\\ 0&0&5\\ \end{bmatrix}$

$E_{32}　　　　 A　　　　　　　u$

최종적으로 $u$행렬이 만들어 진다.
행렬의 곱은 교환법칙은 성립하지 않지만 결합법칙은 성립하기 때문에 아래와 같이 표현할 수 있다.

$E_{32}(E_{21}A)=u\dashrightarrow(E_{32}E_{21})A=u\dashrightarrow EA=u$

• bonus : Permutation Matrix(치환행렬)
  
  

치환행렬은 행이나 열을 바꿔주는 역할을 한다.
단위행렬(Identity Matrix)을 뒤집거나 행이나 열을 바꾼 형태이다.

$P　　A$
row 선형결합의 형태로 표현할 수 있으며 결과적으로 행이 바뀌었다.

$A　　　P$

column 선형결합의 형태로 표현할 수 있으며 결과적으로 열이 바뀌었다.

위의 연산을 보면 같은 행렬을 왼쪽에 붙이냐, 오른쪽에 붙이냐에 따라 결과가 달라진다.
따라서 행렬의 곱에서 교환법칙이 성립하지 않는 것을 알 수 있다.