解三對角方程組的追趕法

解三對角方程組的追趕法第1頁，共90頁，2023年，2月20日，星期四2第二章解線性方程組的直接方法如果用矩陣形式簡記為其中系數(shù)矩陣稱為三對角方程組.是一種特殊的稀疏矩陣.它的非零元素集中分布在主對角線及其相鄰兩條對角線上，稱為三對角矩陣.方程(2-23)(2-24)p5第2頁，共90頁，2023年，2月20日，星期四3第二章解線性方程組的直接方法Gauss消去法用于三對角方程組時過程可以大大簡化.具體地說，第一次消元只要對第2個方程進行，也就是矩陣其中,第一次消元后，第2個方程變成第3頁，共90頁，2023年，2月20日，星期四4第二章解線性方程組的直接方法因而在第二次消元時只要對第3個方程進行消元，即是單位下二對角陣

中.因此類推可以得出,三對角矩陣作三角分解時,矩陣的形式也比較簡單，其中第4頁，共90頁，2023年，2月20日，星期四5第二章解線性方程組的直接方法定理2.2

設矩陣（2-24）滿足下列條件：

是上二對角陣.p2第5頁，共90頁，2023年，2月20日，星期四6第二章解線性方程組的直接方法

其中則它可以分解為為矩陣（2-24）中所給出,且分解是唯一的.(2-25)第6頁，共90頁，2023年，2月20日，星期四7第二章解線性方程組的直接方法

[證明]將式(2-25)右端按乘法規(guī)則展開,并與A進行比較,得如果，則由上式可得（2-26）p11第7頁，共90頁，2023年，2月20日，星期四8第二章解線性方程組的直接方法按Gauss消去法步驟易得，經(jīng)過次消元后,方程組（2-23）的系數(shù)矩陣變成第8頁，共90頁，2023年，2月20日，星期四9第二章解線性方程組的直接方法其中

由A滿足條件（*），顯然有又因為從而有于是第9頁，共90頁，2023年，2月20日，星期四10第二章解線性方程組的直接方法故且矩陣仍滿足條件（*）.依次類推可得出因此由式(2-26)唯一地確定了L和U當矩陣（2-24）按式（2-26）可化為求解方程組和解得（2-27）計算進行三角分解后,求解方程組（2-23）第10頁，共90頁，2023年，2月20日，星期四11第二章解線性方程組的直接方法

再解得方程組（2-23）的解:(2-28)按上述過程求解三對角方程稱為追趕法,式（2-26）和式（2-27）結合稱為“追”的過程,相當于Gauss消去法中的消元過程.式(2-28)稱為“趕”的過程,相當于回代過程.p87第11頁，共90頁，2023年，2月20日，星期四12第二章解線性方程組的直接方法2．對1.輸入算法2.2第12頁，共90頁，2023年，2月20日，星期四13第二章解線性方程組的直接方法

5．輸出4.對,停機.追趕法的基本思想與Gauss消去法及三角分解法相同,只是由于系數(shù)中出現(xiàn)了大量的零，計算中可將它們撇開,從而使得計算公式簡化，也大大地減少計算量.其乘除運算量為第13頁，共90頁，2023年，2月20日，星期四14第二章解線性方程組的直接方法§2.4平方根法與改進的平方根法的對角元素皆為正數(shù)。工程實際問題的計算中，線性方程組的系數(shù)矩陣常常具有對稱正定性，矩陣的這一特性使它的三角分解也有更簡單的形式，從而導出一些特殊的解法。2.4.1平方根法（Cholesky分解法）定理2.3設是對稱正定矩陣,則存在唯一的非奇異下三角陣使得（2-29）且第14頁，共90頁，2023年，2月20日，星期四15第二章解線性方程組的直接方法[證明]因為A由定理2.1,矩陣A

其中角矩陣,且為單位下三角矩陣。則為上三角陣，令因為對稱正定,其各階順序主子式大于零,存在Doolitle分解，即為單位上三對稱，故有第15頁，共90頁，2023年，2月20日，星期四16第二章解線性方程組的直接方法由Doolitle分解的唯一性，得對任意非零向量于是由即正定，所以的對角元素均為正數(shù)。令即是正定的第16頁，共90頁，2023年，2月20日，星期四17第二章解線性方程組的直接方法其中唯一性。假設存在非奇異下三角陣則為非奇異下三角陣,且對角元素皆為正數(shù).元素皆為正數(shù)，且使得其對角于是有第17頁，共90頁，2023年，2月20日，星期四18第二章解線性方程組的直接方法因為是上三角陣，即，與假設矛盾。

