應(yīng)用數(shù)值分析全書(shū)課件整本書(shū)電子教案

應(yīng)用數(shù)值分析

Applied

NumericalAnalysis

提問(wèn)：數(shù)值分析是做什么用的？數(shù)學(xué)建模

構(gòu)造算法程序設(shè)計(jì)上機(jī)計(jì)算求出結(jié)果實(shí)際問(wèn)題近似解

數(shù)值分析

計(jì)算機(jī)輸入復(fù)雜問(wèn)題或運(yùn)算第一章科學(xué)計(jì)算簡(jiǎn)介T(mén)herearethreegreatbranchesofscience:theory,experimentandcomputation.Thefundamentallawofcomputerscience:Asmachinesbecomemorepowerful,theefficiencyofalgorithmsgrowsmoreimportant,notless.—L.N.Trefethen一、研究對(duì)象數(shù)值分析（NumericalAnalysis），也稱數(shù)值方法、計(jì)算方法或計(jì)算機(jī)數(shù)學(xué)，是計(jì)算數(shù)學(xué)的一個(gè)主要部分，計(jì)算數(shù)學(xué)是數(shù)學(xué)科學(xué)的一個(gè)分支，它研究用計(jì)算機(jī)求解各種數(shù)學(xué)問(wèn)題的數(shù)值計(jì)算方法及其理論與軟件實(shí)現(xiàn)，是用公式表示數(shù)學(xué)問(wèn)題以便可以利用算術(shù)和邏輯運(yùn)算解決這些問(wèn)題的技術(shù)。二、學(xué)科特點(diǎn)

算法能在計(jì)算機(jī)上實(shí)現(xiàn)，并有好的計(jì)算復(fù)雜性；

面向計(jì)算機(jī)，提供切實(shí)可行的有效算法；

有可靠理論，對(duì)算法進(jìn)行誤差分析，并能達(dá)到精度要求；

通過(guò)數(shù)值實(shí)驗(yàn)

證明算法行之有效；§1數(shù)值分析簡(jiǎn)介三、學(xué)習(xí)理由1數(shù)值方法能夠極大地覆蓋所能解決的問(wèn)題類型；2學(xué)習(xí)數(shù)值分析可以讓用戶更加智慧地使用“封裝過(guò)的”軟件；3很多問(wèn)題不能直接用封裝的程序解決，如果熟悉數(shù)值方法并擅長(zhǎng)計(jì)算機(jī)編程的話，就可以自己設(shè)計(jì)程序解決問(wèn)題；4數(shù)值分析是學(xué)習(xí)使用計(jì)算機(jī)的有效載體，對(duì)于展示計(jì)算機(jī)的強(qiáng)大和不足是非常理想的；5數(shù)值分析提供了一個(gè)增強(qiáng)對(duì)數(shù)學(xué)理解的平臺(tái).§2誤差一.來(lái)源與分類

從實(shí)際問(wèn)題中抽象出數(shù)學(xué)模型——模型誤差

通過(guò)測(cè)量得到模型中參數(shù)的值——觀測(cè)誤差

求(數(shù)學(xué)表達(dá)的)近似解——方法誤差(截?cái)嗾`差)

模型的準(zhǔn)確解與用數(shù)值方法求得的準(zhǔn)確解之差稱為“截?cái)嗾`差”。

