基于Rn中變分原理的迭代法的研究與實例

1、實驗1 基于Rn中變分原理的迭代法的研究與實例分析一、實驗目的研究基于變分原理以及相應問題空間的特征來設計數值求解算法這一比較普遍的數值求解技術。二、實驗內容1、從理論上討論與總結基于Rn中變分原理推出求解線性代數方程組迭代法的關鍵步驟以及從一般迭代法到按不同特征形成幾個特殊具體的迭代法的形成過程；2、分析松弛因子與下降方向的影響；3、按不同特征選擇幾個線性代數方程組求解示例進行算法設計；4、用Matlab進行程序設計與運行實驗。三、實驗原理、方法和手段3.1 Rn中的變分原理設為一個n階對稱正定矩陣，bRn .則其中x=x, Ax-2x,b該定理把求解Ax=b等價于將一個多元二次函數（也稱泛

2、函）極小化的問題。松弛法的任務是取向量序列xk,使(xk)收斂于x的極小值。給定初值x(0),選取c(k-1),求使得x在向量xk= xk-1+ c(k-1)上達極小。分析可得最小的為k-1= rk-1,ck-1 /Ack-1,ck-1 為保證序列(xk)從總體上收斂最快，令= k-1k-1可得迭代格式xk= xk-1+ k-1k-1c(k-1)當0k-12時收斂。當k取不同范圍時對應的迭代可分為亞松弛0k1完全松弛k=1超松弛1k2實踐表明，對某些矩陣用超松弛迭代比完全松弛收斂快。3.2 坐標松弛在一般松弛法中，取c(k-1)=ei, k-1= i則第i個分量的迭代格式為xi(k)= xi(

3、k-1)+ i(bi- j=1i-1aijxjk- j=inaijxjk-1)/aiii=k-1mod n+1, k=1,2,最佳松弛因子為opt=21+1-HJ2其中HJ為雅克比迭代矩陣。3.3 最優(yōu)斜量法取c(k-1)=r(k-1)得最優(yōu)斜量法迭代公式如下xk= xk-1+ k-1k-1c(k-1)k-1= rk-1,rk-1 /Ark-1,rk-1 r(k-1)=b-Ax(k-1)可驗證gradx|x(k-1)= -2r(k-1)。即r(k-1)是(x)在xk-1點梯度方向的反方向。3.4 實驗方法選取實例研究松弛因子和迭代方向c對結果的影響。四、實驗條件臺式計算機，Matlab軟件試驗

4、平臺。五、實驗步驟5.1 理論分析根據變分原理的定義，推導迭代形式的關鍵在于找到使x達到極小值的條件。為了使收斂最快，加入松弛因子，對某些矩陣用超松弛比完全松弛收斂快，具體見3.1節(jié)的分析。當下降方向c(k)取不同值時對結果影響不同。在一般松弛法中取c(k-1)=ei，每步迭代使二次函數x(k)在ei方向下降最多，其過程類似賽德爾迭代，一般可達到較快的收斂速度。當取c(k-1)=r(k-1)構成最優(yōu)斜量法，使x(k)沿在x(k)的梯度反向，此時可達到最快的下降速度。具體見3.2和3.3節(jié)的分析。5.2 算法設計為了具體研究松弛因子和和下降方向對迭代過程的影響，設計坐標松弛法和最優(yōu)斜量法的計算機

5、實現算法。坐標迭代算法： 輸入A, b，初始值x(0),松弛因子，容許誤差err，容許最大迭代次數maxN. 對i=1,2,n, 循環(huán)T = aii對j=1,2,i-1,循環(huán)al = al + A(i,j) * x(j,k+1);對j=1,2,n,循環(huán)au = au + A(i,j) * x(j,k); 迭代：對i=1,2,n,計算x(k+1)=x(k)+ w *( b(i) - al - au )/A(i,i); 若xk+1-x(k)err,輸出x，否則， 若k100764030221317296512最優(yōu)斜量算法中，當達到容許精度err時不同的松弛因子對應的迭代次數見表5-2。可見下降方向

