0043算法筆記——【隨機化算法】解非線性方程組

1、問題描述求解下面的非線性方程組.%工,%）=。!辦（對K*,、工猶）=。:工（看/3/肌）=。其中，x1,x2,x1,x2, ,x x 促實變量，fifi 是未知量 x1,x2,x1,x2, ,xnxn 的非線性實函,*數(shù)。要求確定上述方程組在指定求根范圍內(nèi)的一組解“%工。問題分析解決這類問題有多種數(shù)值方法，如：牛頓法、擬牛頓法、粒子群算法等。最常用的有線性化方法和求函數(shù)極小值方法。為了求解所給的非線性方程組，構造一目標函數(shù)n（工）=/：（幻式中，x=x=（x1,x2,x1,x2,xnxn）易知，上式取得極小值點即是所求非線性方程組的一組解。求解思路在指定求根區(qū)域 D D 內(nèi)，選定一個隨機點

2、x0 x0 作為隨機搜索的出發(fā)點。在算法的搜索過程中，假設第 j j 步隨機搜索得到的隨機搜索點為 xjxj。在第 j+1j+1 步，計算出下一步的隨機搜索增量 dxjdxj。從當前點 xjxj 依 dxjdxj 得到第 j+1j+1 步的隨機搜索點。當 xx 時，取為所求非線性方程組的近似解。否則進行下一步新的隨機搜索過程。題外話：筆者在讀王曉東算法設計與分析中這一節(jié)時，發(fā)現(xiàn)書上所給的代碼似乎有些問題。在這里指出，如果提得不對，還請大俠們拍磚。書中給出的代碼具體如下：cppviewplaincopy1.boolnonlinear(double*x0,double*dx0,double*x,d

3、oublea0,2.doubleepsilon,doublek,intn,intsteps,intm)3.4.staticrandomnumberrad;5.boolsuccess;6.double*dx,*r;7.dx=newdoublen+1;8.r=newdoublen+1;9.intmm=0;10.intj=0;11.doublea=a0;12.for(inti=1;iepsilon)&(jsteps)20.21.if(fxm)a/=k;32.33.for(inti=1;i=n;i+)34.ri=2.0*rnd.fRandom()-1;35.if(success)36.for(inti

4、=1;in;i+)37.dxi=a*ri;38.else39.for(inti=1;in;i+)40.dxi=a*ri-dxi;41.for(inti=1;in;i+)42.xi+=dxi;43.fx=f(x,n);44.45.if(fxepsilon)&(jsteps)句中， 循環(huán)控制變量jsteps,但在循環(huán)體中，j沒有自加，while循環(huán)永遠不會結束。問題2：在循環(huán)體結束時，有賦值語句：fx=f(x,n);筆者發(fā)現(xiàn)如果此時fxepsilon時，程序while循環(huán)體會繼續(xù)執(zhí)行，到while開始幾句是會更新min的值，可循環(huán)不會跳出，而會繼續(xù)往下執(zhí)行，更新數(shù)組x的值，重新計算目標函數(shù)f(x)

5、。這樣即時程序找到方程的解，也不會停下來。筆者糾正后具體程序如下：cppviewplaincopy1.隨機化算法解線性方程組2.#includestdafx.h3.#includeRandomNumber.h4.#include5.usingnamespacestd;6.7.boolNonLinear(double*x0,double*dx0,double*x,doublea0,8.doubleepsilon,doublek,intn,intSteps,intM);9.10.doublef(double*x,intn);11.intmain()12.(13.double*x0,/根初值14.*

6、x,/根15.*dx0,/增量初值16.a0=0.0001,/步長17.epsilon=0.01,/精度18.k=1.1;/步長變參19.intn=2,/方程個數(shù)20.Steps=10000,/執(zhí)行次數(shù)21.22.M=1000;/失敗次數(shù)23.x0=newdoublen+1;24.dx0=newdoublen+1;25.26.x=newdoublen+1;27./根初值28.x01=0.0;29.30.x02=0.0;31./增量初值32.dx01=0.01;33.34.dx02=0.01;35.cout原方程組為：endl;36.coutx1-x2=1endl;37.38.coutx1+x2

7、=3endl;39.40.cout此方程租的根為：endl;41.boolflag=NonLinear(x0,dx0,x,a0,epsilon,k,n,Steps,M);42.while(!flag)43.(44.flag=NonLinear(x0,dx0,x,a0,epsilon,k,n,Steps,M);45.)46.for(inti=1;i=n;i+)47.(48.coutxi=xi;49.)50.coutendl;52.return0;53.54.55./解非線性方程組的隨機化算法56.boolNonLinear(double*x0,double*dx0,double*x,double

8、a0,57.doubleepsilon,doublek,intn,intSteps,intM)58.59.staticRandomNumberrnd;60.boolsuccess;/搜索成功標志61.double*dx,*r;62.63.dx=newdoublen+1;/步進增量向量64.newdoublen+1;/搜索方向向量65.intmm=0;/當前搜索失敗次數(shù)66.intj=0;/67.doublea=a0;/迭代次數(shù)步長因子68.69.for(inti=1;i=n;i+)70.71.xi=x0i;72.dxi=dx0i;73.74.75.doublefx=f(x,n);/計算目標函數(shù)

9、值76.doublemin=fx;/當前最優(yōu)值77.78.while(jSteps)79.80.81./(1)計算隨機搜索步長if(fxM)91.92.a/=k;93.94.success=false96.97.if(minepsilon)98.(99.break;100.101.102./(2)計算隨機搜索方向和增量103.for(inti=1;i=n;i+)104.(105.ri=2.0*rnd.fRandom()-1;106.107.108.if(success)109.(110.for(inti=1;i=n;i+)111.(112.dxi=a*ri;113.114.115.else116.(117.for(inti=1;i=n;i+)118.(119.dxi=a*ri-dxi;23./(3)計算隨機搜索點124.for(inti=1;i=n;i+)125.(126.xi+=dxi;127.128.129./(4)計算目標函數(shù)值130.fx=f(x,n);131.j+；132.133.134.if(fx=epsilon)135.(136.returntrue;137.138.else139.(44.doublef(double*x,intn)145.146.return(x1-x2-1)*