数值计算方法 教学课件 ppt 作者 刘玲 第2章 非线性方程的数值解法

1、第2章,非线性方程的数值解法,目 录,2.1 二分法 2.2 一般迭代法 2.2.1 迭代法及收敛性 2.2.2 Steffensen加速收敛方法 2.3 Newton切线法 2.3.1 Newton迭代法及其收敛性 2.3.2 代数方程的Newton迭代法 2.4 弦截法 2.5 MATLAB程序代码与算例,主要内容,本章重点介绍求解非线性方程 的几种常见和有效的数值方法,同时也对非线性方程组 求解,简单介绍一些最基本的解法.无论在理论上,还是在 实际应用中,这些数值解法都是对经典的解析方法的突 破性开拓和补充,许多问题的求解,在解析方法无能为力 时,数值方法则可以借助于计算机出色完成.,2.1二分法,求非线性方程,确定方程的有根区间 计算根的近似值,的根的方法,分为两步：,首先确定有根区间：依据零点定理。 设 ， 且 ，则方程 在区间 上至少有一根。如果 在 上恒正或恒负，则此根唯一。,等步长扫描法求有根区间,用计算机求有根区间：等步长扫描法。 设h0是给定的步长，取 ， 若 则扫描成功；否则令 ，继续上述方法，直到成 功。如果 则扫描失败。再将h 缩小， 继续以上步骤。,等步长扫

2、描算法,算法：（求方程 的有根区间） (1) 输入： ； (2) ； (3) ，若 输出失败信息，停机。 (4)若 。输出 ，已算出方程的一个根，停机。,等步长扫描算法,(5) 若 。输出 为有根区间，停机 (6) ，转 3） 注：如果对足够小的步长h扫描失败。说明： 在 内无根 在 内有偶重根,二分法,用二分法(将区间对平分)求解。 令 若 ，则 为有根区间，否则 为有根区间。 记新的有根区间为 ， 则 且,二分法,对 重复上述做法得 且,二分法,设 所求的根为 ， 则 即 取 为 的近似解,求方程f(x)=0的根的二分法算法,求方程f(x)=0的全部实根的二分法算法,求方程f(x)=0的全部实根的二分法算法,例题,例1 设方程 解：取h=0.1,扫描得： 又 即 在 有唯一根。,2.2一般迭代法,2.2.1 迭代法及收敛性 对于 有时可以写成 形式 如：,迭代法及收敛性,考察方程 。这种方程是隐式方程，因而不能直接求出它的根，但如果给出根的某个猜测值 ， 代入 中的右端得到 ，再以 为一个猜测值，代入 的右端得 反复迭代得,迭代法及收敛性,若 收敛，即 则得 是 的一个根,迭代法的

3、几何意义,交点的横坐标,y=x,简单迭代法,将 变为另一种等价形式 。 选取 的某一近似值 ，则按递推 关系 产生的迭代序列 。这种方法算为简单迭代法。,例题,例2.2.1 试用迭代法求方程 在区间(1，2)内的实根。 解：由 建立迭代关系 k=10,1,2,3. 计算结果如下:,例题,精确到小数点后五位,例题,但如果由 建立迭代公式 仍取 ，则有 ， 显然结果越来越大， 是发散序列,迭代法的收敛性,定理2.2.1（压缩映像原理） 设迭代函数 在闭区间 上满足 （1） （2） 满足Lipschitz条件 即 有 且 。,压缩映像原理,则 在 上存在 唯一解 ， 且对 ，由 产生 的序列 收敛于 。,压缩映像原理,证明：不失一般性,不妨设 否则 为方程的根。 首先证明根的存在性 令,压缩映像原理,则 ， 即 由条件2） 是 上的连续函数 是 上的连续函数。 故由零点定理 在 上至少有一根,压缩映像原理,再证根的唯一性 设有 均为方程的根 则 因为 0L1 ，所以只可能 ， 即根是唯一的。,压缩映像原理,最后证迭代序列的收敛性 与n 无关，而0L1 即,压缩映像原理,误差估计 若 满足定理

