Cholesky分解(Cholesky decomposition)とは、正定値な Hermite 行列(実数なら対称行列)$A$ を、対角成分が正の下三角行列 $L$ によって $A=LL^*$ と書くことである。分解はただ 1 つに定まり、成分の漸化式が途中で止まらないことと $A$ が正定値であることは同値なので、判定法も兼ねる。手間は LU 分解の半分で行の入れ替えも要らず、連立 1 次方程式、行列式の対数、多変量正規分布の乱数の計算に使う。帯行列では零の並びが保たれるが、疎な行列では並べ方で因子の非零の個数が大きく変わる。
有限要素法の剛性行列、最小二乗の正規方程式、共分散行列など、応用に現れる連立 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}$ である。
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)。
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$ も実数である。
使える条件をまとめる。
演算の回数は実行列での主要項である。
| 計算 | 公式 | 使える条件 | 演算の回数 | 根拠 |
|---|---|---|---|---|
| 分解 | 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 |
$A\in M_n(K)$ を Hermite 行列とする。次は同値である。
下三角行列 $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}$ である。
要点: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分解 の命題「分解と代入の演算回数」と同じ数え方)。
正定値な対称行列 $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 は $(\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 因子とする。
$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 因子である。
要点:$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$ は下三角の部分だけを使う)
止める判定:丸めのある計算では $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 分解の演算回数」 |
$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$。
$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 と合う。
対角成分が $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$ は全体、因子は下三角を数えた)。零の並びは行列の順で大きく変わるので、疎な行列では分解の前に行と列を同時に並べ替える(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}$ で正なのに、計算した値は負になる。途中で積み重なった丸めの誤差がこの大きさを上回るためで、この「止まった」は正定値でないことの証明にはならない。
大きな疎行列では、$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$ の成分の比較から分解の存在と判定を同時に導いている。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する