第二章非线性方程的数值解法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 )

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 )

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

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 )

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