現(xiàn)代數(shù)值計算(第3版)課件 第6、7章 數(shù)值積分與數(shù)值微分、非線性方程求解_第1頁
現(xiàn)代數(shù)值計算(第3版)課件 第6、7章 數(shù)值積分與數(shù)值微分、非線性方程求解_第2頁
現(xiàn)代數(shù)值計算(第3版)課件 第6、7章 數(shù)值積分與數(shù)值微分、非線性方程求解_第3頁
現(xiàn)代數(shù)值計算(第3版)課件 第6、7章 數(shù)值積分與數(shù)值微分、非線性方程求解_第4頁
現(xiàn)代數(shù)值計算(第3版)課件 第6、7章 數(shù)值積分與數(shù)值微分、非線性方程求解_第5頁
已閱讀5頁,還剩193頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領

文檔簡介

第六章AdvancedNumericalComputing數(shù)值積分與數(shù)值微分現(xiàn)代數(shù)值計算同濟大學數(shù)學科學學院目錄/Contents第六章數(shù)值積分與數(shù)值微分第一節(jié)幾個常用積分公式及其復合公式第二節(jié)變步長方法與外推加速技術第三節(jié)高斯公式第四節(jié)多重積分的計算第五節(jié)數(shù)值微分引言Newton-Leibniz公式:數(shù)值(近似)積分的必要性:無解析原函數(shù)的被積函數(shù):

,

,等等利用數(shù)據(jù)表給出的函數(shù)的積分計算機程序提供的函數(shù)的積分被積函數(shù)表達式太復雜設在 (不妨先設

為有限數(shù))上,

,

為某個較“簡單”的函數(shù),則有誤差為:因此只要

,就有誤差估計引言6.1幾個常用積分公式及其復合公式6.1.1幾個常用積分公式6.1幾個常用積分公式及其復合公式6.1.1幾個常用積分公式6.1幾個常用積分公式及其復合公式6.1.1幾個常用積分公式6.1幾個常用積分公式及其復合公式6.1.1幾個常用積分公式6.1幾個常用積分公式及其復合公式6.1.1幾個常用積分公式6.1幾個常用積分公式及其復合公式6.1.1幾個常用積分公式設如果對函數(shù)

,用

上的函數(shù)值近似代替,即得中點公式推導誤差:設

,由Taylor公式,兩邊積分,即得6.1幾個常用積分公式及其復合公式6.1.1幾個常用積分公式下面我們通過插值節(jié)點

作線性插值函數(shù)

,利用

得梯形公式:上面求積公式的右端值可看成是由線段

,過點

的直線以及

軸圍成的梯形面積.如果

,則由線性插值函數(shù)的誤差公式(見第3章)以及積分中值定理得:6.1幾個常用積分公式及其復合公式6.1.1幾個常用積分公式6.1幾個常用積分公式及其復合公式6.1.1幾個常用積分公式若

用通過節(jié)點

的二次插值多項式

代替,6.1幾個常用積分公式及其復合公式6.1.1幾個常用積分公式則得拋物型公式(或稱Simpson公式)可以證明:若

,則有誤差公式:6.1幾個常用積分公式及其復合公式6.1.1幾個常用積分公式求積公式

、節(jié)點

、系數(shù)

、余項

.6.1幾個常用積分公式及其復合公式6.1.1幾個常用積分公式【定義6.1】如果對于所有次數(shù)

的多項式

,等式

精確成立,但對于某一次數(shù)為

的多項式不精確成立,則稱此求積公式的代數(shù)精度為

次。6.1幾個常用積分公式及其復合公式6.1.2代數(shù)精度【例6.1】試確定系數(shù)

,

,使得求積公式

有盡可能高的代數(shù)精度,并求出此求積公式的代數(shù)精度。解:分別令

, , ,代入使積分公式精確成立,得到線性方程組6.1幾個常用積分公式及其復合公式6.1.2代數(shù)精度解得

,

這樣求積公式為該公式對

精確成立,但

時不精確成立。因此具有三次代數(shù)精度。6.1幾個常用積分公式及其復合公式6.1.2代數(shù)精度設在節(jié)點上的函數(shù)值為作

次Lagrange插值多項式,有插值型求積公式代數(shù)精度有幾次?6.1幾個常用積分公式及其復合公式【定理6.3】求積公式

至少具有

次代數(shù)精度的充分必要條件是它是插值型的。

次數(shù)

時,

,代數(shù)精度至少

次。反之,若代數(shù)精度至少

次,則必定是插值型的:用

代入,6.1幾個常用積分公式及其復合公式Newton-Cotes公式即是等距節(jié)點的插值型求積公式。將區(qū)間

等分,步長

,等距節(jié)點

.

作變量代換

,代入

中,有(NC系數(shù))6.1幾個常用積分公式及其復合公式常見的Newton-Cotes公式梯形公式(一次)拋物線(Simpson)公式(三次)Cotes公式(五次)6.1幾個常用積分公式及其復合公式有負系數(shù)6.1幾個常用積分公式及其復合公式

n12345678【定理6.4】當

為偶數(shù)時,牛頓-柯特斯公式的代數(shù)精度至少為 .證明:只需要證明

時,積分余項為 .作變量替換

.對上述積分再做變量代換

,得6.1幾個常用積分公式及其復合公式穩(wěn)定性即數(shù)據(jù)

有誤差,只能有近似值

,是否有若

,則當

時,

,且

穩(wěn)定.而當

時,由于求積系數(shù)

有正有負,

一般無界,因此穩(wěn)定性不成立,收斂性也不成立.6.1幾個常用積分公式及其復合公式設

,由誤差公式知當

很小時,中點公式,梯形公式及拋物型公式的誤差為

,

,

通常情況下,積分區(qū)間

