2. Elimination with Matrices

 

 

 

방정식을 푸는 방법들은 다양합니다.

 

1. Elimination (소거법)

  - Success

  - Failure

 

2. Back-substitution (후방 대입법)

3. Elimination matrices (소거 행렬)

4. Matrix multiplication (행렬 곱)

 

 

여기서 소거법은 모든 소프트웨어 패키지가 방정식을 풀 때 사용하는 방법입니다.

- 소거법이 성공하면 solution을 얻습니다.

- 좋은 matrix에 대해서만 소거법을 진행했을 때 solution을 얻을 수 있습니다. (square matrix가 아닌 것도 solution을 얻을 수 있습니다.)

 

$x+2y+z=2$

$3x+8y+z=12$

$4y+z=2$

 

다음과 같이 3개의 방정식과 3개의 미지수가 있습니다. 이전에 배운 방법을 사용해서 시스템 행렬 (system matirx)를 만들어 봅시다.

 

 

 

Success

 

 

$$\left[\begin{array}{ccc}1& 2& 1\\ 3& 8& 1\\ 0& 4& 1\end{array}\right]$$

 

이 시스템 행렬이 $Ax=b$ 에서의 A입니다.

 

소거법은 방정식에 0이 아닌 상수를 곱한 뒤 다른 방정식과 뺄셈 연산을 진행하면서 solution을 찾게 됩니다.

 

소거된 방정식의 미지수 계수를 피벗(pivot)이라고 합니다. 간단하게 말하면 여기서 1행에 대한 피벗은 1이 됩니다. (x의 계수가 소거됬으니)

 

- 1행에 3을 곱한 뒤 2행에 빼주겠습니다.

 

$$\left[\begin{array}{ccc}1& 2& 1\\ 0& 2& -2\\ 0& 4& 1\end{array}\right]$$

 

 

2행 1열에 0을 얻었으니 다음은 3행 1열과 2열을 0으로 만들어야 합니다. 

 

 

$$\left[\begin{array}{ccc}1& 2& 1\\ 0& 2& -2\\ 0& 0& 5\end{array}\right]$$

 

이렇게 되면 3개의 피벗을 모두 찾았습니다. 작업이 완료된 행렬을 $u$라고 부르겠습니다. 소거법의 목표는 시스템 행렬 $A$를 $u$로 변경시켜주는 것입니다.

 

여기까지가 성공한 케이스고 이제 실패한 케이스에 대해서 알아보겠습니다. 

 

 

 

 

Failure

 

위에 시스템 행렬은 1행, 1열의 숫자가 1이었습니다. 이 값이 0이었다면 피벗이 0이 되어 소거가 불가능합니다.

 

- 피벗 위치에 0이 존재한다면 행들을 교환해야 합니다. 행을 바꿔서도 피벗을 찾을 수 없다면 역행렬이 존재하지 않는 것입니다.

 

$$\left[\begin{array}{ccc}1& 2& 1\\ 0& 2& -2\\ 0& 4& -4\end{array}\right]$$

 

다음과 같은 경우에는 교체할만한 방정식이 없고 이 상태에서 소거법을 진행하면

 

$$\left[\begin{array}{ccc}1& 2& 1\\ 0& 2& -2\\ 0& 0& 0\end{array}\right]$$

 

극복이 불가능한 complete failure가 돼버립니다.

 

- 이 경우 역행렬이 존재하지 않습니다. 위의 두 개의 방정식으로 마지막 방정식을 표현할 수 있어 소거를 진행하면 마지막 방정식이 전부 소거되기 때문입니다.

 

 

 

Back-substitution (역치환)

 

$Ax=b$에서 A만 사용해서 소거를 진행했지만 사실 b까지 고려해서 소거법을 사용해야 합니다. A와 b를 합쳐서 행렬을 만들어 보겠습니다.

 

$$\left[\begin{array}{cccc}1& 2& 1& 2\\ 3& 8& 1& 12\\ 0& 4& 1& 2\end{array}\right]$$

 

column b를 추가로 가져왔습니다. 이것이 Augment matrix (증강행렬)이라고 합니다. 이 상태로 위에서 했던 소거법을 진행하면 됩니다.

•  여기서 b는 extra column이라고 합니다. 이렇게 소거를 진행하면 소거된 b를 얻을 수 있어서 미지수를 구할 수 있습니다.

 

후방 대입법을 이해하기 위해서 b까지 함께 고려한 소거법을 살펴보겠습니다.

 

$$\left[\begin{array}{cccc}1& 2& 1& 2\\ 0& 2& -2& 6\\ 0& 0& 5& -10\end{array}\right]$$

 

$$\left[\begin{array}{ccc}1& 2& 1\\ 0& 2& -2\\ 0& 0& 5\end{array}\right]=u$$

 

$$\left[\begin{array}{c}2\\ 6\\ -10\end{array}\right]=c$$

 

- 소거된 행렬 $A$는 $u$, 소거된 컬럼 벡터 $b$는 $c$로 표기합니다.

 

