§E20.6最小二乗法と QR 分解

証明.§D3.17 定理 2.2により、条件 (a)と条件 (c)は同値であり、(1)と、(2)の前半が成り立つ。$A$の列空間は$A$の列$a_1,\dots,a_n$で張られるから、条件 (b)は$a_j^{\mathsf T}(b-Ax)=0$（$1\le j\le n$）と同値であり、これは$A^{\mathsf T}(b-Ax)=0$、すなわち条件 (c)と同値である。$A$の列が一次独立ならば$\ker A=\{0\}$であり、§D3.18 補題 1.1により$\ker(A^{\mathsf T}A)=\ker A=\{0\}$であるから、$A^{\mathsf T}A$は正則である。このとき条件 (c)の解は$(A^{\mathsf T}A)^{-1}A^{\mathsf T}b$だけである。▨

証明.§D3.18 定理 1.2により、直交行列$U\in\R^{m\times m}$、$V\in\R^{n\times n}$と、$(i,i)$成分が$\sigma_i(M)$（$1\le i\le p$）でその他の成分が$0$の$\Sigma\in\R^{m\times n}$が存在して$M=U\Sigma V^{\mathsf T}$である。$h\in\R^n$に対して$k:=V^{\mathsf T}h$と置くと、直交行列は Euclid ノルムを保つので$\lVert k\rVert_2=\lVert h\rVert_2$であり、

である。

右辺は$\sigma_1(M)^2\lVert k\rVert_2^2$以下であり、$h$を$V$の第$1$列とすると等号が成り立つから、$\lVert M\rVert_2=\sigma_1(M)$である。$M^{\mathsf T}=V\Sigma^{\mathsf T}U^{\mathsf T}$は§D3.18 定理 1.2の形の$M^{\mathsf T}$の分解であるから、§D3.18 命題 2.1により$M^{\mathsf T}$の特異値は$\sigma_1(M),\dots,\sigma_p(M)$であり、$\lVert M^{\mathsf T}\rVert_2=\sigma_1(M)$である。$M$の第$i$行を$\mu_i$とすると、Cauchy–Schwarz の不等式により$\lVert Mh\rVert_2^2=\sum_i(\mu_ih)^2\le\sum_i\lVert\mu_i\rVert_2^2\lVert h\rVert_2^2=\lVert M\rVert_F^2\lVert h\rVert_2^2$であり、$\lVert M\rVert_2\le\lVert M\rVert_F$である。これで(1)は示された。

$m\ge n$であり$M$の列が一次独立ならば、$M$の階数は$n$であり、§D3.18 定理 1.2により$\sigma_n(M)>0$である。$p=n$であるから、上の等式の右辺は$\sigma_n(M)^2\lVert k\rVert_2^2$以上であり、$h$を$V$の第$n$列とすると等号が成り立つ。$M^{\mathsf T}M=V\operatorname{diag}(\sigma_1(M)^2,\dots,\sigma_n(M)^2)V^{\mathsf T}$であるから

である。ここで$S\in\R^{n\times m}$は$(i,i)$成分が$\sigma_i(M)^{-1}$（$1\le i\le n$）でその他の成分が$0$の行列である。直交行列は Euclid ノルムを保つので、二つの行列の作用素ノルムは対角行列$\operatorname{diag}(\sigma_i(M)^{-2})$と$S$の作用素ノルムに等しく、上と同じ計算によりそれぞれ$\sigma_n(M)^{-2}$と$\sigma_n(M)^{-1}$である。これで(2)は示された。

$E$が(3)の仮定を満たすとする。任意の$h\in\R^n$に対して、(2)と§E20.2 補題 1.2 (1)により

である。$h\ne0$ならば右辺は正であるから、$M+E$の列は一次独立である。(2)を$M+E$に適用し、等号を満たす$h\ne0$をとると、$\sigma_n(M+E)\lVert h\rVert_2=\lVert(M+E)h\rVert_2\ge(\sigma_n(M)-\lVert E\rVert_2)\lVert h\rVert_2$である。▨

