decomposition

線形系を解くための行列の分解

説明

decomposition は再利用可能な行列の分解 (LU、LDL、コレスキー、QR など) を作成して、線形系 (Ax = b または xA = b) をより効果的に解くことを可能にします。たとえば、dA = decomposition(A) の計算後に dA\b を呼び出すと、A\b と同じベクトルを返しますが、通常は大幅に速くなります。decomposition オブジェクトは繰り返して解を求める必要のある問題に適しています。これは、係数行列の分解を複数回実行する必要がないためです。

decomposition オブジェクト dA には、元の係数行列 A に使用する同じ演算子の多くを使用できます。

• 複素共役転置 dA'

• 否定 -dA

• c*dA または dA/c を使用する、スカラーとの乗算またはスカラーによる除算。

• x = dA\b を使用する、線形系 Ax = b の求解。

• x = b/dA を使用する、線形系 xA = b の求解。

作成

構文

dA = decomposition(A)

dA = decomposition(A,type)

dA = decomposition(A,type,triangularFlag)

dA = decomposition(___,Name,Value)

説明

dA = decomposition(A) は行列 A の分解を返します。これを使用して線形系をより効率的に解くことができます。分解タイプは、入力行列のプロパティに基づいて自動的に選択されます。

dA = decomposition(A,type) は実行する分解のタイプを指定します。type は 'qr'、'cod'、'lu'、'ldl'、'chol'、'triangular'、'permutedTriangular'、'banded'、'hessenberg'、'diagonal' にすることができます。

dA = decomposition(A,type,triangularFlag) は、A の上三角部分または下三角部分のみを分解に使用することを指定します。triangularFlag には 'upper' または 'lower' を指定できます。この構文の場合、分解タイプは 'ldl'、'chol' または 'triangular' でなければなりません。

dA = decomposition(___,Name,Value) は、前述の任意の構文と 1 つ以上の Name,Value のペアの引数を使用して、追加オプションを指定します。たとえば、dA = decomposition(A,'CheckCondition',false) は、dA\b の解を求めているときに A の条件に基づく警告をスローしないことを指定します。

入力引数

A — 係数行列

行列

係数行列。係数行列は、線形方程式系の左辺に Ax = b として、右辺に xA = b として現れます。

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

type — 分解タイプ

'auto' (既定値) | 'qr' | 'cod' | 'lu' | 'ldl' | 'chol' | 'triangular' | 'permutedTriangular' | 'banded' | 'hessenberg' | 'diagonal'

分解タイプ。以下の表にあるオプションのいずれかを指定します。

これらのオプションは、すべての係数行列で機能します。

値	A の行列の分解	メモ
'auto' (既定)	N/A	係数行列のプロパティに基づく行列の分解タイプの自動選択。分解の選択方法の詳細については、mldivide のアルゴリズム節を参照してください。
'qr'	$$AP=QR$$ Q はユニタリ行列、R は上三角行列、P は置換行列です。	QR 分解では、最小二乗解が得られます。 type が 'qr' の場合、A'\B または B/A を解くことはできません。このような形式の問題には、代わりに 'cod' を使用してください。
'cod'	$$A=QR{Z}^{*}$$ R は上三角行列で、Q と Z はいずれも直交列をもちます。	完全直交分解では、最小ノルムの最小二乗解が得られます。

正方係数行列でも、これらのオプションを使用できます。

