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

第二章非线性方程的数值解法

2.1二分法2.2一般迭代法2.3牛顿迭代法2.4弦截法第二章非线性方程的数值解法2.1二分法1（1）确定初始含根区间数值计算方法主要分为两大类。第一类是区间收缩法。

（2）收缩含根区间第二类是迭代法。（1）选定根的初始近似值（2）按某种原则生成收敛于根的近似点列（1）确定初始含根区间数值计算方法主要分为两大类。第一类是22.1二分法(对分法)

一、根的隔离将含根区间一个个隔开，找到根的范围，使每个区间只有一个根。

定理：对f(x)=0,f(x)在[a,b]上连续,f(a)f(b)<0且f(x)严格单调上升（或严格单调下降），则f(x)在[a,b]内仅有一根。1。利用零点存在定理2.1二分法(对分法)一、根的隔离将含根区间一个3非线性方程的数值解法ppt课件42。搜索法：2。搜索法：53。作图找出交点xy3。作图找出交点xy6二、对分法设f(x)在（a,b)上连续且f(x)=0在（a,b)内只有一个根1。算法二、对分法设f(x)在（a,b)上连续且f(x)=0在（a,72。收敛性根据精度终止计算。2。收敛性根据精度终止计算。83。误差控制3。误差控制9非线性方程的数值解法ppt课件10例2.1：试用二分法求的非零实根，使其误差小于10-2解：(1)根的隔离取h=0.5例2.1：试用二分法求11(2)预先算出计算步数(3)计算（用表格形式写出来）0(+)1.5(-)21.75+1.7521.875+1.87521.9375–1.8751.93751.90265+1.902651.93751.921875+51.921881.93751.92688+(2)预先算出计算步数(3)计算（用表格形式写出来）0122.1.3

二分法评述优点：简单可靠，易于编程实现，它对函数要求低，适用于的奇数重根情形。缺点：不能直接用于求偶重根，不能用于求复根，也难以向方程组推广使用，收敛速度慢。2.1.3

二分法评述优点：简单可靠，易于编程实现，它对132.2一般迭代法迭代法的算法思想为：(A)把（1）等价变换为如下形式(B)建立迭代格式(C)适当选取初始值x

0，递推计算出所需的解。一迭代法的算法思想

2.2一般迭代法迭代法的算法思想为：(A)把（1）等14或更一般地建立迭代格式或更一般地建立迭代格式15

例由此建立迭代格式也可建立迭代格式-----发散-----收敛例由此建立迭代格式也可建立迭代格式-----发散---16二迭代法的收敛性则称在内李普希兹连续。

定义2.1

设在某个区间

内，函数

满足下述李普希兹条件：命题得证。证则在内李普希兹连续。命题2.1

若在闭区间内连续且

二迭代法的收敛性则称在内17（1）首先用数学归纳法证明：

由假设知

又设，则

综上，由归纳法原理知，结论成立。

证定理2.1设x*=g(x*),g(x)在闭区间：内李普希兹连续，则对任何初值由迭代格式xk+1=g(xk)计算得到的解序列收敛于x*(这时我们称迭代格式xk+1=g(xk)在x*的邻域

上局部收敛）。（1）首先用数学归纳法证明：由假设知又设18因此，，定理得证。

反设存在矛盾。所以结论成立。2)迭代函数在x*附近李普希兹连续从而收敛的迭代格式统称为皮卡（Picard）迭代

(2)由（1）的结论和g(x)在

内李普希兹连续的假设，可递推得到

注1)g(x)在

内李普希兹连续的条件保证了x*为f(x)=0在

内的唯一根。

证因此，，定理19推论设x*=g(x*)，若g(x)在x*附近连续可微且，则迭代格式xk+1=g(xk)在x*附近局部收敛。

注由于x*事先未知，故实际应用时，代之以近似判则。但需注意，这实际上是假设了x0充分接近x*，若x0离x*较远，迭代格式可能不收敛。推论设x*=g(x*)，若g(x)在x20

定理2.2（非局部收敛定理）如果在上连续可微且以下条件满足：命题2.2

若在区间内，则对任何，迭代格式不收敛。

定理2.2（非局部收敛定理）如果21发散收敛证明所以该迭代格式在内不收敛，不可取。易知在x>0时g(x)单调增，故有2<g(2)<g(x)<g(3)<3故由定理2.2得：任取，该迭代格式收敛。发散收敛证明所以该迭代格式在内易知在x>0时g(x)22

三、迭代法的误差估计

故对正整数p，有三、迭代法的误差估计故对正整数p，有23由此，对给定的精度可进行由此，对给定的精度24（2）事后误差估计

(1)事前误差估计简单地代之以或

三、迭代法的误差估计

对给定的精度可进行（2）事后误差估计(1)事前误差估计简单地代之以或25例2.2试建立收敛的迭代格式求解x–e–x=0在x=0.5附近的一个根（ε=10-3）。解建立迭代格式00.560.564860.6065370.568440.5452480.566410.5797090.567560.56006100.5669150.57117例2.2试建立收敛的迭代格式求解x–e–x26

四、迭代法的收敛速度与加速收敛技巧

则称该迭代格式是p阶收敛的。p=1时称为线性收敛1<p<2时称为超线性收敛p=2时称为平方收敛。定义2.2设迭代格式的解序列收敛于的根，如果迭代误差当时满足渐近关系式四、迭代法的收敛速度与加速收敛技巧则称该迭代格式27对分法：线性收敛一般迭代法：线性收敛对分法：线性收敛一般迭代法：线性收敛28

2.3牛顿迭代法

一、牛顿迭代公式的构造

设f(x)在其零点附近连续可微，已知为的第k次近似值，则取的根作为的第k+1次近似值其迭代函数为牛顿迭代法2.3牛顿迭代法一、牛顿迭代公式的构造29几何意义：过点作函数y=f(x)的切线l：以切线l与x轴的交点作为的新近似值几何意义：过点作30二、牛顿迭代法的收敛性与收敛速度

定理2.3给定f(x)=0，如果在根附近f(x)二阶连续，且为f(x)=0的单根，则牛顿迭代法在附近至少是平方收敛的。证首先证明牛顿迭代法的收敛性：

因此由定理2.1的推论知，牛顿迭代法局部收敛。二、牛顿迭代法的收敛性与收敛速度定理2.3给31其次证明牛顿迭代法的收敛速度：整理得

可见，当时，牛顿迭代法为平方收敛；当时，牛顿迭代法超平方收敛。其次证明牛顿迭代法的收敛速度：整理得可见，当32例2.4试用牛顿迭代法求解在区间(2,3)内满足精度要求的根。相应于该方程的牛顿迭代公式为取x0=2，计算结果见表2-4。解0212.10.12.094568121-0.0054318792.094551482-0.0000166392.0945514820例2.4试用牛顿迭代法求解33牛顿迭代法评述

优点：是收敛速度比较快

缺点：(1)局部收敛，对初始值的要求比较高。为解决这一问题，可采用二分法来提供足够“好”的近似值作为迭代初值，或通过增加“下山”限制来放宽对初值的要求，即把牛顿迭代法修改为其中的选取使得（这称为“下山”限制）。该方法称为牛顿下山法。（2）当为重根时，牛顿迭代法仅仅线性收敛。牛顿迭代法评述优点：是收敛速度比较快缺点34（3）由于涉及的计算，导致了对函数的要求高，并增加了每一迭代步的计算量，这在一定程度上减弱了该迭代法收敛快的优越性，而且在向非线性方程组推广时，使计算量和对函数的要求大大增加。因此，人们致力于研究建立牛顿迭代法的修改格式以回避对函数导数值的计算。本章仅对非线性方程介绍一种较为有效的修改算法——弦截法。（3）由于涉及的计算，导35

2.4弦截法

弦截法计算思想是：若已知x*的两个近似值xk和xk-1，则以f(x)在xk与xk-1之间的平均变化率(差商)近似代替，据此把牛顿迭代法修改为几何意义是以过和两点做曲线的弦线l：以l与x轴的交点作为的新近似值2.4弦截法弦截法计算思想是：若已知36yoy=f(x)PQxyoy=f(x)PQx37该定理说明弦截法是超线性收敛的算法，也是局部收敛的方法，其迭代初始值亦可用二分法提供。定理2.4设f(x)在其零点x*的邻域内二阶连续，且对，则对，相应的弦截法是阶收敛的。该定理说明弦截法是超线性收敛的算法，也是局部38

例2.5试用弦截法求解在区间(2,3)内满足精度要求的根。

相应于该方程的弦截法公式为解取计算，结果见表2-5。例2.5试用弦截法求解39

例2.6试讨论函数方程的根的分布情况，分别用牛顿迭代法和弦截法求其最小正根，使误差小于，并比较它们的工作量

因为x-2-1012f(x)-++-+故f(x)在(0,1)内有惟一零点，所以最小正根<1。若采用牛顿迭代法计算，则取计算，结果见表2—7。解在(0,1)内，例2.6试讨论函数方程40若采用弦截法计算，则取，解得的结果见表2-8。若采用弦截法计算，则取41例1：用简单迭