Corgi Dog Bark

ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 가우스 소거법 (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)

    전방 소거법(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)
    반응형

    댓글

Designed by Tistory.