科學(xué)計(jì)算方法解讀課件

科學(xué)計(jì)算的背景非線性方程求根算法線性方程組求解直接法線性方程組求解迭代法《科學(xué)計(jì)算方法》科學(xué)計(jì)算的背景《科學(xué)計(jì)算方法》科學(xué)計(jì)算方法與計(jì)算機(jī)有機(jī)結(jié)合構(gòu)造出強(qiáng)有力的工作平臺(tái)數(shù)值分析——研究用計(jì)算機(jī)求解1969年,Apollo

登月計(jì)劃實(shí)現(xiàn)1981年,Columbia號(hào)航天飛機(jī)發(fā)射成功數(shù)學(xué)問題的方法(算法)和理論方程組求解、方程求根、數(shù)據(jù)插值、數(shù)據(jù)擬合、數(shù)值積分、微分方程求解vonNeumann1994年,GPS完全投入使用科學(xué)計(jì)算方法與計(jì)算機(jī)有機(jī)結(jié)合數(shù)值分析——研究用計(jì)算機(jī)求解19例1:圓內(nèi)接正多邊形邊長計(jì)算Pi方法評(píng)價(jià)算法的主要指標(biāo):速度和精度簡單迭代算法:

n

Lerror1923.14145241.4e-0043843.14155763.5e-0053.14159264.6e-010例1:圓內(nèi)接正多邊形邊長計(jì)算Pi方法評(píng)價(jià)算法的主要指標(biāo):速例2.通信衛(wèi)星覆蓋地球面積數(shù)學(xué)模型實(shí)際問題獲取數(shù)據(jù)數(shù)值方法、程序數(shù)據(jù)結(jié)果將地球考慮成一個(gè)球體,設(shè)R為地球半徑,h為衛(wèi)星高度,D為覆蓋面在切痕平面上的投影(積分區(qū)域)例2.通信衛(wèi)星覆蓋地球面積數(shù)學(xué)模型實(shí)際問題獲取數(shù)據(jù)數(shù)值方法

假設(shè)某一數(shù)據(jù)的準(zhǔn)確值為

x*,其近似值為x，則稱

而稱為

x

的相對(duì)誤差誤差的有關(guān)概念

e(x)=x

-x*

為

x的絕對(duì)誤差假設(shè)某一數(shù)據(jù)的準(zhǔn)確值為x*,其近似值而稱為x的相對(duì)如果存在一個(gè)適當(dāng)小的正數(shù)ε

，使得

則稱ε為絕對(duì)誤差限。

稱εr為相對(duì)誤差限。

如果存在一個(gè)適當(dāng)小的正數(shù)εr

，使得

如果存在一個(gè)適當(dāng)小的正數(shù)ε，使得則稱ε為絕對(duì)誤差限。十進(jìn)制浮點(diǎn)數(shù)表示一臺(tái)微機(jī)價(jià)格:￥3999.00,

浮點(diǎn)數(shù)表示:0.3999×104地球半徑:6378137m,(6.378137e+006)

浮點(diǎn)數(shù)表示:0.6378137×107光速:2.99792458e+008

浮點(diǎn)數(shù)表示:0.299792458×109尾數(shù)部階碼部十進(jìn)制浮點(diǎn)數(shù)表示一臺(tái)微機(jī)價(jià)格:￥3999.00,尾數(shù)部階碼部有效數(shù)字概念:取的有限位數(shù)如下(≈3.1415926)取

x1=3，誤差限不超過0.5;取

x2=3.14,誤差限不超過0.005

;若近似值x

的絕對(duì)誤差限是某一位上的半個(gè)單位，該位到x

的第一位非零數(shù)字一共有n

位，則稱近似值x

有n

位有效數(shù)字.

取

x3=3.1416,誤差限不超過0.00005

;有效數(shù)字概念:取x1=3，誤差限不超過0.5;取x2

r

d

例4.水中浮球問題

有一半徑r=10cm的球體,密度

=0.638.球體浸入水中后,浸入水中的深度d是多少？

