計算方法全書課件完整版ppt整本書電子教案最全教學教程ppt課件

1、計算方法計算方法課程組計算方法課程組12第1章 緒論1.1 計算方法概述科學計算與計算方法數學模型與計算方法計算方法的特點及學習方法1.2 誤差計算機的浮點表示及算術運算誤差來源誤差的基本概念誤差分析3應用舉例1問：今有問：今有上禾三秉，中禾二秉，下禾一秉，實三十九斗；上禾三秉，中禾二秉，下禾一秉，實三十九斗；上禾二秉，中禾三秉，下禾一秉，實三十四斗；上禾二秉，中禾三秉，下禾一秉，實三十四斗；上禾一秉，中禾二秉，下禾三秉，實二十六斗。上禾一秉，中禾二秉，下禾三秉，實二十六斗。問上、中、下禾實一秉各幾何？問上、中、下禾實一秉各幾何？ 九章算術九章算術3239xyz2334xyz2326xyz例：

2、一個古老的數學問題例：一個古老的數學問題4應用舉例應用舉例1 14線性方程組數值求解線性方程組數值求解1112111212222211nnnnnnnnaaaxbaaaxbaaaxb Axb 例：人口預測例：人口預測表格中是我國表格中是我國1950年到年到2005年的人口數（見年的人口數（見中國統(tǒng)計年鑒），試預測未來的人口數中國統(tǒng)計年鑒），試預測未來的人口數插值與曲線擬合插值與曲線擬合 年份年份人口人口(萬萬)1950551961955614651960662071965725381970829921975924201980987051985105851199011433199512112120

3、001267432005130756應用舉例應用舉例2 26例：例：鋁制波紋瓦的長度問題鋁制波紋瓦的長度問題建筑上用的一種鋁制波紋瓦是由機器將一塊平整的鋁板壓建筑上用的一種鋁制波紋瓦是由機器將一塊平整的鋁板壓制而成。假若要求波紋瓦長制而成。假若要求波紋瓦長 4 英尺，每個波紋的高度英尺，每個波紋的高度(從中從中心線心線)為為 1 英寸，且每個波紋以近似英寸，且每個波紋以近似 2 英寸為一個周期。英寸為一個周期。求制做一塊波紋瓦所需鋁板的長度求制做一塊波紋瓦所需鋁板的長度 L。應用舉例應用舉例3 37這個問題就是要求由函數這個問題就是要求由函數 f(x)=sin x給定的曲線從給定的曲線從 x=

4、0 到到 x=48 英寸間的弧長英寸間的弧長 L，即，即:數值積分與數值微分數值積分與數值微分484822001( ) d1(cos ) dLfxxxx上述積分為第二類橢圓積分，無法用普通方法來計算上述積分為第二類橢圓積分，無法用普通方法來計算應用舉例應用舉例3 38Google 搜索引擎搜索引擎PageRank: 對搜索結果按重要性排序基本原理“從優(yōu)質的網頁鏈接過來的網頁必定還是優(yōu)質網頁”超鏈接AB A 對B 投一票若A的質量高，則該投票分數高1998年，美國斯坦福大學的Larry Page和Sergey Brin創(chuàng)立了Google公司應用舉例應用舉例4 49應用舉例應用舉例4 4由于所有網

5、頁的Pr值可由所有鏈向它的頁面的重要性加和得到MPr = Pr(M-I)Pr = 0 100103/1002/13/12/1003/12/102/10M矩陣特征值計算矩陣特征值計算 線性方程組求解問題線性方程組求解問題 蝴蝶效應 洛倫茲吸引子(Lorenz attractor)是由MIT大學的氣象學家Edward Lorenz在1963年給出的，他給出第一個混沌現象蝴蝶效應。 圖1 蝴蝶效應示意圖應用舉例應用舉例5 511 dxxydtdyrxyxzdtdzbzxydt 洛倫茲方程是大氣流體動力學模型的一個簡化的常微分方程組：應用舉例應用舉例5 512數值計算方法定義線性方程組的解法矩陣特征值

6、與特征向量的計算函數插值數值微分與積分非線性方程(組)的解法與最優(yōu)化問題的計算方法常微與偏微分方程的數值解法有關計算方法可靠性的理論研究,如方法的收斂性和穩(wěn)定性分析與誤差估計等.131.1.1 科學計算與計算方法科學計算與計算方法14計算工具15計算工具16計算工具17計算工具18計算古老年輕與時俱進 計算物理、計算化學、計算力學、 數量經濟、計算生物學.19理論研究科學實驗科學計算計算數學科學研究20科學計算風洞21科學計算計算機計算能力的提高，衍生了計算方法這門課程22 數值計算方法的應用極為廣泛，上至國防尖端科技，下至日常生活生產，如火箭和衛(wèi)星的設計與控制、飛機與汽車的優(yōu)化設計、尖端數控

7、機床、地質勘探與油氣開發(fā)、天氣預報、圖像處理、網絡搜索等方面都有數值計算方法的應用。 它作為一種科學方法已經滲透到許多不同的科學領域，并形成了一些諸如計算力學、計算物理、計算化學、計量經濟學、生物信息學等交叉學科。23計算方法與科學計算科學計算是人類從事科學活動和解決科學技術問題不可缺少的手段。計算機科學技術的發(fā)展，為科學計算及數據處理提供了高速和高精度的計算工具。計算機運算: 只能進行加，減，乘，除等算術運算和一些邏輯運算。24計算方法與科學計算實際實際問題問題數學數學模型模型 數值數值方法方法程序程序設計設計計算機計算機計算計算解答解答科學計算的過程科學計算的過程25三維地圖構建26三維地

