一种求解非线性方程组的混合优化算法及程序实现

一种求解非线性方程组的混合优化算法及程序实现
　　摘要：非线性方程组求解是工程实践与理论研究中的一个典型问题。传统的方法主要有梯度法、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格式阅读原文。”

　　相关热词搜索：

　　方程组

　　求解

　　算法

　　混合

　　优化


　　2022/0305/38047
 

版权声明：本站所有文章皆为原创，欢迎转载或转发，请保留网站地址和作者信息。