第4章 非线性方程数值解法

第四章

非线性方程数值解法目录4.1基本问题4.2二分法4.3迭代法4.4Newton迭代法4.5迭代的加速方法4.6多点迭代法4.7数值实验及程序东北林业大学理学院24.1基本问题本章研究求解单变量非线性方程的各种数值解法：①二分法；②单点迭代法；③多点迭代法；④迭代法的收敛性。东北林业大学理学院3对非线性方程求根大致分三个步骤：①判断根的存在性及个数；②根的隔离；③根的精确化。4.2二分法东北林业大学理学院4二分法：是一个把含根区间不断缩短，使含根区间中点成为一个满足误差要求的近似解的方法．二分法的计算步骤东北林业大学理学院5注：二分法要求：函数连续且两端点函数值异号。东北林业大学理学院6优点：计算简单，收敛性可保证，函数要求低。缺点：收敛速度慢，不能求重根和复根。二分法的精度东北林业大学理学院7解：计算结果4.3迭代法东北林业大学理学院8迭代法：基本思想是通过构造一个递推关系式，即迭代格式，计算出一个根的近似值序列，并希望该序列能收敛。不动点：将方程改写成等价的形式不动点迭代法：选择一个初始值，可得称此方法为不动点迭代法。不动点迭代法的几何意义东北林业大学理学院9东北林业大学理学院10解：计算结果不动点——存在性东北林业大学理学院11定理1定理2注1：若L已知，由定理2，根据误差可估计迭代次数；注2：当L≈1时，上述方法不可靠。不动点迭代法——收敛性东北林业大学理学院12全局收敛：局部收敛：定理3不动点迭代法——收敛速度东北林业大学理学院13P阶收敛：渐进误差常数：定理4线性收敛：超线性收敛：平方收敛：解：方法1方法2东北林业大学理学院14东北林业大学理学院15两种方法计算结果比较(x*=1.7320508……)注1：迭代方法2比方法1收敛快注2：迭代方程的收敛速度依赖于迭代函数的选取。4.4Newton迭代法东北林业大学理学院16基本思想：是将非线性方程

逐步归结为某种线性方程来求解。计算公式：设函数具有二阶连续导数，由泰勒公式可得略去余项，得到：从而得到Newton迭代公式：Newton迭代法的几何意义东北林业大学理学院17注1：只有初值充分接近根x*，迭代序列才能很快收敛到x*。注2：Newton迭代法实际是一种单点迭代法。Newton迭代法收敛定理东北林业大学理学院18定理5证明：故两边令东北林业大学理学院19定理6证明：由Taylor展开：得两边对k取极限得证。注1：当f"(x*)=0时，Newton迭代法是超二阶收敛的。注2：定理5和定理6说明Newton迭代法收敛与否与初值有关。东北林业大学理学院20解：东北林业大学理学院21定理7几何解释东北林业大学理学院22解：计算结果Newton迭代法的变形——简化Newton迭代法东北林业大学理学院23简化Newton迭代法：其中C为常数，一般可取C=，此方法也称平行弦法。注：一般的简化Newton迭代法为一阶收敛。Newton迭代法的变形——Newton下山法东北林业大学理学院24Newton下山法：其中

称为下山因子。选择下山因子的原则：要使下山因子在计算过程中可以变动，一般选择下山因子时从开始，逐次将减半进行试算，直到能使下降条件成立为止。若当计算到某步时取不到满足要求的值（或值小到无法容忍），这时称“下山失败”，需要另取初值重新算起。东北林业大学理学院25解：计算结果取初值x0=0.6,分别用Newton法和Newton下山法计算重根情形东北林业大学理学院26故两边令东北林业大学理学院27修正的Newton迭代公式东北林业大学理学院28它是二阶收敛的．称为修正的Newton迭代公式。东北林业大学理学院29解：分别采取三种迭代公式东北林业大学理学院30计算结果可见，方法（2）和方法（3）比方法（1）收敛得快．4.5迭代的加速方法东北林业大学理学院31迭代加速：对于收敛的迭代过程，只要迭代足够多次，就可以使结果达到任意的精度，但有时迭代过程收敛缓慢，从而使计算量变得很大，因此迭代方程的加速是个重要的课题。迭代加速的主要方法：（1）Aitken加速方法（2）Steffensen

迭代法Aitken加速收敛方法东北林业大学理学院32基本思想：通过序列

构造一个更快收敛的序列