値	A の行列の分解	メモ
'lu'	密行列: $$PA=LU$$ L は下三角行列、U は上三角行列、P は置換行列です。 スパース行列: $$P\left(R\backslash A\right)Q=LU$$ P と Q は置換行列で、R は対角スケーリング行列です。
'ldl'	密行列: $$P^{*}AP=LD{L}^{*}$$ L は 1 の対角要素をもつ下三角行列、D は対角行列、P は置換行列です。 スパース行列: $$P^{*}SASP=LD{L}^{*}$$ S はスケーリング行列です。	A は対称でなければなりません。
'chol'	密行列: $$A=L{L}^{*}$$ L は下三角行列です。 スパース行列: $$A=PL{L}^{*}{P}^{*}$$ P は置換行列です。	A は対称正定値でなければなりません。
'triangular'	$$A=T$$ T は三角行列です。	A は三角行列でなければなりません。
'permutedTriangular'	$$A=PT{Q}^{*}$$ T は三角行列、P と Q はいずれも置換行列です。	A は三角行列の置換でなければなりません。
'banded'	$$A=P^{*}LU$$ P は置換行列で、L と U はいずれも帯行列です。	バンド幅の小さい行列に対して最も効果的です。詳細については、bandwidth を参照してください。
'hessenberg'	$$A=P^{*}LU$$ P は置換行列、L は帯行列、U は上三角行列です。	A の 1 番目の下対角要素より下にゼロが含まれなければなりません。
'diagonal'	$$A=D$$ D は対角行列です。	A は対角行列でなければなりません。

triangularFlag — 係数行列の上三角部分または下三角部分のみを使用するためのフラグ

'upper' | 'lower'

係数行列の上三角部分または下三角部分のみを使用するためのフラグ。'upper' または 'lower' のいずれかとして指定します。このオプションは、'triangular'、'chol' および 'ldl' の分解タイプをサポートします。

• 'triangular' — 上三角行列または下三角行列の両方が同じ行列に格納されている場合は、triangularFlag を使用して三角行列を 1 つのみ指定します。

• 'chol' および 'ldl' — triangularFlag を使用してほぼ対称の係数行列の対称化を回避します。

名前と値の引数

引数のオプションのペアを Name1=Value1,...,NameN=ValueN として指定します。ここで Name は引数名で、Value は対応する値です。名前と値の引数は他の引数の後になければなりませんが、ペアの順序は重要ではありません。

R2021a より前では、コンマを使用してそれぞれの名前と値を区切り、Name を引用符で囲みます。

例: dA = decomposition(A,'qr','CheckCondition',false) は A の QR 分解を実行し、係数行列が線形系の求解に使用されるときにその条件に関する警告をオフにします。

一般的なパラメーター

CheckCondition — 係数行列の条件チェックの切り替え

true (既定値) | false

係数行列の条件チェックの切り替え。'CheckCondition' と logical 1 (true) または logical 0 (false) で構成されるコンマ区切りのペアとして指定します。CheckCondition が true で係数行列が悪条件または低いランクである場合、mldivide (\) または mrdivide (/) を使用する線形系の求解で警告が生成されます。

データ型: logical

RankTolerance — ランクの許容誤差

非負のスカラー

ランクの許容誤差。非負のスカラーとして指定します。許容誤差を指定すると、解が係数行列のランダム ノイズの影響を受けにくくなります。

decomposition は A のランクを、QR 分解 [Q,R,p] = qr(A,0) の行列 R において絶対値が tol より大きい対角要素の数として計算します。A のランクが k の場合、A の低ランク近似は、Q の最初の k 列に R の最初の k 行を乗算することで得られます。許容誤差を変更すると、A の低ランク近似に影響します。

メモ

このオプションは、'Type' が 'qr' または 'cod' である場合、または 'Type' が 'auto' でかつ A が方形である場合にのみ適用されます。それ以外の場合、このオプションは無視されます。

スパース行列のパラメーター

BandDensity — バンド密度のしきい値

0.5 (既定値) | スカラー

バンド密度のしきい値。[0 1] の範囲のスカラー値として指定します。'BandDensity' の値は、方程式系の解を求めるときに mldivide (\) または mrdivide (/) でバンド ソルバーを使用するために、スパースのバンド係数行列が満たさなければならない密度を指定します。係数行列のバンド密度が、指定されたバンド密度よりも大きい場合、バンド ソルバーが使用されます。

バンド密度は、(バンドの非ゼロ要素の数) / (バンドの要素の数) で定義されます。値 1.0 は、バンド ソルバーを使用しないことを示します。

