計算方法教案

第1章誤差分析與數(shù)值計算3§1.1引言3§1.2絕對誤差與相對誤差、有效數(shù)字9§1.3近似數(shù)的簡單算術運算12§1.4數(shù)值計算中誤差分析的一些原則13第2章非線性方程（組）的近似解法15§2.1引言15§2.2根的隔離16§2.3對分法16§2.3對分法17§2.4迭代法19§2.6弦截法21§2.6弦截法22§1.7用牛頓法解方程組23本章小結25第3章線性方程組的解法26§3.1引言26§3.2高斯消去法28§3.3矩陣的LU分解31§3.4對稱矩陣的LDLT分解32§3.5線性方程組解的可靠性33§3.6簡單迭代法34本章小結43第4章矩陣特征值與特征向量的計算44§4.1引言44§4.2冪法和反冪法45§4.3雅可比方法46§4.4QR方法*51本章小結52第5章插值與擬合53§5.1引言53§5.2插值多項式的存在和唯一性54§5.3拉格朗日插值多項式55§5.4均差插值公式57§5.5差分等距結點插值公式59§5.6愛爾米特插值公式61§5.7分段低次插值62§5.8三次樣條函數(shù)63§5.9曲線擬合的最小二乘法67本章小結70第6章數(shù)值積分和數(shù)值微分71§6.1引言71§6.2牛頓一科特斯型積分公式72§6.3復合求積公式74§6.4龍貝格求積公式77§6.5高斯求積公式78§6.6二重積分的數(shù)值積分法80§6.7數(shù)值微分81本章小結83第7章常微分方程的數(shù)值解法84§7.1引言84§7.2歐拉法和改進的歐拉法85§7.3龍格-庫塔方法86§7.4線性多步法89§7.5算法的穩(wěn)定性與收斂性91§7.6微分方程組和高階微分方程解法92本章小結94第1章誤差分析與數(shù)值計算§1.1引言1、課程任務和目的：在第七屆國際軟件工程學術會議上，“計算方法”被列入應用方法學的研究領域，強調了計算方法的研究應用與軟件方法學的研究密切結合。這就說明了計算方法與軟件之間的聯(lián)系以及在應用軟件研制中的地位與作用，計算方法是研究各種數(shù)學問題求解的數(shù)值計算方法。在計算機成為數(shù)值計算的主要工具的今天，則要求研究適合于計算機使用的數(shù)值計算方法。計算方法就是研究用計算機解決數(shù)學問題的數(shù)值方法及其理論，它的內(nèi)容包括函數(shù)的數(shù)值逼近、數(shù)值微分與數(shù)值積分、非線性方程值解、線性方程組數(shù)值解、常微和偏微數(shù)值解等，即都是以數(shù)學問題為研究對象的。因此，計算方法是數(shù)學的一個分支，只是它不象純數(shù)學那樣只研究數(shù)學本身的理論，是把理論與計算緊密結合，著重研究數(shù)學問題的數(shù)值方法及其理論，計算方法是計算機應用和軟件研制開發(fā)的重要組成部分，通過本課程的學習和上機實習，使學生掌握利用計算機進行科學計算的基本理論和基本方法，并且學會將基本理論和基本方法應用于軟件開發(fā)以及軟件研制。2、本課程基本要求（1）掌握方法的基本原理和思想。（2）掌握方法處理的技巧及與計算機的結合。（3）掌握誤差分析，收斂性及穩(wěn)定性的基本理論。（4）學會進行可靠的理論分析，對近似計算要確保精度要求，要進行誤差分析。（5）通過例子，學習使用各種計算方法解決實際計算問題。（6）通過上機實踐，能編寫算法和實現(xiàn)算法。（7）掌握數(shù)值計算中一些最基本、最常用的計算方法和算法。3、本課程與各課程的關系：由于本課內(nèi)容包括了微積分、代數(shù)、常微分方程的數(shù)值方法，學生必須掌握這幾門課的基本內(nèi)容才能學好這一課程，同時，學習此課程還必須具備計算機系統(tǒng)的初步知識，掌握一門常用的高級語言，如：BASIC、PASCAL、C語言等，并須具備一定的編程能力。4、本課程的特點：（1）面向計算機，要根據(jù)計算機特點提供實際可行的有效算法。即算法只能包括加、減、乘、除運算和邏輯運算，是計算機能直接處理的。（2）有可靠的理論分析，能任意逼近并達到精度要求，對近似算法要保證收斂性和數(shù)值穩(wěn)定性，還要對誤差進行分析，而且都是建立在相應數(shù)學理論基礎上的。（3）有好的計算復雜性。時間復雜性好是指節(jié)省時間；空間復雜性好是指節(jié)省存儲量。這也是建立算法時要研究的問題，因為它關系到算法能否在計算機上完成。（4）要有數(shù)值實驗。即任何一種算法除了從理論上要滿足上述三點外，還要通過數(shù)值實驗證明是行之有效的。計算方法最基本的立足點是容許誤差，在誤差容許的范圍內(nèi)對某一數(shù)學問題進行近似計算，得到能滿足要求的近似結果?，F(xiàn)實世界中誤差是普遍存在的，由于世界上沒有絕對精確的量具（絕對精確的量具是沒有刻度的），因此人類通過量具采集的數(shù)據(jù)都是近似值，另一方面，我們的生產(chǎn)、實驗工具都不是絕對精確的，這就使得人類在生產(chǎn)和科學實驗中必需容許誤差。計算機的應用可以分為二個方面，即數(shù)值計算和非數(shù)值計算。利用計算機進行數(shù)值計算的過程如下圖所示：SKIPIF1<0在上圖中，計算方法的任務是：由建立的數(shù)學模型給出可編程并由計算機能完成的計算方法，然后編程和上機求解。由于計算方法是編程后可由計算機求解的近似計算方法，如何確保近似解的精度顯得尤為重要，必須深入討論有關誤差的基本概念和基本理論，為近似計算的精度分析打下基礎。1、誤差的來源（種類）誤差的來源主要有以下四種（1）模型誤差：建立數(shù)學模型時的誤差。例如：在求重量的數(shù)學模型G=m*g中，重量G不是僅與質量和重力加速度有關，它還與溫度、測量地點的海拔、地層結構等眾多因素有關，為了使模型較為簡單和實用，采用抓住主要矛盾的方法，去掉了大量對重量影響不大的次要因素，建立了上述重量的近似模型，由此產(chǎn)生了模型誤差。（2）觀測誤差：采集數(shù)據(jù)時的誤差。采集數(shù)據(jù)時，通常是依靠儀器和量具，由于沒有絕對精確的儀器和量具，因此采集的數(shù)據(jù)有誤差，此誤差稱為觀測誤差。（3）舍入誤差：由于計算機字長有限而產(chǎn)生的誤差。硬件再發(fā)展，計算機的字長總是有限的，在計算過程中，當數(shù)據(jù)的長度超過了計算機的字長時，計算機就會進行四舍五入，由此產(chǎn)生的誤差稱為舍入誤差。（4）截斷誤差：無限形式的有限化而產(chǎn)生的誤差。在計算中有時會運用無限形式的計算公式，例如臺勞公式：SKIPIF1<0顯然此公式無法進行計算，因此必需根據(jù)實際需要，從某一項起將后面的各項截斷，即SKIPIF1<0由此產(chǎn)生的誤差稱為截斷誤差?！?.2絕對誤差與相對誤差、有效數(shù)字為描述方便，首先約定x*是精確值x的近似值。引入誤差的概念，其目的是為了衡量近似值x*的好壞。（1）絕對誤差：x*x由于精確值x通常無法確定，因此絕對誤差無法計算，由此引入絕對誤差限的概念。絕對誤差限：絕對誤差的一個上界。即：若|x*x|e，則稱e為x*的絕對誤差限。絕對誤差限的性質是：A.不唯一這是因為|x*x|的上界是不唯一的。B.可確定只要我們對x*的實際背景有一定的了解，就不難確定|x*x|的上界。例如，x*表示身高，則|x*x|的上界可為3米。當x*是你求出的，那么為了說明你的工作認真，你一定會將|x*x|的上界估計得盡量小，因此在這種意義上絕對誤差限可用來衡量x*的好壞。由于絕對誤差限沒有考慮問題的規(guī)模，因此有時它也不能衡量x*的好壞。例如：x是地球與太陽的距離，y是分子中二個原子間的距離，若|x*x|1公里，|y*y|1厘米，則并不能說y*比（2）相對誤差：(x*x)/x*相對誤差限：相對誤差絕對值的一個上界。3、有效數(shù)字這里我們必須搞清楚什么是有效數(shù)字以及如何確定x*有幾位有效數(shù)字。（1）有效數(shù)字的定義若|x*-x|<x*的某一位的半個單位，則稱x*精確到這一位，并從這一位開始，一直到前面第一個不為零的數(shù)都是x*的有效數(shù)字。此定義實際上定義了什么叫精確到某一位和什么叫有效數(shù)字。例如：若x*精確到小數(shù)點后第3位，即指|x*x|0.510-3。（2）有效數(shù)字的判定方法方法一：四舍五入此方法首先確定x*是由x的哪一位四舍五入產(chǎn)生的，然后從這一位的前一位開始一直到前面第一個不為零的數(shù)都是x*的有效數(shù)字。例1若x=0.872596,x*=0.87，求x*的有效位數(shù)。解：SKIPIF1<0x*是由x的小數(shù)點后第三位四舍五入產(chǎn)生的，所以x*有二位有效數(shù)字。注意，方法一判定有效數(shù)字很簡單，但有時會失效。例如，若x=0.272987x*=0.273102，此時無法用方法一確定x*的有效位數(shù)，原因是x*不是由x四舍五入產(chǎn)生的，在這種情況下，必須用有效數(shù)字的定義來確定x*的有效位數(shù)。即方法二：用定義此方法首先計算|x*x|，再判斷它小于等于x*的哪一位的半個單位，然后從近一位開始，一直到第一個不為零的數(shù)都是有效數(shù)字。例2若x=0.62073，x*=0.6207，確定x*的有效位數(shù)。解：因為|x*x|0.00030.5104，x*精確到小數(shù)點后第4位，所以x*有四位有效數(shù)字。例3若x=0.080199，x*=0.802，確定x*的有效位數(shù)。解：因為|x*x|=0.000010.5105，所以SKIPIF1<00.5103，推出x*有三位有效數(shù)字。例4若x=6.28936，x*=7.3132，確定x*的有效位數(shù)。解：|x*x|=0.023570.5101，所以x*有二位有效數(shù)字?！?.3近似數(shù)的簡單算術運算§1.4數(shù)值計算中誤差分析的一些原則為保證計算結果的高精度，在進行數(shù)值計算時應遵循下述幾個原則。（1）在進行除法時，要避免除數(shù)的絕對值<<被除數(shù)的絕對值。①為什么要“避免”？若不“避免”，則除出的結果很大，由于計算機字長有限，它裝不下，因此會進行四舍五入，一個很大的數(shù)進行四舍五入時舍去的部分也會很大，這會使舍入誤差變大。②怎樣“避免”？因為用戶只關心最后的計算結果，當中間計算過程中出現(xiàn)了除數(shù)的絕對值<<被除數(shù)的絕對值時，就應該換一種計算方法，以避免這種情況的發(fā)生，以后我們將會針對具體的計算問題來討論“避免”的方法。（2）在進行減法時，要避免二個相近的數(shù)相減。①為什么要“避免”？若不“避免”，就可能失去大量的有效數(shù)字，例如：若a=30001和b=30000都有五位有效數(shù)字，因為a-b=1，所以結果至多有1位有效數(shù)字。②怎么“避免”？“避免”的思路與第1個原則中“避免”的思路相同，須針對具體計算問題來討論。（3）要防止“大數(shù)吃小數(shù)”①什么是“大數(shù)吃小數(shù)”？我們用一個例子為說明。計算8756294874SKIPIF1<0，其中n=1020，0<ai<106。此題是一個很大的數(shù)與很多很小的數(shù)相加，若采用將大數(shù)依次與a1,a2,,an相加，由于計算機字長有限，因此在與ai相加時會進行四舍五入將ai舍去，這樣，最后的結果仍是大數(shù)，這就是大數(shù)將a1,a2,,an吃掉了。②為什么要“避免”？盡管每個小數(shù)都很小，但它們很多，可能它們的和比大數(shù)還大，而最后計算工結果為大數(shù)，顯然誤差可能很大。③怎樣“避免”？有的同學提出先將小數(shù)相加，然后再與大數(shù)相加，這個思路是對的，但有一個漏洞，因為小數(shù)相加到一定程度也會變成大數(shù)，它也開始吃小數(shù)了?？梢圆扇》植肯嗉拥姆椒ń鉀Q。第2章非線性方程（組）的近似解法§2.1引言方程f(x)=0的解稱為方程的根。也叫做函數(shù)f(x)的零點。方程求根大致包括三個問題（1）方程有沒有根？如果有根，有幾個根？（2）哪里有根？求有根的區(qū)間，區(qū)間內(nèi)的任意一點作為根的近似值。（3）根的精確化，已知一個根的近似值后設法逐步把根精確化，直到足夠精確為止。本課程主要研究問題（2）和（3）。§2.2根的隔離求方程f(x)=0的解的近似值時，首先要確定若干個區(qū)間，使每個區(qū)間內(nèi)只有的一個根，這個步驟稱為根的隔離。對一般的方程，根的隔離有兩種方法（1）試值法。求出f(x)在若干點上的函數(shù)值，觀察函數(shù)值符號變化的情況，從而確定隔根區(qū)間。（2）作圖法。畫出y=f(x)的草圖，觀察曲線y=f(x)與x軸交點的大致位置，從而確定隔根區(qū)間。例1.2.1討論方程f(x)=2x3-4x2+4x+2=0-1012-10-5-1012-10-5051011.52-1-0.500.5§2.3對分法11.52-1-0.500.5設有方程f(x)=0在（ab）內(nèi)有且僅有一個根x*，這時有f(a)f(b)<0可用對分法求x*的近似值，方法如下（1）準備：計算區(qū)間（ab）兩個端點的函數(shù)值f(a)，f(b)（2）對分：取c=(a+b)/2為（ab）的中點，計算f(c)