上式必得是下三角陣,故由矩陣的這種分解稱為Cholesky分解。用比較法可以導出設的計算公式.p14第18頁，共90頁，2023年，2月20日，星期四19第二章解線性方程組的直接方法的對角元素皆為正數(shù)。2.4.1平方根法（Cholesky分解法）定理2.3設是對稱正定矩陣,則存在唯一的非奇異下三角陣,使得（2-29）且矩陣的這種分解稱為Cholesky分解。用比較法可以導出設的計算公式.第19頁，共90頁，2023年，2月20日，星期四20第二章解線性方程組的直接方法比較與這里規(guī)定計算順序是按列進行，即

的相應元素，可得（2-30）第20頁，共90頁，2023年，2月20日，星期四21第二章解線性方程組的直接方法當矩陣A完成Cholesky分解后，求解方程組就轉化為依次求解方程組它們的解分別為即第21頁，共90頁，2023年，2月20日，星期四22第二章解線性方程組的直接方法Cholesky分解法。這種方法無需選主元，計算過程也是單元也少，只要存貯A的下三角部分和右端項b中存放在A的存貯單元，y,x存放在b但這種方法在求L時需作n了計算量.求解線性方程組的上述方法稱為平方根法，也稱為穩(wěn)定的.由于A的對稱性,平方根法的乘除運算量為數(shù)量級，約是Gauss消去法的一半.上機計算時,所需存貯,計算的存貯單元.次開方運算，這樣又增加第22頁，共90頁，2023年，2月20日，星期四23第二章解線性方程組的直接方法[解]顯然系數(shù)矩陣是正定矩陣,設

例用平方根法解線性方程組第23頁，共90頁，2023年，2月20日，星期四解得由由解得第24頁，共90頁，2023年，2月20日，星期四25第二章解線性方程組的直接方法2.4.2改進的平方根法其中為單位下三角矩陣，為對角陣.記定理2.3的證明過程表明，對稱正定矩陣A又可以做如下分解：法

)第25頁，共90頁，2023年，2月20日，星期四26第二章解線性方程組的直接方法注意到由比較法得第26頁，共90頁，2023年，2月20日，星期四27第二章解線性方程組的直接方法第27頁，共90頁，2023年，2月20日，星期四28第二章解線性方程組的直接方法由比較法可以導出分解的計算公式：

對（2-33）計算順序如下：第28頁，共90頁，2023年，2月20日，星期四29第二章解線性方程組的直接方法按式（2-33）進行Cholesky分解約增多一倍，乘除總運算量又變成計算是重復的。引進輔助量分解,雖然避免了開方運算,但在計算每個元時多了相乘的因子，故乘法運算次數(shù)比數(shù)量級，仔細分析式（2-33）可以看出，式中有許多，則式（2-33）可改寫成第29頁，共90頁，2023年，2月20日，星期四30第二章解線性方程組的直接方法（2-34）按式（2-34）進行分解相當，且避免了開方運算。分解，乘除運算量與Cholesky第30頁，共90頁，2023年，2月20日，星期四31第二章解線性方程組的直接方法矩陣作分解后，解方程組可分兩步進行：先解方程組

再由求具體計算公式為（2-35）p34第31頁，共90頁，2023年，2月20日，星期四32第二章解線性方程組的直接方法求解線性方程組的這一方法稱為改進平方根法，也叫法.例6

用改進平方根法求解方程組[解]容易驗證，系數(shù)矩陣

第32頁，共90頁，2023年，2月20日，星期四33第二章解線性方程組的直接方法按式（2-34）計算分解式，得為對稱正定陣。（2-34）第33頁，共90頁，2023年，2月20日，星期四34第二章解線性方程組的直接方法按式（2-35）計算，得（2-35）第34頁，共90頁，2023年，2月20日，星期四35第二章解線性方程組的直接方法所以，方程組的解為稱正定線性方程組的好辦法。平方根法與改進的平方根法不僅計算量僅是Gauss消去法的一半，其數(shù)值穩(wěn)定性良好，是求解中小型稠密對第35頁，共90頁，2023年，2月20日，星期四36§2.5誤差分析重要的作用。2.5誤差分析分析。向量和矩陣的范數(shù)及矩陣的條件數(shù)在研究