8、圖構建（1）實際問題：空中航測（空中連續(xù)拍照）方法，構建某地三維地形圖。（2）數學模型：建立一個大型超定線性方程組。（3）數值方法：采用最小二乘方法求解該方程組的最小二乘解。（4）程序設計：任何語言。（5）計算機計算（6）問題的解，對解進行解釋。27數值計算方法定義數學的一個分支，它以數字計算機求解數學問題的方法與理論為研究對象，其內容包括:28數值計算方法定義線性方程組的解法矩陣特征值與特征向量的計算函數插值數值微分與積分非線性方程(組)的解法與最優(yōu)化問題的計算方法常微與偏微分方程的數值解法有關計算方法可靠性的理論研究,如方法的收斂性和穩(wěn)定性分析與誤差估計等.29為什么要學習計算方法為什么要

9、學習計算方法30舉例說明一311.求解線性方程組Ax=b，其中A為3階可逆方陣X=(x1, x2, x3)T;2.求代數方程x2+x-6=0在0,4上的根x*3.已知y=p(x)為x0, x1上的直線，滿足p(x0)= y0 ， p(x1)= y1求p(x2)4.計算定積分5.解常微分方程初值問題(0)0yxy 1(1)baIdxabx舉例說明二1.求解線性方程組Ax=B，其中A為20階可逆方陣X=(x1, x2, , x20)T;2.求代數方程xex=1在0,1上的根x*3.已知y=f(x)為x0, x1上的函數，滿足f(x0)= y0 ， f(x1)= y1求f(x2)4.計算定積分5.解

10、常微分方程初值問題321(1)lnbaIdxabx2(0)0yxyy線性方程組求解考慮線性代數方程組Ax=b的求解計算問題。其中系數矩陣A為一n階方陣，D=det(A)0Cramer法則 xi=Di / D i=1,2,n 33積分求解對于積分由微積分知識可知：只要找到被積函數f(x)的原函數F(x)，便有下列牛頓萊布尼茲公式badxxfI)()()()(aFbFdxxfba34積分求解原因一：原函數不能用初等函數表示成有限形式原因二：原函數過于復雜babadxxxdxxsin,sin232)(22xxxf) 322ln(216916323432)(2223xxxxxxxF35積分求解原因三：

11、f (x)以離散數據點形式給出xix0 x1xnyi = f(xi)y0y1yn36積分求解有了數學模型，并不一定能夠直接用計算機求解，因此我們需要學習計算方法!學習計算方法這門課程，能夠讓我們學會如何構造或選擇那些“好”的數值計算方法。37秦九韶算法考慮對任意給定的x, 計算代數多項式 (1.1.3) 的值的問題。nkknknnnnnxaaxaxaxaxP01110)(38秦九韶算法考慮對任意給定的x, 計算代數多項式 的值的問題。顯然，上式等價于nnnaxaxaxaxaxP1210)(nkknknnnnnxaaxaxaxaxP01110)(1.1.3)(1.1.5)391.1.3 計算方法

12、的特點及學習方法計算方法的特點及學習方法40課程特點計算方法是一門與計算機應用緊密結合、實用性很強的數學課程，它所涉及的數學問題面很廣、內容非常豐富，亦有其自身的體系它既有數學的高度概括，又非常講究實用性并具有高度的技巧性41課程特點第一，面向計算機，研究計算機上用的計算方法 （算法最終只可包含四則運算和邏輯運算）第二，要有可靠的理論分析 （算法收斂性、穩(wěn)定性及誤差分析）第三，要注重算法的效率 （計算時間、存儲空間）第四，要重視數值實驗42本課程的學習方法掌握構造方法的原理、思想，理解算法，會分析算法精度注重算法的效率和適用范圍，針對不同情況學會選擇和設計優(yōu)秀算法要重視實踐，通過算例和動手計算

13、，學會怎樣使用數值方法在計算機上解決各類數學計算問題431.2 1.2 誤差誤差44誤差計算機的浮點表示及算術運算誤差來源誤差的基本概念誤差估計451.2.11.2.1計算機的浮點表示及算術運算計算機的浮點表示及算術運算46數的浮點表示實數x在計算機中被表示為 x = 0.d1d2dk2p d1=1,di為0或1，i=2,3,k, -mpM.零的浮點數通常表示為 0 = 0.0002-m 47數的浮點表示實數x在計算機中被表示為 x = 0.d1d2dk2p d1=1,di為0或1，i=2,3,k, -mpM.零的浮點數通常表示為 0 = 0.0002-m 尾數階碼48數的浮點表示 x = 0

14、.d1d2dk2p (1.2.1)給定的二進制浮點計算機，只能表示所有形如上式的有限數集S=S(k,m,M)，這是實數軸上的不等距有限點集。49數的浮點表示 S=S(3,1,2) k=3， m=1， M=2， -1p2 那么計算機能表示的浮點數集合是如下的33個點。 0 = 0.0002-1 x= 0.1d2d3 2-1 x= 0.1d2d3 20 x= 0.1d2d3 21 x= 0.1d2d3 2250數的浮點表示 x= 0.1d2d3 2-1 x= 0.1d2d3 20 0.100 2-1=1/4 0.100 20=1/2 0.101 2-1=5/16 0.101 20=5/8 0.11