機(jī)器字長(zhǎng)有限——舍入誤差簡(jiǎn)化…實(shí)際算法:有限、四則運(yùn)算化…（理論計(jì)算誤差）大家一起猜？11/e解：將作Taylor展開(kāi)后再積分S4R4取則稱為截?cái)嗾`差|

舍入誤差

|=0.747……由截去部分引起由留下部分引起二、誤差的定義

絕對(duì)誤差其中x為精確值，x*為x的近似值。，例如：上常記為，稱為絕對(duì)誤差限，一般地，的上限記為

由于通常準(zhǔn)確值x是不知道的，所以誤差e*

的準(zhǔn)確值也不可能求出，但根據(jù)具體情況，可事先估計(jì)出誤差的范圍——誤差絕對(duì)值不能超過(guò)某個(gè)正數(shù)，我們把叫做誤差絕對(duì)值的“上界”，或稱“誤差限”?！堋堋芄こ套ⅲ篹*理論上講是唯一確定的，可能取正，也可能取負(fù)。e*>0時(shí)，x*稱為強(qiáng)近似值，e*<0時(shí)，x*稱為弱近似值e*>0不唯一，當(dāng)然e*越小越具有參考價(jià)值。x的相對(duì)誤差限常定義為注：從的定義可見(jiàn)，實(shí)際上被偷換成了，而后才考察其上限。那么這樣的偷換是否合法？嚴(yán)格的說(shuō)法是，與是否反映了同一數(shù)量級(jí)的誤差？關(guān)于此問(wèn)題的詳細(xì)討論可見(jiàn)教材p5。實(shí)際計(jì)算中，相對(duì)誤差通常取為：相對(duì)誤差三、有效數(shù)字

若近似值x*的誤差限是某一位的半個(gè)單位,該位到x*

的第一位非零數(shù)字共有n位,就說(shuō)x*有n位有效數(shù)字.例:問(wèn)：有幾位有效數(shù)字？請(qǐng)證明你的結(jié)論。43注：0.2300有4位有效數(shù)字，而0.0023只有2位有效數(shù)字。12300如果寫(xiě)成0.123105，則表示只有3位有效數(shù)字。

數(shù)字末尾的0不可隨意省去！用科學(xué)計(jì)數(shù)法，記（其中）。若（即的截取按四舍五入規(guī)則），則有n位有效數(shù)字，精確到。注：關(guān)于有效數(shù)字有以下幾點(diǎn)說(shuō)明：1、用四舍五入法取準(zhǔn)確值的前n位作為近似值，則x*必有n位有效數(shù)字；2、有效數(shù)字位數(shù)相同的兩個(gè)近似數(shù)，絕對(duì)誤差限不一定相同；3、將任何數(shù)乘以10m(m為整數(shù))，等于移動(dòng)該數(shù)的小數(shù)點(diǎn)，并不影響它的有效數(shù)字的位數(shù)；4、準(zhǔn)確值被認(rèn)為具有無(wú)窮位有效數(shù)字.有效數(shù)字與相對(duì)誤差的關(guān)系

有效數(shù)字

相對(duì)誤差限已知x*有n位有效數(shù)字，則其相對(duì)誤差限為

相對(duì)誤差限

有效數(shù)字已知x*的相對(duì)誤差限可寫(xiě)為則可見(jiàn)x*至少有n位有效數(shù)字。例：為使的相對(duì)誤差小于0.001%,至少應(yīng)取幾位有效數(shù)字？解：假設(shè)

*取到n

位有效數(shù)字，則其相對(duì)誤差上限為要保證其相對(duì)誤差小于0.001%，只要保證其上限滿足已知a1=3，則從以上不等式可解得n>6log6，即n6，應(yīng)取

*=3.14159?！?

誤差的傳播一、誤差估計(jì)特別地，由上式可得和、差、積、商之誤差及相對(duì)誤差公式注：函數(shù)值的絕對(duì)誤差等于函數(shù)的全微分，自變量的微分即為自變量的誤差；函數(shù)值的相對(duì)誤差等于函數(shù)的對(duì)數(shù)的全微分。例.)871.030.1(~005.00022.00005.030.1871.0sin005.030.1871.0cos)~(sincos49543.030.1871.0cos)871.030.1(~

22能有二位有效數(shù)字，所以而，由于，解：fuuxyyfxyxffu=<?′+′?-=??-=???==e二、病態(tài)問(wèn)題與條件數(shù)三、算法的數(shù)值穩(wěn)定性(NumericalStability)例：蝴蝶效應(yīng)

——青島的一只蝴蝶翅膀一拍，風(fēng)和日麗的紐約就刮起臺(tái)風(fēng)來(lái)了？！QFNY以上是一個(gè)病態(tài)問(wèn)題關(guān)于本身是病態(tài)的問(wèn)題，我們還是留給數(shù)學(xué)家去頭痛吧！例：計(jì)算

公式一:注意此公式精確成立記為則初始誤差????!!!發(fā)生了什麼?!考察第n步的誤差我們有責(zé)任改變。造成這種情況的是不穩(wěn)定的算法迅速積累,誤差呈遞增走勢(shì).可見(jiàn)初始的小擾動(dòng)

公式二:注意此公式與公式一在理論上等價(jià)。方法：先估計(jì)一個(gè)IN

,再反推要求的In(n<<N)?？扇∪?/p>

我們很幸運(yùn)！考察反推一步的誤差：以此類推，對(duì)n<N

有：誤差逐步遞減,這樣的算法稱為穩(wěn)定的算法。

在我們今后的討論中，誤差將不可回避，算法的穩(wěn)定性會(huì)是一個(gè)非常重要的話題?！?數(shù)值誤差控制1.避免相近二數(shù)相減例：a1=0.12345，a2=0.12346，各有5位有效數(shù)字。而a2

a1=0.00001，只剩下1位有效數(shù)字。

幾種經(jīng)驗(yàn)性避免方法：當(dāng)|x|<<1時(shí)：2.避免小分母:分母小會(huì)造成舍入誤差增大3.避免大數(shù)吃小數(shù)例：用單精度計(jì)算的根。精確解為

算法1：利用求根公式在計(jì)算機(jī)內(nèi)，109存為0.11010，1存為0.1101。做加法時(shí)，兩加數(shù)的指數(shù)先向大指數(shù)對(duì)齊，再將浮點(diǎn)部分相加。即1的指數(shù)部分須變?yōu)?010，則：1=0.00000000011010，取單精度時(shí)就成為：109+1=0.100000001010+0.000000001010=0.100000001010大數(shù)吃小數(shù)

x3.81574

y0.0001==38157.4

x3.81574

y+

y0.0001+0.00001==34688.5算法2：先解出再利用注：求和時(shí)從小到大相加，可使和的誤差減小。例：按從小到大、以及從大到小的順序分別計(jì)算1+2+3+…+40+1094.先化簡(jiǎn)再計(jì)算，減少步驟，避免誤差積累。再如秦九韶算法補(bǔ)充材料

20世紀(jì)十大算法在世紀(jì)之交，經(jīng)過(guò)科學(xué)家的評(píng)選和投票，20世紀(jì)的十大算法得到了國(guó)際學(xué)術(shù)界的公認(rèn)?，F(xiàn)在按照時(shí)間順序列于下。本課程將討論其中一部分。Monte-Carlo方法（1946）；

(2)線性規(guī)劃的單純形算法（1947）；

線性代數(shù)方程組的krylov子空間迭代方法（1950）；

(4)矩陣計(jì)算的分解方法（1951）；(5)Fortran計(jì)算機(jī)語(yǔ)言編譯器（1957）；(6）計(jì)算矩陣特征值問(wèn)題的QR方法（1961）；(7)快速排序算法（1962）；(8)快速Fourier變換（1965）；(9)整數(shù)關(guān)系算法（1977）；

(10)快速多極算法（1987）第二章插值法插值法是數(shù)值分析中很古老的分支，有著悠久的歷史。等距節(jié)點(diǎn)內(nèi)插公式是由我國(guó)隋朝數(shù)學(xué)家劉焯（544-610年）首先提出的，不等距節(jié)點(diǎn)內(nèi)插公式是由唐朝數(shù)學(xué)家張遂（683-727年）提出的，比西歐學(xué)者的相應(yīng)結(jié)果早一千多年（2.1）

設(shè)函數(shù)在區(qū)間上有定義，且已知在相異點(diǎn)上的值，若存在一簡(jiǎn)單函數(shù)，使成立，就稱為的插值函數(shù)，點(diǎn)稱為插值節(jié)點(diǎn)，包含節(jié)點(diǎn)的區(qū)間稱為插值區(qū)間，求插值函數(shù)的方法稱為插值法.

若是次數(shù)不超過(guò)的代數(shù)多項(xiàng)式，其中為實(shí)數(shù)，就稱為插值多項(xiàng)式，相應(yīng)的插值法稱為多項(xiàng)式插值.本章只討論多項(xiàng)式插值與分段插值.

若為分段的多項(xiàng)式，就稱為分段插值.

若為三角多項(xiàng)式，就稱為三角插值.即一、待定系數(shù)法§1代數(shù)多項(xiàng)式插值上的函數(shù)值,求次數(shù)不超過(guò)的多項(xiàng)式，使（2.3）

設(shè)在區(qū)間上給定個(gè)點(diǎn)代數(shù)多項(xiàng)式插值問(wèn)題的具體提法就是:唯一性說(shuō)明：不論用何種方法來(lái)構(gòu)造，也不論用何種形式來(lái)表示插值多項(xiàng)式,只要滿足插值條件(2.1)其結(jié)果都是相互恒等的。

二、Lagrange插值多項(xiàng)式（1）線性插值

線性插值是代數(shù)插值的最簡(jiǎn)單形式。假設(shè)給定了函數(shù)f(x)在兩個(gè)互異的點(diǎn)的值，，，,

現(xiàn)要求用線性函數(shù)近似地代替。選擇參數(shù)a和b，使。稱這樣的線性函數(shù)

為

的線性插值函數(shù)。線性插值的幾何意義:用通過(guò)點(diǎn)和的直線近似地代替曲線

由解析幾何知道,這條直線用點(diǎn)斜式表示為（2）拋物插值拋物插值又稱二次插值，它也是常用的代數(shù)插值之一。設(shè)已知在三個(gè)互異點(diǎn)

的函數(shù)值，要構(gòu)造次數(shù)不超過(guò)二次的多項(xiàng)式使?jié)M足二次插值條件。幾何意義是用經(jīng)過(guò)3個(gè)點(diǎn)的拋物線

近似代替曲線。該三元一次方程組的系數(shù)矩陣

的參數(shù)直接由插值條件決定，即滿足下面的代數(shù)方程組：的行列式是范德蒙行列式，當(dāng)時(shí)，方程組的解唯一。例2.2已知

的函數(shù)表

1

3

1

2求線性插值多項(xiàng)式,并計(jì)算

的值解:由線性插值多項(xiàng)式公式得例2.3求過(guò)點(diǎn)(0,1)、(1,2)、(2,3)的三點(diǎn)插值多項(xiàng)式解:由Lagrange插值公式（給定的三個(gè)點(diǎn)在一條直線上）例2.4已知

的觀測(cè)數(shù)據(jù)012419233構(gòu)造Lagrange插值多項(xiàng)式.解

四個(gè)點(diǎn)可構(gòu)造三次Lagrange插值多項(xiàng)式:基函數(shù)為L(zhǎng)agrange插值多項(xiàng)式為為便于上機(jī)計(jì)算,常將拉格朗日插值多項(xiàng)式(5.8)改寫(xiě)成例2.5已知用線性插值估計(jì)在

時(shí)的截?cái)嗾`差.解:由插值余項(xiàng)公式知

