数值分析 课件

§4 牛顿法 /* Newton - Raphson Method */一、牛顿迭代公式的推导 1、待定参数法 不动点迭代的关键是构造满足收敛条件的迭代函数 g ( x ) 一种自然的选择是令

f ( x ) 0 g( x ) x

g( x ) x cf ( x ) (c 0)

为了加速不动点迭代的收敛过程，应尽可能使迭代函数 g ( x ) 在 x x 处有更多阶导数等于零(定理2.5)。 令 1

g ( x ) 1 cf ( x ) 0 c

现设 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 )

数值分析 课件

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 f ( x k )称之为牛顿

k 0,1, 2,

—拉夫森方法，简称牛顿法

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!

数值分析 课件

将 (x* x0)2 看成高阶小量，则有：0 f ( x*) f ( x0 ) f ( x0 )( x * x0 )f ( x0 ) x* x0 f ( x0 )

x1

y

x*

x2 x1

xx0

y f ( x0 ) f ( x0 )( x x0 )

与x轴交点的横坐标

xk 1

f ( xk ) xk f ( x k )

k 0,1, 2,

只要 f C1,每一步迭代都有 f ( xk ) 0 xk x 而且 lim ,则 x*就是 f 的根。 k

数值分析 课件

例1: 写出求 a (a 0)的Newton迭代格式； 1 ( a 0)的Newton迭代格式,要求公式中既 写出求 a 无开方运算，又无除法运算。解： 等价于求方程 f ( x ) x 2 a 0 (a 0) 的正根 f ( x) 2 x2 f ( xk ) xk a 1 a xk 1 xk xk ( xk ) k 0,1, 2, f ( x k ) 2 xk 2 xk 1 等价于求方程 f ( x ) a 2 0 (a 0) 的正根 x

f ( xk ) xk 1 xk xk f ( x k )

a

1 2 xk

2 3 xk

2 f ( x ) 3 x

1 2 xk (3 axk ) k 0,1, 2, 2

数值分析 课件

Th2.7 (局部收敛性)设 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

数值分析 课件

证明：Newton’s Method 事实上是一种特殊的不动点迭代f ( x) 其中 g( x ) x ,则 f ( x )

f ( x*) f ( x*) g ( x*) 0 2 f ( x*)

f 2 ( x ) f ( x ) f ( x ) g ( x ) 1 f 2 ( x )

收敛

由 Taylor 展开： 在单根 /*simple root */ f ( k ) 0 f ( x*) f ( xk ) f ( xk )( x * xk ) ( x * xk )2 附近收敛快 f ( xk ) f ( k ) x* xk ( x * xk )2 f ( xk ) 2! f ( xk )x k 1

2!

xk 1 x * f ( k ) 2 ( x * xk ) 2 f ( xk )

只要 f ( x ) 0 ,则令 k 可得结论。

数值分析 课件

Th2.8 (收敛的充分条件)设f (x) =0 且f C2[a, b],若(1) f (a) f (b) < 0;(2) 在整个[a, b]上 f 不变号且 f ( x ) 0 ; (3) 选取 x0 [a, b] 使得 f ( x0 ) f ( x0 ) 0 ;

则Newton’s Method产生的序列{ xk } 收敛于方程的根 x , 且 xk 1 x * f ( x*) lim k ( x * x ) 2 2 f ( x*) k 产生的序列单调有 有根 根唯一 界保证收敛

数值分析 课件

注：Newton’s Method 收敛性依赖于x0 的选取。

x0 x0 x0 x*

Th2.9(收敛的另一充分条件)设 f ( x ) 在[a, b]上连续， 且(1) f (a) f (b) < 0;(2) 在整个[a, b]上 f ( x ) 0且 f ( x ) 0 ;f (a ) f (b) b a b a (3) , f (a ) f ( b )

则对 x0 [a, b],Newton’s Method产生的序列{ xk } 收敛于方

程 f ( x ) 0 在[a, b]内的唯一实根 x 。

数值分析 课件

Th2.9中条件(3)的几何意义y f (a ) f (a )( x a ) f (b ) x b f ( b )f (b) f ( b )

af (a ) f ( a )

x

y f ( x) b

f (a ) x a f ( a )

y f (b) f (b)( x b)

保证数列 x k 单调递增且有上界 x

数值分析 课件

改进与推广(补充) /* improvement and generalization */ 重根 /* multiple root */ 加速收敛法： Q1: 若 f ( x*) 0,Newton’s Method 是否仍收敛？ n f ( x ) ( x x ) q ( x ) 且 q( x ) 0 。 设 x* 是 f 的 n 重根，则：

因为 Newton’s Method 事实上是一种特殊的不动点迭代，f ( x) 其中 g( x ) x ,则 f ( x ) 1 f ( x*)2 f ( x*) f ( x*) 1 | g ( x*) | 1 1 2 f ( x*) n

A1: 有局部收敛性，但重数 n 越高，收敛越慢。 Q2: 如何加速重根情况时的收敛速度？ A2: 将求 f 的重根转化为求另一函数的单根。f ( x) 令 ( x) ,则 f 的重根 = f ( x )

的单根。

数值分析 课件

§5 弦割法与抛物线法/* Secant Method and Parabola Method */

一、弦割法Newton’s Method 每一步要计算 f 和 f ,为了避免计算导 数值，现用 f 的值近似 f ,从而得到弦割法(割线法)。割线/* secant line */

x2 x1 x0

切线斜率

割线斜率

f ( x k )

f ( xk )( xk xk 1 ) xk 1 xk f ( xk ) f ( xk 1 )

f ( xk ) f ( xk 1 ) xk xk 1

需要2个初值 x0 和 x1。

数值分析 课件

Th2.10 局部收敛性 [ x , x ] , x*为方程 f (x) =0的根， 0 设 I 表示区间 函数f (x)在 I 中有足够阶连续导数， 且 满足

(i)(ii)

f

( x ) 0f ( ) M 2 f ( )

x I; , I ;

(iii) d M 1ek 1 ekq

则对 x0 , x1 I ,由割线法产生的序列 xk 都收敛于x*,且

limk

K

q 1

收敛速度介于Newton and Bisection 之间

f ( x * ) 1 其中 K , q (1 5 ) 1.618. * 2 f (x ) 2

数值分析 课件

二、抛物线法(Muller)Muller方法的思想来源于弦割法:利用3个已知点构造一条抛物

线,取其与x轴的交点构造下一次迭代值.几何图示

f ( x)

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 )取该抛物线与x轴的交点作为下一次迭代值,即

p2 ( xk 1 ) 0

然后取新的相邻的三次迭代值重复上述过程,即为Muller方法.

数值分析 课件

Muller方法中抛物线根的计算方法:首先要将抛物线化为规范形式:引入新的变量

p2 ( x ) ax bx c2

x xk x x k k 1 xk xk 1 3 x x k 1 k 2 xk xk 2 3 1 3 xk 1 xk 2

数值分析 课件

将上述变量代入前面的抛物线方程,得

p2 ( ) 其中

1

3

a

2

b c

a f ( xk 2 ) 32 f ( xk 1 ) 3 3 f ( xk ) 3 , 2 2 b f ( x ) f ( x ) k 2 3 k 1 3 f ( xk )( 3 3 ), c f ( x ) . k 3 p2 ( ) 的两个零点为:

1,2

b b 4ac 2c 2 2a b b 4ac2