第4章 非線性方程數(shù)值解法

第四章

非線性方程數(shù)值解法目錄4.1基本問題4.2二分法4.3迭代法4.4Newton迭代法4.5迭代的加速方法4.6多點迭代法4.7數(shù)值實驗及程序東北林業(yè)大學理學院24.1基本問題本章研究求解單變量非線性方程的各種數(shù)值解法：①二分法；②單點迭代法；③多點迭代法；④迭代法的收斂性。東北林業(yè)大學理學院3對非線性方程求根大致分三個步驟：①判斷根的存在性及個數(shù)；②根的隔離；③根的精確化。4.2二分法東北林業(yè)大學理學院4二分法：是一個把含根區(qū)間不斷縮短，使含根區(qū)間中點成為一個滿足誤差要求的近似解的方法．二分法的計算步驟東北林業(yè)大學理學院5注：二分法要求：函數(shù)連續(xù)且兩端點函數(shù)值異號。東北林業(yè)大學理學院6優(yōu)點：計算簡單，收斂性可保證，函數(shù)要求低。缺點：收斂速度慢，不能求重根和復根。二分法的精度東北林業(yè)大學理學院7解：計算結果4.3迭代法東北林業(yè)大學理學院8迭代法：基本思想是通過構造一個遞推關系式，即迭代格式，計算出一個根的近似值序列，并希望該序列能收斂。不動點：將方程改寫成等價的形式不動點迭代法：選擇一個初始值，可得稱此方法為不動點迭代法。不動點迭代法的幾何意義東北林業(yè)大學理學院9東北林業(yè)大學理學院10解：計算結果不動點——存在性東北林業(yè)大學理學院11定理1定理2注1：若L已知，由定理2，根據(jù)誤差可估計迭代次數(shù)；注2：當L≈1時，上述方法不可靠。不動點迭代法——收斂性東北林業(yè)大學理學院12全局收斂：局部收斂：定理3不動點迭代法——收斂速度東北林業(yè)大學理學院13P階收斂：漸進誤差常數(shù)：定理4線性收斂：超線性收斂：平方收斂：解：方法1方法2東北林業(yè)大學理學院14東北林業(yè)大學理學院15兩種方法計算結果比較(x*=1.7320508……)注1：迭代方法2比方法1收斂快注2：迭代方程的收斂速度依賴于迭代函數(shù)的選取。4.4Newton迭代法東北林業(yè)大學理學院16基本思想：是將非線性方程

逐步歸結為某種線性方程來求解。計算公式：設函數(shù)具有二階連續(xù)導數(shù)，由泰勒公式可得略去余項，得到：從而得到Newton迭代公式：Newton迭代法的幾何意義東北林業(yè)大學理學院17注1：只有初值充分接近根x*，迭代序列才能很快收斂到x*。注2：Newton迭代法實際是一種單點迭代法。Newton迭代法收斂定理東北林業(yè)大學理學院18定理5證明：故兩邊令東北林業(yè)大學理學院19定理6證明：由Taylor展開：得兩邊對k取極限得證。注1：當f"(x*)=0時，Newton迭代法是超二階收斂的。注2：定理5和定理6說明Newton迭代法收斂與否與初值有關。東北林業(yè)大學理學院20解：東北林業(yè)大學理學院21定理7幾何解釋東北林業(yè)大學理學院22解：計算結果Newton迭代法的變形——簡化Newton迭代法東北林業(yè)大學理學院23簡化Newton迭代法：其中C為常數(shù)，一般可取C=，此方法也稱平行弦法。注：一般的簡化Newton迭代法為一階收斂。Newton迭代法的變形——Newton下山法東北林業(yè)大學理學院24Newton下山法：其中

稱為下山因子。選擇下山因子的原則：要使下山因子在計算過程中可以變動，一般選擇下山因子時從開始，逐次將減半進行試算，直到能使下降條件成立為止。若當計算到某步時取不到滿足要求的值（或值小到無法容忍），這時稱“下山失敗”，需要另取初值重新算起。東北林業(yè)大學理學院25解：計算結果取初值x0=0.6,分別用Newton法和Newton下山法計算重根情形東北林業(yè)大學理學院26故兩邊令東北林業(yè)大學理學院27修正的Newton迭代公式東北林業(yè)大學理學院28它是二階收斂的．稱為修正的Newton迭代公式。東北林業(yè)大學理學院29解：分別采取三種迭代公式東北林業(yè)大學理學院30計算結果可見，方法（2）和方法（3）比方法（1）收斂得快．4.5迭代的加速方法東北林業(yè)大學理學院31迭代加速：對于收斂的迭代過程，只要迭代足夠多次，就可以使結果達到任意的精度，但有時迭代過程收斂緩慢，從而使計算量變得很大，因此迭代方程的加速是個重要的課題。迭代加速的主要方法：（1）Aitken加速方法（2）Steffensen

