首先,疊代法解方程的實質是按照下列步驟構造一個序列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 }
作者:王陸