Cholesky分解

同義語:コレスキー分解Cholesky decompositionCholesky factorization

概要

Cholesky分解(Cholesky decomposition)とは、正定値な Hermite 行列(実数なら対称行列)$A$ を、対角成分が正の下三角行列 $L$ によって $A=LL^*$ と書くことである。分解はただ 1 つに定まり、成分の漸化式が途中で止まらないことと $A$ が正定値であることは同値なので、判定法も兼ねる。手間は LU 分解の半分で行の入れ替えも要らず、連立 1 次方程式、行列式の対数、多変量正規分布の乱数の計算に使う。帯行列では零の並びが保たれるが、疎な行列では並べ方で因子の非零の個数が大きく変わる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 正定値行列, LU分解, 三角行列

有限要素法の剛性行列、最小二乗の正規方程式、共分散行列など、応用に現れる連立 1 次方程式 $Ax=b$ の係数行列は、対称で正定値であることが多い。このとき LU分解 の $A=LU$ の $U$ は $L$ の転置と本質的に同じものなので、$L$ だけを作ればよい。こうして得られる $A=LL^{\top}$ が Cholesky 分解 である。手間は LU 分解の半分で、行の入れ替えが要らず、途中で平方根の中が正でなくなれば $A$ が正定値でないとわかるので、判定法も兼ねる。
この記事では、成分の漸化式が止まらないことと正定値であることが同値であり、そのとき分解はただ 1 つであることを、漸化式を 1 列ずつ追って証明する。続いて演算の回数、成分の上界、零の並びの保存、平方根を使わない LDL 分解を示し、方程式の解法、行列式、正規乱数への使い方を例題で扱う。Schur 補行列による別の証明と、ほかの判定法との同値は 正定値行列 の定理「正定値行列の特徴づけ」にある。

定義と使える条件

以下、$K$ は $\mathbb{R}$ または $\mathbb{C}$ とする。$A\in M_n(K)$ の共役転置を $A^*$ と書く($K=\mathbb{R}$ なら転置)。$A^*=A$ となる行列が Hermite行列 で、実なら対称行列である。Hermite 行列 $A$ が 正定値 であるとは、$0$ でないすべての $x\in K^n$ で $x^*Ax>0$ となることをいう。左上の $k$ 次の行列を $A_k$ と書く。$\|x\|:=\sqrt{x^*x}$ である。

Cholesky 分解

Hermite 行列 $A\in M_n(K)$ を、対角成分がすべて正の実数である下三角行列 $L\in M_n(K)$ によって
$$ A=LL^* $$
と書くことを $A$ の Cholesky 分解(Cholesky decomposition)といい、$L$ を Cholesky 因子 という。

$R:=L^*$ とおけば $A=R^*R$($R$ は対角成分が正の上三角行列)であり、文献によってはこの形で書く(Axl24 7.63)。

Cholesky の漸化式

Hermite 行列 $A=(a_{ij})$ について、$j=1,\dots,n$ の順に
$$ d_j:=a_{jj}-\sum_{k< j}\lvert\ell_{jk}\rvert^2,\qquad\ell_{jj}:=\sqrt{d_j},\qquad\ell_{ij}:=\frac1{\ell_{jj}}\Bigl(a_{ij}-\sum_{k< j}\ell_{ik}\overline{\ell_{jk}}\Bigr)\quad(i>j) $$
を計算する。$d_j\le0$ となったら第 $j$ 列で 止まる という。$d_1,\dots,d_n$ がすべて正なら、下三角行列 $L=(\ell_{ij})$($i< j$ で $\ell_{ij}=0$)が得られる。$d_j$ を第 $j$ 段の ピボット という。

$a_{jj}$ は Hermite 行列の対角成分なので実数であり、$d_j$ も実数である。
使える条件をまとめる。

  1. 存在と一意性(thm-chol-main):$A$ が Hermite 行列で正定値であること。これは分解があることと同値である。
  2. 半正定値な行列:存在も一意性も成り立たない場合がある(節「使える条件と反例」)。
  3. 正定値でない正則な Hermite 行列:首座小行列式が $0$ でなければ、平方根を使わない LDL 分解が使える(prop-chol-ldl)。
  4. 丸めのある計算:条件数が計算機精度の逆数に近いと、正定値でも漸化式が止まることがある(rem-chol-rounding)。