迭代法Aitken加速收斂方法東北林業(yè)大學理學院32基本思想：通過序列

構造一個更快收斂的序列

東北林業(yè)大學理學院33定理8證明：Steffensen迭代方法東北林業(yè)大學理學院34基本思想：將不動點迭代法與Aitken方法結合起來可建立如下Steffenson（斯蒂芬森）迭代方法：東北林業(yè)大學理學院35解：計算結果（Steffensen迭代法）東北林業(yè)大學理學院36計算結果（不動點迭代法）4.6多點迭代法東北林業(yè)大學理學院37基本思想：在計算新的迭代值時，充分利用函數(shù)及在點的信息，從而減少計算量，提高迭代收斂速度。最簡單的多點迭代法：（1）弦截法（2）拋物線法多點迭代法的迭代格式：弦截法東北林業(yè)大學理學院38迭代公式：幾何意義：拋物線法東北林業(yè)大學理學院39拋物線法迭代公式：弦截法和拋物線法的收斂速度：4.7數(shù)值實驗及程序東北林業(yè)大學理學院40二分法實驗Newton下山法實驗Newton迭代法實驗：弦截法實驗二分法實驗東北林業(yè)大學理學院41matlab程序如下：（Dichotomy.m）%二分法求解方程f_name(x)=0在區(qū)間[a,b]的解%eps為誤差限，區(qū)間端點a和b由鍵盤輸入，%函數(shù)f_name在區(qū)間[a,b]連續(xù)，且f_name(a)*f_name(b)<0%逐次將有根區(qū)間長度縮半，當區(qū)間長度小于eps時，區(qū)間中點為近似解function[x,it]=Dichotomy(f_name,eps)ifnargin<2eps=1e-3;%默認誤差限endit=0;%輸入兩端點a=input('\n輸入左端點a=：');b=input('輸入右端點b=：');fa=feval(f_name,a);fb=feval(f_name,b);whilefa*fb>0%兩端點函數(shù)值同號，重新輸入fprintf('\n兩端點函數(shù)值同號，請重新輸\n');a=input('輸入左端點a=：');b=input('輸入右端點b=：');

東北林業(yè)大學理學院42fa=feval(f_name,a);fb=feval(f_name,b);End%二分法計算方程的根whileb-a>=epsit=it+1;%循環(huán)次數(shù)xm=(b+a)/2;%計算中點fxm=feval(f_name,xm);%中點的函數(shù)值iffxm*fa>0a=xm;fa=fxm;elseb=xm;fb=fxm;endendx=(b+a)/2;fprintf('\n二分次數(shù)：%d\n',it);fprintf('方程的近似解：%f\n',x);

matlab程序（f3.m）%求根函數(shù)functiony=f3(x)y=x^3-x-1;東北林業(yè)大學理學院43解：計算過程如下：輸入：[x,it]=Dichotomy('f3')；輸出：輸入左端點a=：1輸入右端點b=：1.5

二分次數(shù)：9，方程的近似解：1.324707Newton法實驗東北林業(yè)大學理學院44matlab程序如下：（Newton.m）%牛頓法求解方程f_name(x)=0在區(qū)間[a,b]的解%eps為誤差限，區(qū)間端點a和b由鍵盤輸入，%函數(shù)f_name(x)在區(qū)間[a,b]連續(xù)，fd_name(x)為函數(shù)f_name(x)的導函數(shù)%fd_name(x)不為0；%逐次迭代，當相鄰兩次計算出的點之間距離小于eps時，迭代結束．function[x,it]=Newton(f_name,fd_name,eps)ifnargin<3eps=1e-3;%默認誤差限endit=1;a=input('\n輸入左端點a=：');%輸入兩端點b=input('輸入右端點b=：');t=a:eps:b;y=feval(f_name,t);plot(t,y);%繪制函數(shù)圖像，尋找初始點leap=input('\n是否重新輸入?yún)^(qū)間端點——YES（輸入非0），NO（輸入0）：');東北林業(yè)大學理學院45whileleap~=0fprintf('\n請重新輸入\n');a=input('輸入左端點a=：');b=input('輸入右端點b=：');t=a:eps:b;y=feval(f_name,t);plot(t,y);leap=input('\n是否重新輸入?yún)^(qū)間端點——Y（輸入非0），N（輸入0）：');end%牛頓迭代法計算方程的根x0=input('輸入起始點:x0=');x1=x0-feval(f_name,x0)/feval(fd_name,x0);whileabs(x1-x0)>=epsit=it+1;%循環(huán)次數(shù)x0=x1;x1=x0-feval(f_name,x0)/feval(fd_name,x0);endx=x1;fprintf('\n迭代次數(shù)：%d\n',it);fprintf('方程的近似解：%f\n',x);matlab程序：（f4.m）%求根函數(shù)functiony=f4(x)y=x.*exp(x)-1;

