-
가우스 소거법 (Gauss_Elimination)머신러닝(MACHINE LEARNING)/간단하게 이론(Theory...) 2021. 4. 28. 18:16반응형
1. 가우스 소거법이란..?
- 가우스 소거법이란, 선형 방정식을 풀기위해 고안된 방법으로, 명명 그대로, 프리드리안 가우스에 의해 고안되어 졌다.일반적으로, 행렬 A,B 가 존재할 때, Ax = B 를 만족시키는 x 를 빨리 찾아낼때, 쓸 수 있다.
-일반적으로, 중학교,고등학교에서 역행렬을 취해줌으로써, x를 구하곤 했지만, 더 고차원으로 가게 되면, 가우스 소거법을 사용하여, 연립일차 방정식을 풀어주게 된다.
2. 가우스 소거법 단계
그럼 가우스 소거법이 왜 쓰인지는 알았으니, 적용을 해보자. 가우스 소거법은 2가지 단계로 이루어져 있으며, 첫번째 단계는
1. 전방 소거법(Forward Elimination)
2. 후방 대입법(back substitution)
을 적용하여 풀게 된다.
1. 전방 소거법(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)
반응형'머신러닝(MACHINE LEARNING) > 간단하게 이론(Theory...)' 카테고리의 다른 글
LU분해(LU_Decomposition)란 (0) 2021.04.29 행사다리꼴 행렬(echelon form matrix)이란 (0) 2021.04.29 ID3 모델 구현_Python(2)_전체모델 (0) 2021.04.26 ID3 모델 구현_Python (2) 2021.04.26 Decision Tree 에서의 ID3 알고리즘 (0) 2021.04.25