的長度

不是非常小,此時誤差就比較大。為了確保計算精度,提出了復合求積公式。即將積分區(qū)間分為若干份,在每一個“小區(qū)間”上用低階求積公式如中點公式,梯形公式及拋物型公式進行計算,再將計算值相加即得原積分的近似值.6.1幾個常用積分公式及其復合公式6.1.2代數(shù)精度復合中點公式等分求積區(qū)間,記小區(qū)間

中點為

,記步長

,每個小區(qū)間上運用中點求積公式設

,則(待證)存在

6.1幾個常用積分公式及其復合公式6.1.3積分公式的復合functionI=fmid(fun,a,b,n)

h=(b-a)/n;

x=linspace(a+h/2,b-h/2,n);

y=feval(fun,x);

I=h*sum(y);6.1幾個常用積分公式及其復合公式6.1.3積分公式的復合復合梯形公式等分求積區(qū)間,節(jié)點為,每個小區(qū)間上運用梯形求積公式設

,則存在

6.1幾個常用積分公式及其復合公式6.1.3積分公式的復合functionI=ftrapz(fun,a,b,n)

h=(b-a)/n;

x=linspace(a,b,n+1);

y=feval(fun,x);

I=h*(0.5*y(1)+sum(y(2:n))+0.5*y(n+1));6.1幾個常用積分公式及其復合公式6.1.3積分公式的復合復合Simpson公式等分求積區(qū)間,記小區(qū)間

中點為

,在每個小區(qū)間上Simpson求積公式,設

,則6.1幾個常用積分公式及其復合公式6.1.3積分公式的復合functionI=fsimpson(fun,a,b,n)

h=(b-a)/n;

x=linspace(a,b,2*n+1);

y=feval(fun,x);

I=(h/6)*(y(1)+2*sum(y(3:2:2*n-1))+4*sum(y(2:2:2*n))+y(2*n+1));6.1幾個常用積分公式及其復合公式6.1.3積分公式的復合【定理6.1】設

,則存在

,使得證:設

,

其中

.

則有6.1幾個常用積分公式及其復合公式6.1.3積分公式的復合利用連續(xù)函數(shù)的中值定理,存在

滿足:所以6.1幾個常用積分公式及其復合公式6.1.3積分公式的復合下面設,推導復合中點公式(5.13)的誤差.首先由(5.12),(5.13)及誤差公式(5.3),利用定理5.2.3,便有6.1幾個常用積分公式及其復合公式6.1.3積分公式的復合同理可推得復合梯形公式、復合Simpson公式的誤差估計:6.1幾個常用積分公式及其復合公式6.1.3積分公式的復合【例6.2】設

在9個節(jié)點處的值由下表給出,分別用復合梯形公式和復合Simpson公式計算積分6.1幾個常用積分公式及其復合公式6.1.3積分公式的復合01/81/43/81/210.99739780.98961580.97672670.95385105/83/47/810.93615560.90885160.87719250.8414709解:將積分區(qū)間

八等分,由復合梯形公式(此時 )計算得:如果將

四等分,由復合Simpson公式( )得:6.1幾個常用積分公式及其復合公式6.1.3積分公式的復合functiony=f(x)

x=x+(x==0)*eps;

y=sin(x)./x;

調用:ftrapz(@f,0,1,8)或fsimpson(@f,0,1,4)與精確值I=0.9460831相比較:復合梯形公式兩位有效數(shù)字,復合Simpson公式有六位有效數(shù)字!6.1幾個常用積分公式及其復合公式6.1.3積分公式的復合【例6.3】利用n=5的復合Simpson公式計算積分將

五等分,由復合Simpson公式( )得:6.1幾個常用積分公式及其復合公式6.1.3積分公式的復合【例6.4】使用三種不同的計算公式:復合中點公式,復合梯形公式,復合Simpson公式計算下列積分值,并分別取

,比較三種不同算法的收斂速度.積分的精確值為6.1幾個常用積分公式及其復合公式6.1.3積分公式的復合解:三種復合求積公式的計算結果分別用

表示,則計算結果如下表.6.1幾個常用積分公式及其復合公式6.1.3積分公式的復合

n10.97510.15890.703021.03700.56700.502140.12220.23483.139×10-382.980×10-25.635×10-21.085×10-3166.748×10-31.327×10-27.381×10-5321.639×10-33.263×10-34.682×10-6644.066×10-48.123×10-42.936×10-71281.014×10-42.028×10-41.836×10-82562.535×10-55.070×10-51.148×10-9三者的收斂速度比較圖,其中橫坐標為

,縱坐標為

,從圖中可看出三種計算公式的誤差分別為:與理論誤差估計相當吻合.6.1幾個常用積分公式及其復合公式6.1.3積分公式的復合對于節(jié)點

及函數(shù)值

,定義三個分段函數(shù)

則在

有:6.1幾個常用積分公式及其復合公式6.1.3積分公式的復合則三個函數(shù)都可看成是

的某種逼近6.1幾個常用積分公式及其復合公式6.1.3積分公式的復合復合中點公式,復合梯形公式和復合Simpson公式可看成

用代替后的近似積分值易證當

為連續(xù)函數(shù)時, .從而有6.1幾個常用積分公式及其復合公式6.1.3積分公式的復合復合求積公式的穩(wěn)定性:設

在節(jié)點

處的精確值為

,實際值為

.

節(jié)點

處的誤差為:記由數(shù)值

計算所得的梯形公式的值為

,則設

,則6.1幾個常用積分公式及其復合公式6.1.3積分公式的復合目錄/Contents第六章數(shù)值積分與數(shù)值微分第一節(jié)幾個常用積分公式及其復合公式第二節(jié)變步長方法與外推加速技術第三節(jié)高斯公式第四節(jié)多重積分的計算第五節(jié)數(shù)值微分引言:(1)復合求積公式是有效的求積方法,當步長

