《山东大学数值分析课第4章 解非线性方程课件》由会员分享，可在线阅读，更多相关《山东大学数值分析课第4章 解非线性方程课件（38页珍藏版）》请在金锄头文库上搜索。
1、第四章 解非线性方程和方程组的迭代法,简介（Introduction）,在实际应用中有许多非线性方程的例子，例如： (1) 在光的衍射理论（the theory of diffraction of light)中,我们需要求 x tan x = 0 的根 (2) 在行星轨道( planetary orbits)的计算中,对任意的a和b，我们需要求 x a sin x = b 的根 (3) 在数学中，需要求n次多项式 xn+ a1 xn-1+.+an-1 x + an 0的根,求 f (x) = 0 的根,本章目的：讲述用于实际计算中求 f (x) = 0 的根的近似值的几种常用方法。,方程根的
2、数值计算大致可以分为三个步骤： (1)判断根的存在性； (2)确定根的分布范围(根的隔离)； (3)根的精确化。,根的隔离,1. 分析法：利用对函数 f (x) 的各种性质的分析来确定根的分布范围。,例：试确定f (x) = x3- 6x2 + 9x-1=0各根的分布范围。 隔根区间为(0,1)、(1,3)、(3,4),2. 逐步搜索法： 先确定方程 f (x) = 0的所有实根所在的区间a , b，再按照选定的步长 h =(b a )/n，取点 xk = a + k h ( k =0,1,2,., n)，逐步计算函数值 f (xk), 依据函数值异号及实根的个数确定隔根区间. 必要时可以调整
3、步长 h, 总可以把隔根区间全部找出.,代数方程根的模上下界定理：,例：求方程 x3-3.2 x2 +1.9 x +0.8 = 0 的隔根区间。 解：设方程的根为 由 = max |-3.2| , |1.9| , |0.8| = 3.2 ; v = (1/0.8) max1, |-3.2| , |1.9| = 4,得： 0.2 | | 4.2 即： -4.2 -0.2 , 0.2 4.2 取 n = 8 , h = 0.5 , 计算 f ( xk),由上表可知隔根区间为 -0.7 , -0.2 , 1.2 , 1.7 , 1.7 , 2.2,3. 图解法： 由函数图像来确定根的大体位置。,4.
4、1 二分法(对分区间法) (Bisection Method ),原理：若 f (x) Ca, b单调，且 f (a) f (b) 0，则 f (x) 在 (a, b) 上有且仅有一实根。,基本思想：通过计算隔根区间的中点，逐步将隔根区间缩小，从而得到方程的近似根数列 xn 。,(1) 先将a , b等分为两个小区间,分点记为x0=(a + b)/2, 判断根属于哪个小区间,舍去无根区间保留有根区间a 1, b1.即,若 f (x0)=0, 则x0= x*. 设 f (x0) 0, 若 f (a) f (x0)0, 则x* (a , x0), 这时令a1= a , b1= x0 ; 否则, x
5、* (x0 , b), 此时令a1= x0 , b1=b. 总之, 可以得到x*所在的新区间a1 , b1, 其长度为a , b的一半.,二分法的步骤：,对区间a1, b1 实施上述同样的过程, 得中点 x1=(a1+ b1)/ 2 和x*的新区间a2, b2, 如此继续下去, 则得一系列有根区间: a0 , b0=a , b , a1 , b1 , a2 , b2 , . , ak , bk , ,其中 bk-ak= (bk -1-ak -1) / 2 . 因此 bk-ak= (b- a ) / 2k , 当k +时, 有根区间ak , bk 最终必收敛于一点, 该点就是所求方程的根x*.,
6、把每次二分后的有根区间ak , bk 的中点xk=(ak+bk ) / 2作为根x*的近似值, 则可得一个根的近似值序列 x0 , x1 , x2 , . , xk , . 该序列的极限即为x* .,误差 分析：,第 k+1 步产生的 xk 有误差,(1) 对于给定的精度 ,可估计二分法所需的步数 k ：,停机条件（termination condition ）或误差控制方法：,(2) 事后估计误差. 先对分, 再判断所得中点是否满足,(3) 用不等式 控制误差。,例1 用二分法求 在(1,2)内的根，要求绝对 误差不超过 解： f (1)=-50 - (1,2) + f (1.5)0 (1,
7、1.5) f (1.25)0 (1.25,1.375) f (1.313)0 (1.360,1.368),例2: 求方程 f (x)= x 3 e -x = 0的一个实根。 解： 因为 f (0)0 . 故 f (x)在(0,1)内有根. (a , b)=(0 , 1 ), 计算结果如表： ka bk xk f (xk) 符号 00 1 0.5000 10.5000 0.7500 20.7500 0.8750 3 0.87500.8125 4 0.81250.7812 5 0.7812 0.7656 60.7656 0.7734 7 0.7734 0.7695 8 0.7695 0.7714
8、90.7714 0.7724 100.7724 0.7729 取x10= 0.7729，误差为| x* - x10|1/ 211 .,Remark1：求奇数个根,Find solutions to the equation x3 - 6x2 +10 x 4 = 0,on the intervals 0, 4，Use the bisection method to compute a solution with an accuracy of 107. Determine the number of iterations to use.,0,1, 1.5, 2.5 and 3,4， 利用前面的公式
9、可计算 迭代次数为k = 23.,Remark2: 要区别根与奇异点,Consider f (x) = tan x on the interval (0,3). Use the 20 iterations of the bisection method and see what happens. Explain the results that you obtained.（如右图）,Remark3: 二分法不能用来求重根, 且收敛速度较慢.,优点: 对函数的性质要求低,程序简单, 易操作.,4.2 简单迭代法,基本思想：先将方程f (x)=0改写成某种等价形式, 由等价形式构造相应的迭代公式,
10、 然后选取方程的某个初始近似根 x0 , 代入迭代公式反复校正根的近似值, 直到满足精度要求为止.,具体做法：,(1) 把 f (x) = 0 改写成下列等价形式,(2) 构造迭代格式： , k=0,1,2,(3) 从给定的初始值x0出发, 按照迭代公式即可得一个数列 x0 , x1 , x2 , , xk , ,(4) 若有极限,则迭代公式收敛, 此时数列极限即为原方程的根,即,这里 (x) 称为迭代函数,注： f (x)=0 化为等价方程 x = (x)的方式是不唯一的, 故迭代格式也不唯一, 有的收敛, 有的发散.,(1) 如果将原方程化为等价方程,由此可见，这种迭代格式是发散的,取初值
11、,For example：2x3 x 1= 0,(2) 如果将原方程化为等价方程,仍取初值,依此类推,得 x3 = 0.9940 x4 = 0.9990 x5 = 0.9998 x6 = 1.0000 x7 = 1.0000,已经收敛,故原方程的解为 x = 1.0000,同样的方程 不同的迭代格式 有不同的结果,什么形式的迭代法能够收敛呢?,收敛性分析,定义: 若存在常数 (0 1) , 使得对一切 x1, x2 a , b , 成立不等式 | g(x1) - g(x2)| |x1 - x2| 则称 g (x)是a , b上的一个压缩映射, 称为压缩系数,考虑方程 x = (x) , (x)
12、 Ca, b, 若 (I) 当 xa, b 时， (x) a, b； (II) 在a , b上成立不等式: | (x1) - (x2) |x1 - x2| , (0 1) 则 (1) (x)在a , b上存在惟一不动点 x* (2) 任取 x0a , b，由 xk+1 = (xk) 得到的序列 xk (a , b) 收敛于x* 。 (3) k 次迭代所得到的近似不动点 xk 与精确不动点 x* 有有误差估计式：,定理4.2,证明： (x) 在a , b上存在不动点？, 不动点唯一？, 当k 时， xk 收敛到 x* ？,|x*- x |=| (x*) - (x )| |x*- x |. 因0
13、1, 故必有 x = x*,若有xa ,b,满足 (x)= x，则,|xk - x*|=| ( xk -1) - (x*)| | xk -1 - x*| 2 | xk -2 - x*| k | x0 - x*| 0 .,令G(x)= (x) -x, xa , b，由条件知G (a)= (a) - a0, G(b)= (b) - b0. 由条件知G(x)在a , b上连续，又由介值定理知存在 x* a , b，使G (x*)=0，即x*= (x*) .,可用 来控制收敛精度, 越小,收敛越快,(4) | xk - x*|=| ( xk -1) - (x*)| | xk -1 - x*| ( |
14、xk - xk -1|+| xk - x*| ), 故有 | xk - x*| /(1-) | xk - xk -1|. 这就证明了第一个估计式.,(5) | xk - xk -1| = | (xk -1) - (xk -2)| | xk -1 - xk -2| k -1| x1 - x0|,结合上一估计式可得 | xk - x*| k -1/(1- ) | x1 - x0| . 即第二个估计式成立,Remark：,定理条件非必要条件，而且定理4.2中的压缩 条件不好验证，一般来讲 若知道迭代函数 (x) C1a , b, 并且满足 | (x)| 1,对任意的 x a , b, 则 (x)是a
15、 , b上的压缩映射.,例3: 已知方程 2x 7 - lgx0，求方程的含根区间，考查用迭代法解此方程的收敛性。,解：在这里我们考查在区间3.5,4的迭代法的收敛性,很容易验证：f (3.5)0 将方程变形成等价形式：x( lg x + 7 ) / 2,由定理4.2知，迭代格式 xk+1( lg xk+7)/2在3.5,4内收敛 .,局部收敛,Def : (局部收敛) 设x*为 的不动点,若存在x*的一个闭邻域U( x*,)=x*-, x*+( 0), 使得对任意x0 U( x*,),由迭代格式 xk+1= (xk) ( k = 0,1, 2,)产生的序列 xk 都收敛于x*, 则称迭代过程
16、 xk+1= (xk) 在的闭邻域U( x*,)内是局部收敛的.,定理4.3: 设x*为 的不动点, (x)与 (x)在包含x*的某邻域U( x*) (即开区间)内连续, 且| ( x*)| L 1, 则迭代格式 xk+1= (xk) ( k = 0,1, 2,) 具有局部收敛性.,证明略,We dont know x*, how do we estimate the inequality？,例4: 用一般迭代法求x3- x -1=0 的正实根x*,解: 将方程改写成,则迭代函数为,易知: (x)在包含x*的某邻域U(x*) 内连续, 且| (x*)|1 . 因此迭代格式 在x*附近收敛.,例5:
