第二章非线性方程求根.ppt

1,第二章 非线性方程求根,1 二分法2 简单迭代法3 牛顿迭代法4 迭代法的收敛阶与加速收敛方法,2,1. 二分法,1.1 问题的提出1.2 有关概念1.3 二分法原理1.4 程序框图1.5 收敛性分析1.6 二分法的优缺点1.7 例题求解1.8 二分法与跨步区间法求方程的全部实根,3,1.1 问题的提出：,函数方程若 不是x的线性函数, 则称(1)为非线性方程 , 特别若 是n次多项式，则称(1)为n次多项式方程或代数方程；若 是超越函数，则称(1)为超越方程 理论上已证明，对于次数n<=5的多项式方程，它的根可以用公式表示，而次数大于5的多项式方程，它的根一般不能用解析表达式表示4,因此对于 的函数方程，一般来说，不存在根的解析表达式，而实际应用中，也不一定必需得到求根的解析表达式，只要得到满足精度要求的根的近似值就可以了求根方法中最直观最简单的方法是二分法5,求根问题包括：根的存在性、根的范围和根的精确化根的存在定理 假设函数 ,且 , 函数图象如图1所示，则至少存在一点 使得 ,这就是根的存在定理。

1.2 有关概念,二分法就是将方程的有根区间对分,然后再选择比原区间缩小一半的有根区间,如此继续下去,直到得到满足精度要求的根为止的一种简单的区间方法6,,函数方程 的解通常称为方程的根或函数 的零点，特别地，如果函数 可分解为 且 , 则称 是 的 重零点或 的 重根 当 时，称 是 的单根 或单零点7,,8,1.3 二分法原理,给定方程 ,设 在区间 连续,且 ,则方程 在 内至少有一根,为便于讨论,不妨设方程 在 内只有一实根 ，采取使有根区间逐步缩小,从而得到满足精度要求的实根 的近似值 9,取区间 二等分的中点 ， 若 ,则 是 的实根； 若 成立,则 必在区间 内,取 ;否则 必在区间 内,取 , 这样,得到新区间 ，其长度为 的一半,如此继续下去,进行 次等分后,得到一组不断缩小的区间 。

其中每一个区间都是前一个区间长度的一半,从而 的长度为,10,11,,图2,1.4 程序框图,12,现在来研究用二分法求函数的根时的精确性假定 是连续函数，并且它在区间 的两端点 所取的值有相反的符号，于是在 中有一个根 ，如果用中点 作为对 的估计，则有 现在应用二分算法，经过n步后将算出一个近似根其误差至多为其中,1.5 收敛性分析,13,二分法计算过程简单，程序容易实现可在大范围内求根，但该方法收敛较慢，且不能求偶数重根和复根，一般用于求根的初始近似值，而后在使用其它的求根方法 二分法收敛速度不快，其收敛速度仅与一个以 1/2为比值的等比级数相同 1.6二分法的优缺点,14,1.7例题求解,例1：用二分法求方程 在区间 内的实根,要求误差限为 解：令 因为 得 得…….,15,16,如果我们把二分法与跨步区间法结合起来,就可以求非线性方程在任一区间上的全部实根。