（3）判斷：如果f(c)=0，則c為f(x)=0的根，否則檢驗： 若f(c)f(a)<0，則方程的根位于[ac]內(nèi)，用c代替b，若f(c)f(b)<0，則方程的根位于[cb]內(nèi)，用c代替a。

（4）檢驗：若|b-a|<e(e為精度要求)此時計算結束x*=c，否則轉（2）。例1.3.1用對分法求方程f(x)=x3+2x-5=0在[12]內(nèi)的根，[e=10-5有根區(qū)間f=inline('x^3+2*x-5')f(1),f(2)f=inline('x^3+2*x-5')f(1),f(2)fplot(f,[12]),gridon1.00001.50001.25001.50001.25001.37501.31251.37501.31251.34381.32811.34381.32811.33591.32811.33201.32811.33011.32811.3291方程的解x=1.3286§2.4迭代法設有方程f(x)=0在[ab]上有且僅有一個根x*，可用迭代法求x*的近似值，方法如下（1）將方程f(x)=0寫成迭代形式x=(x)

（2）在[ab]上任取一個初始值x0。

（3）計算x1=(x0)

（4）若|x1x0|<e(e為精度要求)，此時計算結束x*=x1，否則令x0=x1轉（3）。例1.4.1用迭代法解方程x=10x-2，x0=1分別采用迭代格式x=10x-2和x=log(x+2)，觀察兩個計算過程的區(qū)別。e=1e-3迭代過程:1.00000.47710.39390.37910.37640.3759迭代6次x=0.3759f=inline('f=inline('log10(x+2)')x=1x=f(x)例1.4.2用迭代法求方程f(x)=x3+2x-5=0的根，x0=1[SKIPIF1<0]。迭代過程:1.00001.44221.28371.34491.32201.33061.32741.32861.3281f=inline('(5-2*x)^(1/3)')x=1x=f(x)迭代9次x=1.3281§2.5牛頓迭代法f=inline('(5-2*x)^(1/3)')x=1x=f(x)牛頓法是解方程f(x)=0的重要方法，它也是一種迭代法。設有方程f(x)=0在[ab]上有且僅有一個根x*，可用牛頓法求x*的近似值，方法如下（1）求函數(shù)f(x)的導函數(shù)f(x)，牛頓法迭代公式為x=xf(x)/f(x)

（2）在[ab]上任取一個初始值x0。

（3）計算x1=x0f(x0)/f(x0)

（4）若|x1x0|<e(e為精度要求)，此時計算結束x*=x1，否則令x0=x例1.5.1用牛頓法解方程f(x)=x3-2x2-4x-7=0在[34]內(nèi)的根[x0=4迭代過程:4.00003.67863.63293.6320迭代4次x=3.6320f=inline('x^3-2*x^2-4*x-7')fd=inline('3*x^2-4*x-4')x=4x=x-f(x)/fd(x)§2.6弦截法f=inline('x^3-2*x^2-4*x-7')fd=inline('3*x^2-4*x-4')x=4x=x-f(x)/fd(x)弦截法也是一種是解方程f(x)=0的迭代法，它的特點是不需要計算f(x)的函數(shù)f(x)，且收斂速度也相當快，是工程計算中常用的算法之一。設有方程f(x)=0在[ab]上有且僅有一個根x*，可用弦截法求x*的近似值，方法如下（1）求函數(shù)f(x)在區(qū)間[ab]的兩個端點的函數(shù)值f(x0),f(x1)，其中a=x0,b=x1（2）計算x2=x1f(x1)[x1x0]/[f(x1)f(x0)]

（3）若|x2x1|<e(e為精度要求)，此時計算結束x*=x2，否則令x0=x1x1=x2轉（§1.7用牛頓法解方程組設有非線性方程組u(x,y)=0，v(x,y)=0，在(xn,yn)按臺勞級數(shù)展開，取展開式的第1，2項得到SKIPIF1<0SKIPIF1<0其中(xn,yn)是根的第n次近似值，如果Jn0方程組的第n+1次近似值(xn+1,yn+1)可用以下公式計算SKIPIF1<0例1.7.1用牛頓法解方程組u(x,y)=x3+y34=0，v(x,y)=x4+y23=0迭代初值x0=1,y0=1.4。（u/x=3x2u/y=3y2v/x=4x3v/y=2y例1.7.2用牛頓法解方程組u(x,y)=2x3y21=0，v(x,y)=xy3y4=0迭代初值x0=1.2,y0=1.7。（u/x=6x2u/y=2x v/x=6y3v/y=2xy21）例1.7.3用牛頓法解方程組u(x,y)=xcos(y)=0，v(x,y)=ysin(x)=0迭代初值x0=0,y0=0。（u/x=1 u/y=sin(y)v/x=cos(x) v/y=1）本章小結為了比較各種迭代方法的收斂速度，我們引入收斂階的概念。設迭代過程xn+1=(xn)收斂于方程x=(x)的根x*，令en=xnx*，en稱為迭代誤差，如果存在實數(shù)P1和非零常數(shù)K，使得SKIPIF1<0，則稱該迭代過程為P階收斂的。P=1稱為線性收斂，P>1稱為超線性收斂，P=2稱為平方收斂，顯然P越大，迭代過程收斂的越快?？梢宰C明當x*是方程f(x)=0的單根時，牛頓法是平方收斂的。當x*是方程f(x)=0的重根時，牛頓法僅為線性收斂。弦截法的收斂階P=1.618。對分法的收斂速度與公比為1/2的等比級數(shù)相同。牛頓法：收斂速度最快，但要計算f(x)的導函數(shù)，計算量大，有發(fā)散問題。弦截法：收斂速度次之，不需要計算f(x)的導函數(shù)計算量比牛頓法小，有發(fā)散問題。對分法：收斂速度最慢，但簡單有效，不存在發(fā)散問題。它一定收斂到有根區(qū)間[ab]內(nèi)的某個根。第3章線性方程組的解法§3.1引言在科學實驗和工程設計中，經(jīng)常用到解線性方程組的問題。本章討論用計算機求解線性方程組的兩類主要方法：直接法和迭代法。解線性方程組的一般表達式SKIPIF1<0根據(jù)矩陣的性質可以寫成SKIPIF1<0

簡記為Ax=b其中SKIPIF1<0方程組Ax=b有唯一解的充分必要條件是|A|0。我們只討論這種情況下的解法。解線性方程組的方法可以分為兩類：一類是直接法，它只包含有限次的四則運算，在每次運算都無舍入誤差的情況下，所得到的是方程組的準確解。由于實際計算中總是有舍入誤差，所以實際得到的也是近似解。令一類是迭代法，它首先選擇一組初始值，再運用同樣的計算步驟，重復計算，得到近似解。由于這類方法中出現(xiàn)了極限過程，必須研究迭代過程的收斂性。本章主要介紹：直接法中的高斯消去法和主元高斯消去法。迭代法中的簡單迭代法和塞德爾單迭代法?！?.2高斯消去法以n=4為例說明高斯消去法的計算過程，設有線性方程組SKIPIF1<0SKIPIF1<0SKIPIF1<0SKIPIF1<0經(jīng)過3次消元步驟，得到以上形式。從最后一個方程中解出x4,依此回代得到方程組的全部解。6x1+3x2+2x3=6

例2.2.3用高斯消去法解方程組10x1+5x2+6x3=0

8x1+5x2+3x3=0方程組的增廣矩陣[A|b]6326105608530消元6.00003.00002.00006.0000002.6667-10.000001.00000.3333-8.0000方程組系數(shù)矩陣主對角線元素為零，消元過程無法進行!例2.2.4用列主元高斯消去法解例2.2.3中的方程組。方程組的增廣矩陣[A|b]6326105608530選主元1056063268530消元10.00005.00006.0000000-1.60006.000001.0000-1.80000選主元10.00005.00006.0000001.0000-1.8000000-1.60006.0000消元10.00005.00006.0000001.0000-1.8000000-1.60006.0000回代得到方程組的解5.6250-6.7500-3.7500§3.3矩陣的LU分解§3.4對稱矩陣的LDLT分解§3.5線性方程組解的可靠性§3.6簡單迭代法設有方程組Ax=b，變?yōu)榈问?，x=Mx+f，或x(k+1)=Mx(k)+f，任取初始值x(0)程迭代得到x(0)，x(1)，x(2)，，x(k)，若極限SKIPIF1<0存在，則x*就是原方程組的解。以n=4為例SKIPIF1<0x(k+1) M x(k)f寫成分量形式SKIPIF1<0定理1若SKIPIF1<0，則簡單迭代法對任意初始值x(0)和f都收斂。定理2若SKIPIF1<0，則簡單迭代法對任意初始值x(0)和f都收斂。定理3迭代公式x(k+1)=Mx(k)+f，對任意初始值x(0)和f都收斂的充分必要條件是矩陣M的各個特征值的模都小于1?！?.6雅可比迭代法與高斯-塞德爾迭代法在簡單迭代法的基礎上作改進x(k+1)=M1x(k+1)+M2x(k)+f，以n=4為例SKIPIF1<0x(k+1)M1x(k+1)M2x(k)f寫成分量形式SKIPIF1<0定理1若SKIPIF1<0，則塞德爾迭代法對任意初始值x(0)和f都收斂。定理2若SKIPIF1<0，則塞德爾迭代法對任意初始值x(0)和f都收斂。定理3迭代公式x(k+1)=M1x(k+1)+M2x(k)+f，對任意初始值x(0)和f都收斂的充分必要條件是矩陣(I-M1)-1M松弛法（SuccessiveOverRelaxationMethod）x(k+1)=x(k)+(b-Ax(k))稱為松弛因子，>1超松弛法，>1超松弛法，>1低松弛法。定理3松弛法對任意初始值x(0)和f都收斂的必要條件是0<<2。例2.6.1分別用雅可比迭代法和塞德爾迭代法解方程組SKIPIF1<0誤差e<10-3雅可比迭代法迭代公式x(k+1)=Mx(k)+f,寫成分量形式SKIPIF1<0初始值k=0(000),迭代過程x1(k) x2(k) x3(k) x1(k) x2(k) x3(k)-2.40005.00000.3000-4.00023.00311.9999-4.46124.24952.2802-4.00123.00002.0010-4.55582.74462.4671-4.00022.99922.0002-3.99132.62752.0345-3.99972.99981.9998-3.85792.98491.8865M=[0-0.4-0.2;0.250-0.5;-0.20.30]f=M=[0-0.4-0.2;0.250-0.5;-0.20.30]f=[-2.4;5;0.3]x=[0;0;0]x=M*x+f-4.03033.02372.0219-4.01382.98152.0132-3.99522.99001.9972-3.99543.00261.9960塞德爾迭代法迭代公式x(k+1)=M1x(k+1)+M2x(k)+f寫成分量形式SKIPIF1<0clearM1=[0-0.4-0.2;00-0.5;000]M2=[000;0.2500;-0.20.30]f=[-2.4;5;0.3]x=[0clearM1=[0-0.4-0.2;00-0.5;000]M2=[000;0.2500;-0.20.30]f=[-2.4;5;0.3]x=[0;0;0]B=inv((eye(3)-M1))x=B*M2*x+B*fx1(k) x2(k) x3(k)-2.40005.00000.3000-4.40004.85000.3000-4.00403.07661.8667-3.99962.98712.0238-4.00003.00211.9961-4.00002.99972.0006-4.00003.00002.0000例2.6.2分別用雅可比迭代法和塞德爾迭代法解方程組SKIPIF1<0誤差e<10-3（1）雅可比迭代法迭代公式x(k+1)=Mx(k)+fSKIPIF1<0取初始值k=0(000),迭代過程x1(k) x2(k) x3(k)1.00000-2.00005.0000-0.99600.0080-1.00805.00806.0080-1.00005.00006.0000-1.00005.00006.0000 分析，M的特征方程SKIPIF1<0（2）塞德爾迭代法迭代公式x(k+1)=M1x(k+1)+M2x(k)+fSKIPIF1<0，不收斂分析，B=(I-M1)-1M2的特征方程SKIPIF1<0例2.6.3分別用雅可比代法和塞德爾迭代法解方程組SKIPIF1<0誤差e<10-3（1）雅可比迭代法迭代公式x(k+1)=Mx(k)+fSKIPIF1<0分析，M的特征方程SKIPIF1<0，所以簡單迭代法不收斂。塞德爾迭代法迭代公式x(k+1)=M1x(k+1)+M2x(k)+fSKIPIF1<0分析，B=(I-M1)-1M2的特征方程SKIPIF1<0，收斂取初始值k=0(000),迭代過程x1(k) x2(k) x3(k)2.00001.000001.49800.2500-0.74802.24900.2495-1.43702.59380.4216-1.59392.58610.5039-1.54312.51960.5117-1.49902.49370.5027-1.49172.49450.4986-1.49682.49910.4988-1.50012.50060.4997-1.50062.50040.5001-1.5002本章小結本章討論了解線性方程組的直接解法和迭代解法。直接解法比較適用與系數(shù)矩陣稠密（既零元素較少）的中、小型線性方程組，但對系數(shù)矩陣是帶狀或近似帶狀的大型線性方程組也適用。直接解法中的列主元高斯消去法具有精度較高和省時的優(yōu)點，是計算機中常用的算法。迭代解法中主要介紹了雅可比迭代法、高斯-塞德爾迭代法和松弛法。迭代法具有計算公式簡單、程序設計容易、占用計算機內(nèi)存較少的優(yōu)點。適用于解大型稀疏矩陣（既零元素較多）線性方程組。高斯-塞德爾迭代法是在雅可比迭代法的基礎上改進得到，在很多情況下可以加快收斂速度，但它的收斂域與雅可比迭代法不同，因此不能互相取代。松弛法可以加速迭代過程的收斂速度，但要適當選擇松弛因子（0<<2）。在選擇迭代法時，要特別注意檢驗方法的收斂性問題。第4章矩陣特征值與特征向量的計算§4.1引言求矩陣的特征值和特征向量，是代數(shù)計算中的重要問題。在自然科學和工程中的許多問題，例如電磁振蕩、橋梁的振動，機械振動等都可以歸結為求矩陣的特征值和特征向量問題。矩陣A的特征值和特征向量是指，如果數(shù)和非零列向量x滿足關系式Ax=x，則數(shù)稱為A的特征值非零列向量x稱為A的與特征值對應的特征向量。計算n階矩陣A的特征值，就是求特征方程|AI|=0的根i(i=1,2,,n)。齊次線性方程組(AiI)x=0的非零解xi，是i對應的特征向量。本章討論一些在計算機上計算矩陣的特征值和特征向量的較為穩(wěn)定的數(shù)值算法?！?.2冪法和反冪法1、冪法：計算n階矩陣A的模最大的特征值（主特征值）及對應的特征向量。任取n維列向量x(0)，用迭代公式x(k+1)=Ax(k)計算得到x(0)，x(1)，x(2)，設x(0)=a1v1+a2v2++anvn，因為Avj=ivj所以x(1)=Ax(0)=a11v1+a22v2++annvnx(2)=Ax(1)=a112v1+a222v2++ann2vn一般地有x(k+1)=Ax(k)=a11kv1+a22kv2++annkvn=1k[a1v1+a2(2/1)kv2++an(n/1)kvn]當k充分大時x(k+1)a11k+1v11x(k)向量x(k+1)與x(k)向近似地只差一個倍數(shù)，這個倍數(shù)就是模最大的特征值1。1、反冪法：Ax=x，A-1Ax=A-1x，A-1x=-1x，即A的特征值的倒數(shù)-1是A的逆矩陣A-1的特征值。用冪法求A-1的模最大的特征值，它的倒數(shù)就是A的模最小的特征值?！?.3雅可比方法對于2階方陣SKIPIF1<0SKIPIF1<0令SKIPIF1<0對于n階方陣（以n=3為例）SKIPIF1<0令SKIPIF1<0作變換矩陣SKIPIF1<0則有SKIPIF1<0令SKIPIF1<0作變換矩陣SKIPIF1<0則有SKIPIF1<0令SKIPIF1<0作變換矩陣SKIPIF1<0則有SKIPIF1<0一般地說，令SKIPIF1<0，可以將A中的元素的aij和aji變?yōu)?。在實際計算中采用以下公式SKIPIF1<0例4.3.1 用雅可比求對稱矩陣SKIPIF1<0的特征值和特征向量。消去第i行第j列的元素[ij]=[12]A->1.00000.0000-0.70710.00003.0000-0.7071-0.7071-0.70712.0000消去第i行第j列的元素[ij]=[13]A->0.6340-0.32510.0000-0.32513.0000-0.62800.0000-0.62802.3660消去第i行第j列的元素[ij]=[12]A->0.59010.0000-0.08390.00003.0438-0.6223-0.0839-0.62232.3660消去第i行第j列的元素[ij]=[13]A->0.5862-0.02930.0000-0.02933.0438-0.62160.0000-0.62162.3700消去第i行第j列的元素[ij]=[23]A->0.5862-0.0252-0.0150-0.02523.41400.0000-0.01500.00001.9998消去第i行第j列的元素[ij]=[12]A->0.58590.0000-0.01500.00003.41420.0001-0.01500.00011.9998§4.4QR方法*QR方法是求一般矩陣A的全部特征值和特征向量的一種迭代方法。其基本思路是利用矩陣A的QR分解，通過迭代格式SKIPIF1<0將A化為相似的上三角矩陣（或分塊上三角矩陣），從而求出A的全部特征值和特征向量。例3.4.1 用QR方法求矩陣SKIPIF1<0的特征值和特征向量。特征向量-0.8165-0.6215-0.6760-0.4082-0.6215-0.67600.40820.4770-0.2935特征值 1.00000.69724.3028本章小結本章介紹了求矩陣的特征值和對應的特征向量的幾種方法。冪法可以求出矩陣的主特征值和對應的特征向量，優(yōu)點是算法簡單，但當|1/2|1時，收斂速度很慢。反冪法可以求出矩陣的模最小的特征值和對應的特征向量。雅可比方法是利用一系列正交相似變換（即平面旋轉變換）把實對稱矩陣A化為對角陣（近似），從而求出實對稱矩陣全部特征值。QR方法是用鏡向反射陣將矩陣A作QR分解，是一種求矩陣的全部特征值的有效方法。第5章插值與擬合§5.1引言已知表格函數(shù)y=f(x)xix0x1x2xn-1xnf(xi)y0y1y2yn-1yn構造一個公式p(x)近似地表示f(x)，解決這個問題的方法有兩類：一類是插值法，另一類是擬合法，又稱為逼近法。已知函數(shù)y=f(x)在互異點x0 ,x1,x2,,xn-1,xn上的函數(shù)值y0,y1,y2,,yn-1,yn，構造一個函數(shù)p(x)使得p(xi)=yi這樣的問題稱為插值問題。y=f(x)稱為被插值函數(shù)，[x0xn]稱為插值區(qū)間，p(x)稱為插值函數(shù)，x0 ,x1,x2,,xn-1,xn稱為插值點，在插值區(qū)間內(nèi)部用p(x)代替f(x)稱為內(nèi)插，在插值區(qū)間外部用p(x)代替f(x)稱為外推，R(x)=f(x)-p(x)稱為插值函數(shù)p(x)的誤差?！?.2插值多項式的存在和唯一性定理：給出n+1個插值點及函數(shù)值xix0x1x2xn-1xnf(xi)y0y1y2yn-1yn求一個n次多項式pn(x)=a0+a1x+a2x2++anxn(x0,y0)(x1,y1)(x2,y2)(x3,y(x0,y0)(x1,y1)(x2,y2)(x3,y3)(x4,y4)§5.3拉格朗日插值多項式1、給出2個插值點(x0,y0)，(x1,y1)可以得到一次多項式SKIPIF1<02、給出3個插值點(x0,y0)，(x1,y1)，(x2,y2)可以得到二次多項式SKIPIF1<0不難驗證p2(x)滿足插值條件p2(x0)=y0p2(x1)=y1p2(x2)=y23、給出n+1個插值點(x0,y0)，(x1,y1),,(xn,yn)可以得到一個n次多項式SKIPIF1<0其中SKIPIF1<0例5.3.1按下列表格求y(-0.5)和y(0.5)的值。x|123 y|7解：插值多項式SKIPIF1<0L2(-0.5)=0.2500L2(0.5)=4例4.3.2按下列表格求y(2.5)、y(4.5)、y(5.5)的值。x|解：插值多項式L4(x)=-0.7917x4+9.25x3-37.21x2+60.75x-32L4(2.5)=0.9180,L4(4.5)=6.1323,L4(5.5)=-8.9637§5.4均差插值公式已知函數(shù)f(x)在互異點x0,x1,,xn上的值為f(x0),f(x1),,f(xn)稱SKIPIF1<0為函數(shù)f(x)在點xi,xj處的一階均差。稱SKIPIF1<0為函數(shù)f(x)在點xi,xj,xk處的二階均差。一般地稱SKIPIF1<0為函數(shù)f(x)在點x0,x1,,xn上的n階均差。牛頓插值公式Nn(x)=f(x0)+(x-x0)f(x0,x1) +(x-x0)(x-x1)f(x0,x1,x2)+ +(x-x0)(x-x1)(x-xn-1)f(x0,x1,,xn)牛頓插值公式具有遞推關系Nk+1(x)=Nk(x)+(x-x0)(x-x1)(x-xk)f(x0,x1,,xk+1)新增加一個節(jié)點，只需要增加計算一項(x-x0)(x-x1)(x-xk)f(x0,x1,,xk+1)§5.5差分等距結點插值公式1、差分已知函數(shù)f(x)在等距節(jié)點x0,x1,,xn上的值xx0x+hx+2hx+nhf(x)y0y1y2yn稱△yk=yk+1yk為函數(shù)f(x)在點xk處的一階差分。稱△2yk=△yk+1△yk為函數(shù)f(x)在點xk處的二階差分。一般地稱△myk=△m-1yk+1△m-1yk為函數(shù)f(x)在點xk處的m階差分。2、等距結點插值公式牛頓向前插值公式SKIPIF1<0牛頓向后插值公式SKIPIF1<0§5.6愛爾米特插值公式定理：給出n+1個插值點上的函數(shù)值和導數(shù)值xix0x1x2xn-1xnf(xi)y0y1y2yn-1ynf(xi)y0y1y2yn-1yn求一個2n+1次多項式H(x)滿足Hn(xi)=yi，Hn(xi)=yi(i=0,1,2,,n)。SKIPIF1<0其中SKIPIF1<0SKIPIF1<0§5.7分段低次插值§5.8三次樣條函數(shù)在xoy平面上給定n+1個點(x0,y0),(x1,y1),,(xn,yn)，構造一個函數(shù)S(x)滿足以下條件（1）S(xi)=yi(i=0,1,2,,n)

（2）在區(qū)間(x0,xn)內(nèi)S(x)具有連續(xù)的二階導數(shù)（3）在每個子區(qū)間[xi1,xi]上S(x)（表達式是Si(x)）是一個三次多項式。滿足以上條件S(x)稱為三次樣條插值多項式。三次樣條插值多項式的推導設在子區(qū)間[xi1,xi]上S(x)=Si(x)(i=1,2,,n)由條件（1）得Si(xi-1)=yi1，Si(xi)=yi設S(x)在節(jié)點xi1處的二階導數(shù)為Mi1，在節(jié)點xi處的二階導數(shù)為Mi，即Si(xi-1)=Mi1，Si(xi)=Mi，顯然Si(x)是x的線性函數(shù)，根據(jù)拉格朗日插值公式有SKIPIF1<0，記xi-xi1=hi有SKIPIF1<0將上式積分兩次得到SKIPIF1<0利用Si(xi-1)=yi1，Si(xi)=yi定出積分常數(shù)C1和C2SKIPIF1<0解此方程組得到SKIPIF1<0代入上式整理后得到SKIPIF1<0SKIPIF1<0SKIPIF1<0類似地有SKIPIF1<0SKIPIF1<0因為Si+1(xi)=Si(xi)所以有SKIPIF1<0整理后得到關于位知數(shù)M0,M1,,Mn的線性方程組aiMi-1+2Mi+biMi+1=di(i=1,2,其中SKIPIF1<0邊界條件：n-1個方程組，n+1個位知數(shù)，所有需要補充兩個條件，常見的是以下兩種（1）給定端點的二階導數(shù)M0=a，Mn=b，特別地，當a=b=0時稱為自然樣條。（2）給定端點的一階導數(shù)S(x0)=a，S(xn)=b，這時有SKIPIF1<0例5.7.1給定插值條件，和兩種邊界條件(1)m0=1,m3=0(2)M0=1,M3=0

x|0123

y|0000

m0=1,m3=0s1(x)=0.73333x3-1.7333x2+x0<x<1s2(x)=-0.2x3+1.0667x2-1.8x+0.933331<x<2s3(x)=0.066667x3-0.53333x(2)M0=1,M3=0s1(x)=-0.21111x3+0.5x2-0.28889x0<x<1s2(x)=0.055556x3-0.3x2+0.51111x-0.26667§5.9曲線擬合的最小二乘法給出表格函數(shù)xix0x1x2xn-1xnf(xi)y0y1y2yn-1yn求一個m(m<n)次多項式為pm(x)=a0+a1x+a2x2++amxm逼近這組數(shù)據(jù)。pm(x)的系數(shù)的確定：SKIPIF1<0即SKIPIF1<0(i=0,1,2,,n)SKIPIF1<0由微分學知，使(a0,a1,,am)達到極小值的a0,a1,,am滿足必要條件SKIPIF1<0(K=0,1,2,,m)寫成分量形式SKIPIF1<0正規(guī)方程組解此方程組得到a0,a1,,am即得到所要的多項式。例5.8.1有數(shù)據(jù)表如下，分別用二次和三次多項式逼近這組數(shù)據(jù)。x|-3-2-10123 y|p1(x)=0.1786x+0.5714p2(x)=0.17857x2+0.17857x-0.14286p3(x)=3.2895*10-17x3+0.17857x2+0.17857x-0.14286一次多項式逼近誤差平方和2.8214，二次多項式逼近誤差平方和0.1429，三次多項式逼近誤差平方和0.1429。本章小結本章介紹了兩種構造函數(shù)f(x)的逼近函數(shù)的方法—插值法和曲線擬合。關于插值法，討論的是多項式插值，它要求所構造的多項式函數(shù)嚴格地通過給定的所有數(shù)據(jù)點。由Lagrange插值基函數(shù)的討論，導出了Lagrange插值公式及其余項公式。作為對Lagrange插值的改進，建立了具有遞推性的牛頓插值公式。Hermite插值是一種在插值節(jié)點上插值函數(shù)與被插值函數(shù)不僅有相同的函數(shù)值，而且還有相同的一階導數(shù)值的多項式插值。由于高次插值會產(chǎn)生龍格現(xiàn)象，因此討論了分段插值法，重點介紹了三次樣條插值公式。關于曲線擬合，討論的是曲線擬合的最小二乘法，它不要求所構造的逼近函數(shù)嚴格地通過給定的所有數(shù)據(jù)點，只是在多項式中，以使得殘差的平方和最小為標準，選擇多項式，以作為被逼近函數(shù)的近似替代。本章最后介紹了數(shù)值微分，其中5點公式是常用的。第6章數(shù)值積分和數(shù)值微分§6.1引言計算定積分的牛頓-萊布尼茲公式SKIPIF1<0，其中F(x)是函數(shù)f(x)的原函數(shù)。在實際應用中（1）常遇到某些函數(shù)f(x)的原函數(shù)不能用初等函數(shù)表示，例如sin(x2)，cos(x2),sin(x)/x，1/log(x)等。（2）有些函數(shù)f(x)是用表格形式表示，無法得到它們的原函數(shù)。（3）有些函數(shù)f(x)的原函數(shù)十分復雜，不利于工程上的使用。因此，要研究計算定積分的近似方法：數(shù)值積分。§6.2牛頓一科特斯型積分公式由上一章知，任意函數(shù)f(x)可以用一個拉格朗日插值多項式n(x)近似表示，因此f(x)的定積分也可以用n(x)的定積分近似表示SKIPIF1<0以此為基礎得到的數(shù)值積分公式稱為牛頓一科特斯型積分公式。SKIPIF1<0其中SKIPIF1<0取a=x0<x1<<xn=b為一組等距節(jié)點，令x=a+bt，h=(b-a)/n得到SKIPIF1<0記SKIPIF1<0，于是SKIPIF1<0所以得SKIPIF1<0對不同的n系數(shù)如下n牛頓一科特斯型積分公式系數(shù)余項（誤差）11/2，1/2 (梯形公式)(1/12)h3f(2)()a<21/6，4/6，1/6 （拋物線公式或辛卜生公式）(1/90)h5f(4)(31/8，3/8，3/8，1/8(3/80)h5f(4)(47/90，32/90，12/90，32/90，7/90 （柯特斯公式）(8/945)h7f(6)(519/288，75/288，50/288，50/288，75/288，19/288(275/12096)h7f(6)(641/840，216/840，27/840，272/840，27/840，216/840，41/840(9/1400)h3f(2)(§6.3復合求積公式1、復合梯形公式取a=x0<x1<<xn=b為一組等距節(jié)點將積分區(qū)間[ab]分為n個子區(qū)間[xkxk-1]xk–xk-1=(b-a)/n=h，在每個子區(qū)間[xkxk-1]上應用梯形公式得：SKIPIF1<0于是得到復合梯形公式SKIPIF1<02、復合辛卜生公式在積分區(qū)間[ab]取點a=x0<x1<<x2n-1<x2n=b將[ab]分為2n個子區(qū)間，令x2k-2x2k=(b-a)/n=2h，在每個子區(qū)間[x2k-2x2k]上應用辛卜生公式得：SKIPIF1<0（k=1,2,,n）于是得到復合辛卜生公式SKIPIF1<03、復合柯特斯公式在積分區(qū)間[ab]取點a=x0<x1<<x4n-1<x4n=b將[ab]分為4n個子區(qū)間，令x4k-4x4k=(b-a)/n=4h，在每個子區(qū)間[x4k-4x4k]上應用柯特斯公式得：SKIPIF1<0（k=1,2,,n）得到復合柯特斯公式SKIPIF1<0（k=1,2,,n）4、步長h的自動選擇復合梯形公式|T2nTn|<3e（e表示允許誤差）其中Tn和T2n分別表示取n和2n時用復合梯形公式計算得到的積分近似值。（2）復合辛卜生公式|S2nSn|<15e（e表示允許誤差）其中Sn和S2n分別表示取n和2n時用復合辛卜生公式計算得到的積分近似值。（3）復合柯特斯公式|C2nCn|<63e（e表示允許誤差）其中Cn和C2n分別表示取n和2n時用復合柯特斯公式計算得到的積分近似值?！?.4龍貝格求積公式梯形公式與辛卜生公式之間的關系SKIPIF1<02、辛卜生公式與柯特斯公式之間的關系SKIPIF1<03、龍貝格積分公式SKIPIF1<0§6.5高斯求積公式一個求積公式，若對于任何次數(shù)不超過m的多項式都準確成立，則稱這個求積公式的代數(shù)精確度為m。定義：使插值求積公式SKIPIF1<0的代數(shù)精確度為2n-1的節(jié)點x1,x2,,xn稱為高斯點，對應的插值求積公式稱為高斯求積公式。定理1：若x1,x2,,xn是高斯點，則SKIPIF1<0定理2：高斯求積公式的系數(shù)恒為正，且有SKIPIF1<0n節(jié)點xk(n)系數(shù)Ak(n)余項（誤差）積分區(qū)間[-11]102f(2)()/31<<120.5773503+0.577350311f(4)()/13530.5773503

0+0.57735035/98/9

5/9f(6)()/1575040.8611363

0.3399810

+0.3399810+0.86113630.3478548

0.6521452

0.6521452

0.3478548f(8)()/347287550.90617990.5384693

0

+0.5384693+0.90617990.2369269

0.4786287

0.5688889

0.4786287

0.2369269f(10)()/1237732650§6.6二重積分的數(shù)值積分法§6.7數(shù)值微分給出表格函數(shù)如下表所示，求f(x)在節(jié)點f(xi)處的導數(shù)的近似值。xix0x1x2xn-1xnf(xi)y0y1y2yn-1yn方法：用插值多項式的導數(shù)近似f(x)的導數(shù)。三點公式：SKIPIF1<0SKIPIF1<0三個相鄰節(jié)點的選法，一般是在所考察的節(jié)點兩側各選取一個節(jié)點，如果一側的無節(jié)點，則用另一側的節(jié)點補足。一階導數(shù)的