越小,計算精度越高.(2)實際運用中,需選取一個合適的步長

:若步長太大,計算精度就難以保證,若步長太小,

則會增加不必要的計算開銷;(3)在給定計算精度的情形下,往往通過不斷調整步長的方式進行計算:如采用讓步長逐次折半的方式,反復使用復合求積公式直至相鄰兩次計算結果之差的絕對值小于給定的計算精度為止。這種方法即稱為變步長算法。6.2變步長方法與外推加速技術6.2.1變步長梯形法下面以變步長的梯形公式加以說明:由求積公式誤差估計,若

,則有6.2變步長方法與外推加速技術6.2.1變步長梯形法只要

充分接近,就能保證

的誤差很小。算法(區(qū)間折半法):取初始步長h=b-a;

計算

;

取步長

,計算出相應的積分值

;若條件

滿足,則取

為最后積分計算的近似值,否則讓步長折半,回到第(3)步.6.2變步長方法與外推加速技術6.2.1變步長梯形法變步長梯形積分區(qū)間折半,新增區(qū)間中點,

6.2變步長方法與外推加速技術6.2.1變步長梯形法【例6.5】用變步長梯形公式計算積分

的近似值,要求計

算精度

將積分區(qū)間等分

份復合梯形公式才滿足計算精度。6.2變步長方法與外推加速技術6.2.1變步長梯形法kk00.920735560.946076910.939793370.946081520.944513580.946082730.945690990.946083040.9459850100.946083150.9460596

例如上例中,

, (各具有2,3個有效數(shù)字) 新的近似值具有6位有效數(shù)字。實際上,6.2變步長方法與外推加速技術6.2.2Romberg算法例如,加上修正部分使精度從梯形的

提高到了拋物形的 .6.2變步長方法與外推加速技術6.2.2Romberg算法實際上,從拋物形積分組合得到Cotes積分:從Cotes積分組合得到Romberg積分:6.2變步長方法與外推加速技術6.2.2Romberg算法【例6.6】用Romberg算法求積分

,要求精度

.解:按照公式及不同的步長(初始步長 ),計算結果如下表:注:

表示積分區(qū)間

的等分次數(shù),節(jié)點數(shù)為

.Romberg方法最后采用的步長為

,而上例中普通變步長法為

.兩者的計算精度大致相同,因此Romberg加速收斂的效果是非常明顯的.6.2變步長方法與外推加速技術6.2.2Romberg算法k

00.920735510.93979330.946145920.94451350.94608690.946083030.94569090.94608340.94608310.9460831Richardson外推加速收斂技術,其實質是利用不同步長的復合梯形公式以及外推技術加速收斂速度,通常也稱為龍貝格Romberg求積方法,為推導更一般的結論,我們給出【定理6.2】歐拉-麥克勞林(Euler-MacLaurin)公式:設 (k為非負整數(shù)),

,則存在伯努利數(shù)

,使得下面關系成立:6.2變步長方法與外推加速技術6.2.2外推加速技術與Romberg算法由上面定理知復合梯形公式的誤差為兩邊同乘以

相減,有以

代替

6.2變步長方法與外推加速技術6.2.2Romberg算法由此可見,

的計算精度為

,而

的計算精度為

一般記

,有這個計算過程即稱為龍貝格(Romberg)方法.的計算精度為

6.2變步長方法與外推加速技術6.2.2Romberg算法目錄/Contents第六章數(shù)值積分與數(shù)值微分第一節(jié)幾個常用積分公式及其復合公式第二節(jié)變步長方法與外推加速技術第三節(jié)高斯公式第四節(jié)多重積分的計算第五節(jié)數(shù)值微分若上面求積公式對任何次數(shù)小于等于

的多項式

等式成立,但對于某一個次數(shù)為

的多項式不成立,則稱積分公式的代數(shù)精度為

次。6.4高斯(Gauss)公式6.4.1高斯公式的定義及性質考慮帶權函數(shù)的求積公式其中

稱為權函數(shù).顯然

時上述定義與第二節(jié)一致,因此可以將這里的代數(shù)精度的概念其概念的推廣.

為一些特殊的函數(shù)。如

,

等.而

一般比較光滑的函數(shù)。問:對于等分節(jié)點的Newton-Cotes公式,代數(shù)精度一般為

,而如果采用非等分節(jié)點,即節(jié)點

與求積系數(shù)

都待定的話,能否提高代數(shù)精度呢?要使求積公式具有

次代數(shù)精度,應對

,,,成立下列等式(為敘述簡單,以

為例):關于未知量

的非線性代數(shù)方程組,如何求解?6.4高斯(Gauss)公式6.4.1高斯公式的定義及性質如何選擇

使代數(shù)精度達到最高?6.4高斯(Gauss)公式6.4.1高斯公式的定義及性質最簡單的例子

:試確定

使下面的求積公式有盡量高的代數(shù)精度假設

,

.令

, , ,,代入因此,6.4高斯(Gauss)公式6.4.1高斯公式的定義及性質【定義6.2】若對于節(jié)點

及求積系數(shù)

,求積公式(5.26)的代數(shù)精度為

則稱節(jié)點

為高斯點,

為高斯系數(shù),相應的求積公式稱為帶權的高斯公式。一旦確定了高斯點,由于它的代數(shù)精度為

,因此仍然可用待定系數(shù)法的方法來確定系數(shù)

特別地,若在高斯公式中令

,則有因此高斯公式仍可看成是一種插值型求積公式。6.4高斯(Gauss)公式6.4.1高斯公式的定義及性質【定理6.5】

是求積公式的高斯點的充分必要條件是多項式

與任意次數(shù)不超過

