解線性方程組的迭代法

關于解線性方程組的迭代法第1頁，課件共55頁，創(chuàng)作于2023年2月1引言我們知道，凡是迭代法都有一個收斂問題，有時某種方法對一類方程組迭代收斂，而對另一類方程組進行迭代時就會發(fā)散。一個收斂的迭代法不僅具有程序設計簡單，適于自動計算，而且較直接法更少的計算量就可獲得滿意的解。因此，迭代法亦是求解線性方程組，尤其是求解具有大型稀疏矩陣的線性方程組的重要方法之一。 6.1迭代法的基本概念第2頁，課件共55頁，創(chuàng)作于2023年2月2迭代法的基本思想

迭代法的基本思想是將線性方程組轉(zhuǎn)化為便于迭代的等價方程組，對任選一組初始值，按某種計算規(guī)則，不斷地對所得到的值進行修正，最終獲得滿足精度要求的方程組的近似解。

迭代法的基本思想設非奇異，，則線性方程組

有惟一解，經(jīng)過變換構(gòu)造出一個等價同解方程組第3頁，課件共55頁，創(chuàng)作于2023年2月將上式改寫成迭代式選定初始向量,反復不斷地使用迭代式逐步逼近方程組的精確解,直到滿足精度要求為止。這種方法稱為迭代法如果存在極限

則稱迭代法是收斂的，否則就是發(fā)散的。迭代法的基本思想第4頁，課件共55頁，創(chuàng)作于2023年2月收斂時，在迭代公式中當時，,則,故是方程組的解。對于給定的方程組可以構(gòu)造各種迭代公式。并非全部收斂

迭代法的基本思想第5頁，課件共55頁，創(chuàng)作于2023年2月例1用迭代法求解線性方程組

解構(gòu)造方程組的等價方程組據(jù)此建立迭代公式取計算得例題第6頁，課件共55頁，創(chuàng)作于2023年2月例題迭代解離精確解越來越遠迭代不收斂

第7頁，課件共55頁，創(chuàng)作于2023年2月1雅可比（Jacobi）迭代法1.雅可比迭代法算法構(gòu)造

6.2雅可比迭代法與高斯-賽德爾迭代法例2用雅可比迭代法求解方程組第8頁，課件共55頁，創(chuàng)作于2023年2月例題解：從方程組的三個方程中分離出和第9頁，課件共55頁，創(chuàng)作于2023年2月例題建立迭代公式取初始向量進行迭代,可以逐步得出一個近似解的序列：（k=1,2,…）第10頁，課件共55頁，創(chuàng)作于2023年2月直到求得的近似解能達到預先要求的精度，則迭代過程終止，以最后得到的近似解作為線性方程組的解。當?shù)降?0次有計算結(jié)果表明，此迭代過程收斂于方程組的精確解x*=(3,2,1)T。

例題第11頁，課件共55頁，創(chuàng)作于2023年2月寫成例題考察一般的方程組，將n元線性方程組

第12頁，課件共55頁，創(chuàng)作于2023年2月13若,分離出變量例題據(jù)此建立迭代公式上式稱為解方程組的Jacobi迭代公式。第13頁，課件共55頁，創(chuàng)作于2023年2月2.雅可比迭代法的矩陣表示

設方程組的系數(shù)矩陣A非奇異，且主對角元素，則可將A分裂成記作A=L+D+U雅可比（Jacobi）迭代法第14頁，課件共55頁，創(chuàng)作于2023年2月則等價于即因為

，則這樣便得到一個迭代公式雅可比（Jacobi）迭代法第15頁，課件共55頁，創(chuàng)作于2023年2月其中

雅可比（Jacobi）迭代法稱為雅可比迭代公式,B稱為雅可比迭代矩陣則有（k=0,1,2…）令第16頁，課件共55頁，創(chuàng)作于2023年2月雅可比迭代矩陣表示法，主要是用來討論其收斂性，實際計算中，要用雅可比迭代法公式的分量形式。即

雅可比（Jacobi）迭代法在例2中,由迭代公式寫出雅可比迭代矩陣為第17頁，課件共55頁，創(chuàng)作于2023年2月雅可比（Jacobi）迭代法(k=0,1,2,…)第18頁，課件共55頁，創(chuàng)作于2023年2月3高斯-塞德爾（Gauss-Seidel）迭代法1.高斯-塞德爾迭代法的基本思想在Jacobi迭代法中，每次迭代只用到前一次的迭代值，若每次迭代充分利用當前最新的迭代值，即在求時用新分量代替舊分量,就得到高斯-賽德爾迭代法。其迭代法格式為：

高斯-賽德爾迭代法(i=1,2,…,n

k=0,1,2,…)第19頁，課件共55頁，創(chuàng)作于2023年2月例3用GaussSeidel迭代格式解方程組精確要求為ε=0.005

解GaussSeidel迭代格式為例題第20頁，課件共55頁，創(chuàng)作于2023年2月例題取初始迭代向量,迭代結(jié)果為：x*≈第21頁，課件共55頁，創(chuàng)作于2023年2月2.Gauss—Seidel迭代法的矩陣表示

將A分裂成A=L+D+U，則等價于

(L+D+U)x=b，于是,則高斯—塞德爾迭代過程因為,所以則高斯-塞德爾迭代形式為：故令高斯-賽德爾迭代法第22頁，課件共55頁，創(chuàng)作于2023年2月我們知道,對于給定的方程組可以構(gòu)造成簡單迭代公式、雅可比迭代公式、高斯-塞德爾迭代公式，但并非一定收斂?，F(xiàn)在分析它們的收斂性。對于方程組經(jīng)過等價變換構(gòu)造出的等價方程組在什么條件下迭代序列收斂？迭代法的收斂性第23頁，課件共55頁，創(chuàng)作于2023年2月定理1迭代公式收斂的充分必要條件是迭代矩陣G的譜半徑。迭代法的收斂性第24頁，課件共55頁，創(chuàng)作于2023年2月由此定理可知，不論是雅可比迭代法、高斯—塞德爾迭代法還是簡單迭代法，它們收斂的充要條件是其迭代矩陣的譜半徑

