迭代改善法課件

迭代改善法6、露凝無(wú)游氛，天高風(fēng)景澈。7、翩翩新來(lái)燕，雙雙入我廬，先巢故尚在，相將還舊居。8、吁嗟身后名，于我若浮煙。9、陶淵明（約365年—427年），字元亮，（又一說(shuō)名潛，字淵明）號(hào)五柳先生，私謚“靖節(jié)”，東晉末期南朝宋初期詩(shī)人、文學(xué)家、辭賦家、散文家。漢族，東晉潯陽(yáng)柴桑人（今江西九江）。曾做過(guò)幾年小官，后辭官回家，從此隱居，田園生活是陶淵明詩(shī)的主要題材，相關(guān)作品有《飲酒》、《歸園田居》、《桃花源記》、《五柳先生傳》、《歸去來(lái)兮辭》等。10、倚南窗以寄傲，審容膝之易安。迭代改善法迭代改善法6、露凝無(wú)游氛，天高風(fēng)景澈。7、翩翩新來(lái)燕，雙雙入我廬，先巢故尚在，相將還舊居。8、吁嗟身后名，于我若浮煙。9、陶淵明（約365年—427年），字元亮，（又一說(shuō)名潛，字淵明）號(hào)五柳先生，私謚“靖節(jié)”，東晉末期南朝宋初期詩(shī)人、文學(xué)家、辭賦家、散文家。漢族，東晉潯陽(yáng)柴桑人（今江西九江）。曾做過(guò)幾年小官，后辭官回家，從此隱居，田園生活是陶淵明詩(shī)的主要題材，相關(guān)作品有《飲酒》、《歸園田居》、《桃花源記》、《五柳先生傳》、《歸去來(lái)兮辭》等。10、倚南窗以寄傲，審容膝之易安。5.6.2迭代改善法首先用選主元三角分解法實(shí)現(xiàn)分解計(jì)算如何對(duì)其精度進(jìn)行改善.2計(jì)算剩余向量然后改善33.輸出迭代改善方法迭代次失敗信息當(dāng)不是過(guò)分病態(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)用迭代改善法需要用原始矩陣且用雙倍字長(zhǎng)精度計(jì)算剩余向量，其他計(jì)算用單精度.7計(jì)算結(jié)果如下表.如果需要更多的數(shù)位，迭代可以繼續(xù).85.7矩陣的正交三角化及應(yīng)用95.7.1初等反射陣

定義9設(shè)向量且，為初等反射陣(或稱為豪斯霍爾德（Householder）變換).如果記,則稱矩陣10

定理25設(shè)有初等反射陣,(1)是對(duì)稱矩陣，即(2)是正交矩陣，即(3)設(shè)為對(duì)稱矩陣，那么亦是對(duì)稱矩陣.

證明只證的正交性，其他都可通過(guò)驗(yàn)證得到.其中則：11是一個(gè)初等反射陣.初等反射陣的幾何意義.考慮以為法向量且過(guò)原點(diǎn)的超平面.設(shè)任意向量，則,其中.設(shè)向量,則顯然于是12圖5-1對(duì)于，從而對(duì)任意向量，其中為關(guān)于平面S的鏡面反射(見(jiàn)圖5-1).總有13

定理26設(shè)為兩個(gè)不相等的維向量，則存在一個(gè)初等反射陣，

證明令，而且使則得到一個(gè)初等反射陣14因?yàn)樗允鞘钩闪⒌奈ㄒ婚L(zhǎng)度等于1的向量(不計(jì)符號(hào)).

定理27設(shè)，則存在初等反射陣,使，(約化定理)其中15

證明記,設(shè),取，于是由定理22存在變換其中,使記其中則有于是顯然16如果和異號(hào)，那么計(jì)算時(shí)有可能出現(xiàn)兩相近數(shù)相減的情況，有效數(shù)字可能損失.取和有相同的符號(hào)，即取在計(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ì)算第行與第行元素，即對(duì)有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è)已完成對(duì)上述第1步…第步的約化，再進(jìn)行第步約化.即存在初等反射陣使其中28其中為階上三角陣，不妨設(shè)，(如果列滿秩，則).于是，可選取初等反射陣使令否則這一步不需要約化29第步約化為這就使的三角化過(guò)程前進(jìn)了一步.其中左上角的階子矩陣為階上三角陣.令，繼續(xù)上述過(guò)程，最后有30第步需要計(jì)算及，第步約化大約需要次乘法運(yùn)算.