6、改變了松弛因子與迭代次數的對應關系。最少迭代次數比坐標松弛的最少迭代次數多，且起伏不是很大。表5-1 最優(yōu)斜量算法松弛因子與迭代次數對應關系松弛因子0.20.40.60.81.01.21.41.61.81.24迭代次數n64433024444546476445六、實驗總結通過該實驗，從理論上討論與總結基于Rn中變分原理推出求解線性代數方程組迭代法的關鍵步驟以及從一般迭代法到按不同特征形成幾個特殊具體的迭代法的形成過程，分析了松弛因子與下降方向的影響；并用matlab編程實現了坐標松弛迭代和最優(yōu)斜量算法，通過實例研究驗證了松弛因子和下降方向對結果的影響。附錄1 實驗1代碼% filename:

7、RelaxationIteration.m% 實驗1 基于Rn中變分原理的迭代法的研究與實例分析% 實驗例子:4 3 0; 3 4 -1; 0 -1 4*x1; x2; x3 = 24; 30; -24;% 松弛因子取0.2,0.4,.,1.8,w0，其中w0是最優(yōu)迭代松弛因子，通過調用OptimalW(A)求得% 初始條件是x=1 1 1 ，控制最多迭代次數為100次，maxN =100; 容許誤差err =10(-5).% 調用Iterate(A,b,x0,w,err,maxN)實現坐標迭代并輸出結果% 調用Grade(A,b,x0,w,err,maxN)實現最優(yōu)斜量迭代并輸出結果clea

8、r;clc;% 系數矩陣A= 4 3 0; 3 4 -1; 0 -1 4;% 系數bb= 24 30 -24;% 初始條件x0=1 1 1;% 松弛因子 w w0=OptimalW(A);w = 0.2 0.4 0.6 0.8 1.0 1.2 1.4 1.6 1.8 w0;%容許誤差 errerr = 10(-5);% 最大迭代次數設為100次maxN = 100;%Iterate(A,b,x0,w,err,maxN);Grade(A,b,x0,w,err,maxN);%filename:Itirate.m%坐標松弛迭代函數function f=Iterate(A,b,x0,w,err,max

9、N)% 維數m,nm,n = size(A);% 對每個松弛因子迭代for h=1:length(w) x= x0; k=1; errMeetFlag = 0; % 迭代次數不大于maxN且誤差不小于err時一直迭代 while( k =1 for j=1:i-1 al = al + A(i,j) * x(j,k+1); end end for j=i:n au = au + A(i,j) * x(j,k); end x(i,k+1)=x(i,k)+ w(h) *( b(i) - al - au )/A(i,i); end if(normest(x(:,k+1) - x(:,k) err) e

10、rrMeetFlag = 1; end k=k+1; end % 輸出迭代過程值 disp(w=); disp(w(h); disp(steps=); disp(length(x(1,:)-1); disp( x(1) x(2) x(3); format long; disp(x);end%filename: Grade.m%最優(yōu)斜量法迭代函數function Grade(A,b,x0,w,err,maxN)% 維數m,nm,n = size(A);% 對每個松弛因子迭代for h=1:length(w) x= x0; k=1; errMeetFlag = 0; % 迭代次數不大于maxN且誤

11、差不小于err時一直迭代 while( k = maxN & errMeetFlag) % 對每次進行初始化x(:,j) y=x(:,k); r = b-A*y; alpha=dot(r,r)/dot(A*r,r); y=y+w(h)*alpha*r; x=x y; %檢查容許誤差 if(normest(x(:,k+1) - x(:,k) err) errMeetFlag = 1; end k=k+1; end % 輸出迭代過程值 disp(w=); disp(w(h); disp(steps=); disp(length(x(1,:)-1); disp( x(1) x(2) x(3); format long; disp(x);end