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

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

2、.*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 迭代法思想迭代法思想:收斂性收斂性 收斂速度收斂速度|( )| 1x Iterate:To say or do again

3、 or againandagain(1)( )( *)( *)( *)0 ( *)0rrxxxx 6/36例例1. .經過四舍五入得出經過四舍五入得出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( )11dxdxx 201arcta

4、n( )arctan(0)arctan( )1xdxxxx 2311( 11)1aaaaa 2460(1)darctan( )xaaaax 3571arctan( )357xxxx15/3610ie 16/36例例10.在計算機上對調和級數(shù)逐項求和計算在計算機上對調和級數(shù)逐項求和計算 nknkS11當當 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嚴格單調遞減。嚴格單調遞減。411011022n 18/36 例例12. 構造求構造求ex+10 x-2=0根的迭代法。根的迭代法。提示提示:(2e )( )10 xx ( )10 xex 故迭代法算法一階收斂。故迭代法算法一階收斂。19/36 例例13. 應用牛頓迭代法于方程應用牛頓迭代法于方程x3 a=0,導出求立方根的迭代公式導出求立方根的迭代公式,并討論其收斂階。并討論其收斂階。解：令解：令 f(x) = x3 a，則牛頓迭代公式則牛頓迭代公式 22313323nnnnnnxaxxaxxx

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

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

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

11、。例如d=3時時, 方程在復平面上三個根分別是方程在復平面上三個根分別是iz23212 iz23213 z1 = 1選擇中心位于坐標原點，邊長選擇中心位于坐標原點，邊長為為2 2的正方形內的任意點作初始的正方形內的任意點作初始值，進行迭代，把收斂到三個值，進行迭代，把收斂到三個根的初值分為三類，并分別標根的初值分為三類，并分別標上不同顏色上不同顏色( (例如紅、綠和藍例如紅、綠和藍) )。對充分多的初始點進行實驗，對充分多的初始點進行實驗，繪出牛頓迭代法對該方程的收繪出牛頓迭代法對該方程的收斂域彩色圖斂域彩色圖。 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