定理29且計(jì)算量約為(當(dāng))次乘法運(yùn)算.(矩陣的正交約化)設(shè)且則存在初等反射陣使31

定理30初等反射陣(1)設(shè)且的秩為，其中為階非奇異上三角陣.(2)設(shè)為非奇異矩陣，則有分解其中為正交矩陣，為上三角矩陣.當(dāng)具有正對(duì)角元時(shí)，分解唯一.(矩陣的QR分解)則存在使32(2)由設(shè)及定理29，存在初等反射陣記,即其中為正交矩陣，為上三角陣.

證明(1)由定理29可得.使則上式為33唯一性.設(shè)有其中為正交陣，為非奇異上三角陣，且具有正對(duì)角元素，由假設(shè)及對(duì)稱正定矩陣的Cholesky分解的唯一性，則.也可以用平面旋轉(zhuǎn)變換來(lái)約化矩陣.則從而可得34

定理31(1)存在正交矩陣設(shè)為非奇異矩陣，(用吉文斯變換計(jì)算矩陣的QR分解)則使(2)有QR分解其中為正交陣，為非奇異上三角陣，且當(dāng)對(duì)角元素都為正時(shí)，分解是唯一的.35

證明由設(shè)有使.若，(1)第1步約化：則可選擇吉文斯變換使可簡(jiǎn)記為,其中(2)第步約化：設(shè)上述過(guò)程已完成第1步至第步，于是有36由設(shè)有使，若，則可選擇吉文斯變換，使其中37(3)繼續(xù)上述約化過(guò)程，最后則有其中為正交陣(為一系列平面旋轉(zhuǎn)陣的乘積).記,則有QR分解其中為正交矩陣，為非奇異上三角陣.用變換實(shí)現(xiàn)的正交三角約化需要次乘法，而用吉文斯變換約化計(jì)算約需要次次開(kāi)方運(yùn)算，乘法，次開(kāi)方運(yùn)算.38這說(shuō)明，對(duì)一般矩陣用吉文斯變換實(shí)現(xiàn)的正交三角約化比用變換實(shí)現(xiàn)的正交三角約化，計(jì)算量要大一倍.但是，如果為三對(duì)角陣或上海森伯格陣，則需要約化為零的元素比較少，這時(shí)用吉文斯變換實(shí)現(xiàn)的正交三角約化就顯得簡(jiǎn)單、經(jīng)濟(jì).39

5.7.4求解超定方程組設(shè)，其中.當(dāng)時(shí)稱為超定方

線性最小二乘問(wèn)題：尋求使如果使上式成立的存在，稱為超定方程組最小二乘解.程組，一般地，沒(méi)有通常意義下的解.對(duì)超定方程組，記殘差向量，于是40即尋求使偏差的平方和最小.設(shè)且具有線性無(wú)關(guān)的列，可利用的正交約化來(lái)求超定方程組的最小二乘解.由正交約化定理，可選擇初等反射陣使且同時(shí)約化常數(shù)項(xiàng)41其中，為非奇異矩陣，令,因?yàn)闉檎痪仃?，于是所以?dāng)選取為的解時(shí)42殘差向量達(dá)到極?。?3

算法7設(shè)，其中，本算法利用正交三角約化,其中為非奇異陣，求,達(dá)到極小的殘差向量沖掉.(超定方程組)(列滿秩)，使且設(shè)(1)正交約化對(duì)于44(3)求解三角形方程組(5)求達(dá)到極小的殘差向量對(duì)于求最小二乘解45

例12的最小二乘解.

解(1)正交約化(a)利用算法6，選擇,用正交約化方法求超定方程組記使46于是其中47于是(b)對(duì)于利用算法6，確定使48(2)求解