LDLPivotTolerance — LDL 分解のピボット許容誤差

0.01 (既定値) | スカラー

LDL 分解のピボット許容誤差。区間 [0 0.5] のスカラー値として指定します。ピボット許容誤差により小さな値を使用すると、因子分解の時間が短くなり、要素数が少なくなる可能性もありますが、因子分解が不安定になる場合もあります。

このピボット許容誤差は、ldl が実スパース行列に使用するものと同じです。

LUPivotTolerance — LU 分解のピボット許容誤差

[0.1 0.001] (既定値) | スカラー | ベクトル

LU 分解のピボット許容誤差。スカラーまたはベクトルとして指定します。許容誤差ベクトルの最初の要素を変更するには、スカラー値を指定します。両方の値を変更するには、2 要素ベクトルを指定します。ピボット許容誤差をより小さな値にすると、LU 因子がよりスパースになる傾向がありますが、解が不正確になる可能性があります。ピボット許容誤差をより大きな値にすると、より正確な解が得られることもありますが、通常は総処理量とメモリ使用量が増加します。

このピボット許容誤差は、lu がスパース行列に使用するものと同じです。

プロパティ

MatrixSize — 係数行列のサイズ

ベクトル

この プロパティ は読み取り専用です。

係数行列のサイズ。2 要素の行ベクトルとして返されます。

データ型: double

Type — 分解タイプ

'qr' | 'cod' | 'lu' | 'ldl' | 'chol' | 'triangular' | 'permutedTriangular' | 'banded' | 'hessenberg' | 'diagonal'

この プロパティ は読み取り専用です。

分解タイプ。'qr'、'cod'、'lu'、'ldl'、'chol'、'triangular'、'permutedTriangular'、'banded'、'hessenberg' または 'diagonal' として返されます。

データ型: char

CheckCondition — 係数行列の条件チェックの切り替え

true (既定値) | false

係数行列の条件チェックの切り替え。logical 1 (true) または logical 0 (false) のいずれかとして指定します。CheckCondition が true で係数行列が悪条件または低いランクである場合、mldivide (\) または mrdivide (/) を使用する線形系の求解で警告が生成されます。

データ型: logical

Datatype — 係数行列のデータ型

'double' | 'single'

この プロパティ は読み取り専用です。

係数行列のデータ型。'double' または 'single' のいずれかとして返されます。

データ型: char

IsConjugateTransposed — 係数行列が複素共役転置であることを示すインジケーター

false (既定値) | true

この プロパティ は読み取り専用です。

係数行列が複素共役転置であることを示すインジケーター。logical 1 (true) または logical 0 (false) のいずれかとして返されます。このインジケーターは、係数行列から作成されたすべての decomposition オブジェクトに対して既定で false です。ただし、dA'\b などの式で decomposition オブジェクトに ctranspose 演算子を使用する場合、この値は true です。その場合、dA' は dA と同じ decomposition オブジェクトですが、IsConjugateTransposed の値は true です。

データ型: logical

IsReal — 係数行列が実数であることを示すインジケーター

true | false

この プロパティ は読み取り専用です。

係数行列が実数であることを示すインジケーター。logical 1 (true) または logical 0 (false) のいずれかとして返されます。値 false は、係数行列に複素数が含まれることを示します。

データ型: logical

IsSparse — 係数行列がスパースであることを示すインジケーター

true | false

この プロパティ は読み取り専用です。

係数行列がスパースであることを示すインジケーター。logical 1 (true) または logical 0 (false) のいずれかとして返されます。

データ型: logical

ScaleFactor — 係数行列の乗法スケール係数

1 (既定値) | スカラー

この プロパティ は読み取り専用です。

係数行列の乗法スケール係数。スカラーとして返されます。既定値 1 は係数行列がスケーリングされていないことを示します。ただし、decomposition オブジェクトをスカラーで乗算または除算すると、ScaleFactor の値は変更されます。たとえば、3*dA は dA と等価の decomposition オブジェクトですが、その ScaleFactor 値は 3 です。

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

