2.2 The Idea of Elimination

가우스 소거법

가우스 소거법은 선형 방정식계 Ax=bAx=b를 위삼각행렬 형태의 Ux=cUx=c로 바꾼 뒤, 역대입(back substitution)으로 해를 구하는 방법이다.

핵심 흐름은 다음과 같다.

  1. 아래쪽 항들을 차례로 소거한다.
  2. 행렬을 위삼각행렬로 만든다.
  3. 마지막 방정식부터 거꾸로 대입해 해를 구한다.

즉, 다음 형태를 만드는 것이 목표이다.

Ax=b⟶Ux=cAx=b \quad \longrightarrow \quad Ux=c

간단한 예시: 미지수 2개

다음 연립방정식을 보자.

x−2y=13x+2y=11\begin{align} x - 2y &= 1 \\ 3x + 2y &= 11 \end{align}

이를 행렬 방정식으로 쓰면 다음과 같다.

[1−232][xy]=[111]\begin{bmatrix} 1 & -2 \\ 3 & 2 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 1 \\ 11 \end{bmatrix}

가우스 소거법의 목표는 첫 번째 열의 아래쪽 원소 33을 0으로 만드는 것이다.

즉, 다음 형태로 바꾼다.

x−2y=18y=8\begin{align} x - 2y &= 1 \\ 8y &= 8 \end{align}

행렬로 쓰면 다음과 같다.

[1−208][xy]=[18]\begin{bmatrix} 1 & -2 \\ 0 & 8 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 1 \\ 8 \end{bmatrix}

이제 두 번째 식에서 바로 y=1y=1을 얻고, 첫 번째 식에 대입하면 x=3x=3이다.

Pivot과 Multiplier

가우스 소거법에서 중요한 개념은 pivot과 multiplier이다.

Pivot은 소거 기준이 되는 행의 첫 번째 0이 아닌 값이다.

위 예시에서는 첫 번째 pivot이 A11=1A_{11}=1이다.

Multiplier는 제거하려는 항의 계수를 pivot으로 나눈 값이다.

l21=31=3l_{21} = \frac{3}{1} = 3

여기서 33은 제거하려는 두 번째 행의 첫 번째 열 원소이고, 11은 pivot이다.

두 번째 행에서 첫 번째 행의 33배를 빼면 다음과 같다.

(3,2)−3(1,−2)=(0,8)(3,2) - 3(1,-2) = (0,8)

우변도 같이 계산해야 한다.

11−3⋅1=811 - 3 \cdot 1 = 8

따라서 두 번째 방정식은 다음과 같이 바뀐다.

8y=88y = 8

Elimination이 실패하는 경우

소거 과정이 실패할 수도 있다. 이때는 해가 없거나 무수히 많은 해가 존재한다.

예를 들어 다음 방정식계를 보자.

x−2y=13x−6y=11\begin{align} x - 2y &= 1 \\ 3x - 6y &= 11 \end{align}

두 번째 식의 좌변은 첫 번째 식 좌변의 3배이다.

3(x−2y)=3x−6y3(x-2y) = 3x - 6y

하지만 우변은 11의 3배인 33이 아니라 1111이다.

즉, 서로 모순되는 식이다.

Row picture로 보면 두 직선은 평행하므로 교점이 없다. 따라서 해가 존재하지 않는다.

Column picture로 보면 계수행렬의 열벡터들이 만드는 선형결합으로 b=(1,11)b=(1,11)을 만들 수 없다.

소거 결과 다음과 같은 식이 나오면 해가 없다.

0≠00 \neq 0

반대로 다음과 같은 식이 나오면 중복된 방정식이 있다는 뜻이다.

0=00 = 0

이 경우 자유변수가 생기며, 일반적으로 해가 무수히 많을 수 있다.

Pivot이 0인 경우

Pivot은 0이 될 수 없다. 왜냐하면 multiplier를 계산할 때 pivot으로 나누어야 하기 때문이다.

multiplier=제거할 행의 계수pivot\text{multiplier} = \frac{\text{제거할 행의 계수}}{\text{pivot}}

만약 pivot 자리에 0이 있다면, 아래쪽 행 중에서 해당 열의 값이 0이 아닌 행과 교환해야 한다.

이 과정을 row exchange라고 한다.

행 교환은 방정식의 순서만 바꾸는 것이므로 해를 바꾸지 않는다.

미지수 3개 예시

다음 선형 시스템을 보자.

2x+4y−2z=24x+9y−3z=8−2x−3y+7z=10\begin{align} 2x + 4y - 2z &= 2 \\ 4x + 9y - 3z &= 8 \\ -2x - 3y + 7z &= 10 \end{align}

이를 첨가행렬로 쓰면 다음과 같다.

[24−2249−38−2−3710]\left[ \begin{array}{ccc|c} 2 & 4 & -2 & 2 \\ 4 & 9 & -3 & 8 \\ -2 & -3 & 7 & 10 \end{array} \right]

목표는 아래쪽 원소들을 0으로 만들어 위삼각행렬을 얻는 것이다.

1단계: A21A_{21} 소거

첫 번째 pivot은 A11=2A_{11}=2이다.

제거하려는 원소는 A21=4A_{21}=4이다.

Multiplier는 다음과 같다.

l21=42=2l_{21} = \frac{4}{2} = 2

두 번째 행에서 첫 번째 행의 2배를 뺀다.

R2←R2−2R1R_2 \leftarrow R_2 - 2R_1

계산하면 다음과 같다.

(4,9,−3∣8)−2(2,4,−2∣2)=(0,1,1∣4)(4,9,-3 \mid 8) - 2(2,4,-2 \mid 2) = (0,1,1 \mid 4)

따라서 행렬은 다음과 같이 바뀐다.