根據(jù)阿基米德定律,物體排開水的質(zhì)量就是水對(duì)物體的浮力。整理得:d3–3rd2+4r3

=0例4.水中浮球問題根據(jù)阿基米德定律,物體排開水的質(zhì)量由

=0.638,r=10.代入,得d3–30d2+2552=0令

f(x)=x3–30x2+2552,函數(shù)圖形如下所示求解方程

f(x)=0,即是求函數(shù)

f(x)的零點(diǎn).f(x)的零點(diǎn)所在區(qū)間為:[0,20]roots([1-3002552])ans=26.3146

11.8615-8.1761由=0.638,r=10.代入,得d3–30第一步:對(duì)根進(jìn)行隔離,找出隔根區(qū)間,或在隔根區(qū)間內(nèi)確定一個(gè)解的近似值x0;設(shè)f(x)=0的根為

x*,通過迭代計(jì)算,產(chǎn)生序列:

x0

x1

x2

···

xn·········用數(shù)值方法求非線性方程的根,分兩步進(jìn)行:第二步:逐步逼近,利用近似解x0(或隔根區(qū)間)

通過迭代算法得到更精確的近似解.只須第一步:對(duì)根進(jìn)行隔離,找出隔根區(qū)間,或在隔根區(qū)間內(nèi)確定一個(gè)解已知方程

f(x)=0有一隔根區(qū)間[a,b],且f(x)滿足f(a)·f(b)<0,則先將[a,b]等分為兩個(gè)小區(qū)間,判斷根屬于哪個(gè)小區(qū)間,舍去無根區(qū)間保留有根區(qū)間[a1,b1];二分法迭代把區(qū)間[a1,b1]一分為二,進(jìn)一步判斷根屬于哪個(gè)更小的區(qū)間[a2,b2],如此不斷二分以縮小區(qū)間長度.已知方程f(x)=0有一隔根區(qū)間[a,b],且f(x)滿[a,b]x0=0.5(a+b)[a1,b1]=[a,x0][a1,b1]=[x0,b]x1=0.5(a1+b1)f(a1)f(b1)<0已知f(x)=0在[a,b]內(nèi)有一根,且f(a)f(b)<0(1)計(jì)算:yaf(a),x00.5(a+b),y0f(x0)

判斷,若y0=0,則x0是根,否則轉(zhuǎn)下一步;(2)判斷,若y0·ya<0,則a1a,b1

x0

否則

