The Algorithm of Calculating The Inverse of Triangular Matrices

주어진 행렬을 LU decomposition을 한 뒤 $L$과 $U$ 행렬 각각의 inverse를 구하면 역행렬을 빠르게 구할 수 있다. 이때 triangular matrix의 inverse를 빠르게 계산하는 방법을 소개하려고 한다.

 

예컨대 다음과 같은 상삼각 행렬의 역행렬을 계산해 보자. $$U = \begin{pmatrix} 3 & 6 & 8 \\ 0 & 4 & 7 \\ 0 & 0 & 5 \end{pmatrix}$$  이때 각각의 성분에 대해서 따로따로 생각해 보자. Gauss elimination을 생각하면 역행렬의 대각 성분은 원행렬의 대각 성분의 역수가 된다.  $$U^{-1} = \begin{pmatrix} \frac{1}{3} & * & * \\ 0 & \frac{1}{4} & * \\ 0 & 0 & \frac{1}{5} \end{pmatrix}$$ 다음으로 $6$과 $7$의 자리는 backward substitution을 생각하면 각각 $-\frac{6}{4}, -\frac{7}{5}$에다가 leading $1$을 만들기 위해 대각 성분의 역수를 곱해주어야 한다. $$U^{-1} = \begin{pmatrix} \frac{1}{3} & -\frac{1}{2} & * \\ 0 & \frac{1}{4} & -\frac{7}{20} \\ 0 & 0 & \frac{1}{5} \end{pmatrix}$$ 마지막 남은 성분은 cofacter expansion으로 구해준다. $\det(U) = 3 \cdot 4 \cdot 5 = 20$이고 구해준 소행렬의 판별식의 값은 $42 - 32 = 10$이므로 값은 $\frac{1}{6}$이다. 따라서 최종적인 역행렬은 다음과 같다. $$U^{-1} = \begin{pmatrix} \frac{1}{3} & -\frac{1}{2} & \frac{1}{6} \\ 0 & \frac{1}{4} & -\frac{7}{20} \\ 0 & 0 & \frac{1}{5} \end{pmatrix}$$ Upper triangular matrix에 대해서 구했지만, 동일한 알고리즘이 lower에도 적용된다.