15、0 2-1=3/8 0.110 20=3/4 0.111 2-1=7/16 0.111 20=7/851數的浮點表示 x= 0.1d2d3 2-1 x= 0.1d2d3 20 0.100 2-1=1/4 0.100 20=1/2 0.101 2-1=5/16 0.101 20=5/8 0.110 2-1=3/8 0.110 20=3/4 0.111 2-1=7/16 0.111 20=7/80152數的浮點表示 x= 0.1d2d3 2-1 x= 0.1d2d3 20 0.100 2-1=1/4 0.100 20=1/2 0.101 2-1=5/16 0.101 20=5/8 0.110 2-

16、1=3/8 0.110 20=3/4 0.111 2-1=7/16 0.111 20=7/80153數的浮點表示例如單精度實數用32位的二進制表示，其中符號位占1位，尾數占23位，階數占8位，可以寫成如下形式 x = 0.d1d2d232p |p| 27-1 (1.2.2)注意上面的8位階數中須有1位表示階數的符號，所以階數值占7位。54數的浮點表示例如單精度實數用32位的二進制表示，其中符號位占1位，尾數占23位，階數占8位，可以寫成如下形式 x = 0.d1d2d232p |p| 27-1 (1.2.2)注意上面的8位階數中須有1位表示階數的符號，所以階數值占7位。55浮點數的四則運算設是

17、S10由所有形如 0.d1d2d3d4 10p的4位十進制浮點數的集合，其中1 d19，0 di9，i = 2, 3, 4, 整數p滿足-9 p10。下面舉例說明S10上的算術運算。56浮點數計算特點加減法先對階(將階碼統(tǒng)一為較大者)，后計算，再舍入乘除法先運算再舍入不在計算機數系中的數做四舍五入處理57例1.1(1) 0.2015104 + 0.1911102 0.2015104 + 0.0019104 對階 0.2034104 計算(2) 0.2015104 + 0.191110-1 0.2015104 + 0.0000104 對階 0.2015104 計算(3) 0.2015104 -

18、0.2008104 0.0007104 計算 0.7000101 規(guī)范化58例1.1(4) (0.2015104) (0.191110-5) (0.20150.1911) 10-1 對階 (0.3851 10-1) 10-1 計算 0.3851 10-2 規(guī)范化(5) (0.2015104) (0.191110-5) (0.20150.1911) 109 對階 (0.1054 101) 109 計算 0.1054 1010 規(guī)范化59浮點數計算特點計算過程中應該注意絕對值相差懸殊的兩個數做加減，會造成“大數吃小數”的現象；（例2）非常接近的數相減，會損失掉有效數字； （例3）相對被除數來說，絕

19、對值很小的數做除數，會產生絕對值很大的數，甚至溢出； （例5）在運算過程中注意合理安排運算順序，以便提高運算的精度或保護重要的參數。60例1.2在前面所述的4位十進制浮點計算機（數集S10）上求解如下一元二次方程 x2 24 x +1 = 0 (1.2.3)按求根公式，此方程的兩個根是在4位十進制浮點計算機上， 0.1196102，于是按照上面求根公式有 x1=0.2396102, x2=0.400010-1143121x143-122x14361下面我們換一種方法進行計算x2，即 (1.2.4)則x2=0.417410-1。事實上，x2的精確解應為0.0417393。143121143-12

20、2x62問題631.2.2 1.2.2 誤差來源誤差來源64誤差的來源實際實際問題問題數學數學模型模型 數值數值方法方法程序程序設計設計計算機計算機計算計算解答解答模型誤差模型誤差方法誤差方法誤差觀測誤差觀測誤差舍入誤差舍入誤差65例1.3為了計算函數值ex，| x | 0，并滿足 | e* | = |x* - x| * (1.2.7) 則稱*為近似值x*的絕對誤差限，或簡稱誤差限。69相對誤差定義1.3 設x為精確值，x*為近似值，則稱比值 (1.2.8)為近似值x*的相對誤差，記作er*（實際應用時，常用x*代替上式分母中的x）。xxxxe*70相對誤差限定義1.4 設*是近似值x*的誤差

21、限，則稱 (1.2.9) 為近似值x*的相對誤差限，此時，有 (1.2.10)*xr*rxxxx71有效數字定義1.5 如果 | e* | = |x* - x| 0.510-n (1.2.11) 則說x*近似表示x準確到10-n位（小數點后第n位），并從此位起直到最左邊的非零數字之間的一切數字都稱為有效數字，并把有效數字的位數稱為有效位數。72例1.4取e（e = 2.718281828459 ）的近似值x* = 2.72，則 |2.72 e | 0.001718 0.510-2即x*近似表示e準確到10-2位，因此具有3位有效數字。若取e的近似值x* = 2.71828，則 |2.71828

22、 e | 0.0000018 0.510-5即x*近似表示e準確到10-5位，因此具有6位有效數字。73有效數字定義1.6 將x的近似值x*表示為十進制浮點數的標準形式 x* = 0.d1d2dk 10m (di=0,1,9, d10) (1.2.12)如果 | e* | = |x* - x| 0.510m-n (1.2.13)則說近似值x*具有n位有效數字。這里n是正整數，m是整數。74例若x*=3578.64是x的具有6位有效數字的近似值，試求x*的誤差限。75有效數字與相對誤差的關系定理1.1 若近似值x*具有n位有效數字，則其相對誤差滿足 (1.2.14)反之，如果x*的相對誤差er*

