行列の分解

行列の行列積への分解

線型代数学という数学の分野において、行列の分解(ぎょうれつのぶんかい、: matrix decomposition, matrix factorization)とは、行列の行列の積への因数分解である.多くの異なった行列の分解があり、それぞれがある問題のために利用される。リー群の分解はこれらのより本質的な視点を与える。

数値解析において、異なる分解が効率的な行列アルゴリズムを実装するために用いられる。

例えば、線型方程式系(連立一次方程式)Ax = b を解くとき、行列 ALU分解により分解できる。LU分解は行列を下三角行列 L上三角行列 U の積に分解する。系 L(Ux) = bUx = L−1b は、もとの系 Ax = b と比べて解くのに必要な加法や乗法が少ないが、浮動小数点のような不正確な計算ではかなりの桁数を必要とし得る。

同様に、QR分解A直交行列 Q と上三角行列 R の積 QR として表す。系 Q(Rx) = bRx = tQb = c によって解かれ、系 Rx = c は '後退代入英語版' によって解かれる。必要な加法と乗法の回数はLU分解のときの約2倍だが、QR分解は数値的に安定英語版なため不正確な計算においてより多くの桁数が必要とならない。

線型方程式系を解くことと関係する分解

編集

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分解

編集

階数因数分解

編集

コレスキー分解

編集
  • 適用:正方,対称正定値行列 A
  • 分解:A = tUU,、ただし U は上三角行列で対角成分は正
  • コメント:実対称正定値行列のコレスキー分解は一意にできる(上三角行列Uの対角要素を正にとる)。
  • コメント:実対称と複素対称にも一応適用ができるが、行列が正則でも分解が存在しない(破綻する)可能性がある。
  • コメント:コレスキー分解は複素エルミート行列にも適用できる(その場合にはUの転置はUのエルミート転置に読み替える)。必ずしも分解が存在しないが、行列が正定値なら必ず分解できる。
  • コメント:代替はLDL分解英語版であり,平方根を引き出すことを避けられる.

QR分解

編集
  • 適用:m × n 行列 A
  • 分解:A = QR,、ただし Qm直交行列であり,Rm × n の上三角行列である。
  • コメント:QR分解は方程式系 Ax = bA逆行列を求めずに解く別の方法を提供する。Q が直交行列であることは tQQ = I を意味するので、Ax = bRx = tQb と同値であり、後者は R が三角行列だから解きやすい。

RRQR分解

編集

補間分解

編集

固有値や関連概念に基づく分解

編集

固有値分解

編集
  • スペクトル分解英語版とも呼ばれる。
  • 適用:相異なる固有ベクトルを持つ正方行列 A(固有値は同じものがあってもよい)。
  • 分解:A = VDV−1、 ただし DA固有値からなる対角行列で,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 = Axkxk = kAc によって解かれ、これは xk = VDkV−1c に同値であり、ここで VDA の固有ベクトルと固有値から作られる行列である。D は対角行列だから、冪 Dk は単に各対角成分を k 乗するだけである。A は普通対角でないから Ak 乗するよりもはるかに容易である。

ジョルダン分解

編集

ジョルダン標準形ジョルダン・シュヴァレー分解英語版

  • 適用:正方行列 A
  • コメント:ジョルダン標準形は固有分解を固有値に重複があり対角化できない場合に一般化し、ジョルダン・シュヴァレー分解はこれを基底を選ばずに行う。

シューア分解

編集
  • 適用:正方行列 A
  • コメント:この分解には2つのバージョンがある.複素シューア分解と実シューア分解である.複素行列は必ず複素シューア分解を持つ.
  • 分解(複素バージョン):A = UTU、 ただし Uユニタリ行列で、UU共役転置で、TA の固有値を対角線に持つ複素シューア標準形と呼ばれる上三角行列である。
  • 分解(実バージョン):A = VStV、ただし A, V, S は実数のみからなる行列である。V は直交行列で,tVV転置で、S は実シューア標準形と呼ばれるブロック上三角行列である。S の対角にあるブロックのサイズは 1 × 1(実固有値を表す)かまたは 2 × 2複素共役な固有値の対から導かれる)である。

