射影を引いて直角を作る - グラム・シュミットの正規直交化

$v_{2}$ から $v_{1}$ 方向の成分を引くと、残りは $v_{1}$ と直交します。引き算 1 回で直角が作れる。

この操作を、本数のぶんだけ繰り返すのがグラム・シュミットの正規直交化です^[1]。最後に長さで割れば、正規直交基底ができます。

1 本目と 2 本目

$v_{1}$ はそのまま使います。長さで割って $e_{1}$ とする。

$e_{1} = \frac{v _{1}}{∥ v _{1} ∥}$

2 本目は、 $v_{2}$ から $e_{1}$ 方向の成分を引きます。引いた残りを $u_{2}$ とおく。

$u_{2} = v_{2} - ⟨ v_{2}, e_{1} ⟩ e_{1}, e_{2} = \frac{u _{2}}{∥ u _{2} ∥}$

$⟨ v_{2}, e_{1} ⟩ e_{1}$ は、 $v_{2}$ を $e_{1}$ の張る直線へ落とした足です。垂線の足を引けば、垂線そのものが残る。

引いた残りが直交する理由

計算で確かめます。 $u_{2}$ と $e_{1}$ の内積をとる。

$⟨ u_{2}, e_{1} ⟩ = ⟨ v_{2}, e_{1} ⟩ - ⟨ v_{2}, e_{1} ⟩ ⟨ e_{1}, e_{1} ⟩ = ⟨ v_{2}, e_{1} ⟩ - ⟨ v_{2}, e_{1} ⟩ = 0$

$∥ e_{1} ∥ = 1$ なので $⟨ e_{1}, e_{1} ⟩ = 1$ 。ちょうど打ち消し合います。

長さを $1$ にそろえてあるからこの形になる。そろえていない $v_{1}$ で引くなら、 $∥ v_{1} ∥^{2}$ で割る必要があります^[1]。

一般の手順

$k$ 本目では、すでに作った $e_{1}, \dots, e_{k - 1}$ の全方向について、同じ引き算をします^[1]。

$u_{k} = v_{k} - j = 1 \sum k - 1 ⟨ v_{k}, e_{j} ⟩ e_{j}, e_{k} = \frac{u _{k}}{∥ u _{k} ∥}$

引いたあと $u_{k}$ と $e_{i}$ の内積をとると、 $j = i$ の項だけが残って打ち消し合う。他の項は $⟨ e_{j}, e_{i} ⟩ = 0$ で消えます。

同じ計算が $i = 1, \dots, k - 1$ のすべてで通るので、 $u_{k}$ は前の全部と直交します。

途中までの張る空間は変わらない

$k$ 本目まで見ると、もとの $v_{1}, \dots, v_{k}$ と新しい $e_{1}, \dots, e_{k}$ は同じ空間を張ります^[1]。

$span {v_{1}, \dots, v_{k}} = span {e_{1}, \dots, e_{k}}$

$e_{k}$ は $v_{k}$ と前の $e_{j}$ の一次結合。逆に $v_{k}$ も $e_{1}, \dots, e_{k}$ で書けるので、両向きに含まれます。

この性質があるので、途中で止めても意味のある結果になる。 $k$ 本だけ直交化すれば、その $k$ 本が張る空間の正規直交基底が手に入ります。

例： $R^{3}$ で 3 本を直交化する

$v_{1} = 111, v_{2} = 012, v_{3} = 102$

$u_{1} = v_{1}$ とし、 $∥ u_{1} ∥^{2} = 3$ 。 $⟨ v_{2}, u_{1} ⟩ = 0 + 1 + 2 = 3$ なので、係数は $3/3 = 1$ です^[1]。

$u_{2} = 012 - 1 \cdot 111 = - 1 01$

3 本目は 2 方向ぶん引きます。 $⟨ v_{3}, u_{1} ⟩ = 3$ 、 $⟨ v_{3}, u_{2} ⟩ = 1$ 、 $∥ u_{2} ∥^{2} = 2$ 。

$u_{3} = 102 - 1 \cdot 111 - \frac{1}{2} - 1 01 = 1/2 - 1 1/2$

