《迭代改善法》PPT課件.ppt

1,5.6.2 迭代改善法,設(shè) ，其中 為非奇異矩陣，且為病態(tài) 方程組(但不過分病態(tài)).,本節(jié)研究的問題是，當(dāng)求得方程組的近似解 后，,首先用選主元三角分解法實(shí)現(xiàn)分解計(jì)算,其中 為置換陣， 為單位下三角陣， 為上三角陣，,且求得計(jì)算解 .,如何對其精度進(jìn)行改善.,2,計(jì)算剩余向量,（6.14）,現(xiàn)利用 的剩余向量來提高 的精度.,求解 , 得到的解記為 .,（6.15）,然后改善,如果(6.14)，(6.15)及解 的計(jì)算沒有誤差，則,說明 就是 的精確解.,3,但在實(shí)際計(jì)算中，由于有舍入誤差， 只是方程組的 近似解，重復(fù)(6.14)，(6.15)的過程，就產(chǎn)生一近似解序列 ，有時(shí)可能得到比較好的近似.,算法5,設(shè) ，其中 為非,奇異矩陣，且 為病態(tài)方程組(但不過分病態(tài))，用選 主元分解法得到 及計(jì)算解 .,本算法用迭代改善法提高近似解 的精度.,(迭代改善法),設(shè)計(jì)算機(jī)字長為 ，用數(shù)組 保存 元素，數(shù)組,保存三角矩陣 及 ，用 記錄行交換信息，,4,存貯 及 , 保存 或 .,1. 用選主元三角分解實(shí)行分解計(jì)算 且求計(jì) 算解 (用單精度),2. 對于,(1) 計(jì)算 (用原始 及雙精度計(jì)算),(2) 求解 , 即 (用單精度),(3) 如果 則輸出 , 停機(jī),(4) 改善 (用單精度計(jì)算),5,3. 輸出迭代改善方法迭代 次失敗信息,當(dāng) 不是過分病態(tài)時(shí)，迭代改善法是比較好的改進(jìn),近似解精度的一種方法，當(dāng) 非常病態(tài)時(shí)， 可能,不收斂.,例11,(這里 ，用5位浮點(diǎn)數(shù)運(yùn)算).,用迭代改善法解,6,解,精確解 (舍入到小數(shù)后,首先實(shí)現(xiàn)分解計(jì)算 , 且求,第4位).,計(jì)算解,應(yīng)用迭代改善法需要用原始矩陣 且用雙倍字長精度,計(jì)算剩余向量 ，其他計(jì)算用單精度.,7,計(jì)算結(jié)果如下表.,如果 需要更多的數(shù)位，迭代可以繼續(xù).,8,5.7 矩陣的正交三角化及應(yīng)用,9,5.7.1 初等反射陣,定義9,設(shè)向量 且 ，,為初等反射陣(或稱為豪斯霍爾德（Householder）變換).,如果記 , 則,稱矩陣,10,定理25,設(shè)有初等反射陣 ,(1) 是對稱矩陣，即,(2) 是正交矩陣，即,(3) 設(shè) 為對稱矩陣，那么 亦是對 稱矩陣. ,證明,只證 的正交性，其他都可通過驗(yàn)證得到.,其中,則：,11,是一個(gè)初等反射陣.,初等反射陣的幾何意義.,考慮以 為法向量且過原點(diǎn) 的超平面 .,設(shè)任意向量 ，,則 ,其中 .,設(shè)向量 , 則顯然,于是,12,圖5-1,對于 ，,從而對任意向量 ，,其中 為 關(guān)于平面S的鏡面反射(見圖5-1).,總有,13,定理26,設(shè) 為兩個(gè)不相等的 維向量，,則存在一個(gè)初等反射陣 ，,證明,令 ，,而且,使,則得到一個(gè)初等反射陣,14,因?yàn)?所以,是使 成立的唯一長度等于1的向量(不計(jì)符號).,定理27,設(shè) ，,則存在初等反射陣 ,使 ，,(約化定理),其中,15,證明,記 ,設(shè) ,取 ，,于是由定理22存在 變換,其中 , 使,記 ,其中,則有,于是,顯然,16,如果 和 異號，那么計(jì)算 時(shí)有可能出現(xiàn)兩相 近數(shù)相減的情況，有效數(shù)字可能損失.,取 和 有相同的符號，即取,在計(jì)算 時(shí)，為了避免上溢或下溢，將 規(guī)范化,17,則有 使 ,其中,算法6,設(shè) ，,及 ,本算法計(jì)算,的分量沖掉 的分量.,使,18,關(guān)于 的計(jì)算，,設(shè) ,為 的第 列向量，,其中,則,因此計(jì)算 就是要計(jì)算,于是計(jì)算 只需計(jì)算兩向量的數(shù)量積和兩向量的加法.,計(jì)算 只需作 次乘法運(yùn)算.,19,5.7.2 平面旋轉(zhuǎn)矩陣,設(shè) , 則變換,是平面上向量的一個(gè)旋轉(zhuǎn)變換，其中,為正交矩陣.,20,其中,中變換：,而,21,稱為 中平面 的旋轉(zhuǎn)變換(或稱為吉文斯（Givens） 變換)，,稱為平面旋轉(zhuǎn)矩陣.,顯然， 具有性質(zhì)：,(1) 與單位陣 只是在 位置 元素不一樣，其他相同.,(2) 為正交矩陣,(3) (左乘)只需計(jì)算第 行與第 行元素，,即對 有,22,其中,(4) (右乘)只需計(jì)算第 列與第 列元素,利用平面旋轉(zhuǎn)變換，可使向量 中的指定元素變?yōu)榱?,23,其中,證明,取 .,由 ,定理28,設(shè) ,其中 不全為零，,則可選擇平面旋轉(zhuǎn)陣 ,(約化定理),使,利用矩陣乘法，顯然有,24,由 的取法得,25,5.7.3 矩陣的QR分解,設(shè) 且為非零矩陣，則存在初等反射陣,設(shè),使,26,如果 , 取 ，,(1) 第1步約化：,即這一步不需要約化，,不妨設(shè) ，,于是可選取初等反射陣 ,于是,使,其中,27,(2) 第 步約化：,設(shè)已完成對 上述第1步第 步的約化，再進(jìn)行第 步約化.,即存在初等反射陣,使,其中,28,其中 為 階上三角陣，,不妨設(shè) ，,(如果 列滿秩，,則 ).,于是，可選取初等反射陣,使,令,否則這一步不需要約化,29,第 步約化為,這就使 的三角化過程前進(jìn)了一步.,其中 左上角的 階子矩陣為 階上三角陣 ., 令 ，繼續(xù)上述過程，,最后有,30,第 步需要計(jì)算 及 ，,第 步約化,大約需要 次乘法運(yùn)算.,定理29,且計(jì)算量約為 (當(dāng) )次乘法運(yùn)算.,(矩陣的正交約化),設(shè) 且,則存在初等反射陣,使,31,定理30,初等反射陣,(1) 設(shè) 且 的秩為 ，,其中 為 階非奇異上三角陣.,(2) 設(shè) 為非奇異矩陣，,則 有分解,其中 為正交矩陣， 為上三角矩陣.,當(dāng) 具有正對角元時(shí)，分解唯一.,(矩陣的QR分解),則存在,使,32,(2) 由設(shè)及定理29，存在初等反射陣,記 ,即,其中 為正交矩陣， 為上三角陣.,證明,(1) 由定理29可得.,使,則上式為,33,唯一性.,設(shè)有 其中 為正交陣，,為非奇異上三角陣，且 具有正對角元素，,由假設(shè)及對稱正定矩陣 的Cholesky分解的唯一性，,則 .,也可以用平面旋轉(zhuǎn)變換來約化矩陣.,則,從而可得,34,定理31,(1) 存在正交矩陣,設(shè) 為非奇異矩陣，,(用吉文斯變換計(jì)算矩陣的QR分解),則,使,(2) 有QR分解,其中 為正交陣， 為非奇異上三角陣，且當(dāng) 對角元素 都為正時(shí)，分解是唯一的.,35,證明,由設(shè)有 使 .,若 ，,(1) 第1步約化：,則可選擇吉文斯變換,使,可簡記為 ,其中,(2) 第 步約化：,設(shè)上述過程已完成第1步至第 步，,于是有,36,由設(shè)有 使 ，,若 ，,則可選擇吉文斯變換 ，,使,其中,37,(3) 繼續(xù)上述約化過程，最后則有,其中 為正交陣(為一系列平面旋轉(zhuǎn)陣的乘積).,記 ,則 有QR分解,其中 為正交矩陣， 為非奇異上三角陣.,用 變換實(shí)現(xiàn) 的正交三角約化需要 次乘法，,而用吉文斯變換約化計(jì)算約需要 次,次開方運(yùn)算，,乘法，,次開方運(yùn)算.,38,這說明，對一般矩陣 用吉文斯變換實(shí)現(xiàn) 的 正交三角約化比用 變換實(shí)現(xiàn) 的正交三角約化，計(jì)算量 要大一倍.,但是，如果 為三對角陣或上海森伯格陣，則需要約 化為零的元素比較少，這時(shí)用吉文斯變換實(shí)現(xiàn) 的正交三 角約化就顯得簡單、經(jīng)濟(jì).,39,5.7.4 求解超定方程組,設(shè) ，其中 .,當(dāng) 時(shí)稱為超定方,線性最小二乘問題：,尋求 使,如果使上式成立的 存在，稱 為超定方程組最小 二乘解.,程組，,一般地，沒有通常意義下的解.,對超定方程組，,記殘差向量 ，,于是,40,即尋求 使偏差 的平方和最小.,設(shè) 且 具有線性無關(guān)的列，可利用 的正交約化來求超定方程組的最小二乘解.,由正交約化定理，可選擇初等反射陣,使,且同時(shí)約化常數(shù)項(xiàng),41,其中， 為非奇異矩陣，,令 ,因?yàn)?為正交矩陣，,于是,所以,當(dāng)選取 為 的解時(shí),42,殘差向量達(dá)到極?。?43,算法7,設(shè) ，其中 ，,本算法利用正交三角約化 ,其中 為非奇異陣，,求 ,達(dá)到極小的殘差向量沖掉 .,(超定方程組),(列滿秩)，,使,且設(shè),(1) 正交約化