迭代改善法课件

迭代改善法6、露凝无游氛，天高风景澈。7、翩翩新来燕，双双入我庐，先巢故尚在，相将还旧居。8、吁嗟身后名，于我若浮烟。9、陶渊明（约365年—427年），字元亮，（又一说名潜，字渊明）号五柳先生，私谥“靖节”，东晋末期南朝宋初期诗人、文学家、辞赋家、散文家。汉族，东晋浔阳柴桑人（今江西九江）。曾做过几年小官，后辞官回家，从此隐居，田园生活是陶渊明诗的主要题材，相关作品有《饮酒》、《归园田居》、《桃花源记》、《五柳先生传》、《归去来兮辞》等。10、倚南窗以寄傲，审容膝之易安。迭代改善法迭代改善法6、露凝无游氛，天高风景澈。7、翩翩新来燕，双双入我庐，先巢故尚在，相将还旧居。8、吁嗟身后名，于我若浮烟。9、陶渊明（约365年—427年），字元亮，（又一说名潜，字渊明）号五柳先生，私谥“靖节”，东晋末期南朝宋初期诗人、文学家、辞赋家、散文家。汉族，东晋浔阳柴桑人（今江西九江）。曾做过几年小官，后辞官回家，从此隐居，田园生活是陶渊明诗的主要题材，相关作品有《饮酒》、《归园田居》、《桃花源记》、《五柳先生传》、《归去来兮辞》等。10、倚南窗以寄傲，审容膝之易安。5.6.2迭代改善法首先用选主元三角分解法实现分解计算如何对其精度进行改善.2计算剩余向量然后改善33.输出迭代改善方法迭代次失败信息当不是过分病态时，迭代改善法是比较好的改进近似解精度的一种方法，当非常病态时，可能不收敛.

例11(这里，用5位浮点数运算).用迭代改善法解6

解精确解(舍入到小数后首先实现分解计算,且求第4位).计算解应用迭代改善法需要用原始矩阵且用双倍字长精度计算剩余向量，其他计算用单精度.7计算结果如下表.如果需要更多的数位，迭代可以继续.85.7矩阵的正交三角化及应用95.7.1初等反射阵

定义9设向量且，为初等反射阵(或称为豪斯霍尔德（Householder）变换).如果记,则称矩阵10

定理25设有初等反射阵,(1)是对称矩阵，即(2)是正交矩阵，即(3)设为对称矩阵，那么亦是对称矩阵.

证明只证的正交性，其他都可通过验证得到.其中则：11是一个初等反射阵.初等反射阵的几何意义.考虑以为法向量且过原点的超平面.设任意向量，则,其中.设向量,则显然于是12图5-1对于，从而对任意向量，其中为关于平面S的镜面反射(见图5-1).总有13

定理26设为两个不相等的维向量，则存在一个初等反射阵，

证明令，而且使则得到一个初等反射阵14因为所以是使成立的唯一长度等于1的向量(不计符号).

定理27设，则存在初等反射阵,使，(约化定理)其中15

证明记,设,取，于是由定理22存在变换其中,使记其中则有于是显然16如果和异号，那么计算时有可能出现两相近数相减的情况，有效数字可能损失.取和有相同的符号，即取在计算时，为了避免上溢或下溢，将规范化17则有使,其中

算法6设，及,本算法计算的分量冲掉的分量.使18关于的计算，设,为的第列向量，其中则因此计算就是要计算于是计算只需计算两向量的数量积和两向量的加法.计算只需作次乘法运算.19

5.7.2平面旋转矩阵设,则变换是平面上向量的一个旋转变换，其中为正交矩阵.20其中中变换：而21称为中平面的旋转变换(或称为吉文斯（Givens）变换)，称为平面旋转矩阵.显然，具有性质：(1)与单位阵只是在位置元素不一样，其他相同.(2)为正交矩阵(3)(左乘)只需计算第行与第行元素，即对有22其中(4)(右乘)只需计算第列与第列元素利用平面旋转变换，可使向量中的指定元素变为零.23其中

证明取.由,

定理28设,其中不全为零，则可选择平面旋转阵,(约化定理)使利用矩阵乘法，显然有24由的取法得25

5.7.3矩阵的QR分解设且为非零矩阵，则存在初等反射阵设使26如果,取，(1)第1步约化：即这一步不需要约化，不妨设，于是可选取初等反射阵,于是使其中27(2)第步约化：设已完成对上述第1步…第步的约化，再进行第步约化.即存在初等反射阵使其中28其中为阶上三角阵，不妨设，(如果列满秩，则).于是，可选取初等反射阵使令否则这一步不需要约化29第步约化为这就使的三角化过程前进了一步.其中左上角的阶子矩阵为阶上三角阵.令，继续上述过程，最后有30第步需要计算及，第步约化大约需要次乘法运算.

定理29且计算量约为(当)次乘法运算.(矩阵的正交约化)设且则存在初等反射阵使31

定理30初等反射阵(1)设且的秩为，其中为阶非奇异上三角阵.(2)设为非奇异矩阵，则有分解其中为正交矩阵，为上三角矩阵.当具有正对角元时，分解唯一.(矩阵的QR分解)则存在使32(2)由设及定理29，存在初等反射阵记,即其中为正交矩阵，为上三角阵.

证明(1)由定理29可得.使则上式为33唯一性.设有其中为正交阵，为非奇异上三角阵，且具有正对角元素，由假设及对称正定矩阵的Cholesky分解的唯一性，则.也可以用平面旋转变换来约化矩阵.则从而可得34

定理31(1)存在正交矩阵设为非奇异矩阵，(用吉文斯变换计算矩阵的QR分解)则使(2)有QR分解其中为正交阵，为非奇异上三角阵，且当对角元素都为正时，分解是唯一的.35

证明由设有使.若，(1)第1步约化：则可选择吉文斯变换使可简记为,其中(2)第步约化：设上述过程已完成第1步至第步，于是有36由设有使，若，则可选择吉文斯变换，使其中37(3)继续上述约化过程，最后则有其中为正交阵(为一系列平面旋转阵的乘积).记,则有QR分解其中为正交矩阵，为非奇异上三角阵.用变换实现的正交三角约化需要次乘法，而用吉文斯变换约化计算约需要次次开方运算，乘法，次开方运算.38这说明，对一般矩阵用吉文斯变换实现的正交三角约化比用变换实现的正交三角约化，计算量要大一倍.但是，如果为三对角阵或上海森伯格阵，则需要约化为零的元素比较少，这时用吉文斯变换实现的正交三角约化就显得简单、经济.39

5.7.4求解超定方程组设，其中.当时称为超定方

线性最小二乘问题：寻求使如果使上式成立的存在，称为超定方程组最小二乘解.程组，一般地，没有通常意义下的解.对超定方程组，记残差向量，于是40即寻求使偏差的平方和最小.设且具有线性无关的列，可利用的正交约化来求超定方程组的最小二乘解.由正交约化定理，可选择初等反射阵使且同时约化常数项41其中，为非奇异矩阵，令,因为为正交矩阵，于是所以当选取为的解时42残差向量达到极小：43

算法7设，其中，本算法利用正交三角约化,其中为非奇异阵，求,达到极小的残差向量冲掉.(超定方程组)(列满秩)，使且设(1)正交约化对于44(3)求解三角形方程组(5)求达到极小的残差向量对于求最小二乘解45

例12的最小二乘解.

解(1)正交约化(a)利用算法6，选择,用正交约化方法求超定方程组记使46于是其中47于是(b)对于利用算法6，确定使48(2)求解