的多項式

關于權函數(shù)

正交:6.4高斯(Gauss)公式6.4.1高斯公式的定義及性質必要性:因為

次數(shù)不超過

,其中

,

次數(shù)不超過 .充分性:對于任意給定的次數(shù)不超過

次的多項式

,令

.

6.4高斯(Gauss)公式6.4.1高斯公式的定義及性質6.4高斯(Gauss)公式6.4.1高斯公式的定義及性質【定理6.6】插值型求積公式的代數(shù)精度最高不超過 .證:令

,則

次的多項式。該積分公式的代數(shù)精度不可能達到 .6.4高斯(Gauss)公式6.4.1高斯公式的定義及性質求積公式的穩(wěn)定性令

次多項式.由于Gauss積分精確成立,所以若在高斯公式中取

,則有利用

的性質及穩(wěn)定性的討論知高斯公式對任意

都是穩(wěn)定的.6.4高斯(Gauss)公式6.4.1高斯公式的定義及性質【例6.7】求高斯型求積公式的系數(shù)

和節(jié)點

。6.4高斯(Gauss)公式6.4.1高斯公式的定義及性質【定理6.7】設

為有限數(shù),則對任意的函數(shù)

,當

時,高斯求積公式均收斂,即高斯型公式有三次代數(shù)精度,令 , , ,,代入因此,6.4高斯(Gauss)公式6.4.1高斯公式的定義及性質解之得幾個常見的Gauss-Legendre公式1.高斯--勒讓德(Gauss-Legendre)求積公式

,知高斯點

即為

次勒讓德正交多項式的零點,

.6.4高斯(Gauss)公式6.4.2常用Gauss求積公式6.4高斯(Gauss)公式6.4.2常用Gauss求積公式然后再用相應的高斯--勒讓德公式來計算對于一般區(qū)間

上的積分,我們可以做變量代換將積分區(qū)間化為

,其中

即為高斯點,

為高斯系數(shù).6.4高斯(Gauss)公式6.4.2常用Gauss求積公式2.高斯--切比雪夫(Gauss-Chebyshev)公式取 .知此時的高斯點為區(qū)間

關于權函數(shù)

的正交多項式--切比雪夫正交多項式

的零點.高斯點高斯系數(shù)6.4高斯(Gauss)公式6.4.2常用Gauss求積公式3.高斯--拉蓋爾(Gauss-Laguerre)求積公式:取

,高斯點應為區(qū)間

上關于權函數(shù)

正交的多項式零點-- 次拉蓋爾(Laguerre)正交多項式

的零點.高斯系數(shù)6.4高斯(Gauss)公式6.4.2常用Gauss求積公式4.高斯--埃爾米特(Gauss-Hermite)求積公式取

,高斯點為

上關于權函數(shù)

正交的多項式-- 次埃爾米特正交多項式

的零點.高斯系數(shù)

