数值计算方法 (第2章 非线性方程与方程组的数值解法)

第2章非线性方程与方程组的数值解法1

本章重点介绍求解非线性方程的几种常见和有效的数值方法,同时也对非线性方程组求解,简单介绍一些最基本的解法.无论在理论上,还是在实际应用中,这些数值解法都是对经典的解析方法的突破性开拓和补充,许多问题的求解,在解析方法无能为力时,数值方法则可以借助于计算机出色完成.2二分法求非线性方程

确定方程的有根区间(等长扫描法)

计算根的近似值（二分法）的根的方法分为两步：3概念：有根区间：存在根隔根区间：唯一根4首先确定有限区间：依据零点定理。设，且，则方程在区间上至少有一个根。如果在上恒正或恒负，则此根唯一。5等步长扫描法求有根区间

用计算机求有根区间：等步长扫描法。设h>0是给定的步长，取，若则扫描成功；否则令，继续上述方法，直到成功。如果则扫描失败。再将h缩小，继续以上步骤。6等步长扫描算法

算法：（求方程的有根区间）(1)输入；(2)；(3)，若输出失败信息，停机。(4)若。输出，已算出方程的一个根，停机。7等步长扫描算法(5)若。输出为有根区间，停机(6)，转3）注：如果对足够小的步长h扫描失败。说明：在内无实根或8二分法

用二分法(将区间对平分)求解。令若，则为有根区间，否则为有根区间记新的有根区间为，则且9二分法对重复上述做法得且

10二分法设所求的根为，则即取为的近似解

11求方程f(x)=0的根的二分法算法12求方程f(x)=0的全部实根的二分法算法13求方程f(x)=0的全部实根的二分法算法14例题例1设方程解：取h=0.1,扫描得：又即在有唯一根。15一般迭代法2.2.1迭代法及收敛性

对于有时可以写成形式如：16迭代法及收敛性考察方程。这种方程是隐式方程，因而不能直接求出它的根。

但如果给出根的某个猜测值，代入中的右端得到，再以为一个猜测值，代入的右端得反复迭代得17迭代法及收敛性若收敛，即则得是的一个根18迭代法的几何意义交点的横坐标y=x19简单迭代法

将变为另一种等价形式。选取的某一近似值，则按递推关系产生的迭代序列。这种方法算为简单迭代法。20例题例2.2.1试用迭代法求方程在区间(1，2)内的实根。解：由建立迭代关系

k=0,1,2,3…….计算结果如下:21例题精确到小数点后五位22例题但如果由建立迭代公式仍取，则有，显然结果越来越大，是发散序列23迭代法的收敛性定理（压缩映像原理）设迭代函数在闭区间上满足（1）（2）满足Lipschitz条件即有且。24压缩映像原理则在上存在唯一解，且对，由产生的序列收敛于。

25压缩映像原理证明：不失一般性,不妨设否则a或b为方程的根。首先证明根的存在性令

26压缩映像原理则，即由条件2）是上的连续函数是上的连续函数。故由零点定理在上至少有一根27压缩映像原理再证根的唯一性假设有均为方程的根则因为0<L<1，所以只可能，即根是唯一的。28压缩映像原理最后证迭代序列的收敛性

与n无关，而0<L<1即29压缩映像原理误差估计若满足定理条件，则

这是事后估计，也就是停机标准。L越小，收敛速度越快。

这是事前估计。选取n，预先估计迭代次数。

3031例题例证明函数在区间[1，2]上满足迭代收敛条件。证明：32例题

33例题若取迭代函数，不满足压缩映像原理，故不能肯定收敛到方程的根。34简单迭代收敛情况的几何解释35362.2.2Steffensen加速收敛法对收敛缓慢的迭代格如何加快收敛速度？一个简便易行，而又能大幅度提高收敛速度的方法。372.2.2Steffensen加速收敛法此部分主要有两个内容1.Aitken加速收敛迭代法2.Steffensen加速收敛方法38Aitken加速收敛迭代法概述39Aitken加速收敛迭代法概述40对选取的gi(x)，取初始近似值x0=1.5，迭代计算结果列在表。（a）(b)(c)(d)(e)01．51．51．51．51．51-0.8750.81651.286953771.348399731.373333326.7322.99691.402540801.367376371.365262013-469.71.345458381.36495701.3652300141.03×1081.375170251.3652647581.365916731.3652300291.364878221.36523001231.36522998251.3652300141简单观察迭代过程，(a)(b)不定，(c)(d)(e)都收敛，但收敛速度相差很大。例：对g4(x)产生的迭代序列（表中(d)对应列）进行Aitken加速。解:利用计算公式得比较可得，与x8的误差差不多。

