数值分析chap4.ppt

1、第四章 非线性方程数值求解 Numerical solution of nonlinear equation, 4.1 一元方程求根 Root-finding problem for nonlinear equation in one variable,1. 问题 Problem,考虑单变量非线性方程 f(x)=0 (1) 的求根问题，这里,The basis problems is to find a root or solution of an equation of the form f(x)=0 by numerical methods .,2. 预备知识 Preliminary,满足

2、函数方程 f(x)=0 的x称为方程(1)的根，或称为函数f(x)的零点。如果函数(x)可分解为 (x)=(xs)mg(x) 且g(s )0,则称s是(x)的m重零点或(x)=0的m重根。当m=1时，称s是(x)的单根 或单零点。,A root of the equation (1) is also called a zero of the function f.,若f(x)不是x的线性函数, 则称(1)为非线性方程, 特别地, 若f(x)是n次多项式，则称(1)为n次多项式方程或代数方程；若f(x)是超越函数，则称(1)为超越方程。,Specially, when f(x) is n-deg

3、ree Polynomial , then the equation (1) is called algebra equation. That is,（1.2）,理论上已证明，对于次数n=4的多项式方程,它的根可以用公式表示,而次数大于5的多项式方程,它的根一般不能用解析表达式表示.因此对于f(x)=0的函数方程,一般来说,不存在根的解析表达式,而实际应用中,也不一定必需得到求根的解析表达式,只要得到满足精度要求的根的近似值就可以了。,定理1.(根的存在定理) 假设函数y=f(x)Ca,b,且f(a)f(b)0, 则至少存在一点x (a,b)使得f(x )=0. (并称区间(a,b)为有根区间

4、). 定理2 假设函数y=f(x)在a,b上单调连续,且f(a)f(b)0, 则恰好只存在一点x (a,b)使得 f(x )=0 定理3 假设函数y=f(x)在x=s的某一邻域内充分可微，则s是方程f(x )=0的m重根的充分必要条件是,求根的区间(1) 画图法(2) 逐步搜索法,画出y = f (x)的略图，从而看出曲线与x轴交点的大致位置。 也可将f (x) = 0分解为1(x)= 2(x)的形式， 1(x)与 2(x)两曲线交点的横坐标所在的子区间即为含根区间。 例如xlgx 1 = 0 可以改写为lgx=1/x 画出对数曲线y=lgx,与双曲线y= 1/x,它们交点的横坐标位于区间2,

5、3内,(1) 画图法,0,2,3,y,x,对于给定的f (x)，设有根区间为A,B，从x0=A出发，以步长h=(B-A)/n(n是正整数)，在A,B内取定节点：xi=x0ih (i=0，1，2，n)，从左至右检查f (xi)的符号，如发现xi与端点x0的函数值异号，则得到一个缩小的有根子区间xi-1,xi。 用逐步搜索法进行实根隔离的关键是选取步长h 要选择适当h ，使之既能把根隔离开来，工作量又不太大。,(2) 逐步搜索法,0,0,x,A,B,计算步骤,（1）x0=a (2) 若f(x0)f(x0 +h)0,则x0 , x0 +h为含根子区间，取x0 或 x0 +h为初始近似根，否则转（3）

6、。 （3） x0 = x0 +h ，转（2）。,由此可知方程的有根区间为,3. 二分法 Bisection,常用的求根方法分为区间法和迭代法两大类。 给定方程f(x)=0,设f(x)在区间a,b连续,且f(a)f(b)0,则方程f(x)在(a,b)内至少有一根,为便于讨论,不妨设方程f(x)=0在(a,b)内只有一个(重根视为一个)实根，求满足精度要求的近似值实根。,Suppose f is a continuous function defined on the interval a,b, with f(a) and f(b) of opposite sign. By the interme

7、diate value theorem, there exists a zero for the function f. For simplicity, we assume that the root in this interval is unique.,二分法概念及基本思想 概念： 二分法也称对分区间法、对分法等， 是最简单的求根方法，属于区间法求根类型。 基本思想：利用连续函数的零点定理，将含根区 间逐次减半缩小，就可以构造出收敛点列 来 逼近根x。,The binary-search method calls for a repeated halving of subintervals

8、 Of a,b and, at each step, locating the half containing the zero of f . Therefore, a Sequence is constructed to convergent to the root.,构 造 原 理 定理1.(根的存在定理) 这个原理指出了根的存在区间可由两端点处的函数值是否反号确定，那么注意到，将含根区间分为两个长度相等的子区间后，在这两个子区间上也可利用零点原理确定根在那个子区间上，如此继续下去就达到将含根区间逐步缩小的目的，此时，在这一些相互包含的子区间中构造收敛的数列x_k将它收敛于根x ，见下图,

9、图7-1,详细过程 the process of Bisection method,When to stop,?,这不能保证精确值的精度！,x,x*,Because,A good stopping criterion is,对于给定的精度 ,可估计二分法所需的步数 k ：,An other good stopping criterion is,二分法的优缺点(Advantages and drawbacks),简单并保证收敛; always converges 对f (x) 要求不高(只要连续即可) . f is only required to be continuous 无法求复根 和偶重

