5.6 应用案例二、QR算法与最小二乘问题在线视频

最后这一讲

我们介绍矩阵分解的具体应用

先来看qr迭代算法

这个是求解一般方阵

全部特征值和特征向量最有效的方法之一

其基本步骤是这样的

对矩阵A

记A1=A

那么有qr分解a1=q1r1

再记a2=r1q1

就是将前面的分解调换位置

对a2继续做qr分解

有a2=q2r2

依此类推

当ak有qr分解qkrk时

取a_{k+1}=rkqk

继续做qr分解

如此迭代下去

得到矩阵序列a1,a2,等等等等

可以证明

在一定条件下

当k>+\infty时

a_k接近于上三角矩阵

其实就是A的Schur分解的标准型

那么对角线上的元素就是A的特征值

在这个分解的过程中

我们发现A_k和a_{k+1}

始终都是酉相似的

也就是说A_k都是酉相似到矩阵A

所以k充分大时

a_{k+1}就接近于A的Schur分解的标准型

需要注意的是

当矩阵特别大时

上述方法计算量也会很大

实际中我们会将A

酉相似到上Hessenberg矩阵H

所谓Herseenberg矩阵

就是比上三角矩阵多一列次对角线元素

然后对H用QR迭代算法再去计算

看个例子

用qr迭代算法求矩阵a的Schur分解

这里我们借助数学软件模拟数值计算

取A1=A

通过qr分解得a2是这样的

再依次迭代分别得a3,a4,a5

发现到a6时就已经变成对角矩阵

这里因为a本身是正规的

所以Schur分解标准型就是对角矩阵

由a6知特征值为7.6056和0.3944

和真实特征值的误差可以忽略不计了

说明迭代效果还是不错的

第二个应用是用qr分解处理最小二乘问题

对线性方程组AX=b来说

如果有解也称方程组是相容的

如果无解也称方程组是矛盾的或者不相容的

我们关心的是当方程组无解时

也就是对任意向量x

Ax都不等于b

问题是

能不能找到一个向量x0

使得Ax0与b充分接近

怎么衡量充分接近呢

用数学的语言表述就是

寻找使得ax-b长度最小的向量x

称这个问题为最小二乘问题

而找出的向量x0

称为矛盾方程组的最小二乘解

最小二乘问题在线性代数中就有介绍

在我们的矩阵课程中一共提供4种解决方法

下面我们介绍qr分解的方法

和奇异值分解的方法

后续课程中还会介绍矩阵分析的方法

和广义逆的方法

这也展示解决同一问题的多种数学视角

先来看qr方法

假设A有qr分解

根据向量的酉不变性

如果x_0满足

Ax0-b的长度最小

当且仅当Rx0-Q^hb的长度最小

也就是说

Ax=b的最小二乘解

与另一个方程Rx=Q^H乘以

b的最小二乘解是一样的

而后一个方程的系数是一个上三角的

我们看个具体的例子

假设A是如下的矩阵

b为常数项

要你去求Ax=b的最小二乘解

先对A做QR分解

我们采用Householder变换的方法

下面考虑以R为系数

常数项为Q^Hb的方程组

通过计算

再还原回去

那么得到这样的方程组

根号2 x1+x2=2

根号2 x2=3/ 根号2

0=-1/ 根号2

目的是找出x1,x2使两边尽可能相等

由于最后一个方程无解

我们无能为力

所能作的就是使前2个方程都满足

这样的x就是原方程组的最小二乘解

按照这个思路

我们得到最小二乘解为

x1等于 根号2/4

x2为1.5

此时可算出解的误差为 根号2/2

最后我们来看用奇异值分解

也能解决最小二乘问题

结论是这样的

假设秩为r的矩阵A有奇异值分解

U,V是酉矩阵

\Sigma是分块对角的奇异值

那么取这样形式的向量x0

就是方程组的最小二乘解

证明的思路是

用向量长度的酉不变性

原方程的最小二乘解

等价地转化为以 \Sigma 000

乘以v^h为系数

常数项为U^H

乘以b的最小二乘解

做变量替换

令y=V^H x

令y=V^H x

c=U^H b

先解关于y的方程组

因为\Sigma是对角矩阵

所以还原到方程组得到如下关系

后面的m-r个方程都是无解的

没有办法处理

所能作的就是使前r个方程尽量满足

这样获得的就是关于y的最小二乘解

很容易解出唯一的y1,y2,…,yr

为了简单起见

我们取y_r+1到yn都是0

再替换回去就得到原方程组的最小二乘解x0

从推导过程中看出

y_r+1到yn可以取任意值

得到的都是最小二乘解

不过这里获得的x0

是最小二乘解中长度最小的

称为极小范数最小二乘解

最后我们还是来看前面的例题

依然要去求最小二乘解

先对A做奇异值分解

按照公式求出x0

与qr分解得到的最小二乘解是一致的

下一章我们还会继续讨论

线性方程组解的问题