コレスキー分解｜正定値行列の平方根と正定値性の判定

対称で正定値な行列は、下三角行列とその転置の積に分かれます。

$$A=L{L}^{\top }$$

これをコレスキー分解といいます。$L$ は対角成分がすべて正の下三角行列で、$A$ の平方根にあたるものです。

LU 分解では $L$ と $U$ の 2 つを求めますが、対称性のおかげで片方だけで済みます。計算量も記憶する量も半分になります。

<svg viewBox="0 0 460 200" width="100%" style="max-width:460px;display:block;margin:0 auto">
	<rect x="30" y="40" width="100" height="100" fill="#1b81e0" fill-opacity="0.12" stroke="#c8c8c8" stroke-width="1"></rect>
	<text x="80" y="95" font-size="15" fill="#1f1f1f" text-anchor="middle">A</text>
	<text x="80" y="30" font-size="11" fill="#9a9a9a" text-anchor="middle">対称・正定値</text>
	<text x="150" y="97" font-size="15" fill="#9a9a9a" text-anchor="middle">=</text>
	<polygon points="175,40 175,140 275,140" fill="#1b81e0" fill-opacity="0.12"></polygon>
	<rect x="175" y="40" width="100" height="100" fill="none" stroke="#c8c8c8" stroke-width="1"></rect>
	<line x1="175" y1="40" x2="275" y2="140" stroke="#9a9a9a" stroke-width="1" stroke-dasharray="3 3"></line>
	<text x="205" y="123" font-size="15" fill="#1b81e0" text-anchor="middle">L</text>
	<text x="225" y="30" font-size="11" fill="#9a9a9a" text-anchor="middle">下三角（対角は正）</text>
	<text x="295" y="97" font-size="15" fill="#9a9a9a" text-anchor="middle">×</text>
	<polygon points="320,40 420,40 420,140" fill="#1b81e0" fill-opacity="0.12"></polygon>
	<rect x="320" y="40" width="100" height="100" fill="none" stroke="#c8c8c8" stroke-width="1"></rect>
	<line x1="320" y1="40" x2="420" y2="140" stroke="#9a9a9a" stroke-width="1" stroke-dasharray="3 3"></line>
	<text x="390" y="65" font-size="15" fill="#1b81e0" text-anchor="middle">L</text>
	<text x="400" y="58" font-size="10" fill="#1b81e0">T</text>
	<text x="370" y="30" font-size="11" fill="#9a9a9a" text-anchor="middle">その転置</text>
	<text x="230" y="180" font-size="11" fill="#9a9a9a" text-anchor="middle">求めるのは L だけで、もう一方は転置するだけです</text>
</svg>

コレスキー分解とは

対称行列 $A$ に対して、対角成分が正である下三角行列 $L$ を見つけて $A=L{L}^{\top }$ と書くことをコレスキー分解といいます。

複素数まで広げるなら、エルミート行列に対して $A=L{L}^{\ast }$ と書きます。転置のかわりに共役転置を使うだけで、話の筋は変わりません。

数の世界の平方根と同じ位置にあります。正の数 $a$ が $a=(\sqrt{a}{)}^2$ と書けるように、正定値行列は $L{L}^{\top }$ と書けます。

正定値であることが前提

$A$ が正定値であるとは、$0$ でないすべてのベクトル $x$ について $x^{\top }Ax>0$ が成り立つことをいいます。

この仮定は外せません。$A=L{L}^{\top }$ と書けたとすると、二次形式は $x^{\top }L{L}^{\top }x=\Vert L^{\top }x{\Vert }^2$ となり、必ず $0$ 以上になるからです。

$L$ が正則なら $L^{\top }x=0$ となるのは $x=0$ のときだけで、値は正になります。逆に正定値なら分解が存在することも示せます。

成分は順に決まる

$A=L{L}^{\top }$ を成分ごとに書き下すと、左上から順に $L$ が決まっていきます。対角成分は次の式です。