証明.$(A^{\mathsf T}A)^{\mathsf T}=A^{\mathsf T}A$であり、$x\ne0$ならば列の一次独立性から$Ax\ne0$であって$x^{\mathsf T}A^{\mathsf T}Ax=\lVert Ax\rVert_2^2>0$であるから、$A^{\mathsf T}A$は実対称正定値行列である。§D3.18 命題 2.1により、$\sigma_1(A)^2\ge\dots\ge\sigma_n(A)^2$は$A^{\mathsf T}A$の$n$個の固有値である。§E20.5 命題 4.4 (5)により$\kappa_2(A^{\mathsf T}A)=\sigma_1(A)^2/\sigma_n(A)^2=\kappa_2(A)^2$である。▨

証明.$H_v^{\mathsf T}=H_v$である。$vv^{\mathsf T}vv^{\mathsf T}=(v^{\mathsf T}v)vv^{\mathsf T}$から

であり、$H_v^{\mathsf T}H_v=H_v^2=I_\ell$である。$H_vv=v-2v=-v$であり、$v^{\mathsf T}w=0$ならば$H_vw=w$である。

(2)の記号で、$sx_1=|x_1|$であるから$sv_1=|x_1|+\alpha$であり、$x\ne0$から$\alpha>0$である。$v^{\mathsf T}v=\alpha^2+2s\alpha x_1+\alpha^2=2\alpha(\alpha+|x_1|)=2\alpha sv_1$であるから、$H_v$の定義により$H_vy=y-(v^{\mathsf T}y/(\alpha sv_1))v$である。$v^{\mathsf T}x=\alpha^2+s\alpha x_1=\alpha sv_1$であるから$H_vx=x-v=-s\alpha e_1$である。

$sv'_1=|x_1|-\alpha=(x_1^2-\alpha^2)/(|x_1|+\alpha)=-\bigl(\sum_{i\ge2}x_i^2\bigr)/(|x_1|+\alpha)$である。$v'^{\mathsf T}x=\alpha^2-s\alpha x_1=\alpha(\alpha-|x_1|)$、$v'^{\mathsf T}v'=2\alpha^2-2s\alpha x_1=2\alpha(\alpha-|x_1|)$であり、$v'\ne0$ならば$v'^{\mathsf T}v'>0$であるから、$H_{v'}x=x-v'=s\alpha e_1$である。▨

証明.$Q$の第$1$列から第$n$列からなる行列を$Q_1$とすると$A=Q_1T$、$Q_1^{\mathsf T}Q_1=I_n$である。$Ah=0$ならば$Th=Q_1^{\mathsf T}Ah=0$であり、$T$は対角成分がすべて$0$でない上三角行列であるから正則であって、$h=0$である。したがって$A$の列は一次独立である。任意の$z\in\R^n$について$Q^{\mathsf T}(b-Az)=\begin{pmatrix}c_1-Tz\\c_2\end{pmatrix}$であり、$Q$は Euclid ノルムを保つので

である。等号は$Tz=c_1$のときに限って成り立ち、$T$は正則であるから$Tz=c_1$の解$x$はただ一つである。したがって$x$は$Ax=b$のただ一つの最小二乗解であり、$\lVert b-Ax\rVert_2=\lVert c_2\rVert_2$である。▨

証明. 段$k$の前の作業行列を$W^{(k-1)}$、後の作業行列を$W^{(k)}$とする。段$k$は第$1$列から第$k-1$列を変えず、第$k$列の第$k+1$行から第$m$行を$0$にする（定義 3.4 (1)の場合は既に$0$である）から、$k$に関する帰納法により、$W^{(k)}$の第$j$列（$j\le k$）の第$j+1$行から第$m$行は$0$である。特に$R$は上三角行列である。

