计算方法 非线性方程(组)的数值解法ch07a r

1、1第七章非线性方程(组)的数值解法计算方法 方程求根与二分法方程求根与二分法 不动点迭代及其加速不动点迭代及其加速2本章内容本章内容n 非线性方程求解非线性方程求解n 二分法二分法n 不动点迭代法及其加速不动点迭代法及其加速n 牛顿法、弦截法、抛物线法牛顿法、弦截法、抛物线法n 求根问题的敏感性与多项式的零点求根问题的敏感性与多项式的零点n 非线性方程组的数值求解非线性方程组的数值求解3本讲内容本讲内容l 迭代格式迭代格式l 加速算法加速算法l 收敛性收敛性n 非线性方程求解介绍非线性方程求解介绍n 二分法及其收敛性二分法及其收敛性n 不动点迭代及其加速不动点迭代及其加速4非线性方程数值解法非

2、线性方程数值解法考虑方程考虑方程l 若若 f(x) 是一次多项式，则称为是一次多项式，则称为线性方程线性方程； 否则称为否则称为非线性方程非线性方程f (x) = 0l 若若 f(x) = a0 + a1x + . . . + anxn ，则称为，则称为代数方程代数方程, ( ) , xRf xC a bn=1, 2, 3, 4 时有相应的求根公式，时有相应的求根公式，n 5 时不存在求根公式时不存在求根公式l 非线性方程可能有非线性方程可能有(无穷无穷)多个解，求解时必须强调多个解，求解时必须强调求解区间求解区间l 非线性方程一般没有直接解法，通常都使用非线性方程一般没有直接解法，通常都使用

3、迭代算法迭代算法求解求解5非线性方程数值解法非线性方程数值解法q 几个基本概念几个基本概念l 实根与复根实根与复根l 根的重数根的重数 f(x)=(xx*)m g(x) 且且 g(x*) 0, 则则 x*为为 f(x)=0 的的 m 重根重根l 有根区间：有根区间：a, b 上存在上存在 f (x) = 0 的一个实根的一个实根q 研究内容：研究内容：在在有根有根的前提下求出方程的的前提下求出方程的近似根近似根6二分法（对分法）二分法（对分法）q 基本思想基本思想将有根区间进行对分，找出根所在的小区间，然后再对该将有根区间进行对分，找出根所在的小区间，然后再对该小区间对分，依次类推，直到有根区

4、间的长度满足给定的小区间对分，依次类推，直到有根区间的长度满足给定的精度为止精度为止q 数学原理：数学原理：介值定理介值定理设设 f(x) 在在 a, b 上连续，且上连续，且 f(a) f(b)0，则由介值定理可得，则由介值定理可得，在在 (a, b) 内至少存在一点内至少存在一点 使得使得 f( )=0q 适用范围适用范围求有根区间内的求有根区间内的 单重实根单重实根 或或 奇重实根，即奇重实根，即 f(a) f(b)0 ，则停止计算，则停止计算(2) 对对 k = 1, 2, . , maxit 2abx 计算计算 f(x)，其中，其中若若 |f(x)| 或或 b-a ，停止计算，输出近

5、似解，停止计算，输出近似解 x若若 f(a) f(x) 0，则令，则令 b = x; 否则令否则令 a = xl 优点：优点：简单易用，总是收敛简单易用，总是收敛l 缺点：缺点：收敛速度慢，不能求复根和偶数重根收敛速度慢，不能求复根和偶数重根l 总结：总结：一般用来计算解的一个粗糙估计一般用来计算解的一个粗糙估计8误差分析误差分析记记 a1 = a, b1 = b, 第第 k 步的有根区间为步的有根区间为 ak, bk11224kkkkkkkbababaxxx 112kba 20 ()kkakbxx 结论：结论：二分法总是收敛的二分法总是收敛的9不动点迭代不动点迭代q 基本思想基本思想l 构造

6、构造 f (x) = 0 的一个等价方程：的一个等价方程： ( )xx (x) 的不动点的不动点f (x) = 0 x = (x)等价变换等价变换f (x) 的零点的零点10不动点迭代不动点迭代q 具体过程具体过程l 任取一个迭代初始值任取一个迭代初始值 x0 ，计算，计算得到一个迭代序列：得到一个迭代序列： x0，x1，x2，. . . ，xn，. . . 1()kkxx k = 0, 1, 2, . . 几何含义：几何含义：求曲线求曲线 y = (x) 与直线与直线 y = x 的交点的交点11xyy = xxyy = xxyy = xxyy = xx*x*x*x*y= (x)y= (x)

7、y= (x)y= (x)x0p0 x1p1x0p0 x1p1 x0p0 x1p1x0p0 x1p1x2 12连续性分析连续性分析设设 (x) 连续，若连续，若 收敛，即收敛，即 ，则，则 1limlim ()limkkkkkkxxx lim*kkxx 0kkx *( *)xx ( *)0f x 即即q 收敛性分析收敛性分析性质：性质：若若 ，则不动点迭代，则不动点迭代收敛收敛，且，且 x* 是是 f(x)=0 的解；否则迭代法的解；否则迭代法发散发散。lim*kkxx 13解的存在唯一性解的存在唯一性定理定理：设设 (x) Ca,b 且满足且满足证明：自学证明：自学(1) 对任意的对任意的 x

