迭代法的局部收敛性

定义2 设方程x=(x) 根α, 如果存在α 的某个邻域 : x-α，对任意初值 x0，迭代过程所产生的序列均收敛 于根α ，则称该迭代法是局部收敛的.
迭代过程的收敛速度

定义3 记 ek = α- xk ，若
k
lim
ek 1 ek
p
C 0
则称迭代过程是p阶收敛的. 特别地，当p=1时，称为线性收敛； 当p>1时，称为超线性收敛， 当p=2时，称为平方收敛. p越大，收敛越快.
则
l (l 2 3a ) l (3l 2 a )
解得 l 0, l a .由题知取 l a .即迭代序列收敛于 a .
3 2 a ( xk 3 ax ) /(3 x a) k k ( a xk )3 lim lim lim 3 k ( a x )3 k k ( a x )3 (3 x 2 a ) ( a xk ) k k k
L xk xk xk 1 1 L Lk xk x1 x0 1 L

证 根的存在性 由(2)知(x)连续. 令f(x)=x-(x), f(a)0, f(b)0, 从而 f(x)=0在[a, b] 上有根，即x=(x)在[a, b] 上有根. 根的唯一性 设x=(x)在[a, b] 上有两根α1, α2， α1 α2 ， α1- α2=(α1)-(α2)L α1- α2 与 L<1矛盾.故α1= α2 序列的收敛性 xk+1-α=(xk)-(α)Lxk-α , xk+1-αLk+1x0-α 由0L<1有

不动点迭代法的局部收敛性及收敛阶
定理1.3 若(x)在方程x=(x)的根α的邻域内有 一阶连续的导数，且'(α) <1,则迭代过程 xk+1=(xk)具有局部收敛性 证 由连续函数性质，存在α的充分小邻域 : x-α, 使当x 时，有 ' (x)L<1 由微分中值定理有 (x)–α=(x)–(α)='()x-α<x-α 故(x)，由定理1.2知对任意初值x0 均收敛 .
1 f ( r ) (1 ) x (x ) (r ) r f ( 2 )
1 f ( r ) (1 ) ( x) ( ) ( x ) (x ) (r ) r f (2 )
( ) lim ( x) ( ) 1 1 0, ( ) 1 x x r
1 ( p) xk 1 (1 )( xk ) p p!
k
lim
xk 1 xk
p

1 ( p) ( ) 0 p!
必要性 （略）
例 能不能用迭代法求解方程x=4-2x，如果不能
时，试将方程改写成能用迭代法求解的形式.
方程为x-4+2x =0.设f(x)= x-4+2x ，则f(1)<0，f(2)>0， f‘(x)= 1+2x ln2>0,故方程f(x)=0仅在区间(1, 2)内有唯一根. 题中 (x)=4-2x，当时x[1,2]时,' (x)=-2xln2>2ln2>1 ,由 定理1.2不能用 xk 1 4 2x 来迭代求根. 把原方程改写为x=ln(4-x)/ln2, 此时(x)=ln(4-x)/ln2 , 则有 1°当x[1,2]时， (x)[1,ln3/ln2] [1,2] 2°x[1,2] ，有 '(x)= 1 1 1 1 1 1