因?yàn)槎ewton插值多項(xiàng)式所以f[x1,x2]-f[x0,x1]x2–x0

首先根據(jù)給定函數(shù)表造出均差表.2.6給出的函數(shù)表（見(jiàn)表2-2），求4次牛頓插值多項(xiàng)式，并由此計(jì)算的近似值.例

從均差表看到4階均差近似常數(shù)，5階均差近似為0.

故取4次插值多項(xiàng)式做近似即可.于是

按牛頓插值公式，將數(shù)據(jù)代入截?cái)嗾`差這說(shuō)明截?cái)嗾`差很小，可忽略不計(jì).xif[xi]f[xi,xi+1]f[xi,xi+1,xi+2]114293例2.7已知

的平方根值，求解：三、Matlab函數(shù)§3分段低次插值一.龍格現(xiàn)象及高次插值的病態(tài)性質(zhì)

對(duì)于函數(shù),在區(qū)間上取節(jié)點(diǎn),所作Lagrange插值多項(xiàng)式為,當(dāng)時(shí),內(nèi)收斂于在這區(qū)間之外發(fā)散，這一現(xiàn)象稱為Runge現(xiàn)象。

二.分段線性插值直觀上容易想象,如果不用多項(xiàng)式曲線，而是將曲線的兩個(gè)相鄰的點(diǎn)用線段連接，這樣得到的折線必定能較好地近似曲線。而且只要連續(xù)，節(jié)點(diǎn)越密，近似程度越好。由此得到啟發(fā)，為提高精度，在加密節(jié)點(diǎn)時(shí)，可以把節(jié)點(diǎn)間分成若干段，分段用低次多項(xiàng)式近似函數(shù)，這就是分段插值的思想。用折線近似曲線，相當(dāng)于分段用線性插值，稱為分段線性插值。設(shè)已知函數(shù)在上的

個(gè)節(jié)點(diǎn)

上的函數(shù)值,作一個(gè)插值函數(shù),s.t.,(1);(2)在每個(gè)小區(qū)間上，是線性函數(shù)，則稱函數(shù)為上關(guān)于數(shù)據(jù)的分段線性插值函數(shù)。

由Lagrange線性插值公式容易寫(xiě)出的分段表達(dá)式為了建立的統(tǒng)一表達(dá)式，我們需要構(gòu)造一組基函數(shù)：且在每個(gè)小區(qū)間上是線性函數(shù)。在幾何上就是用折線替代曲線,如右圖所示若用插值基函數(shù)表示,則在

a,b

上

其中定理2.4

如果

在上二階連續(xù)可微，則分段線性插值函數(shù)

的余項(xiàng)有以下估計(jì)其中

。說(shuō)明：當(dāng)節(jié)點(diǎn)加密時(shí)，分段線性插值的誤差變小，收斂性有保證。另一方面，在分段線性插值中，每個(gè)小區(qū)間上的插值函數(shù)只依賴于本段的節(jié)點(diǎn)值，因而每個(gè)節(jié)點(diǎn)只影響到節(jié)點(diǎn)鄰近的一、二個(gè)區(qū)間，計(jì)算過(guò)程中數(shù)據(jù)誤差基本上不擴(kuò)大，從而保證了節(jié)點(diǎn)數(shù)增加時(shí)插值過(guò)程的穩(wěn)定性。但分段線性插值函數(shù)僅在區(qū)間

上連續(xù)，一般地，在節(jié)點(diǎn)處插值函數(shù)不可微，這就不能滿足有些工程技術(shù)問(wèn)題的光滑要求。例2.8已知

在四個(gè)節(jié)點(diǎn)上的函數(shù)值如下表所示304560901求

在區(qū)間上的分段連續(xù)線性插值函數(shù)

解將插值區(qū)間

分成連續(xù)的三個(gè)小區(qū)間

則

在區(qū)間

上的線性插值為

在區(qū)間

45,60

上的線性插值為

在區(qū)間

60,90

