第1期 曹 蓉:解线性最小二乘问题的正交化方法及应用
37
for j=1∶n
[v,#]=house(A(j∶m,j))
T
A(j∶m,j∶n)=(Im-j+1-#vv)A(j∶m,j∶n)d(j)=#
if j<m
A(j+1∶m,j)=v(2∶m-j+1)end
end
function:[v,#]=house(x)
n=length(x)
=‖x‖∞ x=x/
T
!=x(2∶n)x(2∶n)
v(1)=1∶v(2∶n)=x(2∶n)
if!=0 #=0else
=x(1)+! if x(1)≤0
v(1)=x(1)- else
v(1)=-!/(x(1)+ )
end
22
#=2v(1)/(!+v(1));v=v/v(1)
end
2 解最小二乘问题的正交化方法
求解线性最小二乘问题的新算法,,而直接从矛盾方程组Ab=Y入手.常应用
R
Householder变换把系数矩阵A正交三角化,使QA=,其中R为n阶上三角阵,0为(m-n)×n的零矩阵,
由(3)式得到的一个m.mQY相应地分块成n维向量c与(m-n)维向量d,即QY=ccRc-Rb.于是Qr=QY-QAb=-(4)b=dd0 d
因Q是正交矩阵,所以‖r‖2=‖Qr‖2=‖c-Rb‖2+‖d‖2,若选择b,c-Rb=0(5)
00
那么‖r‖2将达到极小值,此时由(4)可得‖r‖2=‖d‖2,且从(4)有Qr=,故r=QT.
dd
由(5)可知,n阶上三角形方程组的解b就是最小二乘解,它是非常容易求解的.这样,可描述正交化方法求最小二乘解的计算步骤为:
1)对m×n矩阵A建立QR分解A=QR;2)计算C=QY,形成方程组Rb=c;
3)用回代法解Rb=c得出最小二乘解b.
正交化方法因其数值稳定而显得优于求解法方程,但因对A建立分解的计算量较大,故除非已经有了这种分解的资料可直接引用或者法方程病态,一般还是愿意从法方程来求最小二乘解的.
^
3 数值实例
01111,2