[24−220114−2−3710]\left[ \begin{array}{ccc|c} 2 & 4 & -2 & 2 \\ 0 & 1 & 1 & 4 \\ -2 & -3 & 7 & 10 \end{array} \right]

2단계: A31A_{31} 소거

첫 번째 pivot은 여전히 A11=2A_{11}=2이다.

제거하려는 원소는 A31=−2A_{31}=-2이다.

Multiplier는 다음과 같다.

l31=−22=−1l_{31} = \frac{-2}{2} = -1

세 번째 행에서 첫 번째 행의 −1-1배를 뺀다.

R3←R3−(−1)R1R_3 \leftarrow R_3 - (-1)R_1

이는 세 번째 행에 첫 번째 행을 더하는 것과 같다.

(−2,−3,7∣10)−(−1)(2,4,−2∣2)=(0,1,5∣12)(-2,-3,7 \mid 10) - (-1)(2,4,-2 \mid 2) = (0,1,5 \mid 12)

따라서 행렬은 다음과 같다.

[24−22011401512]\left[ \begin{array}{ccc|c} 2 & 4 & -2 & 2 \\ 0 & 1 & 1 & 4 \\ 0 & 1 & 5 & 12 \end{array} \right]

3단계: A32A_{32} 소거

두 번째 pivot은 A22=1A_{22}=1이다.

제거하려는 원소는 A32=1A_{32}=1이다.

Multiplier는 다음과 같다.

l32=11=1l_{32} = \frac{1}{1} = 1

세 번째 행에서 두 번째 행을 뺀다.

R3←R3−R2R_3 \leftarrow R_3 - R_2

계산하면 다음과 같다.

(0,1,5∣12)−(0,1,1∣4)=(0,0,4∣8)(0,1,5 \mid 12) - (0,1,1 \mid 4) = (0,0,4 \mid 8)

최종적으로 다음 위삼각행렬을 얻는다.

[24−2201140048]\left[ \begin{array}{ccc|c} 2 & 4 & -2 & 2 \\ 0 & 1 & 1 & 4 \\ 0 & 0 & 4 & 8 \end{array} \right]

즉, 원래의 Ax=bAx=b는 다음 Ux=cUx=c로 바뀐다.

2x+4y−2z=2y+z=44z=8\begin{align} 2x + 4y - 2z &= 2 \\ y + z &= 4 \\ 4z &= 8 \end{align}

여기서 pivot들은 위삼각행렬 UU의 대각선에 놓인다.

2, 1, 42,\ 1,\ 4

Back Substitution

위삼각행렬 형태가 되면 마지막 식부터 거꾸로 해를 구한다.

마지막 식에서 다음을 얻는다.

4z=84z = 8

따라서

z=2z = 2

두 번째 식은 다음과 같다.

y+z=4y + z = 4

z=2z=2를 대입하면 다음과 같다.

y+2=4y + 2 = 4

따라서

y=2y = 2

첫 번째 식은 다음과 같다.

2x+4y−2z=22x + 4y - 2z = 2

y=2y=2, z=2z=2를 대입하면 다음과 같다.

2x+8−4=22x + 8 - 4 = 2

따라서

2x=−22x = -2

그러므로

x=−1x = -1

최종 해는 다음과 같다.

(x,y,z)=(−1,2,2)(x,y,z) = (-1,2,2)

해 검산

원래 방정식에 해를 대입해 확인할 수 있다.

A[−122]=[24−249−3−2−37][−122]A \begin{bmatrix} -1 \\ 2 \\ 2 \end{bmatrix} = \begin{bmatrix} 2 & 4 & -2 \\ 4 & 9 & -3 \\ -2 & -3 & 7 \end{bmatrix} \begin{bmatrix} -1 \\ 2 \\ 2 \end{bmatrix}

각 행을 계산하면 다음과 같다.

2(−1)+4(2)−2(2)=24(−1)+9(2)−3(2)=8−2(−1)−3(2)+7(2)=10\begin{align} 2(-1) + 4(2) - 2(2) &= 2 \\ 4(-1) + 9(2) - 3(2) &= 8 \\ -2(-1) - 3(2) + 7(2) &= 10 \end{align}

따라서

A[−122]=[2810]=bA \begin{bmatrix} -1 \\ 2 \\ 2 \end{bmatrix} = \begin{bmatrix} 2 \\ 8 \\ 10 \end{bmatrix} = b

해가 맞다.

핵심 정리

  1. 가우스 소거법은 선형 시스템 Ax=bAx=b를 위삼각행렬 Ux=cUx=c로 바꾼 뒤, 역대입으로 해를 구하는 방법이다.

  2. (i,j)(i,j) 위치의 원소를 0으로 만들려면, pivot 행에 multiplier를 곱한 뒤 해당 행에서 뺀다.

Ri←Ri−lijRjR_i \leftarrow R_i - l_{ij}R_j
  1. Multiplier는 제거할 행의 계수를 pivot으로 나눈 값이다.
lij=제거할 원소pivotl_{ij} = \frac{\text{제거할 원소}}{\text{pivot}}

  1. Pivot은 0이 될 수 없다. pivot이 0이면 아래쪽의 0이 아닌 행과 row exchange를 수행한다.

  2. 위삼각행렬 Ux=cUx=c는 back substitution으로 해를 구할 수 있다.

  3. 소거 결과 0≠00 \neq 0이 나오면 해가 없다.

  4. 소거 결과 0=00 = 0이 나오면 중복 방정식이 있는 것이며, 자유변수에 따라 해가 무수히 많을 수 있다.

한 줄 요약

가우스 소거법은 방정식계를 위삼각형 모양으로 단순화한 뒤, 마지막 식부터 거꾸로 대입해 해를 구하는 방법이다.