网络热词 > 牛顿迭代法

牛顿迭代法

牛顿迭代法(Newton'smethod)又称为牛顿-拉弗森方法(Newton-Raphsonmethod),它是一种在实数域和复数域上近似求解方程的方法。方法使用函数的泰勒级数的前面几项来寻找方程的根。

牛顿迭代法(Newton's method)又称为牛顿-拉夫逊方法(Newton-Raphson method),它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。多数方程不存在求根公式,因此求精确根非常困难,甚至不可能,从而寻找方程的近似根就显得特别重要。

方法使用函数f(x)的泰勒级数的前面几项来寻找方程f(x) = 0的根。牛顿迭代法是求方程根的重要方法之一,其最大优点是在方程f(x) = 0的单根附近具有平方收敛,而且该法还可以用来求方程的重根、复根,此时线性收敛,但是可通过一些方法变成超线性收敛。另外该方法广泛用于计算机编程中。

设r是f(x) = 0的根,选取x0作为r初始近似值,过点(x0,f(x0))做曲线y = f(x)的切线L,L的方程为y = f(x0)+f'(x0)(x-x0),求出L与x轴交点的横坐标 x1 = x0-f(x0)/f'(x0),称x1为r的一次近似值。过点(x1,f(x1))做曲线y = f(x)的切线,并求该切线与x轴交点的横坐标 x2 = x1-f(x1)/f'(x1),称x2为r的二次近似值。重复以上过程,得r的近似值序列,其中x(n+1)=x(n)-f(x(n))/f'(x(n)),称为r的n+1次近似值,上式称为牛顿迭代公式

解非线性方程f(x)=0的牛顿法是把非线性方程线性化的一种近似方法。把f(x)在x0点附近展开成泰勒级数 f(x) = f(x0)+(x-x0)f'(x0)+(x-x0)^2*f''(x0)/2! +… 取其线性部分,作为非线性方程f(x) = 0的近似方程,即泰勒展开的前两项,则有f(x0)+f'(x0)(x-x0)=0 设f'(x0)≠0则其解为x1=x0-f(x0)/f'(x0) 这样,得到牛顿法的一个迭代序列:x(n+1)=x(n)-f(x(n))/f'(x(n))。

已经证明,如果是连续的,并且待求的零点是孤立的,那么在零点周围存在一个区域,只要初始值位于这个邻近区域内,那么牛顿法必定收敛。 并且,如果不为0, 那么牛顿法将具有平方收敛的性能. 粗略的说,这意味着每迭代一次,牛顿法结果的有效数字将增加一倍。

军人在进攻时常采用交替掩护进攻的方式,若在数轴上的点表示A,B两人的位置,规定在前面的数大于后面的数,则是A>B,B>A交替出现。但现在假设军中有一个胆小鬼,同时大家又都很照顾他,每次冲锋都是让他跟在后面,每当前面的人占据一个新的位置,就把位置交给他,然后其他人再往前占领新的位置。也就是A始终在B的前面,A向前迈进,B跟上,A把自己的位置交给B(即执行B = A操作),然后A 再前进占领新的位置,B再跟上……直到占领所有的阵地,前进结束。像这种两个数一前一后逐步向某个位置逼近的方法称之为迭代法。

迭代法也称辗转法,是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法(或者称为一次解法),即一次性解决问题。迭代算法是用计算机解决问题的一种基该方法。它利用计算机运算速度快、适合做重复性操作的特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。

利用迭代算法解决问题,需要做好以下三个方面的工作:

一、确定迭代变量。在可以用迭代算法解决的问题中,至少存在一个直接或间接地不断由旧值递推出新值的变量,这个变量就是迭代变量。

二、建立迭代关系式。所谓迭代关系式,指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是解决迭代问题的关键,通常可以使用递推或倒推的方法来完成。

三、对迭代过程进行控制。在什么时候结束迭代过程?这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况:一种是所需的迭代次数是个确定的值,可以计算出来;另一种是所需的迭代次数无法确定。对于前一种情况,可以构建一个固定次数的循环来实现对迭代过程的控制;对于后一种情况,需要进一步分析出用来结束迭代过程的条件。

最经典的迭代算法是欧几里德算法,用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理:

定理:gcd(a,b) = gcd(b,a mod b)

证明:a可以表示成a = kb + r,则r = a mod b。假设d是a,b的一个公约数,则有 a%d==0,b%d==0,而r = a - kb,因此r%d==0 ,因此d是(b,a mod b)的公约数

同理,假设d 是(b,a mod b)的公约数,则 b%d==0,r%d==0 ,但是a = kb +r ,因此d也是(a,b)的公约数。

因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得证。

欧几里德算法就是根据这个原理来做的,欧几里德算法又叫辗转相除法,它是一个反复迭代执行,直到余数等于0停止的步骤,这实际上是一个循环结构。其算法用C语言描述为:

int Gcd_2(int a,int b)// 欧几里德算法求a,b的最大公约数

if (a<=0 || b<=0)//预防错误

return 0;

int temp;

while (b > 0)//b总是表示较小的那个数,若不是则交换a,b的值

temp = a % b;//迭代关系式

a = b; //是那个胆小鬼,始终跟在b的后面

b = temp; //向前冲锋占领新的位置

return a;

从上面的程序我们可以看到a,b是迭代变量,迭代关系是temp = a % b;根据迭代关系我们可以由旧值推出新值,然后循环执a = b; b = temp;直到迭代过程结束(余数为0)。在这里a好比那个胆小鬼,总是从b手中接过位置,而b则是那个努力向前冲的先锋。

还有一个很典型的例子是斐波那契(Fibonacci)数列。斐波那契数列为:0、1、1、2、3、5、8、13、21、…,即 fib⑴=0; fib⑵=1;fib(n)=fib(n-1)+fib(n-2) (当n>2时)。

在n>2时,fib(n)总可以由fib(n-1)和fib(n-2)得到,由旧值递推出新值,这是一个典型的迭代关系,所以我们可以考虑迭代算法。

int Fib(int n) //斐波那契(Fibonacci)数列

if (n < 1)//预防错误

return 0;

if (n == 1 || n == 2)//特殊值,无需迭代

return 1;

int f1 = 1,f2 = 1,fn;//迭代变量

int i;

for(i=3; i<=n; ++i)//用i的值来限制迭代的次数

fn = f1 + f2; //迭代关系式

f1 = f2;//f1和f2迭代前进,其中f2在f1的前面

f2 = fn;

return fn;

double func(double x) //函数   

return x*x*x*x-3*x*x*x+1.5*x*x-4.0;

double func1(double x) //导函数

return 4*x*x*x-9*x*x+3*x;

int Newton(double *x,double precision,int maxcyc) //迭代次数   

{double x1,x0;  int k;  x0=*x;  for(k=0;k<maxcyc;k++)  

{if(func1(x0)==0.0)//若通过初值,函数返回值为0  

{ printf("迭代过程中导数为0!\n");  

return 0;}  

x1=x0-func(x0)/func1(x0);//进行牛顿迭代计算   if(fabs(x1-x0)<precision || fabs(func(x1))<precision) //达到结束条件   

{ *x=x1; //返回结果   return 1;  

} else //未达到结束条件   x0=x1; //准备下一次迭代   

} printf("迭代次数超过预期!\n"); //迭代次数达到,仍没有达到精度  

return 0; } int main()  

{ double x,precision;  int maxcyc;  printf("输入初始迭代值x0:");  

scanf("%lf",&x);   

printf("输入最大迭代次数:");   

scanf("%d",&maxcyc);  

printf("迭代要求的精度:");  

scanf("%lf",&precision);  

if(Newton(&x,precision,maxcyc)==1) //若函数返回值为1   

printf("该值附近的根为:%lf\n",x);  

else //若函数返回值为0   

printf("迭代失败!\n");  

getch();  

return 0;  }

//此函数是用来求3元一次方程ax^3+bx^2+cx+d=0的解

//比如 x^3-27=0,我们就可以输入1 0 0 -27,这样我们就可以得到一个解

#include<iostream>

#include<cmath>

using namespace std;

int main()

{double diedai(double a,double b,double c,double d,double x);

double a,b,c,d;

double x=10000.0;

cout<<"请依次输入方程四个系数:";

cin>>a>>b>>c>>d;

x=diedai(a,b,c,d,x);

cout<<x<<endl;

return 0;}

double diedai(double a,double b,double c,double d,double x)

{while(abs(a*x*x*x+b*x*x+c*x+d)>0.000001)

{x=x-(a*x*x*x+b*x*x+c*x+d)/(3*a*x*x+2*b*x+c);

}return x;}

Python代码以实例展示求解f(x) = (x-3)**3,f(x) = 0 的根。def f(x):

return (x-3)**3 ’''定义f(x) = (x-3)**3'''

def fd(x):

return 3*((x-3)**2) ’''定义f'(x) = 3*((x-3)**2)

def newtonMethod(n,assum):

time = n

x = assum

Next = 0

A = f(x)

B = fd(x)

print('A = ' + str(A) + ',B = ' + str(B) + ',time = ' + str(time))

if f(x) == 0.0:

return time,x

else:

Next = x - A/B

print('Next x = '+ str(Next))

if A == f(Next): print('Meet f(x) = 0,x = ' + str(Next)) ’''设置迭代跳出条件,同时输出满足f(x) = 0的x值'''

else:

returnnewtonMethod(n+1,Next)

newtonMethod(0,4.0) ’''设置从0开始计数,x0 = 4.0'''

All rights reserved Powered by 网络热词 87994.com

copyright ©right 2010-2020。
网络热词内容来自网络,如有侵犯请联系客服。zhit325@126.com