일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
- 컴공수학
- 여인수 전개
- 정보처리기사 기출
- 컴퓨터공학
- 알고리즘
- 메가존아이티평생교육원
- 행렬식 파이썬
- LU분해 파이썬
- 가우스조던소거법
- determinant
- 머신러닝
- 선형대수학
- LU분해 알고리즘 구현
- 중간고사
- 행렬식의 정의
- 정규방정식
- 행렬식
- 가우스조르당소거법
- lte라우터
- 선형회귀모델
- 정보처리기사 후기
- 김영평생교육원
- 라이프니츠 공식
- 한국기술교육대학교
- 한국데이터산업진흥원
- 학사
- 학점은행제
- 원격평생교육진흥원
- LU분해
- 화웨이라우터
- Today
- Total
gyeo-ri.com
LU 분해(LU Decomposition) - (2) 해 도출(Forward/Back Substitution) 본문
LU 분해(LU Decomposition) - (2) 해 도출(Forward/Back Substitution)
겨리_Gyeori 2021. 1. 11. 20:55*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 참조)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
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) #실제 해는 마지막 열(앞은 계수행렬 = 단위행렬), 열벡터 형태로 반환
|
cs |
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} $
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
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
|
cs |
Back Substitution은 Forward Substitution과 반복 위치만 다르고, 전체적으로 동일한 연산이다. 마찬가지로 대각행렬을 구하는 소거 연산을 수행한 후 필요에 따라 선행원소를 1로 만들어주는 연산을 적용한다.
함수의 결과로 3,2,1을 원소로 가지는 행렬이 반환된다. 이전 포스팅에서 구현한 가우스-조르당 소거법 연산의 결과와도 동일한 값이다.
참고자료
1. 프로그래머를 위한 선형대수(히라오카 카즈유키 저, 이창신 옮김) - 길벗(2017)
2. [Youtube] 쑤튜브 : 10분 선형대수 강의 모음(youtu.be/x-Ewz1ukXEA)
'Study Note > 선형대수학' 카테고리의 다른 글
수반행렬의 성질과 크래머의 공식 (0) | 2021.01.14 |
---|---|
행렬식(Determinant) - 여인수 전개와 가우스 소거법을 이용한 방법 (0) | 2021.01.13 |
행렬식(Determinant) - 라이프니츠 공식 (0) | 2021.01.12 |
LU 분해(LU Decomposition) - (1) 분해 과정 (2) | 2021.01.07 |
가우스-조르당 소거법(Gauss-Jordan 소거법) (0) | 2021.01.06 |