数值分析3 牛顿迭代法
- 格式：doc
- 大小：93.00 KB
- 文档页数：5
§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)的性质，来讨论迭代法的收敛性及收敛速度。
迭代过程的收敛速度是指迭代过程中误差的下降速度。
设迭代过程)(1k k x g x =+收敛于方程x=g(x)的根x*，
如果迭代误差*x x e k k -=，当k →∞时成立
)0(/1的常数≠→+c c e e p k k （24） 则称该迭代过程是p 阶收敛的。
特别p=1时称为线性收敛，p>1时称超线性收敛，p=2时称为平方收敛。
若f(x)在根附近存在连续的二阶导数，x*是f(x)的单根，且初始值x 0充分接近x*，则牛顿迭代过程收敛，而且有
2
1)(2/)(****+-⋅'''≈-x x x f x f x x k k （25）
证明 1)对于f(x)，取)(/)()(x f x f x x g '-=，则牛顿迭代过程为)(1k k x g x =+，注意到
3
22
2)(/)()(2)(/)()()()()(;)](/[)()()(x f x f x f x f x f x f x f x f x g x f x f x f x g '''-''''+'''='''''='由于x*是f(x)=0的单根，即)(*x f =0,0)(≠'*
x f ，所以有 0)(/)()(,0)(≠'''=''='****x f x f x g x g (26)
由定理2知，迭代过程是局部收敛的。
2)将g(x)在x*处进行泰勒展开并代入k x x =，有
2
2
*)*)]((/*)([2
1*)(*)(!
2*)(*)*)((*)()(x x x f x f x g x x x g x x x g x g x g k k k k -'''⋅+=-''+-'+≈
注意到)(1k k x g x =+，x*=g(x*)，得到 21)())(2/)((****+-⋅''≈-x x x f x f x x k k
因此有
2
1)(2/)(****+-⋅'''≈-x x x f x f x x k k
【说明】)0*)(2/*)((/21≠'''=→+x f x f c c e e k k ，即牛顿迭代过程在x*附近具有平方收敛速度。
牛顿迭代法的优点:快速收敛性,算法简单、容易实现
缺点：初值0x 必须选在x*附近，否则，可能不收敛
01=-x xe
解 牛顿迭代公式为
k
x k k k x e x x x k +--=-+11 取初值5.00=x ，迭代计算，得到
5671432
.0,5671432.0,5671555.0,5710204.04321====x x x x 【注】牛顿法的收敛速度非常快
附：牛顿法的算法函数程序：(存至work 目录中) function y=newton(x0)
x1=x0-f1(x0);
n=1;
while(norm(x1-x0)>=1.0e-6)&(n<=1000) x0=x1;
x1=x0-f1(x0);n=n+1;
end
vpa(x1,7),n %输出n,方程的近似解
function y=f1(x)
y=(x-exp(-x))/(1+x);
end
newton(0.5)
观察初值的选取对解的影响
首先选取初值：(转到指令窗)
x=-10:0.01:10;y=x.^3-x-1;plot(x,y,'r',x,0*x)
解 牛顿迭代公式为
1
31231----=+k k k k k x x x x x function y=f1(x)
y=(x^3-x-1)/(3*x^2-1); end
分别取初值6.00=x 和1.3,比较所用迭代次数. newton(0.6)
newton(1.3)。
