§E20.9特異値分解の数値計算と数値的階数

証明.§D3.18 定理 1.2により、直交行列$U\in\R^{m\times m}$、$V\in\R^{n\times n}$と、$(i,i)$成分が$\sigma_i(A)$（$1\le i\le p$）でその他の成分が$0$の$\Sigma\in\R^{m\times n}$が存在して$A=U\Sigma V^{\mathsf T}$である。$PU$と$Q^{\mathsf T}V$は直交行列であり、$PAQ=(PU)\Sigma(Q^{\mathsf T}V)^{\mathsf T}$は§D3.18 定理 1.2の形の$PAQ$の分解であるから、§D3.18 命題 2.1により$\sigma_i(PAQ)=\sigma_i(A)$である。§E20.6 補題 2.1 (1)により$\lVert PAQ\rVert_2=\sigma_1(PAQ)=\sigma_1(A)=\lVert A\rVert_2$である。▨

証明.(1)を示す。段$k$の前の作業行列を$W^{(k-1)}$、定義 2.2 (1)の後の作業行列を$\widetilde W^{(k)}$、段$k$の後の作業行列を$W^{(k)}$とする。§E20.6 補題 3.2 (1)により$L_k$と$R_k$は対称な直交行列である。$0\le k\le n$について、次の二条件を$\mathrm{Z}_k$とする。

$\mathrm{Z}_0$は条件を課さない。$1\le k\le n$とし、$\mathrm{Z}_{k-1}$を仮定する。

$\widetilde W^{(k)}=L_kW^{(k-1)}$である。実際、$x=0$ならば$L_k=I_m$である。$x\ne0$ならば、$L_k$を左から掛ける操作は第$1$行から第$k-1$行を変えず、各列の第$k$成分から第$m$成分を並べたベクトル$y$を$H_vy$に置き換える。$j<k$ならば (a) によりその$y$は$0$であり、$H_v0=0$である。第$k$列の$y$は$x$であり、§E20.6 補題 3.2 (2)により$H_vx=-s\alpha e_1$であって、これは定義 2.2 (1)の書き込みに一致する。$j>k$ならば、$p=\alpha sv_1$であるから§E20.6 定義 3.4 (4)の値は$y-(v^{\mathsf T}y/(\alpha sv_1))v$であり、§E20.6 補題 3.2 (2)によりこれは$H_vy$である。したがって$\widetilde W^{(k)}$は (a) を$j\le k$について満たし、第$1$行から第$k-1$行は$W^{(k-1)}$と同じであるから (b) を$i\le k-1$について満たす。