8、 a,b 有有 (x) a,b(2) 存在常数存在常数 0L1，使得任意的，使得任意的 x, y a,b 有有( )( )xyL xy则则 (x) 在在 a,b 上存在上存在唯一的不动点唯一的不动点 x*解的存在唯一性解的存在唯一性14收敛性分析收敛性分析定理定理：设设 (x) Ca,b 且满足且满足证明：自学证明：自学(1) 对任意的对任意的 x a,b 有有 (x) a,b(2) 存在常数存在常数 0L1，使得任意的，使得任意的 x, y a,b 有有( )( )xyL xy则对任意初始值则对任意初始值 x0 a,b，不动点迭代，不动点迭代 xk+1= (xk) 收敛，且收敛，且不动点迭代

9、的收敛性不动点迭代的收敛性11011kkkkLLxxxxxxLL 15收敛性分析收敛性分析不动点迭代的收敛性不动点迭代的收敛性若若 (x) C1a,b 且对任意且对任意 x a,b 有有 | (x)| L1则上述定理中的结论成立。则上述定理中的结论成立。收敛性结论表明：收敛性结论表明：收敛性与初始值的选取无关收敛性与初始值的选取无关全局收敛全局收敛16举例举例例：例：求求 f(x) = x3 x 1=0 在区间在区间 1, 2 中的根中的根 3( )1xx 231( )(1)3xx 31( )0.2513x (1)1( )2x (1,2)x 3( )1xx 2( )3xx ( )1x (2)0

10、( )7x (1,2)x ex71.m17局部收敛局部收敛定义定义：设设 x* 是是 (x) 的不动点，若存的不动点，若存在在 x* 的某个的某个 -邻域邻域 U(x*) =x*- , x* + ，对任意，对任意 x0 U(x*)，不动点迭代，不动点迭代 xk+1 = (xk) 产生的点列都收敛到产生的点列都收敛到 x*，则称该迭代，则称该迭代局部收敛。局部收敛。定理：定理：设设 x* 是是 (x) 的不动点，若的不动点，若 (x) 在在 x* 的某个邻域内的某个邻域内连续，且连续，且 | (x*)| 0，则称该迭代为，则称该迭代为 p 阶收敛阶收敛。(1) 当当 p =1 时称为时称为线性收

11、敛线性收敛，此时，此时 C 1 时称为时称为超线性收敛超线性收敛l 二分法是线性收敛的二分法是线性收敛的l 若若 (x*) 0，则，则不动点迭代不动点迭代 xk+1 = (xk) 线性收敛线性收敛19收敛速度收敛速度定理：定理：设设 x* 是是 (x) 的不动点的不动点，若若 (p)(x) 在在 x* 的某邻的某邻域内连续，且域内连续，且(1)()( *)( *)( *)0,( *)0ppxxxx 则迭代则迭代 xk+1 = (xk) 是是 p 阶收敛的。阶收敛的。证明：自学证明：自学20举例举例例：例：求求 f(x) = x2 - 3=0 的正根的正根 2( )3xxx (1)( *)2 3

12、11x ex72.m*3x 23( )4xxx (2)3( *)10.31412x 13( )2xxx (3)( *)0 x 2( *)03x 21Aitken 加速加速Aitken 加速加速10()xx 1010*()( *)()(*)xxxxxx21()xx 2121*()( *)()(*)xxxxxx若若 (x) 变化不大变化不大，则可得：，则可得：12()() 0121*xxxxxxxx 2100210()*2xxxxxxx 1y22Aitken 加速加速01234 . . .xxxxx123 . . .yyy21121()2kkkkkkkxxyxxxx 收敛性：收敛性：1*lim0*

13、kkkyxxx 超线性收敛超线性收敛 23Steffenson 加速加速21()(), (), 2kkkkkkkkkkkyxyxzyxxzyx Steffenson 加速加速将将 Aitken 加速技巧与不动点迭代相结合加速技巧与不动点迭代相结合 k = 0, 1, 2, . . . 迭代函数：迭代函数： 21( ( )(), ( )( )2 ( )kkxxxxxxxxx 24Steffenson 加速加速定理：定理：若若 x* 是是 (x) 的不动点的不动点，则则 x* 是是 (x) 的不的不动点。反之，若动点。反之，若 x* 是是 (x) 的不动点，且的不动点，且 ”(x) 存存在，在， (x*) 1，则，则 x* 是是 (x) 的不动点，且的不动点，且 Steffenson 加速迭代是二阶收敛的。加速迭代是二阶收敛的。l 若原迭代是若原迭代是 p 阶收敛的，则阶收敛的，则 Steffenson 加速后加速后 p+1 阶收敛阶收敛l 原来不收敛的迭代，原来不收敛的迭代，Steffenson 加速可能收敛加速