公式の表

演算の回数は実行列での主要項である。

計算公式使える条件演算の回数根拠
分解def-chol-recurrence$A$ が正定値$\frac13n^3$thm-chol-main、prop-chol-flops
$Ax=b$$Ly=b$(前進代入)、$L^*x=y$(後退代入)$A$ が正定値右辺 1 本 $2n^2$prop-chol-flops
首座小行列式$\det A_k=\prod_{j\le k}d_j$第 $k$ 列まで止まらない分解に含まれるprop-chol-minors
$\log\det A$$2\sum_j\log\ell_{jj}$$A$ が正定値分解+$n$ 回の対数prop-chol-minors
$x^*A^{-1}x$$\Vert L^{-1}x\Vert^2$$A$ が正定値前進代入 $n^2$ex-chol-gauss
正規乱数$X=\mu+LZ$$\Sigma=LL^{\top}$ が正定値、$Z$ は標準正規積 $n^2$ex-chol-gauss
成分の上界$\lvert\ell_{ij}\rvert\le\sqrt{a_{ii}}$$A$ が正定値—prop-chol-bound
条件数$\kappa_2(L)^2=\kappa_2(A)$$A$ が正定値—prop-chol-bound
帯行列正定値な $A$ の $L$ の帯幅も $p$$\lvert i-j\rvert>p$ で $a_{ij}=0$$np^2$prop-chol-zero
LDL 分解$A=L_1DL_1^*$Hermite、首座小行列式が $0$ でない$\frac13n^3$prop-chol-ldl

主定理と証明

存在と一意性

Cholesky 分解の存在と一意性

$A\in M_n(K)$ を Hermite 行列とする。次は同値である。

  1. $A$ は正定値である。
  2. 漸化式(def-chol-recurrence)は止まらない。
  3. $A$ は Cholesky 分解をもつ。
    このとき Cholesky 分解はただ 1 つで、その因子は漸化式の出力 $L$ である。さらに、漸化式が第 $j$ 列で止まるなら、$x^*Ax=d_j\le0$ となる $0$ でない $x$ が、第 $j-1$ 列までの $L$ から後退代入で得られる。
成分を比べ、ピボットを 2 次形式の値として書く

下三角行列 $L$ について、積の成分は $i\ge j$ で
$$ (LL^*)_{ij}=\sum_{k\le j}\ell_{ik}\overline{\ell_{jk}} $$
である。この式を $(\ast)$ と呼ぶ。
3 ⇒ 2 と一意性。 $A=LL^*$ を Cholesky 分解とする。$j$ についての帰納法で、$L$ の第 $j$ 列が漸化式の値に等しいことを示す。第 $j-1$ 列までが等しいとする。$(\ast)$ で $i=j$ とすると $\ell_{jj}^2=a_{jj}-\sum_{k< j}\lvert\ell_{jk}\rvert^2=d_j$ であり、$\ell_{jj}>0$ なので $d_j>0$、$\ell_{jj}=\sqrt{d_j}$ である。$i>j$ とすると $a_{ij}=\sum_{k< j}\ell_{ik}\overline{\ell_{jk}}+\ell_{ij}\ell_{jj}$ なので、$\ell_{ij}$ は漸化式の値である。よって漸化式は止まらず、因子はその出力に限る。
2 ⇒ 3。 漸化式の式は、出力 $L$ が $i\ge j$ で $(\ast)$ の左辺 $=a_{ij}$ を満たすことを意味する。$LL^*$ も $A$ も Hermite 行列なので、$i< j$ の成分も等しく、$A=LL^*$ である。
3 ⇒ 1。 $L$ は対角成分が $0$ でない三角行列なので正則である。$x\ne0$ なら $L^*x\ne0$ であり、$x^*Ax=\|L^*x\|^2>0$ である。
1 ⇒ 2 と最後の主張。 第 $j-1$ 列まで止まらずに進んだとする($j=1$ なら $d_1=a_{11}=e_1^*Ae_1$ である)。$j\ge2$ のとき、$L$ の左上の $j-1$ 次の部分を $L'$、第 $j$ 行の $\ell_{j1},\dots,\ell_{j,j-1}$ の複素共役を並べた縦ベクトルを $u$ とし、$c:=(a_{1j},\dots,a_{j-1,j})^{\top}$ とおく。第 $j$ 行の $\ell_{jk}$($k< j$)も第 $k$ 列を計算したときに定まっている。$(\ast)$ の左辺 $=a_{ij}$ が第 $j-1$ 列まで成り立つので、$A_{j-1}=L'L'^*$ であり、$a_{jk}=\sum_{m\le k}\ell_{jm}\overline{\ell_{km}}$ の複素共役をとると $c=L'u$ である。また $d_j=a_{jj}-\|u\|^2$ である。
$L'^*$ は正則なので、後退代入で $L'^*z=u$ となる $z$ が定まる。$x:=(-z^{\top},1,0,\dots,0)^{\top}\ne0$ とおく。$A_{j-1}z=L'L'^*z=L'u=c$、$c^*z=u^*L'^*z=\|u\|^2$ なので、
$$ A_j\begin{pmatrix}-z\\1\end{pmatrix}=\begin{pmatrix}A_{j-1}&c\\c^*&a_{jj}\end{pmatrix}\begin{pmatrix}-z\\1\end{pmatrix}=\begin{pmatrix}0\\d_j\end{pmatrix} $$
である。よって $x^*Ax=d_j$ である。$A$ が正定値なら $d_j>0$ であり、漸化式は第 $j$ 列でも止まらない。$d_j\le0$ で止まるなら、この $x$ が最後の主張の $x$ である。$\square$

