第3章 非线性方程组数值解法2

p2 ( x )
xk-1 x* xk+1 xk
xk-2
Muller方法的具体实现:
设已知三个点 ( xk 2 , f ( xk 2 )),( xk 1 , f ( xk 1 )), ( xk , f ( xk )). 则过上述三个点的抛物线方程为:
( x xk 1 )( x xk ) ( x xk 2 )( x xk ) p2 ( x ) f ( xk 2 ) f ( x k 1 ) ( xk 2 xk 1 )( xk 2 xk ) ( xk 1 xk 2 )( xk 1 xk ) ( x xk 2 )( x xk 1 ) f ( xk ) ( xk xk 2 )( xk xk 1 )
称之为牛顿
—拉夫森方法，简称牛顿法
2、Taylor展开法/* Taylor’s expansion Method */ 原理：将非线性方程线性化 取 x0 x*，将 f (x)在 x0 做一阶Taylor展开:
f ( x ) f ( x0 ) f ( x0 )( x x0 ) f ( ) ( x x0 ) 2， 在 x0 和 x 之间 2!
(3) 选取 x0 [a, b] 使得 f ( x ) f ( x ) 0 ； 0 0 则Newton’s Method产生的序列{ xk } 收敛于方程的根 x, 且 xk 1 x * f ( x*) lim k ( x * x )2 产生的序列单调有 2 f ( x*) 有根 k 根唯一 界保证收敛
由 Taylor 展开：
在单根 /* 附近
xk 1 x * f ( k ) 2 ( x * xk ) 2 f ( xk )
x k 1
只要 f ( x ) 0 ，则令 k 可得结论。
定理 （收敛的充分条件）设f (x) =0 且f C2[a, b]，若 (1) f (a) f (b) < 0；(2) 在整个[a, b]上 f 不变号且 f ( x ) 0；
定理 局部收敛性
[ x , x ] ， x*为方程 f (x) =0的根， 0 设 I 表示区间 函数f (x)在 I 中有足够阶连续导数， 且 满足
(i)
(ii)
f ( x ) 0
x I;
f ( ) M , I ; 2 f ( )
解： 等价于求方程 f ( x ) x 2 a 0 (a 0) 的正根 f ( x) 2 x
2 f ( xk ) xk a 1 a xk 1 xk xk ( xk ) k 0,1, 2, f ( xk ) 2 xk 2 xk
1 101 101 ? xk 1 2 ( xk x ) k 0,1, 2, k 1 101 x0 10, x1 ( x0 ) 10.05 2 x0 1 101 x2 ( x1 ) 10.0499, 2 x1 1 101 x3 ( x2 ) 10.0499 2 x2
为了加速不动点迭代的收敛过程，应尽可能使迭代函数 g ( x ) 在 x x 处有更多阶导数等于零（定理2.5）。 令 1
0 c g( x ) 1 cf ( x )
现设 g( x ) x h( x ) f ( x )
f ( x )
g( x ) 1 h( x ) f ( x ) h( x ) f ( x ) 1 h( x ) f ( x ) 0 1 h( x ) ( f ( x ) 0) f ( x )

f ( k ) 0 f ( x*) f ( x k ) f ( x k )( x * x k ) ( x * xk )2 2! f ( xk ) f ( k ) x* xk ( x * xk ) 2 f ( xk ) 2! f ( xk )
2 f ( x ) 3 x

定理 （局部收敛性）
设 x* 为方程 f (x) =0的根，在包含x*的某个开区间内 f ( x ) 连续， 且 f ( x ) 0，则存在 x* 的邻域 B ( x*) [ x , x ] ， 使得任取初值 x0 B ( x*) ，由Newton’s Method产生的序列 xk 以不低于二阶的收敛速度收敛于x*，且 xk 1 x * f ( x*) lim 2 k ( x * x ) 2 f ( x*) k
(iii) d M 1
e k 1 ek
q
则对 x0 , x1 I ，由割线法产生的序列 xk 都收敛于x*，且

lim
k
K
q 1
收敛速度介于Newton and Bisection 之间
1 f ( x * ) 其中 K , q (1 5 ) 1.618. * 2 f (x ) 2
证明：Newton’s Method 事实上是一种特殊的不动点迭代
f ( x) 其中 g( x ) x ，则 f ( x)
g( x*)
f ( x*) f ( x*) 0 1 收敛 2 f ( x*)
f 2 ( x ) f ( x ) f ( x ) g( x ) 1 f 2 ( x )
因为 Newton’s Method 事实上是一种特殊的不动点迭代，
f ( x) 其中 g( x ) x ，则 f ( x) 1 f ( x*)2 f ( x*) f ( x*) 1 | g( x*) | 1 1 2 n f ( x*)
故：有局部收敛性，但重数 n 越高，收敛越慢。 如何加速重根情况时的收敛速度？ 答： 将求 f 的重根转化为求另一函数的单根。
lim
k
xk 1 x xk x

p
f ( x ) 6 f (x )

( p 1)/ 2
3 p 1 . 839 其中 ,是方程
( 1) 0 的根.
2
Muller法的优点：有时初值的选取范围比Newton法和弦割法 宽,而且可以一次求得方程的一对复根.
取该抛物线与x轴的交点作为下一次迭代值,即
p2 ( xk 1 ) 0
然后取新的相邻的三次迭代值重复上述过程,即为Muller方法.
*局部收敛性
f ( x ) 在x*的某邻域内连续，则存 设 f ( x ) 0, f ( x ) 0 ，
在 x* 的一个邻域 N ( x*) [ x , x ] ，当 x0 , x1 , x2 N ( x*) 时,由抛物线法产生的序列 xk 收敛于x*，且
将 (x* x0)2 看成高阶小量，则有：
0 f ( x*) f ( x0 ) f ( x0 )( x * x0 )
f ( x0 ) x* x0 f ( x0 )
x1
y
x*
x2 x1
x
x0
y f ( x0 ) f ( x0 )( x x0 )
与x轴交点的横坐标
3、牛顿法 /* Newton - Raphson Method */
一、牛顿迭代公式的几种推导方式 1、待定参数法 不动点迭代的关键是构造满足收敛条件的迭代函数 g ( x ) 一种自然的选择是令
f ( x ) 0 g( x ) x
g( x ) x cf ( x ) (c 0)


