山东大学数值分析课第4章解非线性方程-1.ppt

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*附近收敛.,例

17、5: 用一般迭代法求方程 x ln x2 在区间( 2 , )内的根, 要求| xk-xk-1|/| xk|10 - 8,解：令 f (x) = x -ln x -2,f (2)0, 故方程在( 2 , 4 )内至少有一个根,因此方程在( 2 , )内仅有一个根 x*, 且 x* (2,4),将方程化为等价方程：x2ln x,因此, x0(2,), xk+12lnxk 产生的序列xk 收敛于x*,取初值x03.0, 计算结果如下：,k xi 8 3.146177452 9 3.146188209 10 3.146191628 11 3.146192714 12 3.146193060 13 3

18、.146193169 14 3.146193204,k xi 0 3.000000000 1 3.098612289 2 3.130954362 3 3.141337866 4 3.144648781 5 3.145702209 6 3.146037143 7 3.146143611,另一种迭代格式：,0 3.000000000 1 3.147918433 2 3.146193441 3 3.146193221,注：由此可见, 对同一个非线性方程的迭代格式, 在 收敛的情形下, 有的收敛快, 有的收敛慢 .,Def : 设序列 xk 收敛于x*, 记ek= xk-x*, 若存在 p1和正数C，

19、 使得成立,则称 xk 为 p 阶收敛的.,特别地 p = 1, 且0 1, 称超线性收敛; p = 2, 称平方收敛.,迭代法的收敛阶(收敛速度),注：收敛阶 p 反映了迭代格式收敛的快慢, p 越大收敛越快.,定理4.4: 设x*为 的不动点, p1为正整数, 在x*的某邻域(x*)内p 阶连续可微, 且 (x*)= (x*)= ( p -1)(x*)=0, 而 ( p )(x*)0则存在 0,当x0 x*- , x*+ (x0 x*)时, 由迭代格式产生的序列 xk 以 p 阶收敛速度收敛于x*.,Prove:,(1) 由 ( x*)=0必存在 0, 当x0 x*- , x*+ U(x*)时, 由迭代格式产生的序列 xk 收敛于x*, 并有xk x*- , x*+ 由泰勒公式有,由条件知,(2) 由于 在x*处 p 阶连续可微且 ( p )(x*)0, 知必存在x*的某邻域(x*), 当x U(x*)时