ドキュメンテーション センター

  • 評価版
  • 製品アップデート

このページは前リリースの情報です。該当の英語のページはこのリリースで更新されています。このリリースの英語のドキュメンテーションを参照するには、言語設定を United States に変更してください。

cholinc

スパース不完全コレスキー分解とコレスキー無限分解

    メモ:   cholinc は削除されました。

    • cholinc のほとんどのインスタンスは、ichol で置き換えることができます。cholinc は上三角因子を返しましたが、ichol は既定で下三角因子を返すことに注意してください。

    • 構文 cholinc(X,'inf') を使用するインスタンスはすべて削除してください。これを置き換える構文はありません。

構文

R = cholinc(X,droptol)
R = cholinc(X,options)
R = cholinc(X,'0')
[R,p] = cholinc(X,'0')
R = cholinc(X,'inf')

説明

cholinc は、2 種類の不完全コレスキー分解を出力します。すなわち、棄却許容誤差と 0 レベルの要素充填による分解です。これらの分解は、pcg (前提条件を使った共役勾配法) のような反復手法により解かれる線形方程式の対称正定システムに対する前提条件として有効です。cholinc は、スパース行列に対してのみ機能します。

R = cholinc(X,droptol) は、棄却許容誤差 droptol を使用して、X の不完全コレスキー分解を実行します。

R = cholinc(X,options) では、不完全コレスキー分解で追加オプションを使用できます。options は、最大 3 つのフィールドをもつ構造体です。

droptol

不完全分解の棄却許容誤差

michol

修正不完全コレスキー

rdiag

R の対角上のゼロを置換

設定する必要があるのは計算に関係するフィールドだけです。

droptol は、不完全コレスキー分解の棄却許容誤差として使用される非負のスカラーです。この分解は、不完全 LU 分解を使って計算されます。すなわち、ピボットしきい値のオプションを 0 に設定し (対角要素を強制的にピボットさせます)、不完全上三角因子 U の行を列の対角要素の平方根によってスケーリングします。非ゼロ要素 U(i,j)droptol*norm(X(:,j)) を超えることはないので (luinc 参照)、非ゼロ要素 R(i,j) も、ローカルな棄却許容誤差 droptol*norm(X(:,j))/R(i,i) を超えることはありません。

droptol = 0 に設定すると、完全コレスキー分解になります。これが既定の設定です。

michol は、修正不完全コレスキー分解を意味します。この値は、0 (修正なし、既定の設定) あるいは 1 (修正) のいずれかです。これは X の修正不完全 LU分解を実行し、返された上三角因子を前述のようにスケーリングします。

rdiag は、0 あるいは 1 のいずれかです。これが 1 の場合は、特異因子となることを避けるため、上三角因子 R の対角上のゼロ要素は、ローカルな棄却許容誤差の平方根で置き換えられます。既定の設定は 0 です。

R = cholinc(X,'0') は、非スパース化を行わず実数の対称正定スパース行列の不完全コレスキー因子を出力します。上三角行列 R は、triu(X) とスパース性のパターンが同じです。ただし、簡約のために X が非ゼロとなる一部の位置で、R はゼロとなる場合があります。X の下三角行列は、上三角行列の転置と想定されます。X の正定性は、求めるスパース性を備えた因子の存在を保証するわけではないことに注意してください。分解できなければ、エラー メッセージが表示されます。分解に成功すると、R'*R はスパース性のパターンに関して X と一致します。

[R,p] = cholinc(X,'0') は 2 つの出力引数があり、エラー メッセージを表示しません。R が存在する場合、p0 です。R が存在しない場合、p は正の整数で、Rq = p-1 であるサイズ qn 列の上三角行列になります。この後者の場合、R のスパース性パターンは Xqn 列の上三角行列と同じになります。 R'*R は、最初の q および最初の q 列スパース性パターンに関して X と一致します。

R = cholinc(X,'inf') は、コレスキー無限分解を出力します。この分解はコレスキー分解に基づくもので、さらに実数の半正定行列も扱います。これは内点法で生じるシステムの解を求めるために有効です。通常のコレスキー分解でゼロピボットが発生する場合、コレスキー無限分解の対角は Inf に設定され、その行の残りは 0 に設定されます。これは関連する線形方程式システムにおける解ベクトルの対応する要素を強制的に 0 にします。実際問題として、X は半正定と想定されるので、負のピボットであっても Inf の値に置き換えられます。

例 1

対称正定行列 S から始めます。

S = delsq(numgrid('C',15));

S は、numgrid('C',15) によって生成されるグリッド上の負の 2 次元 5 点離散ラプラシアン (Laplacian) です。