QZ分解

編集
  • 別名:一般シューア分解
  • 適用:正方行列 AB
  • コメント:この分解には2つのバージョンがある:複素と実.
  • 分解(複素バージョン):  および  , ただし QZユニタリ行列で, は共役転置を表し,ST は上三角行列である.
  • コメント:複素QZ分解において,A の対角成分と対応する T の対角成分の比 λi = Sii/Tii一般化固有値問題 Av = λBv(ただし λ は未知のスカラーで v は未知の非零ベクトル)を解く一般化固有値である.
  • 分解(実バージョン):A = QStZ および B = QTtZ, ただし A, B, Q, Z, S, T は実数のみを成分とする行列である.この場合 QZ は直交行列であり.t は転置を表し,ST はブロック上三角行列である. ST の対角ブロックのサイズは 1 × 12 × 2 である.

高木分解

編集
  • 適用:正方,複素,対称行列 A.
  • 分解:A = VDtV, ただし D は実非負対角行列で,V はユニタリ行列である.tVV の転置を表す.
  • コメント:D の対角成分は AA の固有値の非負の平方根である.
  • コメント:VA が実のときでさえ複素かもしれない.
  • コメント:これは固有分解(上述)の特別な場合ではない.

特異値分解

編集
  • 適用:m × n 行列 A.
  • 分解:A = UDV, ただし D は非負対角行列で,UV はユニタリ行列で,VV の共役転置を表す(V が実数のみからなるときは単に転置である).
  • コメント:D の対角成分は A特異値と呼ばれる.
  • コメント:上の固有分解と同様,特異値分解は行列の乗法がスカラー乗法と同じになる基底の方向を見つけることと関わるが,考える行列が正方行列でなくてもよいからより広い一般性を持つ.

他の分解

編集

極分解

編集

代数的極分解

編集
  • 適用:正方,複素,非特異行列 A[4].
  • 分解:A = QS, ただし Q は複素直交行列で S は複素対称行列.
  • コメント:この分解の存在は AtAtAA に相似であることと同値である[5]

Sinkhorn 標準形

編集
  • 適用:正方実行列 A で真に正の成分からなるもの.
  • 分解:A = D1SD2, ただし S二重確率行列D1D2 は真に正の成分からなる実対角行列である.

扇形分解[6]

編集
  • 適用:正方,複素行列 A数値域英語版 が扇形   に含まれるもの.
  • 分解:A = CZC, ただし C は可逆複素行列で,Z = diag(e1, …, en) ですべての   [6][7]

一般化

編集

quasimatrix(準行列)および cmatrix あるいは continuous matrix(連続行列)に対して SVD, QR, LU, コレスキー分解の類似がある[8]。‘quasimatrix’は,行列のように、長方形の体系で、元は添え字付けられているが、1つの離散的な添え字が連続的な添え字に置き換えられる。同様に,‘cmatrix’は両方の添え字が連続である。cmatrix の例として,積分作用素の核を考えることができる。

これらの分解は Fredholm (1903), Hilbert (1904), Schmidt (1907) による初期の研究に基づいている。これら独創的な論文の説明と英訳は Stewart (2011) を参照

関連項目

編集

脚注

編集
  1. ^ Simon & Blume 1994, Chapter 7.
  2. ^ Piziak, R.; Odell, P. L. (1 June 1999). “Full Rank Factorization of Matrices”. Mathematics Magazine 72 (3): 193. doi:10.2307/2690882. 
  3. ^ Meyer 2000, p. 514
  4. ^ Choudhury & Horn 1987, pp. 219–225
  5. ^ Horn & merino 1995, pp. 43–92
  6. ^ 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. 
  7. ^ 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. 
  8. ^ 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, http://www.matrixanalysis.com/ 
  • 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, http://www.cs.umd.edu/~stewart/FHS.pdf 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 

外部リンク

編集