ピボット $d_j$ は、第 $j$ 変数を $1$ に固定し、第 $1$〜$j-1$ 変数を動かして最も小さくしたときの 2 次形式の値である(最小は上の $x$ でとる)。漸化式が止まれば、この $x$ が正定値でないことの証拠になる。

ピボットと首座小行列式

$A$ を Hermite 行列とし、漸化式が第 $j-1$ 列まで止まらないとする($j\ge1$)。$\det A_0:=1$ とおくと
$$ \det A_j=\det A_{j-1}\cdot d_j,\qquad\det A_j=\prod_{k\le j}d_k $$
である。とくに $A$ が正定値であることと、すべての首座小行列式が正であることは同値であり、このとき $\det A=\prod_j\ell_{jj}^2$、$\log\det A=2\sum_j\log\ell_{jj}$ である。

3 つの行列の積に分ける

要点:prf-chol-main の記号で、$A_j$ を三角行列と $\operatorname{diag}(I,d_j)$ の積に分ける。

詳しい証明を開く

$j=1$ は $d_1=a_{11}$ である。$j\ge2$ なら、$A_{j-1}=L'L'^*$、$c=L'u$、$a_{jj}=\|u\|^2+d_j$ から $A_j=\begin{pmatrix}L'&0\\u^*&1\end{pmatrix}\begin{pmatrix}I&0\\0&d_j\end{pmatrix}\begin{pmatrix}L'^*&u\\0&1\end{pmatrix}$ である。行列式をとると $\det A_j=\lvert\det L'\rvert^2d_j=\det A_{j-1}\cdot d_j$ である。この式は $d_j\le0$ でも成り立つ。帰納法で積の形を得る。

同値について。$A$ が正定値なら、thm-chol-main によりすべての $d_j>0$ なので $\det A_j>0$ である。逆にすべての $\det A_j>0$ なら、$j$ についての帰納法で $d_j=\det A_j/\det A_{j-1}>0$ となり漸化式は止まらないので、thm-chol-main により正定値である。$\square$

この同値は Sylvester の判定法である(正定値行列 の定理「正定値行列の特徴づけ」の 3)。

演算の回数と成分の大きさ

加減乗除 1 回を 1 回の演算と数え、平方根は別に数える(LU分解 の命題「分解と代入の演算回数」と同じ数え方)。

Cholesky 分解の演算回数

正定値な対称行列 $A\in M_n(\mathbb{R})$ の分解に要する演算は、平方根 $n$ 回のほかに
$$ \frac{n^3-n}3+\frac{n(n-1)}2=\frac13n^3+\frac12n^2-\frac56n $$
回である。分解ができていれば、右辺 1 本について、前進代入と後退代入はそれぞれ $n^2$ 回の演算である。

