[선형대수] LU분해

수식이 잘 랜더링되지 않을 시, 여러 번 새로고침하거나 다른 브라우저를 사용해보세요.

🔻LU 분해

🔸정의

임의의 정방행렬 A를 하삼각행렬(L)과 상삼각행렬(U)의 곱인 A=LU 로 표현하는 것을 의미한다. LU 분해 또는 LU 행렬 분해라고 한다.

[그림1 - LU분해]

분해된 L 또는 U의 주대각 성분이 모두 1이면 단위 삼각행렬이어서 '단위 상/하삼각행렬 분해'라고도 한다.

🔸LU 분해가 성립하는 조건

당연히 모든 정방행렬이 LU분해되지는 않는다.
다음과 같은 조건을 만족하는 정방행렬만 LU분해가 가능하다.
조건 : 정방행렬 A에 대하여 위쪽 행의 상수배를 아래쪽 행에 더하는 기본행연산만을 적용하여 상삼각행렬로 만들 수 있어야 한다.

기본행연산 ERO 복습 링크
기본행연산에는 3가지 종류가 있었다. 행 교환, 상수배, 상수배를 다른 행에 덧셈.
이 중에서 3번째 ERO, 그리고 그중에서도 위쪽 행의 상수배를 아래쪽 행에 더하는 ERO 연산만 사용해서 상삼각행렬을 만들 수 있어야 한다.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
증명) n차 정방행렬 A에 기본행연산을 취해 상삼각행렬로 만들어보자.

[그림2 - LU분해의 성립 조건]

각각의 기본행렬이 모두 하삼각행렬이라면 하삼각행렬의 곱도 하삼각행렬이므로 A=LU를 만족하게 된다.
그러나 기본행렬 중 하나라도 하삼각행렬이 아니면 기본행렬들의 곱은 하삼각행렬이 아니다.
(하삼각행렬들의 곱도 하삼각행렬인 이유)

그렇다면 각각의 기본행렬들이 모두 하삼각행렬인 조건이 곧 LU분해가 성립하는 조건과 같다고 할 수 있다.
(기본행렬 복습)
기본행렬도 기본행연산과 마찬가지로 3가지 종류밖에 없다.
이 중에서 하삼각행렬인 기본행렬은 아래 사진과 같다.

[그림3 - 하삼각행렬인 기본행렬]

📢상수배 기본행렬도 하삼각행렬인데 왜 조건에 없나요?
상수배 기본행렬도 LU 분해 성립 조건에 부합하는 경우이지만, "굳이" 필요하지 않기 때문에 제외시켜도 상관 없다.
우리는 상삼각행렬을 만드는 것이 목적이지, 행사다리꼴 행렬이나 기약행 사다리꼴 행렬을 만드는 것이 아니기 때문에 상수배 행연산은 LU분해에서 "굳이" 사용할 일이 없다.

📢그런데 위의 2번 그림을 보면 기본행렬의 "역행렬"들이 곱해지고 있는데요?
기본행렬의 역행렬도 똑같이 3가지 종류밖에 없다. 그리고 그 모양이 원래 기본행렬과 같다.
기본행렬이 하삼각행렬이라면, 기본행렬의 역행렬도 하삼각행렬이고
기본행렬이 상삼각이라면, 기본행렬의 역행렬로 상삼각이다.

따라서 3번째 경우의 기본행렬 중에서도 특히 위쪽 행의 상수배를 아래쪽 행에 더하는 기본행렬일 때에만 아래와 같은 수식(기본행렬의 역행렬의 곱=하삼각행렬)을 만족한다.
\((E_n \cdots E_1)^{-1} = E_1^{-1}\cdots E_n^{-1} = L\)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

🔸LU 분해 예제

[그림4 - LU분해 예제]

예제의 초록색 선들을 유심히 보면 알겠지만, 굳이 하삼각행렬 L을 구할 때 기본행렬의 역행렬들을 곱할 필요가 없다.
기본행연산에서 곧바로 하삼각행렬 L을 도출할 수 있다!!!
기본행연산을 다음과 같이 ( R_a - R_b * c ) 라고 표현할 때, 단위행렬의 a행 b열의 성분을 c로 바꾸면 된다.
다음 그림을 보면 더 이해가 쉽다.

[그림5 - 예제 추가설명]

 

🔸LU 분해의 이점 benefit

📢n차 정방행렬 A를 LU분해하는 데에 필요한 기본행연산의 횟수는 최대 (n-1)번이다.
위의 5번 그림과 같이 L을 구할 때 행렬곱 연산도 필요 없으므로 '곱셈 연산'의 횟수도 획기적으로 줄여준다.

 

🔻LU 분해를 활용한 행렬방정식 풀이

🔸풀이

🔸예제

[그림6 - 행렬방정식 LU분해 풀이 예제]