上的線性插值為將各小區(qū)間的線性插值函數(shù)連接在一起，得§4三次樣條插值

我們知道,給定n+1個(gè)節(jié)點(diǎn)上的函數(shù)值可以作n次插值多項(xiàng)式,但當(dāng)n較大時(shí),高次插值不僅計(jì)算復(fù)雜,而且可能出現(xiàn)Runge現(xiàn)象,采用分段插值雖然計(jì)算簡(jiǎn)單、也有一致收斂性,但不能保證整條曲線在連接點(diǎn)處的光滑性,如分段線性插值,其圖形是鋸齒形的折線,雖然連續(xù),但處處都是“尖點(diǎn)”,因而一階導(dǎo)數(shù)都不存在,這在實(shí)用上,往往不能滿足某些工程技術(shù)的高精度要求。如在船體、飛機(jī)等外形曲線的設(shè)計(jì)中,不僅要求曲線連續(xù),而且要有二階光滑度,即有連續(xù)的二階導(dǎo)數(shù)。這就要求分段插值函數(shù)在整個(gè)區(qū)間上具有連續(xù)的二階導(dǎo)數(shù)。因此有必要尋求一種新的插值方法,這就是樣條函數(shù)插值法

一、三次樣條函數(shù)定義2.2設(shè)函數(shù)定義在區(qū)間

a,b

上，給定n+1個(gè)節(jié)點(diǎn)和一組與之對(duì)應(yīng)的函數(shù)值，若函數(shù)滿足:（1）在每個(gè)節(jié)點(diǎn)上滿足

（2）在

a,b

上有連續(xù)的二階導(dǎo)數(shù)（3）在每個(gè)小區(qū)間

xi,xi+1

(i=0,1,…,n-1)

上是一個(gè)三次多項(xiàng)式。則稱為三次樣條插值函數(shù)。在上確定4個(gè)待定系數(shù)，共確定4n個(gè)參數(shù)

求出二、三次樣條插值函數(shù)的求法

設(shè)

在節(jié)點(diǎn)xi處的二階導(dǎo)數(shù)為

連續(xù)兩次積分得由上討論可知,只要確定這n+1個(gè)值,就可定出三樣條插值函數(shù)S(x)。為了求出,利用一階導(dǎo)數(shù)在子區(qū)間連接點(diǎn)上連續(xù)的條件對(duì)上式求導(dǎo)一次,得在區(qū)間

xi-1,xi

上的表達(dá)式為（2.32）

也就是在右端點(diǎn)xi上有在左端點(diǎn)xi-1上有將上式中的i-1改為i,即得在子區(qū)間

xi,xi+1

上的表達(dá)式,并由此得利用在內(nèi)接點(diǎn)的連續(xù)性,即就可得到關(guān)于參數(shù)的一個(gè)方程上式兩邊同乘以,即得方程

若記

簡(jiǎn)寫(xiě)即

這是一個(gè)含有n+1個(gè)未知數(shù)、n-1個(gè)方程的線性方程組.要完全確定的值還需要補(bǔ)充兩個(gè)條件,這兩個(gè)條件通常根據(jù)實(shí)際問(wèn)題的需要，根據(jù)插值區(qū)間

a,b

的兩個(gè)端點(diǎn)處的邊界條件來(lái)補(bǔ)充。第一種邊界條件：即已知插值區(qū)間兩端的一階導(dǎo)數(shù)值：則可得到包含Mi的兩個(gè)線性方程,由(2.33)知,S(x)在子區(qū)間

上的導(dǎo)數(shù)為由條件得即

(2.37)同理,由條件得

邊界條件的種類很多，常見(jiàn)的有以下3種：(2.38)

將式（2.36）和式（2.37）以及式（2.38）合在一起即得確定的線性方程組(2.39)其中第二種邊界條件:即已知插值區(qū)間兩端的二階導(dǎo)數(shù)值:,由于在區(qū)間端點(diǎn)處二階導(dǎo)數(shù)

，所以方程（2.36）中實(shí)際上只包含有n-1個(gè)未知數(shù)，從而得方程組(2.40)

第三種邊界條件:由與，可得

和

(2.41)(2.42)(2.43)其中將式(5.36),(5.41),(5.42)合在一起，即得關(guān)于的線性方程組。(2.44)

利用線性代數(shù)知識(shí),可以證明方程組（2.39）,（2.40）和（2.44）的系數(shù)矩陣都是非奇異的，因此有惟一解。例2.9已知的函數(shù)值如下：x1245f(x)1342在區(qū)間

1,5

上求三次樣條插值函數(shù)S(x),使它滿足邊界條件解:這是在第二種邊界條件下的插值問(wèn)題，故確定的方程組形如前面所示，由已知邊界條件,有則得求解的方程組為根據(jù)給定數(shù)據(jù)和邊界條件算出與

則得方程組解得又

即得S(x)在各子區(qū)間上的表達(dá)式,由式（2.32）知,S(x)在上的表達(dá)式為代入式(2.32)將代入上式化簡(jiǎn)后得

同理S(x)在上的表達(dá)式為

S(x)在上的表達(dá)式為故所求的三次樣條插值函數(shù)S(x)在區(qū)間上的表達(dá)式為三、誤差界與收斂性

用三次樣條繪制的曲線不僅有很好的光滑度，而且當(dāng)節(jié)點(diǎn)逐漸加密時(shí)，其函數(shù)值在整體上能很好地逼近被插函數(shù)，相應(yīng)的導(dǎo)數(shù)值也收斂于被插函數(shù)的導(dǎo)數(shù)，不會(huì)發(fā)生龍格現(xiàn)象。因此三次樣條在計(jì)算機(jī)輔助設(shè)計(jì)中有廣泛的應(yīng)用。本章小結(jié)

本章介紹的插值法是實(shí)用性很強(qiáng)的方法。它們解決的實(shí)際問(wèn)題雖然各式各樣，但抽象為數(shù)學(xué)問(wèn)題卻有它的共性，即利用已知的數(shù)據(jù)去尋求某個(gè)較為簡(jiǎn)單的函數(shù)P(x)來(lái)逼近f(x)。插值法給出了尋求這種近似函數(shù)的原則，以及構(gòu)造近似函數(shù)的幾種具體方法。插值法要求近似函數(shù)在已知的數(shù)據(jù)點(diǎn)必須與f(x)完全一致。

