




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、1.3 解線性方程組的迭代法(Iterative Methods for Linear Equations),2,求如下線性代數(shù)方程的解,解為,3,4,精確解為,5,定義1:對于任一向量 ,按照一定規(guī)則確定一個實數(shù)與之對應,該實數(shù)記為 ,若 滿足下面三性質: (1) 當且僅當X=0時, ; (2)對任意實數(shù)a, ; (3)對任意向量 ,滿足 那么,稱該實數(shù) 為向量X的范數(shù)。,一、 向量范數(shù)(Norm of Vector),1.3.1范數(shù)及有關性質,6,設,,則,是否為向量X的范數(shù)?,常用的三種向量范數(shù)有,(I)、 2范數(shù),(II)、 1范數(shù),(III)、 范數(shù),7,解:,8,二、矩陣的范數(shù),定
2、義2 設XRn,ARnn,則定義,為矩陣A的范數(shù)(算子范數(shù))。,9,二、矩陣的范數(shù),矩陣范數(shù)的性質:,性質: 向量范數(shù)的性質(1,2,3),4、對與矩陣A具有相同維數(shù)的向量X, 恒有,5、對于同階矩陣A,B有,(相容性),10,由此可以得到與前面三種向量范數(shù)對應的矩陣范數(shù)是,(I)、 2范數(shù),(II)、 列范數(shù),(III)、 行范數(shù),11,解:,12,如Rn中的 Rn 1和 Rn ,就存在如下關系:, Rn Rn 1 n Rn ,1/n Rn 1 Rn Rn 1,13,三、向量及矩陣序列的收斂問題,14,從上面范數(shù)的等價性可以推出,在某一種范數(shù)意義下向量序列收斂,則在任何一種范數(shù)意義下該向量序
3、列收斂。因此,一般按計算的需要采用不同的范數(shù),而不特別強調在那種范數(shù)意義下收斂。而且把向量序列X(k)收斂于向量X記為:,同樣,15,16,四、譜半徑,設nn階矩陣A的特征值為i(i=1,2,n) ,則稱,為矩陣A的譜半徑。, 矩陣范數(shù)和譜半徑的關系,17,18,五、擾動方程組的誤差分析,定義4 如果線性方程組AX=b中A或b的元素的微小變化,就會引起方程組解的巨大變化,則稱該方程組為“病態(tài)”方程組,矩陣為“病態(tài)”矩陣;否則稱方程組為“良態(tài)”方程組,矩陣為“良態(tài)”矩陣。,AX=b,A為非奇異陣,19,右端項擾動,解的相對誤差可能達到右端項相對誤差的AA-1倍,20,系數(shù)矩陣的擾動,設:,由,2
4、1,可見,右端項和系數(shù)矩陣的擾動對解的影響都與AA1有關。 A為非奇異陣,定義: cond(A)=AA1 為矩陣A的條件數(shù)。則有:,條件數(shù)cond(A)的值刻劃了方程組“病態(tài)”的程度。,22,條件數(shù)與所用范數(shù)有關。常用的矩陣條件數(shù)有:,23,方程病態(tài)的判斷方法,1.用主元素消去法求解時出現(xiàn)小主元; 2.某些行或某些列幾乎線性相關; 3.矩陣A的元素間數(shù)量級相差很大,且無規(guī)律; 4.當r=b-AXk的|r|很小時,Xk作為解的精度仍然很差或不符合要求。,24,一、簡單迭代法(Jacobi迭代),AX=b,方程組可改寫成多種迭代格式。,1.3.2 解線性代數(shù)方程組的迭代法,25,假設,令,迭代格式
5、:,26,令,27,當k時,若序列X(k)收斂到X*,則X*就是就是原方程的解。因為X*適合方程,以上計算過程稱簡單迭代法,矩陣B稱為簡單迭代法的迭代矩陣 。, k=0, 1, 2,.,28,X(0),,X(1) X(0),X(1) ,,否,. . .,X(m),,實際迭代求解過程:,29,二、Seidel(Gauss-Seidel,G-S) 迭代法, k=0, 1, 2,.,簡單迭代法,30,二、Seidel(G-S) 迭代法,31,二、Seidel(G-S) 迭代法,令:,32,k=0,1,2, ., n,迭代格式,注 意:交換方程和未知數(shù)的次序都會影響Seidel迭代法的計算結果,但這種
6、交換對簡單迭代法是沒有影響的。,33,簡單迭代法,Seidel迭代法,它們有一個共同的特點,就是新的近似解X(k+1)是已知近似解X(k)的線性函數(shù),并且X(k+1) 只與X(k)有關, 這類迭代叫做單點線性迭代。,34,例 1 方程組,從任意選取的初始向量X(0)出發(fā),利用迭代格式(a)構造向量序列X(k) ,該向量序列是否一定收斂呢?,35,1.3.3 迭代法的收斂性及誤差估計,例 2,36,定理5 對任何初始向量X(0)和常數(shù)項f,由迭代式,產生的向量序列X(k)收斂的充分必要條件是,其中:(M)是矩陣M的譜半徑。,證明: 1必要性,假設,令,37,2 充分性,結論:,條件:,收斂,有唯
7、一解,記為X*,設:,38,該定理說明:迭代是否收斂只與迭代矩陣的譜半徑有關,而迭代矩陣M是由系數(shù)矩陣A 演變過來的。所以迭代是否收斂與系數(shù)矩陣A以及演變方式有關,與常數(shù)項和初始迭代向量的選擇無關。,39,對例1來說,迭代矩陣,對例2來說,迭代矩陣,具體問題中,(M)1很難計算。但由于(M) |M|,所以,可以用|M|來作為(M)的一種估計,當|M|1,迭代一定收斂,不過這只是收斂的充分條件。,40,定理 6 若|M|1,則迭代序列X(k)的第k次近似值X(k)和準確解X*有估計式,根據這一定理,在實際計算中,若允許誤差是,則只要相鄰兩次迭代向量的差滿足關系式 就停止迭代,41,證明:,42,
8、定理 7 若迭代矩陣M的范數(shù)|M|=q1,則迭代格式,的第k次迭代X(k) 對于準確解X*的誤差有估計式,根據這一定理,可以粗略估計達到要求精度所需的迭代次數(shù)。,43,證明:,由于,所以,44,(1) 如果方程組Ax=b的系數(shù)矩陣A(aij)Rnxn為嚴格對角占優(yōu)矩陣,則對任意的初始向量,Jacobi迭代法和Gauss-Seidel迭代法收斂。 (2) 如果系數(shù)矩陣A是對稱正定矩陣,則Gauss-Seidel迭代法收斂。,45,例3 已知方程組,1) 證明用雅可比迭代法和高斯賽德爾迭代法求解均收斂。 2)寫出Jacobi法迭代的計算公式,取,3)寫出Gauss-Seidel法的計算公式,202
9、0/7/15,求方程的根:,4次以上的一元n次方程沒有一般公式解法!,由公式求解:,1.4 非線性方程(組)的解法,2020/7/15,1,方程可能有實根或者復根,本章學習求實根。,2,在有根的區(qū)間內,方程可能有單根、多根和重根,本章主要求單根。,本章主要內容是:求某一區(qū)間內的單實根。,2020/7/15,1.4.1 求實根的對分區(qū)間法,設f(x)=0在a,b內僅有一個實根 ,且有,a1 , b1,2020/7/15,a , b, a1 , b1, a2 , b2 , an , bn ,依此類推,可構造得到有根區(qū)間序列:,后一區(qū)間為前一區(qū)間的一半,所以稱該方法為對分區(qū)間法或二分法。若取,為方程
10、根的近似值*,則有,2020/7/15,對分區(qū)間法計算過程歸納:,1、找出有根區(qū)間a, b,計算f(a),f(b); 2、計算f(a+b)/2f ; 3、判斷: 若f =0,停止; 若f * f(a)0, (a+b)/2, b a1, b1; 4、重復2, 3,直到停止或區(qū)間縮小到誤差范圍內。,特點:簡單,對于簡單問題常用,對f(x)的要求不高,收斂速度與比值為的等比級數(shù)相同。不能求偶重根。,2020/7/15, 1.4.2 迭代法,構造迭代格式:,得到序列:,初值x0,2020/7/15,解:方程改寫成等價的迭代形式,真實根,2020/7/15,則將x0=1代入后可得 x1=-6, x2=-
11、230, x3=-12063750,但是,若將方程改寫成如下的等價迭代形式,明顯不收斂。Why?,收斂,2020/7/15,定理1.4.1 設迭代函數(shù)(x)滿足:,當xa, b時,a (x) b; 存在正數(shù)L1,對任意xa, b,均有,2020/7/15,證明:,1、作函數(shù)H(x)= (x)-x,可證明a, b必存在根,2、反證法,可證明a, b的根是唯一的。,2020/7/15,3、證明收斂性,(c),2020/7/15,反復使用(b)式,結合(c)式得,(d),2020/7/15,(1),(2),1、 L越小,收斂越快,因此,稱L為漸進收斂因子。 2、由(1)式,可給出迭代終止條件; 3、
12、由(2)式,可計算所需的迭代次數(shù); 4、定理中的條件是充分的,但不是必要的。,2020/7/15,定義1.4.1 對方程x =(x) ,若存在根的某個鄰域Q : |x- |,且具有性質:對任意的初值x0 Q , xk+1 =(xk) (k=0,1,2,)收斂,則稱xk+1 =(xk)在的鄰域Q內具有局部收斂性。,定理1.4.2 設為方程x =(x)的根, (x) 在的某鄰域內Q一階導連續(xù),且|()|1,則迭代法xk+1 =(xk) 具有局部收斂性。,由于求根時,根并不是已知的,因此,此定理的意義在于:適當?shù)恼{整初值,有可能使迭代法收斂。,2020/7/15,設迭代格式xk1(xk)收斂, 若記
13、ek=xk-.定義1.4.2 若存在實數(shù)p1和c0滿足,則稱該迭代格式p階收斂。當p1時,稱為線性收斂,當p1時稱為超線性收斂,當p2時稱為平方收斂。,2020/7/15,定理1.4.3 如果x(x) 中的迭代函數(shù)(x) 在根附近滿足:1、 (x) 存在連續(xù)的p階導數(shù);2、,則迭代法 xk1(xk) 為 p 階收斂。,證明:,2020/7/15,由于,所以,2020/7/15,例3:求方程x=e-x在0.5, 0.7內的根,并使近似根的誤差小于10-3(取x0 = 0.5進行計算)。,解:,迭代收斂,迭代格式,說明0.5, 0.7為有根區(qū)間。,2020/7/15,迭代法的優(yōu)點是簡單,但對收斂性
14、的要求較高,收斂速度與(x)有密切關系,且有些迭代格式 x =(x) 不收斂。,0.00057 10-3,2020/7/15, 1.4.3 牛頓法(Newton法),一、基本算法,解非線性方程的牛頓法是把非線性方程f(x)=0線性化的一種近似方法。,2020/7/15,牛頓法的迭代序列:,牛頓法的幾何意義:(切線法),n=0,1,2,2020/7/15,例5:用牛頓法求下面方程的根(x0=1),解:,迭代公式:,取x0=1,2020/7/15,二、收斂性估計,此式表明牛頓法具有平方收斂速度。,如果f(x)在一重零點附近存在連續(xù)的二階微商,且初始值x0充分接近于 ,那么牛頓迭代法是收斂的,其收斂
15、速度為,2020/7/15,將f()在xn處作Taylor級數(shù)展開,得,略去高階小量,然后兩邊同除以f(xn),整理得,即,2020/7/15,再化簡,得,兩邊取極限,得,所以,Newton法是二階收斂的。,2020/7/15,1、收斂速度快,可以求重根和復根;(優(yōu)點) 2、需計算導數(shù)值; (缺點),簡化牛頓法:,計算量小,但收斂速度相對較慢。,牛頓法特點:,2020/7/15, 1.4.4 Newton下山法,Newton法收斂速度快,但初值不易確定,而且往往由于初值取得不當而使迭代不收斂。,2020/7/15,但若能保證 | f (xn) | | f (xn+1) | (1)下山條件 則有可能防止迭代發(fā)散。為此先用牛頓法計算,然后引入,n=0,1,2,2020/7/15,加權平均:,合并后:,其中,為下山因子,上式稱為Newton下山法。,一般由試算決定,分別取 11/2 1/22 1/23直到滿足下山條件。若對于一個初值取不到滿足下山條件的,則稱“下山失敗”,需另取初值。 |f (xn+1
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 餐廳服務員崗位面試問題及答案
- 醫(yī)療器械注冊專員崗位面試問題及答案
- 2025屆湖北省蘄春縣高二化學第二學期期末綜合測試模擬試題含解析
- 景區(qū)規(guī)劃組團管理辦法
- 林業(yè)校園食堂管理辦法
- 供熱辦法分戶管理辦法
- 根據處方管理辦法關于
- 校園踩踏事故管理辦法
- 景區(qū)考察接待管理辦法
- 投資策略:股權市場分析
- 肺動脈高壓講課件
- 呼吸困難的識別與護理
- 熱射病的護理
- 小學英語學科融合教學心得體會
- 《高級工程師施工管理》課件
- 中國2型糖尿病防治指南(2024版)解讀課件
- 2024年三副貨物積載與系固題庫
- 康養(yǎng)項目的可行性研究報告
- 2025年四川成都東部新區(qū)政務服務中心招聘窗口人員18人歷年自考難、易點模擬試卷(共500題附帶答案詳解)
- TCAMA 109-2024 半封閉溫室設計規(guī)范
- 《摩爾根果蠅實驗》課件
評論
0/150
提交評論