$${\ell }_{jj}=\sqrt{a_{jj}-\sum _{k<j}{\ell }_{jk}^2}$$

対角より下の成分は、すでに求めた値を使って割り算で出ます。

$${\ell }_{ij}=\frac{1}{{\ell }_{jj}}\left(a_{ij}-\sum _{k<j}{\ell }_{ik}{\ell }_{jk}\right)(i>j)$$

未知数が 1 つずつ増える形なので、連立方程式を解く必要はありません。左上から順に埋めるだけです。

<svg viewBox="0 0 460 210" width="100%" style="max-width:460px;display:block;margin:0 auto">
	<text x="230" y="22" font-size="11" fill="#9a9a9a" text-anchor="middle">左上から順に、下三角の成分が 1 つずつ決まります</text>
	<rect x="150" y="40" width="160" height="140" fill="none" stroke="#c8c8c8" stroke-width="1"></rect>
	<rect x="150" y="40" width="53" height="47" fill="#1b81e0" fill-opacity="0.18"></rect>
	<rect x="150" y="87" width="53" height="46" fill="#1b81e0" fill-opacity="0.14"></rect>
	<rect x="203" y="87" width="53" height="46" fill="#1b81e0" fill-opacity="0.14"></rect>
	<rect x="150" y="133" width="53" height="47" fill="#1b81e0" fill-opacity="0.1"></rect>
	<rect x="203" y="133" width="53" height="47" fill="#1b81e0" fill-opacity="0.1"></rect>
	<rect x="256" y="133" width="54" height="47" fill="#1b81e0" fill-opacity="0.1"></rect>
	<text x="176" y="70" font-size="13" fill="#1f1f1f" text-anchor="middle">1</text>
	<text x="176" y="116" font-size="13" fill="#1f1f1f" text-anchor="middle">2</text>
	<text x="229" y="116" font-size="13" fill="#1f1f1f" text-anchor="middle">3</text>
	<text x="176" y="162" font-size="13" fill="#1f1f1f" text-anchor="middle">4</text>
	<text x="229" y="162" font-size="13" fill="#1f1f1f" text-anchor="middle">5</text>
	<text x="283" y="162" font-size="13" fill="#1f1f1f" text-anchor="middle">6</text>
	<text x="229" y="70" font-size="13" fill="#9a9a9a" text-anchor="middle">0</text>
	<text x="283" y="70" font-size="13" fill="#9a9a9a" text-anchor="middle">0</text>
	<text x="283" y="116" font-size="13" fill="#9a9a9a" text-anchor="middle">0</text>
	<text x="230" y="200" font-size="11" fill="#9a9a9a" text-anchor="middle">対角に来るたびに平方根を 1 回とります</text>
</svg>

例：2 次の行列で手順をなぞる

小さい行列で流れを見ます。

$$A=\left(\begin{array}{cc}4& 2\\ 2& 10\end{array}\right)$$

まず ${\ell }_{11}=\sqrt{4}=2$ です。第 1 列の残りは、対角で割って ${\ell }_{21}=2/2=1$ になります。

対角に戻ると、その行ですでに求めた成分の 2 乗を引いてから平方根を取ります。${\ell }_{22}=\sqrt{10-1^2}=3$ です。

$$L=\left(\begin{array}{cc}2& 0\\ 1& 3\end{array}\right)$$

$L{L}^{\top }$ の $(2,2)$ 成分は $1^2+3^2=10$ で、もとの行列に戻ります。

例：3 次の行列を分解する

次の対称行列を分解します。

$$A=\left(\begin{array}{ccc}4& 12& -16\\ 12& 37& -43\\ -16& -43& 98\end{array}\right)$$

第 1 列から始めます。${\ell }_{11}=\sqrt{4}=2$、${\ell }_{21}=12/2=6$、${\ell }_{31}=-16/2=-8$ です。