列ごとに数える

要点:第 $j$ 列では $d_j$ に $2(j-1)$ 回、下の $n-j$ 個の成分に各 $2(j-1)+1$ 回の演算を使う。

詳しい証明を開く

$d_j$ は乗法と減法が各 $j-1$ 回である。$\ell_{ij}$ は乗法と減法が各 $j-1$ 回と除法 1 回である。第 $j$ 列の合計は $2(j-1)(n-j+1)+(n-j)$ 回である。$\sum_{j=1}^n2(j-1)(n-j+1)=2\sum_{i=0}^{n-1}i(n-i)=\frac{n^3-n}3$、$\sum_{j=1}^n(n-j)=\frac{n(n-1)}2$ である。前進代入の第 $i$ 段は乗法と減法が各 $i-1$ 回と除法 1 回で、和は $n^2$ である。後退代入も同じである。$\square$

主要項 $\frac13n^3$ は LU 分解の $\frac23n^3$ の半分である(BV04 §C.3.2、p. 669)。$n=3$ では $11$ 回である。

成分の上界と条件数

$A$ を正定値行列、$L$ をその Cholesky 因子とする。

  1. $\sum_{k\le i}\lvert\ell_{ik}\rvert^2=a_{ii}$ であり、とくに $\lvert\ell_{ij}\rvert\le\sqrt{a_{ii}}$ である。
  2. $\kappa_2(L)^2=\kappa_2(A)$ である。ここで $\kappa_2$ は Euclid ノルムの条件数である。
対角成分と 2 次形式を見る

要点:1 は $(\ast)$ の $i=j$、2 は $x^*Ax=\|L^*x\|^2$ である。

詳しい証明を開く

1. prf-chol-main の $(\ast)$ で $i=j$ とする。

2. $\kappa_2(M)=\max_{\|x\|=1}\|Mx\|\big/\min_{\|x\|=1}\|Mx\|$ であり、$\kappa_2(L^*)=\kappa_2(L)$ である。$\|L^*x\|^2=x^*Ax$ の最大値・最小値は $A$ の最大・最小の固有値 $\lambda_{\max},\lambda_{\min}$ である。$A$ は正定値なので $\kappa_2(A)=\lambda_{\max}/\lambda_{\min}$ である。$\square$

1 により、ピボット選択をしなくても $L$ の成分の絶対値は $\max_i\sqrt{a_{ii}}$ を超えない。LU 分解では部分ピボット選択をしても途中の成分が $2^{n-1}$ 倍まで増えうる(LU分解 の定理「部分ピボット選択での増大率の上界」)のと対照的である。

零の並びの保存

左の零は保たれる

$A$ を正定値行列、$L$ をその Cholesky 因子とする。

  1. $i>j$ で $a_{i1}=\cdots=a_{ij}=0$ なら、$\ell_{i1}=\cdots=\ell_{ij}=0$ である。
  2. $\lvert i-j\rvert>p$ で $a_{ij}=0$ なら、$i-j>p$ で $\ell_{ij}=0$ である。このとき分解の演算は $n(p^2+2p)$ 回以下で、代入は 1 回 $n(2p+1)$ 回以下である。
漸化式の和が消える
  1. $j$ についての帰納法。$\ell_{i1}=\cdots=\ell_{i,j-1}=0$ なら、漸化式の和の項はすべて $0$ で、$\ell_{ij}=a_{ij}/\ell_{jj}=0$ である。
  2. $i-j>p$ なら $k\le j$ で $i-k>p$ なので $a_{ik}=0$ であり、1 が使える。演算について:第 $j$ 列の第 $j+t$ 行($0\le t\le p$)の和の項は高々 $p-t$ 個なので、乗法と減法の合計は列ごとに高々 $\sum_{t=0}^p2(p-t)=p(p+1)$ 回、除法は高々 $p$ 回である。代入の各段は高々 $2p+1$ 回である。$\square$

平方根を使わない LDL 分解

LDL 分解