a1x0,b1b,yay0[a,b]x0=0.5(a+b)[a1,b1]=[a,x0二分法迭代將得到一系列隔根區(qū)間

定理2.2

設(shè)x*是

f(x)=0在[a,b]內(nèi)的唯一根,且

f(a)·f(b)<0,則二分計(jì)算過程中,各區(qū)間的中點(diǎn)數(shù)列性質(zhì):1.f(an)·f(bn)<0;2.bn–

an=(b–a)/2n滿足:|xn–x*|≤(b–a)/2n+1思考:

|xn+1–xn

|=？二分法迭代將得到一系列隔根區(qū)間定理2.2設(shè)x*是f(構(gòu)造有效的迭代格式選取合適的迭代初值對(duì)迭代格式進(jìn)行收斂性分析例5.圓周率計(jì)算初值:

x0=1(n=1,2,3,······)迭代格式:將一個(gè)計(jì)算過程反復(fù)進(jìn)行稱為迭代,迭代法是一類常見常用的計(jì)算技術(shù)構(gòu)造有效的迭代格式例5.圓周率計(jì)算初值:x0=1(n=初值:x1=1.5迭代格式:xn+1=0.5(xn+2/xn)(n=1,2,·····)例6.平方根算法求xn

Error1.4166666666666672.45e-0031.4142156862745102.12e-0061.4142135623746901.59e-0121.4142135623730952.22e-0161.4142135623730952.22e-016初值:x1=1.5例6.平方根算法求設(shè)

x*是方程

f(x)=0的根,x0是x*的近似值.在

x0附近,對(duì)函數(shù)做局部線性化x1比x0更接近于x*x0x1x*f(x)=0設(shè)x*是方程f(x)=0的根,x0是x*的近似(n=0,1,2,·····)牛頓迭代格式給定初值

x0,迭代產(chǎn)生數(shù)列x0,x1,x2,·········,

xn,

·······應(yīng)用——求正數(shù)平方根算法設(shè)C>0,x2–C=0令

f(x)=x2–C,則(n=0,1,2,·····)牛頓迭代格式給定初值由此可知,平方根迭代具有

2階收斂速度

由此可知,平方根迭代具有2階收斂速度f’<0,f”>0f’>0,f”>0f’>0,f”<0f’<0,f”<0牛頓迭代法收斂的四種情況f’<0,f”>0f’>0,f”>0f’>0,例7.牛頓迭代法的收斂域問題:

用牛頓迭代法求解復(fù)數(shù)方程

z3–1=0，該方程在復(fù)平面上三個(gè)根分別是z1=1選擇中心位于坐標(biāo)原點(diǎn)，邊長為2的正方形內(nèi)的任意點(diǎn)作初始值，進(jìn)行迭代，把收斂到三個(gè)根的初值分為三類，并分別標(biāo)上不同顏色（例如紅、黃、藍(lán)）。對(duì)充分多的初始點(diǎn)進(jìn)行實(shí)驗(yàn)，繪出牛頓迭代法對(duì)該方程的收斂域彩色圖。

例7.牛頓迭代法的收斂域問題:z1=1選擇中心位于坐標(biāo)收斂到z1的牛頓迭代初值點(diǎn)集合收斂到z2的牛頓迭代初值點(diǎn)集合收斂到z3的牛頓迭代初值點(diǎn)集合收斂到z1的牛頓迭代初值點(diǎn)集合收斂到z2的牛頓迭代初在復(fù)平面內(nèi),有一些例外點(diǎn)是牛頓迭代不收斂的初值點(diǎn).這些例外點(diǎn)構(gòu)成了茹利亞集(為紀(jì)念法國女?dāng)?shù)學(xué)家Julia).在復(fù)平面內(nèi),有一些例外點(diǎn)是牛頓迭代不收斂的初值點(diǎn).這些例外線性方程組的矩陣形式a11x1+a12x2+····+a1nxn=b1a21x1+a22x2+····+a2nxn=b2·········································an1x1+an2x2+····+annxn=bnAX=b(i=1,2,···,n)線性方程組求解:1.直接方法;2.基本迭代法;3.子空間方法X

?

b線性方程組的矩陣形式a11x1+a12x2+····+a例8x4=2,x3=4,x2=–1,x1=3例8x4=2,x3=4,x2=–1,x1=3解上三角方程組計(jì)算：xn

=bn

/ann

(a11…ann≠0)xk=[bk－(ak,k+1xk+1+…+ak

n)]/akk

(k=n－1,···,1)除法:n次;乘法:n(n-1)/2次,乘、除法運(yùn)算共n(n+1)/2次,簡記為

O(n2)解上三角方程組計(jì)算：xn=bn/ann(a11…an消元過程(化一般方程組為上三角方程組)消元過程(化一般方程組為上三角方程組)增廣矩陣

計(jì)算:[m21

m31

m41]T=[a21

a31

a41]T/a11

用–m21乘矩陣第一行加到矩陣第二行;用–m31乘矩陣第一行加到矩陣第三行;用–m41乘矩陣第一行加到矩陣第四行;增廣矩陣計(jì)算:[m21m31m41]T=[a實(shí)現(xiàn)第一輪消元實(shí)現(xiàn)第二輪消元、第三輪消元·········消元過程乘除法次數(shù):O(n3)實(shí)現(xiàn)第一輪消元實(shí)現(xiàn)第二輪消元、第三輪消元·········消例9.特點(diǎn):系數(shù)矩陣主對(duì)角元均不為零計(jì)算格式

X(1)=BX(0)+f取

X(0)=例9.特點(diǎn):系數(shù)矩陣主對(duì)角元均不為零計(jì)算格式X(1)=

X*1.00001.00001.0000

X(0)000

X(1)

0.77780.80000.8667

X(2)0.96300.96440.9778

X(3)0.99290.99350.9952計(jì)算格式:X(k+1)=BX(k)+fX(0),X(1),···X(n)·····

X(4)········0.99870.99880.9991X(n+1)≈

BX(n)+fX*X(0)X(1)X(2)X雅可比迭代法(i=1,2,…n;k=1,2,……)取初始向量X(0)=[x1(0)x2(0)···xn(0)]T,迭代計(jì)算(i=1,2,…,n)雅可比迭代法(i=1,2,…n;k=1,2,……)取初雅可比迭代法的矩陣表示將方程組AX=b

的系數(shù)矩陣

A

分解

A=D–U–LAX=b=>DX(k+1)=(U+L)X(k)+bX(k+1)=D-1(U+L)X(k)+D-1b記BJ=D-1(U+L)X(k+1)=BJX(k)+fJ雅可比迭代法的矩陣表示將方程組AX=b的系數(shù)矩陣A雅可比迭代矩陣雅可比迭代矩陣?yán)?0誤差限5e-0045e-0055e-0065e-007賽德爾迭代次數(shù)5567雅可比迭代次數(shù)67910高斯-賽德爾迭代法例10誤差限5e-0045e-0055e-0065e-007高斯-賽德爾迭代法矩陣表示AX=bA=M–NMX(k+1)=NX(k)+b高斯-賽德爾迭代法矩陣表示AX=bA=M–(i=1,2,…,n)高斯-賽德爾迭代法計(jì)算格式(i=1,2,…n;k=1,2,……)取初始向量x(0)=[x1(0)x2(0)···xn(0)]T,

做迭代計(jì)算(i=1,2,…,n)高斯-賽德爾迭代法計(jì)算格式(i=AX=b(M–N)X=b記

(k)=X(k)–X*(k=0,1,2,3,······)則有

(k+1)=B(k)(k=0,1,2,3,······)計(jì)算格式:X(k+1)=BX(k)+f(B=M-1N)

X(k+1)–X*=B(X(k)–X*)設(shè)方程組的精確解為X*,則有X*=BX*+fAX=b(M–N)X=b記平面點(diǎn)列:Xk∈Rn:X1,X2,···,Xk,···················平面點(diǎn)列:Xk∈Rn:X1,X2,···,證:由(k)=B(k-1),得

||(k)||≤||B||||(k-1)||

(k=1,2,3,······)所以命題

若||B||<1,則迭代法

X(k+1)=BX(k)+f

收斂||(k)||≤||B||k||(0)||

||B||<1證:由(k)=B(k-1),得所以命題若|定理4.3

若Ax=b的系數(shù)矩陣A是嚴(yán)格對(duì)角占優(yōu)矩陣,則Jacobi迭代和Seidel迭代均收斂定理4.2:設(shè)X*為方程組

AX=b的解若||B||<1,則對(duì)迭代格式

X(k+1)=BX(k)+f

有(1)(2)定理4.3若Ax=b的系數(shù)矩陣A是嚴(yán)格對(duì)角占優(yōu)矩陣,則Ja例11.平面溫度場問題:令

h=1/(n+1),xj=jh,yj=jh(i,j=0,1,···,n+1)記

ui,j=u(xi,yj),(i,j=0,1,···,n+1)迭代格式(i,j=1,···,n)u0,j=0,ui,0=0,ui,n+1

=0例11.平面溫度場問題:令h=1/(n+1),結(jié)點(diǎn)數(shù)n2102202

402迭代次數(shù)

1826062077CPU時(shí)間(s)0.974.32858.531誤差

0.00236.4274e-41.6814e-4高斯-賽德爾迭代法實(shí)驗(yàn)(誤差限10-8):結(jié)點(diǎn)數(shù)n2102(i=1,2,···,n;k=1,2,3,··········)迭代格式超松馳迭代方法SOR(successiveoverrelaxation)Prof.DavidM.Young1954美國數(shù)學(xué)科學(xué)學(xué)報(bào)(i=1,2,···,n;k=1,2,3,···Seidel迭代格式SOR迭代格式最佳松馳因子平面溫度場的計(jì)算問題Seidel迭代格式SOR迭代格式最佳松馳因子平面溫度場的計(jì)結(jié)點(diǎn)數(shù)n2102202

402迭代次數(shù)

1826062077CPU時(shí)間(s)0.974.32858.531誤差

0.00236.4274e-41.6814e-4高斯-賽德爾迭代(誤差限10-8):SOR迭代實(shí)驗(yàn)(誤差限10-8):結(jié)點(diǎn)數(shù)n2102202

402迭代次數(shù)

4074137CPU時(shí)間(s)0.110.65604.9530誤差

0.00236.4306e-41.6944e-4結(jié)點(diǎn)數(shù)n2102人有了知識(shí)，就會(huì)具備各種分析能力，明辨是非的能力。所以我們要勤懇讀書，廣泛閱讀，古人說“書中自有黃金屋。”通過閱讀科技書籍，我們能豐富知識(shí)，培養(yǎng)邏輯思維能力；通過閱讀文學(xué)作品，我們能提高文學(xué)鑒賞水平，培養(yǎng)文學(xué)情趣；通過閱讀報(bào)刊，我們能增長見識(shí)，擴(kuò)大自己的知識(shí)面。有許多書籍還能培養(yǎng)我們的道德情操，給我們巨大的精神力量，鼓舞我們前進(jìn)。人有了知識(shí)，就會(huì)具備各種分析能力，科學(xué)計(jì)算方法解讀課件科學(xué)計(jì)算的背景非線性方程求根算法線性方程組求解直接法線性方程組求解迭代法《科學(xué)計(jì)算方法》科學(xué)計(jì)算的背景《科學(xué)計(jì)算方法》科學(xué)計(jì)算方法與計(jì)算機(jī)有機(jī)結(jié)合構(gòu)造出強(qiáng)有力的工作平臺(tái)數(shù)值分析——研究用計(jì)算機(jī)求解1969年,Apollo

登月計(jì)劃實(shí)現(xiàn)1981年,Columbia號(hào)航天飛機(jī)發(fā)射成功數(shù)學(xué)問題的方法(算法)和理論方程組求解、方程求根、數(shù)據(jù)插值、數(shù)據(jù)擬合、數(shù)值積分、微分方程求解vonNeumann1994年,GPS完全投入使用科學(xué)計(jì)算方法與計(jì)算機(jī)有機(jī)結(jié)合數(shù)值分析——研究用計(jì)算機(jī)求解19例1:圓內(nèi)接正多邊形邊長計(jì)算Pi方法評(píng)價(jià)算法的主要指標(biāo):速度和精度簡單迭代算法:

n

Lerror1923.14145241.4e-0043843.14155763.5e-0053.14159264.6e-010例1:圓內(nèi)接正多邊形邊長計(jì)算Pi方法評(píng)價(jià)算法的主要指標(biāo):速例2.通信衛(wèi)星覆蓋地球面積數(shù)學(xué)模型實(shí)際問題獲取數(shù)據(jù)數(shù)值方法、程序數(shù)據(jù)結(jié)果將地球考慮成一個(gè)球體,設(shè)R為地球半徑,h為衛(wèi)星高度,D為覆蓋面在切痕平面上的投影(積分區(qū)域)例2.通信衛(wèi)星覆蓋地球面積數(shù)學(xué)模型實(shí)際問題獲取數(shù)據(jù)數(shù)值方法

假設(shè)某一數(shù)據(jù)的準(zhǔn)確值為

x*,其近似值為x，則稱

而稱為

x

的相對(duì)誤差誤差的有關(guān)概念

e(x)=x

-x*

為

x的絕對(duì)誤差假設(shè)某一數(shù)據(jù)的準(zhǔn)確值為x*,其近似值而稱為x的相對(duì)如果存在一個(gè)適當(dāng)小的正數(shù)ε

，使得

則稱ε為絕對(duì)誤差限。

稱εr為相對(duì)誤差限。

如果存在一個(gè)適當(dāng)小的正數(shù)εr

，使得

如果存在一個(gè)適當(dāng)小的正數(shù)ε，使得則稱ε為絕對(duì)誤差限。十進(jìn)制浮點(diǎn)數(shù)表示一臺(tái)微機(jī)價(jià)格:￥3999.00,

浮點(diǎn)數(shù)表示:0.3999×104地球半徑:6378137m,(6.378137e+006)

浮點(diǎn)數(shù)表示:0.6378137×107光速:2.99792458e+008

浮點(diǎn)數(shù)表示:0.299792458×109尾數(shù)部階碼部十進(jìn)制浮點(diǎn)數(shù)表示一臺(tái)微機(jī)價(jià)格:￥3999.00,尾數(shù)部階碼部有效數(shù)字概念:取的有限位數(shù)如下(≈3.1415926)取

x1=3，誤差限不超過0.5;取

x2=3.14,誤差限不超過0.005

;若近似值x

的絕對(duì)誤差限是某一位上的半個(gè)單位，該位到x

的第一位非零數(shù)字一共有n

位，則稱近似值x

有n

位有效數(shù)字.

取

x3=3.1416,誤差限不超過0.00005

;有效數(shù)字概念:取x1=3，誤差限不超過0.5;取x2

r

d

例4.水中浮球問題

有一半徑r=10cm的球體,密度

=0.638.球體浸入水中后,浸入水中的深度d是多少？

根據(jù)阿基米德定律,物體排開水的質(zhì)量就是水對(duì)物體的浮力。整理得:d3–3rd2+4r3

=0例4.水中浮球問題根據(jù)阿基米德定律,物體排開水的質(zhì)量由

=0.638,r=10.代入,得d3–30d2+2552=0令

f(x)=x3–30x2+2552,函數(shù)圖形如下所示求解方程

f(x)=0,即是求函數(shù)

f(x)的零點(diǎn).f(x)的零點(diǎn)所在區(qū)間為:[0,20]roots([1-3002552])ans=26.3146

11.8615-8.1761由=0.638,r=10.代入,得d3–30第一步:對(duì)根進(jìn)行隔離,找出隔根區(qū)間,或在隔根區(qū)間內(nèi)確定一個(gè)解的近似值x0;設(shè)f(x)=0的根為

x*,通過迭代計(jì)算,產(chǎn)生序列:

x0

x1

x2

···

xn·········用數(shù)值方法求非線性方程的根,分兩步進(jìn)行:第二步:逐步逼近,利用近似解x0(或隔根區(qū)間)

通過迭代算法得到更精確的近似解.只須第一步:對(duì)根進(jìn)行隔離,找出隔根區(qū)間,或在隔根區(qū)間內(nèi)確定一個(gè)解已知方程

f(x)=0有一隔根區(qū)間[a,b],且f(x)滿足f(a)·f(b)<0,則先將[a,b]等分為兩個(gè)小區(qū)間,判斷根屬于哪個(gè)小區(qū)間,舍去無根區(qū)間保留有根區(qū)間[a1,b1];二分法迭代把區(qū)間[a1,b1]一分為二,進(jìn)一步判斷根屬于哪個(gè)更小的區(qū)間[a2,b2],如此不斷二分以縮小區(qū)間長度.已知方程f(x)=0有一隔根區(qū)間[a,b],且f(x)滿[a,b]x0=0.5(a+b)[a1,b1]=[a,x0][a1,b1]=[x0,b]x1=0.5(a1+b1)f(a1)f(b1)<0已知f(x)=0在[a,b]內(nèi)有一根,且f(a)f(b)<0(1)計(jì)算:yaf(a),x00.5(a+b),y0f(x0)

判斷,若y0=0,則x0是根,否則轉(zhuǎn)下一步;(2)判斷,若y0·ya<0,則a1a,b1

x0

否則

a1x0,b1b,yay0[a,b]x0=0.5(a+b)[a1,b1]=[a,x0二分法迭代將得到一系列隔根區(qū)間

定理2.2

設(shè)x*是

f(x)=0在[a,b]內(nèi)的唯一根,且

f(a)·f(b)<0,則二分計(jì)算過程中,各區(qū)間的中點(diǎn)數(shù)列性質(zhì):1.f(an)·f(bn)<0;2.bn–

an=(b–a)/2n滿足:|xn–x*|≤(b–a)/2n+1思考:

|xn+1–xn

|=？二分法迭代將得到一系列隔根區(qū)間定理2.2設(shè)x*是f(構(gòu)造有效的迭代格式選取合適的迭代初值對(duì)迭代格式進(jìn)行收斂性分析例5.圓周率計(jì)算初值:

x0=1(n=1,2,3,······)迭代格式:將一個(gè)計(jì)算過程反復(fù)進(jìn)行稱為迭代,迭代法是一類常見常用的計(jì)算技術(shù)構(gòu)造有效的迭代格式例5.圓周率計(jì)算初值:x0=1(n=初值:x1=1.5迭代格式:xn+1=0.5(xn+2/xn)(n=1,2,·····)例6.平方根算法求xn

Error1.4166666666666672.45e-0031.4142156862745102.12e-0061.4142135623746901.59e-0121.4142135623730952.22e-0161.4142135623730952.22e-016初值:x1=1.5例6.平方根算法求設(shè)

x*是方程

f(x)=0的根,x0是x*的近似值.在

x0附近,對(duì)函數(shù)做局部線性化x1比x0更接近于x*x0x1x*f(x)=0設(shè)x*是方程f(x)=0的根,x0是x*的近似(n=0,1,2,·····)牛頓迭代格式給定初值

x0,迭代產(chǎn)生數(shù)列x0,x1,x2,·········,

xn,

·······應(yīng)用——求正數(shù)平方根算法設(shè)C>0,x2–C=0令

f(x)=x2–C,則(n=0,1,2,·····)牛頓迭代格式給定初值由此可知,平方根迭代具有

2階收斂速度

由此可知,平方根迭代具有2階收斂速度f’<0,f”>0f’>0,f”>0f’>0,f”<0f’<0,f”<0牛頓迭代法收斂的四種情況f’<0,f”>0f’>0,f”>0f’>0,例7.牛頓迭代法的收斂域問題:

用牛頓迭代法求解復(fù)數(shù)方程

z3–1=0，該方程在復(fù)平面上三個(gè)根分別是z1=1選擇中心位于坐標(biāo)原點(diǎn)，邊長為2的正方形內(nèi)的任意點(diǎn)作初始值，進(jìn)行迭代，把收斂到三個(gè)根的初值分為三類，并分別標(biāo)上不同顏色（例如紅、黃、藍(lán)）。對(duì)充分多的初始點(diǎn)進(jìn)行實(shí)驗(yàn)，繪出牛頓迭代法對(duì)該方程的收斂域彩色圖。

例7.牛頓迭代法的收斂域問題:z1=1選擇中心位于坐標(biāo)收斂到z1的牛頓迭代初值點(diǎn)集合收斂到z2的牛頓迭代初值點(diǎn)集合收斂到z3的牛頓迭代初值點(diǎn)集合收斂到z1的牛頓迭代初值點(diǎn)集合收斂到z2的牛頓迭代初在復(fù)平面內(nèi),有一些例外點(diǎn)是牛頓迭代不收斂的初值點(diǎn).這些例外點(diǎn)構(gòu)成了茹利亞集(為紀(jì)念法國女?dāng)?shù)學(xué)家Julia).在復(fù)平面內(nèi),有一些例外點(diǎn)是牛頓迭代不收斂的初值點(diǎn).這些例外線性方程組的矩陣形式a11x1+a12x2+····+a1nxn=b1a21x1+a22x2+····+a2nxn=b2·········································an1x1+an2x2+····+annxn=bnAX=b(i=1,2,···,n)線性方程組求解:1.直接方法;2.基本迭代法;3.子空間方法X

?

b線性方程組的矩陣形式a11x1+a12x2+····+a例8x4=2,x3=4,x2=–1,x1=3例8x4=2,x3=4,x2=–1,x1=3解上三角方程組計(jì)算：xn

=bn

/ann

(a11…ann≠0)xk=[bk－(ak,k+1xk+1+…+ak

n)]/akk

(k=n－1,···,1)除法:n次;乘法:n(n-1)/2次,乘、除法運(yùn)算共n(n+1)/2次,簡記為

O(n2)解上三角方程組計(jì)算：xn=bn/ann(a11…an消元過程(化一般方程組為上三角方程組)消元過程(化一般方程組為上三角方程組)增廣矩陣

計(jì)算:[m21

m31

m41]T=[a21

a31

a41]T/a11

用–m21乘矩陣第一行加到矩陣第二行;用–m31乘矩陣第一行加到矩陣第三行;用–m41乘矩陣第一行加到矩陣第四行;增廣矩陣計(jì)算:[m21m31m41]T=[a實(shí)現(xiàn)第一輪消元實(shí)現(xiàn)第二輪消元、第三輪消元·········消元過程乘除法次數(shù):O(n3)實(shí)現(xiàn)第一輪消元實(shí)現(xiàn)第二輪消元、第三輪消元·········消例9.特點(diǎn):系數(shù)矩陣主對(duì)角元均不為零計(jì)算格式

X(1)=BX(0)+f取

X(0)=例9.特點(diǎn):系數(shù)矩陣主對(duì)角元均不為零計(jì)算格式X(1)=

X*1.00001.00001.0000

X(0)000

X(1)

0.77780.80000.8667

X(2)0.96300.96440.9778

X(3)0.99290.99350.9952計(jì)算格式:X(k+1)=BX(k)+fX(0),X(1),···X(n)·····

X(4)········0.99870.99880.9991X(n+1)≈

BX(n)+fX*X(0)X(1)X(2)X雅可比迭代法(i=1,2,…n;k=1,2,……)取初始向量X(0)=[x1(0)x2(0)···xn(0)]T,迭代計(jì)算(i=1,2,…,n)雅可比迭代法(i=1,2,…n;k=1,2,……)取初雅可比迭代法的矩陣表示將方程組AX=b

的系數(shù)矩陣

A

分解

A=D–U–LAX=b=>DX(k+1)=(U+L)X(k)+bX(k+1)=D-1(U+L)X(k)+D-1b記BJ=D-1(U+L)X(k+1)=BJX(k)+fJ雅可比迭代法的矩陣表示將方程組AX=b的系數(shù)矩陣A雅可比迭代矩陣雅可比迭代矩陣?yán)?0誤差限5e-0045e-0055e-0065e-007賽德爾迭代次數(shù)5567雅可比迭代次數(shù)67910高斯-賽德爾迭代法例10誤差限5e-0045e-0055e-0065e-007高斯-賽德爾迭代法矩陣表示AX=bA=M–NMX(k+1)=NX(k)+b高斯-賽德爾迭代法矩陣表示AX=bA=M–(i=1,2,…,n)高斯-賽德爾迭代法計(jì)算格式(i=1,2,…n;k=1,2,……)取初始向量x(0)=[x1(0)x2(0)···xn(0)]T,

做迭代計(jì)算(i=1,2,…,n)高斯-賽德爾迭代法計(jì)算格式(i=AX=b(M–N)X=b記

(k)=X(k)–X*(k=0,1,2,3,······)則有

(k+1)=B(k)(k=0,1,2,3,······)計(jì)算格式:X(k+1)=BX(k)+f(B=M-1N)

X(k+1)–X*=B(X(k)–X*)設(shè)方程組的精確解為X*,則有X*=BX*+fAX=b(M–N)X=b記平面點(diǎn)列:Xk∈Rn:X1,X2,···,Xk,···················平面點(diǎn)列:Xk∈Rn:X1,X2,···,證:由(k)=B(k-1),得

||(k)||≤||B||||(k-1)||

(k=1,2,3,······)所以命題

若||B||<1,則迭代法

X(k+1)=BX(k)+f

收斂||(k)||≤||B||k||(0)||