行列の分解
行列の行列積への分解
例
編集
数値解析において、異なる分解が効率的な行列アルゴリズムを実装するために用いられる。
例えば、線型方程式系︵連立一次方程式︶Ax = bを解くとき、行列 AはLU分解により分解できる。LU分解は行列を下三角行列 Lと上三角行列 Uの積に分解する。系 L(Ux) = bと Ux= L−1b は、もとの系 Ax= bと比べて解くのに必要な加法や乗法が少ないが、浮動小数点のような不正確な計算ではかなりの桁数を必要とし得る。
同様に、QR分解は Aを直交行列 Qと上三角行列 Rの積 QRとして表す。系 Q(Rx) = bは Rx= tQb= cによって解かれ、系 Rx= cは '後退代入' によって解かれる。必要な加法と乗法の回数はLU分解のときの約2倍だが、QR分解は数値的に安定なため不正確な計算においてより多くの桁数が必要とならない。
線型方程式系を解くことと関係する分解
編集LU分解
編集詳細は「LU分解」を参照
●適用‥正方行列 A
●分解‥A = LU,、ただし Lは下三角行列で Uは上三角行列
●関連‥LDU分解は A= LDU である、ただし Lは下三角行列で対角線に1が並び、U は上三角行列で対角線に1が並び、D は対角行列である．
●関連‥LUP分解は A= LUP である、ただし Lは下三角行列で、U は上三角行列で、P は置換行列である．
●存在‥ LUP 分解は任意の正方行列 Aに対して存在する。P が単位行列のとき、LUP分解はLU分解となる。LU分解が存在すればLDU分解も存在する[1]。
●コメント‥LUP 分解とLU分解は n× nの線型方程式系 Ax= bを解く際に有用である。これらの分解はガウスの消去法の過程を行列の形にまとめたものである。行列 Pはガウスの消去法の過程で行われる任意の行の交換を表す。ガウスの消去法で行の交換なしに行階段形になれば P= Iであり、したがってLU分解は存在する。
LUリダクション
編集詳細は「LUリダクション」を参照
ブロックLU分解
編集詳細は「ブロックLU分解」を参照
階数因数分解
編集詳細は「階数因数分解」を参照
●適用‥階数 rの m× n行列 A
●分解‥A = CF、ただし Cは m× rの full column rank matrix であり、F は r× nの full row rank matrix である。
●コメント‥階数因数分解は Aのムーア・ペンローズ擬逆行列を計算するのに使え[2]、適用して線型系 Ax= bの全ての解を得ることができる。
コレスキー分解
編集詳細は「コレスキー分解」を参照
●適用‥正方，対称，正定値行列 A
●分解‥A = tUU,、ただし Uは上三角行列で対角成分は正
●コメント‥実対称正定値行列のコレスキー分解は一意にできる︵上三角行列Uの対角要素を正にとる︶。
●コメント‥実対称と複素対称にも一応適用ができるが、行列が正則でも分解が存在しない︵破綻する︶可能性がある。
●コメント‥コレスキー分解は複素エルミート行列にも適用できる︵その場合にはUの転置はUのエルミート転置に読み替える︶。必ずしも分解が存在しないが、行列が正定値なら必ず分解できる。
●コメント‥代替はLDL分解であり，平方根を引き出すことを避けられる．
QR分解
編集詳細は「QR分解」を参照
●適用‥m × n行列 A
●分解‥A = QR,、ただし Qは m次直交行列であり，R は m× nの上三角行列である。
●コメント‥QR分解は方程式系 Ax= bを Aの逆行列を求めずに解く別の方法を提供する。Q が直交行列であることは tQQ= Iを意味するので、Ax = bは Rx= tQbと同値であり、後者は Rが三角行列だから解きやすい。
RRQR分解
編集詳細は「RRQR分解」を参照
補間分解
編集詳細は「補間分解」を参照
固有値や関連概念に基づく分解
編集固有値分解
編集詳細は「固有値分解」を参照
●スペクトル分解とも呼ばれる。
●適用‥相異なる固有ベクトルを持つ正方行列 A︵固有値は同じものがあってもよい︶。
●分解‥A = VDV−1、 ただし Dは Aの固有値からなる対角行列で，V の行は対応する Aの固有ベクトル。
●存在‥n × n行列 Aはつねに︵重複を込めて︶ n個の固有値を持ち、それらを並べて n× nの対角行列 Dと対応する零でない行の行列 Vを作ることができ、固有値方程式 AV= VDを満たす。n 個の固有ベクトルが相異なるとき、V は可逆であり、分解 A= VDV−1 ができる[3]。
●コメント‥固有ベクトルの長さが 1であるように正規化することがいつでもできる。A が実対称行列であれば、V はいつでも可逆であり正規化された列を持つようにできる。すると等式 VtV= Iが成り立つ、なぜならば各固有ベクトルは互いに直交するからである。したがって、分解は A= VDtVとなる。
●コメント‥n 個の相異なる固有値をもつという条件は十分ではあるが必要ではない。必要十分条件は各固有値の幾何学的重複度がその代数的重複度に等しいことである。
●コメント‥固有分解は線型常微分方程式系あるいは線型差分方程式系の解の理解に有用である。例えば，初期条件 x0 = cから始まる差分方程式 xk+ 1 = Axkは xk= kAcによって解かれ、これは xk= VDkV−1c に同値であり、ここで Vと Dは Aの固有ベクトルと固有値から作られる行列である。D は対角行列だから、冪 Dkは単に各対角成分を k乗するだけである。A は普通対角でないから Aを k乗するよりもはるかに容易である。
ジョルダン分解
編集- 適用：正方行列 A
- コメント：ジョルダン標準形は固有分解を固有値に重複があり対角化できない場合に一般化し、ジョルダン・シュヴァレー分解はこれを基底を選ばずに行う。
シューア分解
編集詳細は「シューア分解」を参照
●適用‥正方行列 A
●コメント‥この分解には2つのバージョンがある．複素シューア分解と実シューア分解である．複素行列は必ず複素シューア分解を持つ．
●分解︵複素バージョン︶‥A = UTU∗、 ただし Uがユニタリ行列で、U∗ は Uの共役転置で、T は Aの固有値を対角線に持つ複素シューア標準形と呼ばれる上三角行列である。
●分解︵実バージョン︶‥A = VStV、ただし A, V, Sは実数のみからなる行列である。V は直交行列で，tV は Vの転置で、S は実シューア標準形と呼ばれるブロック上三角行列である。S の対角にあるブロックのサイズは 1 × 1︵実固有値を表す︶かまたは 2 × 2︵複素共役な固有値の対から導かれる︶である。
QZ分解
編集詳細は「QZ分解」を参照
●別名‥一般シューア分解
●適用‥正方行列 Aと B
●コメント‥この分解には2つのバージョンがある‥複素と実．
●分解︵複素バージョン︶‥
および 
, ただし Qと Zはユニタリ行列で，∗ は共役転置を表し，S と Tは上三角行列である．
●コメント‥複素QZ分解において，A の対角成分と対応する Tの対角成分の比 λi = Sii/Tii は一般化固有値問題 Av= λBv︵ただし λ は未知のスカラーで vは未知の非零ベクトル︶を解く一般化固有値である．
●分解︵実バージョン︶‥A = QStZおよび B= QTtZ, ただし A, B, Q, Z, S, Tは実数のみを成分とする行列である．この場合 Qと Zは直交行列であり．t は転置を表し，S と Tはブロック上三角行列である． Sと Tの対角ブロックのサイズは 1 × 1 か 2 × 2 である．
および , ただし Qと Zはユニタリ行列で，∗ は共役転置を表し，S と Tは上三角行列である．
●コメント‥複素QZ分解において，A の対角成分と対応する Tの対角成分の比 λi = Sii/Tii は一般化固有値問題 Av= λBv︵ただし λ は未知のスカラーで vは未知の非零ベクトル︶を解く一般化固有値である．
●分解︵実バージョン︶‥A = QStZおよび B= QTtZ, ただし A, B, Q, Z, S, Tは実数のみを成分とする行列である．この場合 Qと Zは直交行列であり．t は転置を表し，S と Tはブロック上三角行列である． Sと Tの対角ブロックのサイズは 1 × 1 か 2 × 2 である．
高木分解
編集
●適用‥正方，複素，対称行列 A.
●分解‥A = VDtV, ただし Dは実非負対角行列で，V はユニタリ行列である．tV は Vの転置を表す．
●コメント‥D の対角成分は AA∗ の固有値の非負の平方根である．
●コメント‥V は Aが実のときでさえ複素かもしれない．
●コメント‥これは固有分解︵上述︶の特別な場合ではない．
特異値分解
編集詳細は「特異値分解」を参照
- 適用：m × n 行列 A.
- 分解：A = UDV∗, ただし D は非負対角行列で，U と V はユニタリ行列で，V∗ は V の共役転置を表す（V が実数のみからなるときは単に転置である）．
- コメント：D の対角成分は A の特異値と呼ばれる．
- コメント：上の固有分解と同様，特異値分解は行列の乗法がスカラー乗法と同じになる基底の方向を見つけることと関わるが，考える行列が正方行列でなくてもよいからより広い一般性を持つ．
他の分解
編集極分解
編集詳細は「極分解」を参照
代数的極分解
編集- 適用：正方，複素，非特異行列 A[4].
- 分解：A = QS, ただし Q は複素直交行列で S は複素対称行列．
- コメント：この分解の存在は AtA が tAA に相似であることと同値である[5]．
Sinkhorn 標準形
編集詳細は「Sinkhorn の定理」を参照
- 適用：正方実行列 A で真に正の成分からなるもの．
- 分解：A = D1SD2, ただし S は 二重確率行列で D1 と D2 は真に正の成分からなる実対角行列である．
一般化
編集この節の加筆が望まれています。 |
quasimatrix︵準行列︶および cmatrix あるいは continuous matrix︵連続行列︶に対して SVD, QR, LU, コレスキー分解の類似がある[8]。‘quasimatrix’は，行列のように、長方形の体系で、元は添え字付けられているが、1つの離散的な添え字が連続的な添え字に置き換えられる。同様に，‘cmatrix’は両方の添え字が連続である。cmatrix の例として，積分作用素の核を考えることができる。
これらの分解は Fredholm (1903), Hilbert (1904), Schmidt (1907) による初期の研究に基づいている。これら独創的な論文の説明と英訳は Stewart (2011) を参照
関連項目
編集脚注
編集- ^ Simon & Blume 1994, Chapter 7.
- ^ Piziak, R.; Odell, P. L. (1 June 1999). “Full Rank Factorization of Matrices”. Mathematics Magazine 72 (3): 193. doi:10.2307/2690882.
- ^ Meyer 2000, p. 514
- ^ Choudhury & Horn 1987, pp. 219–225
- ^ Horn & merino 1995, pp. 43–92
- ^ a b Zhang, Fuzhen (30 June 2014). “A matrix decomposition and its applications”. Linear and Multilinear Algebra: 1–10. doi:10.1080/03081087.2014.933219.
- ^ Drury, S.W. (November 2013). “Fischer determinantal inequalities and Highamʼs Conjecture”. Linear Algebra and its Applications 439 (10): 3129–3133. doi:10.1016/j.laa.2013.08.031.
- ^ Townsend & Trefethen 2015
参考文献
編集- Choudhury, Dipa; Horn, Roger A. (April 1987). “A Complex Orthogonal-Symmetric Analog of the Polar Decomposition”. SIAM Journal on Algebraic Discrete Methods 8 (2). doi:10.1137/0608019.
- Fredholm, I. (1903), “Sur une classe d’´equations fonctionnelles” (French), Acta Mathematica 27: 365–390, doi:10.1007/bf02421317
- Hilbert, D. (1904), “Grundzüge einer allgemeinen Theorie der linearen Integralgleichungen” (German), Nachr. Königl. Ges. Gött 1904: 49–91
- Horn, Roger A.; Merino, Dennis I. (January 1995). “Contragredient equivalence: A canonical form and some applications”. Linear Algebra and its Applications 214. doi:10.1016/0024-3795(93)00056-6.
- Meyer, C. D. (2000), Matrix Analysis and Applied Linear Algebra, SIAM, ISBN 978-0-89871-454-8
- Schmidt, E. (1907), “Zur Theorie der linearen und nichtlinearen Integralgleichungen. I Teil. Entwicklung willkürlichen Funktionen nach System vorgeschriebener” (German), Mathematische Annalen 63: 433–476, doi:10.1007/bf01449770
- Simon, C.; Blume, L. (1994). Mathematics for Economists. Norton. ISBN 0-393-95733-0
- Stewart, G. W. (2011), Fredholm, Hilbert, Schmidt: three fundamental papers on integral equations 2015年1月6日閲覧。
- Townsend, A.; Trefethen, L. N. (2015), “Continuous analogues of matrix factorizations”, Proc. R. Soc. A 471 (2173), doi:10.1098/rspa.2014.0585
外部リンク
編集- Online Matrix Calculator
- Wolfram Alpha Matrix Decomposition Computation » LU and QR Decomposition
- Springer Encyclopaedia of Mathematics » Matrix factorization
- GraphLab en:GraphLab collaborative filtering library, large scale parallel implementation of matrix decomposition methods (in C++) for multicore.