$A\in M_n(K)$ を正則な Hermite 行列とし、首座小行列式 $\Delta_k:=\det A_k$($\Delta_0:=1$)がすべて $0$ でないとする。対角成分がすべて $1$ の下三角行列 $L_1$ と実の対角行列 $D=\operatorname{diag}(\delta_1,\dots,\delta_n)$ で
$$ A=L_1DL_1^* $$
となるものがただ 1 組あり、$\delta_k=\Delta_k/\Delta_{k-1}$ である。$A$ が正定値であることと、すべての $\delta_k$ が正であることは同値で、このとき $L=L_1D^{1/2}$ が Cholesky 因子である。

LU 分解の一意性を転置と比べる

要点:$A=L_1DV$ と書いて $A=A^*$ を使うと、LU 分解の一意性から $V=L_1^*$、$D^*=D$ となる。

詳しい証明を開く

三角行列 の定理「LU 分解の存在と一意性」により $A=L_1U$($L_1$ は単位下三角、$U$ は上三角)がただ 1 組あり、$u_{kk}=\Delta_k/\Delta_{k-1}$ である。同じ記事の定理「正則な三角行列」の 3 により $U=DV$($D$ は対角行列、$V$ は単位上三角行列)と書ける。$A^*=A$ から $L_1(DV)=V^*(D^*L_1^*)$ であり、両辺とも単位下三角行列と上三角行列の積なので、一意性により $V^*=L_1$、$DV=D^*L_1^*$ である。よって $DL_1^*=D^*L_1^*$、すなわち $D=D^*$ で、$D$ は実である。逆に $A=L_1DL_1^*$ の形の分解は $U:=DL_1^*$ とすれば LU 分解なので、一意性が従う。

$y:=L_1^*x$ は $K^n$ の全単射で $x^*Ax=y^*Dy=\sum_k\delta_k\lvert y_k\rvert^2$ なので、$A$ が正定値であることとすべての $\delta_k>0$ は同値である。このとき $L:=L_1D^{1/2}$ は対角成分が正の下三角行列で $LL^*=A$ である。$\square$

$D$ の正負の個数は $A$ の正負の固有値の個数に等しい($A$ と $D$ は合同なので、Sylvester の慣性法則による)。正則な $A$ の首座小行列式に $0$ があると分解はない(分解があれば $\Delta_k=\delta_1\cdots\delta_k$ で、$\Delta_n\ne0$ からどれも $0$ でない。たとえば $\begin{pmatrix}0&1\\1&0\end{pmatrix}$ では $a_{21}=\ell_{21}\delta_1=0$ となって合わない)。このような行列も含めて扱うには、置換と $2\times2$ のブロックを許す $PLDL^{\top}P^{\top}$ の形を使う(BV04 §C.3.3、pp. 671–672)。

計算の手順

Cholesky 分解で $Ax=b$ を解く($A$ は下三角の部分だけを使う)

  1. $j=1,\dots,n$ について、$d_j$ を計算する(def-chol-recurrence)。
  2. $d_j\le0$ なら止める。$A$ は正定値でない(thm-chol-main)。LDL 分解か LU分解 に切り替える。
  3. $\ell_{jj}=\sqrt{d_j}$ とし、第 $j$ 列の下の成分を計算する。
  4. $Ly=b$ を上の行から解き(前進代入)、$L^*x=y$ を下の行から解く(後退代入)。逆行列は作らない。
  5. 右辺が増えたら 4 だけを繰り返す。

止める判定:丸めのある計算では $d_j$ が小さい正の数か負の数かは信頼できない。$d_j\le\tau a_{jj}$($\tau$ は計算機精度の $n$ 倍程度に決める)なら $A$ を数値的に正定値でないとみなし、手順 2 と同じく別の分解に切り替える。
同じ数を別の順に計算する形もある。

形計算の順向く場面
列の順(上の手順)第 $j$ 列を前の列から作る下三角を列で持つ場合
行の順第 $i$ 行を前の行から作る行列が 1 行ずつ増える場合。第 $i$ 行で止まれば $A_i$ が正定値でない
Schur 補行列の順第 1 列を作り、残りを $C-\frac1{a_{11}}bb^*$ に更新する(正定値行列 の補題「Schur 補行列による分解」)ブロックに分けて計算する場合