插值法中的拉格朗日插值多項(xiàng)式是研究數(shù)值微積分與微分方程數(shù)值解的重要工具。牛頓插值多項(xiàng)式是拉格朗日插值多項(xiàng)式的變形，具有承襲性，比拉格朗日插值多項(xiàng)式節(jié)省計(jì)算量。分段低次多項(xiàng)式插值由于具有良好的穩(wěn)定性與收斂性，且算法簡(jiǎn)單，便于應(yīng)用。特別是應(yīng)用廣泛的三次樣條插值，不但有較好的穩(wěn)定性和收斂性，而且具有較好的光滑性，從而滿足了許多實(shí)際問(wèn)題的要求?！?分段低次插值一.龍格現(xiàn)象及高次插值的病態(tài)性質(zhì)

對(duì)于函數(shù),在區(qū)間上取節(jié)點(diǎn),所作Lagrange插值多項(xiàng)式為,當(dāng)時(shí),內(nèi)收斂于在這區(qū)間之外發(fā)散，這一現(xiàn)象稱為Runge現(xiàn)象。

二.分段線性插值直觀上容易想象,如果不用多項(xiàng)式曲線，而是將曲線的兩個(gè)相鄰的點(diǎn)用線段連接，這樣得到的折線必定能較好地近似曲線。而且只要連續(xù)，節(jié)點(diǎn)越密，近似程度越好。由此得到啟發(fā)，為提高精度，在加密節(jié)點(diǎn)時(shí)，可以把節(jié)點(diǎn)間分成若干段，分段用低次多項(xiàng)式近似函數(shù)，這就是分段插值的思想。用折線近似曲線，相當(dāng)于分段用線性插值，稱為分段線性插值。設(shè)已知函數(shù)在上的

個(gè)節(jié)點(diǎn)

上的函數(shù)值,作一個(gè)插值函數(shù),s.t.,(1);(2)在每個(gè)小區(qū)間上，是線性函數(shù)，則稱函數(shù)為上關(guān)于數(shù)據(jù)的分段線性插值函數(shù)。

由Lagrange線性插值公式容易寫(xiě)出的分段表達(dá)式為了建立的統(tǒng)一表達(dá)式，我們需要構(gòu)造一組基函數(shù)：且在每個(gè)小區(qū)間上是線性函數(shù)。在幾何上就是用折線替代曲線,如右圖所示若用插值基函數(shù)表示,則在

a,b

上

其中定理2.4

如果

在上二階連續(xù)可微，則分段線性插值函數(shù)

的余項(xiàng)有以下估計(jì)其中

。說(shuō)明：當(dāng)節(jié)點(diǎn)加密時(shí)，分段線性插值的誤差變小，收斂性有保證。另一方面，在分段線性插值中，每個(gè)小區(qū)間上的插值函數(shù)只依賴于本段的節(jié)點(diǎn)值，因而每個(gè)節(jié)點(diǎn)只影響到節(jié)點(diǎn)鄰近的一、二個(gè)區(qū)間，計(jì)算過(guò)程中數(shù)據(jù)誤差基本上不擴(kuò)大，從而保證了節(jié)點(diǎn)數(shù)增加時(shí)插值過(guò)程的穩(wěn)定性。但分段線性插值函數(shù)僅在區(qū)間

上連續(xù)，一般地，在節(jié)點(diǎn)處插值函數(shù)不可微，這就不能滿足有些工程技術(shù)問(wèn)題的光滑要求。例2.8已知

在四個(gè)節(jié)點(diǎn)上的函數(shù)值如下表所示304560901求

在區(qū)間上的分段連續(xù)線性插值函數(shù)

解將插值區(qū)間

分成連續(xù)的三個(gè)小區(qū)間

則

在區(qū)間

上的線性插值為

在區(qū)間

45,60

上的線性插值為

在區(qū)間

60,90

上的線性插值為將各小區(qū)間的線性插值函數(shù)連接在一起，得§4三次樣條插值

我們知道,給定n+1個(gè)節(jié)點(diǎn)上的函數(shù)值可以作n次插值多項(xiàng)式,但當(dāng)n較大時(shí),高次插值不僅計(jì)算復(fù)雜,而且可能出現(xiàn)Runge現(xiàn)象,采用分段插值雖然計(jì)算簡(jiǎn)單、也有一致收斂性,但不能保證整條曲線在連接點(diǎn)處的光滑性,如分段線性插值,其圖形是鋸齒形的折線,雖然連續(xù),但處處都是“尖點(diǎn)”,因而一階導(dǎo)數(shù)都不存在,這在實(shí)用上,往往不能滿足某些工程技術(shù)的高精度要求。如在船體、飛機(jī)等外形曲線的設(shè)計(jì)中,不僅要求曲線連續(xù),而且要有二階光滑度,即有連續(xù)的二階導(dǎo)數(shù)。這就要求分段插值函數(shù)在整個(gè)區(qū)間上具有連續(xù)的二階導(dǎo)數(shù)。因此有必要尋求一種新的插值方法,這就是樣條函數(shù)插值法

一、三次樣條函數(shù)定義2.2設(shè)函數(shù)定義在區(qū)間

a,b

上，給定n+1個(gè)節(jié)點(diǎn)和一組與之對(duì)應(yīng)的函數(shù)值，若函數(shù)滿足:（1）在每個(gè)節(jié)點(diǎn)上滿足

（2）在

a,b

上有連續(xù)的二階導(dǎo)數(shù)（3）在每個(gè)小區(qū)間

xi,xi+1

(i=0,1,…,n-1)

上是一個(gè)三次多項(xiàng)式。則稱為三次樣條插值函數(shù)。在上確定4個(gè)待定系數(shù)，共確定4n個(gè)參數(shù)

求出二、三次樣條插值函數(shù)的求法

設(shè)

在節(jié)點(diǎn)xi處的二階導(dǎo)數(shù)為

連續(xù)兩次積分得由上討論可知,只要確定這n+1個(gè)值,就可定出三次樣條插值函數(shù)S(x)。為了求出,利用一階導(dǎo)數(shù)在子區(qū)間連接點(diǎn)上連續(xù)的條件對(duì)上式求導(dǎo)一次,得在區(qū)間

xi-1,xi

上的表達(dá)式為（2.32）

也就是在右端點(diǎn)xi上有在左端點(diǎn)xi-1上有將上式中的i-1改為i,即得在子區(qū)間