值方法所求得的用數(shù)線性方程組解的誤差分析中起著十分由于不同的算法計算效果不同，因此必須進行誤差第36頁，共90頁，2023年，2月20日，星期四372.5誤差分析2.5.1向量和矩陣的范數(shù)就是對向量大小的一種度量，借助于它可以刻畫中向量序列的收斂性。

中，向量的模在（一）向量的范數(shù)向量的范數(shù)是衡量向量大小的度量概念。例如，第37頁，共90頁，2023年，2月20日，星期四382.5誤差分析

一般地，定義范數(shù)如下：按一定的規(guī)則有若滿足且=0，當且僅當對任意實數(shù)都有一實數(shù)與之對應，記為定義2.1

設對任意向量對任意都有則稱為向量x的范數(shù)。40第38頁，共90頁，2023年，2月20日，星期四392.5誤差分析中的一種范數(shù)。容易驗證，向量的模符合以上三條件，因而它是按定義2.1，向量范數(shù)的具體形式可以有多種，（1）2-范數(shù)常用的有以下三種：第39頁，共90頁，2023年，2月20日，星期四402.5誤差分析（2）1-范數(shù)（3）

下面以∞-范數(shù)為例進行驗證。滿足是顯然的。由實數(shù)絕對值的性質，對任意實數(shù)，都有。

∞-范數(shù)故對任意向量（1）2-范數(shù)第40頁，共90頁，2023年，2月20日，星期四41有所以成立。如果中有兩個范數(shù)和存在實數(shù)使得對任意n維向量x，都有2.5誤差分析則稱這兩種范數(shù)是等價的。第41頁，共90頁，2023年，2月20日，星期四42對兩種等價范數(shù)而言，同一向量序列有相同的極限。∞-范數(shù)是等價的。有不難證明，1-范數(shù)，2-范數(shù)和例如，由式（2-36）與式（2-38），對任意2.5誤差分析所以，2-范數(shù)與∞-

范數(shù)是等價的。設則第42頁，共90頁，2023年，2月20日，星期四43事實上，中任意兩種范數(shù)都是等價的。是指任意一種向量范數(shù)。今后如果不作說明，2.5誤差分析（二）矩陣的范數(shù)類似于向量范數(shù)的定義，可以定義階矩陣的范數(shù)。第43頁，共90頁，2023年，2月20日，星期四44定義2.2

對任意n階方陣A，按一定的規(guī)則有一實數(shù)若滿足當且僅當

A=0；對任意實數(shù)都有與之對應，記為對任意兩個n階方陣A，B都有2.5誤差分析且（相容性條件）為矩陣A的范數(shù).則稱第44頁，共90頁，2023年，2月20日，星期四45~是向量范數(shù)定義的直接推廣，條件則使矩陣范數(shù)在數(shù)值計算中使用更為方便。這里2.5誤差分析常用的矩陣范數(shù):為n階方陣。設（1）1-范數(shù)或列范數(shù)第45頁，共90頁，2023年，2月20日，星期四462.5誤差分析(2)∞-范數(shù)或行范數(shù)其中表示矩陣(3)2-范數(shù)或譜范數(shù)的最大特征值(4)Frobenius范數(shù)可以證明這四種范數(shù)都滿足矩陣范數(shù)的定義,且第46頁，共90頁，2023年，2月20日，星期四定義:對任意的n階方陣和n維向量若不等式成立,則稱矩陣范數(shù)與向量范數(shù)是相容的.47p51第47頁，共90頁，2023年，2月20日，星期四48[證明]顯然且即當且僅當對所有有于是，對任意有所以2.5誤差分析例7

若對任意n方陣定義試證為矩陣A的范數(shù)(1-范數(shù)或列范數(shù))。第48頁，共90頁，2023年，2月20日，星期四492.5誤差分析對任意實數(shù)于是對于任意兩個n階方陣第49頁，共90頁，2023年，2月20日，星期四502.5誤差分析