42Steffensen加速收敛法概述在Aitken加速中，只要有三个相邻点就可以进行加速。把简单迭代与Aitkn加速方法结合起来，建立称之为Steffenson方法的迭代过程。43Steffensen加速收敛法概述由上式产生的序列称为Steffensen迭代序列。44Steffensen加速收敛法概述Steffenson方法不必计算导函数，每迭代步的工作量略多于二步简单迭代的工作量，而收敛速度达二阶。45一般迭代法求解46Steffensen加速收敛472.2.2Steffensen加速收敛法自学为主。不做要求。482.2.2Steffensen加速收敛法迭代法收敛的阶定义设序列收敛到，若有实数和非零常数C，使得其中，，则称该序列是p阶收敛的，C称为渐进误差常数。

49迭代法收敛的阶当p=1时，称为线性收敛；当p>1时，称为超线性收敛；当p=2时，称为平方收敛或二次收敛。50迭代法收敛的阶定理设是方程的不动点，若为足够小的正数。如果且，则从任意出发，由产生的序列收敛到，当时敛速是线性的。

51迭代法收敛的阶证明：满足压缩映像原理52迭代法收敛的阶

敛速是线性的线性收敛到。53Steffensen迭代格式由线性收敛知当n充分大时有

即54Steffensen迭代格式展开有：55Steffensen迭代格式已知，则，改成

n=0，1，2，…56Steffensen迭代格式也可以改写成其中迭代函数57Steffensen迭代法收敛的充要条件定理2.2.358Steffensen迭代法收敛的充要条件证明：必要性59Steffensen迭代法收敛的充要条件充分性60Steffensen算法的收敛速度

61Steffensen算法的收敛速度定理2.2.5在定理假设下，若

产生的序列至少平方收敛到。

62Steffensen算法的收敛速度63Steffensen算法的收敛速度

64Steffensen算法的收敛速度

65Steffensen算法的收敛速度由定理知至少以平方速度收敛到。也就是说：简单迭代法是线性收敛；Steffensen迭代至少平方以上收敛（加速收敛）。66例题例试用Steffensen算法求解方程解法一、取，由

n=0，1，2，…67例题取初值，计算结果如下：NXnYnZn01.51.3572088081.33086095911.3248991811.3247523791.32472449621.3247179571.3247179571.32471795768例题解法二、取，由对于该迭代函数在一般迭代法中是发散的，而Steffensen格式却是收敛的。

n=0，1，2，…69例题取初值，计算结果如下：NXnYnZn01.52.3751.23964843711.4162929751.8409219155.23887276921.3556504421.4913982792.31727069931.3289487771.3470628831.44435122441.3248044891.3251735441.32711728151.3247179441.3247181521.32471898061.32471795770Steffensen迭代格式几何解释

71Steffensen迭代算法

72Steffensen迭代算法

732.3Newton迭代法设x*是方程f(x)=0的根，又x0为x*附近的一个值，将f(x)在x0附近做泰勒展式：令，则

74Newton迭代法

去掉的二次项，有：即以x1代替x0重复以上的过程，继续下去得：75Newton迭代法

以此产生的序列{Xn}得到f(x)=0的近似解，称为Newton法，又叫切线法。76Newton迭代法几何解释

牛顿迭代法的几何意义77Newton迭代法几何解释类似，过点x1再做切线….78当做曲线上的点的引切线，该切线与x轴的交点横坐标即为牛顿迭代公式求得的xn+1，因此牛顿迭代法也称为牛顿且切线法。79例题例2.3.1用Newton法求的近似解。解：由零点定理。80例题81例设a>0，试用Newton法计算,并求的值。解：82Newton迭代法算法框图83Newton迭代法算法84Newton迭代法收敛性定理2.3.1设函数，且满足若初值满足时，由Newton法产生的序列收敛到方程在[a,b]上的唯一根。85Newton迭代法收敛性证明：根的存在性根的唯一性86Newton迭代法收敛性收敛性87Newton迭代法收敛性

88Newton迭代法收敛性89注：牛顿法的平方收敛是在根X*附近的性质，因此迭代初值必须足够靠近X*。应用中常把隔根区间取的如此之小，使其f(x)f”(x)>0，就能保证收敛。9091Newton迭代法收敛性推论在定理条件下，Newton迭代法具有平方收敛速度。92代数方程的Newton迭代法代数方程的Newton迭代法推导设n次代数方程用Newton迭代法求有限区间的实根，则要计算，一般采用秦九韶算法。93代数方程的Newton迭代法由Taylor展式94代数方程的Newton迭代法

9596代数方程的Newton迭代法同理

97代数方程的Newton迭代法比较x的同次幂系数得：故代数方程的Newton迭代公式98代数方程的Newton迭代法算法99

100弦截法Newton迭代法有一个较强的要求是且存在。因此，用弦的斜率近似的替代。101弦截法令y=0，解得弦与x轴的交点是坐标x2102弦截法103弦截法的几何解释(a)定端点弦截法