迭代法求解方程(组)的根

时间:2023-01-07 23:03:56

 

 

摘自福星师哥的博客在这里给出链接https://blog.csdn.net/Akatsuki__Itachi/article/details/80719686

 

首先,迭代法解方程的实质是按照下列步骤构造一个序列x0,x1,…,xn,来逐步逼近方程f(x)=0的解:

1)选取适当的初值x0;

2)确定迭代格式,即建立迭代关系,需要将方程f(x)=0改写为x=φ(x)的等价形式;

3)   构造序列x0,x1,……,xn,即先求得x1=φ(x0),再求x2=φ(x1),……如此反复迭代,就得到一个数列x0, x1,……,xn,若这个数列收敛,即存在极值,且函数 φ(x)连续,则很容易得到这个极限值迭代法求解方程(组)的根,x*就是方程f(x)=0的根。

 

举个例子:

求解方程: f(x) =x^3-x-1=0  在区间 (1,1.5)内的根。

首先我们将方程写成这种形式:

迭代法求解方程(组)的根

用初始根x0=1.5带入右端,可以得到

迭代法求解方程(组)的根

这时,x0和x1的值相差比较大,所以我们要继续迭代求解,将x1再带入公式得

迭代法求解方程(组)的根

直到我们我们得到的解的序列收敛,即存在极值的时候,迭代结束。

下面是这个方程迭代的次数以及每次xi的解(i=0,1,2....)

迭代法求解方程(组)的根

 

我们发现当k=7和8的时候,方程的解已经不再发生变化了,这时候我们就得到了此方程的近似解。

 

 1 #define eps 1e-8
 2 int main()
 3 {
 4     x0=初始近似根;
 5     do{
 6         x1=x0;
 7         x0=g(x1); //按特定的方程计算新的近似根
 8     }while(fabs(x0-x1)>eps);
 9     printf("方程的近似根是%f\n",x0);
10 }

 

注意:如果方程无解,算法求出的近似根序列就不会收敛,那么迭代过程就会变成死循环。因此,在使用迭代算法前应先考察方程是否有解,并在算法中对迭代次数给予限制。

 

下面再写一个求解方程组的例子加深一下理解:

迭代法求解方程(组)的根

 

算法说明:

方程组解的初值X=(x0,x1,…,xn-1),迭代关系方程组为:xi=gi(X)(i=0,1,…,n-1),w为解的精度,maxn为迭代次数。

算法如下:

算法核心:

 1 int main()
 2 {
 3     for (i=0; i<n; i++)
 4         x[i]=初始近似根;
 5     do
 6     {
 7         k=k+1;
 8         for(i=0; i<n; i++ 9             y[i]=x[i];
10         for(i=0; i<n; i++)
11             x[i]=gi(X);   //按特定的方程计算新的近似根
12         c=0;
13         for(i=0; i<n; i++)
14             c=c+fabs(y[i]-x[i]);//c要每次重新设初值为0
15     }while(c>eps and k<maxn );
16     for(i=0; i<n; i++)
17         print("变量的近似根是",x[i]);
18 }

 

选取初始向量 迭代法求解方程(组)的根

精确度为1e-8,迭代次数为100

求解代码如下:

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #define eps 1e-8
 6 using namespace std;
 7 const int maxn=100;
 8 double x[10],y[10];
 9 int main()
10 {
11     for(int i=1;i<=4;i++)
12         x[i]=0;
13     int cnt=0;
14     double c=0;
15     do{
16         for(int i=1;i<=4;i++)
17             y[i]=x[i];
18         for(int i=1;i<=4;i++)
19         {
20             x[1]=(6+x[2]-2*x[3])/10;
21             x[2]=(25+x[1]+x[3]-3*x[4])/11;
22             x[3]=(-11-2*x[1]+x[2]+x[4])/10;
23             x[4]=(15-3*x[2]+x[3])/8;
24         }
25         c=0;
26         for(int i=1;i<=4;i++)
27             c+=(fabs(y[i]-x[i]));
28     }while(c>eps&&cnt<maxn);
29     for(int i=1;i<=4;i++)
30         printf("x%d = %.4lf\n",i,x[i]);
31 }

 

运行结果如下:

迭代法求解方程(组)的根

 

迭代法求解方程的过程是多样化的,比如二分逼近法求解,牛顿迭代法等。

下面就是效率比较高且比较常用的牛顿迭代法

牛顿迭代法又称为切线法,它比一般的迭代法有更高的收敛速度,如下图所示。

首先, 选择一个接近函数f(x)零点的x0, 计算相应的f(x0)和切线斜率f'(x0)(这里f '  表示函数f的导数)。然后我们计算穿过点   (x0,f (x0))且斜率为f '(x0)的直线方程