的計算公式為:求積公式為:6.4高斯(Gauss)公式6.4.2常用Gauss求積公式【例6.8】用高斯--勒讓德公式計算積分 (精確值 )解:先作變換,則積分區(qū)間[0,1化為[-1,1],且用兩點高斯-勒讓德公式得(四位有效數(shù)字):6.4高斯(Gauss)公式6.4.3高斯公式的應用【例6.8】用高斯--勒讓德公式計算積分 (精確值 )解:用三點高斯-勒讓德公式(7位有效數(shù)字):復合梯形公式要求

個點上的值才能達到同樣的精度.6.4高斯(Gauss)公式6.4.3高斯公式的應用【例6.9】用高斯--勒讓德公式計算下列積分分別取

,觀察誤差隨高斯點數(shù)的變化規(guī)律.解:當

時,

處分別為連續(xù)、一階連續(xù)可導以及二階連續(xù)可導的.令誤差用

表示橫坐標和縱坐標,則計算結果如下圖.6.4高斯(Gauss)公式6.4.3高斯公式的應用6.4高斯(Gauss)公式6.4.3高斯公式的應用Figure1:被積函數(shù)的光滑性與高斯公式收斂速度之間的關系從上圖可看到無論取0,1或2,隨著高斯點的增加,誤差也相應地減小,即高斯公式是收斂的.當函數(shù)為無窮次可微的解析函數(shù)時,可以證明此時誤差為指數(shù)收斂(或稱為無窮次收斂速度)

為正常數(shù).6.4高斯(Gauss)公式6.4.3高斯公式的應用當

較大時,誤差

有近似表達式

(為與

無關的正常數(shù)).刻劃收斂速度的指標

隨著被積函數(shù)

的光

滑性的提高而變大.從而可知高斯公式的收斂速度與被積函數(shù)的光滑性有關.目錄/Contents第六章數(shù)值積分與數(shù)值微分第一節(jié)幾個常用積分公式及其復合公式第二節(jié)變步長方法與外推加速技術第三節(jié)高斯公式第四節(jié)多重積分的計算第五節(jié)數(shù)值微分【例6.10】用復合Simpson公式,取

計算積分(真值=1):解:設

,則其中,

.同理,再次利用Simpson公式得6.5多重積分的計算6.5.1二重積分的計算使用同樣思路,可得到矩形區(qū)域

上的復合Simpson公式.將

方向和

方向分成

份和

份,記

則計算二重積分的復合Simpson公式為:6.5多重積分的計算6.5.1二重積分的計算6.5多重積分的計算6.5.1二重積分的計算上述復合Simpson公式原則上可推廣至任何有界區(qū)域上的多重積分.推導如下:取

維長方體將被積函數(shù)

延拓為

上的函數(shù) ,則

化為

維長方體上的積分:由于

為長方體,可以使用上述復合Simpson公式計算

的值.6.5多重積分的計算6.5.1二重積分的計算維數(shù)

的增大,節(jié)點數(shù)

急劇增多.這導致計算量大大增加,而計算的誤差

的減少卻很緩慢,即維數(shù)災難.

維復合Simpson公式的誤差R與節(jié)點數(shù)

的關系為則每個方向的計算誤差約為

,而總的求積誤差 (及

均為正常數(shù)).多重積分的計算誤差與計算節(jié)點數(shù)之間的關系以復合Simpson公式為例,設函數(shù)

充分光滑.復合Simpson公式計算時每個方向取

個點由于區(qū)域是

維,因此總的節(jié)點數(shù)為 .計算高維

數(shù)值積分的蒙特卡羅(MonteCarlo)方法.6.5多重積分的計算6.5.1二重積分的計算考慮區(qū)間[0,1]上的積分,可直接推廣到多維的情形.設隨機變量

服從[0,1]上的均勻分布,即 . 為任意可積函數(shù),則隨機變量

的函數(shù)

的數(shù)學期望函數(shù)

在區(qū)間[0,1]上的積分.6.5多重積分的計算6.5.2蒙特卡羅(MonteCarlo)模擬求積法簡介記則

的一個無偏估計量:由概率論中的大數(shù)定理,當

時,

依概率收斂于

,即6.5多重積分的計算6.5.2蒙特卡羅(MonteCarlo)模擬求積法簡介估計誤差: .由于

仍為隨機變量,我們估計其方差(一般認為均方差即是誤差).由于

,所以由于

相互獨立,可推出當

時,因此6.5多重積分的計算6.5.2蒙特卡羅(MonteCarlo)模擬求積法簡介高維區(qū)域積分可取

次獨立取樣值的算術平均方差仍為

,即收斂速度不受積分區(qū)域維數(shù)

的影響!正因為蒙特卡羅方法具有這個特性,才能成為計算高維積分的有效數(shù)值方法.另外我們可以看出,蒙特卡羅方法的收斂速度為

,與被積函數(shù)的光滑性無關.這一性質與插值型積分公式大不相同!作為積分

的無偏估計量.6.5多重積分的計算6.5.2蒙特卡羅(MonteCarlo)模擬求積法簡介【例6.11】用蒙特卡羅方法計算積分

.解:首先令

,將積分化為標準區(qū)間[0,1]上的積分:其次取

次相互獨立的均勻分布

的樣本,則分別取

,計算出積分的近似值 .6.5多重積分的計算6.5.2蒙特卡羅(MonteCarlo)模擬求積法簡介程序如下:x=[102050100200

500

100020005000100002000050000];I=quad(‘sin(x)’./x’,0,2,1.e-16);fori=1:length(x)z=rand(x(i),1);In=sin(2*z)./z;In=mean(In);y(i)=abs(In-I);endx=log(x);y=log(y);plot(x,y,’.-’);xlabel(‘logN’);ylabel(‘logR_N’);6.5多重積分的計算6.5.2蒙特卡羅(MonteCarlo)模擬求積法簡介6.5多重積分的計算6.5.2蒙特卡羅(MonteCarlo)模擬求積法簡介Figure2:誤差

隨節(jié)點的變化規(guī)律目錄/Contents第六章數(shù)值積分與數(shù)值微分第一節(jié)幾個常用積分公式及其復合公式第二節(jié)變步長方法與外推加速技術第三節(jié)高斯公式第四節(jié)多重積分的計算第五節(jié)數(shù)值微分插值余項令6.6數(shù)值微分6.6.1基于拉格朗日插值多項式的求導方法插值余項兩點公式同理6.6數(shù)值微分6.6.1基于拉格朗日插值多項式的求導方法三點公式6.6數(shù)值微分6.6.1基于拉格朗日插值多項式的求導方法【例6.12】給定函數(shù)的下列數(shù)據(jù)表,試利用二點、三點微分公式計算處的一階導數(shù)值。解:兩點公式6.6數(shù)值微分6.6.1基于拉格朗日插值多項式的求導方法2.52.62.72.82.912.182513.463714.879716.444618.1741解:三點公式6.6數(shù)值微分6.6.1基于拉格朗日插值多項式的求導方法【例6.12】給定函數(shù)的下列數(shù)據(jù)表,試利用二點、三點微分公式計算處的一階導數(shù)值。2.52.62.72.82.912.182513.463714.879716.444618.17416.6數(shù)值微分6.6.1基于拉格朗日插值多項式的求導方法解:【例6.12】給定函數(shù)的下列數(shù)據(jù)表,試利用二點、三點微分公式計算處的一階導數(shù)值。2.52.62.72.82.912.182513.463714.879716.444618.17416.6數(shù)值微分6.6.1基于拉格朗日插值多項式的求導方法【例6.13】給定下列數(shù)據(jù)表,試利用三點微分公式計算

處的一階和二階導數(shù)值。解:1.11.21.30.48600.86161.5975

越小一般精度越高.但在實際計算中,數(shù)據(jù)

有誤差,并不是

越小計算效果越好.理由說明如下.設

,并令

,則可得6.6數(shù)值微分6.6.2基于樣條函數(shù)的求導方法由此可見系數(shù)

有正數(shù),也有負數(shù).并且當數(shù)據(jù)

有一定誤差以及

很小時,由于

的表達式中會出現(xiàn)分母為“小數(shù)”

,因此會造成較大的數(shù)值誤差,即算法不是一個穩(wěn)定的算法.因此實際應用中步長

不要取得太小.基于樣條函數(shù)的求導方法我們將用樣條函數(shù)

代替拉格朗日插值多項式

作為函數(shù)

的近似.若

,則有估計其中

.即此時不但

的函數(shù)值很“接近”,它們的導數(shù)值也很“接近”.如何求

?三彎矩方法、三轉角方法。計算三次樣條函數(shù)的三彎矩方法已在第3章介紹,下面我們將推導直接以節(jié)點處的導數(shù)值

作為未知量的三轉角方程組.6.6數(shù)值微分6.6.2基于樣條函數(shù)的求導方法設 .假定樣條函數(shù)

處的導數(shù)值

,則在區(qū)間

上,

為三次多項式.利用Hermite插值公式,可得求出

的值,需要

處的連續(xù)性條件:以及在區(qū)間

端點

處的附加條件.6.6數(shù)值微分6.6.2基于樣條函數(shù)的求導方法1.設

為已知.使用與第3章類似的方法可知

滿足下列方程組6.6數(shù)值微分6.6.2基于樣條函數(shù)的求導方法2.若

已知,則方程組為6.6數(shù)值微分6.6.2基于樣條函數(shù)的求導方法3.若滿足周期性條件:

,則方程組變?yōu)?.6數(shù)值微分6.6.2基于樣條函數(shù)的求導方法AdvancedNumericalComputing現(xiàn)代數(shù)值計算同濟大學數(shù)學科學學院學海無涯,祝你成功!第七章AdvancedNumericalComputing非線性方程求解現(xiàn)代數(shù)值計算同濟大學數(shù)學科學學院目錄/Contents第七章非線性方程求解第一節(jié)非線性方程求解的基本問題第二節(jié)非線性方程基本迭代方法第三節(jié)牛頓法和割線法第四節(jié)非線性方程組簡介第五節(jié)非線性最小二乘問題第六節(jié)大范圍求解方法7.1非線性方程求解的基本問題在科學工程計算中常常遇到非線性方程和方程組的問題,例:高次代數(shù)方程超越方程【定義7.1】求解非線性方程組