第 2 列に移ります。${\ell }_{22}=\sqrt{37-6^2}=1$、${\ell }_{32}=(-43-(-8)\cdot 6)/1=5$ になります。

最後に ${\ell }_{33}=\sqrt{98-(-8{)}^2-5^2}=\sqrt{9}=3$ です。

$$L=\left(\begin{array}{ccc}2& 0& 0\\ 6& 1& 0\\ -8& 5& 3\end{array}\right)$$

$L{L}^{\top }$ を計算すると、もとの $A$ に戻ります。平方根の中身が $4$、$1$、$9$ とすべて正だったことにも注目してください。

対角を正に取れば一通りに決まる

対角成分を正に取るという約束をすれば、分解は一通りに決まります。上の手順で選択の余地がなかったことが、そのまま証明になっています。

約束を外せば自由が残ります。$L$ の第 $j$ 列全体の符号を反転しても $L{L}^{\top }$ は変わらないからです。

正定値なら平方根の中身が必ず正になり、途中で止まることもありません。この事実の証明には、部分行列も正定値であることを使います。

二次形式が平方和になる

分解ができると、二次形式が平方の和として書けます。

$$x^{\top }Ax=\Vert L^{\top }x{\Vert }^2=\sum _i{\left(\sum _{j\ge i}{\ell }_{ji}{x}_j\right)}^2$$

これは平方完成そのものです。$L$ の成分が、平方完成で出てくる係数に対応します。

正定値性が目に見える形になるのが利点です。二次形式が平方の和である以上、値は $0$ 以上で、$0$ になるのは $L^{\top }x=0$ のときだけです。

例：二次形式を平方完成する

さきほどの 3 次の $A$ で書き下します。二次形式を成分で展開すると、次の式になります。

$$x^{\top }Ax=4x_1^2+37x_2^2+98x_3^2+24x_1{x}_2-32x_1{x}_3-86x_2{x}_3$$

$L$ の列を係数として読むと、3 つの平方の和にまとまります。

$$x^{\top }Ax=(2x_1+6x_2-8x_3{)}^2+(x_2+5x_3{)}^2+(3x_3{)}^2$$

括弧の中に並ぶ数は、$L$ の第 1 列、第 2 列、第 3 列そのものです。$x=(1,1,1)$ を入れると、どちらの式も $45$ になります。

手で平方完成を進めても、同じ式に行き着きます。コレスキー分解は、その手順を行列の形で書き留めたものにほかなりません。

平方根を使わない LDL 分解

平方根を避けたいときは、対角を別に取り出します。

$$A=LD{L}^{\top }$$

ここで $L$ は対角がすべて $1$ の下三角行列、$D$ は対角行列です。成分は次の式で決まります。

$$d_j=a_{jj}-\sum _{k<j}{\ell }_{jk}^2{d}_k$$

$${\ell }_{ij}=\frac{1}{d_j}\left(a_{ij}-\sum _{k<j}{\ell }_{ik}{\ell }_{jk}{d}_k\right)$$

平方根が出てこないので、有理数の範囲で計算が閉じます。$D$ の成分が正なら、平方根を $L$ に配ってコレスキー分解に戻せます。

例：同じ行列を LDL 分解で書く

さきほどの $L$ の各列を、対角成分で割ります。

$$L=\left(\begin{array}{ccc}1& 0& 0\\ 3& 1& 0\\ -4& 5& 1\end{array}\right),D=\left(\begin{array}{ccc}4& 0& 0\\ 0& 1& 0\\ 0& 0& 9\end{array}\right)$$

$D$ の対角は、コレスキー分解の対角を 2 乗したものです。$2^2=4$、$1^2=1$、$3^2=9$ と対応しています。

整数だけで書けている点に注目してください。もとの行列が整数でも、コレスキー分解には平方根が現れることがあります。LDL 分解ならそれを避けられます。

例：平方根が残る行列で 2 つの分解を比べる