分解の選び方は次のとおりである。

分解対象演算の回数ピボット選択出典
Cholesky正定値 Hermite$\frac13n^3$不要prop-chol-flops
LDL正則 Hermite、首座小行列式が $0$ でない$\frac13n^3$不要だが成分は増えうるprop-chol-ldl、BV04 §C.3.3
LU一般の正方行列$\frac23n^3$必要LU分解 の命題「分解と代入の演算回数」
QR一般の行列(行数が列数以上)$\frac43n^3$(正方)不要QR分解 の命題「QR 分解の演算回数」

例題

3 次の行列の分解と方程式

$A=\begin{pmatrix}4&12&-16\\12&37&-43\\-16&-43&98\end{pmatrix}$、$b=(0,6,39)^{\top}$ とする。
使う公式:def-chol-recurrence、prop-chol-minors。
答え:$L=\begin{pmatrix}2&0&0\\6&1&0\\-8&5&3\end{pmatrix}$、$d=(4,1,9)$、$y=(0,6,3)^{\top}$、$x=(1,1,1)^{\top}$。$\det A=36$、$\log\det A\approx3.58352$。

途中の計算を開く

第 1 列:$\ell_{11}=\sqrt4=2$、$\ell_{21}=12/2=6$、$\ell_{31}=-16/2=-8$。第 2 列:$d_2=37-36=1$、$\ell_{32}=(-43-(-8)\cdot6)/1=5$。第 3 列:$d_3=98-64-25=9$。前進代入:$y_1=0$、$y_2=6$、$y_3=(39+0-30)/3=3$。後退代入:$x_3=1$、$x_2=6-5=1$、$x_1=(0-6+8)/2=1$。$\det A=(2\cdot1\cdot3)^2=36$。

複素の Hermite 行列

$A=\begin{pmatrix}4&2i\\-2i&5\end{pmatrix}$ とする。
使う公式:def-chol-recurrence(共役の位置に注意する)。
答え:$L=\begin{pmatrix}2&0\\-i&2\end{pmatrix}$。$d_2=5-\lvert-i\rvert^2=4$ で、$LL^*=\begin{pmatrix}4&2i\\-2i&5\end{pmatrix}$。$\det A=16$。

漸化式が止まる行列と証拠のベクトル

$A=\begin{pmatrix}1&2&3\\2&5&4\\3&4&10\end{pmatrix}$ とする。
使う公式:thm-chol-main の最後の主張。
答え:$d_1=1$、$d_2=1$、$d_3=-3$ で第 3 列で止まるので、$A$ は正定値でない。証拠は $x=(-7,2,1)^{\top}$ で、$Ax=(0,0,-3)^{\top}$、$x^{\top}Ax=-3$。

途中の計算を開く

$\ell_{21}=2$、$\ell_{31}=3$、$\ell_{32}=(4-6)/1=-2$、$d_3=10-9-4=-3$。$L'=\begin{pmatrix}1&0\\2&1\end{pmatrix}$、$u=(3,-2)^{\top}$。$L'^{\top}z=u$ を解いて $z_2=-2$、$z_1=3-2z_2=7$。$x=(-z^{\top},1)^{\top}$。首座小行列式は $1,1,-3$ で、prop-chol-minors と合う。

$n$ 次の 2 階差分の行列

対角成分が $2$、隣の成分が $-1$ の $n$ 次の三重対角行列 $A$ を考える。
使う公式:def-chol-recurrence、prop-chol-zero の 2($p=1$)。
答え:$\ell_{jj}=\sqrt{\dfrac{j+1}j}$、$\ell_{j+1,j}=-\sqrt{\dfrac j{j+1}}$、ほかの成分は $0$。$\det A=n+1$。$n=5$ なら $\ell_{55}=\sqrt{6/5}\approx1.09545$。演算は $n$ に比例する。

途中の計算を開く

$d_j=\frac{j+1}j$ を帰納法で示す。$d_1=2$ である。$\ell_{j,j-1}=-1/\ell_{j-1,j-1}$ なので $\lvert\ell_{j,j-1}\rvert^2=1/d_{j-1}=\frac{j-1}j$ であり、$d_j=2-\frac{j-1}j=\frac{j+1}j$ である。prop-chol-minors により $\det A=\prod_jd_j=n+1$ である。$n=3$ の場合は 正定値行列 の例「3 次の三重対角行列」にある。