若 ,稱

的根或

的零點。【定義7.2】代數(shù)方程:重零點:且非線性方程求根的基本問題:根的存在性,個數(shù)和重數(shù)有根區(qū)間的確定求出足夠精度的近似根【定理7.1】(代數(shù)基本定理)

次多項式函數(shù) ,其中 ,在復數(shù)域中恰有

個根,重根按其重數(shù)計算?!径ɡ?.2】(中值定理)若連續(xù)函數(shù)

在某兩個點

上滿足

,

則在區(qū)間

(或

)上至少存在函數(shù)

的一個零點。7.1非線性方程求解的基本問題【例7.1】考察非線性方程

的根的個數(shù)。7.1非線性方程求解的基本問題7.1非線性方程求解的基本問題【例7.1】考察非線性方程

的根的個數(shù)。7.1非線性方程求解的基本問題【例7.1】考察非線性方程

的根的個數(shù)。7.1非線性方程求解的基本問題【例7.1】考察非線性方程

的根的個數(shù)。7.1非線性方程求解的基本問題【例7.1】考察非線性方程

的根的個數(shù)。【例7.2】求解方程

,

是一給定參數(shù)。7.1非線性方程求解的基本問題【定義7.3】收斂速度設

為第

個迭代點的誤差,若稱

階收斂。線性收斂( )、超線性收斂( )、平方收斂( )【例7.3】考察如下幾個序列的收斂速度:其中,

是Fibonacci數(shù)列,即

,7.1非線性方程求解的基本問題7.1非線性方程求解的基本問題目錄/Contents第七章非線性方程求解第一節(jié)非線性方程求解的基本問題第二節(jié)非線性方程基本迭代方法第三節(jié)牛頓法和割線法第四節(jié)非線性方程組簡介第五節(jié)非線性最小二乘問題第六節(jié)大范圍求解方法7.2.1二分法【定理7.3】(中值定理)若連續(xù)函數(shù)

在某兩個點

上滿足

,則在區(qū)間 (或 )上至少存在函數(shù)

的一個零點。若

連續(xù),

異號,中點 .若

同號,則有有根區(qū)間 ;若

同號,則有有根區(qū)間

;反復上面的過程。幾何意義:7.2.1二分法【算法7.1】(二分法)(1)給定初始區(qū)間 ,滿足 ,以及計算精度 ;(2)令 ;(3)若

或者 ,停止算法;(4)若 ,令

,

否則 ;轉步驟(2).Matlabprogram

(二分法)7.2.1二分法functionx=bisect(f,a,b,tol)

ifnargin<4,tol=1e-12;

end

fa=feval(f,a);fb=feval(f,b);

whileabs(a-b)>tol,

x=(a+b)/2;

fx=feval(f,x);7.2.1二分法

ifsign(fx)==sign(fa),

a=x;fa=fx;

elseif

sign(fx)==sign(fb),b=x;

fb=fx;

elsereturn;

end

end【例7.4】用二分法求解非線性方程 .函數(shù)

滿足 ,方程的近似根為 .7.2.1二分法用erfen.m7.2.1二分法【例7.4】用二分法求解非線性方程 .7.2.1二分法【例7.4】用二分法求解非線性方程 .1.00000-1.000002.000005.000001.00000-1.000001.500000.875001.25000-0.296881.500000.875001.25000-0.296881.375000.224611.31250-0.051511.375000.224611.31250-0.051511.343750.082611.31250-0.051511.328130.014581.32031-0.018711.328130.014581.32422-0.002131.328130.014581.32422-0.002131.326170.006211.32422-0.002131.325200.002047.2.2不動點迭代方法類似于線性方程組的迭代解法,考慮非線性方程等價迭代方程迭代算法【定義7.4】若把函數(shù)

看成是一個映射,求解

滿足

相當于求解

,即求在映射

下不動的點。因此,方程

稱為不動點方程,

稱為函數(shù)

的不動點,該問題也稱為不動點問題?!纠?.5】求解非線性方程

.