次の行列は、差分方程式や格子の問題でよく現れる形です。

$$A=\left(\begin{array}{ccc}2& -1& 0\\ -1& 2& -1\\ 0& -1& 2\end{array}\right)$$

コレスキー分解を進めると、最初の段階から平方根が出てきます。${\ell }_{11}=\sqrt{2}$、${\ell }_{21}=-1/\sqrt{2}$、${\ell }_{31}=0$ です。

続けると ${\ell }_{22}=\sqrt{2-1/2}=\sqrt{3/2}$、${\ell }_{32}=-\sqrt{2/3}$、${\ell }_{33}=\sqrt{4/3}$ になります。手で扱うには重い形です。

同じ行列を LDL 分解で書くと、有理数だけで収まります。

$$L=\left(\begin{array}{ccc}1& 0& 0\\ -\frac{1}{2}& 1& 0\\ 0& -\frac{2}{3}& 1\end{array}\right),D=\left(\begin{array}{ccc}2& 0& 0\\ 0& \frac{3}{2}& 0\\ 0& 0& \frac{4}{3}\end{array}\right)$$

$D$ の対角はすべて正なので、この行列は正定値です。行列式は $2\cdot \frac{3}{2}\cdot \frac{4}{3}=4$ になります。

LU 分解の対称版として見る

$A$ が対称なら、LDU 分解の $U$ は $L$ の転置になります。つまり $A=LD{L}^{\top }$ は LDU 分解の対称版です。

消去の手順もまったく同じです。違うのは、対称性のおかげで下半分だけ計算すれば足りることです。

コレスキー分解は、そこからさらに $D$ の平方根を $L$ に吸収させた形にあたります。3 つの書き方は同じ計算の言い換えです。

ピボット選択が要らず、計算量も半分

正定値性から、平方根の中身が必ず正になります。$0$ で割る心配も、$0$ に近い値で割る心配もありません。

だから行の入れ替えが要りません。LU 分解では安定性のために毎回ピボットを選びますが、こちらでは順番どおりに進めるだけです。

演算量は $n^3/3$ 程度で、LU 分解のおよそ半分です。記憶する量も、下三角だけなので半分で済みます。

連立方程式を解く

$Ax=b$ に $A=L{L}^{\top }$ を入れると、三角の方程式が 2 つ並びます。

まず $Ly=b$ を上から解き、次に $L^{\top }x=y$ を下から解きます。LU 分解と同じ形ですが、使う行列が 1 つだけです。

例：連立方程式を解く

さきほどの $A$ に対して、右辺を $b=(0,6,39)$ とします。

$Ly=b$ を上から解きます。$2y_1=0$ から $y_1=0$、$6y_1+y_2=6$ から $y_2=6$ です。

第 3 式は $-8y_1+5y_2+3y_3=39$ なので、$30+3y_3=39$ から $y_3=3$ になります。

$L^{\top }x=y$ を下から解きます。$3x_3=3$ から $x_3=1$、$x_2+5x_3=6$ から $x_2=1$、$2x_1+6x_2-8x_3=0$ から $x_1=1$ です。

解は $x=(1,1,1)$ で、$Ax$ を計算すると $(0,6,39)$ に戻ります。

行列式は対角の 2 乗の積

$\det A=\det L\cdot \det L^{\top }=(\det L{)}^2$ です。三角行列の行列式は対角の積なので、次の形になります。

$$\det A={\left({\ell }_{11}{\ell }_{22}\cdots {\ell }_{nn}\right)}^2$$

さきほどの例なら $(2\cdot 1\cdot 3{)}^2=36$ です。LDL 分解の $D$ の対角を掛けても $4\cdot 1\cdot 9=36$ で一致します。

正定値行列の行列式が正になることも、この式から出ます。平方になっているので負にはなりません。

正定値かどうかの判定に使える

分解の手順そのものが判定になります。平方根の中身が負になった時点で、その行列は正定値ではありません。

