lu
行列の LU 分解
構文
説明
[___] = lu(___, は、outputForm)outputForm で指定した形式で P と Q を返します。P と Q を置換ベクトルとして返すには、outputForm を 'vector' として指定します。前述の構文にある任意の入力引数の組み合わせが使用できます。
例
行列の LU 分解を計算し、生成される因子を確認します。LU 分解は、行列 を、上三角行列 、下三角行列 、置換行列 に分解する手法です。このとき、 が成立します。これらの行列は、行列が行簡約階段形になるまでガウスの消去法を実行するために必要なステップを表します。行列 にはすべての乗算器が含まれます。また、置換行列 では行交換が考慮されます。
3 行 3 列の行列を作成し、LU 因子を計算します。
A = [10 -7 0
-3 2 6
5 -1 5];[L,U] = lu(A)
L = 3×3
1.0000 0 0
-0.3000 -0.0400 1.0000
0.5000 1.0000 0
U = 3×3
10.0000 -7.0000 0
0 2.5000 5.0000
0 0 6.2000
これらの因子を乗算して、A を再作成します。lu は 2 入力の構文を使用して、置換行列 P を直接 L 因子に組み込みます。このとき、返される L は実際には P'*L となり、そのため A = L*U となります。
L*U
ans = 3×3
10 -7 0
-3 2 6
5 -1 5
3 つの出力を指定して、置換行列を L の乗算器から分離することができます。
[L,U,P] = lu(A)
L = 3×3
1.0000 0 0
0.5000 1.0000 0
-0.3000 -0.0400 1.0000
U = 3×3
10.0000 -7.0000 0
0 2.5000 5.0000
0 0 6.2000
P = 3×3
1 0 0
0 0 1
0 1 0
P'*L*U
ans = 3×3
10 -7 0
-3 2 6
5 -1 5
LU 分解を実行し、因子を使用して問題を単純化することにより、線形システムを解きます。その結果を、バックスラッシュ演算子や decomposition オブジェクトを使用した他の方法と比較します。
5 行 5 列の魔方陣行列を作成し、線形システム を解きます。ここで、b のすべての要素が 65 (魔方陣の和) と等しくなります。65 はこの行列の魔方陣の和である (すべての行および列ではその和が 65 になる) ため、x について予期される解は 1 から成るベクトルです。
A = magic(5); b = 65*ones(5,1); x = A\b
x = 5×1
1.0000
1.0000
1.0000
1.0000
1.0000
一般的な正方行列では、バックスラッシュ演算子は LU 分解を使用して線形システムの解を計算します。LU 分解により、A は三角行列の積として表され、三角行列を含む線形システムは代入式により簡単に解けます。
バックスラッシュにより計算された解を再作成するには、A の LU 分解を計算します。その後、因子を使用して次の 2 つの三角線形システムを解きます。
y = L\(P*b); x = U\y;
線形システムを解く前に行列因子を事前計算するこの方法は、多数の線形システムを解く場合のパフォーマンスを向上させることができます。これは、因数分解の発生が 1 回のみで、繰り返しが不要なためです。
[L,U,P] = lu(A)
L = 5×5
1.0000 0 0 0 0
0.7391 1.0000 0 0 0
0.4783 0.7687 1.0000 0 0
0.1739 0.2527 0.5164 1.0000 0
0.4348 0.4839 0.7231 0.9231 1.0000
U = 5×5
23.0000 5.0000 7.0000 14.0000 16.0000
0 20.3043 -4.1739 -2.3478 3.1739
0 0 24.8608 -2.8908 -1.0921
0 0 0 19.6512 18.9793
0 0 0 0 -22.2222
P = 5×5
0 1 0 0 0
1 0 0 0 0
0 0 0 0 1
0 0 1 0 0
0 0 0 1 0
y = L\(P*b); x = U\y
x = 5×1
1.0000
1.0000
1.0000
1.0000
1.0000
decomposition オブジェクトも、特殊化された因数分解により線形システムを解く場合に便利です。この方法では、因子の使用方法の知識を求められることなく、行列因子の事前計算によるパフォーマンス上のメリットを数多く得られます。同じ結果を再作成するには、タイプが 'lu' の decomposition オブジェクトを使用します。
dA = decomposition(A,'lu');
x = dA\bx = 5×1
1.0000
1.0000
1.0000
1.0000
1.0000
スパース行列の LU 分解を計算して、恒等式 L*U = P*S*Q を検証します。
Buckminster-Fuller 幾何ドームの結合グラフの 60 行 60 列のスパース隣接行列を作成します。
S = bucky;
4 つの出力をもつスパース行列構文を使用して S の LU 分解を計算し、行と列の置換行列を返します。
[L,U,P,Q] = lu(S);
S の行と列を P*S*Q と置換した結果を、三角因子 L*U を乗算した場合と比較します。1 ノルムの違いは丸め誤差の範囲に入るため、L*U = P*S*Q となります。
e = P*S*Q - L*U; norm(e,1)
ans = 5.7732e-15
行列の LU 分解を計算します。行置換を行列ではなくベクトルとして返すことで、メモリを節約します。
1000 行 1000 列のランダム行列を作成します。
A = rand(1000);
行列 P として保存されている置換情報を使用して LU 分解を計算します。結果を、ベクトル p として保存されている置換情報と比較します。行列が大きいほど、置換ベクトルを使用した場合にメモリ効率がより高くなります。
[L1,U1,P] = lu(A); [L2,U2,p] = lu(A,'vector'); whos P p
Name Size Bytes Class Attributes P 1000x1000 8000000 double p 1x1000 8000 double
また、置換ベクトルを使用すると、以降の操作の実行時間が短縮されます。たとえば、前述の LU 分解を使用して、線形システム を解くことができます。置換ベクトルから得られる解と置換行列から得られる解は等価 (丸めを除く) ですが、通常は、置換ベクトルを使用して解を求める方が時間がやや短縮されます。
スパース行列の LU 分解の計算結果を、列置換がある場合と列置換がない場合で比較します。
行列 west0479 を読み込みます。これは 479 行 479 列の実数値のスパース行列です。
load west0479
A = west0479;3 つの出力を指定して lu を呼び出し、A の LU 分解を計算します。L 因子と U 因子の spy プロットを生成します。
[L,U,P] = lu(A); subplot(1,2,1) spy(L) title('L factor') subplot(1,2,2) spy(U) title('U factor')
次に、4 つの出力を指定して lu を使用し、A の LU 分解を計算します。これにより、A の列が置換され、各因子について非ゼロの数が少なくなります。この結果生成される因子は、列置換を使用しない場合と比べて、スパースの傾向が強くなっています。
[L,U,P,Q] = lu(A); subplot(1,2,1) spy(L) title('L factor') subplot(1,2,2) spy(U) title('U factor')
入力引数
出力引数
アルゴリズム
LU 分解は、ガウスの消去法の変形を使用して計算されます。正確な解を計算できるかどうかは、元の行列の条件数の値 cond(A) によって異なります。行列の条件数が大きい (ほぼ特異である) 場合、計算された因数分解は正確でないことがあります。
LU 分解は、inv を使用して逆行列を求めたり、det を使用して行列式の値を求めるための重要な部分です。線形方程式の求解や、演算子 \ や / を使用した行列の除算に対しても基本的な役割を果たします。そのため、必然的に、これらの依存関数にも lu の数値制限が存在することになります。
参照
[1] Gilbert, John R., and Tim Peierls. “Sparse Partial Pivoting in Time Proportional to Arithmetic Operations.” SIAM Journal on Scientific and Statistical Computing 9, no. 5 (September 1988): 862–874. https://doi.org/10.1137/0909058.
[2] Anderson, E., ed. LAPACK Users’ Guide. 3rd ed. Software, Environments, Tools. Philadelphia: Society for Industrial and Applied Mathematics, 1999. https://doi.org/10.1137/1.9780898719604.
[3] Davis, Timothy A. "Algorithm 832: UMFPACK V4.3 – an unsymmetric-pattern multifrontal method." ACM Transactions on Mathematical Software 30, no. 2 (June 2004): 196–199. https://doi.org/10.1145/992200.992206.
