正交化方法

 

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

这样，最小二乘问题

                        (3.3.1)

就等价于原最小二乘问题(3.1.3)。因此，我们就可望通过适当选取正交矩阵，使原问题转化为较容易求解的最小二乘问题（3.3.1），这就是正交化方法的基本思想。现在考虑如何求使问题(3.3.1)易于解决。

定理3.3.1（QR分解定理）设，则有QR分解：

                              (3.3.2)

其中是正交矩阵，是具有非负对角元的上三角阵；而且当且非奇异时，上述的分解还是唯一的。

证明 先证明QR分解的存在性。对用数学归纳法。当时，此定理就是定理3.2.2所述的情形，因此自然成立。现假定已经证明定理对所有矩阵成立，这里假设. 设的第一列为，则由定理3.2.2知，存在正交矩阵使得，于是，有

对矩阵应用归纳法假定，得

其中是正交矩阵，是具有非负元的上三角阵。这样，令

则和满足定理的要求。于是，则归纳法原理知存在性得证。

再证唯一性。设且非奇异，并假定，其中是正交矩阵，是具有非负对角元的上三角阵。非奇异蕴含着的对角均为正数。因此，我们有

既是正交矩阵又是对角元均为正数的上三角矩阵，这只能是单位矩阵。从而，必有，即分解是唯一的。

利用QR分解，我们就可以实现正交化方法。设有线性无关的列，，并且假定已知的QR分解（3.3.2）。现将分块为

并且令

那么

由此即知，是最小二乘问题(3.1.3)的解当且仅当是的解。这样一来，最小二乘问题(3.1.3)的解就可很容易从上三角方程组求得。

综合上面的讨论，可得正交化方法的基本步骤为：

计算的QR分解（3.3.2）；

计算；

求解上三角方程组.

由此可知，实现正交化方法的关键是如何实现矩阵的QR分解。下面我们就来介绍实现这一分解的最常用的Householder方法。

用Householder方法计算QR分解与不选主元的Gauss消去法很类似，就是利用Householder变换逐步将约化为上三角矩阵。设，并假定已经计算出Householder变换和使得

那么我们现在的任务就是集中精力于第三列杯为“+”的5个元素，确定一个Householder变换使得

.

令，则有

对于一般的矩阵，假定我们已经进行了步，得到了householder变换，使得

其中是上三角矩阵。假定

第步是：先用算法32.1确定Householder变换

使得

其中；然后，再计算。令

则

其中是上三角矩阵。这样，从出发，依次进行次，我们就可将约化为上三角阵。现在记

则

注意，这样得到的上三角矩阵的对角元均是非负的。

下面考虑计算的QR分解的存储问题。当分解完成后，一般来说，就不再需要，便可用来存放和。通常并不是将算出，而是只存放构成它的个Householder矩阵，而对每个，我们只需要保存和即可。注意到有如下形式

我们正好可以将存储在的对角元以下位置上。例如，对于的问题，其存储方式如下：

综合上面的讨论，可得如下算法。

算法3.3.1 (计算QR分解:Householder变换法)

容易算出,这一算法的运算量为 此外,该算法有十分良好的数值性态，详细的舍入误差分析参见[21]。利用这一算法求解最小二乘问题（3.1.3）所得到的计算解通常要比正则化方法精确的多。当然，付出的代价也是不容忽视的。

Householder方法并不是实现QR分解的唯一方法，例如，我们亦可利用Givens变换或Gram-Schmidt正交化来实现。通常用Givens变换来实现QR分解所需的运算量大约是Householder方法的二倍，但如果有较多的零元素，则灵活地使用Givens变换往往会使运算量大为减少。

此外，QR分解不仅可用来求解最小二乘问题，而且它也是数值代数许多重要算法的基础。例如，著名的求解特征值问题的QR方法就是利用这一分解而得到的；再如，我们亦可利用QR分解求解线性方程组（1.1.3），而且对于病态方程组QR分解法的计算结果往往要比三角分解法好得多。当然，前者比后者的运算时也要大的多。