このページの翻訳は最新ではありません。ここをクリックして,英語の最新版を参照してください。
分解
はじめに
この節で説明する3つの行列分解では,対角要素の上部または下部の要素がすべてゼロである“三角”行列を使います。三角行列を含む線形方程式は,“前進代入“または“後退代入“のいずれかを使うと,簡単かつ高速に解くことができます。
コレスキー分解
コレスキー分解は,対称行列を三角行列と転置行列との積として表現します。
一个= R或
ここでRは上三角行列です。
対称行列すべてがこの方法で分解できるわけではなく,適用できる行列は正定値と呼ばれています。これは,の対角要素がすべて正で,非対角要素が”大きすぎない”ことを意味しています。パスカル行列を例に行列分解を行います。この章全体を通して行列の例一个は3行3列のパスカル行列を扱いますが,ここでは一時的に6行6列の行列を作成します。
A = 1 1 1 1 1 1 12 3 4 56 1 3 6 10 15 21 1 4 10 20 35 56 15 15 35 70 126 1 6 21 56 126 252
一个の要素は二項係数になります。各要素は上と左の要素の和になります。コレスキー分解は次のようになります。
R = 1 1 1 1 10 1 2 3 4 5 0 0 1 3 6 10 0 0 0 1 4 10 0 0 0 0 1 5 0 0 0
結果の要素は再び二項係数になります。‘* Rが一个に等しいということは,一个が二項係数の積の和を含んでいることを示しています。
コレスキー分解を使用すると,次の線形方程式
Ax = b
を次の式で置き換えることができます。
R 'Rx = b
バックスラッシュ演算子は三角行列を認識するため,次のように高速に解くことができます。
x = R \ (R \ b)
一个がn行n列の行列の場合,胆固醇(A)の計算量はO (n3.)になりますが,バックスラッシュの計算量はO (n2)です。
陆分解
陆分解またはガウスの消去法は任意の正方行列を,下三角行列と上三角行列の置換行列の積として表します。
一个=,
ここでLは対角要素に1をもつ下三角行列を並べ替えたもので,Uは上三角行列を並べ替えたものです。
並べ替えは理論上および計算上の面で必要になります。行列
は行を並べ替えないと,三角行列の積として表現することはできません。ただし,行列は次のようになります。
は三角行列の積として表すことができます。εが小さい場合、因子の要素は大きくなり誤差も大きくなります。よってこの並べ替えは厳密には必要ありませんが、推奨されます。部分ピボットは L の要素の大きさを 1 以下に制限し、U の要素が A の要素より大きくならないようにします。
たとえば,
[L,U] = lu(B) L = 1.0000 00 0.3750 0.5441 1.0000 0.5000 1.0000 0 U = 8.0000 1.0000 6.0000 0 8.5000 -1.0000 00 5.2941
一个陆を分解すると,線形方程式
A * x =
は次の式で高速に解くことができます。
x = U \ (L \ b)
行列式と逆行列は,次の関係を使って陆分解から計算されます。
依据(A) =侦破(L) *侦破(U)
と
发票(A) =发票(U) *发票(左)
依据(A) = prod(诊断接头(U))を使用して行列式を計算することもできますが,行列式の符号が逆になる場合があります。
QR分解
“直”交行列または直交性の列がある行列とは,各列が単位長さをもち相互に直交関係になる実数行列です。问が直交であれば,
问TQ =我
ここで,我は単位行列です。
最も簡単な直交行列は2次元の座標回転変換です。
複素数行列に対応する概念は”“ユニタリです。直交ユニタリ行列は長さと角度が保存され誤差が大きくならないため,数値計算に効果的です。
直交分解またはQR分解は任意の方形行列を,直交行列またはユニタリ行列と上三角行列の積で表現します。列の置換も含まれます。
一个= QR
または
美联社= QR,
ここでQは直交行列またはユニタリ行列,Rは上三角行列,Pは置換行列です。
QR分解には,フルサイズとエコノミーサイズ,列置換をもつものともたないものの4種類あります。
過決定線形システムは,列よりも多くの行をもつ方形行列を含んでいます。すなわち,m行n列でm > nです。フルサイズのQR分解は,m行m列の正方直交行列问とm行n列の上三角行列Rを生成します。
C =画廊(uniformdata, 4 [5], 0);(Q, R) = qr (C) Q = 0.6191 0.1406 -0.1899 -0.5058 0.5522 0.1506 0.4084 0.5034 0.5974 0.4475 0.3954 -0.5564 0.6869 -0.1478 -0.2008 0.3167 0.6676 0.1351 -0.1729 -0.6370 0.5808 -0.2410 -0.4695 0.5792 -0.2207 R = 1.5346 1.0663 1.2010 1.4036 0.7245 0.3474 -0.0126 0 0 0.9320 0.6596 0.6648 0 0 0 0 0 0 0
多くの場合,Qの最後のm - n列はRの下部にゼロを乗算することになるため必要ありません。したがってエコノミーサイズのQR分解は,直交要素をもつm行n列の方形行列问と,正方のn行n列の上三角行列Rを生成します。この5行4列の例ではあまり大きな影響はありませんが,非常に大きい方形行列の場合は,時間とメモリが節約されるため数値計算ではこの手法が非常に効果的になります。
[Q,R] = qr(C,0) Q = 0.6191 0.1406 -0.1899 -0.5058 0.1506 0.4084 0.5034 0.5974 0.3954 -0.5564 0.6869 -0.1478 0.3167 0.6676 0.1351 -0.1729 0.5808 -0.2410 -0.4695 0.5792 R = 1.5346 1.0663 1.2010 1.4036 0 0.7245 0.3474 -0.0126 0 0 0.9320 0.6596 0 0 0 0.6648
陆分解とは異なり,QR分解はピボットや置換は必要ありません。ただし3番目の出力引数を設定すると,オプションの列置換が出力され,特異性やランク落ちを調べる場合に便利です。分解の各ステップでは、分解していない残りの行列の列の中で最も大きなノルムをもつ列がそのステップでの基底として使われます。この計算方法により R の対角要素を小さい順に並べることができ、要素間の関係性を調べることによって各列の間に存在する線形依存性を明らかにすることができます。この簡単な例では、Cの2列目は1列目のノルムよりも大きいノルムをもちます。そこで2つの列を交換します。
[Q,R,P] = qr(C) Q = -0.3522 0.8398 -0.4131 -0.7044 -0.5285 -0.4739 -0.6163 0.1241 0.7777 R = -11.3578 -8.2762 0 7.2460 0 0 P = 0 11 0
エコノミーサイズと列の置換を組み合わせると,3番目の出力引数は置換行列ではなく置換ベクトルになります。
[Q,R,p] = qr(C,0) Q = -0.3522 0.8398 -0.7044 -0.5285 -0.6163 0.1241 R = -11.3578 -8.2762 0 7.2460 p = 2
QR分解では過決定の線形方程式を等価な三角行列に変換します。次の式をみてみましょう。
规范(A * x - b)
は以下と等価です。
规范(Q * R * x - b)
直交行列の乗算はユークリッドノルムを保存するため,この式は以下と同じです。
规范(R * x - y)
ここでy =问' * bです。Rの最後の m-n 行はゼロであるため、この式は 2 つに分けられます。
规范(R (1: n, 1: n) * x - y (1: n))
と
规范(y (n + 1: m))
一个がフルランクの場合はxに対して解くことができ,最初の式はゼロになります。次に2番目の式が残差のノルムを指定します。一个がフルランクでない場合は,Rの三角構造から最小二乗問題に対する基本解を計算します。
行列分解のマルチスレッド計算
MATLAB®は多数の線形関数と要素ごとに計算する数値関数のマルチスレッド計算をサポートしています。これらの関数は自動的にマルチスレッドで実行されます。関数や式に対し、複数の CPU を使用して計算を高速化するにはさまざまな条件があります。
関数は同時実行可能な部分へ簡単に分割できる処理を実行します。この分割部分は各処理間で通信をほとんど行わずに実行されるものでなければなりません。すなわちシーケンシャルな処理がほとんどないものを扱います。
データを分割し,複数の実行スレッドを管理する時間を含めても同時実行する価値があるように,データサイズは十分に大きいものを扱います。たとえば配列が数千個以上の要素を含む場合は,ほとんどの関数に対して高速化の効果があります。
処理がメモリに拘束されないものを扱います。すなわち処理時間の大部分がメモリのアクセス時間にならないものを扱います。一般的には,シンプルな処理より複雑な処理をする関数の方が,高速化の効果があります。
参考
関連するトピック
你也可以从以下列表中选择一个网站:
