一種求解非線性方程組的混合優化算法及程序實現

摘要：非線性方程組求解是工程實踐與理論研究中的一個典型問題。傳統的方法主要有梯度法、Newton迭代法等。該文綜合修正Newton法與梯度法的各自優勢，對非線性方程組的求解問題提出了一種混合方法并用C語言編碼實現該算法。將兩種方法相結合，使其相互取長補短，在迭代初始值不太好的情況下也能保證收斂性，同時加快收斂速度，數值結果表明該算法是有效的。

關鍵詞：非線性方程組；修正牛頓法；最速下降法；混合算法；C語言編碼

中圖分類號：TP312文獻標識碼：A文章編號：1009-3044(2008)36-3024-03

A Hybrid Optimization Algorithm and Program for Solving the Nonlinear Equations

CHEN Wen-qing

(Shaoxing Top Institute of Information and Technology， Shaoxing 312000， China)

Abstract: Solving the nonlinear equations is a typical problem in project practice and theory research. The traditional methods are gradient methods， Newton’s method etc. In this paper， a hybrid algorithm and C language program for solving the nonlinear equations is proposed. It adopts the merits of both modified Newton methods and gradient methods。Even when the iterative initialization is not very well ， it can also ensure the convergence purpose and accelerate the rate of the convergence as well. It shows that the new algorithm is effective by solving proposed nonlinear equations.

Key words: nonlinear equations; modified Newton methods; steepest decent algorithm; hybrid algorithm; C language coding

1 引言

在工程計算中常會遇到非線性代數方程組的求解問題。解非線性方程組F（X）=0，通常方法有兩大類：一類屬于線性化方法，即用一線性代數方程組求近似逼近非線性代數方程組，由此構造一組遞推公式，用于逐次逼近所求的根。這類方法主要有牛頓迭代法及各種改進，用Newton方法求解，初始點的選取適當否決定了算法的收斂性及收斂速度；另一類方法是把方程組所求解問題化為多元函數的極小值的等效問題求解。這類方法主要度法及其各種改進。

梯度法的優點是程序簡單，每次迭代所需的計算量小，所要求的存儲量變少，而從一個不太好的初始近似出發，還是能收斂于局部極小值點。這個方法最大的最大缺點是收斂速度慢。（線性速度），尤其在解的附近，常為了提高一點精度而需要付出很大的代價。牛頓法具有收斂快和自校正等優點，其收斂階大于等于2，但初始值選取不當易導致求解失敗。結合兩算法優點，先采用梯度法搜索出X*，當F值降到一定程度以后，再改用修正Newton法進行若干步搜索。這樣，把梯度法與牛頓法相結合，就能使兩個方法相互取長補短，在迭代初始值不太好的情況下也能保證收斂性，加快收斂速度。

2 問題描述

設有如下非線性方程組的求解問題：

F(X)=0 (1)

x∈D，D?奐Rn有界，F(f1(X)，f2(X)，…fn(X))T=0，其中，fi:Rn→R(i=1，2，…n)是連續可微的實值函數。若存在X*∈D使F(X*)=0，則X*稱為方程組(1)的解。

用最速下降法解方程組（1）時，通常將方程組（1）構造一目標函數：

F(X)= fi2(X) (2)

于是非線性方程組(1)的解就是上式(2)的零極小值點，反之亦然。

3 混合算法

步驟1：給定初值X0、最速下降法允許誤差E、控制常數C、修正Newton法計算精度e1、e2及簡化步m值。

步驟2：用最速下降法搜索出X*。

步驟3：用修正Newton法再進行若干步搜索，若未找出比X*更好的點，結束。否則，將修正Newton法找到的更好的點替代X*，返回步驟1。

4 實例與程序設計過程

驗證方法的可行性與有效性，舉例進行數值實驗。

例：

此方程有兩個精確解x*=(-1/sqr(2)，3/2)T，(0，1)T。

由于篇幅有限，以下是程序主要代碼：

# include \"stdio.h\"

# include \"math.h\"

#include \"time.h\"

# define PI3.1415926

# define N 2

double x[N+1]，a[N+1][N+1]，a1[N+1][N+1];

void zsxj(double E，double c) //最速下降法

{int i，k=0;

double DF[N+1]，Dx[N+1]，F0，sum，RL;

while(fabs(F())>E)

{ F0=F(); //F()函數功能為計算目標函數值

for(i=1;i<=N;i++)

{ if(x[i]==0)Dx[i]=c;

else Dx[i]=c*x[i];

}

sum=0;

for(i=1;i<=N;i++)

{ x[i]=x[i]+Dx[i];

DF[i]=(F()-F0)/Dx[i];

sum=sum+DF[i]*DF[i];

x[i]=x[i]-Dx[i];

}

RL=F()/sum;

for(i=1;i<=N;i++)x[i]=x[i]-RL*DF[i];

k++;

}

printf(\"采用最速下降法搜索到的解:\\");

printf(\" k=%d\"，k);

for(i=1;i<=N;i++)

printf(\"x[%d]=%lf \"，i，x[i]);

}

void xzNewton(float e1，float e2，int m) //x修正牛頓法

{int i，j，t，ok，k;

double z[N+1]，b[N+1]，fanshu_z，fanshu_x，fanshu_F;

k=1;ok=1;

while(ok)

{jacobi_A();//求非線性方程組的Jacobi矩陣

A_1();//求矩陣逆陣

jacobi_A();

for(t=1;t<=m;t++) //m次簡化牛頓步

{for(i=1;i<=N;i++)

b[i]=f(i);

for(i=1;i<=N;i++)

for(j=1;j<=N;j++)

{x[i]=x[i]-a1[i][j]*b[j];

z[i]=a[i][j]*b[j];

}}

fanshu_z=0;fanshu_x=0;

fanshu_F=0;

for(i=1;i<=N;i++) //求z，x，F范數

{ fanshu_z=fanshu_z+fabs(z[i]);

fanshu_x=fanshu_x+fabs(x[i]);

fanshu_F=fanshu_F+fabs(f(i));

}

if(fanshu_z<=e1*fanshu_x||fanshu_F<=e2)

{ printf(\"\采用修正牛頓法求得的解:\\");

printf(\" k=%d\"，k);

for(i=1;i<=N;i++)

printf(\"x[%d]=%lf \"，i，x[i]);

ok=0;

}

else k=k+1;

}}

void main()

{ int i，m;

double E，c，e1，e2;

time_t start，end;//定義時間變量

long unsigned t;

printf(\"非線性方程組:\\");

nline_qs();//輸出非線性方程組

printf(\"輸入初始點X值:\\");

for(i=1;i<=N;i++)

{printf(\"x%d=\"，i);scanf(\"%lf\"，x[i]);}

printf(\"初始點X值:\\");

printf(\"x[1]=%lf，x[2]=%lf\\"，x[1]，x[2]);

printf(\"輸入最速下降法允許誤差E和C:\\");

printf(\"E=\");

scanf(\"%lf\"，E);

printf(\"c=\");

scanf(\"%lf\"，c);

printf(\"輸入修正newton法計算精度e1和

e2及簡化步m的值:\e1=\");

scanf(\"%lf\"，e1);

printf(\"e2=\");scanf(\"%lf\"，e2);

printf(\"m=\");scanf(\"%d\"，m);

start=time(NULL);

zsxj(E，c);

xzNewton(e1，e2，m);

end=time(NULL);

printf(\"\用了%f 秒\\"，difftime(end，start)); //求時間差

}

運行界面如圖1。

4 結論

本程序采用C語言編寫完成，對求解非線性方程組，讀者只需要根據具體所求解方程組適當修改即可，本程序的編寫中，還可采用更好的方式實現，優化代碼。從計算結果可以看出，把梯度法與牛頓法相結合，能使兩個方法相互取長補短。先采用最速下降法搜索出X*，當F值降到一定程度以后，再用修正Newton法進行若干步搜索，若未找出比X*更好的點，結束。否則，將修正Newton法找到的更好的點替代X*，這樣在迭代初始值不太好的情況下也能保證收斂性，同時又加快收斂速度，特別當初始值X0選取離解X*比較遠時，效果顯著。

參考文獻：

[1] 李慶楊.非線性方程組的數值解法[M].北京:科學出版社，1999.

[2] Ortega J M，Rheinboldt W G.Iterative Solution of Nonlinear Equations in Several Variables[M].New York:Academic Press，1970.

[3] 鄭咸義.數值計算方法與FORTRAN語言[M].北京:電子工業出版社，1986.

[4] 角仕云.實用科學與工程計算方法[M].北京:科學出版社，2000.

[5] 北大數學系幾何與代數教研小組.高等代數[M].北京:北京:高等教育出版社，1997.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”