所以是A的矩陣范數(shù)。第50頁，共90頁，2023年，2月20日，星期四512.5誤差分析定理2.4

設

A為n階方陣，是中的向量范數(shù)，則是一種矩陣范數(shù)，稱其為由向量范數(shù)誘導出的矩也稱算子范數(shù)。陣范數(shù)，顯然有p55(2-39)第51頁，共90頁，2023年，2月20日，星期四522.5誤差分析為單位向量，故顯然若則反之，若即對任意非零向量，有由定義2.1之，得所以。[證明]設為任意n階方陣，x為任意n維非零向量。因為第52頁，共90頁，2023年，2月20日，星期四532.5誤差分析對任意實數(shù)，由式（2-39）及定義2.1有對任意兩個n階方陣A和B第53頁，共90頁，2023年，2月20日，星期四542.5誤差分析由式（2-39），對任意n維非零向量x有即于是所以式（2-39）是矩陣A的范數(shù)。（2-39）第54頁，共90頁，2023年，2月20日，星期四552.5誤差分析由定理2.4的證明知，由向量范數(shù)誘導出的矩陣范，還滿足性質對任意n維向量，都有這一性質稱為矩陣范數(shù)與向量范數(shù)的相容性，數(shù)除滿足定義2.2中的（2-40）在誤差分析中經(jīng)常會用到。第55頁，共90頁，2023年，2月20日，星期四562.5誤差分析常用的矩陣范數(shù)有三種，是由三種常用的向量范數(shù)為n階方陣。誘導出的矩陣范數(shù)：設(1)1-范數(shù)(2)∞-范數(shù)第56頁，共90頁，2023年，2月20日，星期四572.5誤差分析其中是矩陣的最大特征值。證明可參考[3]。矩陣的行向量的1-范數(shù)的最大值，故它們又分別的特征值有關，所以又稱為譜范數(shù)。由式（2-37）和式（2-38），矩陣的1-范數(shù)為矩陣的列向量的1-范數(shù)的最大值，矩陣的-范數(shù)為被稱為矩陣的列范數(shù)和行范數(shù)。2-范數(shù)與(3)2-范數(shù)第57頁，共90頁，2023年，2月20日，星期四582.5誤差分析這三種范數(shù)中，1-范數(shù)與2-范數(shù)有一些好性質，故在理論證明常用它。-范數(shù)的計算比較簡單，而2-范數(shù)較復雜，要計算矩陣的特征值。但數(shù)值計算中還有一種常用的范數(shù)(4)F-范數(shù)第58頁，共90頁，2023年，2月20日，星期四592.5誤差分析矩陣的F-范數(shù)可以認為是向量2-范數(shù)的直接推廣，陣的F-范數(shù)與向量的2-范數(shù)相容，但F-范數(shù)不是對任意一種由向量范數(shù)誘導出的矩陣范數(shù)都有即將n階方陣看作維向量所得到.可以證明，矩由向量范數(shù)誘導出的矩陣范數(shù).而因為如果將矩陣范數(shù)看作向量范數(shù)的等價性可得矩陣范數(shù)的等價性。空間上的向量范數(shù)，則由第59頁，共90頁，2023年，2月20日，星期四602.5誤差分析是A的近似矩陣，分別稱為的關于范數(shù)與相對誤差。矩陣的誤差可用矩陣范數(shù)表示.設的絕對誤差第60頁，共90頁，2023年，2月20日，星期四612.5誤差分析即有擾動，從而使計算結果產(chǎn)生誤差，因此需的解為2.5.2方程組的狀態(tài)與條件數(shù)一個實際問題化為數(shù)學問題，初始數(shù)據(jù)往往會有誤差，要研究擾動對解的影響。例8:容易看出，方程組第61頁，共90頁，2023年，2月20日，星期四622.5誤差分析而方程組