东北林业大学理学院33定理8证明：Steffensen迭代方法东北林业大学理学院34基本思想：将不动点迭代法与Aitken方法结合起来可建立如下Steffenson（斯蒂芬森）迭代方法：东北林业大学理学院35解：计算结果（Steffensen迭代法）东北林业大学理学院36计算结果（不动点迭代法）4.6多点迭代法东北林业大学理学院37基本思想：在计算新的迭代值时，充分利用函数及在点的信息，从而减少计算量，提高迭代收敛速度。最简单的多点迭代法：（1）弦截法（2）抛物线法多点迭代法的迭代格式：弦截法东北林业大学理学院38迭代公式：几何意义：抛物线法东北林业大学理学院39抛物线法迭代公式：弦截法和抛物线法的收敛速度：4.7数值实验及程序东北林业大学理学院40二分法实验Newton下山法实验Newton迭代法实验：弦截法实验二分法实验东北林业大学理学院41matlab程序如下：（Dichotomy.m）%二分法求解方程f_name(x)=0在区间[a,b]的解%eps为误差限，区间端点a和b由键盘输入，%函数f_name在区间[a,b]连续，且f_name(a)*f_name(b)<0%逐次将有根区间长度缩半，当区间长度小于eps时，区间中点为近似解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%两端点函数值同号，重新输入fprintf('\n两端点函数值同号，请重新输\n');a=input('输入左端点a=：');b=input('输入右端点b=：');

东北林业大学理学院42fa=feval(f_name,a);fb=feval(f_name,b);End%二分法计算方程的根whileb-a>=epsit=it+1;%循环次数xm=(b+a)/2;%计算中点fxm=feval(f_name,xm);%中点的函数值iffxm*fa>0a=xm;fa=fxm;elseb=xm;fb=fxm;endendx=(b+a)/2;fprintf('\n二分次数：%d\n',it);fprintf('方程的近似解：%f\n',x);

matlab程序（f3.m）%求根函数functiony=f3(x)y=x^3-x-1;东北林业大学理学院43解：计算过程如下：输入：[x,it]=Dichotomy('f3')；输出：输入左端点a=：1输入右端点b=：1.5

二分次数：9，方程的近似解：1.324707Newton法实验东北林业大学理学院44matlab程序如下：（Newton.m）%牛顿法求解方程f_name(x)=0在区间[a,b]的解%eps为误差限，区间端点a和b由键盘输入，%函数f_name(x)在区间[a,b]连续，fd_name(x)为函数f_name(x)的导函数%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);%绘制函数图像，寻找初始点leap=input('\n是否重新输入区间端点——YES（输入非0），NO（输入0）：');东北林业大学理学院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（输入非0），N（输入0）：');end%牛顿迭代法计算方程的根x0=input('输入起始点:x0=');x1=x0-feval(f_name,x0)/feval(fd_name,x0);whileabs(x1-x0)>=epsit=it+1;%循环次数x0=x1;x1=x0-feval(f_name,x0)/feval(fd_name,x0);endx=x1;fprintf('\n迭代次数：%d\n',it);fprintf('方程的近似解：%f\n',x);matlab程序：（f4.m）%求根函数functiony=f4(x)y=x.*exp(x)-1;

matlab程序：（f5.m）functiony=f5(x)%函数f4的导函数y=(x+1).*exp(x);东北林业大学理学院46解：计算过程如下：输入：[x,it]=Newton('f4','f5')；输出：

输入左端点a=：-1输入右端点b=：1是否重新输入区间端点——YES（输入非0），NO（输入0）：0输入起始点:x0=0.5迭代次数：3方程的近似解：0.567143Newton下山法实验东北林业大学理学院47matlab程序如下：（Newton_Down.m）%牛顿法下山法求解方程f_name(x)=0在区间[a,b]的解%eps为误差限，初始点可以任意选取%函数f_name(x)在区间[a,b]连续，fd_name(x)为函数f_name(x)的导函数%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));东北林业大学理学院48whilef1>=f0;k=k/2;x1=x0-k*feval(f_name,x0)/feval(fd_name,x0);f1=abs(feval(f_name,x1));endfprintf('\n迭代次数

下山因子kx1f(x1)\n')fprintf('%5d%8f%8f%14f\n',it,k,x1,feval(f_name,x1));whileabs(x1-x0)>=epsit=it+1;%循环次数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迭代次数：%d\n',it);fprintf('方程的近似解：%14f\n',x)东北林业大学理学院49解：计算过程如下：输入：[x,it]=Newton_Down('f6','f7');输出：输入起始点:x0=0.6迭代次数

下山因子kx1f(x1)10.0312501.140625-0.65664321.0000001.3668140.18664031.0000001.3262800.00667041.0000001.3247200.00001051.0000001.3247180.000000迭代次数：5方程的近似解：1.324718弦截法法实验东北林业大学理学院50matlab程序如下：（Xian_J.m）%弦解法求解方程f_name(x)=0在区间[a,b]的解%eps为误差限，区间端点a和b由键盘输入，%函数f_name(x)在区间[a,b]连续%逐次迭代，当计算的函数值小于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);%绘制函数图像，寻找初始点leap=input('\n是否重新输入区间端点——YES（输入非0），NO（输入0）：');东北林业大学理学院51whileleap~=0fprintf