取 .

,對應迭代方法 ;

,對應迭代方法 ;

,對應迭代方法

;

,對應迭代方法7.2.2不動點迭代方法7.2.2不動點迭代方法1.5001.5000001.5000001.500000000000002.3751.3572090.8000001.3478260869565212.3961.330861-2.7777781.325200398950911904.0031.3258840.1488971.324718173999051.324939-1.0226731.324717957244791.32476021.8054621.324717957244751.3247260.0021081.32471795724475四個不同的迭代方法(neex5.m)【定理7.4】不動點迭代設一元函數(shù)

在區(qū)間

上一階連續(xù)可導,且(1) 對一切

成立;(2)存在常數(shù)

,

,使得

對一切

成立。則成立如下結論:(a)]對任何

產(chǎn)生的迭代序列

必收斂于

在區(qū)間

上的唯一不動點,即

;(b)]序列

的收斂速度有估計7.2.2不動點迭代方法證:令

,則 .因此,存在

, .

,則由數(shù)學歸納法可得

,7.2.2不動點迭代方法因此7.2.2不動點迭代方法證:全局收斂給出

,使得

。局部收斂性非線性方法的收斂與初始點有關,收斂速度與不動點有關若

(線性收斂),7.2.2不動點迭代方法(1)若

,其中

是不動點,則存在

的某個鄰域 ,使得對于任意

,

有 .(2)原因:無法說明

.幾何含義7.2.2不動點迭代方法【例7.6】求解方程

的根。方程等價于有根區(qū)間 .7.2.2不動點迭代方法7.2.2不動點迭代方法1.7501.750000000000001.750000000000001.750000000000001.7871.770794952435151.756890790371001.763254784462251.7231.758951903005441.760194735991501.763222834536611.8391.765652618481771.761775690112281.763222834351901.6421.761847231831661.762531452898811.76322283435190-27.4621.763222834351901.76322283435190

7.2.3迭代加速假設有不動點迭代,設不動點為,若變化不大,得用兩步迭代近似值得到的某種平均是更好的近似;另外,可以看成是一個新的迭代方法,【例7.7】加速例3.2中的函數(shù)的迭代.導數(shù)變化不大令7.2.3迭代加速7.2.3迭代加速加速方法1.750000000000001.750000000000001.756890790371001.763379158584341.760194735991501.763220601443681.761775690112281.763222866181401.762531452898811.763222833898161.763222834358361.763222834351901.763222834351901.763222834351901.76322834351907.2.3Aitken加速若僅知

而不知其具體數(shù)值假若

變化不大,注意:

都是靠近

的數(shù),,公式出現(xiàn)了分子分母都很靠近

的情況。采用雙精度計算方式。7.2.3迭代加速另外的方式:7.2.3Aitken加速【定理7.5】設不動點迭代

的迭代函數(shù)

的某個鄰域內(nèi)具有二階連續(xù)導數(shù),且

,

