가우스 소거법 (Gauss_Elimination)

1. 가우스 소거법이란..?

---

- 가우스 소거법이란, 선형 방정식을 풀기위해 고안된 방법으로, 명명 그대로, 프리드리안 가우스에 의해 고안되어 졌다.일반적으로, 행렬 A,B 가 존재할 때, Ax = B 를 만족시키는 x 를 빨리 찾아낼때, 쓸 수 있다.

-일반적으로, 중학교,고등학교에서 역행렬을 취해줌으로써, x를 구하곤 했지만, 더 고차원으로 가게 되면, 가우스 소거법을 사용하여, 연립일차 방정식을 풀어주게 된다.

 

 

 

2. 가우스 소거법 단계

---

그럼 가우스 소거법이 왜 쓰인지는 알았으니, 적용을 해보자. 가우스 소거법은 2가지 단계로 이루어져 있으며, 첫번째 단계는

1. 전방 소거법(Forward Elimination)

2. 후방 대입법(back substitution) 

을 적용하여 풀게 된다.

 

 

1. 전방 소거법(Forward Elimination)

전방 소거법(Forward Elimination) 진행 후 행렬

- 전방 소거법은 AX = B 라는 행렬에 대해 A를 상삼각행렬(Upper Triangular Matrix)로 만들기 위해 수행해 주는 소거법이다.

- A의 형태를 상삼각행렬로 만들어 주게 된다면, 위의 우측 그림을 보게 되었을때, x3 에 해당하는 변수는 한가지 밖에 없게 되고, 차례 대로 x3->x2->x1을 구해줄 수 있게 된다. 

 

- 전방 소거법을 하는 이유

• 주어진 선형 시스템을 가장 풀기 쉬운 꼴로 변형해준다.
• 주어진 선형시스템의 랭크(Rank)를 알려준다.
• 선형시스템이 해가 있는지 (consistent) 아니면, 해가 없는지 (inconsistent)인지 알려준다.

 

 

 

 

2. 후방 대입법 (Back Substitution)

후방 대입법은 생각보다 쉽게 되는데,

다음과 같은 전방소거법(forward_elimination)이 진행된 행렬에서 x3 는 한개의 변수만을 곱해져, 최종행렬 B 가 되기 때문에, x3->x2->x1 처럼 차례대로 선형시스템의 답을 구할 수 있게 된다.

 

 

 

3. 가우스 소거법 예시

---

그럼 가우스 소거법 예시를 살펴보자.

다음과 같은 연립일차방정식이 주어졌을때, 각각 L1,L2,L3 라 하자.

그렇다면, L1,L2,L3 를 행렬로 표현했을때,

의 코드로 나타낼 수 있으며, 먼저 전방소거법을 진행할때, 위의 L1,L2 식 과 L3,L1 식을 조합하여,

을 하게 되었을 때, 왼쪽의 matrix(2,1) 과 matrix(3,1)은 사라지게 된다. 이렇게 되면,

의 식이 되어 버리게 된다. 이로써 , 앞의 항들을 맨 처음 행을 제외한 열들에 대해 제거 완료 하였다. 2차로

L2 -> (0, 1/2, 1/2, 1)과 L3-> (0, 2, 1, 5) 을 조합하여 L3의 2를 지워주게 되면,

이 가능하게 되고 L3 -4*L2 가 진행 되어 L3 의 2번째 열(2)이 살아지게 된다. 따라서 전방소거법이 진행된 최종 형태는

다음과 같이 상삼각행렬(Triangular Form) 이 적용된 형태가 되게 된다.

후방 대입법은 위에서 설명한 바와 같이 역으로 천천히 진행 해주면 된다.

 

4. 가우스 소거법 Python 코드

---

def gauss(A,x):
    n = len(A)
    # 입력받은 행렬 A 의 크기만큼 loop을 돌면서,
    for i in range(n):
    	# A[i][i] 가 같게되면 가우스 소거법이 불가능한 행렬로, division error 수행
        if a[i][i] == 0.0:
            sys.exit('Divide by zero detected!')
        # i+1열의 A에 대해 i행과 j행의 비율을 구해 준후, 그 ratio만큼을 j-i*ratio 해준다.
        # 결과는 A[i][i] 좌측의 행 전부 0이 되게 된다.
        for j in range(i+1, n):
            ratio = A[j][i]/A[i][i]
            for k in range(n+1):
                A[j][k] -=ratio*A[i][k]
                
    # A 를 구해주고, 맨끝 X[n-1] == A[n-1][n]/A[n-1][n-1] 취해준다.
    x[n-1] = A[n-1][n]/A[n-1][n-1]
    for i in range(n-2,-1,-1):
    	# x[i] 를 구하기 위해 back substitution 시행
        x[i]=A[i][n]
        for j in range(i+1,n):
            x[i] = x[i] - A[i][j]*x[j]
        x[i] = x[i]/a[i][i]
        
    return [A,x]

# 실행 결과
a = [[1,1,1,9],[2,-3,4,13],[3,4,5,40]]

a=np.array(a)
a =a.astype(float)
x = np.zeros(len(a))

a,b = gauss(a,x)
print(a)
print(b)