xi,xi+1

上的表達(dá)式,并由此得利用在內(nèi)接點(diǎn)的連續(xù)性,即就可得到關(guān)于參數(shù)的一個(gè)方程上式兩邊同乘以,即得方程

若記

簡(jiǎn)寫(xiě)即

這是一個(gè)含有n+1個(gè)未知數(shù)、n-1個(gè)方程的線性方程組.要完全確定的值還需要補(bǔ)充兩個(gè)條件,這兩個(gè)條件通常根據(jù)實(shí)際問(wèn)題的需要，根據(jù)插值區(qū)間

a,b

的兩個(gè)端點(diǎn)處的邊界條件來(lái)補(bǔ)充。第一種邊界條件：即已知插值區(qū)間兩端的一階導(dǎo)數(shù)值：則可得到包含Mi的兩個(gè)線性方程,由(2.33)知,S(x)在子區(qū)間

上的導(dǎo)數(shù)為由條件得

即

(2.37)同理,由條件得

邊界條件的種類很多，常見(jiàn)的有以下3種：(2.38)

將式（2.36）和式（2.37）以及式（2.38）合在一起即得確定的線性方程組(2.39)其中第二種邊界條件:即已知插值區(qū)間兩端的二階導(dǎo)數(shù)值:,由于在區(qū)間端點(diǎn)處二階導(dǎo)數(shù)

，所以方程（2.36）中實(shí)際上只包含有n-1個(gè)未知數(shù)，從而得方程組(2.40)

第三種邊界條件:由與，可得

和

(2.41)(2.42)(2.43)其中將式(2.36),(2.41),(2.42)合在一起，即得關(guān)于的線性方程組。(2.44)

利用線性代數(shù)知識(shí),可以證明方程組（2.39）,（2.40）和（2.44）的系數(shù)矩陣都是非奇異的，因此有惟一解。例2.9已知的函數(shù)值如下：x1245f(x)1342在區(qū)間

1,5

上求三次樣條插值函數(shù)S(x),使它滿足邊界條件解:這是在第二種邊界條件下的插值問(wèn)題，故確定的方程組形如前面所示，由已知邊界條件,有則得求解的方程組為根據(jù)給定數(shù)據(jù)和邊界條件算出與

則得方程組解得又

即得S(x)在各子區(qū)間上的表達(dá)式,由式（2.32）知,S(x)在上的表達(dá)式為代入式(2.32)將代入上式化簡(jiǎn)后得

同理S(x)在上的表達(dá)式為

S(x)在上的表達(dá)式為故所求的三次樣條插值函數(shù)S(x)在區(qū)間上的表達(dá)式為三、誤差界與收斂性

用三次樣條繪制的曲線不僅有很好的光滑度，而且當(dāng)節(jié)點(diǎn)逐漸加密時(shí)，其函數(shù)值在整體上能很好地逼近被插函數(shù)，相應(yīng)的導(dǎo)數(shù)值也收斂于被插函數(shù)的導(dǎo)數(shù)，不會(huì)發(fā)生龍格現(xiàn)象。因此三次樣條在計(jì)算機(jī)輔助設(shè)計(jì)中有廣泛的應(yīng)用。本章小結(jié)

本章介紹的插值法是實(shí)用性很強(qiáng)的方法。它們解決的實(shí)際問(wèn)題雖然各式各樣，但抽象為數(shù)學(xué)問(wèn)題卻有它的共性，即利用已知的數(shù)據(jù)去尋求某個(gè)較為簡(jiǎn)單的函數(shù)P(x)來(lái)逼近f(x)。插值法給出了尋求這種近似函數(shù)的原則，以及構(gòu)造近似函數(shù)的幾種具體方法。插值法要求近似函數(shù)在已知的數(shù)據(jù)點(diǎn)必須與f(x)完全一致。

插值法中的拉格朗日插值多項(xiàng)式是研究數(shù)值微積分與微分方程數(shù)值解的重要工具。牛頓插值多項(xiàng)式是拉格朗日插值多項(xiàng)式的變形，具有承襲性，比拉格朗日插值多項(xiàng)式節(jié)省計(jì)算量。分段低次多項(xiàng)式插值由于具有良好的穩(wěn)定性與收斂性，且算法簡(jiǎn)單，便于應(yīng)用。特別是應(yīng)用廣泛的三次樣條插值，不但有較好的穩(wěn)定性和收斂性，而且具有較好的光滑性，從而滿足了許多實(shí)際問(wèn)題的要求。

第三章逼近方法

函數(shù)逼近的處理方法：

插值法

最小二乘曲線（最小二乘回歸）內(nèi)容概要3.1基本概念3.2函數(shù)的最佳平方逼近3.3曲線擬合的最小二乘法3.4最佳平方三角逼近與快速傅立葉變換3.5Matlab曲線擬合工具箱介紹

f(x)p(x)§3.1基本概念函數(shù)逼近問(wèn)題：對(duì)于函數(shù)類A中給定的函數(shù)，記作，要求在另一類簡(jiǎn)單的便于計(jì)算的函數(shù)類B中求函數(shù)，使

與的誤差在某種度量意義下達(dá)到最小。

范數(shù)與賦范數(shù)空間

定義：設(shè)是實(shí)數(shù)域上的線性空間，，如果存在唯一實(shí)數(shù)，滿足條件：

（正定性）（齊次性）（三角不等式）

則稱為線性空間上的范數(shù)，與一起稱

為賦范線性空間，記為。例如，對(duì)上的向量，有三種常用范數(shù)：類似地，對(duì)，可定義常用范數(shù)：內(nèi)積與內(nèi)積空間3.1.1正交函數(shù)族與正交多項(xiàng)式3.1.2勒讓德（Legendre）多項(xiàng)式3.1.3Chebyshev（切比雪夫）多項(xiàng)式3.1.3Chebyshev（切比雪夫）多項(xiàng)式3.1.3Chebyshev（切比雪夫）多項(xiàng)式3.1.4拉蓋爾（Laguerre）多項(xiàng)式3.1.5埃爾米特（Hermite）多項(xiàng)式3.2函數(shù)的最佳平方逼近3.2.2用正交函數(shù)族作最佳平方逼近3.3曲線擬合的最小二乘法3.3.1最小二乘原理3.3.2法方程3.3.3常用的擬合方法