23、滿足 (1.2.15)則x*至少具有n位有效數字。*-(1)11102nred*-(1)11102(1)nred761.2.4 1.2.4 誤差分析誤差分析77誤差分析將帶有誤差的數據進行計算時，誤差在運算過程中會進行傳播，必然導致計算結果出現誤差。一般來說，精確值x與近似值x*之間都比較接近，其誤差可以看作是一個小的增量，即可以把誤差看作微分，即 e* = x* - x = dx這表明：x的微分表示x的誤差，ln x的微分表示x的相對誤差xxxxeerlndd*78(1.2.16)(1.2.17)誤差分析根據上式，可以得到算術運算的誤差，以x, y兩數為例 e* (xy) = d (xy)

24、= d x d y = e* (x) e* (y) e* (xy) = d (xy) = y d x + x d y = y e* (x) + x e* (y) er* (xy) = d ln(xy) = d ln(x) + d ln(y) = er*(x) + er*(y)0()()(ddd2*2*yyyxexyeyyxxyyxyxe)0()()()ln(d)ln(dlnd*yyexeyxyxyxerrr79誤差分析而更一般的情況是，當自變量有誤差時計算函數值時也會產生誤差。其誤差可以用函數的Taylor展開式進行估計。2* *)(2)()()()(xxfxxxfxfxf)()()()()(

25、*xexfxfxfxfe80例1.5已知 由于 的精確值未知，取 1.414進行計算，試問上述3個表達式哪個計算精度最高？f1(x)=(x-1)6f2(x)=99-70 xf3(x)=270991270-991-262281例1.582例1.5830.6320.3680.2640.2080.1680.1600.0400.720例1.6考慮積分 (1.2.25)的近似計算.此積分滿足遞推關系式 In = 1 nIn-1, (1.2.26)假定我們首先計算出I0的近似值 ，保留3位有效數字，利用遞推關系式(1.2.26)依次算出101dxexIxnn0I0I1I2I5I4I6I3I7I84例1.6

26、10=1-1=1-0.632=0.368II21=1-2=1-0.736=0.264II6=0.040I76=1-7=1-0.280=0.720II85例1.6根據積分公式那么1110100，使得對于一切xRn有214,stxx12stscxxcx21xxn xxxn x（2.5.8）（2.5.9）向量的范數向量序列收斂性向量序列收斂性定義定義2. 2 設x(k)= ( x1(k), x2(k), xn(k)T 為Rn 上的一個向量序列(k=1,2,)， x*= ( x1*, x2*, xn*)TRn. 如果對于i=1,2, n 有 則稱向量序列x(k 收斂于向量x*。 215*)(limik

27、ikxx向量的范數容易證明，x(k) 收斂于向量x*的充要條件是再由(2.5.8)和(2.5.9)式可知，上式成立等價于2160lim*)(xxkk0lim2*)(xxkk0lim1*)(xxkk矩陣范數 定義定義2.3設設 為為A的實值函數，若它滿足下的實值函數，若它滿足下列條件列條件（1）正定性）正定性 ，當且僅當，當且僅當A=0時等號成立時等號成立（2）齊次性）齊次性（3）三角不等式）三角不等式 則稱則稱 為為 上的一個上的一個矩陣范數矩陣范數（或矩陣模）（或矩陣模）, 的值稱為矩陣的值稱為矩陣A的范數的范數217n nR0 A ()kAkAkR C ,n nABABA BR ( )n

28、nARN AA()N AAAn nAR 矩陣范數相容范數相容范數218 , ,n nnn nABABA B RAxAxxR A R （ 2.5.13）（ 2.5.14）矩陣范數算子范數算子范數最常用的是利用向量范數來定義的矩陣范數矩陣范數稱之為矩陣A的算子范數算子范數，其中2191,2,p 01maxmaxppppxxpAxAAxx（ 2.5.15）矩陣范數證明：容易證明，由(2.5.15)式所定義的函數滿足定義2.3的三個條件，故它是矩陣范數。另外，當x=0時， (2.5.14)式顯然成立。對任意的x0,兩邊乘以即為(2.5.14)式。220定理2.3由(2.5.15)式所定義的矩陣范數為相

29、容范數:nnpRR0maxpppyppAxAyAxypx矩陣范數再來證(2.5.13)式。注意到由(2.5.14)式有定理證完。221,n nA BRnB xR111m ax m ax m ax pppppxppxppxppABABxABxABxAB矩陣范數定理2.4對于由(2.5.15)式所定義的矩陣范數下列等式成立：其中AT表示A的轉置矩陣。22211111m a xm a xnijinjnijjniAaAa2A(ATA之最大特征值之最大特征值)1/2(2.5.16)(2.5.17)(2.5.18)矩陣范數證明先證(2.5.16)式。首先，對任意滿足 的xRn，因為 ，故有2231x1jx

30、x1111111max ()max max()maxniijji ni njnnijjiji ni njjAXAxa xaxa 矩陣范數另一方面，設第k行為元素絕對值和最大的行，即則可令此時，x滿足且有2241x111maxnnkjiji njjaa 11111()()maxnnkkjjkjkjjjnnkjiji njjAxa xa sng aaa sgn()jijxa矩陣范數再證等式(2.5.18)，注意當 時，ATA是對稱非負定矩陣，故ATA有完全正交的特征向量系 ，即其中 為ATA的特征值22512,nv vvn nAR22(,)( ,)TTTAxAx Axx A Axx A Ax0,

31、( ,)1, Tii iijijA Avvv vij10n矩陣范數對于任意的xRn，借助于特征向量系可表示為且從而有2261niiixv2221( , )niixx x112111(, )(,) =(,)nnTTjji ijinnnjjji iiijiiA Ax xA Avvvv 矩陣范數227由于故有上式說明 是 的上界，并且這個上界在x=v1時達到。定理證完。2221111nnnniiiiiii 121222(, )TnxA Ax xAxx122A xx矩陣范數22811111m a xm a xnijinjnijjniAaAa2A(ATA之最大特征值之最大特征值)1/2行和范數行和范數列

32、和范數列和范數譜范數譜范數01maxmaxppppxxpAxAAxx（2.5.15）譜半徑矩陣A的特征值的按模最大值稱為A的譜半徑記作，即其中是A的特征值。定理1.6對任意 ，有2291( )maxii nA ( )Ain nAR( ) 1,2,pAAp譜半徑由譜半徑的定義,矩陣的2范數可記為當A是實對稱矩陣時，由（1.4.18）式有這也就是說，此時A的2范數與該矩陣的譜半徑相等。2302()TAA A22()()( )TAA AAA第2章 解線性方程組的數值法2.1 引入2.2 Gauss消元法2.3 矩陣的三角分解2.4 消元法在計算機上的實現2.5 向量和矩陣范數2.6 矩陣的條件數與病

33、態(tài)方程組矩陣的條件數與病態(tài)方程組2.7 迭代法2312.6 矩陣的條件數與病態(tài)方程組232病態(tài)方程組233例2.2 令 , 并設123123(,) ,(,)TTxxxxbb bb1/2 1/3 1/41/3 1/4 1/51/4 1/5 1/6A病態(tài)方程組234令Ly = b, 可解得于是，由Ux = y, 可解得112133123121546ybybbybbb11232123312372240180240900720180720600 xbbbxbbbxbbb病態(tài)方程組321332123211600720180 72090024018024072 bbbxbbbxbbbx235),(321b

34、bbb)1500,1860,492( xx病態(tài)方程組236定義 如果矩陣A或常數項b的微小變化,引起方程組Ax=b的巨大變化,則稱此方程組為“病態(tài)病態(tài)”方程組方程組,矩陣A稱為“病態(tài)”矩陣，否則稱方程組為“良態(tài)”方程組，A稱為“良態(tài)”矩陣。條件數237設A為非奇異矩陣,用x表示Ax=b的精確解,而 是擾動方程組的精確解.由Ax=b和(1.5.1)兩式相減,可知解的誤差 滿足方程由此x A xbbA xbxx x 1xAb條件數238利用矩陣的范數性質,有另外,由Ax=b又有由(1.5.2)式和(1.5.3)式,便可得:1pppxAbppppAxAxb1()ppppppxbAAxb條件數239設

35、 是下面擾動方程組的精確解。由Ax=b和(1.5.1)兩式相減，可知解的誤差 滿足方程由此x ()AA xb)(-xxAxAxx x )(-1xxAAx條件數240于是有即pppppxxAAxxAAx-1-1)(-ppppppAAAAxxx1 -條件數241定義2.5 設 為可逆矩陣,稱 為矩陣A在范數 意義下的條件數條件數.矩陣A的條件數越大，方程組的擾動誤差對方程組的解的影響越嚴重。因此稱條件數過大的方程組為病病態(tài)方程組。態(tài)方程組。n nARp1( )pppCondAAA第2章 解線性方程組的數值法2.1 引入2.2 Gauss消元法2.3 矩陣的三角分解2.4 消元法在計算機上的實現2.

36、5 向量和矩陣范數2.6 矩陣的條件數與病態(tài)方程組2.7 迭代法迭代法242 迭代法是求解線性代數方程組的另一類方法。由于它具有保持迭代矩陣不變的特點，因此迭代法特別適合求解大型稀疏系數矩陣的方程組。2.7 迭代法243迭代法的一般形式考慮求解線性代數方程組為了采用迭代法，首先要將方程組（2.7.1）改寫成等價的形式其中 為已知向量， 代表未知向量。244Axb(2.7.1),n nnijMRMmgRnxRxMxg(2.7.2)迭代法的一般形式給定初始近似值 ，定義向量序列稱為迭代序列迭代序列，并稱M為迭代矩陣迭代矩陣。245(0)nxR( )kx(1)( ) 0,1,2.kkxMxgk（2.

37、7.3）迭代法的一般形式如果當k時， 有極限，設為 ,則在等式（2.7.3）兩端取極限可得此式表明迭代序列的極限恰為方程組的解。因此，如果迭代序列收斂，則當k充分大時，可將x(k)取作方程組的近似解。246( )kx*nxR(1)( ) 0,1,2.kkxMxgk（2.7.3）( )kx*xMxg（2.7.4）迭代法的收斂性利用迭代公式（2.7.3）構造序列 ，以求得方程組（2.7.2）的近似解的算法稱為解（2.7.2）式的簡簡單迭代法單迭代法。若迭代序列 收斂，就稱此迭代法是收斂的。247( )kx( )kxxMxg(1)( ) 0,1,2.kkxMxgk（2.7.3）(2.7.2)迭代法的

38、收斂性顯然，只有收斂的迭代法才能使用，因此必須回答在何種條件下，由公式（2.7.3）所定義的 為收斂的向量序列248( )kx(1)( ) 0,1,2.kkxMxgk（2.7.3）迭代法收斂性為討論迭代法的收斂性，引入誤差向量 (k) = x (k) - x *則利用(2.7.2)和(2.7.4)可得 (k+1) = x (k+1) - x *= Mx (k) + g (Mx* + g) = M (x (k) x*) = M(k)于是可以迭代得出 (k+1) = M(k) = M 2(k-1) = = M k+1(0) (2.7.5)迭代法收斂，即 (k+1)0 (零向量) (k)。由于x(0

39、)是任給的，所以其充要條件是M k+10 (零矩陣) (k)。249迭代法的收斂性( )(1)kkxMxg250(1)( ) 0,1,2.kkxMxgk*xM xgxMxgAxb(2.7.1)(2.7.2)(2.7.4)(2.7.3)迭代法的收斂性根據上式可以判定，對任意x(0)即 的充分必要條件是 （零矩陣），k，由此得到下面結果.251( )*kxx( )0kM ( )*0kxx( )*(0)*(), 0,1,2,.kkxxM xxk迭代法的收斂性定理定理2.6 設M = (mij) R nn, 則M k0(k)的充要條件是(M) 1。定理定理2.7 迭代法(2.7.3)對任何初始近似值x

40、(0)均收斂的充分必要條件是迭代矩陣M的譜半徑(M) 1。推論推論2.1 若|M|1（|允許為任何一種相容范數）, 則迭代法(2.7.3)收斂。252(1)( ) 0,1,2.kkxMxgk(2.7.3)迭代法的收斂速度定理 當 時，由迭代法（2.7.3）式所定義的序列滿足如下估計式：證明略.2531H( )kx( )*( )(1)( )*(1)(0)11kkkkkHxxxxHHxxxxH一般迭代法的求解步驟依據方程組分離x得到迭代格式判斷迭代格式是否收斂迭代求解滿足終止條件,迭代結束254xMxg( 1)( )kkxM xg()(1)kkxx()1M1M雅可比迭代法例例2.3 求解方程組若將

41、方程組表示成如下形式2551552218474zyxzyxzyx4782145152xyzyxzzxy7421 481525yzxxzyxyz雅可比迭代法 給出了雅可比迭代格式 如果從初始點(x0, y0, z0) = (1, 2, 2) 開始，即將x0= 1, y0= 2, z0= 2代入（1.6.8）每個方程的右邊，可得到如下新值：256( )( )(1)( )( )(1)( )( )(1)7421 481525kkkkkkkkkyzxxzyxyz(1)(1)(1)72-241.7521 4283.375152253.00 xyz雅可比迭代法考慮方程組 Ax=b 其中 是非奇異的, 為已知

42、向量。將矩陣A寫成如下 A=D-L-U其中 為對角陣, -L, -U分別為A的嚴格下、上三角部分構成的三角陣。257n nARnbR11(,)nnDdiag aa雅可比迭代法2131321200000nnaLaaaa 258121312321,00000nnnnaaaaaUa雅可比迭代法當D非奇異,即aii0(i=1,2,n)時,可將方程組Ax=b寫成于是可得迭代格式稱此格式為求解方程組Ax=b的雅可比迭代法.注意到L+U=D-A,故(2.7.9)式也可寫成25911()xDLU xD b(2.7.9)(1)1( )1() 0,1,2,.kkxD L U xD bk(2.7.10)11()xI

43、D A xD b雅可比迭代法Jacobi方法的迭代矩陣為Jacobi迭代法的分量形式為26011()HDL UID A 1(1)( )( )111() 1,2, ,1,2, .inkkkiijjijjijj iiixa xa xbin ka (2.7.11)雅可比迭代法例2.4 求解方程組2611552218474zyxzyxzyx雅可比迭代法例2.4 求解方程組2621552218474zyxzyxzyx雅可比迭代法263kx(k)y(k)z(k)01.02.02.01-1.53.3755.026.6872.516.375334.68758.015625-17.254-46.61718817

44、.8125-123.734385-307.929688-36.150391211.281256502.62793-124.9296881202.56836高斯賽德爾迭代法簡單迭代法(2.7.3)的分量形式是可以用這些新值來計算 , 于是可得迭代格式這種方法稱為賽德爾迭代法.2641(1)( )( )1 1,2, , .inkkkiijjijjijj ixh xh xgin(1)kix1(1)(1)( )1 inkkkiijjijjijj ixh xh xg(2.7.12)高斯賽德爾迭代法對雅可比迭代(2.7.11)式運用賽德爾技巧得到稱(2.7.13)式為高斯賽德爾迭代法,其矩陣形式為并可整理

45、成一般迭代法的形式2651(1)(1)( )111() 1,2, .inkkkiijjijjijj iiixa xa xbina (2.7.13)(1)1(1)( )()kkkxDLxUxb(1)1( )1()()kkxDLUxDLb(2.7.14)高斯賽德爾迭代法例例2.5 試用Jacobi迭代法和Gauss-Seidel迭代法求解下面線性方程組，并分析其收斂性266123123123226+4223xxxxxxxxx 高斯賽德爾迭代法例例2.5 試用雅可比迭代法和高斯-賽德爾迭代法求解下面線性方程組，并分析其收斂性解解：雅可比迭代法和高斯-賽德爾迭代法的迭代公式分別為：2671231231

46、23226+4223xxxxxxxxx 111(1)( )( )23(1)( )( )23(1)( )( )326224322kkkkkkkkkxxxxxxxxx 111(1)( )( )23(1)(1)( )23(1)(1)(1)326224322kkkkkkkkkxxxxxxxxx 高斯賽德爾迭代法都將都將 作為初值進行計算，結果見表2.2。表表2.2 例例2.5計算結果計算結果268(0)(0)(0)123(,)(0,0,0)xxx迭代次數迭代次數Jacobi迭代法迭代法G-S迭代法迭代法kx(k)y(k)z(k)x(k)y(k)z(k)000000016-4-3621324-11-16

47、-7-49321390372514213-422-175-1197高斯賽德爾迭代法269下面分析其收斂性，設Jacobi方法和Gauss-Seidel方法的迭代矩陣分別為1022()101220JMDL U1022()021086G SMDLU高斯賽德爾迭代法270下面分析其收斂性，設雅可比方法和高斯-賽德爾方法的迭代矩陣分別為1022()101220JMDL U1022()021086GMDLU分別計算兩個矩陣的特征值即1 =2 =3=0, 故(MJ) = 00,求開方值的問題就是要解方程 x2-a=0這樣歸結出的是個非線性方程，從初等數學的角度來看它的求解有難度。該如何化難為易呢？2793

48、.1 引入設給定某個預報值x0,希望借助于某種簡單方法確定校正量x，使校正值x1=x0+x能夠比較準確地滿足所給方程x2-a=0，即有280axx203.1 引入設給定某個預報值x0,希望借助于某種簡單方法確定校正量x，使校正值x1=x0+x能夠比較準確地滿足所給方程x2-a=0，即有一般來說，x是一個小量，因此忽略掉x的平方項，上述方程便是一個關于x 的一次方程，據此寫出x ，從而對校正值x1=x0+x 有281axx2000121xaxx3.1 引入反復施行這種預報校正方法，即可導出開方公式從給定的某個初值x00出發(fā)，利用上式反復迭代，即可獲得滿足精度要求的開方值282kkkxaxx211

49、a3.1 引入283例例3.1：用開方算法求根號 =？誤差到10-6解：分別取x0=9和x0=20,90kkkxaxx211ixixi09.00000020.00000019.50000012.25000029.4868429.79846939.4868339.49178949.4868339.48683459.4868339.486833第三章 非線性方程（組）的數值解3.1 引入3.2非線性方程問題非線性方程問題3.3二分法3.4不動點迭代法3.5牛頓迭代法3.6解非線性方程組的牛頓迭代法284例例3.2 考慮下面的非線性方程(1) ex+1=0， (2) x6-2x5-8x4+14x3+

50、11x2-28x+12=0,(3) cosx=0;285例例3.2 考慮下面的非線性方程(1) ex+1=0，此方程無解(2) x6-2x5-8x4+14x3+11x2-28x+12=0,(3) cosx=0;(1)式無解；(2)式有三個解，x=1，-2，3，無論x取值的區(qū)間怎樣變化，只要它包含-2,3這個區(qū)間，解的性質和個數不變。但這三個解的性質又各不相同，x=3是一個單根，x= -2是兩重根，x=1則是三重根。(3)式隨x的取值范圍不同，解的個數也不同。事實上，在整個實數軸上有無窮多個解。在討論非線性問題時，通?？偸且鼜娬{“ “定義域定義域” ”，往往要求的是自變量在一定范圍內的解，道理

51、就在于此。286在科學研究和工程設計中, 經常會遇到的一大類問題是非線性方程 f(x) =0 的求根問題，其中f(x)為非線性函數。方程f(x)=0的根, 亦稱為函數f(x)的零點。 287如果f(x)是多項式函數，則稱為代數方程，否則稱為超越方程（三角方程，指數、對數方程等）。一般稱n次多項式構成的方程 為n次代數方程，當n1時,方程顯然是非線性的288111000 ()nnnnna xaxa xaa 給定如下非線性方程組 i=1,2,n （3.2.1)引入向量、向量函數記號 (3.2.2)則方程組可改為 F(x)=0 當n=1時，方程組(3.2.1)是一個非線性方程式 f(x) = 0 (

52、3.2.3)2890),(21nixxxf12nxxxx12( )( )( )( )nf xfxF xfx000 0定義定義3.1 設有x*使f(x*)=0則稱x*為方程(3.2.3)的根或根或零點零點。若存在正整數m,使f(x)=(x-x*)mg(x) (3.2.4)且0g(x*)+，則稱x*為(3.2.3)式的m重根重根。當m=1時，x*為單根，這時x*滿足條件f(x*)=0, f(x*) 0;290第三章 非線性方程（組）的數值解3.1 引入3.2非線性方程問題3.3二分法二分法3.4不動點迭代法3.5牛頓迭代法3.6解非線性方程組的牛頓迭代法291292 二分法的基本思想二分法的基本思

53、想: 首先確定有根區(qū)間,將區(qū)間二等分, 通過判斷f(x)的符號, 逐步將有根區(qū)間縮小, 直至有根區(qū)間足夠地小, 便可求出滿足精度要求的近似根。293二分法294例3.3 用二分法求方程f(x)=sinx-x2/4=0的非零實根的近似值，使誤差不超過10-2.解295例3.3 用二分法求方程f(x)=sinx-x2/4=0的非零實根的近似值，使誤差不超過10-2.解nanbnxn+1f(xn+1)01.521.750.21836111.7521.8750.075179621.87521.9375-0.049622831.8751.93751.902650.040420841.906251.937

54、51.9218750.15601451.9218751.93751.92968750.00536340第三章 非線性方程（組）的數值解3.1 引入3.2非線性方程問題3.3二分法3.4不動點迭代法不動點迭代法3.5牛頓迭代法3.6解非線性方程組的牛頓迭代法2963.4.13.4.1不動點迭代法不動點迭代法不動點迭代法是一種逐次逼近的方法，它的基本思想是通過構造一個遞推關系式 (迭代格式) ，計算出根的近似值序列,并要求該序列收斂于方程的根.將方程f(x)=0改寫成等價形式 x= (x) (3.4.1)定義定義3.2 稱所有滿足方程x = (x)的點x，為此方程的方程的不動點不動點。297取初始

55、迭代值x0，記x1 = (x0), x2 = (x1), , 一般有 (3.4.2)記數列x0, x1 ,xk,為xk，當k充分大時，如果xk有極限x*存在，即 (3.4.3)則對(2.1.6)式兩邊同時取極限，得 (3.4.4)這表明x*為等價方程x = (x)的不動點，即x*為方程f(x)=0的根。298kkxx1*kkxx lim *kkkk*xxxxlimlim1 上述求解方程f(x)=0的根的近似值的過程，稱為不動點迭代不動點迭代法法，其中(3.4.2)式中的(x)稱為迭代函數迭代函數，x0稱為迭代的初迭代的初始值始值，公式(3.4.2)稱為迭代格式迭代格式或迭代過程迭代過程，xk稱

56、為根x*的第k次近似值，xk稱為迭代數列迭代數列。若極限式(3.4.3)成立，則稱此迭代法為收斂的收斂的，否則稱為發(fā)散的發(fā)散的。 應用迭代法求方程根的基本問題是：1）化等價方程，構造迭代函數；2）研究迭代數列xk的收斂性、收斂速度及誤差估計。2993.4.2迭代法的幾何解釋迭代法的幾何解釋 通常將方程f(x)=0化為與它同解的方程x = (x)的方法不止一種,有的收斂,有的不收斂,這取決于(x)的性態(tài),方程x = (x)的求根問題在幾何上就是確定曲線y= (x)與直線y=x的交點P*的橫坐標。(a)(b)300迭代法的幾何意義迭代法的幾何意義 3013023.4.3 3.4.3 迭代法的收斂迭

57、代法的收斂定理定理3.1（收斂性定理收斂性定理）假定方程x = (x)滿足： 1) (x)在a,b上連續(xù)；2)當xa,b時, (x) a,b；3) (x)存在，且對任取xa,b有 (3.4.6)則方程x=(x) 在a,b上存在唯一不動點x*，且對任取x0a,b，由迭代格式 xk+1=(xk) , k=0,1,2,所定義xk收斂于唯一不動點x* ，即 同時下列誤差估計式成立 1L x*kkxx limkkkxxLxx1*11(3.4.7)01*1xxLLxxkk(3.4.8)證明證明：令h(x)=x-(x)，則h(x)在a,b上連續(xù)且可微。根據定理3.1的條件(2)知h(a)0, h(b)0，由