内積を確かめると $u_{3} \cdot u_{1} = \frac{1}{2} - 1 + \frac{1}{2} = 0$ 、 $u_{3} \cdot u_{2} = - \frac{1}{2} + 0 + \frac{1}{2} = 0$ 。3 本とも直交しました。

長さで割ると、正規直交基底が出ます。

$e_{1} = \frac{1}{3} 111, e_{2} = \frac{1}{2} - 1 01, e_{3} = \frac{1}{6} 1 - 2 1$

$u_{3}$ を 2 倍しても向きは同じなので、分数を消してから割ると計算が楽です。

一次独立でないと途中で止まる

$v_{k}$ が前の $v_{1}, \dots, v_{k - 1}$ の一次結合なら、 $v_{k}$ はすでに $E_{k - 1}$ に入っています。引くと何も残らない。

$u_{k} = v_{k} - P_{E_{k - 1}} v_{k} = 0$

$0$ を長さで割れないので、そこで手順が止まります。 $u_{k} = 0$ が出た時点で、一次従属だと分かる仕組みです。

判定に使えます。途中で $0$ が出れば従属、最後まで出なければ独立。

$u_{k}$ を作る

$0$ なら一次従属で終了

$0$ でなければ割って次へ

QR 分解が出てくる

$v_{1}, \dots, v_{n}$ を列に並べた行列を $A$ 、 $e_{1}, \dots, e_{n}$ を列に並べた行列を $Q$ とします。

手順を逆に読むと、 $v_{k}$ が $e_{1}, \dots, e_{k}$ の一次結合で書けています。 $e_{k + 1}$ 以降は使いません。

$v_{k} = ⟨ v_{k}, e_{1} ⟩ e_{1} + \dots + ⟨ v_{k}, e_{k - 1} ⟩ e_{k - 1} + ∥ u_{k} ∥ e_{k}$

この係数を第 $k$ 列に縦に並べると、対角より下が $0$ の行列になります。上三角行列 $R$ です^[2]。

$A = QR$

$R$ の対角成分は $∥ u_{k} ∥$ 。一次独立なら全部正なので、 $R$ は正則になります。

例：QR を書き下す

上の 3 本を列に並べた行列で、 $R$ の成分を出します。 $r_{j k} = ⟨ v_{k}, e_{j} ⟩$ で、対角は $∥ u_{k} ∥$ です。

$R = 300320 3 1/ 2 6 /2$

行列式は $3 \cdot 2 \cdot \frac{6}{2} = \frac{6}{2} = 3$ 。 $det Q = \pm 1$ なので $∣ det A ∣ = 3$ になります。

もとの $A$ の行列式を直接計算しても $3$ 。分解が正しいことの確かめになります。

順番を変えると数値が変わる

引き算をどう並べるかで、丸め誤差の乗り方が変わります。数学的には同じでも、計算機では別物です^[3]。

古典版は、もとの $v_{k}$ から全方向ぶんをまとめて引きます。修正版は、1 方向引いた結果からまた次を引く、と順に更新する。

$u_{k}^{(j)} = u_{k}^{(j - 1)} - ⟨ u_{k}^{(j - 1)}, e_{j} ⟩ e_{j}$

内積を、更新前の $v_{k}$ ではなく更新後の $u_{k}^{(j - 1)}$ でとるのが違いです。すでに引いた誤差が次の内積に反映されます。

古典版

内積をすべて $v_{k}$ でとる。直交性が完全に失われる場合がある

修正版

内積を更新後のベクトルでとる。崩れは条件数 $κ (A)$ に比例する形で押さえられる

修正版については、 $∥ I - Q^{T} Q ∥$ が機械イプシロン $ε$ と $κ (A)$ の積で押さえられると示されています^[3]。

$κ (A) = 1.7 \times 1 0^{11}$ のような悪条件の行列だと、この上限でも直交性は残りません。古典版はさらに悪く、失われ方が実験で確かめられています^[3]。

例：ほとんど平行な 2 本