例3.5已知實(shí)測(cè)數(shù)據(jù)表如下,確定數(shù)學(xué)模型y=aebx,用最小二乘法確定a，b。i01234

xi

yi1.001.251.501.752.005.105.796.537.458.46i01234

xi

yi

zi1.001.251.501.752.005.105.796.537.458.461.6291.7561.8762.0082.135i01234

xi

yi192531384419.032.349.073.397.8解按式(3-25)和(3-26)計(jì)算，得3.4最佳平方三角逼近與快速傅里葉變換3.4.1最佳平方三角逼近與三角插值3.4.2*快速傅氏變換（FFT）第四章數(shù)值微積分內(nèi)容提要4.1數(shù)值積分的基本概念4.2牛頓-柯特斯公式4.3復(fù)化求積公式4.4龍貝格求積公式4.5高斯求積公式4.6數(shù)值微分4.1數(shù)值積分（numericalquadrature）的基本概念4.1.1數(shù)值求積分的基本思想但有時(shí)原函數(shù)不能用初等函數(shù)表示，有時(shí)原函數(shù)又十分復(fù)雜，難于求出或計(jì)算；另外如被積函數(shù)是由測(cè)量或數(shù)值計(jì)算給出的一張數(shù)據(jù)表示時(shí)，上述方法也不能直接運(yùn)用。因此有必要研究積分的數(shù)值計(jì)算問(wèn)題。積分中值定理：平均高度f(wàn)(ζ)

a

ζ

b

yxy=f(x)0

a

b

yxy=f(x)0

a

f((a+b)/2)

b

yxy=f(x)0平均高度梯形公式平均高度中矩形公式更一般地，我們構(gòu)造具有下列形式的求積公式求積節(jié)點(diǎn)求積系數(shù)

這類數(shù)值方法通常稱為機(jī)械求積，其特點(diǎn)是將積分求值問(wèn)題歸結(jié)為函數(shù)值的計(jì)算，這就避開(kāi)了牛頓-萊布尼茲公式需要尋求原函數(shù)的困難。4.1.2代數(shù)精度的概念利用代數(shù)精度的概念構(gòu)造求積公式4.1.3插值型的求積公式4.1.4求積公式的收斂性與穩(wěn)定性4.2Newton-Cotes公式4.2.1Cotes系數(shù)4.2.2偶階求積公式的代數(shù)精度4.2.3幾種低階求積公式的余項(xiàng)4.3復(fù)化求積公式

在使用牛頓-柯特斯公式時(shí)將導(dǎo)致求積系數(shù)出現(xiàn)負(fù)數(shù)(當(dāng)n≥8時(shí),牛頓.柯特斯求積系數(shù)會(huì)出現(xiàn)負(fù)數(shù))，因而不可能通過(guò)提高階的方法來(lái)提高求積精度。為了提高精度通常采用將積分區(qū)間劃分成若干個(gè)小區(qū)間，在各小區(qū)間上采用低次的求積公式(梯形公式或辛普森公式)，然后再利用積分的可加性，把各區(qū)間上的積分加起來(lái)，便得到新的求積公式，這就是復(fù)化求積公式的基本思想。本節(jié)只討論復(fù)化的梯形公式和復(fù)化的辛普森公式。問(wèn)題與基本思想4.3.1復(fù)化梯形公式4.3.2復(fù)化辛普森公式xi01/81/43/81/2f(xi)10.99739780.98961580.97672670.9588510xi5/83/47/81f(xi)0.93615560.90885160.84147090.84147094.4龍貝格求積公式4.4.1梯形公式的逐次分半算法4.4.2李查遜（Richardson）外推法第四章數(shù)值微積分內(nèi)容提要4.1數(shù)值積分的基本概念4.2牛頓-柯特斯公式4.3復(fù)化求積公式4.4龍貝格求積公式4.5高斯求積公式4.6數(shù)值微分4.4龍貝格求積公式4.4.1梯形公式的逐次分半算法

于是可以逐次對(duì)分形成一個(gè)序列｛T1,T2,T4,T8,…},此序列收斂于積分真值I。當(dāng)|T2n-Tn|<ε時(shí)，取T2n為I的近似值。以上算法稱為變步長(zhǎng)求積法。但由于此序列收斂太慢。下節(jié)我們將其改造成為收斂快的序列。4.4.2李查遜（Richardson）外推法4.4.3龍貝格求積公式如何提高收斂速度以節(jié)省計(jì)算量是龍貝格算法要討論的中心問(wèn)題。

這樣我們從收斂較慢的{Tn}序列推出了收斂較快的{Sn}序列?？梢宰C明{Sn}序列實(shí)際上就是逐次分半的復(fù)化辛普森公式序列。

這樣我們從{Cn}序列又推出了收斂更快的{Rn}序列.{Rn}序列也稱為龍貝格序列。我們從收斂較慢的{Tn}序列只用了一些四則運(yùn)算，便推出了收斂更快的{Sn}序列,{Cn}序列和{Rn}序列。運(yùn)算順序表T1T2S1T4S2C1T8S4C2R1T16S8C4R2﹕﹕﹕T1T2S1T4S2C1T8S4C2R1T16S8C4R2﹕﹕﹕﹕kT2kS2k-1C2k-2R2k-300.920735510.93979330.946145920.94451350.94608690.946083030.94569090.94608330.94608310.9460831這里利用二分3次的數(shù)據(jù)（它們的精度都很差，只有兩三位有效數(shù)字）通過(guò)三次加速求得R1=0.9460831,這個(gè)結(jié)果的每一位數(shù)字都是有效數(shù)字，可見(jiàn)加速效果是十分顯著的。4.5高斯求積公式一般理論4.6數(shù)值微分4.6.1利用差商求導(dǎo)數(shù)