的解為比較這兩個方程組可以看出，它們只是右端項有微，但它們的解小的差別，最大相對誤差為卻大不相同，解分量的相對誤差至少為第62頁，共90頁，2023年，2月20日，星期四632.5誤差分析當一個方程組，由于系數(shù)矩陣或右端項的微小擾動，就系數(shù)矩陣或右端項分別有擾動的兩種情況進有擾動相應的解x的擾動記為而引起解發(fā)生巨大變化時，稱該方程組是“病態(tài)”的，為了定量刻畫方程組“病態(tài)”的程度，下面對方程組行討論。的擾動對解的影響。設首先考察右端項b即第63頁，共90頁，2023年，2月20日，星期四642.5誤差分析由，得從而有兩邊取范數(shù)，得又因為所以（2-41）第64頁，共90頁，2023年，2月20日，星期四652.5誤差分析式（2-41）表明，當右端項有擾動時，解的相對誤如果右端項無擾動，系數(shù)矩陣A有擾動相應的擾動仍記為則消去得差不超過右端項的相對誤差的倍。的解第65頁，共90頁，2023年，2月20日，星期四662.5誤差分析如果充分小，使得則由上式得因而有第66頁，共90頁，2023年，2月20日，星期四672.5誤差分析式（2-42）表明，當系數(shù)矩陣有擾動時，解的擾動仍與有關。一般地，若系數(shù)矩陣A有擾動右端項有擾動相應的解x有擾動且則有越大，解的擾動就可能也越大。第67頁，共90頁，2023年，2月20日，星期四682.5誤差分析綜合上述各式可以得出，當系數(shù)矩陣或右端項有控制了解的擾動程度。也就是定義2.3

對非奇異矩陣A，稱數(shù)為矩陣A的條件數(shù)，記為擾動時，數(shù)說，數(shù)可以反映方程組的狀態(tài)。第68頁，共90頁，2023年，2月20日，星期四692.5誤差分析引入條件數(shù)后，式（2-41）和式（2-42）可改寫為第69頁，共90頁，2023年，2月20日，星期四702.5誤差分析因此，系數(shù)矩陣A的條件數(shù)刻畫了方程組的“病態(tài)”程度，條件數(shù)越大，“病態(tài)”越嚴重。定義:設線性方程組如果系數(shù)矩陣A非奇異,且條件數(shù)cond(A)很大,則稱是病態(tài)方程組或稱A為病態(tài)矩陣.如果條件數(shù)cond(A)相對很小,則稱為良態(tài)方程組,或稱A為良態(tài)矩陣.第70頁，共90頁，2023年，2月20日，星期四712.5誤差分析矩陣的條件數(shù)與所取范數(shù)有關，最常用的條件數(shù)有(2-43)(2-44)其中分別為矩陣的的最大的特征值和又稱為譜條件數(shù)。最小特征值，故第71頁，共90頁，2023年，2月20日，星期四72特別地，如果A為實對稱矩陣，為A的特征值，且則2.5誤差分析第72頁，共90頁，2023年，2月20日，星期四732.5誤差分析例8中，方程組的系數(shù)矩陣為其逆矩陣為于是有條件數(shù)很大，所以方程組是“病態(tài)”的。第73頁，共90頁，2023年，2月20日，星期四742.5誤差分析條件數(shù)有以下性質：因為由定義2.2(2)

對任意非零實數(shù)，有(3)若A為正交矩陣，則(1)對任意n階方陣A，都有第74頁，共90頁，2023年，2月20日，星期四752.5誤差分析例9

已知方程組的解為若把系數(shù)取成2位有效數(shù)字的小數(shù)，得方程組第75頁，共90頁，2023年，2月20日，星期四762.5誤差分析求解此方程組，并分析所的結果。[解]用Gauss消去求解，第一次消元得第76頁，共90頁，2023年，2月20日，星期四772.5誤差分析第二次消元得回代得解比較兩個方程組可以看出，它們的右端項系數(shù)相同，系數(shù)矩陣中元的最大相對誤差僅為0.01，而得到的解卻嚴重失重。這表明原方程組“病態(tài)”嚴重。第77頁，共90頁，2023年，2月20日，星期四782.5誤差分析事實上，原方程組的系數(shù)矩陣為其逆矩陣為于是有條件數(shù)很大，所以方程組“病態(tài)”嚴重。第78頁，共90頁，2023年，2月20日，星期四792.5誤差分析原方程組的一般形式為是典型的“病態(tài)”方程組，稱為Hilbert方程組，n越大，“病態(tài)”越嚴重。如n=6時，嚴重“病態(tài)”的方程組，即使用主元素法求解也是數(shù)值不穩(wěn)定的。第79頁