$v_{1} = (1, ε, 0)$ 、 $v_{2} = (1, 0, ε)$ を $ε = 1 0^{- 8}$ でとります。ほぼ同じ向きの 2 本です。

$⟨ v_{2}, v_{1} ⟩ = 1$ 、 $∥ v_{1} ∥^{2} = 1 + ε^{2}$ 。ところが $ε^{2} = 1 0^{- 16}$ は、倍精度では $1$ に足しても消えます。

引き算 $1 - 1$ で有効数字が全部落ちる。桁落ちと呼ばれる現象で、残った $u_{2}$ の向きは誤差だけで決まってしまいます。

安定させたいなら、直交化をもう一度かける方法があります。誤差の乗った $e_{2}$ を、 $e_{1}$ に対してさらに直交化し直す手順です。

やり直しは 1 回で足ります。2 回目を終えた時点で、直交性は機械精度まで戻ると示されています^[3]。

より安定なのはハウスホルダー変換による QR 分解。こちらは引き算ではなく鏡映を重ねるので、桁落ちが起きません。

グラム・シュミットが崩れやすいのは、ほとんど平行なベクトルを引き算で分けるからです。

鏡映で直交化するハウスホルダー変換なら、大きさが変わらない操作だけを重ねるので誤差が増えない。

グラム・シュミットの途中で $u_{k} = 0$ が出ました。何が分かりますか。

内積の計算を間違えた
$v_{k}$ が前のベクトルの一次結合になっている
$v_{k}$ が零ベクトルである

__RESULT__

$u_{k}$ は $v_{k}$ から $E_{k - 1}$ への射影を引いたものです。 $0$ になるのは $v_{k}$ がすでに $E_{k - 1}$ に入っているとき、つまり一次従属のときになります。 $v_{k}$ 自身が零ベクトルとは限りません。

分解の形も確かめます。

$A = QR$ で $R$ の対角成分は何にあたりますか。

もとのベクトルの長さ $∥ v_{k} ∥$
引いたあとに残った長さ $∥ u_{k} ∥$
つねに $1$

__RESULT__

$v_{k} = \dots + ∥ u_{k} ∥ e_{k}$ と展開したときの $e_{k}$ の係数が対角成分です。前の方向ぶんを引いた残りの長さで、 $∥ v_{k} ∥$ より小さくなります。一次独立ならすべて正になります。

まちがえやすい点

e_{j}

ではなく正規化前の

u_{j}

で引くとき、

∥ u_{j} ∥^{2}

で割るのを忘れる。長さが

1

でないと打ち消し合いません。

2 本目までしか引かずに 4 本目を作る。

k

本目では

k - 1

方向すべてを引きます。

引く前のベクトルどうしで内積をとる。修正版では、更新後のベクトルでとります。

u_{k}

を正規化せずに次の段へ進む。次の内積の係数がずれます。

垂線の足を引いて残りをとる。この 1 手を繰り返すだけで、どんな一次独立の組も正規直交基底に変わります。順番を変えると数値が変わる、という点だけが実装の分かれ目。

出典

Sergei Treil. *Linear Algebra Done Wrong*, Chapter 5. Brown University.

David Austin. *Finding Orthogonal Bases*. Understanding Linear Algebra.

Luc Giraud, Julien Langou, Miroslav Rozloznik. *On the loss of orthogonality in the Gram-Schmidt orthogonalization process*. CERFACS Technical Report TR/PA/03/25.

$v_2$ から $v_1$ 方向の成分を引けば、残りは $v_1$ と直交します。内積をとると $\langle v_2, e_1 \rangle$ が二度出てきて打ち消し合う、それだけの仕掛け。$k$ 本目では $k-1$ 方向ぶん引き、最後に長さで割ります。$(1,1,1)$、$(0,1,2)$、$(1,0,2)$ を直交化する計算例を追い、係数を縦に並べると上三角の $R$ が現れて $A = QR$ になるところまで。途中で $u_k = 0$ が出れば一次従属と分かる。ほとんど平行な 2 本で桁落ちが起きる理由、内積を更新後のベクトルでとる修正版が安定する理由も扱いました。