線形代数
LU分解; LU Decomposition

概要

---

LU分解はある行列\(A\)を下三角行列\(L\)と上三角行列\(U\)を用いて\(A=L U\)として分解する手法である。
LU分解することで行列式や逆行列が計算しやすくなるという利点がある。

\(L, U\)は以下のような行列になる。
\( \quad L = \begin{pmatrix} 1 & 0 & & \cdots & & 0 \\ l_{2, 1} & 1 & 0 & & & \\ \vdots & \ddots & \ddots & & & \\ & & l_{i+1, i} & & \ddots & \vdots \\ \vdots & & & \ddots & \ddots & 0 \\ l_{N, 1} & \cdots & & \cdots & l_{N, N-1}, & 1 \end{pmatrix} , \quad U = \begin{pmatrix} u_{1, 1} & & & \cdots & & u_{1, N} \\ 0 & u_{2, 2} & & & & \\ \vdots & \ddots & \ddots & & & \\ & & & u_{i, i} & & \vdots \\ \vdots & & & \ddots & \ddots & \\ 0 & \cdots & & \cdots & 0 & u_{N, N} \end{pmatrix} \)
またLU分解には、\(L\)の対角成分を1とするドゥーリトル法と、\(U\)の対角成分を1とするクラウト法があるが、ここではドゥーリトル法を用いる。

行列クラス本体はこちら

LU分解の性質

---

LU分解で求められた\(L, U\)は以下のような性質を持つ。ここで\(|A|\)は\(A\)の行列式である。
\( \quad A = LU \)
\( \quad A^{-1} = U^{-1} L^{-1} \)
\( \quad |A| = |L| |U| = \displaystyle \prod_{i=1}^{N} u_{i, i} \)


ソースコード

---

namespace Algebra {
    /// <summary>行列クラス</summary>
    public partial class Matrix {
        /// <summary>LU分解</summary>
        public void LUDecomposition(out Matrix lower_matrix, out Matrix upper_matrix) {
            if(!IsSquare(this)) {
                throw new InvalidOperationException();
            }
            
            Matrix m = Copy();
            lower_matrix = Matrix.Zero(Size, Size);
            upper_matrix = Matrix.Zero(Size, Size);

            int i, j, k, n = Size;

            //LU分解
            for(i = 0; i < n; i++) {
                for(j = i + 1; j < n; j++) {
                    double mul = m[j, i] /= m[i, i];
                    m[j, i] = mul;

                    for(k = i + 1; k < n; k++) {
                        m[j, k] -= m[i, k] * mul;
                    }
                }
            }

            //三角行列格納
            for(i = 0; i < n; i++) {
                lower_matrix[i, i] = 1;
                for(j = 0; j < i; j++) {
                    lower_matrix[i, j] = m[i, j];
                }
                for(; j < n; j++) {
                    upper_matrix[i, j] = m[i, j];
                }
            }
        }
    }
}

関連項目

---

行列
ガウスの消去法
QR分解
行列式
トレース
固有値・固有ベクトル