数值分析迭代加速牛顿法及弦截法
- 格式：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
牛顿-拉夫森(Newton-Raphson)迭代法
§3.4 牛顿迭代法牛顿迭代法也称为牛顿-拉夫森(Newton-Raphson)迭代法，它是数值分析中最重要的方法之一，它不仅适用于方程或方程组的求解，还常用于微分方程和积分方程求解。
3.4.1 牛顿迭代法用迭代法解非线性方程时，如何构造迭代函数是非常重要的，那么怎样构造的迭代函数才能保证迭代法收敛呢？牛顿迭代法就是常用的方法之一，其迭代格式的来源大概有以下几种方式：1设],[)(2b a C x f ∈，对)(x f 在点],[0b a x ∈作泰勒展开： !2))((''))((')()(20000x x f x x x f x f x f -+-+=ξ略去二次项，得到)(x f 的线性近似式：))((')()(000x x x f x f x f -+≈。
由此得到方程=)(x f 0的近似根(假定≠)('0x f 0)，)(')(000x f x f x x -=即可构造出迭代格式(假定≠)('k x f 0)：)(')(1k k k k x f x f x x -=+ 公式(3.4.1)这就是牛顿迭代公式，若得到的序列{k x }收敛于α，则α就是非线性方程的根。
2 牛顿迭代法也称为牛顿切线法，这是由于)(x f 的线性化近似函数)(x l ＝))((')(000x x x f x f -+是曲线y ＝)(x f 过点))(,(00x f x 的切线而得名的，求)(x f 的零点代之以求)(x l 的零点，即切线)(x l 与x 轴交点的横坐标，如右图所示，这就是牛顿切线法的几何解释。
实际上，牛顿迭代法也可以从几何意义上推出。
利用牛顿迭代公式，由k x 得到1+k x ，从几何图形上看，就是过点))(,(k k x f x 作函数)(x f 的切线k l ，切线k l 与x 轴的交点就是1+k x ，所以有1)()('+-=k k k k x x x f x f ，整理后也能得出牛顿迭代公式： )(')(1k k k k x f x f x x -=+。
数值分析中的牛顿迭代法
数值分析中的牛顿迭代法在现代科学技术领域中，数值计算是一项不可忽视的内容。
牛顿迭代法是数值计算中的一种重要方法，被广泛应用于数学、物理、化学、航空航天等领域。
下面就让我们来了解一下什么是牛顿迭代法，以及它的原理、特点和应用。
1. 概述牛顿迭代法又称为牛顿-拉夫逊迭代法，是一种求解非线性方程组的数值计算方法。
它的基本思想是：从已知函数的一个近似解出发，借助函数的切线逼近函数的零点，直到达到指定的精度要求为止。
牛顿迭代法的应用非常广泛，如求解函数的根、优化问题、最小二乘拟合、时间依赖问题等。
2. 原理假设$f(x)$是一个在$x0$处有连续二阶导数的函数。
如果要找到它在$x0$处的零点，那么牛顿迭代法的基本公式为：$$ x_{n+1} = x_n -\frac{f(x_n)}{f'(x_n)} $$其中，$n$表示迭代的次数，$x_{n+1}$表示迭代后的值，$x_n$表示当前的值，$f(x_n)$表示函数在$x_n$点的值，$f'(x_n)$表示函数在$x_n$点的导数。
公式的物理意义是：先用当前的$x$值求出函数值$f(x)$，然后用当前的$x$值求出函数的导数$f'(x)$，接着用$f(x)$和$f'(x)$计算出一个斜率，最后用当前的$x$值减去这个斜率，得到一个新的近似解$x_{n+1}$。
迭代过程如下：（1）选取初始值$x_0$；（2）计算出第一个近似值$x_1$，即$x_1=x_0-\frac{f(x_0)}{f'(x_0)}$；（3）计算出第二个近似值$x_2$，即$x_2=x_1-\frac{f(x_1)}{f'(x_1)}$；（4）依此类推，直到$f(x_n)$的值小到满足预设的精度为止。
3. 特点牛顿迭代法具有以下几个特点：（1）收敛速度快。
迭代公式是二阶收敛的，收敛速度远远超出了线性迭代法和高斯-赛德尔迭代法。
（2）精度高。
根据牛顿迭代法的收敛次数和精度估计定理，只要初值足够接近所求的跟，牛顿迭代法就能收敛，并且有二阶精度。
数值分析3-牛顿迭代法
§3 牛顿迭代法Newton Iteration————切线法牛顿迭代法是最著名的方程求根方法。
已经通过各种方式把它推广到解其他更为困难的非线性问题。
【例如】非线性方程组、非线性积分方程和非线性微分方程。
虽然牛顿法对于给定的问题不一定总是最好的方法，但它的简单形式和快的收敛速度常常使得解非线性问题的人优先考虑它。
迭代一般理论告诉我们，构造好的迭代函数可使收敛速度提高。
然而迭代函数的构造方法又各不相同，方法多样。
牛顿法是受几何直观启发，给出构造迭代函数的一条重要途径。
牛顿迭代的基本思想:方程f(x)=0的根，几何意义是曲线y=f(x)与ox轴y=0的交点。
求曲线与y=0的交点没有普遍的公式，但直接与0x 轴的交点容易计算。
用直线近似曲线y=f(x)，从而用直线方程的根逐步代替f(x)=0的根。
即把非线性方程逐步线性化。
方法：设x k是f(x)=0的一个近似根，把f(x)在x k处作一阶Taylor 展开，得到))(()()(k k k x x x f x f x f -'+≈ （19）设)(k x f '≠0，由于0)())(()(=≈-'+x f x x x f x f k k k所以求得解记为1+k x ，有牛顿迭代公式：（20） 按牛顿迭代计算称为牛顿迭代法。
牛顿法的几何意义：选初值x k 以后，过))(,(k k x f x p 点，作曲线y=f(x)的切线，其切线方程为))(()()(k k k x x x f x f x f -'+= (21)切线与ox 轴的交点，为1+k x ，则)(/)(1k k k k x f x f x x '-=+（22）牛顿迭代法也称为切线法。
迭代法的收敛性：如果取)(/)()(k k x f x f x x g '-=，则有x=g(x)，从而牛顿迭代公式就是)(1k k x g x =+因此就可以由考察g(x)的性质，来讨论迭代法的收敛性及收敛速度。
数值分析E
牛顿迭代公式的收敛速度
从xk+1= xk-f(xk)/f '(xk)得牛顿法的迭代函数为 f(x) ϕ(x)=xf ′(x) 经计算有 f(x*)f ′′(x*)
ϕ′(x*)=
{f ′(x*)}
2
结论 当x*是f(x)的单根, 即 f(x*)=0, f'(x*) 0,有 ϕ'(x*)=0<1, 因此 (1) 牛顿公式具有局部收敛性, (2) 对单根是二阶收敛的 注 对于重根, 牛顿公式的收敛速度会减低.
p的大小是衡量迭代公式优劣的标准
定理 设ϕ(x)在x=ϕ(x)根x*邻近有p阶连续导数,且 (p)(x*) (p-1) ϕ 0, ϕ'(x*)=ϕ''(x*)=…=ϕ (x*)=0, 则迭代公式xk+1=ϕ(xk)具有p阶收敛速度 证明 首先计算ek+1=xk+1-x*=ϕ(xk)-ϕ(x*) 将ϕ(xk)在x*处泰勒展开 等于0 * ϕ(xk)=ϕ(x )+ϕ'(x*)(xk-x)+... +ϕ(p-1)(x*)(xk-x*)p-1/(p-1)!+ϕ(p)(ξ) (xk-x*)p/p! =ϕ(x*)+ϕ(p)(ξ) (xk-x*)p/p! : 其中ξ介于xk,x*之间 令k
迭代过程的收敛速度
Lk|x1-x0|/(1-L)知, L越小,收敛速度越快 但L的计算不容易 用误差减小的幅度表示收敛速度的快慢 定义 假设xk+1=ϕ(xk)收敛到x*, 记误差ek=x*-xk,若 由 |xk-x*|
e k+1 lim p =c ≠ 0 k →∞ e k
称该公式具有p阶收敛速度 特别地, p=1 称为线性收敛 p=2 称为平方收敛 p 注 按极限定义, 当k较大时, 有 e k+1 ≈ ce k 当|ek|<1时, p越大,ek+1减小越快, 即敛速越快
牛顿-拉夫森(Newton-Raphson)迭代法
xn 1 xn f ( xn ) L
记 L 1 ，上面两式可以合并写成：
f ( x) L 。 这种迭代公式称作简单的牛顿公式，其相应的迭代函数是： 需要注意的是，由于 L 是 ' ( x) 的估计值，若取 ( x) x f ( x) ，则 ' ( x) 实际上便是
f ' ( x) 2 L ，可见当 L 与 f ' ( x) 同号且满足上述不等式时，推广的简化
法就有平方收敛的速度，为了扬长避短，扩大初始值选取的范围，下面介绍牛顿法的一种改进 ——牛顿下山法。
xn 1 xn
将牛顿法的迭代公式修改为： 其中， 是一个参数， 的选取应使
f ( xn ) f ' ( xn )
xn 1 xn
计算平方根的准确而有效的计算方法。 3.4.3 牛顿迭代法的变形 用牛顿法解方程，虽然在单根附近具有较快的收敛速度，但它有个明显的缺点，就是每次 都要计算导数 f ' ( x) ，当 f ( x) 比较复杂时，计算 f ' ( x) 可能很困难。下面介绍两种克服这种 困难的方法，另外还介绍一种扩大牛顿迭代法初值选择范围的方法，它们统称为变形的牛顿迭 代法。 1 简化牛顿法
f ( xn ) f ' ( xn ) 。
( x) x
牛顿迭代公式可以看成是由 不动点迭代的收敛原则，只须证明在根 附近的迭代函数是一个压缩映象。由于：
f ( x) f ' ( x) 而获得的不动点迭代格式。这样就可以应用
' ( x) 1
[ f ' ( x)]2 f ( x) f "( x) f ( x) f "( x) [ f ' ( x)]2 [ f ' ( x)]2 ，
记 L 1 ，上面两式可以合并写成：
f ( x) L 。 这种迭代公式称作简单的牛顿公式，其相应的迭代函数是： 需要注意的是，由于 L 是 ' ( x) 的估计值，若取 ( x) x f ( x) ，则 ' ( x) 实际上便是
f ' ( x) 2 L ，可见当 L 与 f ' ( x) 同号且满足上述不等式时，推广的简化
法就有平方收敛的速度，为了扬长避短，扩大初始值选取的范围，下面介绍牛顿法的一种改进 ——牛顿下山法。
xn 1 xn
将牛顿法的迭代公式修改为： 其中， 是一个参数， 的选取应使
f ( xn ) f ' ( xn )
xn 1 xn
计算平方根的准确而有效的计算方法。 3.4.3 牛顿迭代法的变形 用牛顿法解方程，虽然在单根附近具有较快的收敛速度，但它有个明显的缺点，就是每次 都要计算导数 f ' ( x) ，当 f ( x) 比较复杂时，计算 f ' ( x) 可能很困难。下面介绍两种克服这种 困难的方法，另外还介绍一种扩大牛顿迭代法初值选择范围的方法，它们统称为变形的牛顿迭 代法。 1 简化牛顿法
f ( xn ) f ' ( xn ) 。
( x) x
牛顿迭代公式可以看成是由 不动点迭代的收敛原则，只须证明在根 附近的迭代函数是一个压缩映象。由于：
f ( x) f ' ( x) 而获得的不动点迭代格式。这样就可以应用
' ( x) 1
[ f ' ( x)]2 f ( x) f "( x) f ( x) f "( x) [ f ' ( x)]2 [ f ' ( x)]2 ，
牛顿下山法、弦截法、解非线性方程组的牛顿法 - 牛顿法、简化牛顿法
为此，将牛顿法的计算结果
xk +1
xk
-
f ( xk ) f ﾢ( xk )
与前一步的近似值 xk 适当加权平均作为新的改进值，
xk+1 l xk+1 + (1- l)xk ， 其中 l(0 < l ﾢ1) 称为下山因子。
xk +1
xk
-l
f (xk ) f '(xk )
(k 0,1, 2...)
解：设 f (x) x2 - a ，求 a 即计算 f (x) 0 的根。
则由牛顿迭代公式可得：
xk +1
xk
-
f (xk ) f ﾢ(xk )
xk
-
xk2 - a 2xk
1 2
� � �xk
+
a xk
� � �.
令初始值 x0 3 ，得
x1
1 2
� � �3 +
7 3
� � �
2.667,
xk +1
xk
-
f (xk ) f ﾢ(x0 )
（牛顿法） 2. 牛顿重根法
（简化牛顿法）
如果 x0 为 f (x) 的 k 重根，牛顿迭代公式修改为：
(k 0,1,L)
【注】若三种方法 都收敛，则一般 重根法收敛最快， 牛顿法次之，简 化迭代法最慢。
xk +1 xk
-k
f (xk ) f '(xk )
以方程
f (x) ﾢ f (x0 ) + f ﾢ(x0 )(x - x0 )
f (x0 ) + f ﾢ(x0 )(x - x0 ) 0
近似方程（7-1），其解
x1
xk +1
xk
-
f ( xk ) f ﾢ( xk )
与前一步的近似值 xk 适当加权平均作为新的改进值，
xk+1 l xk+1 + (1- l)xk ， 其中 l(0 < l ﾢ1) 称为下山因子。
xk +1
xk
-l
f (xk ) f '(xk )
(k 0,1, 2...)
解：设 f (x) x2 - a ，求 a 即计算 f (x) 0 的根。
则由牛顿迭代公式可得：
xk +1
xk
-
f (xk ) f ﾢ(xk )
xk
-
xk2 - a 2xk
1 2
� � �xk
+
a xk
� � �.
令初始值 x0 3 ，得
x1
1 2
� � �3 +
7 3
� � �
2.667,
xk +1
xk
-
f (xk ) f ﾢ(x0 )
（牛顿法） 2. 牛顿重根法
（简化牛顿法）
如果 x0 为 f (x) 的 k 重根，牛顿迭代公式修改为：
(k 0,1,L)
【注】若三种方法 都收敛，则一般 重根法收敛最快， 牛顿法次之，简 化迭代法最慢。
xk +1 xk
-k
f (xk ) f '(xk )
以方程
f (x) ﾢ f (x0 ) + f ﾢ(x0 )(x - x0 )
f (x0 ) + f ﾢ(x0 )(x - x0 ) 0
近似方程（7-1），其解
x1
数值分析期末复习知识点
第一章（有效数字位数）1、经四舍五入取近似值，其绝对误差限不超过末尾数字的半个单位。
2、设X*为准确值，X为近似值，称e=X*-X为近似值X的绝对误差，简称误差（显然e可正可负，准确值X*未知，因此e的准确值无法求出）3、|e|=|X-X*|≤ŋ，则称ŋ为近似值X的绝对误差限，简称误差限。
4、e r=e/X*称为相对误差，由于准确值X*总是未知的，所以也把e r*=e/X称为近似值X的相对误差5、|e r*|=|e/X|≤ŋ*，则称ŋ*为近似值X的相对误差限6、设X是X*的近似值，如果|X*-X|≤1/2×10-k,则称用X近似值表示X*时准确到小数点后第k位，并称从小数点后第k位起，直到最左边的非零数字之间的所有数字为有效数字，称有效数字的位数为有效数位。
7、设X是X*的近似值，X=±10m×0.a1a2…,其中a i（i=2，3…）是0到9之间的自然数，a1≠0，m为整数，如果|X*-X|≤1/2×10m-n，那么称近似值有n位有效数字。
8、四舍五入所得到的数均为有效数字，但并不是说非四舍五入所得到的数不能为有效数字。
第二章、非线性方程求根（不动点迭代、牛顿法、弦截法、快速弦截法、局部收敛、全局收敛、收敛阶）1、不动点迭代法（迭代法）（单根区间求解方法）：将非线性方程f（x）=0化为一个同解方程x=ø（x），若要求f（x*）=0，则x*=ø（x*），称x*为f（x）的零点，为ø（x）的一个不动点。
2、定理：设迭代函数ø（x）在【a，b】上连续，且满足（1）当x∈【a，b】时，a≤ø（x）≤b，（2）存在一正数L，满足0<L<1,且∀x∈【a，b】,有|ø/（x）|≤L<1。
则1、方程x=ø（x）在【a，b】内有唯一解x*。
2、对于任意初值x0∈【a，b】,迭代法x k+1=ø（x k）均收敛x*3、设ø（x）有不动点x*，如果存在x*的一个邻域 S:|X*-X|< ŋ,对任意初值x0∈S,迭代过程x k+1=ø（x k）均收敛，则称迭代过程在根x*邻近局部收敛。
- 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)迭代公式.