4、2.2.1条件，则 这是事后估计，也就是停机标准。L越小，收敛速度越快。 这是事前估计。选取n，预先估计迭代次数。,例题,例2.2.2 证明函数 在区间1，2上满足迭代收敛条件。 证明：,例题,例题,若取迭代函数 ， 不满足压缩映像原理，故不能肯定 收敛到方程的根。,简单迭代收敛情况的几何解释,2.2.2 Steffensen加速收敛方法,迭代法收敛的阶 定义2.2.1 设序列 收敛到 ，若有实数 和非零常数C，使得 其中， ，则称该序列是p 阶收敛的，C 称为渐进误差常数。,迭代法收敛的阶,当p=1时，称为线性收敛； 当p1时，称为超线性收敛； 当p=2时，称为平方收敛或二次收敛。,迭代法收敛的阶,定理2.2.2 设 是方程 的不动点，若 为足够小的正数 。如果 且 ，则从任意 出发，由 产生的序列 收敛到 ，当 时敛速是线性的。,迭代法收敛的阶,证明： 满足压缩映像原理,迭代法收敛的阶,敛速是线性的 线性收敛到 。,Steffensen迭代格式,由线性收敛知 当n充分大时有 即,Steffensen迭代格式,展开有：,Steffensen迭代格式,已知 ，则 ， 改成,n=0，1，

5、2，,Steffensen迭代格式,也可以改写成 其中迭代函数,Steffensen迭代法收敛的充要条件,定理2.2.3,Steffensen迭代法收敛的充要条件,证明：必要性,Steffensen迭代法收敛的充要条件,充分性,Steffensen算法的收敛速度,Steffensen算法的收敛速度,定理2.2.5 在定理2.2.3假设下，若 产生的序列 至少平方收敛到 。,Steffensen算法的收敛速度,Steffensen算法的收敛速度,Steffensen算法的收敛速度,Steffensen算法的收敛速度,由定理2.2.4知 至少以平方速度收敛到 。 也就是说：简单迭代法是线性收敛；Steffensen迭代至少平方以上收敛（加速收敛）。,例题,例2.2.3试用Steffensen算法求解方程 解法一、取 ，由,n = 0，1，2，,例题,取初值 ，计算结果如下：,例题,解法二、取 ，由 对于该迭代函数在一般迭代法中是发散的，而Steffensen格式却是收敛的。,n=0，1，2，,例题,取初值 ，计算结果如下：,Steffensen迭代格式几何解释,Steffensen迭代算法

6、,Steffensen迭代算法,2.3 Newton迭代法,设x* 是方程f (x ) = 0的根，又x0 为x* 附近的一个值 ，将f (x ) 在x0附近做泰勒展式 令 ，则,Newton迭代法,去掉 的二次项，有： 即 以x1代替x0重复以上的过程，继续下去得：,Newton迭代法,以此产生的序列Xn得到f(x)=0的近似 解，称为Newton法，又叫切线法。,Newton迭代法几何解释,几何意义,例题,例2.3.1 用Newton法求 的近似解。 解：由零点定理。,例题,例题,例2.3.2 用Newton法计算 。 解：,Newton迭代法算法框图,Newton迭代法算法,Newton迭代法收敛性,定理2.3.1 设函数 ，且满足 若初值 满足 时，由Newton法产生的序列收敛到 在a,b上的唯一根。,Newton迭代法收敛性,证明： 根的存在性 根的唯一性,Newton迭代法收敛性,收敛性,Newton迭代法收敛性,Newton迭代法收敛性,Newton迭代法收敛性,推论 在定理2.3.1条件下， Newton迭代法具有平方收敛速度。,代数方程的Newton迭代法,代数方程的Newton迭代法推导 设n次代数方程 用Newton迭代法求有限区间的实根，则要计算 ，一般采用秦九韶算法。,代数方程的Newton迭代法,由Taylor展式,代数方程的Newton迭代法,代数方程的Newton迭代法,同理,代数方程的Newton迭代法,比较x的同次幂系数得： 故代数方程的Newton迭代公式,代数方程的Newton迭代法算法,2.4弦截法,Newton迭代法有一个较强的要求是 且存在。因此，用弦的斜率 近似的替代 。,弦截法,令y=0,解得弦与x轴的交点是坐标x2,弦截法,弦截法的几何解释,例题,例2.4.1 用快速弦截法求方程 在区间（1，2）内的实根。 解：取x0=1,x1=2,代入公式2.4.2计算结果,如表2.4.1所示。,弦截法收敛定理,弦截法收敛定理,求解方程f(x)=0的快速弦截法,

《数值计算方法 教学课件 ppt 作者 刘玲 第2章 非线性方程的数值解法》由会员E****分享，可在线阅读，更多相关《数值计算方法 教学课件 ppt 作者 刘玲 第2章 非线性方程的数值解法》请在金锄头文库上搜索。