《山东大学数值分析课解非线性方程-1》由会员分享，可在线阅读，更多相关《山东大学数值分析课解非线性方程-1（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), 依据函数值异号及实根的个数确定隔 根区间. 必要时可以调整步长 h,
3、总可以把隔根区间全部找出.代数方程根的模上下界定理：定理：设代数方程 f (x)= xm+am-1xm-1+a1x+a0=0则: (1) 若=max|am-1|,|a1|,|a0|, 方程根的模小于+1；(2) 若 v =1/|a0| max1, |am-1|,|a1|, 方程根的模大于1/(v+1).例：求方程 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 0 - (1,2) +f (1.5)
4、0 (1,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.771
5、4 90.7714 0.7724 100.7724 0.7729 取x10= 0.7729，误差为| x* - x10|1/ 211 .Remark1：求奇数个根Find solutions to the equation x3 - 6x2 +10x 4 = 0on 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，利用前面的公式可计算
6、迭代次数为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改写成某种等价形式, 由等价形式构造相应的迭代公式, 然后选取方
7、程的某个初始近似根 x0 , 代入迭代公式反复 校正根的近似值, 直到满足精度要求为止.具体做法：(1) 把 f (x) = 0 改写成下列等价形式f (x) = 0x = (x)等价变换f (x) 的根 (x) 的不动点(2) 构造迭代格式： , k=0,1,2,(3) 从给定的初始值x0出发, 按照迭代公式即可得 一个数列x0 , x1 , x2 , , xk , (4) 若有极限,则迭代公式收敛, 此时数列极限即为原方程的根,即这里 (x) 称为迭代函数注： f (x)=0 化为等价方程 x = (x) 的方式是不唯一的, 故迭代格式也不 唯一, 有的收敛, 有的发散. (1)(1) 如
8、果将原方程化为等价方程由此可见，这种迭代格式是发散的 取初值For example：2x3 x 1= 0(2)(2) 如果将原方程化为等价方程 仍取初值依此类推,得x3 = 0.9940x4 = 0.9990x5 = 0.9998x6 = 1.0000x7 = 1.0000已经收敛,故原方程的解为 x = 1.0000同样的方程 不同的迭代格式有不同的结果什么形式的迭代 法能够收敛呢?收敛性分析定义: 若存在常数 (0 0 将方程变形成等价形式：x( lg x + 7 ) / 2由定理4.2知，迭代格式 xk+1( lg xk+7)/2在3.5,4内收敛 .局部收敛Def : (局部收敛) 设
9、x*为 的不动点,若存在x*的一个闭邻域 U( x*,)=x*-, x*+( 0), 使得对任意x0 U( x*,),由迭代 格式 xk+1= (xk) ( k = 0,1, 2,)产生的序列 xk 都收敛于x*, 则称迭代过程 xk+1= (xk) 在的闭邻域U( x*,)内是局部收敛的.定理4.3: 设x*为 的不动点, (x)与 (x)在包含x*的某邻域 U( x*) (即开区间)内连续, 且| ( x*)| L 0, 故方程在( 2 , 4 )内至少有一个根因此方程在( 2 , )内仅有一个根 x*, 且 x* (2,4) 将方程化为等价方程：x2ln x因此, x0(2,), xk+
10、12lnxk 产生的序列xk 收敛于x*取初值x03.0, 计算结果如下：k xi 8 3.146177452 9 3.146188209 10 3.146191628 11 3.146192714 12 3.146193060 13 3.146193169 14 3.146193204k xi0 3.0000000001 3.0986122892 3.1309543623 3.1413378664 3.1446487815 3.1457022096 3.1460371437 3.146143611另一种迭代格式：0 3.0000000001 3.1479184332 3.1461934413
11、 3.146193221注：由此可见, 对同一个非线性方程的迭代格式, 在收敛的情形下, 有的收敛快, 有的收敛慢 .Def : 设序列 xk 收敛于x*, 记ek= xk-x*, 若存在 p1和正数C，使得成立则称 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
12、 x*- , x*+ (x0x*)时, 由迭代 格式产生的序列 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*)时, 有 ( p ) (x)0 .由于 x*- , x*+ U(x*), 故 ( p )( ) 0, k=0,1,2,可见, 当初值x0x*时, xkx*. 于是有即 xk 有p 阶收敛速度.4.
13、3 迭代过程的加速加速迭代的收敛方法主要用于线性收敛的迭代格式一、松弛迭代设 xk 是根 x*的某个近似值, 用迭代公式校正一次, 得假设 在所考察的范围内改变不大, 设其估计值为L, 则 有由此解得：记：则得加速迭代公式：或若记则称为松弛因子, 故这种方法也称为松弛迭代法, 从理论 上讲, 取 最有效; 实际应用时常取 近似代替 .一、Aitken迭代将迭代值 再迭代一次, 得 由于 联立消去L, 得 解得： 这样就得到Atiken加速迭代公式： 或 注：Aitken加速迭代对线性收敛迭代格式的加速效果是非 常明显的. 定理4.5: 设 的迭代函数 在其不动点 x*的某邻域 内有二阶连续导数, , 且 , 则Atiken加速迭代二阶收敛.Prove：Aitken迭代函数为： (1)：先证 与 有相同的不动点 10 若 , 则20 若 , 则(2)：再证二阶收敛所以于是故有所以Aitken迭代二阶收敛.定理4.6: 如果由迭代公式 产生的数列 满足(1)
