《数值分析 第7章 非线性方程的数值解法..ppt;ppt》由会员分享，可在线阅读，更多相关《数值分析 第7章 非线性方程的数值解法..ppt;ppt（69页珍藏版）》请在金锄头文库上搜索。
1、1,在科学研究的数学问题中更多的是非线性问题，它们又常常归结为非线性方程或非线性方程组的求解问题。,2,第7章 非线性方程与方程组的数值解法/* Numerical Solutions of Nonlinear Equations*/,7.1 方程求根与二分法 7.2 不动点迭代法及其收敛性 7.3 迭代收敛的加速方法 7.4 牛顿法 7.5 弦截法与抛物线法 7.6 求根问题的敏感性与多项式的零点7.7 非线性方程组的数值解法,3,7.1 方程求根与二分法,7.1.1 引言,（1.1）,单变量非线性方程的一般形式,其中 也可以是无穷区间.,f(x)是高次多项式函数或超越函数,（1.2）,如果
2、函数 是多项式函数，即,其中 为实数，则称方程(1.1)为 次代数方程.,超越函数,不能表示为多项式的函数,如 (x)=3x5-2x4+8x2-7x+1,(x)=e2x+1-xln(sinx)-2,高次代数方程,超越方程,4,若 是 的 重零点，且 充分光滑，则,次方程在复数域有且只有 个根（含重根， 重根为 个根）.,超越方程,它在整个 轴上有无穷多个解，若 取值范围不同，解也不同，因此讨论非线性方程(1.1)的求解必须强调 的定义域，即 的求解区间,如果实数 满足 ，则称 是方程(1.1)的根，或称 是 的零点.,若 可分解为,其中 为正整数，且 则称 为方程(1.1)的 重根，或 为 的
3、 重零点， 时为单根.,结论,5,通常方程根的数值解法大致分为三个步骤进行：,非线性问题一般不存在直接的求解公式，要使用迭代法.,本章将介绍常用的求解非线性方程的近似根的几种数值解法,判定根的存在性。即方程有没有根？如果有根，有几个根？, 确定根的分布范围。即将每一个根用区间隔离开来，这个过程实际上是获得方程各根的初始近似值。, 根的精确化。将根的初始近似值按某种方法逐步精确化，直到满足预先要求的精度为止.,6,如何求方程 的有根区间？,设 f(x)Ca, b, 且 f(a) f(b)0, 存在(a,b) ，使 f()=0.,根的存在性定理闭区间上连续函数的介值定理,有根区间,如果f(x)在a
4、,b上还是单调递增或递减的，则f(x)=0仅有一个实根。,(1)描图法,画出y=f(x)的略图，从而看出曲线与x轴交点的大致位置。也可将f(x)=0等价变形为g1(x)=g2(x)的形式，y=g1(x)与y=g2(x)两曲线交点的横坐标所在的子区间即为含根区间。,例1 求方程3x-1-cosx=0的有根区间。,方程等价变形为3x-1=cosx，,y=3x-1与y=cosx的图像只有一个交点位于0.5，1内。,7,对 的根进行搜索计算，,例2 求方程 的有根区间.,由此可知方程的有根区间为,(2)逐步搜索法,先确定方程f(x)=0的所有实根所在的区间为a,b,从x0=a 出发,以步长 h=(b-
5、a)/n 其中n是正整数，在a,b内取定节点： xi=x0ih (i=0,1,2，n) 计算f(xi)的值,依据函数值异号及实根的个数确定有根区间,通过调整步长，总可找到所有有根区间。,解,8,7.1.2 二分法,求解方程f(x)= 0的近似根的一种常用的简单方法。,原理,基本思想,设函数f(x)在闭区间a,b上连续,且f(a)f(b)0,则 f(x)= 0在(a,b)内必有实根区间。,逐步将区间二等分, 通过判断区间端点f(x)的符号, 逐步将有根区间缩小, 直至有根区间足够地小, 便可求出满足精度要求的近似根。,具体做法,9,以此类推,由二分法的过程知,(1),(2),(3),作为根的近似
6、,可得一个近似根的序列,10,（1.3）,且,(4),只要二分足够多次（即 充分大），便有,这里 为预定的精度.,要使,解：,例3 用二分法求方程 在区间 上的根，误差限为 ，问至少需对分多少次？,11,二分法的算法,步骤1 准备 计算 在有根区间 端点处的值,步骤2 二分 计算 在区间中点 处的值,步骤3 判断 若 ，则 即是根，计算过程结束，否则检验.,12,13,例4 求方程,在区间 内的一个实根，要求准确到小数点后第2位.,欲使,只需 ，即只要二分6次，便能达到预定的精度.,解,得到新的有根区间,14,二分法对多个零点的情况，只能算出其中一个零点。即使 f(x)在a, b上有零点，也未
7、必有 f(a) f(b)0。,不管有根区间多大,总能求出满足精度要求的根,且对函数f(x)的要求不高,只要连续即可,计算亦简单。,优点,缺点,注：用二分法求根，最好先给出 f (x) 草图以确定根的大概位置。或用搜索程序，将a, b分为若干小区间，对每一个满足 f (ak)f (bk) 0 的区间调用二分法程序，可找出区间a, b内的多个根，且不必要求 f (a)f (b) 0 。,15,7.2 不动点迭代法及其收敛性,7.2.1 不动点与不动点迭代法/*Fixed-Point Iteration*/,（2.1）,若 满足 ，则 ；反之亦然，称为函数 的一个不动点.,求 的零点就等价于求 的不
8、动点.,基本思想,（2.2）,称为迭代函数.,得到的序列 有极限,如果对任何 ，由迭代,不动点迭代法,16,则称迭代法收敛，且 为 的不动点，,不动点迭代是一种逐次逼近的方法,用某个固定公式反复校正根的近似值,使之逐步精确化，最后得到满足精度要求的结果。,对预先给定的精度要求，只要某个k满足,即可结束计算并取,迭代终止的判定,17,几何意义,交点的横坐标,y=x,18,19,例5 求方程,（2.3）,在 附近的根,设将方程改写成,建立迭代公式,解,各步迭代的结果如下表,即为所求的根.,如果仅取6位数字，结果 与 完全相同，,发散,说明：迭代函数不唯一，迭代点列可能收敛，也可能发散，迭代收敛与否
9、不仅与迭代函数有关，还与初始点有关。,20,7.2.2 不动点的存在性与迭代法的收敛性,不动点的存在唯一性定理,证明,存在性,若 或 ，则不动点为 或 ，,因 ，,以下设 及 ，,定义函数,显然 ，,且,由零点定理知存在 ,使 ,即,21,唯一性,设 都是 的不动点，,故 的不动点是唯一的.,则由,即为 的不动点.,得,矛盾.,（2.5）,L 越 收敛越快,小,事前估计：选取k，预先估计迭代次数。,22,证明,设 是 在 上的唯一不动点，,由条件，可知,因 ，故当 时序列 收敛到 .,又由,误差估计,收敛性,由,（2.6）,得,反复递推得,23,迭代过程的控制,只要相邻两次计算结果的偏差 足够
10、小，即可保证,近似值 具有足够精度.,事后估计,事前估计：选取k，预先估计迭代次数。,注：,定理1、2的条件(2)可替换为,（2.7）,如果 且对任意 有,则由中值定理可知对 有,24,例5,又因 ，,而当 时， ，在区间 中 不满足定理条件.,当 时，,在区间 中，,所以迭代法是收敛的.,25,7.2.3 局部收敛性与收敛阶,迭代序列 在区间 上的收敛性，,全局收敛性,定义1 设 有不动点 ,如果存在 的某个邻域 对任意 ，迭代 产生的序列 且收敛到 ，则称迭代法局部收敛.,定理3 设 为 的不动点， 在 的某个邻域连续，且 ，则迭代法 局部收敛.,局部收敛性,证明,由连续函数的性质，存在
11、的某个邻域,使对于任意 成立,所以，,对于任意 ，,总有 。,因为,26,迭代序列的收敛速度,例6 用不同方法求方程 的根,解,构造不同的迭代法,27,取 ，对上述4种迭代法，计算三步所得的结果如下表.,从计算结果看到迭代法（1）及（2）均不收敛，且它们均不满足定理3中的局部收敛条件.,注意 .,迭代法（3）和（4）均满足局部收敛条件，且迭代法（4）比（3）收敛快，因在迭代法（4）中 .,28,求方程xex-1=0在0.5附近的根,精度要求=10-3。,可以验证方程xex-1=0在区间0.5,0.61内仅有一个根。,例7,改写方程为x=e-x ,建立迭代格式,由于(x)=e-x ,在0.5,0
12、.61上有|(x)|e-0.50.6 1，且(x)0.5,0.61，所以迭代法收敛。,取x0=0.5,得,解,29,所以,取近似根x10=0.56691满足精度要求。,如果精度要求为=10-5, 则由,可知,需要迭代20次。,实际上,方程在区间0.55,0.6上有唯一根，而在区间0.55,0.6上有|(x)|e-0.550.581。若取L=0.58，则有,注意：这里迭代次数20是充分的但不是必要的。,可知, 只需迭代17次。,30,迭代法的收敛阶/*the order of Convergence*/,特别地, 时称线性收敛，,时称超线性收敛，,时称平方收敛.,数p的大小反映了迭代法收敛的速度
13、的快慢，p愈大，则收敛的速度愈快，故迭代法的收敛阶是对迭代法收敛速度的一种度量。,设(x) 连续,|ek+1|=|xk+1-x|=|(xk)-(x)|=|(k)|ek|,当(x)0时,有,所以,当(x)0时,简单迭代法只具有线性收敛。,31,由于 ，可以断定迭代过程 局部收敛.,将 在根 处做泰勒展开，,则有,证明,由上式得,因此,当 时有,（2.9）,32,迭代过程的收敛速度依赖于迭代函数 的选取.,如果当 时 ，,注：,则该迭代过程是线性收敛.,33,7.3 迭代收敛的加速方法/* Accelerating Method*/,7.3.1 埃特金加速收敛方法,设 是根 的某个近似值，用迭代公式迭代一次得,由微分中值定理,其中 介于 与 之间.,假定 改变不大，,（3.1）,若将校正值 再迭代一次，又得,