首先, 将方程式f(x)=0化为函数式y=f(x).假设方程求解区间为x[a,b] ,跨步区间为h长,允许误差为如图3所示,由a点出发向 b点跨步,每跨一步h,经过判断在该区间内是否有根如有根则进行二分法求根计算,否则继续以h为步长向前跨步找根,直到走出区间[a,b]为止 这样 ,我们就可以按顺序将方程的全部实根找出1.8 二分法与跨步区间法求方程的全部实根,17,但应注意在计算中步长h要适当取小一些,若h过长则容易丢根(若在区间范围内有两相邻函数值符号相同而判定无根),若间隔h值太小,则影响计算速度18,二、简单迭代法,--------(2),将非线性方程,继续,--------(3),称(3)式为求解非线性方程(2)的简单迭代法,--------(1),化为一个同解方程,19,则称迭代法(3)收敛,否则称为发散4),如果将(2)式表示为,与方程(2)同解,收敛,20,例3.,解:,(1) 将原方程化为等价方程,发散,21,显然迭代法发散,(2) 如果将原方程化为等价方程,22,仍取初值,x2 = 0.9644x3 = 0.9940x4 = 0.9990x5 = 0.9998x6 = 1.0000x7 = 1.0000,依此类推,得,已经收敛,故原方程的解为,同样的方程不同的迭代格式有不同的结果,什么形式的迭代法 能够收敛呢?,迭代函数的构造有关,23,定理1.,24,证:,25,26,27,28,定理1指出,,只要,因此,当,迭代就可以终止,,只要构造的迭代函数满足,此时虽收敛但不 一定是唯一根,29,例4.,用迭代法求方程的近似解,精确到小数点后6位,解:,本题迭代函数有两种构造形式,因此采用迭代函数,30,d1 = 0.1000000d2 = -0.0105171d3 = 0.1156e-002d4 = -0.1265e-003d5 = 0.1390e-004d6 = -0.1500e-005d7 = 0.1000e-006,由于|d7| =0.1000e-006<1e-6,因此原方程的解为,x7 = 0.090525,x1 = 0.1000000x2 = 0.0894829x3 = 0.0906391x4 = 0.0905126x5 = 0.0905265x6 = 0.0905250x7 = 0.0905251,31,定理2,若存在区间 ，使,（1）方程 在 内有实根 ；,（2） 在 内连续且 。

则迭代法 在 附近具有局部收敛性（指存在 的一个邻域，使当 时， 收敛于 32,证明：,因为 在 内连续且 ，故在 内存在 的一个邻域 和小于1的正数 ，使 在 上存在且,这表明，若取 ，则 在 上满足定理1中的条件（1）；另一方面，当 （即 ）时（其中 介于 与 之间），这说明 在 上又满足定理1中的条件（2）因此当 时，迭代序列 收敛于 33,例5：,方程 有唯一实根 ，试分析迭代过程 的收敛性。

解：,这里 容易看出在区间 内连续且,由定理2知，所给迭代法 在 附近具有局部收敛性，只要 取的好（充分接近 ），则迭代法收敛34,三、Newton迭代法,将f(x)在初值处作Taylor展开,取线性部分作为f(x)的近似，有：,1、牛顿迭代公式,35,这样一直下去，我们可以得到迭代序列,Newton迭代的等价方程为：,36,例6.,用Newton迭代法求方程的根:,解:,由Newton迭代法,x0 =0.5;x1 =0.3333333333x2 =0.3472222222x3 =0.3472963532x4 =0.3472963553,迭代四次,精度达10-8,37,2、牛顿迭代的判定条件,定理3,对于方程 ，若存在区间 ，使,（1）在 内存在方程的单根 ；,（2） 在 连续则牛顿迭代法在 附近具有局部收敛性证明：,易知牛顿迭代法的迭代函数为：,38,定理4,对于方程 ，若存在区间 ，使,39,40,Newton迭代法,需要求每个迭代点处的导数,复杂！,--------(12),--------(13),这种格式称为简化Newton迭代法,精度稍低,,3 弦割法,41,则Newton迭代法变为,--------(14),这种格式称为弦截法,,收敛阶约为1.618,几何意义,42,例7.,用简化Newton法和弦截法解例(5)中方程的根，,解:,由简化Newton法,并和Newton 迭代法比较,由弦截法,43,x0=0.5x1= 0.3333333333x2 = 0.3497942387x3 = 0.3468683325x4 = 0.3473702799x5 = 0.3472836048x6 = 0.3472985550x7 = 0.3472959759x8 = 0.3472964208x9 = 0.3472963440x10 = 0.3472963572x11 = 0.3472963553,x0=0.5;x1=0.4;x2 = 0.3430962343x3 = 0.3473897274x4 = 0.3472965093x5 = 0.3472963553x6 = 0.3472963553,简化Newton法,由弦截法,要达到精度10-8,简化Newton法迭代11次,弦截法迭代5次,Newton迭代法迭代4次,44,无论前面哪种迭代法：,Newton迭代法,简化Newton法,弦截法,Newton迭代法,x0 = 2x1 = -3.54x2 = 13.95x3 = -279.34x4 = 122017,。