이것을 방정식으로 다시 정리하면($ux=c$)

 

$x+2y+z=2$ 여기서 $x=2$

 

$2y-2z=6$ 여기서는 $y=1$

 

$5z=-10$ $z=-2$ 라는 것을 알 수가 있습니다.

 

 

 

 

 

Elimination matrices (소거행렬)

 

우리가 소거법을 사용하여 미지수의 값들을 찾았는데 이것을 행렬연산으로 표현해 보겠습니다. $EA=u$ 에서 $E$를 소거행렬이라고 합니다. ($A$행렬에 어떤 행렬을 곱해야 소거된 행렬이 나오는지 찾는 과정)

 

$EA=u$

 

1번째 row와 3번째 row는 변화가 없다.

 

행렬 $A$의 1행을 그대로 가져오고 2행은 1열 원소를 제거된 상태로 만들어줍니다. 우선 2행 1열 성분을 제거하는 소거행렬이기 때문에 A의 3행도 변경없이 가져오면 됩니다.

 

 

1번째 피벗을 찾음

 

그러기 위해서는 행렬 $E$의 2행에서 1번째 원소를 -3을 주고 2번째 원소를 1을 주어서 3을 없애줍니다. 이 행렬을 $E_{21}$라고 부르겠습니다. (1행에 -3을 곱하고 2행과 더해주어 소거되는 과정)

 

이제 다음 단계 $E_{32}$를 구해봅시다. 위와 같은 방법으로 $A_{31},A_{32}$성분을 소거해주기 위한 행렬을 만들어주면 됩니다.

 

 

전체적인 과정을 살펴보면

 

1.  $E_{21}A$ 2행의 1열 원소를 소거해주고
2. $E_{32}(E_{21}A)=u$ 3행의 1, 2열 원소를 소거해줍니다.

$(E_{32}{E}_{21})A=u$ 다음과 같이 행렬 E 두 개를 곱해주면 전체 과정을 한 번에 수행할 수 있는 행렬을 구할 수 있습니다. (선형적이어서 결합법칙이 성립한다.)

 

 

 

 

Permutation (치환행렬)

 

1행과 2행을 교환하는 과정을 행렬 연산으로 표현해보겠습니다.

다음과 같이 치환행렬 P와 A행렬이 존재할 때

 

 

P의 1행에서 A행렬 2행만 가져오고

 

 

P의 2행에서 A행렬의 1행만 가져오면 됩니다.

 

 

$PA$가 아닌 $AP$는 어떻게 될까?

곱셈 순서를 바꿔주면 column을 변경할 수 있습니다.

- 어떤 순서로 곱하냐 따라서 행, 열이 바뀝니다. 즉 곱셈 순서에 따라서 연산의 의미가 바뀝니다. (교환법칙이 성립되지 않는다.)

 

 

 

 

Inverse matrix (역행렬)

 

소거를 통해서 A행렬을 u행렬로 바꿔줬는데 이제 다시 u행렬을 A행렬로 변경해보겠습니다.

 

$E$ 행렬에 어떠한 행렬을 곱해서 항등행렬(indentity matrix)로 만들어줄 수 있다면 변환을 다시 되돌릴 수 있습니다. (이 어떠한 행렬을 $E^{-1}$이라고 하겠습니다.)

• $EA=u$
• $(E^{-1}E)A=E^{-1}u$
• $IA=A$

 

- 행렬 $E$ 1, 3 행은 유지하고 2행만 변경해주면 될 거 같습니다.

 

 

$E^{-1}$ 2행 부분을 $E$의 1행에 3을 곱하고 2행과 더해주게 만들어주면 됩니다.  

• 간단하게 생각하면 이전 연산에서 1행을 가져와서 3번 빼줬으니 그 역으로 3번 더해주면 되는 것입니다.

 

 

 

 

요약

 

- 연립일차방정식을 시스템 행렬로 만들고 나서 소거법을 사용하면 해를 구할 수 있다. 소거법을 통해서 소거가 완료된 행렬은 상삼각행렬이 된다. (피벗을 찾아주는 과정으로 인해서)

 

- 소거법은 연립해서 방정식을 푸는 과정을 행렬 연산으로 표현한 것인데 이때 소거행렬의 역행렬을 통해서 쉽게 원래 행렬을 찾을 수 있다.

 

- 치환행렬은 행을 교환하게 해주어 피벗을 찾는 과정을 도와줄 수 있고 곱하는 순서를 바꿔주게 되면 행이 아닌 열을 교환해준다.

 

- 소거된 행렬에서 원소가 모두 0인 행 벡터가 존재한다면 complete failure가 되고 선형종속을 의미하기 때문에 역행렬이 존재하지 않는다. (행을 교환해도 소거를 진행할 수 없어도 complete failure이다.)

 

- 소거법을 진행할 때 $Ax=b$에서 b벡터까지 고려해서 진행해야한다. (증강행렬로 만들어서 진행)