§D3.17QR 分解と最小二乗解

証明. 存在を示す。$\vec a_1, \dots, \vec a_n$は一次独立であるから、§D3.14 定理 2.1を適用して正規直交系$\vec e_1, \dots, \vec e_n$を得る。同定理より、各$j$について

が成り立つ。とくに$\vec a_j$は$W_j = \operatorname{span}\{\vec e_1, \dots, \vec e_j\}$に属する。$\{\vec e_1, \dots, \vec e_j\}$は$W_j$の正規直交基底であるから、§D3.14 命題 3.1を$W_j$に適用して

を得る。そこで$Q$を列が$\vec e_1, \dots, \vec e_n$である$m \times n$行列とし、$R = (r_{ij})$を$i \le j$のとき$r_{ij} = \langle \vec a_j, \vec e_i\rangle$、$i > j$のとき$r_{ij} = 0$と定める。$QR$の第$j$列は$\sum_{i} r_{ij}\vec e_i = \vec a_j$であるから$A = QR$である。$Q^\top Q = I_n$は$\vec e_i$が正規直交系であることから従う。対角成分については、§D3.14 定理 2.1の記号で$\vec u_j = \vec a_j - \sum_{i<j} c_i \vec u_i$、$\vec e_j = \vec u_j / \|\vec u_j\|$と書くと、$\vec u_1, \dots, \vec u_j$が互いに直交することから

となる。よって$R$は上三角で対角成分がすべて正である。

一意性を示す。$A = QR$を QR 分解とし、$Q$の列を$\vec q_1, \dots, \vec q_n$と書く。$j$についての帰納法で、$\vec q_1, \dots, \vec q_j$と$R$の第$1$列から第$j$列までが$A$から一意に定まること、および$\operatorname{span}\{\vec q_1, \dots, \vec q_j\} = \operatorname{span}\{\vec a_1, \dots, \vec a_j\}$が成り立つことを示す。

$j = 1$のとき、$R$が上三角であることから$\vec a_1 = r_{11}\vec q_1$であり、$\|\vec q_1\| = 1$、$r_{11} > 0$より$r_{11} = \|\vec a_1\|$、$\vec q_1 = \vec a_1 / \|\vec a_1\|$と定まる。張る空間も一致する。

$j-1$まで成り立つとする。$R$が上三角であることから

である。$i < j$について両辺と$\vec q_i$の内積を取ると、$\vec q_1, \dots, \vec q_n$が正規直交系であることから$r_{ij} = \langle \vec a_j, \vec q_i\rangle$となり、帰納法の仮定より右辺は$A$から定まる。そこで$\vec u = \vec a_j - \sum_{i<j} r_{ij}\vec q_i$とおくと$\vec u = r_{jj}\vec q_j$である。もし$\vec u = \vec 0$ならば$\vec a_j \in \operatorname{span}\{\vec q_1, \dots, \vec q_{j-1}\} = \operatorname{span}\{\vec a_1, \dots, \vec a_{j-1}\}$となり、列の一次独立性に反する。よって$\vec u \ne \vec 0$であり、$r_{jj} > 0$と$\|\vec q_j\| = 1$から$r_{jj} = \|\vec u\|$、$\vec q_j = \vec u / \|\vec u\|$と定まる。張る空間が一致することも上の等式から従う。▨

証明. 任意の$\vec x$に対して$QQ^\top \vec x = \sum_i \langle \vec x, \vec q_i\rangle \vec q_i$を与えるので、§D3.14 命題 3.2により結論を得る。▨

証明.$W = \operatorname{Im} A$とおく。$W$は$\mathbb{R}^m$の部分空間であるから正規直交基底$\vec f_1, \dots, \vec f_k$をもつ。$\vec p = \sum_{i} \langle \vec b, \vec f_i\rangle \vec f_i$とおくと、§D3.14 命題 3.2より$\vec b - \vec p$は$W$に直交し、$W$のどの要素$\vec w$についても$\|\vec b - \vec p\| \le \|\vec b - \vec w\|$であり、等号が成り立つのは$\vec w = \vec p$のときに限る。

1を示す。$A\vec x \in W$であるから、上の最良近似の一意性より、$\vec x$が最小二乗解であることと$A\vec x = \vec p$が成り立つことは同値である。次に$A\vec x = \vec p$と$\vec b - A\vec x \perp W$が同値であることを示す。$A\vec x = \vec p$ならば$\vec b - A\vec x = \vec b - \vec p$が$W$に直交する。逆に$\vec b - A\vec x \perp W$とすると、$\vec w \in W$に対し$A\vec x - \vec w \in W$であるから、ピタゴラスの定理により$\|\vec b - \vec w\|^2 = \|\vec b - A\vec x\|^2 + \|A\vec x - \vec w\|^2 \ge \|\vec b - A\vec x\|^2$となり、$A\vec x$は$W$の中で$\vec b$に最も近い。最良近似の一意性から$A\vec x = \vec p$である。最後に、$W$は$A$の列$\vec a_1, \dots, \vec a_n$で張られるから、$\vec b - A\vec x \perp W$はすべての$j$について$\langle \vec a_j, \vec b - A\vec x\rangle = 0$と同値であり、これは$A^\top(\vec b - A\vec x) = \vec 0$、すなわち$A^\top A\vec x = A^\top \vec b$と同値である。

2を示す。$\vec p \in W = \operatorname{Im} A$であるから$A\vec x_0 = \vec p$を満たす$\vec x_0$が存在し、 1よりこれは最小二乗解である。また$\vec x$が最小二乗解であることは$A\vec x = \vec p = A\vec x_0$、すなわち$\vec x - \vec x_0 \in \operatorname{Ker} A$と同値である。

3を示す。2より、最小二乗解がただ一つであることは$\operatorname{Ker} A = \{\vec 0\}$と同値である。$A\vec x = \sum_j x_j \vec a_j$であるから、$\operatorname{Ker} A = \{\vec 0\}$は$\vec a_1, \dots, \vec a_n$が一次独立であることと同値である。▨

証明. 列が一次独立であるから、定理 2.2の3より最小二乗解はただ一つである。

$Q^\top Q = I_n$より$A^\top A = R^\top Q^\top Q R = R^\top R$であり、$A^\top \vec b = R^\top Q^\top \vec b$である。よって正規方程式は

と書ける。$R$は上三角で対角成分が正であるから、第1列に沿った余因子展開を繰り返すと$\det R = r_{11}r_{22}\cdots r_{nn} > 0$となり、$R$と$R^\top$はいずれも正則である。両辺に$(R^\top)^{-1}$を左から掛けて$R\vec x = Q^\top \vec b$を得る。逆にこの等式から正規方程式が従う。$R$が正則であるから、この連立一次方程式の解はただ一つである。

正射影については、命題 1.3のとおり$QQ^\top$が$\operatorname{Im} A$への正射影を表す。▨