?二分法
迭代法
迭代法的加速（ Aitken加速法,Steffensen迭代法）
牛顿迭代法
非线性方程组的迭代法第八章 非线性方程（组）的数值解
( ) 0
fx
f
,求 解 非 线 性 方 程其 中,是 非问 题线 性 函 数,
1
1 1 0
( ) 0,1.
,
( ) si n 0
nn
nn
x
f x a x a x a x a n
f x e x
,代 数 方 程程例例 超 越 方
1,根 的 存 在 性？
2,根 的 分 布 范 围？
3,如 何 选 择 求 根 法,使 之 简 单,有 效,经 济？
( ) [,] [,]
( ) ( ) 0
( ) 0,( ) 0
f x a b a b
f a f b
f a f b
设 在 上 连 续 且 有 且 仅 有 一 个 根 又
。 则 可 用 对 分 法,
不 妨 设
1 1 1 1
1 0,0
2 2 2
,,.
22
a b a b a b
f x f
a b a b
a b b b a a
） 若 输 出 根 否 则,若,
令,反 之
1 1 2 22 ) [,] 1 [,],a b a b对 区 间 重 复 ） 的 计 算,并 产 生
3 ) 0,
22
i i i ia b a bfx
若,则 得 到 根
§ 1,非线性方程实根的对分法 (二分法 )
二分法的收敛性
11 [,] [,] [,]nna b a b a b
二 分 法 产 生 一 个 有 根 区 间,
11
[,]
11
( ) ( )
22
nn
n n n n n
ab
b a b a b a
区 间 长 度,
2nnn banx当 足 够 大 时,取 近 似 值,
1
2
n n
ba
xx?
误 差,
计 算 简 便,容 易 估 计 误 差,但 收 敛 较 慢 。
a x* x0 b
()fx
a1 b1
*
20
1,3 2 ; 0 ;
0,6 3 ; 0,3,3,6 0,3
0,1.5,1.5,3 1.5,3
1,5,2,2 5,2,2 5,3
1,5,2,2 5 1,8 7 5
f x x
c f c x c
c
x
§ 2,迭代法连续。且改写方程,)(0)( xxxf
1 ( ) n n nx x x建 立 迭 代 格 式,,得 到 序 列
{ } ( 0 n fxx?则 若 收 敛 必 收 敛 到 ） 的 根,
1
*
1
* * *
{ } l im
l im l im l im
( ) ( ) 0
nn
nn
n
n n n
n n n
x
xx
x x f x
xx
x x x
若 收 敛,即,则
2
22
0 1 0
2
2 1 1
2
0
1
1 0 1
1
[ [ 0 3 ],
1.2,
1
1 ; 1 ;
1
x x x
x x x
f x x x
x
x x x x x x x
ab,
取
,]=
选迭代过程的几何表示
()yx
yx?
O x* x2 x1 x0 x
y
0P
1Q
1P
2P
*P
2Q
()
()
yx
xx
xy
交点即为真根迭代法需解决的三个问题迭代函数的构造由迭代函数产生的解序列的收敛性序列的收敛速度和误差估计
3* 0( ) 1 0 1,5,f x x x x x例,求 方 程 在 附 近 的 根
3
3
1
k
1 1
1 ( 0,1,2 )
k 0 1 2 7 8
x 1,5 1,3 5 7 2 1 1,3 3 0 8 6 1,3 2 4 7 2 1,3 2 4 7 2
kk
xx
x x k
解,（ ） 将 方 程 改 写 为由 此 建 立 迭 代 公 式迭 代 收 敛 。
3
3
1
k
2 1
1.
k 0 1 2
x 1,5 2,3 7 5 1 2,3 9
kk
xx
xx
（ ） 若 将 方 程 改 写 为建 立 迭 代 公 式迭 代 不 收 敛 。
如何选取合适的迭代函数？下面介绍三个迭代法的收敛定理。
()x?
*
1
,( ) [,]
1 [,] ( ) ;
( 2) 0 1,
,[,],
( ) ( )
( ) [,],
[,],
( ) (
nn
x a b
x a b a x b
L L i psc hi t z
x y a b
x y L x y L i psc hi t z
x x a b x
ab
x x n
1
0
定 理 设 函 数 在 区 间 上 满 足 条 件
（ ） 对 任 意,都 有存 在 常 数 常 数 使 得 对一 切 都 有条 件则 方 程 在 内 有 唯 一 的 根 且 对 任 何初 值 x 迭 代 序 列
*
*
10
0,1,)
x
1
n
n
x
L
x x x
L
均 收 敛 于,并 有
2 ( ) [,]
( ) ( ),( ) [,]
( ) ( ) 0,( ) ( ) 0
[,] 0,
( ) [,]
x a b
x x x x a b
a a a b b b
ab
x x a b
证,存 在 性 由 条 件 （ ） 知 在 上 连 续 。
令 则 在 上 连 续,且故 存 在,使 得 （ ） 即 （ ）,
所 以 方 程 在 内 有 根 。
**
12
* * * * * * * *
1 2 1 2 1 2 1 2
( ) [,]
,2
( ) ( )
x x a b
xx
x x x x L x x x x
唯 一 性 假 设 方 程 在 内 有 两 个 根由 条 件 （ ）,有导 出 矛 盾,唯 一 性 得 证 。
0
* * *
11
**
0
*
0
*
1 1 1
10
[,],
( ) ( )
0 1,l i m
x [,],
( ) ( )
n n n
n
n
n
n
n
k k k k k k
k
x a b
x x x x L x x
x x L x x
L x x
a b x
x
k
x x x x L x x
L x x
对 任 意 由 迭 代 公 式 有依 此 类 推,得因 所 以即 对 任 意 初 值 迭 代 序 列 均 收敛 到 方 程 的 根 。
类 似 地,对 任 意 正 整 数,有
,,np于 是,对 任 意 正 整 数 有
1 1 2 1
12
1 0 1 0 1 0
12
10
10
*
10
( 1 )
1
1
,
1
n p n n p n p n p n p n n
n p n p n
n p p
p
n
n
n
L
p
L
x
L
x x x x x x x x
x x x x x xL L L
xxL L L
L
xxL
x x x
令 得
'
*
1
*
*
,( ) [,]
1 [,] ( ) ;
( 2) 0 1,[,],
( )
( ) [,],
[,],
( ) ( 0,1,)
x
nn
x a b
x a b a x b
L x a b
xL
x x a b x
ab
x x n
x
0
定 理 2 设 函 数 在 区 间 上 满 足 条 件
（ ） 对 任 意,都 有存 在 常 数 使 得 对 一 切 都 有则 方 程 在 内 有 唯 一 的 根 且 对 任 何初 值 x 迭 代 序 列均 收 敛 于,并 有
10
1
n
n
L
x x x
L
'
'
'
,[,]
,
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
( ) ( )
( ) 2
x y a b
xy
x y x y
x y x y
x y L x y
x
证,设 为 上 任 意 两 点,由 微 分 中值 定 理,在 之 间 至 少 存 在 一 点,使 得即 满 足 上 一 定 理 的 条 件 （ ）,故 结 论 成立 。
'( ) ( )
[,]
xx
ab
因 而 构 造 迭 代 函 数 的 原 则 是 使 在 有 根区 间 上 有 尽 可 能 小 的 上 界 。
*
10 1
n
n
Lx x x x
L
误 差 估 计 式 表 明,
L 常 数 越 小,简 单 迭 代 法 收 敛 越 快
1 1 2 1
1 2
11
1
1
1
1
1
1
*
,
1
n p n n p n p n p n p n n
p p
n n n n
n n n
nn
p
L
p
L
x x x x x x x x
L x x x xL
x x xx
xx
对任意正整数 有
）
令得可通过检查 来判断迭代过程应否终止。
（
c os si n / 4 ; 2 4 2,
1.
c os si n / 4,
2
c os sin / 4 1
4
x
x x x x
x
xL
x x x x
x x x
例,能 否 用 迭 代 法 求 解 下 列 方 程,如 果 不 能,试 将 方 程改 成 能 用 迭 代 法 求 解 的 形 式 。
1
分 析,判 断 在 根 的 附 近 能 否 满 足解 1 ＝,有能 用 迭 代 法 求 根 。
1
4 2 4 2,1 0,2 0
12
2 l n 2 2 l n 2 1.38629 1
l n 4 - / l n 2,l n 4 - / l n 2,
1 1 1 1 1
1,
4 l n 2 4 2 l n 2 2 l n 2
l n 4 -
xx
x
kk
x f x x f f
x
x x x x
x
x
xx
＋
2 ＝,令 >,
区 间,内 有 根,但
＝
不 能 直 接 用 该 迭 代 函 数 迭 代 。
改 写 原 方 程 为 则 ＝
－
＝
－
可 以 用 下 述 迭 代 公 式 来 求 解,
/ l n 2
2 ( ) 1 0 f x x x例,用 简 单 迭 代 法 求 方 程 的 根 。
( 1,5 ) 0,2 5 0,( 2 ) 1 0
[ 1,5,2 ]
ff
解,
为 有 根 区 间 。
11
'
1
1 1 ( ) 1,5 1,5 1 ( ) 2 1 2
1 1 1
()
3,1 6 22 1 2 2,5
x x x x
x
x
（ ） 因且
22
'
2 22
1 1 1
( 2 ) 1 ( ) 1,5 1 ( ) 1 2
2 1,5
1 1 1
( )
1,5 2,2 5
x x x
x
x
x
因且
0
[ 1,5,2 ],x?根 据 定 理,任 取 由 这 两 种 等 价方 程 所 构 造 的 简 单 迭 代 方 法 都 收 敛,且 第 一 种所 产 生 的 迭 代 序 列 收 敛 较 快 。
0.2
*
1 1 0
0 5
11
,1,
,
1
[ 0.2 1 ] 55
[ 0.4 1 ] 26
[ 0.5 1 ] 21
k
x
x
xx
x
n
x
kn
x e x
f x x e
x e x e L
ee
L
x e x x x x
L
n
n
n
-5
例,用 简 单 迭 代 法 求 方 程 在,附 近 的 根,
要 求 精 度 =10 。
解,令 =0,显 然 方 程 在 [0.2,1] 有 根,
迭 代 函 数 收 敛迭 代 格 式 为 由 〈,得
，
，
，
* * *
*
'*
**
0
1
*
( ) (,)
()
( ) 1,,,
[,],
( ) ( 0,1,2,)
.
nn
x x O x
x x x
x
x x x
x x n
x
定 理 3,如 果 函 数 在 的 一 邻 域内 连 续 可 微,为 方 程 的 根,且则 存 在 正 数 使 得 对 任 意迭 代 序 列收 敛 于 局 部 收 敛 性
' * * '
* * *
'
**
* * *
**
*
1
( ) (,) ( ) 1,
1,,[,]
( ) 1
( ),
( ) ( ) ( )
( ) [,]
()
nn
x O x x
L x x x
xL
xx
x x x x L x x
x x x
x x x
证：因 在 内连续，且 故存在正数 使得对,有另一方面，由 又有即 。由上面定理知，迭代序列收敛于 。
实际用迭代法计算时，先用对分区间法求较好的初值，然后再进行迭代。
迭代法收敛速度定义
1
**
1
()
()
( 0
11
2
kk
kk
k
p
k
xx
x x x e x x
k
e
CC
e
p
pp
p
定义：设迭代过程 收敛于方程的根,如 果迭代误差当 时成立下列渐进关系式为常数）
则称该迭代过程是 阶收敛的。
为线性收敛,为超线性收敛，
为平方收敛。
()
1
*
' * " * ( 1 ) * ( ) *
*
( ),( )
( ) ( ) ( ) 0 ; ( ) 0
p
kk
pp
x x x
x
x x x x
xp
定理：对于迭代过程 如果 在所求根 的邻近连续，并且则该迭代过程在点 邻近是 阶收敛的。
'*
1
*
()
**
( ) ( ) *
** 1
1
( ) 0 1,( )
()
()
( ) ( ) ( )
!
( ) ( )
()
!!
kk
k
p
p
kk
pp
p k
kk p
k
x x x
xx
x x x x
p
e x
x x x x
p e p
证：由于 故 具有局部收敛性。
将 在根 处展开，由条件有
'
' '
'
( )
[,] ( ) 0,
1 ( ) 1,( ) 0,
2 ( ) 0,( ) 0,
k
k
x
x a b x
x x x
x x x
迭 代 过 程 的 收 敛 速 度 依 赖 于 迭 代 函 数的 选 取 。 如 果 当 时 则 该 迭 代过 程 只 可 能 是 线 性 收 敛 。
特 别 地,
当 序 列 线 性 收 敛 ；
当 序 列 平 方 收 敛 。
迭代法加速（ Aitken法）
2
1
1
21
()
( )
2
k
kk
k k k
k k k
k
x
xx
x x x
x x x
x
设 序 列 线 性 收 敛,迭 代 格 式 为
＝,
且 序 列 平 方 收 敛 。
*
0
1 0 2 1
* * ' *
1 0 1 0
* * ' *
2 1 2 1
'
* * * *
1 0 2 1
*
1
2
( ) ( )
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
( ),
( ) ( )
xx
x x x x
x x x x x x
x x x x x x
xL
x x L x x x x L x x
xx
xx
设 是根 的某个预测值，通过两次迭代校正有由微分中值定理，有假定 改变不大，近似地取某个近似值则由
* 2
*0 21
2
**
1 0 1 2
()
2
xx xx
xx
x x x x x
此种加速需用两次迭代值进行加工。
1
11
2
11
1
1
11
( )
( )
()
2
k
k
kk
kk
k
k
kk
k
xx
xx
xx
xx
x x x
校 正再 校 正改 进如 果 将 一 次 改 进 值 作 为 一 步,则 计 算公 式 如 下,
Steffensen迭代法
Aitken加速法的加速技巧与原迭代法的结合，即
1 ( ) 1kkxx设 原 迭 代 法 为
2
1
()
()
()
2
kk
kk
kk
kk
k k k
yx
zy
yx
xx
z y x
2
()
( )
2
xx
xx
x x x
其 中
1 ( ) kkxx迭 代 格 式 为,2
1
p
p?
结 论,若 迭 代 公 式 1 是 阶 收 敛 的,则 迭 代公 式 2 是 阶 收 敛 的 。
Newton 迭代法
Newton 迭代法的收敛性
简单 Newton 迭代法
Newton 下山法
Newton 迭代法的重根处理
弦截法
§ 3,Newton 迭代法
0
2 0
0 0 0 0
( ) 0
2
f x x Tay lor
fx
f x f x x - x f x x - x
!
在 真 根 附 近 点 展 开 成 级 数,
非线性问题的最简单解法是线性近似。
将非线性方程线性化，以线性方程的解逐步逼近非线性方程的解，这就是 Newton法的基本思想。
一、牛顿迭代法
1
1 0 0 0 0 ( 0 )
xx
x x f x f x f x
解 出 作 为 近 似 根,
1
N e w to n
/,0,1,2,n n n nx x f x f x n
依 次 产 生 迭 代 格 式,称 法,
0 00 0 'f x f x x xxf
取 线 性 部 分 近 似 代 替
Newton 法的几何解释
1
'
1
x ( 0 )
0 1 0( ) ( )
y x
ffx x x x
与 轴 交 点 为 第 二 个 近 似 根,
0 0 0
0 0 0
,( )
( )
( ) ( ) ( )
f
fx
y f f x
x x x
x x x
当 在 取 定 后 （ 在 真 根 附 近 ）,过作 的 切 线,则 切 线 方 程,
0
1
ξ
(?
0
,f (?
0
))
1 '
'
''
'
2
'
* * ' *
'*
*
()
,
()
()
( )
()
( ) ( )
( )
()
( ) ( ) 0,( ) 0,
( ) 0,
k
kk
k
fx
xx
fx
fx
xx
fx
f x f x
x
fx
x f x f x f x
x
x
对 牛 顿 公 式 其 迭 代 函 数 为由 于假 定 是 的 一 个 单 根,即则 由 上 式 知 由 上 述 定 理 知,牛 顿 法 在根 的 邻 近 至 少 是 平 方 收 敛 的 。
'
'
1
1 0,
( ) 1,( ) ( 1 )
()
( )
( ) 1
1
k
x
xx
x
x
k
kk
k
xe
f x x e f x e x
f x x e
x x x
f x x
xe
xx
x
例,用 牛 顿 法 解 方 程解,
牛 顿 法 迭 代 函 数 为牛 顿 迭 代 公 式 为
0 0,5x?可 先 用 二 分 法 或 经 验 确 定 迭 代 初 值,再 按牛 顿 公 式 进 行 迭 代 。
例,用 牛 顿 法 求 115 的 近 似 值 。
2
*
0
'
2
1
( ) 1 1 5 0,
1 0 1 5,1 1 6,1 0,1 1
( ) 2 0,( ) 2 0,1 1
()
( )
()
115
2
k
kk
k
f x x
f f x
f x x f x x
fx
xx
fx
x
xx
x
解,
取 ＝,
牛 顿 法 迭 代 函 数 为牛 顿 迭 代 公 式 为
2
'
2
10
( ) 0,
()
( )
()
1
0,0,1,2,
22
1,2,,,
k
k k k
kk
kk
f x x a
fx
xx
fx
a
xa a
x x x x k
xx
k x a x
一 般 的,
牛 顿 法 迭 代 函 数 为求 的 牛 顿 迭 代 公 式 为
,>
可 以 证 明,对 一 切 且 序 列 是单 减 的,从 而 迭 代 过 程 收 敛 。
1
1
1
1
2
1
2
11
0
2 2
kk
k
kk
k
k
k
k
a
xx
x
x a x a
x
xa
x a
xa
2
2
可 以 证 明,迭 代 过 程 平 方 收 敛 。
1
3
Pa g e 2 3 9 1 0,; 2 ) l im 0 ;
k
k
k
k
xa
x a C
xa
例,第 题分 析,1 ） 证 明 的 极 限 为
0
22
2
2 2 2 2
22
22
0,0,0 1,2,.
3 / 3,
3 3 3 3 6
33
k
a x x k
x x x a x a
x a x a x x a x x a
x
x a x a
证 明,1 ） 令则
22
0,1,,
3 / 3 0,,.
.
k
x x x l
l l l a l a l l a l a
a
即 迭 代 法 收 敛,设 的 极 限 为 则 有迭 代 序 列 收 敛 于
32
1
33
3
3 2
2
3 / 3
2 l im l im
11
l im l im 0
43
3
k k k
k
kk
kk
k
kk
k
kk
a x a x x a
ax
a x a x
ax
axa
a x x a
a
）
迭 代 式 是 的 三 阶 方 法 。
3
'
3
1 2
0 0 0
1
( ) 1 0 1.5
()
( )
()
1
31
1.5 0 6 0 6
17 9
kk
kk
k
f x x x x
fx
xx
fx
xx
xx
x
x x x
x
例 用 牛 顿 迭 代 法 求 在附 近 的 一 个 根 。
解,牛 顿 法 迭 代 函 数 为牛 顿 迭 代 公 式 为比 较 与,,可 以 发 现 在 取,时,
所 得,,偏 离 较 大 。
Newton法具有收敛快，稳定性好，
精度高等优点，是求解非线性方程的有效方法之一。但它每次迭代均需计算函数值与导数值，故计算量较大。而且当导数值提供有困难时,Newton法无法进行。
二,Newton 迭代法的收敛性
00
0
,
0,
0,0,
f x a b
f x f x
f a f b f x f x
Ne wton x
定 理,设 在 有 限 区 间 上 二 阶 导 数 存 在,
且 不 变 号,在 端 定 满 足则 迭 代 公 式 对 任 何 初 始 值 都 收 敛 。
三、简单迭代法
10
0
/,0,1,2,
/
n n n
x x f x f x n
x x f x f x?
迭 代 格 式迭 代 函 数 为
0
,,
1 1,
2
c x x c f x
fx
x c f x L
c f x
1
收 敛 性,令 =
取 0< 时,迭 代 法 收 敛,
四、下山迭代法
1
11
1,0,1,2,
,
n
nn
n
n
n n n n
n
fx
xx
fx
fx
x x x x n
fx
fx
xx
fx
加 权 平 均由 牛 顿 迭 代 法下 山 迭 代 公 式迭 代 函 数 为为 下 山 因 子,
1
1 1 1 2
12
*
1
,
(,
0,1
kk
k k k
k
f x f x
f x x x
xx
选 取 的 原 则 是 使,
迭 代 停 止 条 件,
或为 预 先 给 定 的 小 正 数 ）
取 。
否 则 减 小,继 续 迭 代 。
3
'
3
1
2
0 1 0
10
( ) 1 0 1.5
()
( )
()
1
32
1
32 3 1
0 6 17.9( )
1.14062( ),
kk
kk
k
f x x x x
fx
xx
fx
xx
xx
x
x x x
xx
例 用 下 山 迭 代 法 求 在附 近 的 一 个 根 。
解,迭 代 函 数 为取,迭 代 公 式 为取,与 偏 离 很 大,
与 偏 离 不 大五,弦截法
1
'
( ),( ),
()
kk
k
f x f x
fx
基 本 思 想,利 用 一 些 函 数 值回 避 导 数 值 的 计 算 。
1
1
1
11
,,,( ) 0
( ),( ),,( ),
( ),( ) 0 ( ) 0
(,,,),
12
k k k r
k k k r
rr
k
k k k k r
x x x f x
f x f x f x
p x p x f x
x
x x x x
rr
＋
设 是 的 一 组 近 似 根,利 用函 数 值 构 造 插 值 多 项 式并 适 当 选 取 的 一 个 根 作 为 的新 的 近 似 根,这 就 确 定 了 一 个 迭 代 过 程,记 迭代 函 数 为,
当 时 为 弦 截 法,当 时 为 抛 物 线 法 。
弦截法
11
11
1
1
1
1
1
1
1
,( ) 0 ( ),( )
( ) ( ) 0
( ) 0,
( ) ( )
( ) ( ) ( )
()
( ),
( ) ( )
k k k k
k
kk
kk
kk
kk
k k k
kk
x x f x f x f x
p x p x
f x x
f x f x
p x f x x x
xx
xx
x x f x
f x f x
设 是 的 近 似 根,利 用构 造 一 次 插 值 多 项 式,并 用 的 根 作 为的 新 的 近 似 根由
1
' 1
1
()
()
( ) ( )
()
k
kk
k
kk
kk
fx
xx
fx
f x f x
fx
xx
此 迭 代 公 式 可 看 作 牛 顿 公 式中 的 导 数 用 差 商 取 代 的 结 果 。
1
1 0 1
1
,.,
k
kk
kk
x
x x x x
xx
弦 截 法 在 求 时 要 用 到 前 面 两 步 的 结 果需 两 个 初 值,而 牛 顿 切 线 法 在计 算 时,只 用 到 前 一 步 的 值 。
弦截法的几何表示
x0 Xx*x1 x2 x3
Y
f(x)<0P
0
P2
P1
弦截法收敛性定理
**
'
01
11
1
*
( ),
( ) 0,
,,
()
( ),
( ) ( )
15
1,6 1 8,
2
k
k k k k
kk
f x x x x
x f x
xx
fx
x x x x
f x f x
px
定理：假设 在根 的邻域 内具有二阶连续导数，且对任意 有 又初值 那么当邻域 充分小时，弦截法将按阶 收敛到根
11
*
11
"
1
11
""
* * *11
1 1 1,
11
,
( ) 0 ( ),
()
( ) ( ) ( ) ( )
2
( ) ( )
( ) ( ) ( )
22
( ) 0
k k k
kk
kk
k k k k
k
x x x
f x p x x x
f
f x p x x x x x
ff
p x x x x x e e
x p x
证,用 数 学 归 纳 法 证 明 迭 代 值 全 属 于 。
首 先 证 明 当 时 必 属 于 。
设,是 以 为 节 点 的 插 值 多 项 式 。
由又 由 于 是 的 根,故 有
* * ' *
1 1 1 1 1 1
*'1
1 2 1
1
( ) ( ) ( ) ( ) ( )
( ) ( )
( ) ( ),
kk
kk
kk
kk
p x p x p x p x x
f x f x
x x f e
xx
"
1
11 '
2
1 2 1 1
"
12
'
()
.
2 ( )
,[,],,
m a x ( )
,.,
2 m in ( )
k k k
k k k k
x
x
f
e e e
f
x x x x
fx
M
fx
对 上 两 个 式 子 联 立由 于 故 当 时记
1
11
1
01
,1,
,
,
,,
k
k
k k k
k
k
Mx
x
e M e e M
x
x x x
选 取 邻 域 充 分 小 以 保 证 则 当与 属 于 时因 由 数 学 归 纳 法 知 一 切 全 属 于
2
2
1 1 1 2
32
4
23
1
( )
0,
k k k k k
k
k k k
k
e M e e M e e
M e e e M
M
ke
由 递 推 不 等 式故 当 时 有 收 敛 性 得 证 。
"
*1
1 1 1 1'
2
"*
*
'*
1 1.*
()
2 ( )
()
.
2 ( )
1
,
k
k k k k k k
z
k k k k
k
f
e e e e M e e
f
fx
M
fx
e d z z z
M
当 充 分 大 时,由这 里令 则 有 差 分 方 程
2
12
1 1 2 2
12
1 0
1,6 1 8,0,6 1 8 ;
,
k
k
kk
k
z
z c c
cc
考 虑 的 特 解,其 特 征 方 程 为故 差 分 方 程 的 通 解 为
（ 为 任 意 常 数 ）
1
1 1 1 1 1 1
11
11
1
1 2 1 1
1 * * *
**
1 1**
1 *
1
,,
1 1 1
( )
11
1
1,61 8.
kk
k
k
k
k
k
z cc
k
z c
k
k
kk
k
k z c
e d d d
M M M
e d d
MM
e
e M e M
M e
－
由 于 当 充 分 大 时故而,
故 有 （ ）
此 说 明 弦 截 法 收 敛 的 阶用弦截法给出埃特金算法的几何解释
() xx用弦截法讨论形如 得方程，给出埃特金算法的几何解释。 yx?
()yx
*P
3P
2P
0P
1P
*x 2x1x 3x
0x
33
21
3 1 3 0
10
2
0 2 1
3
0 1 2
*
2 0 1
3
()
2
.
,,
.
Px
xx
x x x x
xx
x x x
x
x x x
x x x x
x
点 的坐标 满足由此解出此即为加速埃特金公式从图上可知 尽管迭代值 比 和 更远偏离了但按上式定出的 却明显地扭转了这种发散的趋势二、抛物线法
12
22
1
( ) 0,,,
( ),( )
,
,.
k k k
k
f x x x x
p x p x
x
设已知方程 的三个近似根 以这三点为节点构造二次插值多项式 并适当选取 的一个零点 作为新的近似根 这样确定的迭代过程称抛物线法 也称密勒法
()fx
2()Px
*x
1kx? k
x1kx? 2kx?
抛物线法计算公式
21
1 2 1
12
1 1 2 1
2
2
( ) ( ) [,] ( )
+ [,,] ( ) ( ),
[,,]
[,] + [,,] ( )
()
( ) ( )
k k k k
k k k k k
k k k k
k k k k k k k k
kk
kk
p x f x f x x x x
f x x x x x x x
a f x x x
b f x x f x x x x x
c f x
p x a x x
插值多项式令
2
2
*
21
1
2
()
4 2
2
4
,,,,
,.
2 sgn ( )
4
k k k
k k k k
k
kk
k
k k k k
k k k k
kk
kk
kk
k k k k
b x x c
b b a c c
x x x
a
b b a c
x x x x x
x x x
cb
xx
b b a c
在 三个近似根中假定 更接近根 故新的近似根应在 邻近 即 较小于是抛物线计算公式为
*
*
0 1 2
*
*
,( ),
,,,
( ) 0 1,8 4
f x x
x x x x
x f x
x
可 以 证 明 如 果 在 其 零 点 邻 近 三 阶 连 续 可 微 且 初值 充 分 接 近 抛 物 线 法 是 收 敛 的 。 特 别 地,若是 方 程 的 单 根,收 敛 解 为 。
另 一 方 面,在 收 敛 性 的 证 明 中 虽 然 要 求 初 始 值 充 分 接近 根,但 实 际 计 算 表 明,抛 物 线 法 对 初 值 要 求 并 不苛 刻,在 初 值 不 太 好 的 情 况 下 常 常 也 能 收 敛 。 缺 点 是程 序 较 复 杂,并 在 计 算 实 根 的 过 程 中,也 常 常 需 要 采用 复 数 计 算,增 加 了 工 作 量 。 因 此,抛 物 线 法 适 用 于当 ( ) 0fx?初 值 不 太 好 时 求 方 程 的 复 根 的 情 况 。
迭代法
迭代法的加速（ Aitken加速法,Steffensen迭代法）
牛顿迭代法
非线性方程组的迭代法第八章 非线性方程（组）的数值解
( ) 0
fx
f
,求 解 非 线 性 方 程其 中,是 非问 题线 性 函 数,
1
1 1 0
( ) 0,1.
,
( ) si n 0
nn
nn
x
f x a x a x a x a n
f x e x
,代 数 方 程程例例 超 越 方
1,根 的 存 在 性？
2,根 的 分 布 范 围？
3,如 何 选 择 求 根 法,使 之 简 单,有 效,经 济？
( ) [,] [,]
( ) ( ) 0
( ) 0,( ) 0
f x a b a b
f a f b
f a f b
设 在 上 连 续 且 有 且 仅 有 一 个 根 又
。 则 可 用 对 分 法,
不 妨 设
1 1 1 1
1 0,0
2 2 2
,,.
22
a b a b a b
f x f
a b a b
a b b b a a
） 若 输 出 根 否 则,若,
令,反 之
1 1 2 22 ) [,] 1 [,],a b a b对 区 间 重 复 ） 的 计 算,并 产 生
3 ) 0,
22
i i i ia b a bfx
若,则 得 到 根
§ 1,非线性方程实根的对分法 (二分法 )
二分法的收敛性
11 [,] [,] [,]nna b a b a b
二 分 法 产 生 一 个 有 根 区 间,
11
[,]
11
( ) ( )
22
nn
n n n n n
ab
b a b a b a
区 间 长 度,
2nnn banx当 足 够 大 时,取 近 似 值,
1
2
n n
ba
xx?
误 差,
计 算 简 便,容 易 估 计 误 差,但 收 敛 较 慢 。
a x* x0 b
()fx
a1 b1
*
20
1,3 2 ; 0 ;
0,6 3 ; 0,3,3,6 0,3
0,1.5,1.5,3 1.5,3
1,5,2,2 5,2,2 5,3
1,5,2,2 5 1,8 7 5
f x x
c f c x c
c
x
§ 2,迭代法连续。且改写方程,)(0)( xxxf
1 ( ) n n nx x x建 立 迭 代 格 式,,得 到 序 列
{ } ( 0 n fxx?则 若 收 敛 必 收 敛 到 ） 的 根,
1
*
1
* * *
{ } l im
l im l im l im
( ) ( ) 0
nn
nn
n
n n n
n n n
x
xx
x x f x
xx
x x x
若 收 敛,即,则
2
22
0 1 0
2
2 1 1
2
0
1
1 0 1
1
[ [ 0 3 ],
1.2,
1
1 ; 1 ;
1
x x x
x x x
f x x x
x
x x x x x x x
ab,
取
,]=
选迭代过程的几何表示
()yx
yx?
O x* x2 x1 x0 x
y
0P
1Q
1P
2P
*P
2Q
()
()
yx
xx
xy
交点即为真根迭代法需解决的三个问题迭代函数的构造由迭代函数产生的解序列的收敛性序列的收敛速度和误差估计
3* 0( ) 1 0 1,5,f x x x x x例,求 方 程 在 附 近 的 根
3
3
1
k
1 1
1 ( 0,1,2 )
k 0 1 2 7 8
x 1,5 1,3 5 7 2 1 1,3 3 0 8 6 1,3 2 4 7 2 1,3 2 4 7 2
kk
xx
x x k
解,（ ） 将 方 程 改 写 为由 此 建 立 迭 代 公 式迭 代 收 敛 。
3
3
1
k
2 1
1.
k 0 1 2
x 1,5 2,3 7 5 1 2,3 9
kk
xx
xx
（ ） 若 将 方 程 改 写 为建 立 迭 代 公 式迭 代 不 收 敛 。
如何选取合适的迭代函数？下面介绍三个迭代法的收敛定理。
()x?
*
1
,( ) [,]
1 [,] ( ) ;
( 2) 0 1,
,[,],
( ) ( )
( ) [,],
[,],
( ) (
nn
x a b
x a b a x b
L L i psc hi t z
x y a b
x y L x y L i psc hi t z
x x a b x
ab
x x n
1
0
定 理 设 函 数 在 区 间 上 满 足 条 件
（ ） 对 任 意,都 有存 在 常 数 常 数 使 得 对一 切 都 有条 件则 方 程 在 内 有 唯 一 的 根 且 对 任 何初 值 x 迭 代 序 列
*
*
10
0,1,)
x
1
n
n
x
L
x x x
L
均 收 敛 于,并 有
2 ( ) [,]
( ) ( ),( ) [,]
( ) ( ) 0,( ) ( ) 0
[,] 0,
( ) [,]
x a b
x x x x a b
a a a b b b
ab
x x a b
证,存 在 性 由 条 件 （ ） 知 在 上 连 续 。
令 则 在 上 连 续,且故 存 在,使 得 （ ） 即 （ ）,
所 以 方 程 在 内 有 根 。
**
12
* * * * * * * *
1 2 1 2 1 2 1 2
( ) [,]
,2
( ) ( )
x x a b
xx
x x x x L x x x x
唯 一 性 假 设 方 程 在 内 有 两 个 根由 条 件 （ ）,有导 出 矛 盾,唯 一 性 得 证 。
0
* * *
11
**
0
*
0
*
1 1 1
10
[,],
( ) ( )
0 1,l i m
x [,],
( ) ( )
n n n
n
n
n
n
n
k k k k k k
k
x a b
x x x x L x x
x x L x x
L x x
a b x
x
k
x x x x L x x
L x x
对 任 意 由 迭 代 公 式 有依 此 类 推,得因 所 以即 对 任 意 初 值 迭 代 序 列 均 收敛 到 方 程 的 根 。
类 似 地,对 任 意 正 整 数,有
,,np于 是,对 任 意 正 整 数 有
1 1 2 1
12
1 0 1 0 1 0
12
10
10
*
10
( 1 )
1
1
,
1
n p n n p n p n p n p n n
n p n p n
n p p
p
n
n
n
L
p
L
x
L
x x x x x x x x
x x x x x xL L L
xxL L L
L
xxL
x x x
令 得
'
*
1
*
*
,( ) [,]
1 [,] ( ) ;
( 2) 0 1,[,],
( )
( ) [,],
[,],
( ) ( 0,1,)
x
nn
x a b
x a b a x b
L x a b
xL
x x a b x
ab
x x n
x
0
定 理 2 设 函 数 在 区 间 上 满 足 条 件
（ ） 对 任 意,都 有存 在 常 数 使 得 对 一 切 都 有则 方 程 在 内 有 唯 一 的 根 且 对 任 何初 值 x 迭 代 序 列均 收 敛 于,并 有
10
1
n
n
L
x x x
L
'
'
'
,[,]
,
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
( ) ( )
( ) 2
x y a b
xy
x y x y
x y x y
x y L x y
x
证,设 为 上 任 意 两 点,由 微 分 中值 定 理,在 之 间 至 少 存 在 一 点,使 得即 满 足 上 一 定 理 的 条 件 （ ）,故 结 论 成立 。
'( ) ( )
[,]
xx
ab
因 而 构 造 迭 代 函 数 的 原 则 是 使 在 有 根区 间 上 有 尽 可 能 小 的 上 界 。
*
10 1
n
n
Lx x x x
L
误 差 估 计 式 表 明,
L 常 数 越 小,简 单 迭 代 法 收 敛 越 快
1 1 2 1
1 2
11
1
1
1
1
1
1
*
,
1
n p n n p n p n p n p n n
p p
n n n n
n n n
nn
p
L
p
L
x x x x x x x x
L x x x xL
x x xx
xx
对任意正整数 有
）
令得可通过检查 来判断迭代过程应否终止。
（
c os si n / 4 ; 2 4 2,
1.
c os si n / 4,
2
c os sin / 4 1
4
x
x x x x
x
xL
x x x x
x x x
例,能 否 用 迭 代 法 求 解 下 列 方 程,如 果 不 能,试 将 方 程改 成 能 用 迭 代 法 求 解 的 形 式 。
1
分 析,判 断 在 根 的 附 近 能 否 满 足解 1 ＝,有能 用 迭 代 法 求 根 。
1
4 2 4 2,1 0,2 0
12
2 l n 2 2 l n 2 1.38629 1
l n 4 - / l n 2,l n 4 - / l n 2,
1 1 1 1 1
1,
4 l n 2 4 2 l n 2 2 l n 2
l n 4 -
xx
x
kk
x f x x f f
x
x x x x
x
x
xx
＋
2 ＝,令 >,
区 间,内 有 根,但
＝
不 能 直 接 用 该 迭 代 函 数 迭 代 。
改 写 原 方 程 为 则 ＝
－
＝
－
可 以 用 下 述 迭 代 公 式 来 求 解,
/ l n 2
2 ( ) 1 0 f x x x例,用 简 单 迭 代 法 求 方 程 的 根 。
( 1,5 ) 0,2 5 0,( 2 ) 1 0
[ 1,5,2 ]
ff
解,
为 有 根 区 间 。
11
'
1
1 1 ( ) 1,5 1,5 1 ( ) 2 1 2
1 1 1
()
3,1 6 22 1 2 2,5
x x x x
x
x
（ ） 因且
22
'
2 22
1 1 1
( 2 ) 1 ( ) 1,5 1 ( ) 1 2
2 1,5
1 1 1
( )
1,5 2,2 5
x x x
x
x
x
因且
0
[ 1,5,2 ],x?根 据 定 理,任 取 由 这 两 种 等 价方 程 所 构 造 的 简 单 迭 代 方 法 都 收 敛,且 第 一 种所 产 生 的 迭 代 序 列 收 敛 较 快 。
0.2
*
1 1 0
0 5
11
,1,
,
1
[ 0.2 1 ] 55
[ 0.4 1 ] 26
[ 0.5 1 ] 21
k
x
x
xx
x
n
x
kn
x e x
f x x e
x e x e L
ee
L
x e x x x x
L
n
n
n
-5
例,用 简 单 迭 代 法 求 方 程 在,附 近 的 根,
要 求 精 度 =10 。
解,令 =0,显 然 方 程 在 [0.2,1] 有 根,
迭 代 函 数 收 敛迭 代 格 式 为 由 〈,得
，
，
，
* * *
*
'*
**
0
1
*
( ) (,)
()
( ) 1,,,
[,],
( ) ( 0,1,2,)
.
nn
x x O x
x x x
x
x x x
x x n
x
定 理 3,如 果 函 数 在 的 一 邻 域内 连 续 可 微,为 方 程 的 根,且则 存 在 正 数 使 得 对 任 意迭 代 序 列收 敛 于 局 部 收 敛 性
' * * '
* * *
'
**
* * *
**
*
1
( ) (,) ( ) 1,
1,,[,]
( ) 1
( ),
( ) ( ) ( )
( ) [,]
()
nn
x O x x
L x x x
xL
xx
x x x x L x x
x x x
x x x
证：因 在 内连续，且 故存在正数 使得对,有另一方面，由 又有即 。由上面定理知，迭代序列收敛于 。
实际用迭代法计算时，先用对分区间法求较好的初值，然后再进行迭代。
迭代法收敛速度定义
1
**
1
()
()
( 0
11
2
kk
kk
k
p
k
xx
x x x e x x
k
e
CC
e
p
pp
p
定义：设迭代过程 收敛于方程的根,如 果迭代误差当 时成立下列渐进关系式为常数）
则称该迭代过程是 阶收敛的。
为线性收敛,为超线性收敛，
为平方收敛。
()
1
*
' * " * ( 1 ) * ( ) *
*
( ),( )
( ) ( ) ( ) 0 ; ( ) 0
p
kk
pp
x x x
x
x x x x
xp
定理：对于迭代过程 如果 在所求根 的邻近连续，并且则该迭代过程在点 邻近是 阶收敛的。
'*
1
*
()
**
( ) ( ) *
** 1
1
( ) 0 1,( )
()
()
( ) ( ) ( )
!
( ) ( )
()
!!
kk
k
p
p
kk
pp
p k
kk p
k
x x x
xx
x x x x
p
e x
x x x x
p e p
证：由于 故 具有局部收敛性。
将 在根 处展开，由条件有
'
' '
'
( )
[,] ( ) 0,
1 ( ) 1,( ) 0,
2 ( ) 0,( ) 0,
k
k
x
x a b x
x x x
x x x
迭 代 过 程 的 收 敛 速 度 依 赖 于 迭 代 函 数的 选 取 。 如 果 当 时 则 该 迭 代过 程 只 可 能 是 线 性 收 敛 。
特 别 地,
当 序 列 线 性 收 敛 ；
当 序 列 平 方 收 敛 。
迭代法加速（ Aitken法）
2
1
1
21
()
( )
2
k
kk
k k k
k k k
k
x
xx
x x x
x x x
x
设 序 列 线 性 收 敛,迭 代 格 式 为
＝,
且 序 列 平 方 收 敛 。
*
0
1 0 2 1
* * ' *
1 0 1 0
* * ' *
2 1 2 1
'
* * * *
1 0 2 1
*
1
2
( ) ( )
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
( ),
( ) ( )
xx
x x x x
x x x x x x
x x x x x x
xL
x x L x x x x L x x
xx
xx
设 是根 的某个预测值，通过两次迭代校正有由微分中值定理，有假定 改变不大，近似地取某个近似值则由
* 2
*0 21
2
**
1 0 1 2
()
2
xx xx
xx
x x x x x
此种加速需用两次迭代值进行加工。
1
11
2
11
1
1
11
( )
( )
()
2
k
k
kk
kk
k
k
kk
k
xx
xx
xx
xx
x x x
校 正再 校 正改 进如 果 将 一 次 改 进 值 作 为 一 步,则 计 算公 式 如 下,
Steffensen迭代法
Aitken加速法的加速技巧与原迭代法的结合，即
1 ( ) 1kkxx设 原 迭 代 法 为
2
1
()
()
()
2
kk
kk
kk
kk
k k k
yx
zy
yx
xx
z y x
2
()
( )
2
xx
xx
x x x
其 中
1 ( ) kkxx迭 代 格 式 为,2
1
p
p?
结 论,若 迭 代 公 式 1 是 阶 收 敛 的,则 迭 代公 式 2 是 阶 收 敛 的 。
Newton 迭代法
Newton 迭代法的收敛性
简单 Newton 迭代法
Newton 下山法
Newton 迭代法的重根处理
弦截法
§ 3,Newton 迭代法
0
2 0
0 0 0 0
( ) 0
2
f x x Tay lor
fx
f x f x x - x f x x - x
!
在 真 根 附 近 点 展 开 成 级 数,
非线性问题的最简单解法是线性近似。
将非线性方程线性化，以线性方程的解逐步逼近非线性方程的解，这就是 Newton法的基本思想。
一、牛顿迭代法
1
1 0 0 0 0 ( 0 )
xx
x x f x f x f x
解 出 作 为 近 似 根,
1
N e w to n
/,0,1,2,n n n nx x f x f x n
依 次 产 生 迭 代 格 式,称 法,
0 00 0 'f x f x x xxf
取 线 性 部 分 近 似 代 替
Newton 法的几何解释
1
'
1
x ( 0 )
0 1 0( ) ( )
y x
ffx x x x
与 轴 交 点 为 第 二 个 近 似 根,
0 0 0
0 0 0
,( )
( )
( ) ( ) ( )
f
fx
y f f x
x x x
x x x
当 在 取 定 后 （ 在 真 根 附 近 ）,过作 的 切 线,则 切 线 方 程,
0
1
ξ
(?
0
,f (?
0
))
1 '
'
''
'
2
'
* * ' *
'*
*
()
,
()
()
( )
()
( ) ( )
( )
()
( ) ( ) 0,( ) 0,
( ) 0,
k
kk
k
fx
xx
fx
fx
xx
fx
f x f x
x
fx
x f x f x f x
x
x
对 牛 顿 公 式 其 迭 代 函 数 为由 于假 定 是 的 一 个 单 根,即则 由 上 式 知 由 上 述 定 理 知,牛 顿 法 在根 的 邻 近 至 少 是 平 方 收 敛 的 。
'
'
1
1 0,
( ) 1,( ) ( 1 )
()
( )
( ) 1
1
k
x
xx
x
x
k
kk
k
xe
f x x e f x e x
f x x e
x x x
f x x
xe
xx
x
例,用 牛 顿 法 解 方 程解,
牛 顿 法 迭 代 函 数 为牛 顿 迭 代 公 式 为
0 0,5x?可 先 用 二 分 法 或 经 验 确 定 迭 代 初 值,再 按牛 顿 公 式 进 行 迭 代 。
例,用 牛 顿 法 求 115 的 近 似 值 。
2
*
0
'
2
1
( ) 1 1 5 0,
1 0 1 5,1 1 6,1 0,1 1
( ) 2 0,( ) 2 0,1 1
()
( )
()
115
2
k
kk
k
f x x
f f x
f x x f x x
fx
xx
fx
x
xx
x
解,
取 ＝,
牛 顿 法 迭 代 函 数 为牛 顿 迭 代 公 式 为
2
'
2
10
( ) 0,
()
( )
()
1
0,0,1,2,
22
1,2,,,
k
k k k
kk
kk
f x x a
fx
xx
fx
a
xa a
x x x x k
xx
k x a x
一 般 的,
牛 顿 法 迭 代 函 数 为求 的 牛 顿 迭 代 公 式 为
,>
可 以 证 明,对 一 切 且 序 列 是单 减 的,从 而 迭 代 过 程 收 敛 。
1
1
1
1
2
1
2
11
0
2 2
kk
k
kk
k
k
k
k
a
xx
x
x a x a
x
xa
x a
xa
2
2
可 以 证 明,迭 代 过 程 平 方 收 敛 。
1
3
Pa g e 2 3 9 1 0,; 2 ) l im 0 ;
k
k
k
k
xa
x a C
xa
例,第 题分 析,1 ） 证 明 的 极 限 为
0
22
2
2 2 2 2
22
22
0,0,0 1,2,.
3 / 3,
3 3 3 3 6
33
k
a x x k
x x x a x a
x a x a x x a x x a
x
x a x a
证 明,1 ） 令则
22
0,1,,
3 / 3 0,,.
.
k
x x x l
l l l a l a l l a l a
a
即 迭 代 法 收 敛,设 的 极 限 为 则 有迭 代 序 列 收 敛 于
32
1
33
3
3 2
2
3 / 3
2 l im l im
11
l im l im 0
43
3
k k k
k
kk
kk
k
kk
k
kk
a x a x x a
ax
a x a x
ax
axa
a x x a
a
）
迭 代 式 是 的 三 阶 方 法 。
3
'
3
1 2
0 0 0
1
( ) 1 0 1.5
()
( )
()
1
31
1.5 0 6 0 6
17 9
kk
kk
k
f x x x x
fx
xx
fx
xx
xx
x
x x x
x
例 用 牛 顿 迭 代 法 求 在附 近 的 一 个 根 。
解,牛 顿 法 迭 代 函 数 为牛 顿 迭 代 公 式 为比 较 与,,可 以 发 现 在 取,时,
所 得,,偏 离 较 大 。
Newton法具有收敛快，稳定性好，
精度高等优点，是求解非线性方程的有效方法之一。但它每次迭代均需计算函数值与导数值，故计算量较大。而且当导数值提供有困难时,Newton法无法进行。
二,Newton 迭代法的收敛性
00
0
,
0,
0,0,
f x a b
f x f x
f a f b f x f x
Ne wton x
定 理,设 在 有 限 区 间 上 二 阶 导 数 存 在,
且 不 变 号,在 端 定 满 足则 迭 代 公 式 对 任 何 初 始 值 都 收 敛 。
三、简单迭代法
10
0
/,0,1,2,
/
n n n
x x f x f x n
x x f x f x?
迭 代 格 式迭 代 函 数 为
0
,,
1 1,
2
c x x c f x
fx
x c f x L
c f x
1
收 敛 性,令 =
取 0< 时,迭 代 法 收 敛,
四、下山迭代法
1
11
1,0,1,2,
,
n
nn
n
n
n n n n
n
fx
xx
fx
fx
x x x x n
fx
fx
xx
fx
加 权 平 均由 牛 顿 迭 代 法下 山 迭 代 公 式迭 代 函 数 为为 下 山 因 子,
1
1 1 1 2
12
*
1
,
(,
0,1
kk
k k k
k
f x f x
f x x x
xx
选 取 的 原 则 是 使,
迭 代 停 止 条 件,
或为 预 先 给 定 的 小 正 数 ）
取 。
否 则 减 小,继 续 迭 代 。
3
'
3
1
2
0 1 0
10
( ) 1 0 1.5
()
( )
()
1
32
1
32 3 1
0 6 17.9( )
1.14062( ),
kk
kk
k
f x x x x
fx
xx
fx
xx
xx
x
x x x
xx
例 用 下 山 迭 代 法 求 在附 近 的 一 个 根 。
解,迭 代 函 数 为取,迭 代 公 式 为取,与 偏 离 很 大,
与 偏 离 不 大五,弦截法
1
'
( ),( ),
()
kk
k
f x f x
fx
基 本 思 想,利 用 一 些 函 数 值回 避 导 数 值 的 计 算 。
1
1
1
11
,,,( ) 0
( ),( ),,( ),
( ),( ) 0 ( ) 0
(,,,),
12
k k k r
k k k r
rr
k
k k k k r
x x x f x
f x f x f x
p x p x f x
x
x x x x
rr
＋
设 是 的 一 组 近 似 根,利 用函 数 值 构 造 插 值 多 项 式并 适 当 选 取 的 一 个 根 作 为 的新 的 近 似 根,这 就 确 定 了 一 个 迭 代 过 程,记 迭代 函 数 为,
当 时 为 弦 截 法,当 时 为 抛 物 线 法 。
弦截法
11
11
1
1
1
1
1
1
1
,( ) 0 ( ),( )
( ) ( ) 0
( ) 0,
( ) ( )
( ) ( ) ( )
()
( ),
( ) ( )
k k k k
k
kk
kk
kk
kk
k k k
kk
x x f x f x f x
p x p x
f x x
f x f x
p x f x x x
xx
xx
x x f x
f x f x
设 是 的 近 似 根,利 用构 造 一 次 插 值 多 项 式,并 用 的 根 作 为的 新 的 近 似 根由
1
' 1
1
()
()
( ) ( )
()
k
kk
k
kk
kk
fx
xx
fx
f x f x
fx
xx
此 迭 代 公 式 可 看 作 牛 顿 公 式中 的 导 数 用 差 商 取 代 的 结 果 。
1
1 0 1
1
,.,
k
kk
kk
x
x x x x
xx
弦 截 法 在 求 时 要 用 到 前 面 两 步 的 结 果需 两 个 初 值,而 牛 顿 切 线 法 在计 算 时,只 用 到 前 一 步 的 值 。
弦截法的几何表示
x0 Xx*x1 x2 x3
Y
f(x)<0P
0
P2
P1
弦截法收敛性定理
**
'
01
11
1
*
( ),
( ) 0,
,,
()
( ),
( ) ( )
15
1,6 1 8,
2
k
k k k k
kk
f x x x x
x f x
xx
fx
x x x x
f x f x
px
定理：假设 在根 的邻域 内具有二阶连续导数，且对任意 有 又初值 那么当邻域 充分小时，弦截法将按阶 收敛到根
11
*
11
"
1
11
""
* * *11
1 1 1,
11
,
( ) 0 ( ),
()
( ) ( ) ( ) ( )
2
( ) ( )
( ) ( ) ( )
22
( ) 0
k k k
kk
kk
k k k k
k
x x x
f x p x x x
f
f x p x x x x x
ff
p x x x x x e e
x p x
证,用 数 学 归 纳 法 证 明 迭 代 值 全 属 于 。
首 先 证 明 当 时 必 属 于 。
设,是 以 为 节 点 的 插 值 多 项 式 。
由又 由 于 是 的 根,故 有
* * ' *
1 1 1 1 1 1
*'1
1 2 1
1
( ) ( ) ( ) ( ) ( )
( ) ( )
( ) ( ),
kk
kk
kk
kk
p x p x p x p x x
f x f x
x x f e
xx
"
1
11 '
2
1 2 1 1
"
12
'
()
.
2 ( )
,[,],,
m a x ( )
,.,
2 m in ( )
k k k
k k k k
x
x
f
e e e
f
x x x x
fx
M
fx
对 上 两 个 式 子 联 立由 于 故 当 时记
1
11
1
01
,1,
,
,
,,
k
k
k k k
k
k
Mx
x
e M e e M
x
x x x
选 取 邻 域 充 分 小 以 保 证 则 当与 属 于 时因 由 数 学 归 纳 法 知 一 切 全 属 于
2
2
1 1 1 2
32
4
23
1
( )
0,
k k k k k
k
k k k
k
e M e e M e e
M e e e M
M
ke
由 递 推 不 等 式故 当 时 有 收 敛 性 得 证 。
"
*1
1 1 1 1'
2
"*
*
'*
1 1.*
()
2 ( )
()
.
2 ( )
1
,
k
k k k k k k
z
k k k k
k
f
e e e e M e e
f
fx
M
fx
e d z z z
M
当 充 分 大 时,由这 里令 则 有 差 分 方 程
2
12
1 1 2 2
12
1 0
1,6 1 8,0,6 1 8 ;
,
k
k
kk
k
z
z c c
cc
考 虑 的 特 解,其 特 征 方 程 为故 差 分 方 程 的 通 解 为
（ 为 任 意 常 数 ）
1
1 1 1 1 1 1
11
11
1
1 2 1 1
1 * * *
**
1 1**
1 *
1
,,
1 1 1
( )
11
1
1,61 8.
kk
k
k
k
k
k
z cc
k
z c
k
k
kk
k
k z c
e d d d
M M M
e d d
MM
e
e M e M
M e
－
由 于 当 充 分 大 时故而,
故 有 （ ）
此 说 明 弦 截 法 收 敛 的 阶用弦截法给出埃特金算法的几何解释
() xx用弦截法讨论形如 得方程，给出埃特金算法的几何解释。 yx?
()yx
*P
3P
2P
0P
1P
*x 2x1x 3x
0x
33
21
3 1 3 0
10
2
0 2 1
3
0 1 2
*
2 0 1
3
()
2
.
,,
.
Px
xx
x x x x
xx
x x x
x
x x x
x x x x
x
点 的坐标 满足由此解出此即为加速埃特金公式从图上可知 尽管迭代值 比 和 更远偏离了但按上式定出的 却明显地扭转了这种发散的趋势二、抛物线法
12
22
1
( ) 0,,,
( ),( )
,
,.
k k k
k
f x x x x
p x p x
x
设已知方程 的三个近似根 以这三点为节点构造二次插值多项式 并适当选取 的一个零点 作为新的近似根 这样确定的迭代过程称抛物线法 也称密勒法
()fx
2()Px
*x
1kx? k
x1kx? 2kx?
抛物线法计算公式
21
1 2 1
12
1 1 2 1
2
2
( ) ( ) [,] ( )
+ [,,] ( ) ( ),
[,,]
[,] + [,,] ( )
()
( ) ( )
k k k k
k k k k k
k k k k
k k k k k k k k
kk
kk
p x f x f x x x x
f x x x x x x x
a f x x x
b f x x f x x x x x
c f x
p x a x x
插值多项式令
2
2
*
21
1
2
()
4 2
2
4
,,,,
,.
2 sgn ( )
4
k k k
k k k k
k
kk
k
k k k k
k k k k
kk
kk
kk
k k k k
b x x c
b b a c c
x x x
a
b b a c
x x x x x
x x x
cb
xx
b b a c
在 三个近似根中假定 更接近根 故新的近似根应在 邻近 即 较小于是抛物线计算公式为
*
*
0 1 2
*
*
,( ),
,,,
( ) 0 1,8 4
f x x
x x x x
x f x
x
可 以 证 明 如 果 在 其 零 点 邻 近 三 阶 连 续 可 微 且 初值 充 分 接 近 抛 物 线 法 是 收 敛 的 。 特 别 地,若是 方 程 的 单 根,收 敛 解 为 。
另 一 方 面,在 收 敛 性 的 证 明 中 虽 然 要 求 初 始 值 充 分 接近 根,但 实 际 计 算 表 明,抛 物 线 法 对 初 值 要 求 并 不苛 刻,在 初 值 不 太 好 的 情 况 下 常 常 也 能 收 敛 。 缺 点 是程 序 较 复 杂,并 在 计 算 实 根 的 过 程 中,也 常 常 需 要 采用 复 数 计 算,增 加 了 工 作 量 。 因 此,抛 物 线 法 适 用 于当 ( ) 0fx?初 值 不 太 好 时 求 方 程 的 复 根 的 情 况 。