matlab程序：（f5.m）functiony=f5(x)%函數(shù)f4的導函數(shù)y=(x+1).*exp(x);東北林業(yè)大學理學院46解：計算過程如下：輸入：[x,it]=Newton('f4','f5')；輸出：

輸入左端點a=：-1輸入右端點b=：1是否重新輸入?yún)^(qū)間端點——YES（輸入非0），NO（輸入0）：0輸入起始點:x0=0.5迭代次數(shù)：3方程的近似解：0.567143Newton下山法實驗東北林業(yè)大學理學院47matlab程序如下：（Newton_Down.m）%牛頓法下山法求解方程f_name(x)=0在區(qū)間[a,b]的解%eps為誤差限，初始點可以任意選取%函數(shù)f_name(x)在區(qū)間[a,b]連續(xù)，fd_name(x)為函數(shù)f_name(x)的導函數(shù)%fd_name(x)不為0；%逐次迭代，當相鄰兩次計算出的點之間距離小于eps時，迭代結束．function[x,it]=Newton_Down(f_name,fd_name,eps)ifnargin<3eps=1e-3;%默認誤差限endit=1;clc%牛頓下山法計算方程的根k=1;%下山因子x0=input('輸入起始點:x0=');x1=x0-k*feval(f_name,x0)/feval(fd_name,x0);f0=abs(feval(f_name,x0));f1=abs(feval(f_name,x1));東北林業(yè)大學理學院48whilef1>=f0;k=k/2;x1=x0-k*feval(f_name,x0)/feval(fd_name,x0);f1=abs(feval(f_name,x1));endfprintf('\n迭代次數(shù)

下山因子kx1f(x1)\n')fprintf('%5d%8f%8f%14f\n',it,k,x1,feval(f_name,x1));whileabs(x1-x0)>=epsit=it+1;%循環(huán)次數(shù)k=1;x0=x1;f0=f1;x1=x0-k*feval(f_name,x0)/feval(fd_name,x0);f1=abs(feval(f_name,x1));whilef1>=f0;k=k/2;x1=x0-k*feval(f_name,x0)/feval(fd_name,x0);f1=abs(feval(f_name,x1));endfprintf(‘%5d%8f%8f%14f\n',it,k,x1,feval(f_name,x1));endx=x1;fprintf('\n迭代次數(shù)：%d\n',it);fprintf('方程的近似解：%14f\n',x)東北林業(yè)大學理學院49解：計算過程如下：輸入：[x,it]=Newton_Down('f6','f7');輸出：輸入起始點:x0=0.6迭代次數(shù)

下山因子kx1f(x1)10.0312501.140625-0.65664321.0000001.3668140.18664031.0000001.3262800.00667041.0000001.3247200.00001051.0000001.3247180.000000迭代次數(shù)：5方程的近似解：1.324718弦截法法實驗東北林業(yè)大學理學院50matlab程序如下：（Xian_J.m）%弦解法求解方程f_name(x)=0在區(qū)間[a,b]的解%eps為誤差限，區(qū)間端點a和b由鍵盤輸入，%函數(shù)f_name(x)在區(qū)間[a,b]連續(xù)%逐次迭代，當計算的函數(shù)值小于eps時，迭代結束．function[x,it]=Xian_J(f_name,eps)ifnargin<2eps=1e-5;%默認誤差限Endit=0;%輸入兩端點a=input('\n輸入左端點a=：');b=input('輸入右端點b=：');t=a:eps:b;y=feval(f_name,t);plot(t,y);%繪制函數(shù)圖像，尋找初始點leap=input('\n是否重新輸入?yún)^(qū)間端點——YES（輸入非0），NO（輸入0）：');東北林業(yè)大學理學院51whileleap~=0fprintf