数据拟合线性最小二乘法及其应用(householder变换)(2)

定理1：设u≠0，令π=2 2

则

H=I 1 T

是一个Householder矩阵.

证明：设 ′= ，那么 ′ =1，且

′′ H=I 2=I 2 Householder矩阵的一个关键是能把一个给定向量的若干个指定的分量变为零，具体地说就是下列定理：

定理2：设 ∈R ，σ=± ，且假定 ≠ σ 1，则可找到一个Householder矩阵H使

H = 1

其中 1=(1,0, ,0)

11证明：作 = + 1，求出π=2 2，则H=I π 1 1即为所求的Householder

矩阵.

因为

1 + 1 ( + 1) 2

1 = 2+2 2 1+ 2 = 2+ 1 =

数据拟合线性最小二乘法及其应用(householder变换)

所以

= 1

( + 1)( + 1)

= 1=x + 1 = 1

上述定理的证明是构造性的，即它叙述了计算u与π的过程，一旦 的正负号确定后，就可以求出

1= 1+

= ( =2, , )

以及 = ( + 1)

如果 与 1异号，在计算 1时就会发生抵消，因此，我们取σ=Sign( 1) . 这样我们可以运用Householder变换把系数矩阵化为上梯形矩阵.

定理二显示出，对于任意的 ∈ ( ≠0)都可构造出Householder矩阵H，使Hx的后n-1个分量为零；而且其证明亦告诉我们，可按如下的步骤来构造确定H的单位向量u：

计算 = ± 2 1;

计算 = / 2

首先，一个自然的问题是，实际计算时， 2前的符号如何选取最好. 为了使变换后得到的 为负数，则应取

= 2 1

但是这样选取就会出现一个问题，如果x是一个很接近 1的向量，计算

1= 1 2 1

时，就会出现两个相近的数相减，而导致严重地损失有效数字，这里 1和 1分别表示向量v和x的第一个分量. 不过，幸运的是，只要对上式做一简单的等价变形，就可避免这一问题的出现，事实上，注意到

222 1 2 ( 2+ + )2 1= 1 2== 1212

只要在 1>0时使用上面式子来计算 1，就会避免出现两个相近的数相减的情形.

数据拟合线性最小二乘法及其应用(householder变换)

其次，注意到

= 2 =

2 2 = 其中 = u不可，而只需求出 和 即可. 然而在实际

计算时，将 规格化为第一个分量为1的向量是方便的，这是因为这样正好可以把 的后 1个分量保存在 的后 1个化为0的分量位置上，而 的第一个分量1就无需保存了.

此外，上溢和下溢也是计算中需要考虑的问题. 当下溢发生时，一些计算机系统自动置其为零，这就可能出现 为零的情形. 另外如果x的分量太大，当该分量平方时，便会出现上溢. 考虑到对任意的非零实数α有α 与 的单位化向量相同，为了避免溢出现象的出现，我们可用 ∞代替x来构造v（这样做相当于在原来的v之前乘了常数α=1 ∞）

3.2 QR分解

设 ∈ × , = ，由于2范数具有正交不变性，故对任意的正交矩阵 ∈ × 有

2= ( ) 2

这样，最小二乘问题

min 2

就等价于原最小二乘问题. 因此，就可以通过适当选取正交矩阵Q，使原问题转化为较容易求解的最小二乘问题，这就是正交化方法的基本思想.

定理3（QR分解定理）设 ∈ × （m≥n），则A有QR分解：

A=Q 0

其中 ∈ × 是正交矩阵， ∈ × 是具有非负对角元的上三角阵；而且当m=n且A非奇异时，上述的分解时唯一的.

证明见附录.

数据拟合线性最小二乘法及其应用(householder变换)

利用QR分解，就可以实现正交化方法. 设 ∈ × （m≥n）有线性无关的列， ∈ ，并且假定已知A的QR分解. 现将Q分块为

Q=[ 1 2]

并且令

1 1 Q = b= 22

那么

222 x b 22= Q Q 2= 1 2+ 2 2

由此即知，x是最小二乘问题的解当且仅当x是 = 1的解. 这样一来，最小二乘问题的解可以很容易从上三角方程组 = 1求得.

综合上面的分析，可得求正交化方法的基本步骤为：

（1）计算A的QR分解；

（2）计算 1= 1 ；

（3）求解上三角方程组 = 1；

由此可知，实现正交化方法的关键是如何实现矩阵A的QR分解.

3.3 算法

设 ∈ × ，把 的列向量记作 =( 1 , 2 , , ) , =1,2, , .

第一步，令 1= = 1, 2, , ，利用定理二，取 = 1= 11, 12,, 1 ，

1求出 =± ， 1= + 1， 1= 1 2， 1= 1 1 1T， 1 1=2

1，令 1= σ

于是

1 12 0 (2)

22 2= 1 1= (2) 0 2(2) (2) 2 (2) 1 (2)

假设进行了 1步，得到Householder变换 1, 2, , k 1，使

= k 1 k 2 1 = 11

( ) 12 1 ( ) +1 22( )

数据拟合线性最小二乘法及其应用(householder变换)

其中 11是上三角矩阵，假定 22=[ , , ]，其中

=[ , , , = , , ] ( )( )

第k步，令 = 1，其中

= , =

1 2 22 = 1 ( ) 1 = +1 ， ，其中 = ( )2 1 ( ) = 2 ，则 = ( 1, )仍为Householder矩阵，

于是 +1= = 11

0( ) ) ( 22 12( ) .

最后得到 1 2 1 = = ，其中 为 × 阶上三角矩阵， 1

为 × 阶矩阵， = , 1 为 × 阶上梯形矩阵. 记Q= 1 2 1 ，则

= . 特别，若r=rankA=n,

则当m>n时，经n步可将矩阵A化为一个上三角阵，得到 = ，

其中R为 × 阶上三角阵；当m=n时，经n-1步可将A化为一个上三角阵，得到A=QR.

经过以上分析，可以得到矩阵的正交三角化的完整算法.

For j =1 : n

υ,β = house(A(j∶ m,j))

A j∶ m,j∶ n =( +1 βυ )A(j∶ m,j∶ n)

D j = β

If j< m

A j+1∶ m,j = υ(2∶m j+1)

end

end

function : υ,β =house(x)

n= length(x)

数据拟合线性最小二乘法及其应用(householder变换)

η= ∥x∥∞ = ∕

σ=x 2:n (2: )

υ 1 =1:υ 2:n =x(2:n)

ifσ=0

β=0

else

α= if x 1 ≤0

υ 1 =x 1 α

else

υ 1 = σ∕(x(1)+ α)

end

β=2υ 1 2 + 1 2 ; = ∕ (1)

end

第四章最小二乘法的正交化方法

求解线性最小二乘问题的快速算法，主要是避免构造法方程组，而直接从矛盾方

程组Ab=Y入手．常应用House …… 此处隐藏：2631字，全部文档内容请下载后查看。喜欢就下载吧 ……