多変量正規分布の乱数と密度

$\mu=0$、$\Sigma=\begin{pmatrix}4&2\\2&5\end{pmatrix}$ の 2 変量正規分布を考える。
使う公式:def-chol-recurrence、多変量正規分布 の定理「1 次変換で多変量正規分布は保たれる」と定理「多変量正規分布の密度」。
答え:$L=\begin{pmatrix}2&0\\1&2\end{pmatrix}$。独立な標準正規分布の $Z=(Z_1,Z_2)^{\top}$ について $X=LZ$ は共分散行列 $LL^{\top}=\Sigma$ をもつ($Z=(1,-1)^{\top}$ なら $X=(2,-1)^{\top}$)。$x=(2,1)^{\top}$ での密度は、$Ly=x$ の解 $y=(1,0)^{\top}$ から $x^{\top}\Sigma^{-1}x=\|y\|^2=1$、$\log\det\Sigma=2(\log2+\log2)\approx2.77259$ を使って $\dfrac{e^{-1/2}}{2\pi\cdot4}\approx0.024133$ である。

矢印行列と並べ替え

$D=2I_{16}$、$u=(0.2,\dots,0.2)^{\top}\in\mathbb{R}^{16}$ とし、$A=\begin{pmatrix}1&u^{\top}\\u&D\end{pmatrix}$ を考える(BV04 Example C.1、p. 670 の形)。
使う公式:prop-chol-zero の 1。
答え:$u^{\top}D^{-1}u=0.32< 1$ なので正定値である。$A$ の下三角の非零は $33$ 個だが、因子 $L$ の下三角は $153$ 個すべてが非零になる。第 1 行と第 1 列を最後へ移した行列 $\begin{pmatrix}D&u\\u^{\top}&1\end{pmatrix}$ の因子は非零が $33$ 個のままである(下図)。

理由を開く

並べ替えた行列では、第 $i$ 行($i\le16$)の対角の左がすべて $0$ なので、prop-chol-zero の 1 により $L$ の第 $i$ 行も対角の左が $0$ である。$d_j=2$($j\le16$)、$d_{17}=1-u^{\top}D^{-1}u=0.68>0$ で、正定値であることもわかる。正定値性は対称な並べ替えで変わらない。元の順では第 1 列を消したあとの行列が $D-uu^{\top}$ になり、全成分が $0$ でない。

矢印行列 A とその Cholesky 因子、第 1 行と第 1 列を最後へ移した行列とその因子の非零の位置 矢印行列 A とその Cholesky 因子、第 1 行と第 1 列を最後へ移した行列とその因子の非零の位置
図の黒い升が非零の成分である($A$ は全体、因子は下三角を数えた)。零の並びは行列の順で大きく変わるので、疎な行列では分解の前に行と列を同時に並べ替える(BV04 §C.3.2、pp. 670–671)。

使える条件と反例

外す条件反例成り立たなくなること
Hermite(対称)$B=\begin{pmatrix}1&1\\-1&1\end{pmatrix}$$x^{\top}Bx=x_1^2+x_2^2>0$ だが、$LL^{\top}$ は対称なので $B\ne LL^{\top}$
正定値(半正定値、存在)$\begin{pmatrix}1&1\\1&1\end{pmatrix}$$d_2=0$ で止まる。$\det=0$ なので対角成分が正の $L$ はない
正定値(半正定値、一意性)$\begin{pmatrix}0&0\\0&1\end{pmatrix}$対角成分を $0$ 以上に緩めても、$c^2+s^2=1$、$s\ge0$ の $L=\begin{pmatrix}0&0\\c&s\end{pmatrix}$ がすべて $LL^{\top}=A$ を満たす
正定値(不定)$\begin{pmatrix}1&2\\2&1\end{pmatrix}$$d_2=-3$ で止まる。LDL 分解は $L_1=\begin{pmatrix}1&0\\2&1\end{pmatrix}$、$D=\operatorname{diag}(1,-3)$
対角成分が正$A=I_2$$L=I_2$ と $L=\operatorname{diag}(1,-1)$ の 2 つがある
prop-chol-zero の 1 の「左がすべて $0$」$\begin{pmatrix}4&2&2\\2&5&0\\2&0&5\end{pmatrix}$$a_{32}=0$ だが $a_{31}\ne0$ で、$\ell_{32}=-\frac12\ne0$
丸めのない計算$H_{14}$正定値でも倍精度の漸化式は止まる(rem-chol-rounding)