,則相應的艾特肯(Aitken)迭代加速是二階收斂的,迭代序列的極限仍為 .7.2.3迭代加速{【例7.8】對例3.3中的迭代函數(shù)做Aitken加速.Aitken加速為該方法每一步的計算量約為原迭代每一步計算量的兩倍.7.2.3迭代加速7.2.3Aitken加速艾特肯加速1.750000000000001.750000000000001.770794952435151.763249280656661.758951903005441.763222834456391.765652618481771.763222834351901.76184723183166NaN1.7632283435190目錄/Contents第七章非線性方程求根第一節(jié)非線性方程求根的基本問題第二節(jié)非線性方程基本迭代方法第三節(jié)牛頓法和割線法第四節(jié)非線性方程組簡介第五節(jié)非線性最小二乘問題第六節(jié)大范圍求解方法7.3牛頓法和割線法考慮非線性方程

,近似根為

,在近似根處的Taylor展開為取其線性部分有Newton迭代格式為注:可看作不動點迭代考慮有若迭代格式

,取

,則其加速為特殊的加速法7.3牛頓法和割線法幾何含義7.3牛頓法和割線法【定理7.6】牛頓法設

是方程

的根,

在某個包含

為內(nèi)點的區(qū)間內(nèi)足夠光滑,且

那么存在

的一個鄰域

,使得對于任意

牛頓法產(chǎn)生的迭代序列以不低于二階的收斂速度收斂于解

.證:牛頓法是對應于函數(shù)

的不動點迭代。若

,則有

.局部收斂7.3牛頓法和割線法證:因此【定理7.6】牛頓法設

是方程

的根,

在某個包含

為內(nèi)點的區(qū)間內(nèi)足夠光滑,且

那么存在

的一個鄰域

,使得對于任意

牛頓法產(chǎn)生的迭代序列以不低于二階的收斂速度收斂于解

.7.3牛頓法和割線法證:

定號,根是唯一的。

定號,可得四種情形:

;

;【定理7.7】給定非線性函數(shù)

,若它在區(qū)間

上二階連續(xù)可微,滿足

,并且對于所有

, .若選定初始點

滿足

,則牛頓迭代法收斂于方程的唯一解 .7.3牛頓法和割線法

;

,函數(shù)單調遞增。由于

,

,因此 .歸納證明:【定理7.7】給定非線性函數(shù)

,若它在區(qū)間

上二階連續(xù)可微,滿足

,并且對于所有

, .若選定初始點

滿足

,則牛頓迭代法收斂于方程的唯一解 .證:

定號,根是唯一的。

定號,可得四種情形:7.3牛頓法和割線法

;

單調下降且有下界

.兩邊取極限。證:【定理7.7】給定非線性函數(shù)

,若它在區(qū)間

上二階連續(xù)可微,滿足

,并且對于所有

, .若選定初始點

滿足

,則牛頓迭代法收斂于方程的唯一解 .7.3牛頓法和割線法【定理7.8】設在區(qū)間

上有二階連續(xù)可微函數(shù)

,

,并且對于所有

,有

,

.若

兩點滿足則對于任何

,牛頓法迭代收斂于方程的唯一根 .【定理7.7】給定非線性函數(shù)

,若它在區(qū)間

上二階連續(xù)可微,滿足

,并且對于所有

, .若選定初始點

滿足

,則牛頓迭代法收斂于方程的唯一解 .7.3牛頓法和割線法計算

相當于求解方程

的正根??勺C【例7.9】設計一個算法計算

,其中 .7.3牛頓法和割線法【例7.9】設計一個算法計算

,其中 .7.3牛頓法和割線法有效位02.00000000000000011.50000000000000121.41666666666667331.41421568627451641.414213562374691251.414213562373091561.4142135623730915

有重根的情形:設

,其中,

且 .單根7.3牛頓法和割線法7.3牛頓法和割線法牛頓下山法的迭代公式參數(shù)

依次取

使

成立.7.3牛頓下山法【算法7.2】牛頓下山法(1)給定初始值

,精度

;(2)若

,近似解為

,停止迭代;(3)令

,

;(4)若

,則, 轉(5);否則,

,重復步驟(4);(5) ,轉(2).7.3牛頓法和割線法幾何含義7.3牛頓下山法7.3牛頓法和割線法function[x,it,convg]=newton(x0,f,g,maxit,tol)%findthezerooffunctionf,withgradientgprovided%Usage:[x,it,convg]=newton(x0,f,g,maxit,tol)

ifnargin<5,

tol=1e-10;

ifnargin<4,maxit=100;

end;end

x=x0;

fx=feval(f,x);

convg=0;

it=1;

while~convg,

it=it+1;

ifnorm(fx)<=tol,

fprintf('NewtonIterationsuccesses!!\n');

convg=1;

return;

end7.3牛頓下山法7.3牛頓法和割線法

d=-feval(g,x)\fx;

lambda=1;

lsdone=0;

while~lsdone,

xn=x+lambda*d;

fn=feval(f,xn);

ifabs(fn)<abs(fx),

lsdone=1;

else

lambda=1/2*lambda;

iflambda<=eps,

convg=-1;

error('linesearchfails!!');

end

end

end7.3牛頓下山法

x=xn;

fx=fn;

ifit>maxit,

convg=0;

error('Newtonmethodneedsmoreiterations.!!');

end

end7.3牛頓法和割線法例:計算方程的根。編寫兩個Matlab文件:functionv=f(x)

v=x.^2+\sin(10*x)-1;和functionv=g(x)

v=2*x+10*\cos(10*x);7.3牛頓下山法調用>>[x,it,convg]=newton(30,'f','g’)NewtonIterationsuccesses!!

x=

-0.412101013664971it=

12convg=

1令代入牛頓法幾何含義:用割線代替牛頓法中的切線7.3牛頓法和割線法【例6.10】用割線法求方程的解。有根區(qū)間:.7.3牛頓法和割線法【例6.10】用割線法求方程的解。有根區(qū)間:.7.3牛頓法和割線法牛頓法割線法01.0000000000000000.00000000000000010.8000000000000001.00000000000000020.7568181818181820.50000000000000030.7548814744397500.69230769230769240.7548776662613990.77560339204174850.7548776662466930.75352325251062460.75484958576524170.75487770485289880.75487766624559390.754877666246693【定理7.9】割線法給定非線性方程 .若函數(shù)

在其解

的某個鄰域內(nèi)二階連續(xù)可導,且

,則存在

的一個鄰域

使得對于任意

,雙點割線法產(chǎn)生的序列收斂于解

,且收斂階為

.單點割線法7.3牛頓法和割線法目錄/Contents第七章非線性方程求根第一節(jié)非線性方程求根的基本問題第二節(jié)非線性方程基本迭代方法第三節(jié)牛頓法和割線法第四節(jié)非線性方程組簡介第五節(jié)非線性最小二乘問題第六節(jié)大范圍求解方法7.4非線性方程組簡介記:

定義:若對于某個

,存在

的一個鄰域

,則稱

的內(nèi)點。稱

點處可微,若【算法7.3】非線性方程組的高斯--賽德爾迭代方法(1)給定

,

,控制精度

;(2)對

,以

為初始值求解如下問題:

并把其解記為

;(3)若

,則迭代收斂,方程組的近似解為

;

否則,

,轉步驟(2).7.4非線性方程組簡介【定理7.10】壓縮映像定理設

在某區(qū)域上滿足

,并且存在壓縮因子

,使得對于任意

成立 .那么下面的結論成立:在

上存在唯一不動點,即

;對于任意的

,不動點迭代

收斂到該唯一不動點

,且收斂速度有估計7.4非線性方程組簡介牛頓法設函數(shù)

連續(xù)可微,有近似值

,向量形式7.4非線性方程組簡介【例7.11】求解非線性方程組不動點迭代高斯---賽德爾迭代7.4非線性方程組簡介牛頓法7.4非線性方程組簡介不動點高斯-賽德爾牛頓法01(0.45969769,0.15852902)(0.45969769,1.44367720)(0.49023685,1.03629258)2(0.01253943,1.44367720)(0.87322296,1.76640321)(0.24236719,0.74784106)3(0.87322296,1.01253910)(1.19436188,1.92998127)(0.26208909,0.74085322)4(0.47029118,1.76640321)(1.35151131,1.97605323)(0.26211952,0.74087174)5(1.19436188,1.45314588)(1.39425486,198445699)(0.26211953,0.74087174)6(0.88262077,1.92998127)(1.40196392,1.98578163)(0.26211953,0.740

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論