オブジェクト関数

decomposition オブジェクトに対して使用できる基本関数と演算子は、線形方程式系の求解に関連しています。分解タイプが 'qr' である場合、A'\B または B/A を解くことはできません。このような形式の問題には、代わりに 'cod' を使用してください。

ctranspose	複素共役転置
mldivide	x に対する線形方程式 Ax = B の求解
mrdivide	x に対する線形方程式 xA = B の求解
isIllConditioned	行列が悪条件かどうかの判別

decomposition オブジェクトの基となる行列の条件数またはランクもチェックできます。異なるアルゴリズムが使用されるため、decomposition オブジェクトに対してこれらの関数を使用した結果は、係数行列に対して同じ関数を直接使用した場合と異なることがあります。

rank	1 入力形式の rank(dA) のみがサポートされています。 分解タイプは 'qr' または 'cod' でなければなりません。 ランクの値は、RankTolerance の選択 (指定した場合) に応じて異なります。
rcond	バックスラッシュ \ が警告を発行するかどうかを決定するために使用するものと同じ条件チェックを実行します。 'qr' と 'cod' を除くすべての分解タイプをサポートします。

例

複数の右辺をもつ線形系の求解

decomposition オブジェクトを使用することで、複数の右辺をもつ $\mathrm{Ax}=\mathit{b}$ の求解の効率がどのように向上するかを示します。

"逆反復法" は、多数の右辺をもつ線形系の解を求める反復固有値アルゴリズムです。これは、対応する固有ベクトルの推定値から始めて、行列の固有値を反復的に計算する方法です。各反復で x = A\x を計算してから、そのノルムで x をスケーリングします。

スパース行列 A とランダムな開始ベクトル x1 および x2 を作成します。

n = 1e3;
rng default % for reproducibility
A = sprandn(n,n,0.2) + speye(n);
x1 = randn(n,1);
x2 = x1;

バックスラッシュを使用して逆反復法アルゴリズムの反復を 100 回適用し、A の固有値を計算します。

tic
for ii=1:100
    x1 = A \ x1;
    x1 = x1 / norm(x1);
end
toc

Elapsed time is 20.774384 seconds.

lambda = x1'*A*x1

lambda = -0.6707

次に、decomposition オブジェクトを使用して同じ問題を解きます。

tic
dA = decomposition(A); 
for ii=1:100
    x2 = dA \ x2;
    x2 = x2 / norm(x2);
end
toc

Elapsed time is 1.007912 seconds.

lambda = x2'*A*x2

lambda = -0.6707

各反復で行列 A を因子分解する必要がないため、アルゴリズムのパフォーマンスは大幅に向上します。また、バックスラッシュ アルゴリズムは for ループの前に A の LU 分解を実行することで改善できますが、decomposition オブジェクトでは、複雑なコードを記述せずに同等なパフォーマンスの改善を実現できます。

分解タイプの選択

分解タイプを選択して、入力行列に基づく既定の自動選択をオーバーライドします。

係数行列を作成し、分解タイプの既定の選択を使用して、その行列を分解します。

A = ones(3);
dA = decomposition(A)

dA = 
  decomposition with properties:

    MatrixSize: [3 3]
          Type: 'lu'

  Show all properties

右辺に 1 のベクトルを使用して、線形系を解きます。

b = ones(3,1);
x = dA\b

Warning: Matrix is singular to working precision.

x = 3×1

   NaN
   NaN
   NaN

既定の 'ldl' メソッドの代わりに 'qr' メソッドを使用する分解タイプを指定します。これにより、バックスラッシュ (\) は NaN のベクトルを返さずに、問題の最小二乗解を求めます。

dA_qr = decomposition(A,'qr')

dA_qr = 
  decomposition with properties:

    MatrixSize: [3 3]
          Type: 'qr'

  Show all properties

x = dA_qr\b

Warning: Rank deficient, rank = 1, tol =  1.153778e-15.

