2013-2014（1）专业课程实践论文
题目：方程的牛顿法
一、算法理论
1．牛顿迭代法原理
设已知方程f (x ) =0的近似根x 0, 则在x 0附近f (x ) 可用一阶泰勒多项式p (x ) =f (x 0) +f ' (x 0)(x -x 0) 近似代替。因此, 方程f (x ) =0可近似地表示为
p (x ) =0。用x 1表示p (x ) =0的根, 它与f (x ) =0的根差异不大。
设f ' (x 0) ≠0, 由于x 1满足f (x 0) +f ' (x 0)(x 1-x 0) =0, 解得
x 1=x 0-
f (x 0)
f ' (x 0)
重复这一过程, 得到迭代格式
x n +1=x n -
f (x n )
f ' (x n )
这就是著名的牛顿迭代公式, 它相应的不动点方程为
g (x ) =x -
f (x )
f ' (x )
2. 牛顿迭代法的几何解析
在x 0处作曲线的切线，切线方程为y =f (x 0) +f ' (x 0)(x -x 0) 。令y =0，可得切线与x 轴的交点坐标x 1=x 0-牛顿法又称“切线法”。
3．牛顿迭代法的收敛性
定义 设迭代过程x k +1=ϕ(x k ) 收敛于方程x =ϕ(x ) 的根x *，如果迭代误差
f (x 0)
，这就是牛顿法的迭代公式。因此，f ' (x 0)
εk =x k -x *当k →∞时成立下列关系式
εk +1
→C (C ≠0为常数) ， p εk
则迭代过程是p 阶收敛的。特别的，p =1时称为线性收敛，p >1时称为超线性收敛，p =2时称为平方收敛
定理1 对于迭代过程x k +1=ϕ(x k ) ，如果ϕ(p ) (x ) 在所求根x *的临近连续，并且 则该迭代过程在点 邻近是 阶收敛的。
ϕ'(x *) =ϕ''(x *) = =ϕ(p -1) (x *) =0, ϕ(p ) (x *) ≠0
定理2 如果x *是方程f (x ) 的一个单根，并且f (x ) 在x *及其附近具有连续的二阶导数，则只要初始近似根x 0充分靠近x *，牛顿法在根x *的临近平法收敛。 定理3 设函数f (x ) 在[a , b ]上存在二阶连续导数，且满足条件： （1）f (a ) f (b )
（2）当x ∈[a , b ]时，f '(x ) ≠0； （3）当x ∈[a , b ]时，f ''(x ) 不变号； （4）
f (0)f (1)
≤1, ， ''f (0)f (1)
则对于任意初始值x ∈[a , b ]，由牛顿迭代格式确定的序列{x k }收敛于f (x ) =0在区间[a , b ]内唯一的根x *。
定理4 设函数f (x ) 在区间[a , b ]内有二阶导数，如果x ∈[a , b ]，满足： （1）f '(x 0) ≠0, f ''(x 0) ≠0； （2）f '(x 0) >
2
f ''(x 0)
f (x 0) ； 2
则以x 0为初始值，由牛顿迭代法所确定的序列{x k }收敛于方程f (x ) =0的根
x *。
#include #include #include #define EPS 1e-6 #define N 100
float f(float x) { return x*x*x+x*x-3*x-3; }
float fd(float x) { return 3*x*x+2*x-3; }
main() { int i=0,n=0; float x[N]; printf("请输入初始值x[0]：\n"); scanf("%f",&x[0]); do { x[i+1]=x[i]-f(x[i])/fd(x[i]); if((n++>N)||fd(x[i])==0) { printf("迭代失败\n"); break; } x[i]=x[i+1]; i++; }
while(fabs(x[i]-x[i-1])>EPS||fabs(f(x[i]))>EPS); for(i=0;i
例1．用牛顿法求方程f (x ) =x (x +1) 2-1=0在0.4附近的根，并精确到6位有效数字。
解：在vc++6.0窗口输入下面程序
#include #include #include #define EPS 1e-6 #define N 100
float f(float x) { return x*(x+1)*(x+1)-1; }
float fd(float x) { return (x+1)*(x+1)+2*x*(x+1); }
main() { int i=0,n=0; float x[N]; printf("请输入初始值x[0]："); scanf("%f",&x[0]); do { x[i+1]=x[i]-f(x[i])/fd(x[i]); if((n++>N)||fd(x[i])==0) { printf("迭代失败\n"); break; } x[i]=x[i+1]; i++; }
while(fabs(x[i]-x[i-1])>EPS||fabs(f(x[i]))>EPS); for(i=0;i
{ printf("x[%d]=%.6f\t\n",i+1,x[i]); } }
程序结果如下：
例2．用牛顿发求方程2xe x -1=0在区间[0,1]内的根。要求精确度为10-4。 解：在vc++6.0窗口输入下面程序 #include #include #include #define EPS 1e-6 #define E 2.7182 #define N 100
float f(float x) { return 2*x*E*E-1; }
float fd(float x) { return 2*E*E; }
main() { int i=0,n=0;
float x[N]; printf("请输入初始值x[0]："); scanf("%f",&x[0]); do { x[i+1]=x[i]-f(x[i])/fd(x[i]); if((n++>N)||fd(x[i])==0) { printf("迭代失败\n"); break; } x[i]=x[i+1]; i++; }
while(fabs(x[i]-x[i-1])>EPS||fabs(f(x[i]))>EPS); for(i=0;i
程序结果如下：
2013-2014（1）专业课程实践论文
题目：方程的牛顿法
一、算法理论
1．牛顿迭代法原理
设已知方程f (x ) =0的近似根x 0, 则在x 0附近f (x ) 可用一阶泰勒多项式p (x ) =f (x 0) +f ' (x 0)(x -x 0) 近似代替。因此, 方程f (x ) =0可近似地表示为
p (x ) =0。用x 1表示p (x ) =0的根, 它与f (x ) =0的根差异不大。
设f ' (x 0) ≠0, 由于x 1满足f (x 0) +f ' (x 0)(x 1-x 0) =0, 解得
x 1=x 0-
f (x 0)
f ' (x 0)
重复这一过程, 得到迭代格式
x n +1=x n -
f (x n )
f ' (x n )
这就是著名的牛顿迭代公式, 它相应的不动点方程为
g (x ) =x -
f (x )
f ' (x )
2. 牛顿迭代法的几何解析
在x 0处作曲线的切线，切线方程为y =f (x 0) +f ' (x 0)(x -x 0) 。令y =0，可得切线与x 轴的交点坐标x 1=x 0-牛顿法又称“切线法”。
3．牛顿迭代法的收敛性
定义 设迭代过程x k +1=ϕ(x k ) 收敛于方程x =ϕ(x ) 的根x *，如果迭代误差
f (x 0)
，这就是牛顿法的迭代公式。因此，f ' (x 0)
εk =x k -x *当k →∞时成立下列关系式
εk +1
→C (C ≠0为常数) ， p εk
则迭代过程是p 阶收敛的。特别的，p =1时称为线性收敛，p >1时称为超线性收敛，p =2时称为平方收敛
定理1 对于迭代过程x k +1=ϕ(x k ) ，如果ϕ(p ) (x ) 在所求根x *的临近连续，并且 则该迭代过程在点 邻近是 阶收敛的。
ϕ'(x *) =ϕ''(x *) = =ϕ(p -1) (x *) =0, ϕ(p ) (x *) ≠0
定理2 如果x *是方程f (x ) 的一个单根，并且f (x ) 在x *及其附近具有连续的二阶导数，则只要初始近似根x 0充分靠近x *，牛顿法在根x *的临近平法收敛。 定理3 设函数f (x ) 在[a , b ]上存在二阶连续导数，且满足条件： （1）f (a ) f (b )
（2）当x ∈[a , b ]时，f '(x ) ≠0； （3）当x ∈[a , b ]时，f ''(x ) 不变号； （4）
f (0)f (1)
≤1, ， ''f (0)f (1)
则对于任意初始值x ∈[a , b ]，由牛顿迭代格式确定的序列{x k }收敛于f (x ) =0在区间[a , b ]内唯一的根x *。
定理4 设函数f (x ) 在区间[a , b ]内有二阶导数，如果x ∈[a , b ]，满足： （1）f '(x 0) ≠0, f ''(x 0) ≠0； （2）f '(x 0) >
2
f ''(x 0)
f (x 0) ； 2
则以x 0为初始值，由牛顿迭代法所确定的序列{x k }收敛于方程f (x ) =0的根
x *。
#include #include #include #define EPS 1e-6 #define N 100
float f(float x) { return x*x*x+x*x-3*x-3; }
float fd(float x) { return 3*x*x+2*x-3; }
main() { int i=0,n=0; float x[N]; printf("请输入初始值x[0]：\n"); scanf("%f",&x[0]); do { x[i+1]=x[i]-f(x[i])/fd(x[i]); if((n++>N)||fd(x[i])==0) { printf("迭代失败\n"); break; } x[i]=x[i+1]; i++; }
while(fabs(x[i]-x[i-1])>EPS||fabs(f(x[i]))>EPS); for(i=0;i
例1．用牛顿法求方程f (x ) =x (x +1) 2-1=0在0.4附近的根，并精确到6位有效数字。
解：在vc++6.0窗口输入下面程序
#include #include #include #define EPS 1e-6 #define N 100
float f(float x) { return x*(x+1)*(x+1)-1; }
float fd(float x) { return (x+1)*(x+1)+2*x*(x+1); }
main() { int i=0,n=0; float x[N]; printf("请输入初始值x[0]："); scanf("%f",&x[0]); do { x[i+1]=x[i]-f(x[i])/fd(x[i]); if((n++>N)||fd(x[i])==0) { printf("迭代失败\n"); break; } x[i]=x[i+1]; i++; }
while(fabs(x[i]-x[i-1])>EPS||fabs(f(x[i]))>EPS); for(i=0;i
{ printf("x[%d]=%.6f\t\n",i+1,x[i]); } }
程序结果如下：
例2．用牛顿发求方程2xe x -1=0在区间[0,1]内的根。要求精确度为10-4。 解：在vc++6.0窗口输入下面程序 #include #include #include #define EPS 1e-6 #define E 2.7182 #define N 100
float f(float x) { return 2*x*E*E-1; }
float fd(float x) { return 2*E*E; }
main() { int i=0,n=0;
float x[N]; printf("请输入初始值x[0]："); scanf("%f",&x[0]); do { x[i+1]=x[i]-f(x[i])/fd(x[i]); if((n++>N)||fd(x[i])==0) { printf("迭代失败\n"); break; } x[i]=x[i+1]; i++; }
while(fabs(x[i]-x[i-1])>EPS||fabs(f(x[i]))>EPS); for(i=0;i
程序结果如下：