數(shù)值分析典型例題與習(xí)題

1、1/36數(shù)值分析典型例題典型例題 I一、二章內(nèi)容提要一、二章內(nèi)容提要典型例題分析典型例題分析例題與練習(xí)題例題與練習(xí)題實(shí)驗(yàn)題介紹實(shí)驗(yàn)題介紹2/36化大為小化大為小 化繁為簡(jiǎn)化繁為簡(jiǎn) 化難為易化難為易 核心的概念核心的概念 誤差誤差算法的構(gòu)造與分析算法的構(gòu)造與分析 收斂性收斂性 穩(wěn)定性穩(wěn)定性 復(fù)雜度復(fù)雜度( (時(shí)間與空間時(shí)間與空間) )等等3/36有效數(shù)字概念有效數(shù)字概念若近似值若近似值 x 的絕對(duì)誤差限是某一位上的半個(gè)的絕對(duì)誤差限是某一位上的半個(gè)單位單位, ,該位到該位到 x 的第一位非零數(shù)字一共有的第一位非零數(shù)字一共有 n 位位, ,則稱(chēng)近似值則稱(chēng)近似值 x 有有 n 位有效數(shù)字位有效數(shù)字。*

2、.*x 從左向右看第從左向右看第一個(gè)非零數(shù)一個(gè)非零數(shù)誤差限不超過(guò)該誤差限不超過(guò)該位的半個(gè)單位位的半個(gè)單位n位有效數(shù)字位有效數(shù)字4/36nraxe 1051)(如果如果x具有具有n位有效數(shù)字位有效數(shù)字, 則相對(duì)誤差滿(mǎn)足則相對(duì)誤差滿(mǎn)足:mnaaax10021 .nmxxxe 1021| )(|其絕對(duì)誤差滿(mǎn)足其絕對(duì)誤差滿(mǎn)足:如果一個(gè)規(guī)格化浮點(diǎn)數(shù)如果一個(gè)規(guī)格化浮點(diǎn)數(shù)則稱(chēng)近似數(shù)則稱(chēng)近似數(shù)x具有具有n位有效數(shù)字。位有效數(shù)字。5/36*lim()nnxx 0101()()nnxxxxx 迭代法思想迭代法思想:收斂性收斂性 收斂速度收斂速度|( )| 1x Iterate:To say or do again

3、 or againandagain(1)( )( *)( *)( *)0 ( *)0rrxxxx 6/36例例1. .經(jīng)過(guò)四舍五入得出經(jīng)過(guò)四舍五入得出x1 1=6.1025=6.1025和和x2 2=80.100,=80.100,試問(wèn)它們分別具有幾位有效數(shù)字試問(wèn)它們分別具有幾位有效數(shù)字? ?解解： *4112|*|10 xx *3122|*|10 xx 7/36例例2. .已知近似數(shù)已知近似數(shù)x有兩位有效數(shù)字有兩位有效數(shù)字, ,試求其相對(duì)試求其相對(duì)誤差限。誤差限。解解：| er(x)|1000時(shí)時(shí), Sn有三位有效數(shù)。有三位有效數(shù)。14/362arctan( )11dxdxx 201arcta

4、n( )arctan(0)arctan( )1xdxxxx 2311( 11)1aaaaa 2460(1)darctan( )xaaaax 3571arctan( )357xxxx15/3610ie 16/36例例10.在計(jì)算機(jī)上對(duì)調(diào)和級(jí)數(shù)逐項(xiàng)求和計(jì)算在計(jì)算機(jī)上對(duì)調(diào)和級(jí)數(shù)逐項(xiàng)求和計(jì)算 nknkS11當(dāng)當(dāng) n很大時(shí)，很大時(shí)，Sn 將不隨將不隨n 的增加而增加。試的增加而增加。試分析原因分析原因。 17/36例例11. 證明方程證明方程1-x-sinx=0在區(qū)間在區(qū)間0,1上有上有一根一根, 使用二分法求誤差不大于使用二分法求誤差不大于0.5*10-4的的根需要二分多少次？根需要二分多少次？提示提

5、示: f(0)=1, f(1)=-sin10。且。且f(x)=-1-cosx在區(qū)間在區(qū)間(0,1嚴(yán)格單調(diào)遞減。嚴(yán)格單調(diào)遞減。411011022n 18/36 例例12. 構(gòu)造求構(gòu)造求ex+10 x-2=0根的迭代法。根的迭代法。提示提示:(2e )( )10 xx ( )10 xex 故迭代法算法一階收斂。故迭代法算法一階收斂。19/36 例例13. 應(yīng)用牛頓迭代法于方程應(yīng)用牛頓迭代法于方程x3 a=0,導(dǎo)出求立方根的迭代公式導(dǎo)出求立方根的迭代公式,并討論其收斂階。并討論其收斂階。解：令解：令 f(x) = x3 a，則牛頓迭代公式則牛頓迭代公式 22313323nnnnnnxaxxaxxx

6、2332)(xaxx 33232)(xax 42)(xax *()0()0 xx 且且故立方根迭代算法二階收斂故立方根迭代算法二階收斂20/36例例14. 設(shè)設(shè)a 為正實(shí)數(shù)為正實(shí)數(shù),試建立求試建立求1/a 的牛頓迭代公的牛頓迭代公式式,要求在迭代公式中不含有除法運(yùn)算要求在迭代公式中不含有除法運(yùn)算,并考慮并考慮迭代公式的收斂。迭代公式的收斂。 xn+1 = xn(2 axn)，(n=0，1，2 ) kaxaxk20)1(1 )1(1 120kaxaxk 所以所以,當(dāng)當(dāng)| 1 ax0| 0,迭代格式迭代格式212(3 )3nnnnxxCxxC *xC 是是計(jì)計(jì)算算的的三三階階方方法法。22/36例

7、例16. *()1()()0 xp xfx 解解:2( )( ) ( )( )( ),( )( ),( )0( )xxp x f xq x fxp xq xf xx 設(shè)設(shè)試試確確定定函函數(shù)數(shù)和和使使求求解解根根的的迭迭代代格格式式至至少少三三階階收收斂斂。2( )1( ) ( )( )( )( )( )2 ( ) ( )( )xp x f xp x fxq x fxq x f x fx 2( )( ) ( )( )( )( )( )( )( ) ( )( )2 ( ) ( )( )2 ( ) ( )( ) 2 ( )( )( )2 ( ) ( )( )xpx f xp x fxp x fxp

8、x fxqx fxq x f x fxq x f x fxq x fx fxq x f x fx *2()2()()()()2 ()()0 xp xfxp xfxq xfx ( )1/( )p xfx 3( )( )2( )fxq xfx 23/36Ex2. 若若 x*是是f(x)=0的的m重根重根,試證明修正的牛頓試證明修正的牛頓迭代法迭代法1()()nnnnf xxxmfx 至少為二階收斂至少為二階收斂 。 1/1/1( )( )( )1/( )( )mmu xf xu xm f xfx 且且f(x)1/m或或f(x)/f(x)單根單根1/1/1 ( )(x)( )1/ ( )( )( )

9、mmf xfxxxmm f xfxfx 24/36Ex3 對(duì)于復(fù)變量對(duì)于復(fù)變量 z=x+iy 的復(fù)值函數(shù)的復(fù)值函數(shù)f(z) 應(yīng)用牛頓迭代公式應(yīng)用牛頓迭代公式 )()(1nnnnzfzfzz 時(shí)為避開(kāi)復(fù)數(shù)運(yùn)算時(shí)為避開(kāi)復(fù)數(shù)運(yùn)算,令令zn=xn+iynf(zn)=An+iBn，f(zn)=Cn+iDn 證明證明 221nnnnnnnnDCDBCAxx 221nnnnnnnnDCCBDAyy 25/36例例17. 提示提示: 取初值取初值x1=21/2,222lim=2nnnxx 給給出出求求的的迭迭代代格格式式, ,并并證證明明。12nnxx 迭迭代代格格式式考慮序列單調(diào)有界考慮序列單調(diào)有界,則該序

10、列必有極限。則該序列必有極限。26/36*2.5 ( ), ( )( )1, xxxxx 定定理理設(shè)設(shè)為為的的不不動(dòng)動(dòng)點(diǎn)點(diǎn)在在的的某某鄰鄰域域連連續(xù)續(xù)且且則則迭迭代代法法局局部部收收斂斂。例例18.:( )x 提提示示 因因?yàn)闉檫B連續(xù)續(xù), , 由由局局部部保保號(hào)號(hào)性性知知存存在在一一個(gè)個(gè)鄰鄰域域|( )|1,xL 有有且且有有|( )|1,xL 有有且且有有*| ( )| ( )()|0, 均收斂于均收斂于21/2。21212(2)2(2)nnnnxxxx 29/36牛頓迭代法的收斂域問(wèn)題牛頓迭代法的收斂域問(wèn)題: : 用牛頓迭代法求解方程用牛頓迭代法求解方程 zd 1 = 0的復(fù)根。例如的復(fù)根

11、。例如d=3時(shí)時(shí), 方程在復(fù)平面上三個(gè)根分別是方程在復(fù)平面上三個(gè)根分別是iz23212 iz23213 z1 = 1選擇中心位于坐標(biāo)原點(diǎn)，邊長(zhǎng)選擇中心位于坐標(biāo)原點(diǎn)，邊長(zhǎng)為為2 2的正方形內(nèi)的任意點(diǎn)作初始的正方形內(nèi)的任意點(diǎn)作初始值，進(jìn)行迭代，把收斂到三個(gè)值，進(jìn)行迭代，把收斂到三個(gè)根的初值分為三類(lèi)，并分別標(biāo)根的初值分為三類(lèi)，并分別標(biāo)上不同顏色上不同顏色( (例如紅、綠和藍(lán)例如紅、綠和藍(lán)) )。對(duì)充分多的初始點(diǎn)進(jìn)行實(shí)驗(yàn)，對(duì)充分多的初始點(diǎn)進(jìn)行實(shí)驗(yàn)，繪出牛頓迭代法對(duì)該方程的收繪出牛頓迭代法對(duì)該方程的收斂域彩色圖斂域彩色圖。 30/3631/3632/3633/3634/36 % Perform Newt

12、on iterations for k=1:maxIter; Z=Z-(f(Z,d)./fprime(Z,d); endfunction y=f(x,d); y=(x.d)-1;end function y=fprime(x,d); y=d*(x.(d-1);end代碼片段1:35/36 % Find d roots of unity, and the mask for j=1:d root=exp(2*pi*i/d)j; % the jth root Mj=abs(Z-root); % distance % Each root gets a unique number in 1,d mask=(Mj=tol)*j; renderMat=renderMat+mask; end colormap(hsv); % Set the color map imagesc(renderMat) % Render