$W^{(k)}=\widetilde W^{(k)}R_k$である。実際、$R_k=I_n$の場合は定義 2.2 (2)は何も行わない。$R_k=\operatorname{diag}(I_k,H_{v'})$の場合、$H_{v'}$は対称であるから、$R_k$を右から掛ける操作は第$1$列から第$k$列を変えず、各行の第$k+1$成分から第$n$成分を並べたベクトル$z$を$H_{v'}z$に置き換える。$i<k$ならば$j\ge k+1>i+1$であるから、(b) によりその$z$は$0$である。第$k$行の$z$は$x'$であり、§E20.6 補題 3.2 (2)により$H_{v'}x'=-s'\alpha'e_1$である。$i>k$ならば、上と同じく§E20.6 定義 3.4 (4)の値は$H_{v'}z$である。したがって$W^{(k)}$は、第$1$列から第$k$列が$\widetilde W^{(k)}$と同じであるから (a) を満たし、(b) を$i\le k-1$について満たす。$i=k$については、$k\le n-2$かつ$x'\ne0$ならば上の書き込みにより、$k\le n-2$かつ$x'=0$ならば$x'$の定義により、$k\ge n-1$ならば$j>k+1\ge n$を満たす$j\le n$が存在しないことにより、(b) が成り立つ。これで$\mathrm{Z}_k$が成り立つ。

$k$に関する帰納法により$\mathrm{Z}_n$が成り立つ。$i>n$ならば第$i$行の成分の列番号$j\le n$は$j<i$を満たすので、(a) によりその成分は$0$である。したがって$B=W^{(n)}$は上二重対角行列である。$L_k^{\mathsf T}=L_k$であるから

であり、直交行列の積$U$、$V$は直交行列である。補題 1.1により$\sigma_i(B)=\sigma_i(A)$である。

(2)を示す。段$k$の定義 2.2 (1)で$x\ne0$ならば、$\ell=m-k+1$について、§E20.6 定義 3.4 (2)の計算式は$\ell$回の乗算、$\ell-1$回の加算、平方根$1$回、$v_1$の加算$1$回、$p$の乗算$1$回の$2\ell+2$回であり、§E20.6 定義 3.4 (4)の計算式は一つの列について$\omega$に$2\ell-1$回、$\tau$に$1$回、更新に$2\ell$回の$4\ell$回であって、$n-k$個の列に施す。段$k\le n-2$の定義 2.2 (2)で$x'\ne0$ならば、同じく$\ell'=n-k$について$2\ell'+2+4\ell'(m-k)$回である。$x=0$または$x'=0$の段では対応する回数が$0$になる。すべての段で$x\ne0$、$x'\ne0$であるときの回数は

である。$j:=n-k$と置くと$m-k=m-n+j$であり、第一の和は$2mn-n^2+3n+4\sum_{j=0}^{n-1}j(m-n+j+1)$、第二の和は$n^2+n-6+4\sum_{j=2}^{n-1}j(m-n+j)$である。第二の和の$\sum_{j=2}^{n-1}$に$j=1$の項を加えて$4(m-n+1)$を差し引くと、二つの$4\sum$の和は

であり、これに$2mn-n^2+3n+n^2+n-6$を加えて展開すると$N(m,n)$を得る。最後に$N(m,n)-4mn^2+\frac43n^3=-2n(m-n)-4m+\frac{22}3n-10$であり、$m\ge n$から右辺は$-4n+\frac{22}3n-10=\frac{10}3n-10$以下である。▨

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

証明.$X'^{\mathsf T}=J^{\mathsf T}X^{\mathsf T}J=X'$である。$J$の第$j$列（$j\notin\{p,q\}$）は$e_j$であり、第$p$列は$ce_p-se_q$、第$q$列は$se_p+ce_q$である。$i\notin\{p,q\}$ならば$J^{\mathsf T}e_i=e_i$であるから、$x'_{ij}=e_i^{\mathsf T}XJe_j$であり、

である。$x'_{pq}=(ce_p-se_q)^{\mathsf T}X(se_p+ce_q)=csx_{pp}+c^2x_{pq}-s^2x_{qp}-scx_{qq}$であり、$x_{qp}=x_{pq}$から(1)を得る。

$c^2+s^2=1$であるから、$i\notin\{p,q\}$について$x'^2_{ip}+x'^2_{iq}=x_{ip}^2+x_{iq}^2$である。$i\ne j$を満たす組$(i,j)$を、$\{i,j\}\cap\{p,q\}=\emptyset$のもの、$\{i,j\}$と$\{p,q\}$がただ一つの元を共有するもの、$\{i,j\}=\{p,q\}$のものに分ける。第一の組の項は変わらない。第二の組の項の和は、$X$と$X'$の対称性により$2\sum_{i\notin\{p,q\}}(x_{ip}^2+x_{iq}^2)$であり、変わらない。第三の組の項の和は$X$では$2x_{pq}^2$、$X'$では$2x'^2_{pq}$である。これで(2)は示された。▨

証明.(1)を示す。$V_0=I_n$、$A_0=AV_0$である。$V_k$が直交行列で$A_k=AV_k$ならば、平面回転$J_k$は直交行列であるから$V_{k+1}=V_kJ_k$は直交行列であり、$A_{k+1}=A_kJ_k=AV_{k+1}$である。$k$に関する帰納法により前半が従い、$G_k=A_k^{\mathsf T}A_k=V_k^{\mathsf T}A^{\mathsf T}AV_k$である。

(2)を示す。$k\ge0$とし、段$k$で選んだ対を$(p,q)$、$\gamma:=g^{(k)}_{pq}$とする。$G_k$は対称であり、$G_{k+1}=J_k^{\mathsf T}A_k^{\mathsf T}A_kJ_k=J_k^{\mathsf T}G_kJ_k$である。補題 3.3 (1)と補題 3.2により$G_{k+1}$の$(p,q)$成分は$\gamma(c^2-s^2)+cs(g^{(k)}_{pp}-g^{(k)}_{qq})=0$であり、補題 3.3 (2)により$\operatorname{off}(G_{k+1})=\operatorname{off}(G_k)-2\gamma^2$である。$\operatorname{off}(G_k)$は$n(n-1)$個の項$(g^{(k)}_{ij})^2$（$i\ne j$）の和であり、$G_k$の対称性と対の選び方により各項は$\gamma^2$以下であるから、$\gamma^2\ge\operatorname{off}(G_k)/(n(n-1))$である。したがって$\operatorname{off}(G_{k+1})\le\theta_n\operatorname{off}(G_k)$であり、$G_0=A^{\mathsf T}A$から$k$に関する帰納法により後半が従う。

(3)を示す。$D_k$を$G_k$の対角成分を並べた対角行列とし、$E_k:=G_k-D_k$と置く。$D_k$の対角成分は$A_k$の列のノルムの二乗であり、$E_k$は対称であって、§E20.6 補題 2.1 (1)により$\lVert E_k\rVert_2\le\lVert E_k\rVert_F=\operatorname{off}(G_k)^{1/2}$である。§E20.8 定理 4.3を$D_k$と$E_k$に適用すると、$1\le j\le n$について$\lvert\lambda_j(G_k)-\lambda_j(D_k)\rvert\le\operatorname{off}(G_k)^{1/2}$であり、$\lambda_{n+1-i}(D_k)=\nu_{k,i}^2$である。(1)により$\det(tI-G_k)=\det(tI-A^{\mathsf T}A)$である。§D3.18 定理 1.2の分解$A=U\Sigma V_A^{\mathsf T}$をとると$A^{\mathsf T}A=V_A\Sigma^{\mathsf T}\Sigma V_A^{\mathsf T}$であり、$\Sigma^{\mathsf T}\Sigma=\operatorname{diag}(\sigma_1(A)^2,\dots,\sigma_p(A)^2,0,\dots,0)$であるから、$\lambda_{n+1-i}(G_k)$は$1\le i\le p$ならば$\sigma_i(A)^2$、$p<i\le n$ならば$0$である。$j=n+1-i$と置いて主張を得る。

(4)を示す。直交行列の各列は単位ベクトルであるから、$V_k$の各成分の絶対値は$1$以下である。§D1.8 定理 2.2を$n^2$個の成分に順に適用して部分列をとり直すと、収束する部分列が得られる。収束する任意の部分列を$(V_{k_l})_{l\ge1}$、その極限を$V$とする。行列の積の成分は成分の多項式であるから、$V^{\mathsf T}V=\lim_lV_{k_l}^{\mathsf T}V_{k_l}=I_n$であり、(1)により$V^{\mathsf T}A^{\mathsf T}AV=\lim_lG_{k_l}$である。$\operatorname{off}$は成分の多項式であり、$n\ge2$から$0\le\theta_n<1$であるので、(2)により

である。したがって$(AV)^{\mathsf T}(AV)$は対角行列であり、$AV$の列は互いに直交する。

$v_1,\dots,v_n$は直交行列$V$の列を並べ替えたものであるから、$\R^n$の正規直交基底である。$Av_1,\dots,Av_n$は互いに直交し、そのうち$0$でないものは$Av_1,\dots,Av_r$である。互いに直交する$0$でないベクトルは一次独立であるから$r\le m$であり、$r\le n$と合わせて$r\le p$である。$u_1,\dots,u_r$は正規直交系であり、これを延長した正規直交基底$u_1,\dots,u_m$が存在する。$U:=(u_1\ \cdots\ u_m)$、$V':=(v_1\ \cdots\ v_n)$と置き、$(i,i)$成分が$w_i$（$1\le i\le p$）でその他の成分が$0$の$\Sigma\in\R^{m\times n}$をとる。$U\Sigma$の第$i$列は、$i\le r$ならば$w_iu_i=Av_i$、$r<i\le p$ならば$w_iu_i=0=Av_i$、$i>p$ならば$0=Av_i$であるから、$U\Sigma=AV'$であり、$A=U\Sigma V'^{\mathsf T}=\sum_{i=1}^rw_iu_iv_i^{\mathsf T}$である。$U$、$V'$は直交行列であり、$w_1\ge\dots\ge w_p\ge0$であるから、この分解は§D3.18 定理 1.2の形であり、§D3.18 命題 2.1により$\sigma_i(A)=w_i$（$1\le i\le p$）である。§D3.18 定理 1.2により正の特異値の個数は$\operatorname{rank}A$であるから、$r=\operatorname{rank}A$である。▨