10、根 收敛慢 (仅与一个以 1/2为比值的等比级数相同) converge slowly 调用一次求解一个a, b间的多个根无法求得,确定根所在的范围a,b对有的函数也是一 件困难的事。所幸的是，在实际应用中，根 据其物理或工程的背景，在绝大部分场合是 不困难的。对给定的函数也有确定范围的方 法。,注：用二分法求根，最好先给出 f (x) 草图以确定根的大概位置。或用搜索程序，将a, b分为若干小区间，对每一个满足 f (ak)f (bk) 0 的区间调用二分法程序，可找出区间a, b内的多个根，且不必要求 f (a)f (b) 0 。,Example: 求方程,在区间 内的一个实根，要求准确到

11、小数点后第2位.,取 的中点 ，将区间二等分，,即 与 同号，,故所求的根 必在 右侧.,如此反复二分下去, 按误差估计（1.3）式,欲使,这里 ，,而,由于,这时应令 ，从而得到新的有根区间,只需 ，,计算结果如表7-1.,即只要二分6次，便能达到预定的精度.,二分法是计算机上的一种常用算法，计算步骤如下：,步骤2 二分,计算 在区间中点 处的值,若 ，则以 代替 ，否则以,代替 .,步骤1 准备 计算 在有根区间 端点处的 值,步骤3 判断 若 ，则 即是根， 计算过程结束，,此时中点 即为所求近似根.,不动点迭代法 Fixed-Point Iteration,f (x) = 0,f (x

12、) 的根, (x)的不动点,x= (x),主要思想：,从一个初值 x0 出发，计算 x1 = (x0), x2 =(x1), , xk+1 = (xk), 若 收敛，即存在 x* 使得 ，且 连续，则由 可知 x* = (x* )，即x* 是 的不动点，也就是f 的根。,迭代过程的几何表示,y,x2,x1,需要讨论的问题 Problem,首先期望每个xk都在 (x)的定义域上,保持有界而且收敛到精确解; 如何选取适合的迭代函数 (x) ; 迭代函数 (x)迭代满足什么条件,迭代序列收敛到精确解, 收敛速度如何; How to choose the iterative function (x)

13、so that the iterative method converges?,Example: 求方程,设将原方程改写成下列形式,在 附近的根,据此建立迭代公式,各步迭代的结果见下表,建立迭代公式,仍取迭代初值 ，则有,结果会越来越大，不可能趋于某个极限.,但若采用方程另一种等价形式,不动点的存在性定理Existence theorem of fixed point,定理1,Theorem : If and for , In addition, with 0L1. Then the fixed point in a,b is unique.,注:（Remark）,条件(2)可用更强更便于应用

14、的条件代替: the condition (2) can be replaced by,不动点迭代收敛性定理the convergence theorem of the fixed-point iteration,定理2,设 满足定理1中的两个条件，,对任意 ，,由得到的迭代序列 收敛到,的不动点 ，并有误差估计,Theorem: if (x)satisfied the hypotheses of theorem 1, Then for any x_0 in a,b, the sequence defined by Fixed-point iteration converges to uniq

15、ue fixed Point.,（*）,注:（Remark）,1。迭代终止的判断准则 stopping criterion,2。由（*）式可知 L越小，收敛越快,3。定理条件非必要条件，并不易检验。实际应用时 通常只在不动点的邻近考察其收敛性，即局部收敛性.,The rate of convergence depends on the factor Ln. The smaller the value of L, the faster the convergence.,定义：,对任意 ，,且收敛到 ，,迭代（2.2）产生的序列,则称迭代法（2.2）局部收敛.,设 有不动点 ，,如果存在 的某个邻

16、域,设 为 的不动点，,定理3 ：,Because We dont know x*,how To estimate the inequality？,例,用不同方法求方程 的根,解,这里,其不动点为,由此构造不同的迭代法：,可改写为各种不同的等价形式,从计算结果看到迭代法（1）及（2）均不收敛，且它们均不满足定理3中的局部收敛条件.,迭代法（3）和（4）均满足局部收敛条件，且迭代法（4）比（3）收敛快，因在迭代法（4）中 .,收敛阶(描述收敛速度) the order of convergence,则称该迭代过程是p阶收敛的.,特别地, 时 称线性收敛linearly convergent;,时

17、称超线性收敛;superlinearly,时称平方收敛. Quadratically convergent,定义,判别收敛阶的两定理,定理4：如果 是 的不动点，在定理3的条件下还有 ， 则不动点迭代法是线性收敛。,Theorem 4: For the fixed point of , under the hypotheses of theorem 3, if then the fixed-point Iterative method converges only linearly to the unique Fixed point.,定理5：对于迭代过程 ，如果 在所求根 的邻近连续，并且:

18、 则该迭代过程在点 邻近是P阶收敛的。,上述定理说明，迭代过程的收敛速度依赖于迭代函数 的选取.,Remark: The rate of convergence of the iterative method Depends on (x).,牛顿法 Newton Method,Taylor 展开式.,An important means of introducing Newtons method is based on Taylor Polynomials.,设已知方程 有近似根 （假定 )，,将函数 在点 展开，有,于是方程 可近似地表示为,这是个线性方程，记其根为 ，所以：,这就是牛顿(Newton)法.,其迭代函数为,牛顿法的几何解释 The geometrical explanation,设 是根