LU 분해(LU Decomposition) - (2) 해 도출(Forward/Back Substitution)

*LU분해의 과정에 관한 내용은 이전 포스팅 참조

 

 

  가우스-조르당 소거법 포스팅에서 $Ax = b$를 다음과 같이 정의하였다.

 

$\begin{pmatrix} 2 & 2 & 1 \\ 2 & 1 & 3 \\ 1 & 2 & 3 \end{pmatrix} \begin{pmatrix} x \\ y \\ z \end{pmatrix} = \begin{pmatrix} 11 \\ 11 \\ 10 \end{pmatrix}$

 

 

  이때, LU 분해를 통해 행렬 A를 분해할 수 있다.

 

$A = L \cdot U = \begin{pmatrix} 2 & 0 & 0 \\ 2 & -1 & 0 \\ 1 & 1 & 9/2 \end{pmatrix} \cdot \begin{pmatrix} 1 & 1 & 1/2 \\ 0 & 1 & -2 \\ 0 & 0 & 1 \end{pmatrix}$

 

 

  따라서, 연립방정식 $Ax = b$는 $L\cdot U\cdot x = b$와 같다

 

 

  여기서 $U\cdot x = z$로 정의하면 식을

$L\cdot z = b$

로 표현할 수 있는데, 이것은 $u$가 해인 새로운 방정식으로 볼 수 있다.

($U$는 3x3, $x$는 3x1이므로 $U\cdot x = z$는 3x1의 열벡터 형태이다)

 

 

 

1. Forward Substitution

  $u$는 방정식의 첨가행렬 $[\, L \,|\, b \,]$을 기본행 연산을 통해 $[\, I \,|\, z \,]$로 변환하여 구할 수 있다. 이때, 계수행렬에 해당하는 $L$은 하삼각행렬이므로, 첫 원소를 제외한 모든 열의 원소가 0인 1행부터 순차적으로 아래 행을 소거, 단위행렬($I$)을 만드는 Forward Substitution을 수행할 수 있다. 이는 가우스-조르당 소거법에서 사용하는 Back Substitution과 소거 방향만 다른 동일한 연산이다.

 

 

$[L \, | \, b] = \begin{bmatrix} 2 & 0 & \;\; 0 \;\ | \; 11 \\ 2 & -1 & \;\; 0 \;\; | \; 11 \\ 1 & 1 & 9/2 | \; 10 \end{bmatrix}   \Leftrightarrow   [I \, | \, z] = \begin{bmatrix} 1 & 0 & 0 | 11/2 \\ 0 & 1 & 0 | \;\;\; 0 \;\; \\ 0 & 0 & 1 | \;\;\; 1 \;\; \end{bmatrix}$

 

연산 결과, $z^{T} = [[11/2, 0, 1]]$이다.

 

 

 

Forward Substitution 과정을 파이썬 함수로 구현한 코드는 다음과 같다(전체 코드는 Github 참조)

def forward_substitution(aug_matrix):
    mcol = len(aug_matrix[0])
    for col in range(mcol-1):
        for row in range(col+1,mcol-1): #col/row를 파이썬 인덱스에 맞게 적용
            const = aug_matrix[row][col]/aug_matrix[col][col] * -1  #constraint
            print(col+1,"행을",round(const,2), "만큼 상수배하여", row+1, "행의", col+1,"열을 소거")
            aug_matrix[row] += const * aug_matrix[col]
            print(np.around(aug_matrix,2)) #출력을 위한 반올림
            print()
    
    for i in range(mcol-1): #행의 갯수만큼
        aug_matrix[i] /= aug_matrix[i][i] # 각 행의 선행원소를 1로 만들어 줌
            
    
    print("선행원소를 1로 만드는 연산")
    print(aug_matrix)
    
    return aug_matrix[:,-1].reshape(1,-1) #실제 해는 마지막 열(앞은 계수행렬 = 단위행렬), 열벡터 형태로 반환

 

  LU 분해 과정에서 계수행렬(L)이 하삼각행렬로 분해되었으므로, forward_substitution 함수는 첫 행부터 상수배 후 다음 행에 덧셈(뺄셈)하는 연산만을 수행하여 계수행렬을 대각행렬로 만들 수 있다. 마지막으로, 해를 구하기 위해 계수행렬의 대각원소(=각 행의 선행원소)를 1로 만들어 반환한다.

 

  실제 파이썬 연산 결과도 동일한 $z$를 반환한다.

 

 

 

 

 

 

 

2. Back Substitution

  Forward Substitution의 결과로 $z$의 값이 도출되었으므로, 앞서 새로 정의한 방정식 $U\cdot x = z$의 해 $x$를 구하기 위한 첨가행렬을 다음과 같이 나타낼 수 있다.

 

 

  $[U \, | \, z] =  \begin{bmatrix} 1 & 1 & 1/2 | 11/2 \\ 0 & 1 & -2 | \;\;\; 0 \;\; \\ 0 & 0 & \;\; 1 \; | \;\;\; 1 \;\; \end{bmatrix}$

 

첨가행렬 $[U \, | \, z]$은 행사다리꼴 형태(상삼각행렬 + 열벡터)이며, 이를 가우스-조르당 소거법과 같이 Back Substitution 하면 방정식의 최종 해 $x$를 구할 수 있다.

 

$x = \begin{pmatrix} 3 \\ 2 \\ 1 \end{pmatrix}$

 

 

 

def back_substitution(aug_matrix):
    mcol = len(aug_matrix[0])
    for col in range(mcol-2,0,-1):
        for row in range(col-1,-1,-1): #col/row를 파이썬 인덱스에 맞게 적용
            const = aug_matrix[row][col]/aug_matrix[col][col] * -1 #
            print(col+1,"행을", round(const,2), "만큼 상수배하여", row+1, "행의", col+1,"열을 소거")
            aug_matrix[row] += const * aug_matrix[col]
            print(np.around(aug_matrix,2)) #출력을 위한 반올림
    
    
    for i in range(mcol-1): #행의 갯수만큼
        aug_matrix[i] /= aug_matrix[i][i] # 각 행의 선행원소를 1로 만들어 줌
    
    return aug_matrix

 

 

  Back Substitution은 Forward Substitution과 반복 위치만 다르고, 전체적으로 동일한 연산이다. 마찬가지로 대각행렬을 구하는 소거 연산을 수행한 후 필요에 따라 선행원소를 1로 만들어주는 연산을 적용한다.

 

 

 

 

함수의 결과로 3,2,1을 원소로 가지는 행렬이 반환된다. 이전 포스팅에서 구현한 가우스-조르당 소거법 연산의 결과와도 동일한 값이다.

 

 

 

 

 

참고자료

1. 프로그래머를 위한 선형대수(히라오카 카즈유키 저, 이창신 옮김) - 길벗(2017)

2. [Youtube] 쑤튜브 : 10분 선형대수 강의 모음(youtu.be/x-Ewz1ukXEA)