2
f ( x ) 0 且 f ( x ) cos x 在 x x 。

二、抛物线法(Muller)
Muller方法的思想来源于弦割法:利用3个已知点构造一条抛物
线,取其与x轴的交点构造下一次迭代值.
几何图示
f ( x)
割线
/* secant line */
x2 x1 x0
切线斜率

割线斜率

f ( xk )
f ( xk )( xk xk 1 ) xk 1 xk f ( xk ) f ( xk 1 )
f ( xk ) f ( xk 1 ) xk xk 1
需要2个初值 x0 和 x1。
1 取 h( x ) ( f ( x ) 0) f ( x ) f ( x) 因此，选取迭代函数 g ( x ) x f ( x )
Newton – Raphson迭代格式

满足 g ( x ) 0
f ( xk ) xk 1 xk k 0,1, 2, f ( xk )
1 a
)

满足 g ( x )0 判断合适不合适就看是否
1 解法二： 等价于求方程 f ( x ) a 2 0 (a 0) 的正根 x 1
f ( xk ) xk 1 xk xk f ( x k ) a
2 xk
2 3 xk 1 2 xk (3 axk ) k 0,1, 2, 2
Corollary(推论) 设 x* 为方程 f (x) =0的一个根，f ( x ) 0， 且 f ( x ) 在 x* 的附近连续，则 0,使得 x0 , x1 [ x , x ] 由
Secant Method产生的序列 xk 都收敛于x*。 例1 证明方程
注：Newton’s Method 收敛性依赖于x0 的选取。
x
0
x0 x 0 x*
重根 /* multiple root */ 加速收敛法： 若 f ( x*) 0 ，Newton’s Method 是否仍收敛？
n f ( x ) ( x x ) q( x ) 且 q( x ) 0 。 设 x* 是 f 的 n 重根，则：
f ( x) 令 ( x ) ，则 f 的重根 = f ( x)