Main Content

このページの内容は最新ではありません。最新版の英語を参照するには、ここをクリックします。

chol

説明

R = chol(A) は、対称正定値行列 A を、A = R'*R を満たす上三角行列 R に因数分解します。A が非対称の場合、chol はこの行列を対称であるものとして処理し、A の対角部分と上三角部分のみを使用します。

R = chol(A,triangle) は、因数分解の計算に使用する A の三角因子を指定します。たとえば、triangle'lower' の場合、cholA の対角部分と下三角部分のみを使用して、A = R*R' を満たす下三角行列 R を生成します。triangle の既定値は 'upper' です。

[R,flag] = chol(___) は出力 flag も返します。この出力は、A対称正定値であるかどうかを表します。前述の構文にある任意の入力引数の組み合わせが使用できます。flag 出力を指定すると、chol は入力行列が対称正定値でない場合にエラーを生成しません。

  • flag = 0 の場合、入力行列は対称正定値であり、因数分解は成功しています。

  • flag がゼロでない場合、入力行列が対称正定値 "ではなく"、flag は因数分解が失敗したピボット位置のインデックスを示す整数です。

[R,flag,P] = chol(S) はこれに加えて置換行列 P を返します。この行列は、amd により得られるスパース行列 S の事前並べ替えです。flag = 0 の場合、S は対称正定値であり、RR'*R = P'*S*P を満たす上三角行列です。

[R,flag,P] = chol(___,outputForm) は、前述の構文における入力引数の任意の組み合わせを使用して、置換情報 P を行列とベクトルのいずれで返すかを指定します。このオプションはスパース行列入力についてのみ使用できます。たとえば、outputForm'vector' で、かつ flag = 0 である場合、S(p,p) = R'*R になります。outputForm の既定値は 'matrix' で、このとき R'*R = P'*S*P になります。

すべて折りたたむ

chol を使用して対称係数行列を因子分解してから、コレスキー因子を使用して線形系を解きます。

対角上に正の値をもつ対称行列を作成します。

A = [1 0 1; 0 2 0; 1 0 3]
A = 3×3

     1     0     1
     0     2     0
     1     0     3

行列のコレスキー因子を計算します。

R = chol(A)
R = 3×3

    1.0000         0    1.0000
         0    1.4142         0
         0         0    1.4142

方程式 Ax=b の右辺のベクトルを作成します。

b = sum(A,2);

コレスキー分解により A=RTR であるため、この線形方程式は RTR x=b になります。バックスラッシュ演算子を使用して、x について解きます。

