13:30
16/25
表5 初值取 1.5 时牛顿迭代法速度
n xn 0 1.5 1 1.2666666 2 1.1385620 3 1.0707773 4 1.0357918 5 1.0180008 6 1.0090271 7 1.0045203 8 1.0022618 9 1.0011313 10 1.0005657 11 1.0002829 13:30
2
2
xn 1 2 1 2 2 xn ( xn 2 )
| x n1 2 | 1 lim 2 n | x 2| 2 2 n
l i mxn 2
n
由此可知平方根算法具有 2 阶收敛速度。
思考: 如何求倒数、平方根和立方根？
9/25
Newton迭代法的局部收敛性 定理2.7 设 f(x) 在点x*的某邻域内具有二阶连 续导数, 且 f(x*)=0和 f′(x*) ≠ 0, 则对充分靠近 点x*的初值x0, Newton迭代法至少平方收敛。 f ( x) f ( xn ) ( x) x xn 1 xn f ( x ) f ( xn ) * * * * 2 ( x ) f ( x ) f ( x ) / [ f ( x )] 0 1 收敛
11/25
注释1:
牛顿迭代法 : xn1 xn f ( xn ) / f ( xn )
为了二次收敛有意义我们需要f′(x)相除, 这 个假设是关键的。
f(x)=x3 –3x + 2 = 0 在x*=1附近 源自 ( x ) 013:30
12/25
注释2:
Newton方法收敛性依赖于x0 的选取。存 在 x0使Newton迭代法陷入死循环。
xn
| en | 5.00e-001 5.00e-001 1.62e-001 4.57e-002 5.52e-003 1.72e-004 6.31e-007 7.24e-011
| en+1 |/| en |1.618
1.5347 0.4978 0.8691 0.8109 0.7742 0.7785 0.7778
给定初值 x0 , 迭代产生数列
x0, x1, x2,· · · , xn, · · ·
13:30
4/25
设 x*是方程 f(x)=0 的根, x0是x*的近似值。 在 x0 附近对函数做局部线性化 化难为易
化繁为简 f ( x) f ( x0 ) f ( x0 )( x x0 )
f(x ) = 0
1 m重根, ( x ) 1 1 n
*
13:30
18/25
若 x*是 f(x)=0 的 m 重根,修正的牛顿迭代法 f ( xn ) 1/m或f(x)/f′(x) [ f ( x )] xn1 xn m f ( xn ) 单根 为二阶收敛
m=2
xn1
f ( xn ) xn 2 f ( xn )
x
0
x0 x 0
x*
13:30
13/25
Newton迭代法的变型－弦截法
由于
f ( xn ) f ( x n 1 ) f ( xn ) xn xn -1
代入牛顿迭代格式
xn 1 f ( xn ) xn f ( xn )
x1 x0

13:30
f ( xn ) xn 1 xn ( x n x n 1 ) f ( x n ) f ( x n 1 )
| en | 5.00e-001 2.66e-001 1.38e-001 7.07e-002 3.57e-002 1.80e-002 9.02e-003 4.52e-003 2.26e-003 1.13e-003 5.65e-004 2.82e-004
| en+1 |/| en |
0.5333 0.5196 0.5108 0.5057 0.5029 0.5015 0.5007 0.5004 0.5002 0.5001 0.5000
| en | 5.00e-001 3.33e-002 1.85e-004 5.52e-009 | en+1 |/| en |2 0.1333 0.1639 0.1667
19/25
表5 x*为二重根时修正的牛顿迭代实验
n
0 1 2 3
13:30
xn 1.5 1.03333333333 1.00018214936 1.00000000552

f n ( x ) x2
f 2 ( x ) xn f n ( x ) xn
f1 ( x ) xn
f ( x0 ) f ( x0 )( x x0 ) 0 f ( x0 ) x1 x0 f ( x0 )
x*
x0 x1
x1比x0更接近于x*
13:30
5/25
应用——求正数平方根算法
设C > 0,
x C
2 n
x2 – C = 0
f ( x ) 2 x
令 f(x ) = x 2 – C , 则
20/25
迭代方法比较 二分法
收敛速度慢
函数值的正负号
不动点家族(牛顿法)
收敛速度快(特别快)
函数值(函数的导数值) 收敛是有条件的
总是收敛
13:30
21/25
非线性方程组: Gauss–Newton方法
F ( x) 0
F ( x ) F ( x ( k ) ) F ( x ( k ) )( x x ( k ) ) F ( x ( k ) )( x x ( k ) ) F ( x ( k ) )
3 n
x 10 xn 20 牛顿迭代格式 xn1 xn 2 3 xn 10 表2 牛顿迭代法实验 n xn | en | 0 1.5 1 1.59701492537 0.002452808741981 2 1.59456374876 1.632137654805e-06 3 1.59456211663 7.227551890309e-13 4 1.59456211663 2.220446049250e-16 13:30
n
*
13:30
1/25
《数值分析》4
Newton迭代格式
Newton迭代法的收敛性
Newton迭代法收敛速度
弦截法迭代格式
13:30
2/25
Nature and Nature' law lay hid in night. God said, "Let Newton be," and all was light. Alexander Pope 13:30
15/25
表4 初值取 – 1.5 时牛顿迭代法速度
n 0 1 2 3 4 5
xn | en | | en+1 |/| en |2 -1.5 5.00e-001 -2.33333333333 3.33e-001 1.3333 -2.05555555555 5.55e-002 0.5000 -2.00194931773 1.94e-003 0.6316 -2.00000252829 2.52e-006 0.6654 -2.00000000000 4.26e-012 0.6667
14/25
例3.已知方程
有两根:
x 3x 2 0 * * 参考: 数值分析基础, 关冶 陆金甫 x1 2 x2 1
3
取根附近值做初值,分析牛顿迭代法实验的数据。
表3 弦截法收敛速度实验
n 1 2 3 4 5 6 7 8
-1.5 -2.5 -1.83783783783 -1.95420890762 -2.00552244119 -1.99982796307 -1.99999936831 -2.00000000007
不动点框架:
| ( x) | 1
收敛性
( x*) ( x*) ( r 1) ( x*) 0 ( r ) ( x*) 0
收敛速度
x0 x1 ( x0 ) xn ( xn1 )
lim ( xn ) x
set the interval or the starting point (find a range of xvalues over which the function changes sign) iteratively refine the initial guess with a root-finding algorithm (bisection is dependable but slow; Newton is fast if the initial value is good)
2
2
只要x0 0, xn 2 (n 1) (有界)
2 2 xn 1 2 xn1 xn [ xn ] xn = 0 (单调下降) 2 xn 2 xn
13:30
8/25
1 2 xn1 2 [ xn ] 2 2 xn
1 [ xn 2 1 ] ( xn 2)2 2 xn xn
17/25
推论: 设 x*是 f(x)=0 的二重根, 则牛顿迭代法只具
有一阶收敛。
证: x*是二重根 f(x)=(x – x*)2g(x) * * f ( x) ( x x )[2 g( x) ( x x ) g( x)] ( x x * ) g( x ) ( x) x * 2 g( x ) ( x x ) g( x ) 1 * ( x ) 1 牛顿迭代法只是一阶收敛。 2
3/25
x x ( x) f ( x) ( x)
( x ) 1 ( x ) f ( x ) 0