1 a x ( x ), x0 0 (k 0,1, 2, 例 研究求 a 的Newton公式 k 1 k 2 xk
证明：对一切 k 1, 2, , xk a ,且序列{xk}是单调递减的， 从而迭代过程收敛.
事实上，若α是f(x)=0的重根，设其重数为r,
f ( x) ( x) x f ( x)
f ( ) f ( )( x ) x f ( ) f ( )( x ) 1 1 f ( r 1) ( )( x )r 1 f (r ) (1 )( x )r (r 1)! r! 1 1 f ( r 1) ( )( x )r 2 f (r ) ( 2 )( x ) r 1 (r 2)! (r 1)!
由此知若α是f(x)=0的一个单根, f(α)=0, f'(α)0, '(α)=0, ''(α)=f''(α)/f'(α), 则在根α附近Newton 法是局部收敛的, 并且是二阶收敛的,即 p=2.
EI 2 但如果α是f(x)=0的重根，则Newton法仅是线性 收敛的 ,即 p=1.
1 11


定理1.4 若(x)在方程x=(x)的根α的邻域内有 充分阶连续的导数，则迭代过程xk+1=(xk)是p阶 收敛的充分且必要条件是 (j)(α)=0, j=1,2,,p-1 (p)(α)0

证 充分性
xk 1 ( xk ) ( ) ( )( xk ) 1 1 ( p 1) ( )( xk ) p 1 ( p ) ( )( xk ) p ( p 1)! p!
1 L
令p，有
L xk xk 1 1 L Lk xk x1 x0 1 L
xk
定理1.2 设(x)在[a, b]上具有一阶导数，且 (1)当x[a, b]时, (x)[a, b] ； (1) x[a, b] ，有'(x)L<1 则对任意初值x0 [a, b], 迭代过程 xk+1=(xk)收敛于 x=(x)的惟一根.
Newton迭代法的全局部收敛性
定理1.5 设f(x)在有根区间[a, b]上二阶导数存在， 且满足 (1) f(a)f(b)<0; (2) f'(x)0, x[a, b]; (3) f''(x)不变号, x[a, b]; (4) 初值x0 [a, b]且使f''(x0) f(x0)>0; 则 Newton 迭代法收敛于f(x)=0在[a, b]内的惟一 根.
逐次逼近方程f(x)=0的根α ，这种求根算法称为 Newton法（切线法），此公式称为 Newton迭代公式.
Newton迭代法的收敛性及收敛阶
f ( x) Newton法的迭代函数是 ( x ) x ( x) f 从而 ( x) f ( x) f ( x) [ f ( x)]2
a xk 1
lim
1 1 0 k 3 x 2 a 4a k
a
故此迭代式确是求
的三阶方法.
Newton迭代法
Newton迭代法

设有方程f(x)=0，在f(x)=0的根α附近任取一点x0 作为初始近似根，由迭代公式
f ( xk ) xk 1 xk f ( xk ) (k 0,1, 2, )
第一章
非线性方程和方程组的数值解法
非线性方程根的概念
给定非线性方程f(x)=0 如果有α使得f(α)=0，则称α为f(x)=0的根 或f(x)的零点. 设有正整数m使得f(x)=(x-α)mg(x) 且g(α)0 ，则当m2时，称α为f(x)=0的m 重根；当m=1时，称α为f(x)=0的单根. 若α为f(x)=0的m重根，则 f(α)=f(α)==f (m-1)(α)=0, f (m)(α)0 这里只讨论实根的求法.
求根步骤

（1）根的存在性. （2）根的隔离. （3）根的精确化.
非线性方程求根的数值方法

二分法 迭代法
单点迭代法(不动点迭代，Newton迭代法) 多点迭代法(弦截法）

迭代法是一种逐次逼近的方法，它的基 本思想是通过构造一个递推关系式 (迭 代格式) ，计算出根的近似值序列,并要 求该序列收敛于方程的根.

多点迭代法

建立迭代公式 xk+1=(xk-n+1, ,xk-2, xk-1, xk)
(3)
对于迭代法需要考虑一下几个主要问题 收敛性 收敛速度 计算效率
迭代法的局全收敛性

定义1 设为f(x)=0的根，如果x0[a, b]， 由迭代法产生的序列都收敛于根 ，则 称该迭代法是全局收敛的。

例 设a>0,x0>0,证明:迭代公式
2 xk ( xk 3a) xk 1 2 (3xk a)
是计算 a 的三阶方法.

证 显然当a>0，x0>0时，xk>0（k=1,2,…）.令 (x)=x(x2+3a)/(3x2+a)
(3x 2 3a)(3x 2 a) x( x 2 3a) 6 x 3( x 2 a) 2 ( x) 2 2 (3x a) (3x 2 a)2 故对x 0, ( x) 1 ，从而迭代收敛.设{xk}的极限为l，则有
k
lim xk
误差估计 xk+1-xk=(xk)–(xk-1)Lxk-xk-1 xk+2-xk+1=(xk+1)–(xk)L2xk-xk-1 xk+p-xk+p-1Lpxk-xk-1 xk+p-xk xk+p-xk+p-1+xk+p-1-xk+p-2++ xk+1-xk (Lp+Lp-1++L) xk-xk-1 L Lp 1 = xk xk 1

k
4 x ln 2
4 2 ln 2
2ln 2
由定理1.2知可用迭代公式xk+1=ln(4-xk)/ln2来求解(1,2)区 间内的唯一根.