오늘은 선형대수학에서의 가우스 소거법의 의미와 방법을 알아보고 알고리즘으로 구현해 보는 시간을 갖도록 하겠습니다.
가우스 소거법이란?
가우스 소거법이란 선형대수학에서 연립일차방정식의 해를 구하는 방법입니다.
예를 들어 다음의 식을 모두 만족하는 해를 구한다고 생각해 봅시다.
- x + y + z = 9
- 2x + 4y - 3z = 1
- 3x + 6y - 5z = 0
가우스 소거법은 행렬 연산을 이용해 연립일차방정식의 해를 구하는 대표적인 방법 중 하나입니다.
먼저 각 미지수의 계수와 상수를 넣은 확대계수행렬을 만듭니다.
이후 기본행연산을 통해 행사다리꼴행렬로 만들어줍니다.
기본행연산이란 행렬에 다음과 같은 연산을 적용하는 것을 의미합니다.
- 두 행을 교환한다.
- 한 행에 상수배를 곱한다.
- 한 행에 상수배를 곱하여 다른 행에 더한다.
기본행연산을 적용한 두 행렬은 동치이며 두 연립일차방정식의 해는 달라지지 않습니다.
행사다리꼴행렬이란 행에서 0이 아닌 첫 번째 값인 선행 계수(피벗)의 밑의 숫자를 모두 0으로 만든 행렬입니다.
행사다리꼴행렬의 예시는 밑에서 보여드리겠습니다.
컴퓨터 알고리즘에서는 행사다리꼴로 만드는 과정에서 기본행연산중 3번의 방법만 보통 사용합니다.
1, 2번 방법은 인간이 계산의 편의를 위해 사용하는 방법이고 오히려 컴퓨터 연산 횟수를 늘릴 수 있기 때문입니다.
가령 위의 행의 피벗이 아래의 숫자보다 큰 경우나 피벗이 분수인 경우를 생각해 봅시다.
이 경우 3번 방법만을 사용한다면 분수를 통해 연산해야 하는데 인간은 분수를 통해 계산하는 것에 어려움이 있기 때문에 1, 2번 방법을 사용하는 것입니다.
하지만, 컴퓨터의 경우 분수를 통해 연산하는 것에 어려움이 없고 1, 2번 방법을 사용할 경우 연산 횟수만 늘어나기 때문에 3번 방법만 사용합니다.
이제 기본행연산을 통해 행사다리꼴행렬을 만들어봅시다.
첫 번째 행에 -2를 곱하여 두 번째 행에 더해주면 두 번째 행의 첫 번째 계수가 0이 됩니다.
그리고, 첫 번째 행에 -3을 곱하여 세 번째 행에 더해주면 세 번째 행의 첫 번째 계수가 0이 됩니다.
이후 두 번째 행에 -3/2을 곱하여 세 번째 행에 더해주면 세 번째 행의 두 번째 계수가 0이 됩니다.
위의 행렬을 행사다리꼴 행렬이라 하고 행렬의 모양이 0을 제외하고 본다면 사다리꼴 모양인 것을 알 수 있습니다.
위의 행사다리꼴 행렬은 다음의 연립일차방정식으로 쓸 수 있습니다.
- x + y + z = 9
- 2y - 5z = -17
- -0.5z = -1.5
이제는 3번째 연립일차방정식부터 풀어서 위의 행에 각 미지수의 값을 차례대로 대입해주기만 하면 됩니다.
위와 같은 방법을 후진대입법이라 합니다.
3번 행 계산 결과 z = 3, 이를 2번 행에 대입하면 y = -1, 이를 1번 행에 대입하면 x = 7이라는 해가 나오게 됩니다.
가우스 소거법 알고리즘
이제 위의 계산 과정을 컴퓨터 프로그래밍을 통해 구현해 보도록 하겠습니다.
해가 무수히 많거나 없는 경우, 행사다리꼴은 구할 수 있으나 해를 구할 수는 없습니다.
a는 계수행렬이고, b는 상수벡터입니다.
1. 행사다리꼴 변환
# 행사다리꼴 변환
for k in range(0, n-1): ## 1
for i in range(k+1, n): ## 2
if a[i, k] != 0.0: ## 3
lam = a[i, k] / a[k, k] ## 4
a[i, k:n] = a[i, k:n] - lam*a[k, k:n] ## 5
b[i] = b[i] - lam*b[k] ## 6- 처음에 주어지는 행렬은 행이 0부터 n-1까지 총 n개의 행이 있는 확대계수행렬입니다. k는 현재 피벗이 포함된 피벗행이고 피벗행은 0부터 n-2까지 총 n-1개의 행이 있습니다.
- i는 피벗을 통해 계수가 0으로 변환될 피벗 밑에 있는 행들이고 k+1부터 n까지 n-k개의 행이 있습니다.
- a[i, k]는 계수행렬의 i행, k열로 피벗 밑의 값을 의미합니다. a[i, k]가 0인 경우 행 변환을 건너뜁니다.
- lam은 피벗 밑의 값을 0으로 만들기 위한 람다값입니다.
- 피벗행(k행)에 람다값을 곱하여 밑에 행에 빼줍니다. 이 과정을 통해 피벗 밑의 값이 0이 됩니다.
- 상수벡터에도 똑같은 연산을 해줍니다.
위의 과정을 for문을 통해 반복하면 행사다리꼴 행렬을 구할 수 있습니다.
2. 후진 대입법
# 후진 대입법
x = [0, 0, 0] ## 1
for k in range(n-1, -1, -1): ## 2
x[k] = (b[k] - np.dot(a[k, k+1: n], x[k+1: n])) / a[k, k] ## 3- 해 벡터를 0으로 초기화합니다.
- n-1부터 1씩 감소하면서 0까지 반복합니다.
- y, z의 값은 밑에서 구했다고 가정했을 때, ax + by + cz = d에서 x의 해를 구하기 위해선 x = (d - by - cz) / a 형태로 변환하면 됩니다. 이때 밑에서 구한 해를 위의 미지수에 대입하는 것 대신 행렬의 내적을 이용하여 (by + cz) 값을 구할 수 있습니다.
위의 알고리즘을 함수로 만들어 실제 행렬을 대입하여 해를 구해봅시다.
# 가우스 소거법으로 해 구하기
import numpy as np
def gaussElimin(a, b):
n = len(b)
# 행사다리꼴 변환
for k in range(0, n-1):
for i in range(k+1, n):
if a[i, k] != 0.0:
lam = a[i, k] / a[k, k]
a[i, k:n] = a[i, k:n] - lam*a[k, k:n]
b[i] = b[i] - lam*b[k]
# 후진 대입법
x = [0, 0, 0]
for k in range(n-1, -1, -1):
x[k] = (b[k] - np.dot(a[k, k+1: n], x[k+1: n])) / a[k, k]
return a, x계수행렬 a와 상수벡터 b를 넣으면 행사다리꼴 a와 해 벡터 x를 return 하는 함수입니다.
a = np.array([[1, 1, 1],
[2, 4, -3],
[3, 6, -5]],
dtype=np.float64)
b = np.array([9, 1, 0], dtype=np.float64)
a, x = gaussElimin(a, b)위에서 손으로 계산했던 것과 동일한 계수행렬과 상수벡터를 함수에 넣어봅시다.
이전에 구한 것과 동일한 결과가 나오는 것을 확인할 수 있습니다.
지금까지 가우스 소거법의 의미와 방법을 알아보고 알고리즘으로 구현해 보는 시간을 가져보았습니다.
위의 알고리즘은 행사다리꼴 변환 단계에서 약 n^3 / 3, 후진 대입 단계에서 n^2 / 2의 연산 횟수를 가집니다.
하지만 계수행렬이 특정 조건들을 만족할 경우 LU 분해의 일종인 cholesky 분해를 통해 연산 횟수를 줄일 수 있는데 이것은 다음 시간에 알아보도록 하겠습니다.