$W^{(k)}=H_kW^{(k-1)}$が成り立つ。実際、定義 3.4 (1)の場合は$H_k=I_m$である。$x\ne0$の場合、$H_k$は第$1$行から第$k-1$行を変えない。$j<k$ならば第$j$列の第$k$行から第$m$行は$0$であるから、補題 3.2 (1)により$H_k$は第$j$列を変えない。補題 3.2 (2)により$H_vx=-s\alpha e_1$であり、これは定義 3.4 (3)の書き込みに一致する。$j>k$ならば、$p=\alpha sv_1$であるから定義 3.4 (4)の値は$y-(v^{\mathsf T}y/(\alpha sv_1))v=H_vy$である。

したがって$W^{(n)}=H_n\cdots H_1(A\ b)$である。補題 3.2 (1)により各$H_k$は対称な直交行列であるから、$Q$は直交行列であって$Q^{\mathsf T}=H_n\cdots H_1$である。$W^{(n)}$の第$1$列から第$n$列は$\begin{pmatrix}R\\0\end{pmatrix}$、第$n+1$列は$c$であるから、$A=Q\begin{pmatrix}R\\0\end{pmatrix}$、$b=Qc$を得る。$A$の列が一次独立ならば、$\begin{pmatrix}R\\0\end{pmatrix}=Q^{\mathsf T}A$の列も一次独立であり、$R$は正則であるから、上三角行列$R$の対角成分はすべて$0$でない。最後の主張は補題 3.5を$T=R$に適用したものである。▨

証明. 演習とする（問題 7.1）。▨

証明. 範囲条件により各積$x_ix_i$は$0$であるか正規範囲にあるから、§E20.1 系 3.2 (1)または§E20.1 系 3.2 (2)により、$|\mu_i|\le u$を満たす$\mu_i$が存在して$\operatorname{fl}(x_ix_i)=x_i^2(1+\mu_i)$である。$q$の計算値$\hat q$はこれらの逐次和であり、§E20.3 系 1.4 (1)により各項の深さは$\ell-1$以下であるから、§E20.3 定理 1.3 (1)により$\hat q=\sum_ix_i^2e_i$であって、各$e_i$は$1+\mu_i$と高々$\ell-1$個の$1+\delta$（$|\delta|\le u$）の積である。$u\le1/2$であるから、補題 4.2 (1)と補題 4.2 (2)により$e_i\in B_\ell$であり、$\alpha^2=\sum_ix_i^2>0$であるから、補題 4.2 (3)により$\hat q/\alpha^2\in B_\ell$であり、特に$\hat q>0$である。$\sqrt{\hat q}>0$であり、範囲条件により$\sqrt{\hat q}$は正規範囲にあるから、§E20.1 定理 2.2 (2)により$|\delta_\alpha|\le u$を満たす$\delta_\alpha$が存在して$\hat\alpha=\sqrt{\hat q}(1+\delta_\alpha)$である。$c_1:=\hat\alpha/\alpha=(\hat q/\alpha^2)^{1/2}(1+\delta_\alpha)$は、補題 4.2 (2)により$B_{\ell/2+1}$に属する。

補題 3.2 (2)により$sv_1=|x_1|+\alpha$であり、$x_1+s\hat\alpha=s(|x_1|+c_1\alpha)=c'v_1$である。ここで$c':=(|x_1|\cdot1+\alpha c_1)/(|x_1|+\alpha)$は$1$と$c_1$の正の重みによる平均であるから、補題 4.2 (3)により$B_{\ell/2+1}$に属する。$x_1$と$s\hat\alpha$は$F$の元であり、範囲条件によりその和の絶対値は$N_{\max}$以下であるから、§E20.1 系 3.3により$|\delta_v|\le u$を満たす$\delta_v$が存在して$\hat v_1=c'(1+\delta_v)v_1$である。$c_2:=c'(1+\delta_v)$は$B_{\ell/2+2}$に属し、$i\ge2$では$\hat v_i=x_i=v_i$であるから、$\hat v=v+(c_2-1)v_1e_1$である。