PA = LU,  Ax=b

1. A를 한 번 분해해 P, L, U 준비
2. Ly=Pb를 앞에서부터 풀이
3. Ux=y를 뒤에서부터 풀이

소거를 분해로 저장

다음 A는 둘째 행에서 첫째 행의 2배를 빼면 위삼각형이 됩니다. L의 대각은 1로 두는 표현을 사용합니다.

A = [ 2  1 ]      L = [ 1  0 ]      U = [ 2  1 ]
    [ 4  3 ]          [ 2  1 ]          [ 0  1 ]

R₂ ← R₂ - 2R₁
L에는 제거에 사용한 배수 2를 기록
LU = [ 2  1 ] = A
     [ 4  3 ]

소거 행렬에는 -2가 등장하지만, 이를 되돌려 A를 구성하는 L에는 +2가 들어갑니다. L과 소거 연산 자체의 부호를 혼동하지 않습니다. 가우스 소거는 해집합을 보존하는 절차, LU는 그 절차를 분해 형태로 보관하는 관점입니다.

앞·뒤 대입으로 해 구하기

b=(5,11)일 때 Ly=b를 먼저 풉니다. L은 아래삼각이므로 첫 행부터 y를 결정할 수 있습니다.

Ly=b:
  y₁=5
  2y₁+y₂=11 → y₂=1

Ux=y:
  x₂=1
  2x₁+x₂=5 → x₁=2

해 x=(2,1),  Ax=(5,11)

같은 A에 다른 b가 들어오면 기존 L·U를 그대로 두고 두 삼각 풀이만 반복합니다. A 자체가 바뀌면 같은 분해를 계속 사용할 수 있는지 다시 판단해야 합니다.

피벗과 행 교환

첫 피벗이 0이라고 행렬 전체가 반드시 특이한 것은 아닙니다. 예를 들어 다음 A₀는 첫 성분이 0이지만 det(A₀)=-2라 가역입니다.

A₀ = [ 0  2 ]      P = [ 0 1 ]      PA₀ = [ 1 3 ]
     [ 1  3 ]          [ 1 0 ]            [ 0 2 ]

b=(4,7) → Pb=(7,4)
L=I, U=PA₀

Ux=Pb → x₂=2, x₁=1

계수행렬만 교환하고 b를 그대로 두면 다른 선형계를 풀게 됩니다. 라이브러리가 A=PLU 같은 다른 순열 표기를 쓸 수도 있으므로 이름 P보다 반환한 관계식을 먼저 확인합니다.

부동소수점에서는 0인 피벗만 피하는 것이 아니라 작은 수로 나누며 생기는 오차도 고려합니다. 부분 피벗은 현재 열에서 사용할 수 있는 성분의 절댓값을 비교해 행을 선택합니다. 뒤 단계에서 행을 교환하면 앞서 기록한 L의 관련 부분도 일관되게 관리해야 합니다.

선택과 실패 조건

삼각 풀이 중 0인 대각으로 나눌 수는 없습니다. 피벗 없는 LU를 진행하지 못하는 경우와 원래 선형계가 유일해를 갖지 않는 경우를 같은 이유로 단정하지 않습니다. 조건수는 분해를 성공시켰어도 입력 오차에 민감할 수 있는 문제를 설명합니다.

그래픽스의 변형·제약 풀이에서 같은 계수행렬에 여러 위치·좌표 성분을 대입할 때 분해 재사용이 유용합니다. 분해는 수치 풀이의 도구이며 렌더링 API가 자동으로 수행하는 행렬 업로드 단계는 아닙니다.