数值分析迭代加速牛顿法及弦截法
- 格式：pptx
- 大小：441.85 KB
- 文档页数：34
下载文档原格式
合集下载
数值分析-牛顿法
切线
收敛比Newton’s Method 慢，且对初值要求同样高。
/* tangent line */
x1 x0
切线斜率
割线斜率
f ( xk )( xk xk 1 ) f ( xk ) f ( xk 1 )
f ( xk )
f ( xk ) f ( xk 1 ) xk xk 1
保证产生的序列
{xk}单调有界
证明：以 f ' ( x) 0, f "( x) 0, f ( x ) 0 为例证明
0
将f(x*)在 xk 处作Taylor展开
* *
f "(k ) * 0=f ( x ) f ( xk ) f '( xk )( x xk ) ( x xk )2 2! f (x ) f "( ) * * 2
x*
x2
x
x1 x0
牛顿法也称为切线法
f ( x1 ) x2 x1 f ( x1 )
二、牛顿法的收敛性与收敛速度
（局部收敛性定理） 设 f (x)C2[a, b]，若 x* 为 f (x)
在[a, b]上的根,且 f (x*) 0，则存在 x* 的邻域 U ( x*) 使得任取初始值 x0 U ( x*) ，Newton 法产生的序列 { xk } 收敛到 x*，且满足
| xk 1 x* | | f ( x*) | lim 2 k | x x* | 2 | f ( x*) | k
至少平方收敛
证明：Newton法实际上是一种特殊的迭代法
f ( x) g ( x) x f ( x)
f ( x*) f ( x*) g ( x*) 0 1 在x*的附近收敛 2 f ( x*)
Newton法快速弦截法的实验报告
Newton 快速弦截法的实验报告一：实验题目：newton法，快速弦截法。
二：实验目的：通过用MATLAB语言计算newton法，弦截法对两种方法的结果进行分析。
三：实验内容：a：了解MATLAB语言的用法b：用这两种方法求线性方程组四：实验方法与步骤：Newton法Function [x,k]=Mendnewton(f,x0,emg)[f1,d1]=feval(f,x0);k=1;x(1)=x0;x(2)=x(1)-f1/d1;while abs(f1)>emgu=1;k=k+1;[f1,d1]=feval(f,x(k));X(k+1)=x(k)-u*f1/d1;[f2,d2]=feval(f,x(k+1));While abs(f2)>abs(f1)U=u/2;X(k+1)=x(k)-u*f1/d1;[f2,d2]=feval(f,x(k+1));endend例：用牛顿下山法求方程f(x)= 的根，使精度达到10 初值分别选取为：（1）x0=-1;(2)x0=2.0;编写函数名func3.mFunction [f,d]=func3(x)F=sqrt(x^2+1)-tan(x);D1=’sqrt(x^2+1)-tan(x)’;D=subs(diff(d1));在命令窗口输入：f=@func3;[x,k]=Mendnewton(f,x0,10^-6);若选初值为x0=-1;运行结果为：迭代次数k x值f(1)=feval(f,x(k))值1 -7.069047932971935e-001 2.078789280010764e+0002 1.942400972108479e-001 8.219695728408301e-0013 1.163518073303871e+000 -7.838374932606165e-0014 1.023918977930554e+000 -2.113030290935414e-0015 9.530711345686330-001 -2.606996588743926e-0026 9.416925081385333e-001 -5.085688425774393e-0047 9.414616152761416e-001 -2.012113482496858e-0078 9.414615238528302e-001 -3.153033389935445e-014若选初值为x0=2.0;运行结果如下：迭代次数k x值f1(kfeval(f,x(k))值1 2.905969917234289e+000 3.313289980588459e+0002 3.829942435553551e+000 3.135774879468060e+0003 4.382754035040099e+000 1.572413838570136e+0004 4.474505813415593e+000 4.607393526441488e-0015 4.501556126032599e+000 -6.131570643391715e-0026 4.498750820792893e+000 -8.285614610334946e-0047 4.498711866735406e+000 -1.555631969907267e-0078 4.498711859418998e+000 -1.154631945610163e-014 快速弦截法：function [x,k]=Fast_chord(f,x1,x2,emg);k=1;y1=feval(f,x1);y2=feval(f,x2);x(k)=x2-(x2-x1)*y2/(y2-y1);y(k)=feval(f,x(k));k=k+1;x(k)=x(k-1)-(x(k-1)-x2)*y(k-1)/(y(k-1)-y2);while abs(x(k)-x(k-1))>emgy(k)=feval(f,x(k));x(k+1)=x(k)-(x(k)-x(k-1))*y(k)/(y(k)-y(k-1));k=k+1;end用快速弦截法求解方程4cos x=e 的根，要求精度为10 ，初值为：x1=45度；x2=90度编写函数文件func4.mFunction f=func4（x）F=exp(x)-4*cos(x)在命令窗口输入：f=@func4; [x,k]=Fast_chord(f,pi/4,pi/2,10^-6);运行结果如下：迭代次数k x值f1(k)=feval(f,x(k))值1 8.770025972944068e-001 -1.541498847256566e-0012 8.985446421856659e-001 -3.497120992034475e-0023 9.048658349261991e-001 4.359577241643819e-0044 9.047880039957831e-001 -1.201259723249137e-0065 9.047882178657145e-001 -4.102540529515864e-011五：结果分析与讨论：newton迭代法对算法的局部收敛性，优缺点分析如下具有收敛快，形式简单等优点，但它对初始值要求较高，需计算n+n2个函数值及导数值，求解过程计算量较大，它也是一种不动点法，是以曲线的切线与x 轴的焦点作为曲线与x轴的交点的近似值弦截法：对算法的局部收敛性，优缺点等分析如下：弦截法是两步法，他必须给出两组初始值x0,x1，通常取根的端点即可，其收敛速度大概为简单迭代法的1.618倍，从几何上看，弦截法是以曲线上两点的割线与x轴的交点,作为曲线与x轴的交点的近似值，计算结果表明：迭代5次精确度达到8位有效数字，它的收敛速度低于newton迭代法。
数值计算方法第2章2-1节
（2）计算
f
(
a
2
b)
。
（3）若
f
(
a
2
b
)
0
，计算停止；若
f
(
a
2
b
)
f
(a)
0
，用
若
f
(
a
2
b)
f
(b)
0
，以
a
2
b
代替
a
。
a
2
b
代替
b
；
（4）反复执行第二步与第三步，直到区间长缩小到允许误差范围
之内，此时区间中点即可作为所求的近似解。
18
证明方程 x3 3x2 6x 1 0 在区间（0，1）内有唯一的实根，并
在[－1,－0.25]，[0.5，1.25]，[1.25，2]各区间内至少有一个实根。
10
2.1.3 区间二分法
定理 函数f(x)在[a,b]上单调连续，且f(a)f(b)<0， 则方程f(x)=0在区间[a,b]上有且仅有一个实根x*。
二分法的基本思想 将有根的区间二分为两个小区间，然后判断根在那 个小区间，舍去无根的小区间，而把有根的小区间 再一分为二，再判断根属于哪个更小的区间，如此 反复 ，直到求出满足精度要求的近似根。
5
有根区间
介值定理 若函数 f (x) 在[a, b] 连续，且
f (a) f (b) 0 ，则方程 f ( x) 0 在(a,b) 内至
少有一个实根。将[a, b] 称为 f (x) 的有根区间。
6
2.1.2 逐步搜索法
假设f(x)在区间[a,b]内有一
个实根x*,若 b – a较小，则可 在(a,b)上任取一点x0作为初始 近似根。
数值分析3.1.二分法、迭代法及收敛性
上述令p→∞, 及limxk+p=x* (p→∞)即得(2.6)式. 证毕. 注：误差估计式(2.5)原则上确定迭代次数，但它由 于含有信息 L 而不便于实际应用. 而误差估计式(2.6) 是实用的，只要相邻两次计算结果的偏差足够小即 可保证近似值 xk 具有足够精度.
注： 对定理1和定理2中的条件2º 可以改为导数，即 在使用时如果(x)∈C[a, b]且对任意x∈[a, b]有
显然f(x)∈C[a, b],且满足f(a)=(a)-a>0, f(b)=(b)-b<0, 由连续函数性质可知存在 x*∈(a, b) 使 f(x*)=0，即 x*=(x*)，x*即为(x)的不动点. 再证不动点的唯一性. 设x1*, x2*∈[a, b]都是(x) 的不动点，则由(2.4)得
可以如此反复迭代计算
xk+1=(xk) 到的序列{xk}有极限 (k=0,1,2,). (2.2)
(x)称为迭代函数. 如果对任何x0∈[a, b]，由(2.2)得
lim xk x .
k
则称迭代方程(2.2)收敛. 且x*=(x*)为(x)的不动点， 故称(2.2)为不动点迭代法.
例1 用二分法求方程 f(x)=x3-x-1=0在(1, 1.5)的实根, 要求误差不超过0.005.
解 由题设条件，即：
|x*-xn|≤0.005 则要
1 2
n 1
(b a)
1 2
n 1
(1.5 1)
1 2
n 2
0.005
2 由此解得 n 1 5.6,取 n=6, 按二分法计算过程见 lg 2
L2 xk 1 xk 2 Lk x1 x0 .
于是对任意正整数 p 有
数值分析迭代加速牛顿法及弦截法
以上两式相除得
xk1 xk1
C C
xk xk
C C
2 .
据此反复递推有
xk xk
C C
x0 x0
2k
C C
.
第14页/共34页
(4.6)
记
q x0 C x0 C
整理(4.6)式，得
q2k xk C 2 C 1 q2k .
对任意初值x0>0，总有|q|<1，故由上式推知，当 k→∞时xk C ，即迭代过程恒收敛.
值x0, x1△，那么当邻域△充分小时，弦截法(5.2)将 按阶
p 1 5 1.618. 2
收敛到x*. 这里p是方程λ2-λ-1=0的正根. 定理证明可见P116.
第26页/共34页
因为(5.2)式用到前两点xk-1和xk的值，故此方法又 称为双点割线法.
如果把(5.2)式中的xk-1改为x0，即迭代公式为
比较困难，为此可以利用已求函数值 f(xk),f(xk-1),来
回避导数值 f(xk)的计算. 这类方法是建立在插值原理
基础上的，下面介绍弦截法与抛物线法.
第22页/共34页
3.5.1 弦截(割线)法
设 xk, xk-1是 f(x)=0的近似根，我们利用 f(xk), f(xk-1) 构造一次插值多项式 p1(x)，并用 p1(x)=0 的根作为方程 f(x)=0 的新的近似根 xk+1，由于
x*
x
(4.2)的计算结果.
y=f(x)
xk+2xk+1xk
第9页/共34页
牛顿迭代法的收敛性
牛顿迭代法的迭代函数为
(x) x f (x)
f ( x)
设x*是 f(x) 的一个单根，即 f(x*)=0，f(x*)≠0, 有
数学方法解决非线性方程组
数学方法解决非线性方程组非线性方程组在科学、工程和数学领域中具有重要的应用价值。
解决非线性方程组是一个复杂的任务，而数学方法为我们提供了一种有效的途径。
本文将介绍一些常用的数学方法，以解决非线性方程组的问题。
1. 牛顿法牛顿法是一种常用的数值解法，用于求解非线性方程组。
它基于泰勒级数的思想，通过迭代逼近方程组的根。
具体步骤如下：首先，选择一个初始点作为近似解。
然后，根据函数的导数来计算方程组在该点的切线，找到切线与坐标轴的交点。
将该交点作为新的近似解，继续迭代，直到满足收敛条件。
牛顿法具有快速收敛的特点，但在某些情况下可能会陷入局部极小值点。
2. 雅可比迭代法雅可比迭代法也是一种常见的数值解法。
它将非线性方程组转化为线性方程组的形式，然后通过迭代来逼近解。
具体步骤如下：首先，将非线性方程组表示为矩阵形式，其中包含未知数的系数矩阵和常数向量。
然后，将方程组进行变换，使得未知数的系数矩阵变为对角矩阵。
接下来，选择一个初始解向量，并通过迭代计算新的解向量，直到满足收敛条件。
雅可比迭代法适用于大规模的非线性方程组求解，但收敛速度较慢。
3. 高斯-赛德尔迭代法高斯-赛德尔迭代法是雅可比迭代法的改进版本。
它在每次迭代中使用新的解向量来更新未知数的值，从而加快收敛速度。
具体步骤如下：首先，选择一个初始解向量。
然后，通过迭代计算新的解向量，直到满足收敛条件。
高斯-赛德尔迭代法相对于雅可比迭代法而言，可以更快地收敛到解。
它在求解非线性方程组时具有较好的效果。
4. 弦截法弦截法是一种近似求解非线性方程组的方法。
它通过线段的截断来逼近方程组的根。
具体步骤如下：首先，选择一个初始的线段，其中包含方程组的两个近似解。
然后，通过截取线段上的新点，构造新的线段。
重复这个过程，直到满足收敛条件。
弦截法是一种迭代方法，它可以在不需要计算导数的情况下逼近方程组的根。
但是，它的收敛速度比牛顿法和雅可比迭代法要慢。
总结：数学方法提供了一种有效的途径来解决非线性方程组的问题。
非线性方程的数值求法牛顿迭代法和弦截法PPT课件
26
Newton下山法
原理：若由 xk 得到的 xk+1 不能使 | f | 减小，则在 xk 和 xk+1 之 间找一个更好的点 xk1，使得 f ( xk1) f ( xk ) 。
xk
xk+1
xk1 (1 )xk , [0, 1]
xk 1
[xk
)g( xn
)
n1
n
mng(xn ) mg( xn ) n g(
xn
)
n2 g( xn )
mg( xn ) n g( xn )
n1
2 n
g( xn )
mg( xn ) n g( xn )
若 xn 收敛，即
n 0 (n ),
没有具体的描述，而且若x0 的值没有取好，有可 能得不到收敛的结果。
以下定理，给出了 f x 满足一定的条件时，要使得牛顿
迭代法收敛，x0 应满足什么条件。
又 f ( ) 0
( ) 0 1,
牛顿迭代法局部收敛于
又 ( ) 0
即有：牛顿迭代法具有二阶（平方）收敛速度。
注. 定理要求 x0 充分接近 (局部收敛)，充分的程度
没有具体的描述，而且若x0 的值没有取好，有可 能得不到收敛的结果。
以下定理，给出了 f x 满足一定的条件时，要使得牛顿
迭代法收敛，x0 应满足什么条件。
定理 设 f x 在区间 a,b 上的二阶导数存在，且满足： ① f (a) f (b) 0; （保证 a, b中至少存在一个根）
若 xn 收敛，即 n 0 (n )
lim n1 lim[1
研究生数值分析(5)牛顿(Newton)迭代法
(k 0,1, 2,)
称为埃特肯算法。
例７ 用迭代法求方程
f ( x) x 2 x 0 在[0，1]内根 x *
的近似值，精确到
xk 1 xk 104
解：取初始近似根 x0 0.5 xk 1 2 x 1.用简单迭代法 2.用牛顿迭代法 3.用埃特肯算法
1 1 0 m
这表明直接用牛顿迭代法对方程 只有线性收敛速度。
f ( x) 0
求重根
对 x* 是方程 则 x* 是方程
f ( x) 0
重根的情形，如将方程改写成
(其中 F ( x) f ( x) / f ' ( x) ）
F ( x) 0
F ( x) 0
的单根，再对
F ( x) 0
f ' ( x) 0
；
在 [a, b] 上保号，
则当初值 x0 [a, b] ，且 f ( x0 ) f '' ( x0 ) 0 时， 牛顿迭代公式产生的迭代序列 { xk } 收敛于方程
f ( x) 0 在 [a, b] 上的唯一实根 x* 。
定理５的简要几何说明：
条件（1）保证了曲线 y=f (x)的连续性和光滑性； 条件（2）保证了方程y = f (x) 在[a ,b]内至少有 一实根； 条件（3）说明在[a ,b]上恒有
135.607
使其精确至7位有效数字。 解：作函数 f ( x) x2 c ， 则f (x)=0的正根 x* 就是 c
f ( x) 0 的牛顿迭代公式为
2 f ( xk ) xk c 1 c xk 1 xk ' xk ( xk ) f ( xk ) 2 xk 2 xk
称为埃特肯算法。
例７ 用迭代法求方程
f ( x) x 2 x 0 在[0，1]内根 x *
的近似值，精确到
xk 1 xk 104
解：取初始近似根 x0 0.5 xk 1 2 x 1.用简单迭代法 2.用牛顿迭代法 3.用埃特肯算法
1 1 0 m
这表明直接用牛顿迭代法对方程 只有线性收敛速度。
f ( x) 0
求重根
对 x* 是方程 则 x* 是方程
f ( x) 0
重根的情形，如将方程改写成
(其中 F ( x) f ( x) / f ' ( x) ）
F ( x) 0
F ( x) 0
的单根，再对
F ( x) 0
f ' ( x) 0
；
在 [a, b] 上保号，
则当初值 x0 [a, b] ，且 f ( x0 ) f '' ( x0 ) 0 时， 牛顿迭代公式产生的迭代序列 { xk } 收敛于方程
f ( x) 0 在 [a, b] 上的唯一实根 x* 。
定理５的简要几何说明：
条件（1）保证了曲线 y=f (x)的连续性和光滑性； 条件（2）保证了方程y = f (x) 在[a ,b]内至少有 一实根； 条件（3）说明在[a ,b]上恒有
135.607
使其精确至7位有效数字。 解：作函数 f ( x) x2 c ， 则f (x)=0的正根 x* 就是 c
f ( x) 0 的牛顿迭代公式为
2 f ( xk ) xk c 1 c xk 1 xk ' xk ( xk ) f ( xk ) 2 xk 2 xk
数值分析-方程迭代法
实验内容1 用下列方法求方程201303==--x x x 在附近的根，要求准确到四位有效数字。
（1）牛顿法。
（2）单点弦截法（3）双点弦截法2 用Aitken 法求方程0123=--x x 在5.10=x 附近的根，精度要求为410-=ε。
三 实验步骤（算法）与结果1： 用双点弦截法求方程201303==--x x x在附近的根①算法的C 语言代码：#include<stdio.h>#include<math.h>double f(double x){ double f;f=x*x-1/x;return f;}void main(){double y=0,z=0,x;printf("please enter a number near the root: ") ;scanf("%f",&x);for (y=f(x),z=f(y);fabs(z-y)>5e-5;){x=(x*z-y*y)/(x-2*y+z) ;y=f(x);z=f(y);}printf("the root is:") ;printf("X=%-10.4f\n",z);}②实验结果：如下图，按题要求输入2，则可得结果X=1.46562：用Aitken 法求方程0123=--x x在5.10=x 附近的根①算法的C 语言代码：#include<stdio.h>#include<math.h>double f(double x){double f=pow(x,3)-3*x-1;return f;}void main(){double f1,f2,x=2.0,y=1.5,z;for(;fabs(y-x)>5e-5;){f1=f(x);f2=f(y);z=y-f2*(y-x)/(f2-f1);x=y;y=z;}printf("the root is:") ;printf("X=%-10.4f\n",y);}②实验结果：如下图，在程序代码中预先设置接近于根的两个值x1=2.0与x2=1.5作为初值，则可得结果X=1.8794.。
弦 截 法
两个初始近似根 x0 , x1 ，这种方法称为多点迭
代法。
例2.12 用弦截法求方程 x ex在x0 0.5 初始
值邻近的一个根。要求 xk1 xk 0.0001 解：取 x0 0.5 , x1 0.6, 令 f (x) x ex
利用弦截迭代公) (exk
1.2 弦截法几何意义
弦截法也称割线法,其几何意义是用过曲线上两
点 P0 (x0 , f (x0 )) 、P1(x1, f (x1)) 的割线来代替曲线,用割 线与x轴交点的横座标作为方程的近似根 x2再过
P1点和点 P2 (x2 , f (x2 )) 作割线求出 x3 ,再 过P2点和点 P3 (x3, f (x3 )) 作割线求出 x4 ,余 此类推，当收敛时
可求出满足精度要
x0 x2 x3 x*
P1 y=f(x)
x1
求的 xk
P3 P0 P2
可以证明，弦截法具有超线性收敛，收敛
的阶约为1.618，它与前面介绍的一般迭代法
一样都是线性化方法，但也有区别。即一般迭
代法在计算 xk1 时只用到前一步的值 xk ，故称 之为单点迭代法；而弦截法在求 xk1 时要用到前 两步的结果 xk1 和 xk ，使用这种方法必须给出
e ) xk1
(xk
xk 1 )
计算结果见P34列表，
易见取近似根 x4 0.56714
则可满足精度要求。
1.3
弦 截 法 算 法 实 现
k+1 k
x1 x0 x2 x1 f(x1)f(x0) f(x2) f(x1)
y
输 入 x0, x1,,ε,N
1k
y
f (x0 ) 0?
x0 x2
n y
代法。
例2.12 用弦截法求方程 x ex在x0 0.5 初始
值邻近的一个根。要求 xk1 xk 0.0001 解：取 x0 0.5 , x1 0.6, 令 f (x) x ex
利用弦截迭代公) (exk
1.2 弦截法几何意义
弦截法也称割线法,其几何意义是用过曲线上两
点 P0 (x0 , f (x0 )) 、P1(x1, f (x1)) 的割线来代替曲线,用割 线与x轴交点的横座标作为方程的近似根 x2再过
P1点和点 P2 (x2 , f (x2 )) 作割线求出 x3 ,再 过P2点和点 P3 (x3, f (x3 )) 作割线求出 x4 ,余 此类推，当收敛时
可求出满足精度要
x0 x2 x3 x*
P1 y=f(x)
x1
求的 xk
P3 P0 P2
可以证明，弦截法具有超线性收敛，收敛
的阶约为1.618，它与前面介绍的一般迭代法
一样都是线性化方法，但也有区别。即一般迭
代法在计算 xk1 时只用到前一步的值 xk ，故称 之为单点迭代法；而弦截法在求 xk1 时要用到前 两步的结果 xk1 和 xk ，使用这种方法必须给出
e ) xk1
(xk
xk 1 )
计算结果见P34列表，
易见取近似根 x4 0.56714
则可满足精度要求。
1.3
弦 截 法 算 法 实 现
k+1 k
x1 x0 x2 x1 f(x1)f(x0) f(x2) f(x1)
y
输 入 x0, x1,,ε,N
1k
y
f (x0 ) 0?
x0 x2
n y
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
设 x0 是根 x*的某个近似值, 用迭代公式校正一次得
x1=(x0)
而由微分中值定理，有
x1 x ( x0 ) ( x ) ( )( x0 x ), 在x与x0之间.
假设 (x) 改变不大, 近似地取某个近似值 L, 则有
x1 x L( x0 x ).
(3.1)
若将校正值 x1=(x0) 再校正一次，又得
导数连续，则埃特金法为 2p–1 阶收敛.
3.3.2 斯蒂芬森(Steffensen)迭代法
埃特金方法不管原序列{xk}是怎样产生的，对{xk} 进行加速计算，得到序列{ ̄xk }. 如果把埃特金加速技 巧与不定点迭代结合，则可得到如下的迭代法：
yk ( xk ), zk ( yk ),
xk1
牛顿法的几何意义：设xk是根x*的某个近似值， 过曲线y=f(x)上横坐标为xk的点Pk引切线，并将该切 线与x轴交点的横坐标xk+1作为x*的新的近似值. 注意 到切线方程为
y f ( xk ) f ( xk )( x xk ).
y
Pk
这样求得的值xk+1必满足
Pk+1
(4.1), 从而就是牛顿公式
注：埃特金(Aitken)加速迭代法也可写成下面格式
x(1) k 1
(
xk
)
x(2) k1
(
x(1) k 1
)
xk1
x(2) k 1
(
x(2) k 1
x(1) k 1
)2
x(2) k 1
2 Aitken ) 外推法. 可以证明:
若 xk1 ( xk ) 为线性收敛,则埃特金法为平方收敛； 若 xk1 ( xk ) 为 p ( p > 1)阶收敛， ( x) 的 p 阶
.
(( x)) 2( x) x
(3.4) (3.5)
对不动点迭代(3.5)有以下局部收敛性定理.
定理5 若x*为(3.5)定义的迭代函数Ψ(x)的不动
点，则x*为(x)的不定点. 反之，若x*为(x)的不动 点，设(x)在 x* 连续 ，(x*)≠1，则x*是Ψ(x)的不动
点，且斯蒂芬森迭代法(3.3)是2阶收敛的.
x*
x
(4.2)的计算结果.
y=f(x)
xk+2xk+1 xk
牛顿迭代法的收敛性
牛顿迭代法的迭代函数为
(x) x f (x)
f ( x)
设x*是 f(x) 的一个单根，即 f(x*)=0，f(x*)≠0, 有
( x )
f
( [
x ) f ( x f ( x* )]2
)
0,
( x )
f f
( x ) ( x )
xk
( yk xk )2 zk 2 yk xk
(k 0,1,).
称为斯蒂芬森(Steffensen)迭代法.
(3.3)
实际上(3.3)是将不定点迭代法(2.2)计算两步合并
成一步得到的，可将它写成另一种不动点迭代
其中
xk1 ( xk ) (k 0,1,),
(x) x
[( x) x]2
第3章 非线性方程的数值解法
• 3.1 方程求根与二分法 • 3.2 迭代法及其收敛性 • 3.3 迭代收敛的加速方法 • 3.4 牛顿法 • 3.5 弦截法与抛物线法
3.3 迭代收敛的加速方法
3.3.1 埃特金加速收敛方法
对于收敛的迭代过程，只要迭代足够多次，就可 以使结果达到任意的精度，但是有时迭代过程收敛较 慢，从而使计算量变得很大.
f ( x) x2 C, ( x) x f ( x) 1 x C .
f ( x) 2 x
xk1
1 2
xk
C xk
.
(4.5)
我们现在证明，这种迭代公式对于任意初值x0>0 都是收敛的.
0.
由定理4可得
lim
k
|
xk1 x (xk x)2
|
lim |
k
1 2!
(
)(
xk
x)2
(xk x)2
|
1 | (x) ||
2!
f (x) 2 f (x)
|
0.
定理(局部收敛性) 设fC2[a, b], 若x*为 f(x)在[a,
b]上的根，且 f(x*)0，则存在 x* 的邻域 U, 使得任取
似,记作 ̄x1，一般情形是由xk计算 xk+1, xk+2，记
xk1
xk
( xk1 xk )2 xk2 2xk1 xk
xk
(xk )2 2 xk
(k 0,1,).
(3.1)式称为埃特金(Aitken) △2加速方法.
(3.2)
可以证明
lim
k
xk1 x xk x
0.
它表明序列{̄xk}的收敛速度比{xk}的收敛速度快.
f(x)=x–e–x， f(x)=1+e–x，
牛顿迭代公式为
xk 1
xk
xk exk 1 exk
取 x0=0.5，迭代得
x1=0.566311, x2=0.5671431, x3=0.5671433.
例2 对于给定的正数 C，应用牛顿法解二次方程
x2 C 0, 推导出求开方值 C 的计算公式.
3.4 牛 顿 法
3.4.1 牛顿法及其收敛性
牛顿法实质上是一种线性化方法，其基本思想是 将非线性方程 f(x)=0 逐步归结为某种线性方程来求 解.
设已知方程f(x)=0有近似根x0，且在 x0附近f(x)可 用一阶泰勒多项式近似，表示为
f ( x) f ( x0 ) f ( x0 )( x x0 )
初值 x0U，牛顿法产生的序列 {xk} 收敛到 x*，且满 足
lim
k
|
xk1 x (xk x)2
||
f (x) 2 f (x)
|.
由此得到，当x*为单根时，牛顿迭代法在根x*的 邻近是二阶(平方)收敛的.
例1 用牛顿迭代法求方程x=e–x在x=0.5附近的根.
解 将原方程化为 x–e–x= 0，则
x2=(x1)
由于
x2-x*≈L(x1-x*).
将它与(3.1)式联立，消去未知的L，有
由此推知
x1 x x2 x
x0 x x1 x
x
x0 x2 x12 x2 2x1 x0
x0
( x1 x0 )2 x2 2x1 x0
.
在计算了 x1 及 x2 之后，可用上式右端作为 x* 的新近
当 f(x0)≠0 时，方程 f(x)=0 可用线性方程(切线) 近似
代替，即
f(x0)+f(x0)(x-x0)=0.
(4.1)
解此线性方程得 得迭代公式
x
x0
f ( x0 ) f ( x0 )
xk1 xk
f (xk ) f ( xk )
(k 0,1,),
(4.2)
此式称为牛顿(Newton)迭代公式.
x1=(x0)
而由微分中值定理，有
x1 x ( x0 ) ( x ) ( )( x0 x ), 在x与x0之间.
假设 (x) 改变不大, 近似地取某个近似值 L, 则有
x1 x L( x0 x ).
(3.1)
若将校正值 x1=(x0) 再校正一次，又得
导数连续，则埃特金法为 2p–1 阶收敛.
3.3.2 斯蒂芬森(Steffensen)迭代法
埃特金方法不管原序列{xk}是怎样产生的，对{xk} 进行加速计算，得到序列{ ̄xk }. 如果把埃特金加速技 巧与不定点迭代结合，则可得到如下的迭代法：
yk ( xk ), zk ( yk ),
xk1
牛顿法的几何意义：设xk是根x*的某个近似值， 过曲线y=f(x)上横坐标为xk的点Pk引切线，并将该切 线与x轴交点的横坐标xk+1作为x*的新的近似值. 注意 到切线方程为
y f ( xk ) f ( xk )( x xk ).
y
Pk
这样求得的值xk+1必满足
Pk+1
(4.1), 从而就是牛顿公式
注：埃特金(Aitken)加速迭代法也可写成下面格式
x(1) k 1
(
xk
)
x(2) k1
(
x(1) k 1
)
xk1
x(2) k 1
(
x(2) k 1
x(1) k 1
)2
x(2) k 1
2 Aitken ) 外推法. 可以证明:
若 xk1 ( xk ) 为线性收敛,则埃特金法为平方收敛； 若 xk1 ( xk ) 为 p ( p > 1)阶收敛， ( x) 的 p 阶
.
(( x)) 2( x) x
(3.4) (3.5)
对不动点迭代(3.5)有以下局部收敛性定理.
定理5 若x*为(3.5)定义的迭代函数Ψ(x)的不动
点，则x*为(x)的不定点. 反之，若x*为(x)的不动 点，设(x)在 x* 连续 ，(x*)≠1，则x*是Ψ(x)的不动
点，且斯蒂芬森迭代法(3.3)是2阶收敛的.
x*
x
(4.2)的计算结果.
y=f(x)
xk+2xk+1 xk
牛顿迭代法的收敛性
牛顿迭代法的迭代函数为
(x) x f (x)
f ( x)
设x*是 f(x) 的一个单根，即 f(x*)=0，f(x*)≠0, 有
( x )
f
( [
x ) f ( x f ( x* )]2
)
0,
( x )
f f
( x ) ( x )
xk
( yk xk )2 zk 2 yk xk
(k 0,1,).
称为斯蒂芬森(Steffensen)迭代法.
(3.3)
实际上(3.3)是将不定点迭代法(2.2)计算两步合并
成一步得到的，可将它写成另一种不动点迭代
其中
xk1 ( xk ) (k 0,1,),
(x) x
[( x) x]2
第3章 非线性方程的数值解法
• 3.1 方程求根与二分法 • 3.2 迭代法及其收敛性 • 3.3 迭代收敛的加速方法 • 3.4 牛顿法 • 3.5 弦截法与抛物线法
3.3 迭代收敛的加速方法
3.3.1 埃特金加速收敛方法
对于收敛的迭代过程，只要迭代足够多次，就可 以使结果达到任意的精度，但是有时迭代过程收敛较 慢，从而使计算量变得很大.
f ( x) x2 C, ( x) x f ( x) 1 x C .
f ( x) 2 x
xk1
1 2
xk
C xk
.
(4.5)
我们现在证明，这种迭代公式对于任意初值x0>0 都是收敛的.
0.
由定理4可得
lim
k
|
xk1 x (xk x)2
|
lim |
k
1 2!
(
)(
xk
x)2
(xk x)2
|
1 | (x) ||
2!
f (x) 2 f (x)
|
0.
定理(局部收敛性) 设fC2[a, b], 若x*为 f(x)在[a,
b]上的根，且 f(x*)0，则存在 x* 的邻域 U, 使得任取
似,记作 ̄x1，一般情形是由xk计算 xk+1, xk+2，记
xk1
xk
( xk1 xk )2 xk2 2xk1 xk
xk
(xk )2 2 xk
(k 0,1,).
(3.1)式称为埃特金(Aitken) △2加速方法.
(3.2)
可以证明
lim
k
xk1 x xk x
0.
它表明序列{̄xk}的收敛速度比{xk}的收敛速度快.
f(x)=x–e–x， f(x)=1+e–x，
牛顿迭代公式为
xk 1
xk
xk exk 1 exk
取 x0=0.5，迭代得
x1=0.566311, x2=0.5671431, x3=0.5671433.
例2 对于给定的正数 C，应用牛顿法解二次方程
x2 C 0, 推导出求开方值 C 的计算公式.
3.4 牛 顿 法
3.4.1 牛顿法及其收敛性
牛顿法实质上是一种线性化方法，其基本思想是 将非线性方程 f(x)=0 逐步归结为某种线性方程来求 解.
设已知方程f(x)=0有近似根x0，且在 x0附近f(x)可 用一阶泰勒多项式近似，表示为
f ( x) f ( x0 ) f ( x0 )( x x0 )
初值 x0U，牛顿法产生的序列 {xk} 收敛到 x*，且满 足
lim
k
|
xk1 x (xk x)2
||
f (x) 2 f (x)
|.
由此得到，当x*为单根时，牛顿迭代法在根x*的 邻近是二阶(平方)收敛的.
例1 用牛顿迭代法求方程x=e–x在x=0.5附近的根.
解 将原方程化为 x–e–x= 0，则
x2=(x1)
由于
x2-x*≈L(x1-x*).
将它与(3.1)式联立，消去未知的L，有
由此推知
x1 x x2 x
x0 x x1 x
x
x0 x2 x12 x2 2x1 x0
x0
( x1 x0 )2 x2 2x1 x0
.
在计算了 x1 及 x2 之后，可用上式右端作为 x* 的新近
当 f(x0)≠0 时，方程 f(x)=0 可用线性方程(切线) 近似
代替，即
f(x0)+f(x0)(x-x0)=0.
(4.1)
解此线性方程得 得迭代公式
x
x0
f ( x0 ) f ( x0 )
xk1 xk
f (xk ) f ( xk )
(k 0,1,),
(4.2)
此式称为牛顿(Newton)迭代公式.