ドキュメンテーション

最新のリリースでは、このページがまだ翻訳されていません。 このページの最新版は英語でご覧になれます。

cholupdate

コレスキー分解のランク 1 の更新

構文

R1 = cholupdate(R,x)
R1 = cholupdate(R,x,'+')
R1 = cholupdate(R,x,'-')
[R1,p] = cholupdate(R,x,'-')

説明

R1 = cholupdate(R,x) は、R = chol(A)A の元のコレスキー分解である場合、A + x*x' の上三角コレスキー因子を返します。ここで、x は適切な長さの列ベクトルです。cholupdate は、R の対角要素と上三角部分のみを使用します。R の下三角部分は無視されます。

R1 = cholupdate(R,x,'+') は、R1 = cholupdate(R,x) と同じ結果になります。

R1 = cholupdate(R,x,'-') は、A - x*x' のコレスキー因子を返します。R が有効なコレスキー因子ではないか、復旧された (downdated) 行列が正定行列ではないためにコレスキー分解が行われない場合には、エラー メッセージを表示します。

[R1,p] = cholupdate(R,x,'-') は、エラー メッセージを返しません。p0 の場合、R1A - x*x'' のコレスキー因子です。p0 より大きい場合、R1 は元の A のコレスキー因子です。p1 の場合、復旧された行列が正定ではないので、cholupdate は失敗します。p2 の場合、R の上三角部分が有効なコレスキー因子ではないので、cholupdate は失敗します。

A = pascal(4)
A =

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

R = chol(A)
R =

     1     1     1     1
     0     1     2     3
     0     0     1     3
     0     0     0     1
x = [0 0 0 1]';

これは rank(x*x')1 であることから、A に対するランク 1 の更新 (update) と呼ばれます。

A + x*x' 
ans =

     1     1     1     1
     1     2     3     4
     1     3     6    10
     1     4    10    21

R1 = chol(A + x*x') でコレスキー因子を計算する代わりに、cholupdate を使用することができます。

R1 = cholupdate(R,x)
R1 =
    1.0000    1.0000    1.0000    1.0000
         0    1.0000    2.0000    3.0000
         0         0    1.0000    3.0000
         0         0         0    1.4142

以下に、A の最後の要素から 1 を引いて、正定性を壊します (実際には行列を特異にします)。復旧された行列は、以下のようになります。

A - x*x'
ans =
 
     1     1     1     1
     1     2     3     4
     1     3     6    10
     1     4    10    19

cholcholupdate を比較します。

R1 = chol(A-x*x')
Error using chol
Matrix must be positive definite.
R1 = cholupdate(R,x,'-')
Error using cholupdate
Downdated matrix must be positive definite.

しかし、A の最後の要素から 0.5 を引くと正定行列になるため、cholupdate を使用してコレスキー因子を比較することができます。

x = [0 0 0 1/sqrt(2)]';
R1 = cholupdate(R,x,'-') 
R1 =
    1.0000    1.0000    1.0000    1.0000
         0    1.0000    2.0000    3.0000
         0         0    1.0000    3.0000
         0         0         0    0.7071

詳細

すべて折りたたむ

ヒント

cholupdate が機能するのは非スパース行列だけです。

アルゴリズム

cholupdate は、LINPACK のサブルーチン ZCHUDZCHDD のアルゴリズムを使用します。cholupdate が役に立つのは、最初から新規にコレスキー因子を計算するのが O(N3) アルゴリズムであるのに対して、このような方法で既存の因子を簡単に更新するのが O(N2) アルゴリズムであるからです。

参照

[1] Dongarra, J.J., J.R. Bunch, C.B. Moler, and G.W. Stewart, LINPACK Users' Guide, SIAM, Philadelphia, 1979.

参考

|

この情報は役に立ちましたか?