。

事實上,在例1中,迭代矩陣G=，其特征多項式為,特征值為-2，-3，,所以迭代發(fā)散

迭代法的收斂性第25頁，課件共55頁，創(chuàng)作于2023年2月定理2(迭代法收斂的充分條件)若迭代矩陣G的一種范數(shù),則迭代公式收斂。迭代法的收斂性第26頁，課件共55頁，創(chuàng)作于2023年2月例5已知線性方程組考察用Jacobi迭代和G-S迭代求解時的收斂性解:⑴雅可比迭代矩陣例題第27頁，課件共55頁，創(chuàng)作于2023年2月⑵將系數(shù)矩陣分解則高斯-塞德爾迭代矩陣例題故Jacobi迭代收斂第28頁，課件共55頁，創(chuàng)作于2023年2月故高斯—塞德爾迭代收斂。

例題第29頁，課件共55頁，創(chuàng)作于2023年2月定理3設n階方陣為對角占優(yōu)陣,則非奇異。（證明省略）迭代法的收斂性系數(shù)矩陣為對角占優(yōu)陣的線性方程組稱作對角占優(yōu)方程組。第30頁，課件共55頁，創(chuàng)作于2023年2月定理4對角占優(yōu)線性方程組的雅可比迭代公式和高斯-賽德爾迭代公式均收斂。迭代法的收斂性第31頁，課件共55頁，創(chuàng)作于2023年2月定理5若方程組的系數(shù)矩陣A是對稱正定的，

則G－S迭代法收斂。迭代法的收斂性第32頁，課件共55頁，創(chuàng)作于2023年2月例6設求解線性方程組的雅可比迭代

求證當<1時,相應的高斯-塞德爾迭代收斂例題第33頁，課件共55頁，創(chuàng)作于2023年2月34證:由于B是雅可比迭代的迭代矩陣,故有例題第34頁，課件共55頁，創(chuàng)作于2023年2月∴系數(shù)矩陣為對角占優(yōu)陣,故G-S迭代收斂例題則又<1,故有第35頁，課件共55頁，創(chuàng)作于2023年2月例7設,證明,求解方程組的Jacobi迭代與G-S迭代同時收斂或發(fā)散例題第36頁，課件共55頁，創(chuàng)作于2023年2月37證:雅可比迭代矩陣例題其譜半徑第37頁，課件共55頁，創(chuàng)作于2023年2月G-S迭代矩陣其譜半徑顯然,和同時小于、等于或大于1,因而Jacobi迭代法與G-S迭代法具有相同的收斂性例題第38頁，課件共55頁，創(chuàng)作于2023年2月例9考察用雅可比迭代法和高斯-塞德爾迭代法解線性方程組Ax=b的收斂性，其中例題第39頁，課件共55頁，創(chuàng)作于2023年2月40解：先計算迭代矩陣例題雅可比矩陣第40頁，課件共55頁，創(chuàng)作于2023年2月求特征值例題

(B)=0<1∴用雅可比迭代法求解時，迭代過程收斂第41頁，課件共55頁，創(chuàng)作于2023年2月例題高斯-塞德爾迭代矩陣第42頁，課件共55頁，創(chuàng)作于2023年2月例題1=0,2=2,3=2(G1)=2>1

∴用高斯-塞德爾迭代法求解時，迭代過程發(fā)散求特征值第43頁，課件共55頁，創(chuàng)作于2023年2月例12討論用雅可比迭代法和高斯-塞德爾迭代法解線性方程組Ax=b的收斂性。例題第44頁，課件共55頁，創(chuàng)作于2023年2月45解：先計算迭代矩陣例題雅可比矩陣第45頁，課件共55頁，創(chuàng)作于2023年2月求特征值例題1=-1，2,3=1/2

(B)=1∴用雅可比迭代法求解時，迭代過程不收斂第46頁，課件共55頁，創(chuàng)作于2023年2月求特征值高斯-塞德爾迭代矩陣例題第47頁，課件共55頁，創(chuàng)作于2023年2月例題1=0,(G1)=0.3536<1∴用高斯-塞德爾迭代法求解時，迭代過程收斂第48頁，課件共55頁，創(chuàng)作于2023年2月求解AX=b,當取何值時迭代收斂？

例13給定線性方程組AX=b

用迭代公式X(K+1)=X(K)+(b-AX(K))(k=0,1,…）例題第49頁，課件共55頁，創(chuàng)作于2023年2月50解:所給迭代公式的迭代矩陣為例題第50頁，課件共55頁，創(chuàng)作于2023年2月即2-(2-5)+1-5+4

2=0

2-(2-5)+(1-)(1-4)=0

[-(1-)][-(1-4)]=0

1=1-2=1-4例題(B)=max{|1-|,|1-4|}<1取0<<1/2迭代收斂第51頁，課件共55頁，創(chuàng)作于2023年2月

本章介紹了解線性方程組迭代法的一些基本理論和具體方法。本章小結(jié)迭代法是一種逐次逼近的方法，即對任意給定的初始近似解向量，按照某種方法逐步生成近似解序列，使解序列的極限為方程組的解。注意到在使用迭代法第52頁，課件共55頁，創(chuàng)作于2023年2月

解方程組時，其迭代矩陣B和迭代向量f在計算過程中始終不變,迭代法具有循環(huán)的計算公式,