共軛梯度法和LU分解程序

1、一.共軛梯度法共軸梯度法是介于最速下降法與牛頓法之間的一個(gè)方法，它僅需利用一階導(dǎo)數(shù)信息，但 克服了最速下降法收斂慢的缺點(diǎn)，又避免了牛頓法需要存儲(chǔ)和計(jì)算Hesse矩陣并求逆的缺 點(diǎn)，共軸梯度法不僅是解決大型線性方程組最有用的方法之一，也是解大型非線性最優(yōu)化最 有效的算法之一。共軸梯度法最早是又Hestenes和Stiefle(1952)提出來的，用于解正定系數(shù)矩陣的線 性方程組，在這個(gè)基礎(chǔ)上，F(xiàn)letcher和Reeves(1964)首先提出了解非線性最優(yōu)化問題的 共軸梯度法。由于共軸梯度法不需要矩陣存儲(chǔ)，且有較快的收斂速度和二次終止性等優(yōu)點(diǎn)， 現(xiàn)在共軸梯度法已經(jīng)廣泛地應(yīng)用與實(shí)際問題中。共軸梯度

2、法是一個(gè)典型的共軸方向法，它的每一個(gè)搜索方向是互相共軸的，而這些搜索 方向d僅僅是負(fù)梯度方向與上一次迭代的搜索方向的組合，因此，存儲(chǔ)量少，計(jì)算方便.下面舉一個(gè)例子通過C程序來求解線性方程組的解.例：已知 a44=1,1,1,1,1,2,3,4,1,3,6,10,1,4,10,20，b4=1,6,3,4，通過共軸梯度 法試求解線性方程組ax=b的解.解：以下便是C求解的程序：include include int a44=1,1,1,1,1,2,3,4,1,3,6,10,1,4,10,20,i,j,k;doubleX04=0,0,0,0,x14=0,0,0,0,r04,r14,d04,d14,s

3、4=0,0,0,0,b4=1,6,3,4;double c0,c1,p;double sum (double *r)double t=0.0;for (i=0;i4;i+)t+=ri*ri;return t;void main()for (i=0;i4;i+) for(j=0;j4；j+)si+=aij*x0j;r0i=bi-si;d0i=r0i;for(k=0;k4;k+)double u4=0,0,0,0,w4=0,0,0,0,v=0.0;for (i=0;i4;i+)for(j=0;j4;j+)ui+=aij*d0j;v+=d0i*ui;c0=sum(r0)/v;for(i=0;i4;i

4、+)x1i=x0i+c0*d0i;for (i=0;i4;i+)for(j=0;j4;j+)wi+=aij*x1j;r1i=bi-wi;if (sqrt(sum(r1)/sum(b)0.000001|k=4) break;elsep=sum(r1)/sum(r0);for (i=0;i4;i+)d1i=r1i+p*d0i;for (i=0;i4;i+) d0i=d1i;r0i=r1i;x0i=x1i;printf(輸出最優(yōu)解為：);for(i=0;i4;i+)printf(%5.2f,x1i);printf(nn);printf(-此時(shí)的殘差向量為：);for (i=0;i4;i+)print

5、f(%5.2f,r1i);輸出結(jié)果為：輸出最優(yōu)解為：-24.0057.00-44.0012.00此時(shí)的殘差向量為：0.00 0.00 0.00 0.00Press any key to continue二矩陣的LU分解在求解最優(yōu)化問題的許多算法中，求搜索方向d0的問題最終歸結(jié)為求解一個(gè)線性方程 組Ax=b，而且在大多數(shù)的情況下系數(shù)矩陣A式對(duì)稱正定矩陣，在線性方程組求解中關(guān)鍵是 矩陣分解技術(shù)，若一個(gè)矩陣A的各順序主子式都不為0,則存在唯一的單位下三角陣L和可 逆的上三角陣U,滿足 A=LU，稱其為矩陣A的LU分解.下面也通過一個(gè)簡單的實(shí)例來進(jìn)行矩陣的LU分解.例：a33 = 5,2,-4,2,1

6、,2,-4,-2,5，對(duì)矩陣 A 進(jìn)行 LU 分解.解：以下便是C求解的程序：includeincludeint a33=5,2,-4,2,1,2,-4,-2,5,i,j,k;double l33=1,0,0,0,1,0,0,0,1,u33=0,t3=0,f3=0,w=0;void main ()printf(原來矩陣為：n);for(i=0;i3;i+)for(j=0;j3;j+)printf(%5d,aij);printf(n);printf(nn);for(i=0;i3;i+)u0i=a0i;li0=ai0/u00;for(i=1;i3;i+)for (j=0;ji;j+)ti+=lij

7、*uji;uii=aii-ti;for(j=i+1;j3;j+)for(k=0;ki;k+)fj+=lik*ukj;uij=aij-fj;lji=(aji-fj)/uii;for (k=0;k2;k+)w+=l2k*uk2;u22=a22-w;printf(分解的上三角矩陣為：n);for(i=0;i3;i+)for(j=0;j3;j+)printf(%5.2f,lij);printf(n);printf(nn);printf(分解的下三角矩陣為：n);for(i=0;i3;i+)for(j=0;j3;j+)printf(%5.2f,uij);printf(n);輸出結(jié)果為：原來矩陣為： TOC o 1-5 h z 52-4212-4-25分解的上三角矩陣為：1.00 0.0