典型例題與習(xí)題1

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

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

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

4、xdxx 201arctan( )arctan(0)arctan( )1xdxxxx 2311( 11)1aaaaa 2460(1)darctan( )xaaaax 3571arctan( )357xxxx15/3610ie 16/36例例10.在計算機上對調(diào)和級數(shù)逐項求和計算在計算機上對調(diào)和級數(shù)逐項求和計算 nknkS11當(dāng)當(dāng) n很大時很大時，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，則牛頓迭代公式則牛頓迭代公式 22313323nnnnn

6、nxaxxaxxx 2332)(xaxx 33232)(xax 42)(xax *()0()0 xx且且故立方根迭代算法二階收斂故立方根迭代算法二階收斂20/36例例14. 設(shè)設(shè)a 為正實數(shù)為正實數(shù),試建立求試建立求1/a 的牛頓迭代公的牛頓迭代公式式,要求在迭代公式中不含有除法運算要求在迭代公式中不含有除法運算,并考慮并考慮迭代公式的收斂。迭代公式的收斂。 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 是是計計算算的的三三階階方方

7、法法。22/36例例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 f

8、xp x fxp 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 對于復(fù)變量對于復(fù)變量 z=x+iy 的復(fù)值函數(shù)的復(fù)值函數(shù)f(z) 應(yīng)用牛頓迭代公式應(yīng)用牛頓迭代公式 )()(1nnnnzfzfzz 時為避開復(fù)數(shù)運算時為避開復(fù)數(shù)運算,令令zn=xn+iynf(zn)=An+iBn，f(zn)=Cn+iDn 證明證明 221nnnnnnnnDCDBCAxx 221nnnnnnnnDCCBDAyy 25/36例例17. 提示提示: 取初值取初值x1=21/2,222lim=2nnnxx給給出出求求的的迭迭代代格格式式, ,并并證證明明。12nnxx 迭迭代代格格式式考慮序列單調(diào)有界考慮

10、序列單調(diào)有界,則該序列必有極限。則該序列必有極限。26/360:52*2.5 ( ), ( )( )1, xxxxx 定定理理設(shè)設(shè)為為的的不不動動點點在在 的的某某鄰鄰域域連連續(xù)續(xù)且且則則迭迭代代法法局局部部收收斂斂。例例18.:( )x 提提示示 因因為為連連續(xù)續(xù), , 由由局局部部保保號號性性知知存存在在一一個個鄰鄰域域|( )|1,xL 有有且且有有|( )|1,xL 有有且且有有*| ( )| ( )()|0, 均收斂于均收斂于21/2。21212(2)2(2)nnnnxxxx 29/36牛頓迭代法的收斂域問題牛頓迭代法的收斂域問題: : 用牛頓迭代法求解方程用牛頓迭代法求解方程 zd

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

12、 % Perform Newton 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 ma