第四章

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

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

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

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

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

41ppt課件東北林業(yè)大學(xué)理學(xué)院42fa=feval(f_name,a);fb=feval(f_name,b);End%二分法計(jì)算方程的根whileb-a>=epsit=it+1;%循環(huán)次數(shù)xm=(b+a)/2;%計(jì)算中點(diǎn)fxm=feval(f_name,xm);%中點(diǎn)的函數(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;42ppt課件東北林業(yè)大學(xué)理學(xué)院43解：計(jì)算過程如下：輸入：[x,it]=Dichotomy('f3')；輸出：輸入左端點(diǎn)a=：1輸入右端點(diǎn)b=：1.5

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

輸入左端點(diǎn)a=：-1輸入右端點(diǎn)b=：1是否重新輸入?yún)^(qū)間端點(diǎn)——YES（輸入非0），NO（輸入0）：0輸入起始點(diǎn):x0=0.5迭代次數(shù)：3方程的近似解：0.56714346ppt課件Newton下山法實(shí)驗(yàn)東北林業(yè)大學(xué)理學(xué)院47matlab程序如下：（Newton_Down.m）%牛頓法下山法求解方程f_name(x)=0在區(qū)間[a,b]的解%eps為誤差限，初始點(diǎn)可以任意選取%函數(shù)f_name(x)在區(qū)間[a,b]連續(xù)，fd_name(x)為函數(shù)f_name(x)的導(dǎo)函數(shù)%fd_name(x)不為0；%逐次迭代，當(dāng)相鄰兩次計(jì)算出的點(diǎn)之間距離小于eps時(shí)，迭代結(jié)束．function[x,it]=Newton_Down(f_name,fd_name,eps)ifnargin<3eps=1e-3;%默認(rèn)誤差限endit=1;clc%牛頓下山法計(jì)算方程的根k=1;%下山因子x0=input('輸入起始點(diǎn):x0=');x1=x0-k*feval(f_name,x0)/feval(fd_name,x0);f0=abs(feval(f_name,x0));f1=abs(feval(f_name,x1));47ppt課件東北林業(yè)大學(xué)理學(xué)院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)48ppt課件東北林業(yè)大學(xué)理學(xué)院49解：計(jì)算過程如下：輸入：[x,it]=Newton_Down('f6','f7');輸出：輸入起始點(diǎn):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.32471849ppt課件弦截法法實(shí)驗(yàn)東北林業(yè)大學(xué)理學(xué)院50matlab程序如下：（Xian_J.m）%弦解法求解方程f_name(x)=0在區(qū)間[a,b]的解%eps為誤差限，區(qū)間端點(diǎn)a和b由鍵盤輸入，%函數(shù)f_name(x)在區(qū)間[a,b]連續(xù)%逐次迭代，當(dāng)計(jì)算的函數(shù)值小于eps時(shí)，迭代結(jié)束．function[x,it]=Xian_J(f_name,eps)ifnargin<2eps=1e-5;%默認(rèn)誤差限Endit=0;%輸入兩端點(diǎn)a=input('\n輸入左端點(diǎn)a=：');b=input('輸入右端點(diǎn)b=：');t=a:eps:b;y=feval(f_name,t);plot(t,y);%繪制函數(shù)圖像，尋找初始點(diǎn)leap=input('\n是否重新輸入?yún)^(qū)間端點(diǎn)——YES（輸入非0），NO（輸入0）：');50ppt課件東北林業(yè)大學(xué)理學(xué)院51whileleap~=0