基于Rn中变分原理的迭代法的研究与实例分析

1实验1基于Rn中变分原理的迭代法的研究与实例分析一、实验目的研究基于变分原理以及相应问题空间的特征来设计数值求解算法这一比较普遍的数值求解技术。二、实验内容1、从理论上讨论与总结基于Rn中变分原理推出求解线性代数方程组迭代法的关键步骤以及从一般迭代法到按不同特征形成几个特殊具体的迭代法的形成过程；2、分析松弛因子与下降方向的影响；3、按不同特征选择几个线性代数方程组求解示例进行算法设计；4、用Matlab进行程序设计与运行实验。三、实验原理、方法和手段3.1Rn中的变分原理设Ａ为一个n阶对称正定矩阵，b∈𝑅𝑛.则**()min()nxRAxbxx其中𝜑(𝑥)=(𝑥,𝐴𝑥)−2(𝑥,𝑏)该定理把求解𝐴𝑥=𝑏等价于将一个多元二次函数（也称泛函）极小化的问题。松弛法的任务是取向量序列{𝑥(𝑘)},使{𝜑(𝑥(𝑘))}收敛于𝜑(𝑥)的极小值。给定初值𝑥(0),选取𝑐(𝑘−1),求α使得𝜑(𝑥)在向量𝑥(𝑘)=𝑥(𝑘−1)+𝛼𝑐(𝑘−1)上达极小。分析可得最小的α为2𝛼𝑘−1=(𝑟(𝑘−1),𝑐(𝑘−1))/(𝐴𝑐(𝑘−1),𝑐(𝑘−1))为保证序列{𝜑(𝑥(𝑘))}从总体上收敛最快，令α=𝜔𝑘−1𝛼𝑘−1可得迭代格式𝑥(𝑘)=𝑥(𝑘−1)+𝜔𝑘−1𝛼𝑘−1𝑐(𝑘−1)当0𝜔𝑘−12时收敛。当𝜔𝑘取不同范围时对应的迭代可分为亚松弛0𝜔𝑘1完全松弛𝜔𝑘=1超松弛1𝜔𝑘2实践表明，对某些矩阵用超松弛迭代比完全松弛收敛快。3.2坐标松弛在一般松弛法中，取𝑐(𝑘−1)=𝑒𝑖,𝜔𝑘−1=𝜔𝑖则第i个分量的迭代格式为𝑥𝑖(𝑘)=𝑥𝑖(𝑘−1)+𝜔𝑖(𝑏𝑖−∑𝑎𝑖𝑗𝑥𝑗(𝑘)𝑖−1𝑗=1−∑𝑎𝑖𝑗𝑥𝑗(𝑘−1)𝑛𝑗=𝑖)/𝑎𝑖𝑖𝑖=(𝑘−1)(𝑚𝑜𝑑𝑛)+1,𝑘=1,2,…最佳松弛因子为𝜔𝑜𝑝𝑡=21+√1−[𝜌(𝐻𝐽)]2其中𝐻𝐽为雅克比迭代矩阵。3.3最优斜量法取𝑐(𝑘−1)=𝑟(𝑘−1)得最优斜量法迭代公式如下3𝑥(𝑘)=𝑥(𝑘−1)+𝜔𝑘−1𝛼𝑘−1𝑐(𝑘−1)𝛼𝑘−1=(𝑟(𝑘−1),𝑟(𝑘−1))/(𝐴𝑟(𝑘−1),𝑟(𝑘−1))𝑟(𝑘−1)=𝑏−𝐴𝑥(𝑘−1)可验证𝑔𝑟𝑎𝑑𝜑(𝑥)|𝑥(𝑘−1)=−2𝑟(𝑘−1)。即𝑟(𝑘−1)是𝜑(𝑥)在𝑥(𝑘−1)点梯度方向的反方向。3.4实验方法选取实例研究松弛因子ω和迭代方向𝑐对结果的影响。四、实验条件台式计算机，Matlab软件试验平台。五、实验步骤5.1理论分析根据变分原理的定义，推导迭代形式的关键在于找到使𝜑(𝑥)达到极小值的条件。为了使收敛最快，加入松弛因子ω，对某些矩阵用超松弛比完全松弛收敛快，具体见3.1节的分析。当下降方向𝑐(𝑘)取不同值时对结果影响不同。在一般松弛法中取𝑐(𝑘−1)=𝑒𝑖，每步迭代使二次函数𝜑(𝑥(𝑘))在𝑒𝑖方向下降最多，其过程类似赛德尔迭代，一般可达到较快的收敛速度。当取𝑐(𝑘−1)=𝑟(𝑘−1)构成最优斜量法，使𝜑(𝑥(𝑘))沿在𝑥(𝑘)的梯度反向，此时可达到最快的下降速度。具体见3.2和3.3节的分析。5.2算法设计为了具体研究松弛因子和和下降方向对迭代过程的影响，设计坐标松弛法和最优斜量法的计算机实现算法。坐标迭代算法：4①输入A,b，初始值𝑥(0),松弛因子ω，容许误差err，容许最大迭代次数maxN.②对i=1,2,…,n,循环T=aii对j=1,2,…,i-1,循环al=al+A(i,j)*x(j,k+1);对j=1,2,…,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);④若‖𝑥(𝑘+1)−𝑥(𝑘)‖𝑒𝑟𝑟,输出x，否则，⑤若kmaxN,k=k+1,转到③最优斜量算法：5.3实例选择与程序实现实例选择为课本P277例8.7.方程组为[43034−10−14][𝑥1𝑥2𝑥3]=[2430−24]取初值𝑥(0)=(111)𝑇,最大迭代次数maxN=100,容许误差err=10−5.分别使用坐标松弛法和最优斜量法进行迭代，选择松弛因子ω分别为0.2,1）给定000,nxRrbAx；50.4,…,1.8和最优松弛因子𝜔𝑜𝑝𝑡=1.24,输出不同松弛因子达到容许误差内时需要的迭代次数，以及每次迭代的x值。程序选择使用matlab代码实现，代码请见附录1.5.4结果分析坐标松弛算法中，当达到容许精度err时不同的松弛因子对应的迭代次数见表5-1.可见迭代次数在最优松弛因子处达到最小，表明此时收敛速度最快；松弛因子与最优松弛因子的距离越远，对应的迭代次数越多；总体来看，松弛因子在(1.0,1.5)区间时收敛速度比较理想。表5-1坐标松弛算法松弛因子与迭代次数对应关系松弛因子ω0.20.40.60.81.01.21.41.61.81.24迭代次数n100764030221317296512最优斜量算法中，当达到容许精度err时不同的松弛因子对应的迭代次数见表5-2。可见下降方向改变了松弛因子与迭代次数的对应关系。最少迭代次数比坐标松弛的最少迭代次数多，且起伏不是很大。表5-1最优斜量算法松弛因子与迭代次数对应关系松弛因子ω0.20.40.60.81.01.21.41.61.81.24迭代次数n64433024444546476445六、实验总结通过该实验，从理论上讨论与总结基于Rn中变分原理推出求解线性代数方程组迭代法的关键步骤以及从一般迭代法到按不同特征形成几个特殊具体的迭代法的形成过程，分析了松弛因子与下降方向的影响；并用matlab编程实现了坐标松弛迭代和最优斜量算法，通过实例研究验证了松弛因子和下降方向对结果的影响。6附录1实验1代码%filename:RelaxationIteration.m%实验1基于Rn中变分原理的迭代法的研究与实例分析%实验例子:[430;34-1;0-14]*[x1;x2;x3]=[24;30;-24];%松弛因子取0.2,0.4,...,1.8,w0，其中w0是最优迭代松弛因子，通过调用OptimalW(A)求得%初始条件是x=[111]'，控制最多迭代次数为100次，maxN=100;容许误差err=10^(-5).%调用Iterate(A,b,x0,w,err,maxN)实现坐标迭代并输出结果%调用Grade(A,b,x0,w,err,maxN)实现最优斜量迭代并输出结果clear;clc;%系数矩阵A=[430;34-1;0-14];%系数bb=[2430-24]';%初始条件x0=[111]';%松弛因子ww0=OptimalW(A);w=[0.20.40.60.81.01.21.41.61.8w0];%容许误差errerr=10^(-5);%最大迭代次数设为100次maxN=100;%Iterate(A,b,x0,w,err,maxN);Grade(A,b,x0,w,err,maxN);%filename:Itirate.m%坐标松弛迭代函数functionf=Iterate(A,b,x0,w,err,maxN)%维数[m,n][m,n]=size(A);%对每个松弛因子迭代forh=1:length(w)x=x0;7k=1;errMeetFlag=0;%迭代次数不大于maxN且误差不小于err时一直迭代while(k=maxN&&~errMeetFlag)%对每次进行初始化x(:,j)fori=1:nal=0;au=0;ifi-1=1forj=1:i-1al=al+A(i,j)*x(j,k+1);endendforj=i:nau=au+A(i,j)*x(j,k);endx(i,k+1)=x(i,k)+w(h)*(b(i)-al-au)/A(i,i);endif(normest(x(:,k+1)-x(:,k))err)errMeetFlag=1;endk=k+1;end%输出迭代过程值disp('w=');disp(w(h));disp('steps=');disp(length(x(1,:))-1);disp('x(1)x(2)x(3)');formatlong;disp(x');end%filename:Grade.m%最优斜量法迭代函数functionGrade(A,b,x0,w,err,maxN)%维数[m,n][m,n]=size(A);8%对每个松弛因子迭代forh=1:length(w)x=x0;k=1;errMeetFlag=0;%迭代次数不大于maxN且误差不小于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=[xy];%检查容许误差if(normest(x(:,k+1)-x(:,k))err)errMeetFlag=1;endk=k+1;end%输出迭代过程值disp('w=');disp(w(h));disp('steps=');disp(length(x(1,:))-1);disp('x(1)x(2)x(3)');formatlong;disp(x');end%filename:OptimalW.m%求取最佳迭代因子wopfunction[optW]=OptimalW(A)%求最优松弛因子%求雅克比迭代矩阵HD=tril(A)+triu(A)-A;H=inv(D)*(D-A);%d是特征值d=eig(H);maxd2=max(d.*d);optW=2/(1+sqrt(1-maxd2));