x = R\(R'\b)
x = 3×1

    1.0000
    1.0000
    1.0000

行列の上コレスキー分解と下コレスキー分解を計算し、結果を確認します。

関数 gallery を使用して、6 行 6 列のテスト用対称正定値行列を作成します。

A = gallery('lehmer',6);

A の上三角部分を使用してコレスキー因子を計算します。

R = chol(A)
R = 6×6

    1.0000    0.5000    0.3333    0.2500    0.2000    0.1667
         0    0.8660    0.5774    0.4330    0.3464    0.2887
         0         0    0.7454    0.5590    0.4472    0.3727
         0         0         0    0.6614    0.5292    0.4410
         0         0         0         0    0.6000    0.5000
         0         0         0         0         0    0.5528

上三角因子が丸め誤差の範囲内で R'*R - A = 0 を満たしていることを確認します。

norm(R'*R - A)
ans = 2.8779e-16

次に、'lower' オプションを指定し、A の下三角部分を使用してコレスキー因子を計算します。

L = chol(A,'lower')
L = 6×6

    1.0000         0         0         0         0         0
    0.5000    0.8660         0         0         0         0
    0.3333    0.5774    0.7454         0         0         0
    0.2500    0.4330    0.5590    0.6614         0         0
    0.2000    0.3464    0.4472    0.5292    0.6000         0
    0.1667    0.2887    0.3727    0.4410    0.5000    0.5528

下三角因子が丸め誤差の範囲内で L*L' - A = 0 を満たしていることを確認します。

norm(L*L' - A)
ans = 3.2914e-16

chol に 2 つの出力を指定して使用し、入力行列が対称正定値でない場合にエラーを非表示にします。

5 行 5 列の二項係数の行列を作成します。この行列は対称正定値であるため、最後の要素から 1 を減算し、確実に不定値にします。

A = pascal(5);
A(end) = A(end) - 1
A = 5×5

     1     1     1     1     1
     1     2     3     4     5
     1     3     6    10    15
     1     4    10    20    35
     1     5    15    35    69

A のコレスキー因子を計算します。2 つの出力を指定して、A が対称正定値でない場合にエラーが生成されないようにします。

[R,flag] = chol(A)
R = 4×4

     1     1     1     1
     0     1     2     3
     0     0     1     3
     0     0     0     1

flag = 5

flag は非ゼロであるため、因数分解に失敗したピボットのインデックスが出力されます。chol は、変更された行列の部分を検出して失敗するまでの q = flag-1 = 4 個の行と列を正しく計算できます。

R'*RA(1:q,1:q) を満たす 4 行 4 列を返すことを確認します。

q = flag-1;
R'*R
ans = 4×4

     1     1     1     1
     1     2     3     4
     1     3     6    10
     1     4    10    20

A(1:q,1:q)
ans = 4×4

     1     1     1     1
     1     2     3     4
     1     3     6    10
     1     4    10    20

スパース行列のコレスキー因子を計算し、置換出力を使用して非ゼロのさらに少ないコレスキー因子を作成します。

west0479 行列に基づくスパース正定値行列を作成します。

load west0479
A = west0479;
S = A'*A;

行列のコレスキー因子を 2 通りの方法で計算します。まず 2 つの出力を指定してから、行と列の並べ替えを有効にするために 3 つの出力を指定します。

[R,flag] = chol(S);
[RP,flagP,P] = chol(S);

各計算で flag = 0 であるかを調べて、計算が成功していることを確認します。

if ~flag && ~flagP
    disp('Factorizations successful.')
else
    disp('Factorizations failed.')
end
Factorizations successful.

chol(S) の非ゼロの数を、並べ替えた行列 chol(P'*S*P) と比較します。ベスト プラクティスは、スパース行列に chol の 3 出力構文を使用することです。これは、行と列の並べ替えにより、コレスキー因子の非ゼロの数が大幅に減少するためです。

subplot(1,2,1)
spy(R)
title('Nonzeros in chol(S)')
subplot(1,2,2)
spy(RP)
title('Nonzeros in chol(P''*S*P)')

Figure contains 2 axes objects. axes object 1 with title Nonzeros in chol(S), xlabel nz = 59887 contains a line object which displays its values using only markers. axes object 2 with title Nonzeros in chol(P'*S*P), xlabel nz = 7637 contains a line object which displays its values using only markers.

chol'vector' オプションを使用して、置換情報を行列ではなくベクトルとして返します。

スパース有限要素行列を作成します。

S = gallery('wathen',10,10);
spy(S)

Figure contains an axes object. The axes object with xlabel nz = 4861 contains a line object which displays its values using only markers.

この行列のコレスキー因子を計算します。'vector' オプションを指定して置換ベクトル p を返します。

[R,flag,p] = chol(S,'vector');

flag = 0 であることを確認します。これは計算が成功したことを示します。

if ~flag
    disp('Factorization successful.')
else
    disp('Factorization failed.')
end
Factorization successful.

丸め誤差の範囲内で S(p,p) = R'*R であることを確認します。

norm(S(p,p) - R'*R,'fro')
ans = 2.1039e-13

入力引数

すべて折りたたむ

入力行列。引数 A は非スパース ストレージまたはスパース ストレージを使用できますが、正方かつ対称正定値でなければなりません。

chol では、A が実数行列の場合は対称、複素行列の場合はエルミートであると仮定します。chol は、triangle の値に応じて、A の上三角部分または下三角部分のみを使用して計算を実行します。

データ型: single | double
複素数のサポート: あり

スパース入力行列。S は正方かつ対称正定値でなければなりません。

chol では、S が実数行列の場合は対称、複素行列の場合はエルミートであると仮定します。chol は、triangle の値に応じて、S の上三角部分または下三角部分のみを使用して計算を実行します。

データ型: double
複素数のサポート: あり

入力行列の三角因子。'upper' または 'lower' として指定します。このオプションを使用して、chol が因子分解の計算に入力行列の上三角因子または下三角因子を使用するように指定します。chol では、入力行列が実数行列の場合は対称、複素行列の場合はエルミートであると仮定します。chol は、上三角部分または下三角部分のみを使用して計算を実行します。

'lower' オプションの使用は、'upper' オプションと入力行列の転置を使用して chol を呼び出してから、出力 R を転置することと等価です。

例: R = chol(A,'lower')

置換出力の形状。'matrix' または 'vector' として指定します。このフラグは、置換出力 P が置換行列または置換ベクトルのいずれで返されるかを制御します。

  • flag = 0 の場合、S は対称正定値であり、P'*S*P = R'*R (P が行列の場合) または S(p,p) = R'*R (p がベクトルの場合) です。

  • flag がゼロでない場合、S は対称正定値ではありません。R はサイズが qn 列の上三角行列で、q = flag-1 です。R'*R の最初の qq 列の L 型領域は、P'*S*P (P が行列の場合) または S(p,p) (p がベクトルの場合) の L 型領域と一致します。

  • 'lower' オプションを指定した場合、R は下三角行列であり、前述の恒等式の R'*RR*R' に置き換えることができます。

P'*S*P (P が行列の場合) または S(p,p) (p がベクトルの場合) のコレスキー因子は、S のコレスキー因子よりスパース性が高くなる傾向があります。

例: [R,flag,p] = chol(S,'vector')

出力引数

すべて折りたたむ

コレスキー因子。行列として返されます。

  • R が上三角の場合、A = R'*R になります。スパース行列について P 出力を指定した場合、outputForm の値に応じて P'*S*P = R'*R または S(p,p) = R'*R になります。

  • R が下三角の場合、A = R*R' になります。スパース行列について P 出力を指定した場合、outputForm の値に応じて P'*S*P = R*R' または S(p,p) = R*R' になります。

  • flag がゼロでない場合、R には部分的な結果のみが含まれます。flag は因子分解が失敗したピボット位置を示し、R には部分的に完了した因子分解が含まれます。

対称正定値フラグ。スカラーとして返されます。

  • flag = 0 の場合、入力行列は対称正定値です。R は、R'*R = A となる上三角行列です。

  • A が対称正定値でない場合、flag は因子分解に失敗したピボット位置を示す正の整数であり、MATLAB® はエラーを生成しません。R は、R'*R = A(1:q,1:q) となる、サイズが q = flag-1 の上三角行列です。

  • A がスパースの場合、R はサイズが qn 列の上三角行列であり、R'*R の最初の q 行と最初の q 列からなる L 型領域が A または S の対応部分と一致します。

  • 'lower' オプションを指定した場合、R は下三角行列であり、前述の恒等式の R'*RR*R' に置き換えることができます。

スパース行列の置換。outputForm の値に応じて、行列またはベクトルとして返されます。この出力が満たす恒等式については、outputForm を参照してください。

この置換行列は、amd により計算された近似最小次数の並べ替えに基づいています。ただし、chol はパフォーマンス向上のため順序をわずかに変更する場合があるため、この事前並べ替えは amd により直接得られるものとは異なることがあります。

詳細

すべて折りたたむ

対称正定値行列

"対称正定値行列" とは、固有値がすべて正である対称行列です。

任意の実可逆行列 A について、積 B = A'*A を使用して対称正定値行列を作成することができます。コレスキー分解は、任意の対称正定値行列 B は積 R'*R に因数分解できるとしてこの式を逆にしたものです。

"対称半正定値" 行列は同様の方法で定義されますが、固有値はすべて正またはゼロでなければならない点が異なります。

数値計算の文脈で、正定値行列と半正定値行列の境界はあいまいです。固有値が厳密にゼロになることはほとんどありませんが、数値的にゼロになることはあります (マシン精度の桁で)。この理由から、chol はある半正定値行列を因数分解することができても、固有値が非常に類似している他の行列で失敗することがあります。

ヒント

参照

[1] 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.

[2] Chen, Yanqing, Timothy A. Davis, William W. Hager, and Sivasankaran Rajamanickam. “Algorithm 887: CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate.” ACM Transactions on Mathematical Software 35, no. 3 (October 2008): 1–14. https://doi.org/10.1145/1391989.1391995.

拡張機能

バージョン履歴

R2006a より前に導入

参考

| | |

トピック