第2章非线性方程求解

15
作业：P29
1. 用MATLAB编程实现第7题。 2. 14题
15
2.5 埃特金加速算法
若将一般迭代法与弦截法结合使用,往往可以加速迭代的收敛过程 讨论形如x = ϕ ( x )的方程，令xk是x = ϕ ( x )的一个近似解, 应用一般迭代 公式则有 : xk +1 = ϕ ( xk ) xk +1 = ϕ ( xk +1 )
2 k +1
x k − 2 x k + 1 + x k +1
此 即 为 加 速 埃 特 金 公 式.
17
校正 再校正 改进
x k +1 = ϕ ( xk ) x k +1 = ϕ ( x k +1 ) xk +1 ≈ xk x k +1 − x
2 k +1
xk − 2 x k +1 + x k +1
此时,X*为F(x)的单根,所以是2阶收敛. 但要用到二阶导数.（见P27例9）
22
See you next time!
习题2 1,4,7,13,14
19
⎧ ⎪ 3 x k +1 = xk − 1 ⎪ 3 ⎪ ⎨ x k +1 = x k +1 − 1 ⎪ 2 ⎪ x = xk x k +1 − x k +1 ⎪ k +1 xk − 2 x k +1 + x k +1 ⎩
仍取x0=1.5,计算结果。
20
2.7 Newton法的改进(IV)---重根情形
f1 = f ( x1 )，f1′ = f ′( x1 )
⎧ x1 − x0 , 当 x1 < c时； ⎪ 3.控制 计算 δ = ⎨ x1 − x0 c通常取1 ， ，当 x1 ≥ c时。 ⎪ x 1 ⎩ 判断若 δ < ε ，计算结束，取 x1为结果；否则以(x1,f1,f1') 代替(x0,f0,f0 ')转 2 继续执行。
其 中 迭 代 函 数 ϕ x) = x − f ( x) / f '( x) （ 1 * ' ' ≠ 0 .且 ϕ（ x * ) < 1， ϕ（ x ) = 1 − m 所以牛顿法求重根只是线性收敛。
21
方法一. 若已知重数m(m>1),则利用m构造新的迭代公式:
f ( xk ) xk +1 = xk − m ' f ( xk )
先用一般迭代公式进行两次的迭代，然后进行运算组 合得到埃特金公式。虽然每次迭代的计算工作量增加了， 但却大大减少了迭代次数，整个迭代过程加速了，因此， 总的计算工作量减少。
18
例：用埃特金迭代法求 x3-x-1=0 在(1,1.5)内的根。 解： 前面已经提到,迭代公式 x k+1=x3k-1, k=0,1,2,… 是发散的。 现用埃特金算法来求根,其迭代公xk +1
xk
从图上可知,尽管迭代值xk +1比xk 和xk +1更远偏离了x* , 但按上式定出的xk +1却明显地扭转了这种发散的趋势
16
xk +1 − xk +1 x − xk +1 = x − xk xk +1 − xk
由此可解得 x = x k+1 = x k x k +1 − x
——Taylor展开线性化 (1)
f(x)=0
近似于
f ( xk ) = xk − f ′( xk )
f(xk)+ f′(xk)(x-xk)=0
从(1)解出x,
xk +1
记为xk+1 ,则
( k = 0,1,...) (f ′( xk ) ≠ 0) (2)
应用公式（2）来解方程的方法就称为牛顿迭代法。 它是解代数方程和超越方程的有效方法之一.
•
ϕ ( x) = x −
f ( x) f '( x )
• Newton迭代是局部线性化方法,它在单根附近 具有较高的收敛速度. • 方法有效前提:
f ' ( xk ) ≠ 0
牛顿迭代法的优缺点
优点： 在单根附近, 牛顿迭代法具有平方收敛的速 度，所以在迭代过程中只要迭代几次就会得到很精 确解。 缺点: 1. 牛顿迭代法计算量比较大:因每次迭代除 计算函数值外还要计算微商值; 2. 选定的初值要接近方程的解，否则有可能得 不到收敛的结果; 3. 重根情形下为局部线性收敛;
例：求解方程exp(x)+10*x-2=0的根,要求误差 不超过0.5*10^(-3) 。
[k,xk,yk,piancha,xdpiancha]= newtonqx(0,0.5*10^(-3),0.5*10^(-3),1000) x1 = 0.09052510858339 n= 2 [k,x,wuca,yx]= erfen(0,1,0.5*10^(-3)) x1 = 0.09033203125000 n = 10 iteration(0,inline('(2-exp(x))/10'),0.5*10^(-3),1000) x1 =0.09051261667437 n =4
所以，Newton法至少二阶收敛.
( xk +1 − x * ) f " ( x* ) lim = x →∞ ( x − x * ) 2 2 f ' ( x* ) k
例题：写出求解x6 − 5 = 0的牛顿迭代公式，并求lim
k →∞
( x − 5)
6 k
xk+1 − 6 5
2
8
Newton迭代法的特征 Newton迭代公式是一种特殊的不动点迭代,其迭 代方程为:
点xk+1满足该弦的方程,即有
0 = f ( xk ) + f ( xk ) − f ( xk −1 ) ( xk +1 − xk ) xk − xk −1
从而可求得弦截迭代公式
f ( xk ) xk +1 = xk − ( xk − xk −1 ) f ( xk ) − f ( xk −1 )
13
5
4. Newton迭代法收敛定理 定理2.3.1 '' 设x * 是f ( x) = 0的一个单根，若在x *的某个邻域R内f ′′( x) f 存在且连续，则对任意初值x0 ∈ R，牛顿法收敛，即具有
局部收敛性，且至少是二阶收敛。 ( xk +1 − x* ) f '' ( x* ) lim ( xk − x* )2 = 2 f ' ( x* ) = c k →∞
3、弦位法算法的步骤
1.给定初始值x0，x1及精度ε；
2.计算f0 = f ( x0 )，f1 = f ( x1 )及x2 = x1 − f ( x1 )( x1 − x0 ) /[ f ( x1 ) − f ( x0 )]
⎧ x2 − x1 , 当.. x2 < c时； ⎪ 3.计算 δ = ⎨ x2 − x1 c通常取1 ， ，当... x2 ≥ c时。 ⎪ x 2 ⎩ 判断若 δ < ε ，计算结束，取 x2 为结果； 否则 x1 =x 2 转 2 继续执行。
与x轴(y=0)的交点x，作为下一个迭代点xk+1 ,即
x k +1 = xk
−
f ( xk ) f '( xk )
Newton迭代法又称切线法.
3、牛顿迭代法的步骤
1.准备 给定初始值x0 及精度ε；计算f 0 = f ( x0 )，f 0′ = f ′( x0 )
并判断若f 0′=0,STOP, 否则转2; f0 2.迭代 计算x1 = x0 − 迭代一次，得到新的近似值x1，计算 f 0′
此时, ϕ ( x ) = x − m 不实用: m往往不确定. 方法二. 取 F ( x ) =
f ( x) f ' ( x)
f (x) f '(x)
,ϕ ' ( x * ) = 0
, 至少2阶收敛.
,再对函数F(x)用Newton迭代:
'
F ( xk ) f ( xk ) f ( xk ) xk +1 = xk − ' = xk− ' [ f ( xk )]2 − f ( xk ) f '' ( xk ) F ( xk )
证：将f(x)在 xn 处作2阶Taylor展开,并将解x*代入 证：
∴
| xn +1 − x* | lim = c (c ≠ 0) n →∞ x − x* | p n
∴ x* = xn − f " ( ξn ) f ( xn ) f " ( ξn ) ( x * − xn )2 − ( x * − xn )2 = xn+1 − 2 f ' ( xn ) f ' ( xn ) 2 f ' ( xn )
n→ ∞
注意到ξn 在xn 及x*之间,及 lim x n = x *
xn+1 − x* xn − x =
* 2
,故
f " ( ξn ) f " ( x* ) = → = * 2 f ' ( xn ) 2 f' ( x )
> 0(二阶收敛 )若 f "( x * ) ≠ 0 = 0(大于二阶收敛 )若 f "( x * ) = 0
它对应的迭代方程为
f ( x) x= x− f ′( x )
f ( x) f ′( x )
显然是f(x)=0的同
( f ′( x ) ≠ 0)
解方程，故其迭代函数为
ϕ( x) = x −
2. Newton迭代法的几何意义 用f(x)在 xk 处的切线