コレスキー分解とレベル 0 の不完全コレスキー分解を計算し、要素の充填を比較します。対角要素をゼロにすることで S を特異にし、レベル 0 の (部分的) 不完全コレスキー分解を計算します。

C = chol(S);
R0 = cholinc(S,'0');
S2 = S; S2(101,101) = 0;
[R,p] = cholinc(S2,'0');

完全コレスキー因子では S の対角帯に要素が充填されますが、不完全コレスキー因子では充填されません。特異行列 S2 の不完全分解は p = 101 行で停止し、100 行 139 列の部分的な分解という結果になります。

D1 = (R0'*R0).*spones(S)-S;
D2 = (R'*R).*spones(S2)-S2;

D1 には eps の次数の要素があり、R0'*R0 がスパース性のパターンに関して S と一致することを示しています。D2 では最初の 100 行と最初の 100 列、D2(1:100,:) および D2(:,1:100) に、eps の次数の要素があります。

例 2

下に示す最初のサブブロットは、棄却許容誤差 0 の不完全コレスキー因子である cholinc(S,0) が、S のコレスキー因子と同じであることを示しています。図のように、棄却許容誤差が大きくなると、不完全分解のスパース性が増加します。

残念ながら、棄却許容誤差と norm(R'*R-S,1)/norm(S,1) を比較した以下の図のプロットが示すように、スパース性が高い分解の近似は貧弱です。

例 3

ヒルベルト行列は、(i,j) 要素が 1/(i+j-1) で表される行列で、理論的に正定です。

H3 = hilb(3)
H3 =
    1.0000    0.5000    0.3333
    0.5000    0.3333    0.2500
    0.3333    0.2500    0.2000
R3 = chol(H3)
R3 =
    1.0000    0.5000    0.3333
         0    0.2887    0.2887
         0         0    0.0745

実際問題としてコレスキー分解は、行列が大きくなるほど成功率が低下します。

H20 = sparse(hilb(20));
[R,p] = chol(H20);
p =
    14

この hilb(20) の場合、コレスキー分解は、14 行目の計算で数値的にゼロピボットとなるため失敗します。コレスキー無限分解を使用すれば、このエラーを避けることができます。ゼロピボットが発生すると、cholinc は主対角上に Inf を設定し、行の残りはゼロに設定して計算を続けます。

Rinf = cholinc(H20,'inf');

この場合、以降のピポットもすべて非常に小さく、上三角分解の結果、以下の状態になります。

full(Rinf(14:end,14:end))
ans =
   Inf     0     0     0     0     0     0
     0   Inf     0     0     0     0     0
     0     0   Inf     0     0     0     0
     0     0     0   Inf     0     0     0
     0     0     0     0   Inf     0     0
     0     0     0     0     0   Inf     0
     0     0     0     0     0     0   Inf

制限

cholinc が機能するのは正方スパース行列だけです。cholinc(X,'0')cholinc(X,'inf') の場合、X は実数でなければなりません。

詳細

すべて展開する

ヒント

不完全分解は、大規模なスパース線形方程式システムを解くための前提条件として有効です。上三角因子の対角上に 1 つの 0 があると、行列は特異になります。棄却許容誤差をもつ不完全分解は、上三角行列の対角上にゼロがある場合、警告メッセージを表示します。同様に、rdiag オプションを使用して対角上のゼロを置き換えた場合も、この問題による警告がなくなるだけで、解くことにはなりません。前提条件は特異でない場合もありますが、おそらく有効ではなく、警告メッセージが表示されます。

コレスキー無限分解は、内点法の中で使用することを意図したものです。それ以外での使用はお勧めしません。

アルゴリズム

R = cholinc(X,droptol) は、[L,U] = luinc(X,options) から得られます。ここで、options.droptol = droptol および options.thresh = 0 です。上三角部分 U の行は、その行の対角要素の平方根でスケーリングされ、そのスケール係数が R になります。

R = cholinc(X,options) は、rdiag オプションが udiag オプションに変わり、milu オプションが michol オプションの値を取ることを除けば、同様の方法で出力されます。

R = cholinc(X,'0') は、コレスキー分解の変形である "KJI" を基本にしています。X の上三角部分の非ゼロである位置に対してのみ要素が更新されます。

R = cholinc(X,'inf') は、Zhang [2] のアルゴリズムを基本にしています。

参照

[1] Saad, Yousef, Iterative Methods for Sparse Linear Systems, PWS Publishing Company, 1996. Chapter 10, “Preconditioning Techniques”

[2] Zhang, Yin, Solving Large-Scale Linear Programs by Interior-Point Methods Under the MATLAB Environment, Department of Mathematics and Statistics, University of Maryland Baltimore County, Technical Report TR96-01

参考

| | |

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