3-5.減少QR法運算-Hessenberg矩陣的Implicit Multishift
前一篇\( Double Shift \)文章取矩陣\(H\)的右下角\(2 \times 2\)子矩陣得到2個特徵值\( \mu_1,\mu_2 \)，以\((H-\mu_1I)(H-\mu_2I)\)來計算\(QR\)分解。
而\(Multishift\)則是取矩陣\(H\)的右下角\(k \times k\)子矩陣得到\(k\)個特徵值\(\mu_1,\mu_2,\ldots,\mu_{k}\)，以\((H-\mu_1I)(H-\mu_2I)...(H-\mu_{k}I)\)來計算\(QR\)分解。
\(k\)個特徵值中若\(\mu\)為實數則直接計算\((H-\mu I)\)，若\(\mu,\overline{\mu}\)互為共軛複數，則計算\((H-\mu I)(H-\overline{\mu}I)=H^2-2Re(\mu)H+|\; \mu |\;^2I\)以避免複數運算。
以\(n=9\)舉例說明
將\(A\)矩陣轉換成\(Hessenberg\)矩陣
\( A=\left[ \matrix{\times & \times & \times & \times & \times & \times & \times & \times & \times \cr
\times & \times & \times & \times & \times & \times & \times & \times & \times \cr
\times & \times & \times & \times & \times & \times & \times & \times & \times \cr
\times & \times & \times & \times & \times & \times & \times & \times & \times \cr
\times & \times & \times & \times & \times & \times & \times & \times & \times \cr
\times & \times & \times & \times & \times & \times & \times & \times & \times \cr
\times & \times & \times & \times & \times & \times & \times & \times & \times \cr
\times & \times & \times & \times & \times & \times & \times & \times & \times \cr
\times & \times & \times & \times & \times & \times & \times & \times & \times} \right] \Rightarrow H=\left[ \matrix{\times & \times & \times & \times & \times & \times & \times & \times & \times \cr
\times & \times & \times & \times & \times & \times & \times & \times & \times \cr
0 & \times & \times & \times & \times & \times & \times & \times & \times \cr
0 & 0 & \times & \times & \times & \times & \times & \times & \times \cr
0 & 0 & 0 & \times & \times & \times & \times & \times & \times \cr
0 & 0 & 0 & 0 & \times & \times & \times & \times & \times \cr
0 & 0 & 0 & 0 & 0 & \times & \times & \times & \times \cr
0 & 0 & 0 & 0 & 0 & 0 & \times & \times & \times \cr
0 & 0 & 0 & 0 & 0 & 0 & 0 & \times & \times} \right] \)
取\(H\)右下角\(4 \times 4\)子矩陣\(T=\left[ \matrix{\times & \times & \times & \times \cr \times & \times & \times & \times \cr 0 & \times & \times & \times \cr 0 & 0 & \times & \times} \right]\)為例
計算\(det(T-\mu I)=0\)，得到4個特徵值\(\mu=\mu_1,\mu_2,\mu_3,\mu_4\)
計算\((H-\mu_1I)(H-\mu_2I)(H-\mu_3I)(H-\mu_4I)e1=\left[ \matrix{\times \cr \times \cr \times \cr \times \cr \times \cr 0 \cr 0 \cr 0 \cr 0} \right]\)
其中\(e1\)為第一元為1，其餘為0的向量，換句話說就是取\( (H-\mu_1I)(H-\mu_2I)(H-\mu_3I)(H-\mu_4I) \)相乘後的第1行
取前5個非0元形成向量\( \left[ \matrix{\times \cr \times \cr \times \cr \times \cr \times} \right] \)找一個\( 5\times 5 Householder \)矩陣\( \hat{P_0} \)，使得\( \hat{P_0}\left[ \matrix{\times \cr \times \cr \times \cr \times \cr \times} \right]=\left[ \matrix{* \cr 0 \cr 0 \cr 0 \cr 0} \right] \)
設\( P_0=diag(\hat{P_0},I_4) \)，計算\( H_0=P_0^T H P_0 =\left[\matrix{
\times & \times & \times & \times & \times & \times & \times & \times & \times \cr
\times & \times & \times & \times & \times & \times & \times & \times & \times \cr
+ & \times & \times & \times & \times & \times & \times & \times & \times \cr
+ & + & \times & \times & \times & \times & \times & \times & \times \cr
+ & + & + & \times & \times & \times & \times & \times & \times \cr
+ & + & + & + & \times & \times & \times & \times & \times \cr
0 & 0 & 0 & 0 & 0 & \times & \times & \times & \times \cr
0 & 0 & 0 & 0 & 0 & 0 & \times & \times & \times \cr
0 & 0 & 0 & 0 & 0 & 0 & 0 & \times & \times} \right] \) 其中\( \matrix{+& & & \cr + & + & & \cr + &+&+&\cr + & + & +&+} \)形成凸起(bulge)
接下來將凸起往右下角推
取向量\( \left[ \matrix{H_0[2,1] \cr H_0[3,1] \cr H_0[4,1] \cr H_0[5,1] \cr H_0[6,1]} \right]=\left[ \matrix{\times \cr + \cr + \cr + \cr +} \right] \)找一個\( 5\times 5 Householder \)矩陣\( \hat{P_1} \)，使得\( \hat{P_1}\left[ \matrix{\times \cr + \cr + \cr + \cr +} \right]=\left[ \matrix{* \cr 0 \cr 0 \cr 0 \cr 0} \right] \)
設\( P_1=diag(I_1,\hat{P_1},I_3) \)，計算\( H_1=P_1^T H_0 P_1 =\left[\matrix{
\times & \times & \times & \times & \times & \times & \times & \times & \times \cr
\times & \times & \times & \times & \times & \times & \times & \times & \times \cr
0 & \times & \times & \times & \times & \times & \times & \times & \times \cr
0 & + & \times & \times & \times & \times & \times & \times & \times \cr
0 & + & + & \times & \times & \times & \times & \times & \times \cr
0 & + & + & + & \times & \times & \times & \times & \times \cr
0 & + & + & + & + & \times & \times & \times & \times \cr
0 & 0 & 0 & 0 & 0 & 0 & \times & \times & \times \cr
0 & 0 & 0 & 0 & 0 & 0 & 0 & \times & \times} \right] \) 將凸起\( \matrix{+& & & \cr + & + & & \cr + &+&+&\cr + & + & +&+} \)往右下角推
取向量\( \left[ \matrix{H_1[3,2] \cr H_1[4,2] \cr H_1[5,2] \cr H_1[6,2] \cr H_1[7,2]} \right]=\left[ \matrix{\times \cr + \cr + \cr + \cr +} \right] \)找一個\( 5\times 5 Householder \)矩陣\( \hat{P_2} \)，使得\( \hat{P_2}\left[ \matrix{\times \cr + \cr + \cr + \cr +} \right]=\left[ \matrix{* \cr 0 \cr 0 \cr 0 \cr 0} \right] \)
設\( P_2=diag(I_2,\hat{P_2},I_2) \)，計算\( H_2=P_2^T H_1 P_2 =\left[\matrix{
\times & \times & \times & \times & \times & \times & \times & \times & \times \cr
\times & \times & \times & \times & \times & \times & \times & \times & \times \cr
0 & \times & \times & \times & \times & \times & \times & \times & \times \cr
0 & 0 & \times & \times & \times & \times & \times & \times & \times \cr
0 & 0 & + & \times & \times & \times & \times & \times & \times \cr
0 & 0 & + & + & \times & \times & \times & \times & \times \cr
0 & 0 & + & + & + & \times & \times & \times & \times \cr
0 & 0 & + & + & + & + & \times & \times & \times \cr
0 & 0 & 0 & 0 & 0 & 0 & 0 & \times & \times} \right] \) 將凸起\( \matrix{+& & & \cr + & + & & \cr + &+&+&\cr + & + & +&+} \)往右下角推
取向量\( \left[ \matrix{H_2[4,3] \cr H_2[5,3] \cr H_2[6,3] \cr H_2[7,3] \cr H_2[8,3]} \right]=\left[ \matrix{\times \cr + \cr + \cr + \cr +} \right] \)找一個\( 5\times 5 Householder \)矩陣\( \hat{P_3} \)，使得\( \hat{P_3}\left[ \matrix{\times \cr + \cr + \cr + \cr +} \right]=\left[ \matrix{* \cr 0 \cr 0 \cr 0 \cr 0} \right] \)
設\( P_3=diag(I_3,\hat{P_3},I_1) \)，計算\( H_3=P_3^T H_2 P_3 =\left[\matrix{
\times & \times & \times & \times & \times & \times & \times & \times & \times \cr
\times & \times & \times & \times & \times & \times & \times & \times & \times \cr
0 & \times & \times & \times & \times & \times & \times & \times & \times \cr
0 & 0 & \times & \times & \times & \times & \times & \times & \times \cr
0 & 0 & 0 & \times & \times & \times & \times & \times & \times \cr
0 & 0 & 0 & + & \times & \times & \times & \times & \times \cr
0 & 0 & 0 & + & + & \times & \times & \times & \times \cr
0 & 0 & 0 & + & + & + & \times & \times & \times \cr
0 & 0 & 0 & + & + & + & + & \times & \times} \right] \) 將凸起\( \matrix{+& & & \cr + & + & & \cr + &+&+&\cr + & + & +&+} \)往右下角推
取向量\( \left[ \matrix{H_3[5,4] \cr H_3[6,4] \cr H_3[7,4] \cr H_3[8,4] \cr H_2[9,4]} \right]=\left[ \matrix{\times \cr + \cr + \cr + \cr +} \right] \)找一個\( 5\times 5 Householder \)矩陣\( \hat{P_4} \)，使得\( \hat{P_4}\left[ \matrix{\times \cr + \cr + \cr + \cr +} \right]=\left[ \matrix{* \cr 0 \cr 0 \cr 0 \cr 0} \right] \)
設\( P_4=diag(I_4,\hat{P_4}) \)，計算\( H_4=P_4^T H_3 P_4 =\left[\matrix{
\times & \times & \times & \times & \times & \times & \times & \times & \times \cr
\times & \times & \times & \times & \times & \times & \times & \times & \times \cr
0 & \times & \times & \times & \times & \times & \times & \times & \times \cr
0 & 0 & \times & \times & \times & \times & \times & \times & \times \cr
0 & 0 & 0 & \times & \times & \times & \times & \times & \times \cr
0 & 0 & 0 & 0 & \times & \times & \times & \times & \times \cr
0 & 0 & 0 & 0 & + & \times & \times & \times & \times \cr
0 & 0 & 0 & 0 & + & + & \times & \times & \times \cr
0 & 0 & 0 & 0 & + & + & + & \times & \times} \right] \) 將凸起\( \matrix{+& & \cr +&+& \cr +&+&+} \)往右下角推
取向量\( \left[ \matrix{H_4[6,5] \cr H_4[7,5] \cr H_4[8,5] \cr H_4[9,5]} \right]=\left[ \matrix{\times \cr + \cr + \cr +} \right] \)找一個\( 4\times 4 Householder \)矩陣\( \hat{P_5} \)，使得\( \hat{P_5}\left[ \matrix{\times \cr + \cr + \cr +} \right]=\left[ \matrix{* \cr 0 \cr 0 \cr 0} \right] \)
設\( P_5=diag(I_5,\hat{P_5}) \)，計算\( H_5=P_5^T H_4 P_5 =\left[\matrix{
\times & \times & \times & \times & \times & \times & \times & \times & \times \cr
\times & \times & \times & \times & \times & \times & \times & \times & \times \cr
0 & \times & \times & \times & \times & \times & \times & \times & \times \cr
0 & 0 & \times & \times & \times & \times & \times & \times & \times \cr
0 & 0 & 0 & \times & \times & \times & \times & \times & \times \cr
0 & 0 & 0 & 0 & \times & \times & \times & \times & \times \cr
0 & 0 & 0 & 0 & 0 & \times & \times & \times & \times \cr
0 & 0 & 0 & 0 & 0 & + & \times & \times & \times \cr
0 & 0 & 0 & 0 & 0 & + & + & \times & \times} \right] \) 將凸起\( \matrix{+& \cr +&+} \)往右下角推
取向量\( \left[ \matrix{H_5[7,6] \cr H_5[8,6] \cr H_5[9,6]} \right]=\left[ \matrix{\times \cr + \cr +} \right] \)找一個\( 3\times 3 Householder \)矩陣\( \hat{P_6} \)，使得\( \hat{P_6}\left[ \matrix{\times \cr + \cr +} \right]=\left[ \matrix{* \cr 0 \cr 0} \right] \)
設\( P_6=diag(I_6,\hat{P_6}) \)，計算\( H_6=P_6^T H_5 P_6 =\left[\matrix{
\times & \times & \times & \times & \times & \times & \times & \times & \times \cr
\times & \times & \times & \times & \times & \times & \times & \times & \times \cr
0 & \times & \times & \times & \times & \times & \times & \times & \times \cr
0 & 0 & \times & \times & \times & \times & \times & \times & \times \cr
0 & 0 & 0 & \times & \times & \times & \times & \times & \times \cr
0 & 0 & 0 & 0 & \times & \times & \times & \times & \times \cr
0 & 0 & 0 & 0 & 0 & \times & \times & \times & \times \cr
0 & 0 & 0 & 0 & 0 & 0 & \times & \times & \times \cr
0 & 0 & 0 & 0 & 0 & 0 & + & \times & \times} \right] \) 將凸起\(+\)往右下角推
取向量\( \left[ \matrix{H_6[8,7] \cr H_6[9,7]} \right]=\left[ \matrix{\times \cr +} \right] \)找一個\( 2\times 2 Householder \)矩陣\( \hat{P_7} \)，使得\( \hat{P_7}\left[ \matrix{\times \cr +} \right]=\left[ \matrix{* \cr 0} \right] \)
設\( P_7=diag(I_7,\hat{P_7}) \)，計算\( H_7=P_7^T H_6 P_7 =\left[\matrix{
\times & \times & \times & \times & \times & \times & \times & \times & \times \cr
\times & \times & \times & \times & \times & \times & \times & \times & \times \cr
0 & \times & \times & \times & \times & \times & \times & \times & \times \cr
0 & 0 & \times & \times & \times & \times & \times & \times & \times \cr
0 & 0 & 0 & \times & \times & \times & \times & \times & \times \cr
0 & 0 & 0 & 0 & \times & \times & \times & \times & \times \cr
0 & 0 & 0 & 0 & 0 & \times & \times & \times & \times \cr
0 & 0 & 0 & 0 & 0 & 0 & \times & \times & \times \cr
0 & 0 & 0 & 0 & 0 & 0 & 0 & \times & \times} \right] \) 仍是\(Hessenberg\)矩陣
－－－－－－－－－－－－－－－－－－－－－－－－－－－
虛擬碼
Householder(X)
{
\( e1 \)為第1元為1,其餘為0的向量
定義\( sign(x_1)=+1 \)若\( x_1 \ge 0 \)
\( sign(x_1)=-1 \)若\( x_1 <0 \)
\( \displaystyle v=\frac{x+sign(x_1)\Vert\; x \Vert\; e1}{\Vert\; x+sign(x_1)\Vert\; x \Vert\; e1 \Vert\;} \)，其中\( \Vert\; * \Vert\; \)為向量長度
Householder矩陣\(H=I-2vv^T \)
\( return(H) \)
}
theFirstColumnofΠk(H,Bulge)
{
\(H\)為\(n \times n\)的\(Hessenberg\)矩陣，取右下角\(Bulge \times Bulge\)子矩陣\(T\)
計算子矩陣\(T\)的特徵值\(\lambda=\mu_1,\mu_2,\ldots,\mu_{Bulge}\)
若特徵值\(\mu\)為實數則計算\((H-\mu I)\)
若特徵值\(\mu,\overline{\mu}\)為共軛複數則計算\((H-\mu I)(H-\overline{\mu}I)=H^2-2Re(\mu)H+|\;\mu|\;^2I\)
\(Column1=(H-\mu_1I)(H-\mu_2I)\ldots(H-\mu_{Bulge}I)e_1\)，其中\(e_1=\left[\matrix{1 \cr 0 \cr \vdots \cr 0} \right]\)
換句話說取\( \displaystyle \prod_{i=1}^{Bulge}(H-\mu_i I)\)的第一行向量
取\(Column1\)前\(Bulge+1\)個非零0元得到向量\(X\)
}
HessenbergImplicitMultishift(H,Bulge)
{
計算\( \displaystyle \prod_{i=1}^{Bulge}(H-\mu_i I)\)的第一行向量
theFirstColumnofΠk(H,Bulge)
for k=0 ~ (n-2)
{\(\hat{P_k}=Householder(X)\)，找一個\(Householder\)矩陣\(\hat{P_k}\)，使得\(\hat{P_k}X=\left[ \matrix{* \cr 0 \cr \vdots \cr 0} \right]\)，*為非零數字
\(P_k=diag(I_k,\hat{P_k},I_{n-Bulge-1-k})\)
\(H=P_k^THP_k\)
if \(k=n-2\) then，已將凸起完全消除
{\(return(H)\)，\(H\)仍是\(Hessenberg\)矩陣
}
若\(k=0 \sim (n-Bulge-2)\)
{\(Xrows=Bulge+1\)}
若\(k=(n-Bulge-1) \sim(n-3)\)
{\(Xrows=n-k-1\)}
取\(X=\left[ \matrix{H[k+1+1,k+1] \cr H[k+1+2,k+1] \cr \vdots \cr H[k+1+Xrows,k+1]} \right]\)做為下一次Householder(X)使用
}
}
－－－－－－－－－－－－－－－－－－－－－－－－－－－
參考資料
Z. Bai and J.W. Demmel(1989). "On a Block Implementation of Hessenberg Multishift QR Iteration," Int. J. High Speed Comput. 1,97-112.
http://www.netlib.org/lapack/lawnspdf/lawn08.pdf
要先載入diag才能使用diag指令
(%i1) load(diag);
(%o1) C:\maxima-5.41.0\share\maxima\5.41.0\share\contrib\diag.mac
轉換成Householder矩陣副程式
(%i2)
Householder(X):=block
([n,e1,normx,v,normv,P_hat],
n:length(X),
if X=zeromatrix(n,1) then
(print("X為0向量,H=",ident(n)),
return(ident(n))
),
if X[1,1]>=0 then sign:+1 else sign:-1,
print("X向量=",X,"第1元=",X[1,1]," , sign(X_1)=",sign,",長度∥X∥=sqrt(",X,".",X,")=",normx:ratsimp(sqrt(X.X))),
print("第1元是1,其餘為0的向量e1=",e1:genmatrix(lambda([i,j],if i=1 then 1 else 0),n,1)),
print("X+sign(X_1)*∥X∥*e1=",X,"+",sign,"*",normx,"*",e1,"=",v:X+sign*normx*e1),
print("長度∥X+sign(X_1)*∥X∥*e1∥=sqrt(",v,".",v,")=",normv:ratsimp(sqrt(v.v))),
print("v=",v,"/",normv,"=",v:ratsimp(v/normv)),
print(" P_hat=I-2*v.v^T=",ident(n),"-2*",v,".",transpose(v),"=",P_hat:ratsimp(ident(n)-2*v.transpose(v))),
return(P_hat)
)$
計算(H-u1I)(H-u2I)...(H-ukI)第一行
(%i3)
theFirstColumnofΠk(H,Bulge):=block
([n:length(H),T,equation,column1,mu,eigenvalue,realpart,cabs,HH,X],
print("取H矩陣右下角",Bulge,"*",Bulge,"子矩陣T=",
T:genmatrix(lambda([i,j],H[n-Bulge+i,n-Bulge+j]),Bulge,Bulge)),
print("計算T的特徵值"),
print("det(T-μ*I)=0,",equation:T-%mu*ident(Bulge),"=0"),
print("展開行列式",equation:factor(determinant(equation)),"=0"),
print("特徵值μ=",eigenvalue:map(rhs,solve(equation,%mu))),
print("第1元為1,其餘為0的向量e1=column1=",column1:genmatrix(lambda([i,j],if i=1 then 1 else 0),n,1)),
for i:1 thru Bulge do
(mu:eigenvalue[ i ],
if numberp(mu)=true then
(print("當特徵值為實數μ=",mu),
print("計算column1=(H-",mu,"I).column1=",column1: (H-mu*ident(n)).column1)
)
else
(realpart:realpart(mu),
cabs:cabs(mu)^2,
print("當特徵值為共軛複數μ=",eigenvalue[ i ],",",eigenvalue[i+1],",Re(μ)=",realpart,",|μ|^2=",cabs),
print("column1=(H^2-2*(",realpart,")H+",cabs,"I).column1"),
HH:H.H-2*realpart*H+cabs*ident(n),
print("column1=",HH,".",column1,"=",column1:HH.column1),
i:i+1
)
),
print("column1=(H-μ1I)(H-μ2I)...(H-μ",Bulge,"I)e1=",column1),
print("擷取第1行前",Bulge+1,"元數字X=",X:genmatrix(lambda([i,j],column1[i,1]),Bulge+1,1)),
return(X)
)$
針對Hessenberg矩陣Implicit Multishift副程式
(%i4)
HessenbergImplicitMultishift(H,X):=block
([n:length(H),Bulge:length(X)-1,P_hat_k,P_k,Xrows:length(X)],
for k:0 thru n-2 do
(print("k=",k),
print("取向量",X,"找一個Householder矩陣P_hat_",k,",使得",P_hat_k:Householder(X),X,"=",P_hat_k.X),
if k=0 then
(P_k:diag([P_hat_k,ident(n-Bulge-1)]))
else if k>n-Bulge-2 then
(P_k:diag([ident(k),P_hat_k]))
else
(P_k:diag([ident(k),P_hat_k,ident(n-k-Bulge-1)])),
print("設P_",k,"=",P_k),
print("計算H_",k,"=P_",k,"^T.H_",k-1,".P_",k,"=",H:ratsimp(transpose(P_k).H.P_k)),
if k=n-2 then
(numer:false,
return(H)
),
if k+Bulge>n-2 then
(Xrows:n-k-1),
print("取向量",genmatrix(lambda([i,j],concat("H",k,"[",i+k+1,",",k+1,"]")),Xrows,1),"=",
X:genmatrix(lambda([i,j],H[i+k+1,k+1]),Xrows,1)),
print("------------------------"),
if numer=false and ratnump(sqrt(X.X))=false then
(print("向量X長度=",sqrt(X.X),"不是完全平方數,改用浮點數計算"),
numer:true,
ratprint:false
)
)
)$
Hessenberg矩陣
(%i5)
H:matrix([-2,1,-1, 1,2,-2/3,-3,0,29/6],
[-1,-1,1,2,-2,1,2/3,-5/2,-23/6],
[0,-1,1,2,-1,1,6,-8/3,-65/6],
[0,0,-1,-2,0,3,-1,7/2,10/3],
[0,0,0,-1,-1,2,-1,-1,-4],
[0,0,0,0,-2,1,2,2,-1],
[0,0,0,0,0,-1,-2,0,1],
[0,0,0,0,0,0,1,-1,-2],
[0,0,0,0,0,0,0,1,-1] );
(%o5) \( \left[ \matrix{\displaystyle -2&1&-1&1&2&-\frac{2}{3}&-3&0&\frac{29}{6}\cr
-1&-1&1&2&-2&1&\frac{2}{3}&-\frac{5}{2}&-\frac{23}{6}\cr
0&-1&1&2&-1&1&6&-\frac{8}{3}&-\frac{65}{6}\cr
0&0&-1&-2&0&3&-1&\frac{7}{2}&\frac{10}{3}\cr
0&0&0&-1&-1&2&-1&-1&-4\cr
0&0&0&0&-2&1&2&2&-1\cr
0&0&0&0&0&-1&-2&0&1\cr
0&0&0&0&0&0&1&-1&-2\cr
0&0&0&0&0&0&0&1&-1} \right] \)
取H右下角4*4矩陣計算特徵值，計算(H-u1I)(H-u2I)...(H-u4I)第一行
(%i6) X:theFirstColumnofΠk(H,4);
取\(H\)矩陣右下角\(4*4\)子矩陣\(T=\left[ \matrix{1&2&2&-1 \cr-1&-2&0&1 \cr0&1&-1&-2 \cr0&0&1&-1}\right] \)
計算\(T\)的特徵值
\(det(T-\mu*I)=0,\left[ \matrix{1-\mu&2&2&-1 \cr-1&-\mu-2&0&1 \cr0&1&-\mu-1&-2 \cr0&0&1&-\mu-1}\right] \)=0
展開行列式\((\mu^2+\mu+1)(\mu^2+2\mu+2)=0\)
特徵值\( \displaystyle \mu=[-\%i-1,\%i-1,-\frac{\sqrt{3}\%i+1}{2},\frac{\sqrt{3}\%i-1}{2} \)
第1元為1,其餘為0的向量\(e1=column1=\left[ \matrix{1 \cr0 \cr0 \cr0 \cr0 \cr0 \cr0 \cr0 \cr0}\right] \)
當特徵值為共軛複數\(\mu=-\%i-1,\%i-1,Re(\mu)=-1,|\; \mu |\;^2=2 \)
\(column1=(H^2-2*(-1)H+2I).column1\)
\(column1=\left[ \matrix{ \displaystyle 1&0&-1&-4&-\frac{5}{3}&\frac{28}{3}&-\frac{11}{3}&\frac{31}{6}&-\frac{29}{6} \cr1&-1&1&1&-5&5&\frac{47}{6}&\frac{9}{2}&\frac{11}{3} \cr1&-2&2&1&-2&1&\frac{11}{3}&-\frac{11}{3}&\frac{19}{6} \cr0&1&-1&0&-5&3&\frac{11}{2}&\frac{17}{2}&-\frac{7}{2} \cr0&0&1&1&-3&2&5&-\frac{7}{2}&-\frac{13}{3} \cr0&0&0&2&-4&-1&6&5&4 \cr0&0&0&0&2&-1&0&-1&0 \cr0&0&0&0&0&-1&-1&-1&1 \cr0&0&0&0&0&0&1&0&-1}\right].
\left[ \matrix{1 \cr0 \cr0 \cr0 \cr0 \cr0 \cr0 \cr0 \cr0}\right]=\left[ \matrix{ \displaystyle 1 \cr1 \cr1 \cr0 \cr0 \cr0 \cr0 \cr0 \cr0}\right] \)
當特徵值為共軛複數\( \displaystyle \mu=-\frac{\sqrt{3}\%i+1}{2},\frac{\sqrt{3}\%i-1}{2},Re(\mu)=-\frac{1}{2},|\; \mu |\;^2=1 \)
\(column1=(\displaystyle H^2-2*(-\frac{1}{2})H+1I).column1\)
\(column1=\left[ \matrix{ \displaystyle 2&-1&0&-5&-\frac{11}{3}&10&-\frac{2}{3}&\frac{31}{6}&-\frac{29}{3} \cr2&-1&0&-1&-3&4&\frac{43}{6}&7&\frac{15}{2} \cr1&-1&0&-1&-1&0&-\frac{7}{3}&-1&14 \cr0&1&0&1&-5&0&\frac{13}{2}&5&-\frac{41}{6} \cr0&0&1&2&-3&0&6&-\frac{5}{2}&-\frac{1}{3} \cr0&0&0&2&-2&-3&4&3&5 \cr0&0&0&0&2&0&1&-1&-1 \cr0&0&0&0&0&-1&-2&-1&3 \cr0&0&0&0&0&0&1&-1&-1}\right].
\left[ \matrix{ \displaystyle 1 \cr1 \cr1 \cr0 \cr0 \cr0 \cr0 \cr0 \cr0}\right]=
\left[ \matrix{ \displaystyle 1 \cr1 \cr0 \cr1 \cr1 \cr0 \cr0 \cr0 \cr0}\right] \)
\(column1=(H-\mu 1I)(H-\mu 2I)...(H-\mu 4I)e1=\left[ \matrix{ \displaystyle 1 \cr1 \cr0 \cr1 \cr1 \cr0 \cr0 \cr0 \cr0}\right] \)
擷取第1行前5元數字\(X=\left[ \matrix{ \displaystyle 1 \cr1 \cr0 \cr1 \cr1}\right]\)
(%o6) \(\left[ \matrix{1 \cr1 \cr0 \cr1 \cr1}\right] \)
(%i7) HessenbergImplicitMultishift(H,X);
\(k=0\)
\(X\)向量\(=\left[ \matrix{\displaystyle 1\cr 1\cr 0\cr 1\cr 1}\right]\)第1元\(=1,sign(X_1)=1\),長度\( \Vert\;X \Vert\;=sqrt(\left[ \matrix{\displaystyle 1\cr 1\cr 0\cr 1\cr 1}\right].\left[ \matrix{\displaystyle 1\cr 1\cr 0\cr 1\cr 1}\right] )=2\)
第1元是1,其餘為0的向量\( e1=\left[ \matrix{\displaystyle 1\cr 0\cr 0\cr 0\cr 0}\right] \)
\(X+sign(X_1)*\Vert\; X \Vert\;*e1=\left[ \matrix{\displaystyle 1\cr 1\cr 0\cr 1\cr 1}\right]+1*2*\left[ \matrix{\displaystyle 1\cr 0\cr 0\cr 0\cr 0}\right]=\left[ \matrix{\displaystyle 3\cr 1\cr 0\cr 1\cr 1}\right] \)
長度\(\Vert\; X+sign(X_1)*\Vert\; X \Vert\;*e1 \Vert\;=sqrt(\left[ \matrix{\displaystyle 3\cr 1\cr 0\cr 1\cr 1}\right].\left[ \matrix{\displaystyle 3\cr 1\cr 0\cr 1\cr 1}\right] )=2\sqrt{3} \)
\(v=\left[ \matrix{\displaystyle 3\cr 1\cr 0\cr 1\cr 1}\right]/2\sqrt{3}=\left[\matrix{\displaystyle \frac{\sqrt{3}}{2}\cr \frac{1}{2\sqrt{3}}\cr 0\cr \frac{1}{2\sqrt{3}}\cr \frac{1}{2\sqrt{3}}}\right] \)
\( \hat{P}=I-2*v.v^T=\left[ \matrix{\displaystyle 1&0&0&0&0\cr 0&1&0&0&0\cr 0&0&1&0&0\cr 0&0&0&1&0\cr 0&0&0&0&1}\right]-2*\left[ \matrix{\displaystyle \frac{\sqrt{3}}{2}\cr \frac{1}{2\sqrt{3}}\cr 0\cr \frac{1}{2\sqrt{3}}\cr \frac{1}{2\sqrt{3}}}\right].\left[ \matrix{\displaystyle \frac{\sqrt{3}}{2}&\frac{1}{2\sqrt{3}}&0&\frac{1}{2\sqrt{3}}&\frac{1}{2\sqrt{3}}}\right]=\left[ \matrix{\displaystyle -\frac{1}{2}&-\frac{1}{2}&0&-\frac{1}{2}&-\frac{1}{2}\cr -\frac{1}{2}&\frac{5}{6}&0&-\frac{1}{6}&-\frac{1}{6}\cr 0&0&1&0&0\cr -\frac{1}{2}&-\frac{1}{6}&0&\frac{5}{6}&-\frac{1}{6}\cr -\frac{1}{2}&-\frac{1}{6}&0&-\frac{1}{6}&\frac{5}{6}}\right] \)
取向量\( \left[ \matrix{\displaystyle 1\cr 1\cr 0\cr 1\cr 1}\right] \)找一個\(Householder\)矩陣\( \hat{P}_0\),使得\(\left[ \matrix{\displaystyle -\frac{1}{2}&-\frac{1}{2}&0&-\frac{1}{2}&-\frac{1}{2}\cr -\frac{1}{2}&\frac{5}{6}&0&-\frac{1}{6}&-\frac{1}{6}\cr 0&0&1&0&0\cr -\frac{1}{2}&-\frac{1}{6}&0&\frac{5}{6}&-\frac{1}{6}\cr -\frac{1}{2}&-\frac{1}{6}&0&-\frac{1}{6}&\frac{5}{6}}\right] \left[ \matrix{1\cr 1\cr 0\cr 1\cr 1}\right]=\left[ \matrix{\displaystyle -2\cr 0\cr 0\cr 0\cr 0}\right] \)
設\(P_0=\left[ \matrix{\displaystyle -\frac{1}{2}&-\frac{1}{2}&0&-\frac{1}{2}&-\frac{1}{2}&0&0&0&0\cr -\frac{1}{2}&\frac{5}{6}&0&-\frac{1}{6}&-\frac{1}{6}&0&0&0&0\cr 0&0&1&0&0&0&0&0&0\cr -\frac{1}{2}&-\frac{1}{6}&0&\frac{5}{6}&-\frac{1}{6}&0&0&0&0\cr -\frac{1}{2}&-\frac{1}{6}&0&-\frac{1}{6}&\frac{5}{6}&0&0&0&0\cr 0&0&0&0&0&1&0&0&0\cr 0&0&0&0&0&0&1&0&0\cr 0&0&0&0&0&0&0&1&0\cr 0&0&0&0&0&0&0&0&1}\right] \)
計算\(H_0=P_0^T.H_{-1}.P_0=\left[ \matrix{\displaystyle -1&-\frac{5}{6}&\frac{1}{2}&-\frac{5}{6}&-\frac{1}{3}&-\frac{8}{3}&\frac{13}{6}&0&-\frac{1}{6}\cr
1&-\frac{19}{18}&\frac{3}{2}&\frac{35}{18}&-\frac{20}{9}&\frac{1}{3}&\frac{43}{18}&-\frac{5}{2}&-\frac{11}{2}\cr
0&-1&1&2&-1&1&6&-\frac{8}{3}&-\frac{65}{6}\cr
1&-\frac{7}{18}&-\frac{1}{2}&-\frac{43}{18}&-\frac{5}{9}&\frac{7}{3}&\frac{13}{18}&\frac{7}{2}&\frac{5}{3}\cr
1&-\frac{7}{18}&\frac{1}{2}&-\frac{25}{18}&-\frac{14}{9}&\frac{4}{3}&\frac{13}{18}&-1&-\frac{17}{3}\cr 1&\frac{1}{3}&0&\frac{1}{3}&-\frac{5}{3}&1&2&2&-1\cr 0&0&0&0&0&-1&-2&0&1\cr 0&0&0&0&0&0&1&-1&-2\cr 0&0&0&0&0&0&0&1&-1}\right] \)
取向量\( \left[ \matrix{\displaystyle H0[2,1]\cr H0[3,1]\cr H0[4,1]\cr H0[5,1]\cr H0[6,1]}\right]=\left[ \matrix{\displaystyle 1\cr 0\cr 1\cr 1\cr 1}\right] \)
------------------------
\(k=1\)
\(X\)向量\(=\left[ \matrix{\displaystyle 1\cr 0\cr 1\cr 1\cr 1}\right] \)第1元\(=1,sign(X_1)=1\),長度\( \Vert\;X \Vert\;=sqrt(\left[ \matrix{\displaystyle 1\cr 0\cr 1\cr 1\cr 1}\right].\left[ \matrix{\displaystyle 1\cr 0\cr 1\cr 1\cr 1}\right] )=2\)
第1元是1,其餘為0的向量\( e1=\left[ \matrix{\displaystyle 1\cr 0\cr 0\cr 0\cr 0}\right] \)
\(X+sign(X_1)*\Vert\; X \Vert\;*e1=\left[ \matrix{\displaystyle 1\cr 0\cr 1\cr 1\cr 1}\right]+1*2*\left[ \matrix{\displaystyle 1\cr 0\cr 0\cr 0\cr 0}\right]=\left[ \matrix{\displaystyle 3\cr 0\cr 1\cr 1\cr 1}\right] \)
長度\(\Vert\; X+sign(X_1)*\Vert\; X \Vert\;*e1 \Vert\;=sqrt(\left[ \matrix{\displaystyle 3\cr 0\cr 1\cr 1\cr 1}\right].\left[ \matrix{\displaystyle 3\cr 0\cr 1\cr 1\cr 1}\right] )=2\sqrt{3}\)
\(v=\left[ \matrix{\displaystyle 3\cr 0\cr 1\cr 1\cr 1}\right]/2\sqrt{3}=\left[ \matrix{\displaystyle \frac{\sqrt{3}}{2}\cr 0\cr \frac{1}{2\sqrt{3}}\cr \frac{1}{2\sqrt{3}}\cr \frac{1}{2\sqrt{3}}}\right] \)
\(\hat{P}=I-2*v.v^T=\left[ \matrix{\displaystyle 1&0&0&0&0\cr 0&1&0&0&0\cr 0&0&1&0&0\cr 0&0&0&1&0\cr 0&0&0&0&1}\right]-2*\left[ \matrix{\displaystyle \frac{\sqrt{3}}{2}\cr 0\cr \frac{1}{2\sqrt{3}}\cr \frac{1}{2\sqrt{3}}\cr \frac{1}{2\sqrt{3}}}\right].\left[ \matrix{\displaystyle \frac{\sqrt{3}}{2}&0&\frac{1}{2\sqrt{3}}&\frac{1}{2\sqrt{3}}&\frac{1}{2\sqrt{3}}}\right]=\left[\matrix{\displaystyle-\frac{1}{2}&0&-\frac{1}{2}&-\frac{1}{2}&-\frac{1}{2}\cr 0&1&0&0&0\cr -\frac{1}{2}&0&\frac{5}{6}&-\frac{1}{6}&-\frac{1}{6}\cr -\frac{1}{2}&0&-\frac{1}{6}&\frac{5}{6}&-\frac{1}{6}\cr -\frac{1}{2}&0&-\frac{1}{6}&-\frac{1}{6}&\frac{5}{6}}\right] \)
取向量\( \left[ \matrix{\displaystyle 1\cr 0\cr 1\cr 1\cr 1}\right] \)找一個\(Householder\)矩陣\(\hat{P}_1\),使得\(\left[ \matrix{\displaystyle -\frac{1}{2}&0&-\frac{1}{2}&-\frac{1}{2}&-\frac{1}{2}\cr 0&1&0&0&0\cr -\frac{1}{2}&0&\frac{5}{6}&-\frac{1}{6}&-\frac{1}{6}\cr -\frac{1}{2}&0&-\frac{1}{6}&\frac{5}{6}&-\frac{1}{6}\cr -\frac{1}{2}&0&-\frac{1}{6}&-\frac{1}{6}&\frac{5}{6}}\right] \left[ \matrix{1\cr 0\cr 1\cr 1\cr 1}\right]=\left[ \matrix{\displaystyle -2\cr 0\cr 0\cr 0\cr 0}\right] \)
設\(P_1=\left[ \matrix{\displaystyle 1&0&0&0&0&0&0&0&0\cr 0&-\frac{1}{2}&0&-\frac{1}{2}&-\frac{1}{2}&-\frac{1}{2}&0&0&0\cr 0&0&1&0&0&0&0&0&0\cr 0&-\frac{1}{2}&0&\frac{5}{6}&-\frac{1}{6}&-\frac{1}{6}&0&0&0\cr 0&-\frac{1}{2}&0&-\frac{1}{6}&\frac{5}{6}&-\frac{1}{6}&0&0&0\cr 0&-\frac{1}{2}&0&-\frac{1}{6}&-\frac{1}{6}&\frac{5}{6}&0&0&0\cr 0&0&0&0&0&0&1&0&0\cr 0&0&0&0&0&0&0&1&0\cr 0&0&0&0&0&0&0&0&1}\right] \)
計算\(H_1=P_1^T.H_0.P_1=\left[ \matrix{\displaystyle -1&\frac{7}{3}&\frac{1}{2}&\frac{2}{9}&\frac{13}{18}&-\frac{29}{18}&\frac{13}{6}&0&-\frac{1}{6}\cr -2&-1&-\frac{3}{4}&\frac{1}{6}&\frac{29}{12}&-\frac{37}{12}&-\frac{35}{12}&-1&\frac{21}{4}\cr 0&-\frac{1}{2}&1&\frac{13}{6}&-\frac{5}{6}&\frac{7}{6}&6&-\frac{8}{3}&-\frac{65}{6}\cr 0&0&-\frac{5}{4}&-\frac{463}{162}&\frac{361}{324}&\frac{427}{324}&-\frac{113}{108}&4&\frac{21}{4}\cr 0&\frac{1}{2}&-\frac{1}{4}&-\frac{137}{81}&\frac{91}{324}&\frac{157}{324}&-\frac{113}{108}&-\frac{1}{2}&-\frac{25}{12}\cr 0&-\frac{1}{2}&-\frac{3}{4}&-\frac{44}{81}&-\frac{131}{324}&-\frac{137}{324}&\frac{25}{108}&\frac{5}{2}&\frac{31}{12}\cr 0&\frac{1}{2}&0&\frac{1}{6}&\frac{1}{6}&-\frac{5}{6}&-2&0&1\cr 0&0&0&0&0&0&1&-1&-2\cr 0&0&0&0&0&0&0&1&-1}\right] \)
取向量\( \left[ \matrix{\displaystyle H1[3,2]\cr H1[4,2]\cr H1[5,2]\cr H1[6,2]\cr H1[7,2]}\right]=\left[ \matrix{\displaystyle -\frac{1}{2}\cr 0\cr \frac{1}{2}\cr -\frac{1}{2}\cr \frac{1}{2}}\right] \)
------------------------
\(k=2\)
\(X\)向量\(=\left[ \matrix{\displaystyle -\frac{1}{2}\cr 0\cr \frac{1}{2}\cr -\frac{1}{2}\cr \frac{1}{2}}\right] \)第1元\(\displaystyle =-\frac{1}{2},sign(X_1)=-1\),長度\( \Vert\;X \Vert\;=sqrt(\left[ \matrix{\displaystyle -\frac{1}{2}\cr 0\cr \frac{1}{2}\cr -\frac{1}{2}\cr \frac{1}{2}}\right].\left[ \matrix{\displaystyle -\frac{1}{2}\cr 0\cr \frac{1}{2}\cr -\frac{1}{2}\cr \frac{1}{2}}\right] )=1\)
第1元是1,其餘為0的向量\( e1=\left[ \matrix{\displaystyle 1\cr 0\cr 0\cr 0\cr 0}\right] \)
\(X+sign(X_1)*\Vert\; X \Vert\;*e1=\left[ \matrix{\displaystyle -\frac{1}{2}\cr 0\cr \frac{1}{2}\cr -\frac{1}{2}\cr \frac{1}{2}}\right]+-1*1*\left[ \matrix{\displaystyle 1\cr 0\cr 0\cr 0\cr 0}\right]=\left[ \matrix{\displaystyle -\frac{3}{2}\cr 0\cr \frac{1}{2}\cr -\frac{1}{2}\cr \frac{1}{2}}\right] \)
長度\(\Vert\; X+sign(X_1)*\Vert\; X \Vert\;*e1 \Vert\;=sqrt(\left[ \matrix{\displaystyle -\frac{3}{2}\cr 0\cr \frac{1}{2}\cr -\frac{1}{2}\cr \frac{1}{2}}\right].\left[ \matrix{\displaystyle -\frac{3}{2}\cr 0\cr \frac{1}{2}\cr -\frac{1}{2}\cr \frac{1}{2}}\right] )=\sqrt{3}\)
\(v=\left[ \matrix{\displaystyle -\frac{3}{2}\cr 0\cr \frac{1}{2}\cr -\frac{1}{2}\cr \frac{1}{2}}\right]/\sqrt{3}=\left[ \matrix{\displaystyle -\frac{\sqrt{3}}{2}\cr 0\cr \frac{1}{2\sqrt{3}}\cr -\frac{1}{2\sqrt{3}}\cr \frac{1}{2\sqrt{3}}}\right] \)
\(\hat{P}=I-2*v.v^T=\left[ \matrix{\displaystyle 1&0&0&0&0\cr 0&1&0&0&0\cr 0&0&1&0&0\cr 0&0&0&1&0\cr 0&0&0&0&1}\right]-2*\left[ \matrix{\displaystyle -\frac{\sqrt{3}}{2}\cr 0\cr \frac{1}{2\sqrt{3}}\cr -\frac{1}{2\sqrt{3}}\cr \frac{1}{2\sqrt{3}}}\right].\left[ \matrix{\displaystyle -\frac{\sqrt{3}}{2}&0&\frac{1}{2\sqrt{3}}&-\frac{1}{2\sqrt{3}}&\frac{1}{2\sqrt{3}}}\right]=\left[\matrix{\displaystyle -\frac{1}{2}&0&\frac{1}{2}&-\frac{1}{2}&\frac{1}{2}\cr 0&1&0&0&0\cr \frac{1}{2}&0&\frac{5}{6}&\frac{1}{6}&-\frac{1}{6}\cr -\frac{1}{2}&0&\frac{1}{6}&\frac{5}{6}&\frac{1}{6}\cr \frac{1}{2}&0&-\frac{1}{6}&\frac{1}{6}&\frac{5}{6}}\right] \)
取向量\( \left[ \matrix{\displaystyle -\frac{1}{2}\cr 0\cr \frac{1}{2}\cr -\frac{1}{2}\cr \frac{1}{2}}\right]\)找一個\(Householder\)矩陣\( \hat{P}_2\),使得\(\left[ \matrix{\displaystyle -\frac{1}{2}&0&\frac{1}{2}&-\frac{1}{2}&\frac{1}{2}\cr 0&1&0&0&0\cr \frac{1}{2}&0&\frac{5}{6}&\frac{1}{6}&-\frac{1}{6}\cr -\frac{1}{2}&0&\frac{1}{6}&\frac{5}{6}&\frac{1}{6}\cr \frac{1}{2}&0&-\frac{1}{6}&\frac{1}{6}&\frac{5}{6}}\right] \left[ \matrix{\displaystyle -\frac{1}{2}\cr 0\cr \frac{1}{2}\cr -\frac{1}{2}\cr \frac{1}{2}}\right]=\left[ \matrix{\displaystyle 1\cr 0\cr 0\cr 0\cr 0}\right] \)
設\(P_2=\left[ \matrix{\displaystyle 1&0&0&0&0&0&0&0&0\cr 0&1&0&0&0&0&0&0&0\cr 0&0&-\frac{1}{2}&0&\frac{1}{2}&-\frac{1}{2}&\frac{1}{2}&0&0\cr 0&0&0&1&0&0&0&0&0\cr 0&0&\frac{1}{2}&0&\frac{5}{6}&\frac{1}{6}&-\frac{1}{6}&0&0\cr 0&0&-\frac{1}{2}&0&\frac{1}{6}&\frac{5}{6}&\frac{1}{6}&0&0\cr 0&0&\frac{1}{2}&0&-\frac{1}{6}&\frac{1}{6}&\frac{5}{6}&0&0\cr 0&0&0&0&0&0&0&1&0\cr 0&0&0&0&0&0&0&0&1}\right] \)
計算\(H_2=P_2^T.H_1.P_2=\left[ \matrix{\displaystyle -1&\frac{7}{3}&2&\frac{2}{9}&\frac{2}{9}&-\frac{10}{9}&\frac{5}{3}&0&-\frac{1}{6}\cr -2&-1&\frac{5}{3}&\frac{1}{6}&\frac{29}{18}&-\frac{41}{18}&-\frac{67}{18}&-1&\frac{21}{4}\cr 0&1&-\frac{3}{2}&-\frac{85}{54}&\frac{34}{27}&-\frac{26}{27}&-\frac{38}{9}&-\frac{1}{6}&\frac{43}{12}\cr
0&0&0&-\frac{463}{162}&\frac{113}{162}&\frac{281}{162}&-\frac{79}{54}&4&\frac{21}{4}\cr 0&0&\frac{1}{2}&-\frac{4}{9}&-\frac{7}{18}&\frac{7}{6}&\frac{43}{18}&-\frac{4}{3}&-\frac{62}{9}\cr 0&0&-\frac{1}{2}&-\frac{145}{81}&-\frac{11}{162}&-\frac{125}{162}&-\frac{191}{54}&\frac{10}{3}&\frac{133}{18}\cr 0&0&\frac{1}{2}&\frac{229}{162}&-\frac{34}{81}&-\frac{19}{81}&\frac{41}{27}&-\frac{5}{6}&-\frac{137}{36}\cr 0&0&\frac{1}{2}&0&-\frac{1}{6}&\frac{1}{6}&\frac{5}{6}&-1&-2\cr 0&0&0&0&0&0&0&1&-1}\right] \)
取向量\( \left[ \matrix{\displaystyle H2[4,3]\cr H2[5,3]\cr H2[6,3]\cr H2[7,3]\cr H2[8,3]}\right]=\left[ \matrix{\displaystyle 0\cr \frac{1}{2}\cr -\frac{1}{2}\cr \frac{1}{2}\cr \frac{1}{2}}\right] \)
------------------------
\(k=3\)
\(X\)向量\(=\left[ \matrix{\displaystyle 0\cr \frac{1}{2}\cr -\frac{1}{2}\cr \frac{1}{2}\cr \frac{1}{2}}\right]\)第1元\(=0,sign(X_1)=1\),長度\( \Vert\;X \Vert\;=sqrt(\left[ \matrix{\displaystyle 0\cr \frac{1}{2}\cr -\frac{1}{2}\cr \frac{1}{2}\cr \frac{1}{2}}\right].\left[ \matrix{\displaystyle 0\cr \frac{1}{2}\cr -\frac{1}{2}\cr \frac{1}{2}\cr \frac{1}{2}}\right] )=1 \)
第1元是1,其餘為0的向量\( e1=\left[ \matrix{\displaystyle 1\cr 0\cr 0\cr 0\cr 0}\right] \)
\(X+sign(X_1)*\Vert\; X \Vert\;*e1=\left[ \matrix{\displaystyle 0\cr \frac{1}{2}\cr -\frac{1}{2}\cr \frac{1}{2}\cr \frac{1}{2}}\right]+1*1*\left[ \matrix{\displaystyle 1\cr 0\cr 0\cr 0\cr 0}\right]=\left[ \matrix{\displaystyle 1\cr \frac{1}{2}\cr -\frac{1}{2}\cr \frac{1}{2}\cr \frac{1}{2}}\right] \)
長度\(\Vert\; X+sign(X_1)*\Vert\; X \Vert\;*e1 \Vert\;=sqrt(\left[ \matrix{\displaystyle 1\cr \frac{1}{2}\cr -\frac{1}{2}\cr \frac{1}{2}\cr \frac{1}{2}}\right].\left[ \matrix{\displaystyle 1\cr \frac{1}{2}\cr -\frac{1}{2}\cr \frac{1}{2}\cr \frac{1}{2}}\right] )=\sqrt{2} \)
\(v=\left[ \matrix{\displaystyle 1\cr \frac{1}{2}\cr -\frac{1}{2}\cr \frac{1}{2}\cr \frac{1}{2}}\right]/\sqrt{2}=\left[ \matrix{\displaystyle \frac{1}{\sqrt{2}}\cr \frac{1}{2^{3/2}}\cr -\frac{1}{2^{3/2}}\cr \frac{1}{2^{3/2}}\cr \frac{1}{2^{3/2}}}\right] \)
\(\hat{P}=I-2*v.v^T=\left[ \matrix{\displaystyle 1&0&0&0&0\cr 0&1&0&0&0\cr 0&0&1&0&0\cr 0&0&0&1&0\cr 0&0&0&0&1}\right]-2*\left[ \matrix{\displaystyle \frac{1}{\sqrt{2}}\cr \frac{1}{2^{3/2}}\cr -\frac{1}{2^{3/2}}\cr \frac{1}{2^{3/2}}\cr \frac{1}{2^{3/2}}}\right].\left[ \matrix{\displaystyle \frac{1}{\sqrt{2}}&\frac{1}{2^{3/2}}&-\frac{1}{2^{3/2}}&\frac{1}{2^{3/2}}&\frac{1}{2^{3/2}}}\right]=\left[\matrix{\displaystyle 0&-\frac{1}{2}&\frac{1}{2}&-\frac{1}{2}&-\frac{1}{2}\cr -\frac{1}{2}&\frac{3}{4}&\frac{1}{4}&-\frac{1}{4}&-\frac{1}{4}\cr \frac{1}{2}&\frac{1}{4}&\frac{3}{4}&\frac{1}{4}&\frac{1}{4}\cr -\frac{1}{2}&-\frac{1}{4}&\frac{1}{4}&\frac{3}{4}&-\frac{1}{4}\cr -\frac{1}{2}&-\frac{1}{4}&\frac{1}{4}&-\frac{1}{4}&\frac{3}{4}}\right] \)
取向量\( \left[ \matrix{\displaystyle 0\cr \frac{1}{2}\cr -\frac{1}{2}\cr \frac{1}{2}\cr \frac{1}{2}}\right]\)找一個\(Householder\)矩陣\( \hat{P}_3\),使得\(\left[ \matrix{\displaystyle 0&-\frac{1}{2}&\frac{1}{2}&-\frac{1}{2}&-\frac{1}{2}\cr -\frac{1}{2}&\frac{3}{4}&\frac{1}{4}&-\frac{1}{4}&-\frac{1}{4}\cr \frac{1}{2}&\frac{1}{4}&\frac{3}{4}&\frac{1}{4}&\frac{1}{4}\cr -\frac{1}{2}&-\frac{1}{4}&\frac{1}{4}&\frac{3}{4}&-\frac{1}{4}\cr -\frac{1}{2}&-\frac{1}{4}&\frac{1}{4}&-\frac{1}{4}&\frac{3}{4}}\right] \left[ \matrix{\displaystyle 0\cr \frac{1}{2}\cr -\frac{1}{2}\cr \frac{1}{2}\cr \frac{1}{2}}\right]=\left[ \matrix{\displaystyle -1\cr 0\cr 0\cr 0\cr 0}\right] \)
設\(P_3=\left[ \matrix{\displaystyle 1&0&0&0&0&0&0&0&0\cr 0&1&0&0&0&0&0&0&0\cr 0&0&1&0&0&0&0&0&0\cr 0&0&0&0&-\frac{1}{2}&\frac{1}{2}&-\frac{1}{2}&-\frac{1}{2}&0\cr 0&0&0&-\frac{1}{2}&\frac{3}{4}&\frac{1}{4}&-\frac{1}{4}&-\frac{1}{4}&0\cr 0&0&0&\frac{1}{2}&\frac{1}{4}&\frac{3}{4}&\frac{1}{4}&\frac{1}{4}&0\cr 0&0&0&-\frac{1}{2}&-\frac{1}{4}&\frac{1}{4}&\frac{3}{4}&-\frac{1}{4}&0\cr 0&0&0&-\frac{1}{2}&-\frac{1}{4}&\frac{1}{4}&-\frac{1}{4}&\frac{3}{4}&0\cr 0&0&0&0&0&0&0&0&1}\right] \)
計算\(H_3=P_3^T.H_2.P_3=\left[ \matrix{\displaystyle -1&\frac{7}{3}&2&-\frac{3}{2}&-\frac{23}{36}&-\frac{1}{4}&\frac{29}{36}&-\frac{31}{36}&-\frac{1}{6}\cr -2&-1&\frac{5}{3}&\frac{5}{12}&\frac{125}{72}&-\frac{173}{72}&-\frac{259}{72}&-\frac{7}{8}&\frac{21}{4}\cr 0&1&-\frac{3}{2}&\frac{13}{12}&\frac{559}{216}&-\frac{55}{24}&-\frac{625}{216}&\frac{251}{216}&\frac{43}{12}\cr 0&0&-1&-\frac{1}{4}&\frac{55}{54}&-\frac{3}{2}&-\frac{193}{54}&\frac{103}{27}&\frac{241}{24}\cr0&0&0&\frac{1}{2}&-\frac{529}{1296}&-\frac{13}{48}&\frac{1495}{1296}&-\frac{2081}{1296}&-\frac{647}{144}\cr0&0&0&-\frac{1}{2}&\frac{1385}{1296}&-\frac{65}{144}&-\frac{1535}{1296}&\frac{6121}{1296}&\frac{719}{144}\cr 0&0&0&0&-\frac{233}{144}&-\frac{71}{144}&-\frac{43}{48}&-\frac{329}{144}&-\frac{203}{144}\cr 0&0&0&\frac{1}{2}&-\frac{529}{1296}&-\frac{151}{144}&-\frac{809}{1296}&-\frac{1937}{1296}&\frac{19}{48}\cr 0&0&0&-\frac{1}{2}&-\frac{1}{4}&\frac{1}{4}&-\frac{1}{4}&\frac{3}{4}&-1}\right] \)
取向量\( \left[ \matrix{\displaystyle H3[5,4]\cr H3[6,4]\cr H3[7,4]\cr H3[8,4]\cr H3[9,4]}\right]=\left[ \matrix{\displaystyle \frac{1}{2}\cr -\frac{1}{2}\cr 0\cr \frac{1}{2}\cr -\frac{1}{2}}\right] \)
------------------------
\(k=4\)
\(X\)向量\(=\left[ \matrix{\displaystyle \frac{1}{2}\cr -\frac{1}{2}\cr 0\cr \frac{1}{2}\cr -\frac{1}{2}}\right]\)第1元\(\displaystyle=\frac{1}{2},sign(X_1)=1\),長度\( \Vert\;X \Vert\;=sqrt(\left[ \matrix{\displaystyle \frac{1}{2}\cr -\frac{1}{2}\cr 0\cr \frac{1}{2}\cr -\frac{1}{2}}\right].\left[ \matrix{\displaystyle \frac{1}{2}\cr -\frac{1}{2}\cr 0\cr \frac{1}{2}\cr -\frac{1}{2}}\right] )=1\)
第1元是1,其餘為0的向量\( e1=\left[ \matrix{\displaystyle 1\cr 0\cr 0\cr 0\cr 0}\right] \)
\(X+sign(X_1)*\Vert\; X \Vert\;*e1=\left[ \matrix{\displaystyle \frac{1}{2}\cr -\frac{1}{2}\cr 0\cr \frac{1}{2}\cr -\frac{1}{2}}\right]+1*1*\left[ \matrix{\displaystyle 1\cr 0\cr 0\cr 0\cr 0}\right]=\left[ \matrix{\displaystyle \frac{3}{2}\cr -\frac{1}{2}\cr 0\cr \frac{1}{2}\cr -\frac{1}{2}}\right] \)
長度\(\Vert\; X+sign(X_1)*\Vert\; X \Vert\;*e1 \Vert\;=sqrt(\left[ \matrix{\displaystyle \frac{3}{2}\cr -\frac{1}{2}\cr 0\cr \frac{1}{2}\cr -\frac{1}{2}}\right].\left[ \matrix{\displaystyle \frac{3}{2}\cr -\frac{1}{2}\cr 0\cr \frac{1}{2}\cr -\frac{1}{2}}\right] )=\sqrt{3}\)
\(v=\left[ \matrix{\displaystyle \frac{3}{2}\cr -\frac{1}{2}\cr 0\cr \frac{1}{2}\cr -\frac{1}{2}}\right]/\sqrt{3}=\left[ \matrix{\displaystyle \frac{\sqrt{3}}{2}\cr -\frac{1}{2\sqrt{3}}\cr 0\cr \frac{1}{2\sqrt{3}}\cr -\frac{1}{2\sqrt{3}}}\right] \)
\(\hat{P}=I-2*v.v^T=\left[ \matrix{\displaystyle 1&0&0&0&0\cr 0&1&0&0&0\cr 0&0&1&0&0\cr 0&0&0&1&0\cr 0&0&0&0&1}\right]-2*\left[ \matrix{\displaystyle \frac{\sqrt{3}}{2}\cr -\frac{1}{2\sqrt{3}}\cr 0\cr \frac{1}{2\sqrt{3}}\cr -\frac{1}{2\sqrt{3}}}\right].\left[ \matrix{\displaystyle \frac{\sqrt{3}}{2}&-\frac{1}{2\sqrt{3}}&0&\frac{1}{2\sqrt{3}}&-\frac{1}{2\sqrt{3}}}\right]=\left[ \matrix{\displaystyle -\frac{1}{2}&\frac{1}{2}&0&-\frac{1}{2}&\frac{1}{2}\cr \frac{1}{2}&\frac{5}{6}&0&\frac{1}{6}&-\frac{1}{6}\cr 0&0&1&0&0\cr -\frac{1}{2}&\frac{1}{6}&0&\frac{5}{6}&\frac{1}{6}\cr \frac{1}{2}&-\frac{1}{6}&0&\frac{1}{6}&\frac{5}{6}}\right] \)
取向量\( \left[ \matrix{\displaystyle \frac{1}{2}\cr -\frac{1}{2}\cr 0\cr \frac{1}{2}\cr -\frac{1}{2}}\right] \)找一個\(Householder\)矩陣\( \hat{P}_4\),使得\(\left[ \matrix{\displaystyle -\frac{1}{2}&\frac{1}{2}&0&-\frac{1}{2}&\frac{1}{2}\cr \frac{1}{2}&\frac{5}{6}&0&\frac{1}{6}&-\frac{1}{6}\cr 0&0&1&0&0\cr -\frac{1}{2}&\frac{1}{6}&0&\frac{5}{6}&\frac{1}{6}\cr \frac{1}{2}&-\frac{1}{6}&0&\frac{1}{6}&\frac{5}{6}}\right] \left[ \matrix{\displaystyle \frac{1}{2}\cr -\frac{1}{2}\cr 0\cr \frac{1}{2}\cr -\frac{1}{2}}\right]=\left[ \matrix{\displaystyle -1\cr 0\cr 0\cr 0\cr 0}\right] \)
設\(P_4=\left[ \matrix{\displaystyle 1&0&0&0&0&0&0&0&0\cr 0&1&0&0&0&0&0&0&0\cr 0&0&1&0&0&0&0&0&0\cr 0&0&0&1&0&0&0&0&0\cr 0&0&0&0&-\frac{1}{2}&\frac{1}{2}&0&-\frac{1}{2}&\frac{1}{2}\cr 0&0&0&0&\frac{1}{2}&\frac{5}{6}&0&\frac{1}{6}&-\frac{1}{6}\cr 0&0&0&0&0&0&1&0&0\cr 0&0&0&0&-\frac{1}{2}&\frac{1}{6}&0&\frac{5}{6}&\frac{1}{6}\cr 0&0&0&0&\frac{1}{2}&-\frac{1}{6}&0&\frac{1}{6}&\frac{5}{6}}\right] \)
計算\(H_4=P_4^T.H_3.P_4=\left[ \matrix{\displaystyle -1&\frac{7}{3}&2&-\frac{3}{2}&\frac{13}{24}&-\frac{139}{216}&\frac{29}{36}&-\frac{101}{216}&-\frac{121}{216}\cr-2&-1&\frac{5}{3}&\frac{5}{12}&\frac{143}{144}&-\frac{931}{432}&-\frac{259}{72}&-\frac{485}{432}&\frac{2375}{432}\cr 0&1&-\frac{3}{2}&\frac{13}{12}&-\frac{59}{48}&-\frac{1321}{1296}&-\frac{625}{216}&-\frac{143}{1296}&\frac{6293}{1296}\cr 0&0&-1&-\frac{1}{4}&\frac{89}{48}&-\frac{2305}{1296}&-\frac{193}{54}&\frac{5305}{1296}&\frac{12653}{1296}\cr 0&0&0&-1&-\frac{1}{4}&\frac{3557}{3888}&-\frac{2545}{2592}&\frac{15283}{3888}&\frac{17111}{3888}\cr 0&0&0&0&-1&-\frac{679}{3888}&-\frac{1225}{2592}&\frac{8575}{3888}&\frac{10499}{3888}\cr 0&0&0&0&1&-\frac{295}{216}&-\frac{43}{48}&-\frac{305}{216}&-\frac{493}{216}\cr 0&0&0&0&1&-\frac{4297}{3888}&-\frac{3463}{2592}&\frac{3121}{3888}&\frac{11309}{3888}\cr 0&0&0&0&-1&\frac{113}{1296}&\frac{133}{288}&-\frac{1721}{1296}&-\frac{4837}{1296}}\right] \)
取向量\( \left[ \matrix{\displaystyle H4[6,5]\cr H4[7,5]\cr H4[8,5]\cr H4[9,5]}\right]=\left[ \matrix{\displaystyle -1\cr 1\cr 1\cr -1}\right] \)
------------------------
\(k=5\)
\(X\)向量\(=\left[ \matrix{-1\cr 1\cr 1\cr -1}\right] \)第1元\(=-1,sign(X_1)=-1\),長度\( \Vert\;X \Vert\;=sqrt(\left[ \matrix{-1\cr 1\cr 1\cr -1}\right].\left[ \matrix{-1\cr 1\cr 1\cr -1}\right] )=2\)
第1元是1,其餘為0的向量\( e1=\left[ \matrix{1\cr 0\cr 0\cr 0}\right] \)
\(X+sign(X_1)*\Vert\; X \Vert\;*e1=\left[ \matrix{-1\cr 1\cr 1\cr -1}\right]+-1*2*\left[ \matrix{\displaystyle 1\cr 0\cr 0\cr 0}\right]=\left[ \matrix{-3\cr 1\cr 1\cr -1}\right] \)
長度\(\Vert\; X+sign(X_1)*\Vert\; X \Vert\;*e1 \Vert\;=sqrt(\left[ \matrix{-3\cr 1\cr 1\cr -1}\right].\left[ \matrix{-3\cr 1\cr 1\cr -1}\right] )=2\sqrt{3}\)
\(v=\left[ \matrix{-3\cr 1\cr 1\cr -1}\right]/2\sqrt{3}=\left[ \matrix{\displaystyle -\frac{\sqrt{3}}{2}\cr \frac{1}{2\sqrt{3}}\cr \frac{1}{2\sqrt{3}}\cr -\frac{1}{2\sqrt{3}}}\right] \)
\(\hat{P}=I-2*v.v^T=\left[ \matrix{\displaystyle 1&0&0&0\cr 0&1&0&0\cr 0&0&1&0\cr 0&0&0&1}\right]-2*\left[ \matrix{\displaystyle -\frac{\sqrt{3}}{2}\cr \frac{1}{2\sqrt{3}}\cr \frac{1}{2\sqrt{3}}\cr -\frac{1}{2\sqrt{3}}}\right].\left[ \matrix{\displaystyle -\frac{\sqrt{3}}{2}&\frac{1}{2\sqrt{3}}&\frac{1}{2\sqrt{3}}&-\frac{1}{2\sqrt{3}}}\right]=\left[ \matrix{\displaystyle -\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&-\frac{1}{2}\cr \frac{1}{2}&\frac{5}{6}&-\frac{1}{6}&\frac{1}{6}\cr \frac{1}{2}&-\frac{1}{6}&\frac{5}{6}&\frac{1}{6}\cr -\frac{1}{2}&\frac{1}{6}&\frac{1}{6}&\frac{5}{6}}\right] \)
取向量\( \left[ \matrix{-1\cr 1\cr 1\cr -1}\right] \)找一個\(Householder\)矩陣\( \hat{P}_5\),使得\(\left[ \matrix{\displaystyle -\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&-\frac{1}{2}\cr \frac{1}{2}&\frac{5}{6}&-\frac{1}{6}&\frac{1}{6}\cr \frac{1}{2}&-\frac{1}{6}&\frac{5}{6}&\frac{1}{6}\cr -\frac{1}{2}&\frac{1}{6}&\frac{1}{6}&\frac{5}{6}}\right] \left[ \matrix{-1\cr 1\cr 1\cr -1}\right]=\left[ \matrix{\displaystyle 2\cr 0\cr 0\cr 0}\right] \)
設\(P_5=\left[ \matrix{\displaystyle 1&0&0&0&0&0&0&0&0\cr 0&1&0&0&0&0&0&0&0\cr 0&0&1&0&0&0&0&0&0\cr 0&0&0&1&0&0&0&0&0\cr 0&0&0&0&1&0&0&0&0\cr 0&0&0&0&0&-\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&-\frac{1}{2}\cr 0&0&0&0&0&\frac{1}{2}&\frac{5}{6}&-\frac{1}{6}&\frac{1}{6}\cr 0&0&0&0&0&\frac{1}{2}&-\frac{1}{6}&\frac{5}{6}&\frac{1}{6}\cr 0&0&0&0&0&-\frac{1}{2}&\frac{1}{6}&\frac{1}{6}&\frac{5}{6}}\right] \)
計算\(H_5=P_5^T.H_4.P_5=\left[ \matrix{\displaystyle -1&\frac{7}{3}&2&-\frac{3}{2}&\frac{13}{24}&\frac{37}{48}&\frac{433}{1296}&-\frac{1217}{1296}&-\frac{115}{1296}\cr -2&-1&\frac{5}{3}&\frac{5}{12}&\frac{143}{144}&-\frac{129}{32}&-\frac{7703}{2592}&-\frac{1289}{2592}&\frac{12629}{2592}\cr 0&1&-\frac{3}{2}&\frac{13}{12}&-\frac{59}{48}&-\frac{985}{288}&-\frac{16277}{7776}&\frac{5365}{7776}&\frac{31535}{7776}\cr 0&0&-1&-\frac{1}{4}&\frac{89}{48}&-\frac{1075}{288}&-\frac{22727}{7776}&\frac{36895}{7776}&\frac{70853}{7776}\cr 0&0&0&-1&-\frac{1}{4}&-\frac{2045}{1728}&-\frac{13177}{46656}&\frac{216029}{46656}&\frac{172699}{46656}\cr 0&0&0&0&2&-\frac{859}{1152}&-\frac{39167}{31104}&-\frac{27749}{31104}&\frac{30413}{31104}\cr 0&0&0&0&0&\frac{8155}{10368}&-\frac{360449}{279936}&-\frac{289307}{279936}&-\frac{295117}{279936}\cr 0&0&0&0&0&-\frac{10907}{10368}&-\frac{287807}{279936}&\frac{526555}{279936}&\frac{962189}{279936}\cr 0&0&0&0&0&\frac{13199}{10368}&-\frac{72541}{279936}&-\frac{789199}{279936}&-\frac{1077113}{279936}}\right] \)
取向量\( \left[ \matrix{\displaystyle H5[7,6]\cr H5[8,6]\cr H5[9,6]}\right]=\left[ \matrix{\displaystyle \frac{8155}{10368}\cr -\frac{10907}{10368}\cr \frac{13199}{10368}}\right] \)
------------------------
向量\(X\)長度\(\displaystyle=\frac{5\sqrt{1598579}}{3456}\)不是完全平方數,改用浮點數計算
\(k=6\)
\(X\)向量\(=\left[ \matrix{\displaystyle \frac{8155}{10368}\cr -\frac{10907}{10368}\cr \frac{13199}{10368}}\right]\)第1元\(=0.7865547839506173,sign(X_1)=1\),長度\( \Vert\;X \Vert\;=sqrt(\left[ \matrix{\displaystyle \frac{8155}{10368}\cr -\frac{10907}{10368}\cr \frac{13199}{10368}}\right].\left[ \matrix{\displaystyle \frac{8155}{10368}\cr -\frac{10907}{10368}\cr \frac{13199}{10368}}\right] )=1.829208969513448\)
第1元是1,其餘為0的向量\( e1=\left[ \matrix{1\cr 0\cr 0}\right] \)
\(X+sign(X_1)*\Vert\; X \Vert\;*e1=\left[ \matrix{\displaystyle \frac{8155}{10368}\cr -\frac{10907}{10368}\cr \frac{13199}{10368}}\right]+1*1.829208969513448*\left[ \matrix{\displaystyle 1\cr 0\cr 0}\right]=\left[ \matrix{\displaystyle 2.615763753464065\cr -1.05198688271605\cr 1.273051697530864}\right] \)
長度\(\Vert\; X+sign(X_1)*\Vert\; X \Vert\;*e1 \Vert\;=sqrt(\left[ \matrix{2.615763753464065\cr -1.05198688271605\cr 1.273051697530864}\right].\left[ \matrix{2.615763753464065\cr -1.05198688271605\cr 1.273051697530864}\right] )=3.093470064495413 \)
\(v=\left[ \matrix{2.615763753464065\cr -1.05198688271605\cr 1.273051697530864}\right]/3.093470064495413=\left[ \matrix{0.8455759063214779\cr -0.3400669347959709\cr 0.4115286946339066}\right] \)
\(\hat{P}=I-2*v.v^T=\left[ \matrix{1&0&0\cr 0&1&0\cr 0&0&1}\right]-2*\left[ \matrix{0.8455759063214779\cr -0.3400669347959709\cr 0.4115286946339066}\right].\left[ \matrix{ 0.8455759063214779&-0.3400669347959709&0.4115286946339066}\right]=\)
\(\left[ \matrix{ -0.4299972267027781&0.5751048132001405&-0.6959574978847209\cr 0.5751048132001405&0.7687089597169466&0.2798946035294795\cr -0.6959574978847209&0.2798946035294795&0.661288266985825}\right] \)
取向量\( \left[ \matrix{\displaystyle \frac{8155}{10368}\cr -\frac{10907}{10368}\cr \frac{13199}{10368}}\right] \)找一個\(Householder\)矩陣\( \hat{P}_6\),使得\(\left[ \matrix{ -0.4299972267027781&0.5751048132001405&-0.6959574978847209\cr 0.5751048132001405&0.7687089597169466&0.2798946035294795\cr -0.6959574978847209&0.2798946035294795&0.661288266985825}\right] \left[ \matrix{\displaystyle \frac{8155}{10368}\cr -\frac{10907}{10368}\cr \frac{13199}{10368}}\right]=\left[ \matrix{-1.829208969513457\cr 7.771561172376096*10^{-16}\cr -2.886579864025407*10^{-15}}\right] \)
設\(P_6=\left[ \matrix{1&0&0&0&0&0&0&0&0\cr 0&1&0&0&0&0&0&0&0\cr 0&0&1&0&0&0&0&0&0\cr 0&0&0&1&0&0&0&0&0\cr 0&0&0&0&1&0&0&0&0\cr 0&0&0&0&0&1&0&0&0\cr 0&0&0&0&0&0&-0.4299972267027781&0.5751048132001405&-0.6959574978847209\cr 0&0&0&0&0&0&0.5751048132001405&0.7687089597169466&0.2798946035294795\cr 0&0&0&0&0&0&-0.6959574978847209&0.2798946035294795&0.661288266985825}\right] \)
計算\(H_6=P_6^T.H_5.P_6=\left[ \matrix{ -1&2.333333333333333&2&-1.5&0.5416666666666666&0.7708333333333334&-0.6219569788349768&-0.5545418975815991&-0.5540350924250236\cr -2&-1&1.666666666666667&0.4166666666666667&0.9930555555555556&-4.03125&-2.39903113723365&-0.7276656161967713&5.151074840285687\cr 0&1&-1.5&1.083333333333333&-1.229166666666667&-3.420138888888889&-1.525529515680916&0.4616279381076218&4.331720709928399\cr 0&0&-1&-0.25&1.854166666666667&-3.732638888888889&-2.355920465963594&4.516780134134694&9.387602241820074\cr 0&0&0&-1&-0.25&-1.183449074074074&0.2082096026209324&4.4329301669687&3.940325053062458\cr 0&0&0&0&2&-0.7456597222222222&-0.6521038280089702&-1.136304030499402&1.273261703644264\cr 0&0&0&0&0&-1.829208969513453&-1.610172351137944&4.19317878751438&4.254779928150215\cr 0&0&0&0&0&7.7715611723761*10^{-16}&0.0579988841413669&-0.605664190520036&1.767500658619938\cr 0&0&0&0&0&-2.886579864025409*10^{-15}&0.04700389329356565&-0.4617357301648267&-1.038503736119814}\right] \)
取向量\( \left[ \matrix{H6[8,7]\cr H6[9,7]}\right]=\left[ \matrix{\displaystyle 0.0579988841413669\cr 0.04700389329356565}\right] \)
------------------------
\(k=7\)
\(X\)向量\(=\left[ \matrix{\displaystyle 0.0579988841413669\cr 0.04700389329356565}\right]\)第1元\(=0.0579988841413669,sign(X_1)=1\),長度\( \Vert\;X \Vert\;=sqrt(\left[ \matrix{0.0579988841413669\cr 0.04700389329356565}\right].\left[ \matrix{0.0579988841413669\cr 0.04700389329356565}\right] )=0.07465411272258612 \)
第1元是1,其餘為0的向量\( e1=\left[ \matrix{1\cr 0}\right] \)
\(X+sign(X_1)*\Vert\; X \Vert\;*e1=\left[ \matrix{0.0579988841413669\cr 0.04700389329356565}\right]+1*0.07465411272258612*\left[ \matrix{1\cr 0}\right]=\left[ \matrix{0.132652996863953\cr 0.04700389329356565}\right] \)
長度\(\Vert\; X+sign(X_1)*\Vert\; X \Vert\;*e1 \Vert\;=sqrt(\left[ \matrix{0.132652996863953\cr 0.04700389329356565}\right].\left[ \matrix{0.132652996863953\cr 0.04700389329356565}\right] )=0.1407344434093547 \)
\(v=\left[ \matrix{\displaystyle 0.132652996863953\cr 0.04700389329356565}\right]/0.1407344434093547=\left[ \matrix{0.9425766262357311\cr 0.3339899754095393}\right] \)
\(\hat{P}=I-2*v.v^T=\left[ \matrix{\displaystyle 1&0\cr 0&1}\right]-2*\left[ \matrix{0.9425766262357311\cr 0.3339899754095393}\right].\left[ \matrix{0.9425766262357311&0.3339899754095393}\right]=\left[\matrix{-0.7769013926518663&-0.6296222884361566\cr -0.6296222884361566&0.7769013926518692}\right] \)
取向量\( \left[ \matrix{0.0579988841413669\cr 0.04700389329356565}\right]\)找一個\(Householder\)矩陣\( \hat{P}_7\),使得\(\left[ \matrix{-0.7769013926518663&-0.6296222884361566\cr -0.6296222884361566&0.7769013926518692}\right] \left[ \matrix{0.0579988841413669\cr 0.04700389329356565}\right]=\left[ \matrix{-0.0746541127225859\cr 6.245004513516506*10^{-17}}\right] \)
設\(P_7=\left[ \matrix{1&0&0&0&0&0&0&0&0\cr 0&1&0&0&0&0&0&0&0\cr 0&0&1&0&0&0&0&0&0\cr 0&0&0&1&0&0&0&0&0\cr 0&0&0&0&1&0&0&0&0\cr 0&0&0&0&0&1&0&0&0\cr 0&0&0&0&0&0&1&0&0\cr 0&0&0&0&0&0&0&-0.7769013926518663&-0.6296222884361566\cr 0&0&0&0&0&0&0&-0.6296222884361566&0.7769013926518692}\right] \)
計算\(H_7=P_7^T.H_6.P_7=\left[ \matrix{-1&2.333333333333333&2&-1.5&0.5416666666666666&0.7708333333333334&-0.6219569788349768&0.7796572152815339&-0.08127869629395262\cr -2&-1&1.666666666666667&0.4166666666666667&0.9930555555555556&-4.03125&-2.39903113723365&-2.677907098238435&4.460031707558076\cr 0&1&-1.5&1.083333333333333&-1.229166666666667&-3.420138888888889&-1.525529515680916&-3.085987294254227&3.074668613324933\cr 0&0&-1&-0.25&1.854166666666667&-3.732638888888889&-2.355920465963594&-9.419736382934685&4.449375810914967\cr 0&0&0&-1&-0.25&-1.183449074074074&0.2082096026209324&-5.924866097337959&0.2701723850207669\cr 0&0&0&0&2&-0.7456597222222222&-0.6521038280089702&0.08112223614429317&1.704641134813782\cr 0&0&0&0&0&-1.829208969513453&-1.610172351137944&-5.936590714812356&0.6654256275903683\cr 0&0&0&0&0&1.213681349951592*10^{-15}&-0.07465411272258583&-0.1385315695498772&-1.038138425003079\cr 0&0&0&0&0&-2.731902729369484*10^{-15}&6.245004513516506*10^{-17}&1.191097963781674&-1.505636357089966}\right] \)
(%o7) \( \left[\matrix{-1&2.333333333333333&2&-1.5&0.5416666666666666&0.7708333333333334&-0.6219569788349768&0.7796572152815339&-0.08127869629395262\cr -2&-1&1.666666666666667&0.4166666666666667&0.9930555555555556&-4.03125&-2.39903113723365&-2.677907098238435&4.460031707558076\cr 0&1&-1.5&1.083333333333333&-1.229166666666667&-3.420138888888889&-1.525529515680916&-3.085987294254227&3.074668613324933\cr 0&0&-1&-0.25&1.854166666666667&-3.732638888888889&-2.355920465963594&-9.419736382934685&4.449375810914967\cr 0&0&0&-1&-0.25&-1.183449074074074&0.2082096026209324&-5.924866097337959&0.2701723850207669\cr 0&0&0&0&2&-0.7456597222222222&-0.6521038280089702&0.08112223614429317&1.704641134813782\cr 0&0&0&0&0&-1.829208969513453&-1.610172351137944&-5.936590714812356&0.6654256275903683\cr 0&0&0&0&0&1.213681349951592*10^{-15}&-0.07465411272258583&-0.1385315695498772&-1.038138425003079\cr 0&0&0&0&0&-2.731902729369484*10^{-15}&6.245004513516506*10^{-17}&1.191097963781674&-1.505636357089966}\right]\)
