3장-LU분해

먼저, 벡터와 행렬의 연산은 for루프를 돌려 성분마다 조작하는 것이 기본이다. 행렬과 벡터의 곱을 구현하면 이중루프가 되고, 행렬끼리의 곱을 구현하면 삼중루프가 된다. 사용하는 프로그래밍언어마다 적절한 패키지가 존재하므로 이를 사용하면 된다. 

 

 

LU분해

컴퓨터로 수치계산을 할 때에는 LU분해가 기본 부품으로 사용되는데, 처음에 시간을 들여 분해해 두면, 나중에 여기저기 편해지기 때문이라고 생각하면 된다. L과 U의 형태를 이용하여 행렬식을 구하거나 일차방정식을 푸는 등의 계산을 적은 계산양으로 수행할 수 있게 된다. 

L은 하삼각행렬이고, U는 상삼각행렬을 나타내며, 하나의 행렬을 L과 U의 곱으로 나타내는 것을 LU 분해라고 한다.

위와 같은 형태가 만들어질 수 있도록 ■ 의 값을 잘 채워주는 것이다. 

 

실제로는, L의 대각성분을 1로 한정하여 아래와 같은 형태를 보인다.

 

LU 분해의 순서

 

 

LU분해로 행렬식 구하기

정방행렬 A가 LU분해 되어 있다면, A의 행렬식은 바로 구해진다. 

곱의 행렬식은 행렬식의 곱이므로, det A = det(LU) = (det L)(det U) 이다. 여기서 하삼각행렬과 상삼각행렬의 행렬식은 대각성분의 곱이다. 행렬 L의 대각성분은 모두 1이므로 det L = 1 이므로, det A = (U의 대각성분의 곱) 이라고 할 수 있다.

 

 

 

LU분해로 일차방정식 풀기

정칙행렬이 n차 정방행렬 A와 n차원 벡터인 y 에 대해 Ax = y 가 되는 x를 구하는 문제가 연립일차방정식의 문제이다. 여기서 A가 LU로 분해되어 있다고 가정하는 것이기 때문에, 문제를 두 단계로 나눌 수 있다. x에 우선 U를 곱하고, 거기에 L을 곱하면 y가 된다는 것을 의미한다. 그렇다면, Lz = y 가 되는 z를 구하고, Ux = z 가 되는 x를 구하는 순서가 된다.

 

즉, 

Ax = LUx = L(U)x = Lz = y 가 된다. 

 

행렬 L과 U의 형태가 특별하기 때문에 쉽게 구할 수 있게 된다. L의 경우 대각성분이 모두 1이기 때문에 첫 번째 식에서부터 변숫값을 구하여 대입해 나갈 수 있고(위에서 표현한 것으로는 z를 구할 수 있음), U의 경우도 마찬가지로, 맨 아래의 행은 대각성분 하나만 값이 있고 나머지는 0이기 때문에 변숫값을 바로 구할 수 있으며, 차례로 윗 행에 대입해 가면서 구할 수 있다.(위에서 표현한 것으로는 x를 구할 수 있게 됨) 

아래의 그림을 본다면 훨씬 쉽게 이해할 수 있다.