三、迭代收敛的加速方法
2.斯特芬森迭代法
• 加速方法
- 将埃特金加速技巧与不动点迭代结合
x0 y0 z0
x1
y1
z1
x2 y 2
z2

yk ( xk ), z k ( yk )
( y k xk ) 2 xk 1 xk z k 2 y k xk
四、牛顿法
1.牛顿法的基本算法
f ( xk ) m m
收敛速度？
xk 1 x 0 m 1 m 1 xk k 1 1, 线性收敛. m xk 0 m
四、牛顿法
2. 收敛性
•
f ( x) 牛顿法就是对 ( x) x f ( x) 的不动点迭代法
• 重根情形( f '(x*)=0 ,...,f (m-1)(x*)=0, f (m)(x*)≠0) - 修正牛顿法 :
原则上确定迭 代次数，但它 由于含有信息 L而不便于实 际应用.
(2.5)
(2.6)
| xk x* |
1 | xk 1 xk | . 1 L
二、不动点迭代法
3. 存在性与收敛性
• 全局收敛的充分条件
- 定理2 设(x) 满足定理1中两条件，则对任意 x0∈[a, b]，迭代法收敛，并有误差估计式
| ( x) ( y ) | L | x y |;
则(x)在[a, b]上存在唯一的不动点x*.
二、不动点迭代法
3. 存在性与收敛性
• 全局收敛的充分条件
- 定理2 设(x) 满足定理1中两条件，则对任意 x0∈[a, b]，迭代法收敛，并有误差估计式
Lk | xk x* | | x1 x0 | . 1 L
Tangent line : y f ( x0 ) f ( x0 )( x x0 )
• 牛顿迭代法的几何解释 y
x1 x0
f ( x0 ) f ( x0 )
x*
x
x0
f ( x1 ) x2 x1 f ( x1 )
x 2x 1
二、牛顿法应用举例
例7 用牛顿法求方程x e 解：牛顿迭代公式为
解：
3 (2) xk 1 xk 1,
0
1 2
1.5
1.35721 1.33086
3
4 5
1.32588
1.32494 1.32476
x0 1.5, x1 2.375, x2 12.39, .
6
7
1.32473
1.32472
二、不动点迭代法
2. 不动点迭代法
( x) 3 x 1
四、牛顿法
2. 收敛性
•
f ( x) 牛顿法就是对 ( x) x f ( x) 的不动点迭代法
• 单根情形( f '(x*)≠0 )
- 例 用牛顿法求f(x)=x2-a (a>0)的根的收敛性及 收敛速度. - 解 f '(√a)=2√a≠0，平方收敛
xk 1 a 2 1 . 2 收敛速度 k ( xk a ) 2 2 a 2 a lim
二、不动点迭代法
1.不动点
• 不动点
- 如果 x* ( x*) ，则称x*为 ( x) 的一个不动点
• 方程的根与不动点
- 方程 f ( x) 0总可以写成等价形式 x ( x) - x*为方程 f ( x) 0 的根等价于x*为 x ( x) 的不 动点
二、不动点迭代法
1.3203
1.3242
−
−
一、二分法
4. 二分法的优缺点
• 二分法的优点是算法简单，且总是收敛的，缺 点是收敛太慢
一、二分法
习题：
考虑方程 x 4 =x 3 +10 .
1) 求一个长度为1的区间 [a,b] ，使方程在其中有一 个解.
2) 以[a,b]开始，要算出10-10的之内的解需要多少步 二分法？用整数回答.
二、不动点迭代法
2. 不动点迭代法
( x) x 3 1
不动点迭代法收敛： 1. 不动点存在 2. 迭代序列收敛
二、不动点迭代法
3. 存在性与收敛性
• 定理1（不动点存在唯一性定理） 设(x)∈C[a, b]满足以下两个条件： 1). 对任意x∈[a, b]有a≤(x)≤b. 2). 存在正数L& 求x x 1 0在[1.0,1.5]内的一个实根，准确到 小数点后2位.
k 0 1 ak 1.0 1.25 bk 1.5 xk 1.25 1.375 f(xk)符号 − +
3
2
3 4 1.3125
1.375
1.3125
1.3438
−
+ +
1.3438
1.3281
5
6 1.3203
1.3281
①考察有根区间[a,b]，检查中点 c (a b) 2上的 函数值
②若f (c)=0，c为f (x)=0的根
否则若f (a)f (c)<0，有根在[a,c]区间中
否则若f (c)f (b)<0，有根在[c,b]区间中 ①对规模更小的有根区间，重复以上步骤，直到 区间长度小于ε
一、二分法
3. 二分法的一个例题
• 设 x*是方程 f (x)=0 的根, xk是x*的近似值.将 f (x)在 xk 附近展开, 有
f ( xk ) f ( xk )( x xk ) 0
牛顿迭代法 x0 初始估计; f ( xk ) xk 1 xk . f ( xk )
四、牛顿法
1.牛顿法的基本算法
3 3 （2）xk 1 ， ( x) 2 ， ( x*) 1; xk x 1 2 x 不同不动点迭代 3 ( x*) 1 （3）xk 1 xk ( xk 3)， ( x) 1 ， 0.134; 收敛速度不一样 4 2 2 1 3 1 3 （ 4）xk 1 ( xk )， ( x) (1 2 )， ( x*) 0. 2 xk 2 x
非线性方程的数值解法
二分法 不动点迭代法
牛顿法 求根问题的敏感性与多项式的零点
一、二分法
1. 二分法的理论基础
• 介值定理
- 设f 是区间[a,b]上的连续函数，满足f (a)f (b)<0 ，那么f在a与b之间有一个根，即存在一个数r （a<r<b），使f(r)=0.
一、二分法
一、二分法
2. 二分法的求解步骤
k xk 迭代法(1) 迭代法(2) 迭代法(3) 2 1.5 2 1.5 ‫׃‬ 2 1.75 1.73475 1.732631 ‫׃‬ 迭代法(4) 0 1 2 3 ‫׃‬ x0 x1 x2 x3 ‫׃‬ 2 3 9 87 ‫׃‬ 2 1.75 1.732143 1.732051 ‫׃‬
二、不动点迭代法
f ( xk ) xk 1 xk m 或 f ' ( xk )
( xk ) f ( x) xk 1 xk ， ( x) ， ' ( xk ) f ' ( x)
均局部平方收敛于x * .
四、牛顿法
习题：
▪ 1）求f(x)=sin x+x2cos x-x2-x的根x*=0的重数，并估 计牛顿法收敛到6位正确小数所需步数(设x0=1).
一、不动点迭代法
习题：
2 ( x ) x 2 x 2 的每一个不动点，并确定不动 ▪ 1）求
点迭代是否局部收敛于它.
三、迭代收敛的加速方法
1.埃特金加速收敛方法
• 加速方法
x0 x1 x1 x2 x2 x3 x3
xk 1 ( xk ) , k 0 ,1,
( xk 1 xk ) 2 xk 1 xk xk 2 2 xk 1 xk
四、牛顿法
2. 收敛性
•
f ( x) 牛顿法就是对 ( x) x f ( x) 的不动点迭代法
• 重根情形( f '(x*)=0 ,...,f (m-1)(x*)=0, f (m)(x*)≠0) - ( x*) 1 1 0, ' ( x*) 0
m
- 因此牛顿迭代法局部线性收敛，
第七章 非线性方程的数值解法
一些基本概念
▪ 非线性方程
3 2 • 如 f ( x) x 11.1x 38.8 x 41.77
▪ 方程的根
• 如果实数 x * 满足 f ( x*) 0 ，则称 x * 为方程的根
▪ m重根
m • 若 f ( x) 能分解为 f ( x) ( x x*) g ( x)，则称 x *为方 程的m重根
只要相邻两次 计算结果的偏 差足够小即可 保证近似值xk 具有足够精度
Lk | xk x* | | x1 x0 | . 1 L
| xk x* | 1 | xk 1 xk | . 1 L
(2.5)
(2.6)
二、不动点迭代法
3. 存在性与收敛性
• 局部收敛性
- 定义1 设(x)有不动点x*，若对任意x0∈{ x* 的某个邻域R}，迭代公式(2.2)产生的序列 {xk}∈R，且收敛到x*，则称迭代法(2.2)局部 收敛.
2. 不动点迭代法
• x0=初始估计 • xk 1 ( xk ) , k 0,1,
当步数趋于无穷时，数列xk可能收敛，也可能不收敛。 如果φ连续且xk收敛到x*，那么x*就是一个不动点。
二、不动点迭代法
2. 不动点迭代法
例3 求x3 x 1 0在1.5附近的根x * .
k xk
xk e xk xk 1 xk 1 xk