《迭代改善法.ppt》由会员分享，可在线阅读，更多相关《迭代改善法.ppt（49页珍藏版）》请在三一文库上搜索。
1、1,5.6.2 迭代改善法,设 ，其中 为非奇异矩阵，且为病态 方程组(但不过分病态).,本节研究的问题是，当求得方程组的近似解 后，,首先用选主元三角分解法实现分解计算,其中 为置换阵， 为单位下三角阵， 为上三角阵，,且求得计算解 .,如何对其精度进行改善.,2,计算剩余向量,（6.14）,现利用 的剩余向量来提高 的精度.,求解 , 得到的解记为 .,（6.15）,然后改善,如果(6.14)，(6.15)及解 的计算没有误差，则,说明 就是 的精确解.,3,但在实际计算中，由于有舍入误差， 只是方程组的 近似解，重复(6.14)，(6.15)的过程，就产生一近似解序列 ，有时可能得到比较
2、好的近似.,算法5,设 ，其中 为非,奇异矩阵，且 为病态方程组(但不过分病态)，用选 主元分解法得到 及计算解 .,本算法用迭代改善法提高近似解 的精度.,(迭代改善法),设计算机字长为 ，用数组 保存 元素，数组,保存三角矩阵 及 ，用 记录行交换信息，,4,存贮 及 , 保存 或 .,1. 用选主元三角分解实行分解计算 且求计 算解 (用单精度),2. 对于,(1) 计算 (用原始 及双精度计算),(2) 求解 , 即 (用单精度),(3) 如果 则输出 , 停机,(4) 改善 (用单精度计算),5,3. 输出迭代改善方法迭代 次失败信息,当 不是过分病态时，迭代改善法是比较好的改进,近
3、似解精度的一种方法，当 非常病态时， 可能,不收敛.,例11,(这里 ，用5位浮点数运算).,用迭代改善法解,6,解,精确解 (舍入到小数后,首先实现分解计算 , 且求,第4位).,计算解,应用迭代改善法需要用原始矩阵 且用双倍字长精度,计算剩余向量 ，其他计算用单精度.,7,计算结果如下表.,如果 需要更多的数位，迭代可以继续.,8,5.7 矩阵的正交三角化及应用,9,5.7.1 初等反射阵,定义9,设向量 且 ，,为初等反射阵(或称为豪斯霍尔德（Householder）变换).,如果记 , 则,称矩阵,10,定理25,设有初等反射阵 ,(1) 是对称矩阵，即,(2) 是正交矩阵，即,(3)
4、 设 为对称矩阵，那么 亦是对 称矩阵. ,证明,只证 的正交性，其他都可通过验证得到.,其中,则：,11,是一个初等反射阵.,初等反射阵的几何意义.,考虑以 为法向量且过原点 的超平面 .,设任意向量 ，,则 ,其中 .,设向量 , 则显然,于是,12,图5-1,对于 ，,从而对任意向量 ，,其中 为 关于平面S的镜面反射(见图5-1).,总有,13,定理26,设 为两个不相等的 维向量，,则存在一个初等反射阵 ，,证明,令 ，,而且,使,则得到一个初等反射阵,14,因为,所以,是使 成立的唯一长度等于1的向量(不计符号).,定理27,设 ，,则存在初等反射阵 ,使 ，,(约化定理),其中,
5、15,证明,记 ,设 ,取 ，,于是由定理22存在 变换,其中 , 使,记 ,其中,则有,于是,显然,16,如果 和 异号，那么计算 时有可能出现两相 近数相减的情况，有效数字可能损失.,取 和 有相同的符号，即取,在计算 时，为了避免上溢或下溢，将 规范化,17,则有 使 ,其中,算法6,设 ，,及 ,本算法计算,的分量冲掉 的分量.,使,18,关于 的计算，,设 ,为 的第 列向量，,其中,则,因此计算 就是要计算,于是计算 只需计算两向量的数量积和两向量的加法.,计算 只需作 次乘法运算.,19,5.7.2 平面旋转矩阵,设 , 则变换,是平面上向量的一个旋转变换，其中,为正交矩阵.,2
6、0,其中,中变换：,而,21,称为 中平面 的旋转变换(或称为吉文斯（Givens） 变换)，,称为平面旋转矩阵.,显然， 具有性质：,(1) 与单位阵 只是在 位置 元素不一样，其他相同.,(2) 为正交矩阵,(3) (左乘)只需计算第 行与第 行元素，,即对 有,22,其中,(4) (右乘)只需计算第 列与第 列元素,利用平面旋转变换，可使向量 中的指定元素变为零.,23,其中,证明,取 .,由 ,定理28,设 ,其中 不全为零，,则可选择平面旋转阵 ,(约化定理),使,利用矩阵乘法，显然有,24,由 的取法得,25,5.7.3 矩阵的QR分解,设 且为非零矩阵，则存在初等反射阵,设,使,
7、26,如果 , 取 ，,(1) 第1步约化：,即这一步不需要约化，,不妨设 ，,于是可选取初等反射阵 ,于是,使,其中,27,(2) 第 步约化：,设已完成对 上述第1步第 步的约化，再进行第 步约化.,即存在初等反射阵,使,其中,28,其中 为 阶上三角阵，,不妨设 ，,(如果 列满秩，,则 ).,于是，可选取初等反射阵,使,令,否则这一步不需要约化,29,第 步约化为,这就使 的三角化过程前进了一步.,其中 左上角的 阶子矩阵为 阶上三角阵 ., 令 ，继续上述过程，,最后有,30,第 步需要计算 及 ，,第 步约化,大约需要 次乘法运算.,定理29,且计算量约为 (当 )次乘法运算.,(
8、矩阵的正交约化),设 且,则存在初等反射阵,使,31,定理30,初等反射阵,(1) 设 且 的秩为 ，,其中 为 阶非奇异上三角阵.,(2) 设 为非奇异矩阵，,则 有分解,其中 为正交矩阵， 为上三角矩阵.,当 具有正对角元时，分解唯一.,(矩阵的QR分解),则存在,使,32,(2) 由设及定理29，存在初等反射阵,记 ,即,其中 为正交矩阵， 为上三角阵.,证明,(1) 由定理29可得.,使,则上式为,33,唯一性.,设有 其中 为正交阵，,为非奇异上三角阵，且 具有正对角元素，,由假设及对称正定矩阵 的Cholesky分解的唯一性，,则 .,也可以用平面旋转变换来约化矩阵.,则,从而可得
9、,34,定理31,(1) 存在正交矩阵,设 为非奇异矩阵，,(用吉文斯变换计算矩阵的QR分解),则,使,(2) 有QR分解,其中 为正交阵， 为非奇异上三角阵，且当 对角元素 都为正时，分解是唯一的.,35,证明,由设有 使 .,若 ，,(1) 第1步约化：,则可选择吉文斯变换,使,可简记为 ,其中,(2) 第 步约化：,设上述过程已完成第1步至第 步，,于是有,36,由设有 使 ，,若 ，,则可选择吉文斯变换 ，,使,其中,37,(3) 继续上述约化过程，最后则有,其中 为正交阵(为一系列平面旋转阵的乘积).,记 ,则 有QR分解,其中 为正交矩阵， 为非奇异上三角阵.,用 变换实现 的正交
10、三角约化需要 次乘法，,而用吉文斯变换约化计算约需要 次,次开方运算，,乘法，,次开方运算.,38,这说明，对一般矩阵 用吉文斯变换实现 的 正交三角约化比用 变换实现 的正交三角约化，计算量 要大一倍.,但是，如果 为三对角阵或上海森伯格阵，则需要约 化为零的元素比较少，这时用吉文斯变换实现 的正交三 角约化就显得简单、经济.,39,5.7.4 求解超定方程组,设 ，其中 .,当 时称为超定方,线性最小二乘问题：,寻求 使,如果使上式成立的 存在，称 为超定方程组最小 二乘解.,程组，,一般地，没有通常意义下的解.,对超定方程组，,记残差向量 ，,于是,40,即寻求 使偏差 的平方和最小.,
11、设 且 具有线性无关的列，可利用 的正交约化来求超定方程组的最小二乘解.,由正交约化定理，可选择初等反射阵,使,且同时约化常数项,41,其中， 为非奇异矩阵，,令 ,因为 为正交矩阵，,于是,所以,当选取 为 的解时,42,残差向量达到极小：,43,算法7,设 ，其中 ，,本算法利用正交三角约化 ,其中 为非奇异阵，,求 ,达到极小的残差向量冲掉 .,(超定方程组),(列满秩)，,使,且设,(1) 正交约化,对于,44,(3) 求解三角形方程组,(5) 求达到极小的残差向量,对于,求最小二乘解,45,例12,的最小二乘解.,解,(1) 正交约化,(a) 利用算法6，,选择 ,用正交约化方法求超定方程组,记,使,46,于是,其中,47,于是,(b) 对于,利用算法6，,确定,使,48,(2) 求解 ，即,得到超定方程组的最小二乘解,49,