よくある誤り

誤り正しくはなぜ
対称な行列ならいつでも使えるとする正定値が必要で、$d_j\le0$ なら止めるthm-chol-main
$d_j< 0$ でも複素数の平方根で続ける止める。続けても $LL^*\ne A$ である対角成分が実で正の分解は存在しない(thm-chol-main)
複素行列で $A=LL^{\top}$ と書く$A=LL^*$ で、漸化式に共役が入るex-chol-complex
$A=LL^*$ と $A=L^*L$ を取り違える$L^*L$ は別の行列である$A=\begin{pmatrix}2&1\\1&1\end{pmatrix}$ の因子では $L^{\top}L=\begin{pmatrix}5/2&1/2\\1/2&1/2\end{pmatrix}$
$A^{-1}$ を作って $x=A^{-1}b$ とする三角行列の方程式を 2 回解く代入は右辺 1 本 $2n^2$ 回
$\det A=\prod\ell_{jj}^2$ をそのまま掛ける$\log\det A=2\sum\log\ell_{jj}$ を計算する大きな行列では積があふれやすい
疎な $A$ の因子も疎だと思う並べ替えで因子の零の個数が変わるex-chol-arrow

補足

丸めで止まる正定値行列

$n$ 次の Hilbert 行列 $H_n=(1/(i+j-1))$ は正定値である(正定値行列 の例「Gram 行列と Hilbert 行列」)。倍精度で漸化式を計算すると、$n=14$ の行列は第 $14$ 列までに止まる(止まる列と計算した値は和をとる順序で変わり、第 $13$ 列で止まる実装もある)。厳密な値は $d_{13}\approx5.47\times10^{-15}$、$d_{14}\approx3.42\times10^{-16}$ で正なのに、計算した値は負になる。途中で積み重なった丸めの誤差がこの大きさを上回るためで、この「止まった」は正定値でないことの証明にはならない。

最小二乗問題との関係

列が 1 次独立な $A$ の正規方程式 $A^{\top}Ax=A^{\top}b$ を Cholesky 分解で解くこともできる。対角成分を正にした QR 分解の $R_1$ について、$R_1^{\top}$ が $A^{\top}A$ の Cholesky 因子である(QR分解 の命題「Gram 行列・条件数・行列式との関係」)が、$A^{\top}A$ を作る段階で条件数が 2 乗になり、丸めで正定値でなくなることがある(QR分解 の例「正規方程式が解けなくなる行列」)。

不完全 Cholesky 分解

大きな疎行列では、$L$ の非零の位置を制限して $A\approx LL^{\top}$ とする不完全 Cholesky 分解を、反復法の前処理に使う。正定値な行列でも、この分解は存在するとは限らない(Saa03 第 10 章、p. 358)。

文献

Cholesky 分解の存在と一意性は Axl24 7.63(p. 267)にあり、そこでは QR分解 を経由して証明し、分解が 1924 年に没後刊行されたことも記している。正定値の定義は 7.62(p. 266)にある。実対称行列の分解、$\frac13n^3$ の演算、方程式の解法(Algorithm C.2)、帯行列($nk^2$)、疎行列と矢印行列(Example C.1)は BV04 §C.3.2(pp. 669–671)に、LDLT 分解は §C.3.3(pp. 671–672)にある。この記事の証明は、漸化式を 1 列ずつ追ってピボットを 2 次形式の値として書く形に組み立てたもので、$\ast$ の成分の比較から分解の存在と判定を同時に導いている。

関連項目

参考文献

[1]
Stephen Boyd, Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2004, §C.3.2(pp. 669–671、Algorithm C.2、Example C.1)、§C.3.3(pp. 671–672)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する