非线性方程数值解法--课件

“”第四章第四章非线性方程数值解法非线性方程数值解法1ppt课件“”目目录录4.1基本问题4.2二分法4.3迭代法4.4Newton迭代法4.5迭代的加速方法4.6多点迭代法4.7数值实验及程序东北林业大学理学院东北林业大学理学院22ppt课件“”4.1 4.1 基本问题基本问题本章研究求解单变量非线性方程的各种数值解法：本章研究求解单变量非线性方程的各种数值解法：二分法；二分法；单点迭代法；单点迭代法；多点迭代法；多点迭代法；迭代法的收敛性。迭代法的收敛性。东北林业大学理学院东北林业大学理学院3v对非线性方程求根大致分三个步骤：对非线性方程求根大致分三个步骤：判断根的存在性及个数；根的隔离；根的精确化。3ppt课件“”4.2 4.2 二分法二分法东北林业大学理学院东北林业大学理学院4v二分法二分法：是一个把含根区间不断缩短，使含根区间中点成为一个满足误差要求的近似解的方法4ppt课件“”二分法的计算步骤二分法的计算步骤东北林业大学理学院东北林业大学理学院5注注：二分法要求：二分法要求：函数连续函数连续 且且 两端点函数值异号两端点函数值异号。5ppt课件“”东北林业大学理学院东北林业大学理学院6优点优点：计算简单，收敛性可保证，函数要求低。：计算简单，收敛性可保证，函数要求低。缺点缺点：收敛速度慢，不能求重根和复根。：收敛速度慢，不能求重根和复根。二分法的精度二分法的精度6ppt课件“”东北林业大学理学院东北林业大学理学院7解：解：计算结果计算结果7ppt课件“”4.3 4.3 迭代法迭代法东北林业大学理学院东北林业大学理学院8v迭代法迭代法：基本思想是通过构造一个递推关系式，即迭代格式，计算出一个根的近似值序列，并希望该序列能收敛。v不动点不动点：将方程 改写成等价的形式v不动点迭代法不动点迭代法：选择一个初始值 ，可得称此方法为 不动点迭代法。8ppt课件“”不动点迭代法的几何意义不动点迭代法的几何意义东北林业大学理学院东北林业大学理学院99ppt课件“”东北林业大学理学院东北林业大学理学院10解：解：计算结果计算结果10ppt课件“”不动点不动点存在性存在性东北林业大学理学院东北林业大学理学院11定理定理1 1定理定理2 2注注1 1：若：若L L已知，由定理已知，由定理2 2，根据误差可估计迭代次数；，根据误差可估计迭代次数；注注2 2：当：当L L1 1时，上述方法不可靠。时，上述方法不可靠。11ppt课件“”不动点迭代法不动点迭代法收敛性收敛性东北林业大学理学院东北林业大学理学院12全局收敛全局收敛：局部收敛局部收敛：定理定理3 312ppt课件“”不动点迭代法不动点迭代法收敛速度收敛速度东北林业大学理学院东北林业大学理学院13P P阶收敛阶收敛：渐进误差常数渐进误差常数：定理定理4 4线性收敛：线性收敛：超线性收敛：超线性收敛：平方收敛：平方收敛：13ppt课件“”解：解：方法方法1 1方法方法2 2东北林业大学理学院东北林业大学理学院1414ppt课件“”东北林业大学理学院东北林业大学理学院15两种方法计算结果比较两种方法计算结果比较(x*=1.7320508)(x*=1.7320508)注注1 1：迭代方法：迭代方法2 2 比比 方法方法1 1收敛快收敛快注注2 2：迭代方程的：迭代方程的 收敛速度收敛速度 依赖于依赖于 迭代函数迭代函数 的选取。的选取。15ppt课件“”4.4 Newton4.4 Newton迭代法迭代法东北林业大学理学院东北林业大学理学院16v基本思想：基本思想：是将非线性方程 逐步归结为某种线性方程来求解。v计算公式：计算公式：设函数 具有二阶连续导数，由泰勒公式可得略去余项，得到：从而得到Newton迭代公式：16ppt课件“”NewtonNewton迭代法的几何意义迭代法的几何意义东北林业大学理学院东北林业大学理学院17注注1 1：只有初值充分接近根：只有初值充分接近根x*x*，迭代序列才能很快收敛到，迭代序列才能很快收敛到x*x*。注注2 2：NewtonNewton迭代法迭代法 实际是一种实际是一种 单点迭代法。单点迭代法。17ppt课件“”NewtonNewton迭代法收敛定理迭代法收敛定理东北林业大学理学院东北林业大学理学院18定理定理5 5证明：证明：故故两边令两边令18ppt课件“”东北林业大学理学院东北林业大学理学院19定理定理6 6证明：证明：由由TaylorTaylor展开：展开：得得两边对两边对 k k 取极限得证。取极限得证。注注1 1：当：当f(x*)=0f(x*)=0 时，时，NewtonNewton迭代法是超二阶收敛的。迭代法是超二阶收敛的。注注2 2：定理：定理5 5 和定理和定理6 6 说明说明NewtonNewton迭代法迭代法 收敛与否收敛与否 与初值有关。与初值有关。19ppt课件“”东北林业大学理学院东北林业大学理学院20解：解：20ppt课件“”东北林业大学理学院东北林业大学理学院21定理定理7 7几几何何解解释释21ppt课件“”东北林业大学理学院东北林业大学理学院22解：解：计算结果计算结果22ppt课件“”NewtonNewton迭代法的变形迭代法的变形简化简化NewtonNewton迭代法迭代法东北林业大学理学院东北林业大学理学院23v简化简化NewtonNewton迭代法：迭代法：其中C为常数，一般可取C=，此方法也称平行弦法。注：一般的简注：一般的简化化NewtonNewton迭代迭代法为一阶收敛。法为一阶收敛。23ppt课件“”NewtonNewton迭代法的变形迭代法的变形NewtonNewton下山法下山法东北林业大学理学院东北林业大学理学院24vNewtonNewton下山法：下山法：其中 称为 下山因子下山因子。v选择下山因子的原则：选择下山因子的原则：要使下山因子在计算过程中可以变动，一般选择下山因子时从 开始，逐次将减半进行试算，直到能使下降条件成立为止。若当计算到某步时取不到满足要求的值（或值小到无法容忍），这时称“下山失败”，需要另取初值 重新算起。24ppt课件“”东北林业大学理学院东北林业大学理学院25解：解：计算结果计算结果取初值x0=0.6,分别用Newton法和Newton下山法计算25ppt课件“”重根情形重根情形东北林业大学理学院东北林业大学理学院26故故两边令两边令26ppt课件“”东北林业大学理学院东北林业大学理学院2727ppt课件“”修正的修正的 Newton Newton迭代公式迭代公式东北林业大学理学院东北林业大学理学院28它是二阶收敛的称为 修正的修正的NewtonNewton迭代公式迭代公式。28ppt课件“”东北林业大学理学院东北林业大学理学院29解：解：分别采取三种迭代公式29ppt课件“”东北林业大学理学院东北林业大学理学院30计算结果计算结果可见，方法（可见，方法（2 2）和方法（）和方法（3 3）比方法（）比方法（1 1）收敛得快）收敛得快30ppt课件“”4.5 4.5 迭代的加速方法迭代的加速方法东北林业大学理学院东北林业大学理学院31v迭代加速：迭代加速：对于收敛的迭代过程，只要迭代足够多次，就可以使结果达到任意的精度，但有时迭代过程收敛缓慢，从而使计算量变得很大，因此迭代方程的加速是个重要的课题。v迭代加速的主要方法：迭代加速的主要方法：（1 1）Aitken 加速方法加速方法（2 2）Steffensen 迭代法迭代法31ppt课件“”AitkenAitken加速收敛方法加速收敛方法东北林业大学理学院东北林业大学理学院32v基本思想：基本思想：通过序列 构造一个更快收敛的序列 32ppt课件“”东北林业大学理学院东北林业大学理学院33定理定理8 8证明：证明：33ppt课件“”SteffensenSteffensen迭代方法迭代方法东北林业大学理学院东北林业大学理学院34v基本思想：基本思想：将不动点迭代法与Aitken方法结合起来可建立如下SteffensonSteffenson（斯蒂芬森）迭代方法：34ppt课件“”东北林业大学理学院东北林业大学理学院35解：解：计算结果（计算结果（SteffensenSteffensen迭代法）迭代法）35ppt课件“”东北林业大学理学院东北林业大学理学院36计算结果（不动点迭代法）计算结果（不动点迭代法）36ppt课件“”4.6 4.6 多点迭代法多点迭代法东北林业大学理学院东北林业大学理学院37v基本思想：基本思想：在计算新的迭代值 时，充分利用函数 及 在点 的信息，从而减少计算量，提高迭代收敛速度。v最简单的多点迭代法：最简单的多点迭代法：（1 1）弦截法）弦截法（2 2）抛物线法）抛物线法v多点迭代法的迭代格式：多点迭代法的迭代格式：37ppt课件“”弦截法弦截法东北林业大学理学院东北林业大学理学院38v迭代公式：迭代公式：v几何意义：几何意义：38ppt课件“”抛物线法抛物线法东北林业大学理学院东北林业大学理学院39v抛物线法抛物线法 迭代公式：迭代公式：v弦截法弦截法 和和 抛物线法的收敛速度：抛物线法的收敛速度：39ppt课件“”4.7 4.7 数值实验及程序数值实验及程序东北林业大学理学院东北林业大学理学院40v二分法实验二分法实验vNewtonNewton下山法实验下山法实验vNewtonNewton迭代法实验：迭代法实验：v弦截法实验弦截法实验40ppt课件“”二分法实验二分法实验东北林业大学理学院东北林业大学理学院41matlab程序如下：（程序如下：（Dichotomy.m）%二分法求解方程二分法求解方程f_name(x)=0f_name(x)=0在区间在区间a,ba,b的解的解%eps%eps为误差限，区间端点为误差限，区间端点a a和和b b由键盘输入，由键盘输入，%函数函数f_namef_name在区间在区间a,ba,b连续，且连续，且f_name(a)*f_name(b)0f_name(a)*f_name(b)0%逐次将有根区间长度缩半，当区间长度小于逐次将有根区间长度缩半，当区间长度小于epseps时，区间中点为近似解时，区间中点为近似解functionx,it=Dichotomy(f_name,eps)ifnargin0%两端点函数值同号，重新输入两端点函数值同号，重新输入fprintf(n两端点函数值同号，请重新输两端点函数值同号，请重新输n);a=input(输入左端点输入左端点a=：);b=input(输入右端点输入右端点b=：);41ppt课件“”东北林业大学理学院东北林业大学理学院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*fa0a=xm;fa=fxm;elseb=xm;fb=fxm;endendx=(b+a)/2;fprintf(n二分次数：二分次数：%dn,it);fprintf(方程的近似解：方程的近似解：%fn,x);matlab程序（程序（f3.m）%求根函数求根函数functiony=f3(x)y=x3-x-1;42ppt课件“”东北林业大学理学院东北林业大学理学院43解：解：计算过程如下：输入：x,it=Dichotomy(f3)；输出：输入左端点a=：1输入右端点b=：1.5二分次数：9，方程的近似解：1.32470743ppt课件“”NewtonNewton法实验法实验东北林业大学理学院东北林业大学理学院44matlab程序如下：（程序如下：（Newton.m）%牛顿法求解方程牛顿法求解方程f_name(x)=0f_name(x)=0在区间在区间a,ba,b的解的解%eps%eps为误差限，区间端点为误差限，区间端点a a和和b b由键盘输入，由键盘输入，%函数函数f_name(x)f_name(x)在区间在区间a,ba,b连续，连续，fd_name(x)fd_name(x)为函数为函数f_name(x)f_name(x)的导函数的导函数%fd_name(x)%fd_name(x)不为不为0 0；%逐次迭代，当相邻两次计算出的点之间距离小于逐次迭代，当相邻两次计算出的点之间距离小于epseps时，迭代结束时，迭代结束functionx,it=Newton(f_name,fd_name,eps)ifnargin=epsit=it+1;%循环次数循环次数x0=x1;x1=x0-feval(f_name,x0)/feval(fd_name,x0);endx=x1;fprintf(n迭代次数：迭代次数：%dn,it);fprintf(方程的近似解：方程的近似解：%fn,x);matlab程序：（程序：（f4.m）%求根函数求根函数functiony=f4(x)y=x.*exp(x)-1;matlab程序：（程序：（f5.m）functiony=f5(x)%函数函数f4f4的导函数的导函数y=(x+1).*exp(x);45ppt课件“”东北林业大学理学院东北林业大学理学院46解：解：计算过程如下：输入：x,it=Newton(f4,f5)；输出：输入左端点a=：-1输入右端点b=：1是否重新输入区间端点YES（输入非0），NO（输入0）：0输入起始点:x0=0.5迭代次数：3方程的近似解：0.56714346ppt课件“”NewtonNewton下山法实验下山法实验东北林业大学理学院东北林业大学理学院47matlab程序如下：（程序如下：（Newton_Down.m）%牛顿法下山法求解方程牛顿法下山法求解方程f_name(x)=0f_name(x)=0在区间在区间a,ba,b的解的解%eps%eps为误差限，初始点可以任意选取为误差限，初始点可以任意选取%函数函数f_name(x)f_name(x)在区间在区间a,ba,b连续，连续，fd_name(x)fd_name(x)为函数为函数f_name(x)f_name(x)的导函数的导函数%fd_name(x)%fd_name(x)不为不为0 0；%逐次迭代，当相邻两次计算出的点之间距离小于逐次迭代，当相邻两次计算出的点之间距离小于epseps时，迭代结束时，迭代结束functionx,it=Newton_Down(f_name,fd_name,eps)ifnargin=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%14fn,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%14fn,it,k,x1,feval(f_name,x1);endx=x1;fprintf(n迭代次数：迭代次数：%dn,it);fprintf(方程的近似解：方程的近似解：%14fn,x)48ppt课件“”东北林业大学理学院东北林业大学理学院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.32471849ppt课件“”弦截法法实验弦截法法实验东北林业大学理学院东北林业大学理学院50matlab程序如下：（程序如下：（Xian_J.m）%弦解法求解方程弦解法求解方程f_name(x)=0f_name(x)=0在区间在区间a,ba,b的解的解%eps%eps为误差限，区间端点为误差限，区间端点a a和和b b由键盘输入，由键盘输入，%函数函数f_name(x)f_name(x)在区间在区间a,ba,b连续连续%逐次迭代，当计算的函数值小于逐次迭代，当计算的函数值小于epseps时，迭代结束时，迭代结束functionx,it=Xian_J(f_name,eps)ifnargin=epsit=it+1;%循环次数循环次数x2=x1-f1/(f1-f0)*(x1-x0);%弦解法迭代公式弦解法迭代公式x0=x1;x1=x2;f0=feval(f_name,x0);f1=feval(f_name,x1);endx=x1;fprintf(n迭代次数：迭代次数：%dn,it);fprintf(方程的近似解：方程的近似解：%fn,x);51ppt课件“”东北林业大学理学院东北林业大学理学院52解：解：计算过程如下：输入：x,it=Xian_J(f4)；输出：输入左端点a=：-1输入右端点b=：1是否重新输入区间端点YES（输入非0）,NO（输入0）：0输入第一个起始点:x0=0.5输入第二个起始点:x1=0.6迭代次数：3方程的近似解：0.56714352ppt课件“”DepartmentofMathematics,NortheastForestry53ppt课件