迭代法求解方程(组)的根

和x轴的交点的x的坐标,也就是求如下方程的解

迭代法求解方程(组)的根

将新求得交点的x坐标命名为x1。如图4所示,通常x1会比x0更接近方程f(x) = 0的解。接下来用x1开始下一轮迭代 .

迭代公式可化简为:

迭代法求解方程(组)的根

上式就是有名的牛顿迭代公式。已经证明, 如果f'  是连续的, 并且待求的零点x是孤立的, 那么在零点x周围存在一个区域, 只要初始值x0位于这个邻近区域内, 那么牛顿法必定收敛。

迭代法求解方程(组)的根

 

迭代法求解方程(组)的根

求形如ax^3+bx^2+cx+d=0方程根的算法,系数a、b、c、d的值依次为1、2、3、4,由主函数输入。求x在1附近的一个实根。求出根后由主函数输出。

 

由以上的公式可得到代码:

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #define eps 1e-8
 6 using namespace std;
 7 int main()
 8 {
 9     double a,b,c,d;
10     cin>>a>>b>>c>>d;
11     double x1=1,x,f,fx;
12     do{
13         x=x1;
14         f=((a*x+b)*x+c)*x+d;
15         fx=(3*a*x+2*b)*x+c;
16         x1=x-f/fx;
17     }while(fabs(x1-x)>=eps);
18     printf("%.2lf",x1);
19 }

结果如下:

迭代法求解方程(组)的根

 

接下来说一下二分逼近法

用二分法求解方程f(x)=0根的前提条件是:f(x)在求解的区间[a,b]上是连续的,且已知f(a)与f(b)异号,即 f(a)*f(b)<0。

令[a0,b0]=[a,b],c0=(a0+b0)/2,若f(c0)=0,则c0为方程f(x)=0的根;否则,若f(a0)与f(c0)异号,即 f(a0)*f(c0)<0,则令[a1,b1]=[a0,c0];若f(b0)与f(c0)异号,即 f(b0)*f(c0)<0,则令[a1,b1]=[c0,b0]。

 依此做下去,当发现f(cn)=0时,或区间[an,bn]足够小,比如| an-bn |<0.0001时,就认为找到了方程的根。

迭代法求解方程(组)的根

 

例:

用二分法求一元非线性方程f(x)= x^3/2+2x^2-8=0(其中^表示幂运算)在区间[0,2]上的近似实根r,精确到0.0001.

算法如下:

 

 1 int main( )
 2 {
 3     double x,x1=0,x2=2,f1,f2,f;
 4     print(“input a,b (f(a)*f(b)<0)”);
 5     input(a,b);
 6     f1=x1*x1*x1/2+2*x1*x1-8;
 7     f2=x2*x2*x2/2+2*x2*x2-8;
 8     if(f1*f2>0)
 9     {
10         printf("No root");
11         return;
12     }
13     do{
14         x=(x1+x2)/2;
15         f=x*x*x/2+2*x*x-8;
16         if(f=0)
17             break;
18         if(f1*f>0.0)
19         {
20             x1=x;
21             f1=x1*x1*x1/2+2*x1*x1-8;
22         }
23         else
24             x2=x;
25     }
26     while(fabs(f)>=1e-4);
27     print("root=",x);
28 }