數(shù)值微分就是要用函數(shù)值的線性組合近似函數(shù)在某點(diǎn)的導(dǎo)數(shù)值。由導(dǎo)數(shù)定義差商近似導(dǎo)數(shù)得到數(shù)值微分公式。中點(diǎn)方法與誤差分析hG(h)hG(h)hG(h)10.36600.050.35300.0010.35000.50.35640.010.35000.00050.30000.10.35350.0050.35000.00010.3000插值型的求導(dǎo)公式第五章解線性方程組的直接方法內(nèi)容提要5.1引言5.2高斯消去法5.3高斯列主元消去法5.4矩陣三角分解法5.5平方根法5.5向量與矩陣的范數(shù)5.6誤差分析引言關(guān)于線性方程組的數(shù)值解法一般有兩類：1、直接解法：經(jīng)過(guò)有限次的算術(shù)運(yùn)算，可求得方程組精確解的方法（若計(jì)算過(guò)程中沒(méi)有舍入誤差）。但實(shí)際計(jì)算中由于舍入誤差的存在和影響，這種方法也只能求得線性方程組的近似解。本章主要研究此類問(wèn)題的解法。2、迭代法：用某種極限過(guò)程去逐步逼近現(xiàn)行方程組精確解的方法。迭代法具有需要計(jì)算機(jī)的存儲(chǔ)單元較少、程序設(shè)計(jì)簡(jiǎn)單、原始系數(shù)矩陣在計(jì)算過(guò)程中始終不變等優(yōu)點(diǎn)。高斯消去法再求解三角方程組,得高斯消去法的條件高斯列主元消去法列主元消去法矩陣三角分解法

Ax=b是線性方程組,A是n×n方陣,并設(shè)A的各階順序主子式不為零。令A(yù)(1)=A,當(dāng)高斯消元法進(jìn)行第一步后,相當(dāng)于用一個(gè)初等矩陣左乘A(1)。不難看出，這個(gè)初等矩陣為重復(fù)這個(gè)過(guò)程，最后得到一般地

這就是說(shuō)，高斯消去法實(shí)質(zhì)上產(chǎn)生了一個(gè)將A分解為兩個(gè)三角形矩陣相乘的因式分解，于是我們得到如下重要定理。當(dāng)A進(jìn)行LU分解后，Ax=b就容易解了.即Ax=b等價(jià)于:

追趕法

在一些實(shí)際問(wèn)題中，例如解常微分方程邊值問(wèn)題，熱傳導(dǎo)方程以及船體數(shù)學(xué)放樣中建立三次樣條函數(shù)等，都會(huì)要求解系數(shù)矩陣為對(duì)角占優(yōu)的三對(duì)角線方程組其中|i-j|>1時(shí),aij=0,且滿足如下的對(duì)角占優(yōu)條件:(1)|b1|>|c1|>0,|bn|>|an|>0(2)|bi|≥|ai|+|ci|,aici≠0,i=2,3,…,n-1.平方根法平方根法（Cholesky分解法）第一步第二步：求解下三角形方程組第三步：求解上三角形方程組用平方根法解對(duì)稱正定方程組時(shí)，計(jì)算的元素需要開(kāi)方。為了避免這一運(yùn)算，引進(jìn)改進(jìn)的平方根法。定義1(向量范數(shù))x和y是Rn中的任意向量,向量范數(shù)‖?‖是定義在Rn上的實(shí)值函數(shù),它滿足:(1)‖

x

‖≥0,并且當(dāng)且僅當(dāng)x=0時(shí),‖

x

‖=0;(2)‖k

x

‖=|k|‖

x

‖,k是一個(gè)實(shí)數(shù);(3)‖

x+y

‖≤‖

x

‖+‖

y

‖常使用的向量范數(shù)有三種,設(shè)x=(x1,x2,…,xn)T

敏感性與解的誤差分析常使用的矩陣范數(shù)有三種,設(shè)x=(x1,x2,…,xn)T

由向量導(dǎo)出的矩陣范數(shù)：F范數(shù)誤差分析內(nèi)容提要

6.1單步定常迭代法

6.2基于矩陣分裂的迭代法

6.3特殊方程組迭代法的收斂性

6.4迭代法在數(shù)值求解偏微分方程中的應(yīng)用第六章解線性代數(shù)方程組的迭代法

即AX=b其中A為非奇異矩陣，當(dāng)A為低階稠密矩陣時(shí)，線性方程組用直接法(如高斯消去法和三角分解法)是有效的，但對(duì)于由工程技術(shù)中產(chǎn)生的大型稀疏矩陣方程組（A的階數(shù)n很大，但零元素較多），利用迭代法求解是適合的。在計(jì)算機(jī)內(nèi)存和運(yùn)算兩方面，迭代通常都可利用A中有大量零元素的特點(diǎn)。考慮線性方程組

本章將介紹迭代法的一般理論及雅可比迭代法、高斯—塞德?tīng)柕ā⒅鸫纬沙诘?，研究它們的收斂性?.1

單步定常迭代法矩陣序列的極限單步定常迭代法單步定常迭代法將方程組迭代矩陣迭代法的一般理論迭代法的收斂速度6.2基于矩陣分裂的迭代法Jacobi迭代法等價(jià)變形高斯—塞德?tīng)柕ㄖ鸫纬神Y(SOR)迭代法SOR迭代法的計(jì)算公式:對(duì)k=0,1,…,說(shuō)明:

1)ω=1,即為GS（高斯-賽德?tīng)柕ǎ?2)ω>1，稱為超松馳法；

ω<1，稱為低松馳法；

3)SOR方法每迭代一次主要運(yùn)算量是計(jì)算一次矩陣與向量的乘法。例6-3

用SOR迭代法解線性代數(shù)方程組6.3迭代法的收斂性單步定常迭代法的基本定理

注：定理4中的矩陣是迭代矩陣，常用格式的迭代矩陣如下：1)雅可比迭代法:2)高斯-賽德?tīng)柕?3)SOR迭代法:

例6-4

考察用雅可比迭代法求解線性方程組的收斂性。某些特殊方程組的迭代收斂性定義6.3（1）按行嚴(yán)格對(duì)角占優(yōu)

（2）按行弱對(duì)角占優(yōu)

上式至少有一個(gè)不等號(hào)嚴(yán)格成立。

定理8(對(duì)角占優(yōu)定理)若矩陣A按行(或列)嚴(yán)格對(duì)角占優(yōu)，或按行(或列)弱對(duì)角占優(yōu)且不可約；則矩陣A非奇異。

定理6.8

若矩陣A按行(或列)嚴(yán)格對(duì)角占優(yōu),或按行(或列)弱對(duì)角占優(yōu)不可約；則Jacobi迭代、Gauss-Seidel迭代都收斂。定理6.11

對(duì)于線性方程組，若(1)A為對(duì)稱正定矩陣，(2)0<ω<2，

則解

的SOR迭代收斂。

定理12

對(duì)于線性代數(shù)方程組Ax=b，若A按行(或列)嚴(yán)格對(duì)角