x = 3×1

    1.0000
         0
         0

行列の三角部分の使用

'upper' を指定して、分解で入力行列の上三角部分のみを使用します。

係数行列を作成します。上三角部分のみを使用して、行列の三角分解を作成します。このオプションは、上三角行列と下三角行列の両方が同じ行列に格納されている場合に便利です。

A = randi([0 5],10)

A = 10×10

     4     0     3     4     2     1     4     5     2     0
     5     5     0     0     2     4     1     1     4     0
     0     5     5     1     4     3     3     4     3     3
     5     2     5     0     4     0     4     1     3     4
     3     4     4     0     1     0     5     5     5     5
     0     0     4     4     2     2     5     2     1     0
     1     2     4     4     2     5     3     1     4     3
     3     5     2     1     3     2     0     1     4     2
     5     4     3     5     4     3     0     3     2     0
     5     5     1     0     4     1     1     2     3     2

dA = decomposition(A,'triangular','upper')

dA = 
  decomposition with properties:

    MatrixSize: [10 10]
          Type: 'triangular'

  Show all properties

行列条件の警告をオフにする

'CheckCondition' の名前と値のペアを使用して、decomposition を使用した線形系の求解時に係数行列の条件に基づく警告をオフにします。

悪条件の係数行列を作成します。この行列の最初の 2 列を平均して 3 番目の列を生成します。

A = [1 2 1.5; 3 4 3.5; 5 6 5.5]

A = 3×3

    1.0000    2.0000    1.5000
    3.0000    4.0000    3.5000
    5.0000    6.0000    5.5000

右辺に 1 のベクトルを使用して線形系 $\mathrm{Ax}=\mathit{b}$ を解きます。mldivide は係数行列の条件付けに関する警告を出力します。

b = ones(3,1);
x = A\b

Warning: Matrix is singular to working precision.

x = 3×1

   NaN
   Inf
  -Inf

次に、この行列の decomposition オブジェクトを作成して同じ線形系を解きます。mldivide が係数行列の条件をチェックしないよう、'CheckCondition' を false に指定します。同じ解が返されますが、mldivide は警告メッセージを表示しません。

dA = decomposition(A,'CheckCondition',false);
x = dA\b

x = 3×1

   NaN
   Inf
  -Inf

関数 isIllConditioned を使用して、decomposition オブジェクトが悪条件の行列に基づいているかどうかをチェックします。

tf = isIllConditioned(dA)

tf = logical
   1

参照

[1] Davis, Timothy A. “Algorithm 930: FACTORIZE: An Object-Oriented Linear System Solver for MATLAB.” ACM Transactions on Mathematical Software 39, no. 4 (July 2013): 1–18. https://doi.org/10.1145/2491491.2491498.

拡張機能

スレッドベースの環境

MATLAB® の backgroundPool を使用してバックグラウンドでコードを実行するか、Parallel Computing Toolbox™ の ThreadPool を使用してコードを高速化します。

この関数はスレッドベースの環境を完全にサポートしています。詳細については、スレッドベースの環境での MATLAB 関数の実行を参照してください。

分散配列

Parallel Computing Toolbox™ を使用して、クラスターの結合メモリ上で大きなアレイを分割します。

使用上の注意事項および制限事項:

• A が密の場合、type の値で 'ldl'、'cod'、および 'hessenberg' はサポートされません。

• A がスパースの場合、type の値で 'chol'、'cod'、および 'hessenberg' はサポートされません。

• A がスパースで type が 'lu' の場合、rcond で条件数の逆数を判定できないため、CheckCondition は false でなければなりません。

• A がスパースで rcond(decomposition(A,'lu','CheckCondition',false)) の場合、MATLAB^® は [] を返します。

詳細については、分散配列を使用した MATLAB 関数の実行 (Parallel Computing Toolbox)を参照してください。

バージョン履歴

R2017b で導入

参考

lsqminnorm | mldivide | mrdivide

トピック

• 線形方程式