58、連續(xù)函數的介值定理，必有x*a,b，使h(x*)=0，即x*=(x*)。因此x*便為方程x=(x)于a,b內的不動點。假設另有 ，且 ，使 ，則由拉格朗日中值定理，得 其中 介于x*和 之間，因x*= ，故只有 ，這與定理3.1中|(x)|L1矛盾303,bax*xx )(xx)()()(*xxxxxxx0)(1)(*xxx1)(對任xa,b，由|(x)|L1得即對任xa,b， 。注意及304*111*2*120()()()()0kkkkkkkxxxxxxL xxL xxL xxk *limxxkkkkxxLxx*1*kkkkxxxxxx11*kkkxxxx11*得即(3.4.7)式成立，由于

59、再利用已證(3.4.7)式，即知(3.4.8)式成立。3051*1kkkkxxxxxxkkxxLxx*(1)kL xx111)()(kkkkkkxxLxxxx01212xxLxxLkkk306定理3.1給出了迭代法收斂的充分條件且十分適用。首先，對有根區(qū)間a,b并沒有限制其范圍大小，只要滿足條件1）2）3）即可，故a,b可取為任意有限大小的區(qū)間。因此，可視此定理為大范圍收斂定理大范圍收斂定理。其次，在收斂性的證明過程中可以看出，迭代序列收斂速度的快慢取決于L的大小，L越小，收斂越快。結論中的第一個誤差估計式可以作為上機控制迭代中止的一個條件；第二個誤差估計式可用于估計滿足指定誤差精度所需的迭代

60、次數k.307事實上，由定理的證明過程可知，定理的條件(3)可放寬為：若(x) 在a, b滿足Lipschitz條件，即對a, b 上的任意兩點x1, x2, 有且Lipschitz常數L1，則定理依然成立。 2121Lxxxx例3.4求方程 f(x)=xex-1=0 (或x=e-x) 在1/2,ln2中的解。若要求迭代次數k至少應為多少？3086*10kxx解：取迭代函數 ，當x1/2,ln2時， (x)連續(xù)可微，又 ，故(x)為單調下降函數，且有又可見，(x)滿足定理2.1的全部條件，因此x=e-x于1/2,ln2有唯一不動點，且由 所定義的迭代序列xk收斂到此不動點。取初值x0=1/2，