首座小行列式をすべて計算する方法や、固有値を求める方法より手軽です。分解を試みて、最後まで進めるかどうかを見るだけで済みます。

数値計算のライブラリが正定値性を確かめるときも、たいていこの方法を使います。判定と分解が同時に終わるので無駄がありません。

例：正定値でない行列では途中で止まる

次の対称行列で試します。

$$A=\left(\begin{array}{cc}1& 2\\ 2& 1\end{array}\right)$$

${\ell }_{11}=1$、${\ell }_{21}=2$ までは進みます。ところが次の段階で行き詰まります。

$${\ell }_{22}^2=1-2^2=-3$$

平方根が実数の範囲で取れません。実際この行列の固有値は $3$ と $-1$ で、正定値ではありません。

$x=(1,-1)$ を入れると二次形式が $1-4+1=-2$ になります。負の値を取るので、平方の和には書けないわけです。

半正定値のときは一意でなくなる

$x^{\top }Ax\ge 0$ どまりの半正定値行列でも、分解自体は存在します。ただし対角に $0$ が現れ、一意性が崩れます。

$$A=\left(\begin{array}{cc}0& 0\\ 0& 1\end{array}\right)$$

${\ell }_{11}=0$ になるので、${\ell }_{21}$ を決める割り算ができません。${\ell }_{21}$ をどう選んでも ${\ell }_{11}{\ell }_{21}=0$ は満たされます。

${\ell }_{21}=s$、${\ell }_{22}=\sqrt{1-s^2}$ と置けば、$-1\le s\le 1$ のどれでも $L{L}^{\top }=A$ になります。分解が無数にあるわけです。

実際の計算では、対角の大きい成分を先に持ってくる置換を入れて対処します。階数のぶんだけ正の対角が並ぶ形に整えられます。

応用

統計では、共分散行列から相関のある乱数を作るのに使います。互いに独立な標準正規乱数 $z$ に $L$ を掛けると、$Lz$ の共分散行列が $A$ になります。

最小二乗法の正規方程式にも現れます。係数行列 $A^{\top }A$ は対称で、列が一次独立なら正定値なので、この分解で解けます。

大きな疎行列の反復解法では、途中を切り捨てた不完全コレスキー分解を前処理に使います。厳密な分解でなくても、収束を速める効果があります。

例：共分散行列から相関のある乱数を作る

相関係数が $0.6$ の 2 変数を作ります。目標とする共分散行列は次の形です。

$$A=\left(\begin{array}{cc}1& \frac{3}{5}\\ \frac{3}{5}& 1\end{array}\right)$$

分解すると ${\ell }_{11}=1$、${\ell }_{21}=3/5$、${\ell }_{22}=\sqrt{1-9/25}=4/5$ です。

$$L=\left(\begin{array}{cc}1& 0\\ \frac{3}{5}& \frac{4}{5}\end{array}\right)$$

独立な標準正規乱数 $z_1$、$z_2$ に $L$ を掛けると、$x_1=z_1$、$x_2=\frac{3}{5}{z}_1+\frac{4}{5}{z}_2$ が得られます。

$x_2$ の分散は ${\left(\frac{3}{5}\right)}^2+{\left(\frac{4}{5}\right)}^2=1$、$x_1$ との共分散は $3/5$ です。狙いどおりの相関を持つ組ができました。

他の話題とのつながり

ブロックに区切って同じ消去を進めると、右下にシューア補元が現れます。正定値行列のシューア補元もまた正定値になるので、分解が最後まで進むことの説明になります。

スペクトル分解を使えば、対称行列の別の平方根も作れます。固有値の平方根を使う $A^{1/2}$ は対称ですが、コレスキー分解の $L$ は三角です。同じ「平方根」でも形が違います。

正定値性そのものの判定法は正定値行列と半正定値行列の記事に、二次形式の標準形は二次形式と標準形の記事にあります。

よくある誤り

参考文献