《对线性方程组和矩阵特征值特征向量数值解法的研究》由会员分享，可在线阅读，更多相关《对线性方程组和矩阵特征值特征向量数值解法的研究（45页珍藏版）》请在金锄头文库上搜索。
1、 对线性方程组和矩阵特征值特征向量数值解法的研究摘 要：线性方程组数值解法主要包括直接法和迭代法，一般直接方法包括列主元Guass消去法，选主元的LU分解法，追赶法法等方法。对于迭代法主要包括共轭梯度法，GMRES法，Bicgstab法。迭代法适用于解决在实际中大量出现矩阵为稀疏的大型方程组。矩阵计算是科学与工程计算的核心，大部分科学与工程问题都要归结为一个矩阵计算问题，在大量的实际问题中，经常会碰到求矩阵特征值和特征向量的问题，这类问题统称为特征值问题。本文求解矩阵特征值和特征向量的方法包括Jacobi法，QR法，幂法和反幂法。本文主要针对以上提出的算法进行分析比较。关键词：列主元Guass
2、消去法; 选主元LU分解法; 共轭梯度法; GMRES法; Bicgstab法; 追赶法; Jacobi法; QR法; 幂法11 引言线性方程组是线性代数历史上的第一个分支，是线性代数许多思想的源头。许多科学和工程技术问题，都归结为求解线性方程组。比如，行列式和矩阵都产生于方程组的研究。线性方程组不但是最基本最重要的数学理论和研究工具，而且有广泛的应用。对于线性方程组的求解本文采用直接法和迭代法，其中直接法是经过有限次运算后可求得方程组精确解的方法(不计舍入误差)；迭代法是从解的某个近似值出发，通过构造一个无穷列去逼近精确解的方法（一般有限步内得不到精确解）。在实际应用中，特征值问题有着广泛的
3、应用背景，例如微分方程的刚性比和数值方法的稳定性；动力系统和结构系统的振动问题；电力系统的静态稳定问题等，实质上都是矩阵的特征值问题。幂法，Jacobi方法及QR方法是求矩阵特征值和特征向量的常用数值方法，它们都是造构造迭代产生的矩阵序列来达到目的的。本文采用C语言编写以上算法，并进行了算法间的比较，最后采用图表的方式分析所得到的结果。2 问题分析研究线性方程组主要解决下面三个问题：（1）方程组是否有解，即解的存在性问题；（2）若方程组有解，那么有多少解，解与解之间有什么关系，即解的结构问题；（3）解的求法。求解线性方程组的方法可以分为两大类：直接法和迭代法。直接法的特点是，运用此类方法求解线
4、性方程组时，如果计算过程没有舍入误差，那么经过有限次运算就能求出方程组的精确解。迭代法求解方程组就是构造一个无限的向量序列，使它的极限是方程组的解向量。即使计算过程是精确进行的，迭代法也不能通过有限次算术运算求得方程组的精确解，而只能逐步逼近它。因此，凡是迭代法都存在收敛性与精度控制的问题。迭代法常用于求解大型稀疏线性方程组。一般的，代数方法只适用于阶数较低的矩阵，当矩阵阶数较高时，用代数方法求矩阵的特征值和特征向量是极其困难的。本文主要采用三种方法，幂法、Jacobi法及QR分解法。3 算法及算法分析表1 求解线性方程组算法的比较算法适用范围计算复杂度优点不足列主元素高斯消去法中小型方程组具
5、有良好的数值稳定性存储量大选主元的LU分解法中小型方程组与三角分解相比，精度得到了提高要求矩阵为非奇异阵求解三对角线性方程组的追赶法中小型方程组计算量小；所占用的存储单元少；方法简单，算法稳定。有时可能导致求解不精确甚至求解失败。共轭梯度法稀疏矩阵；求解无约束优化问题存储量少，计算方便收敛速度一般而言要比BICGSTAB慢GMRES法解大规模线性方程组有较好的收敛特性高效性和稳定性运算量和存储空间需求量大BICGSTAB法大型稀疏矩阵收敛速度快，精度高，而且稳定性好存储量大表2 求矩阵特征值和特征向量算法的比较算法适用问题优点不足Jacobi法中小型矩阵收敛快；精度高；便于并行计算且算法稳定不
6、能有效地利用矩阵的各种特殊形状以节省工作量； n收敛速度减慢QR法中小型对称矩阵收敛快；精度高只适用于实对称矩阵幂法大型稀疏矩阵计算量小 只能求解矩阵按模最大的特征值； 收敛速度慢4 结果分析本文采用C语言在WIN-TC环境下编写了上述算法的程序，实现了对线性方程组、矩阵特征值和特征向量的求解，以进一步解决实际中的问题。4.1 直接法求解线性方程组的结果分析针对3种不同的算法，为便于分析比较，我们将输入同一个线性方程组，计算其结果。采用的方程组为： 此方程组的精确解舍入到4位有效数字是：，对于求解线性方程组的直接法和迭代法，程序采用C语言中的SWITCH语句，当手动输入系数矩阵和常数项后，界面
7、将提示选择求解线性方程组的方法（如图1所示）。表3为所选字符与求解方法的对应关系。图1 运行时的提示界面表3 字符与算法的对应关系字符算法程序中对应的函数0列主元Guass消去法gaussliezhuyuan(float amax_dimensionmax_dimension,float bmax_dimension,int n);1选主元LU分解法LU(float amax_dimensionmax_dimension,float bmax_dimension,int n);2三对角线性方程组的追赶法chased_method(float amax_dimensionmax_dimensio
8、n,float bmax_dimension,int n);图24为选择不同字符时求解线性方程组的运行结果。图2 列主元Guass消去法运行结果图3 选主元LU分解法运行结果图4 三对角线性方程组的追赶法运行结果本文将以表格的方式列出由各种算法计算的结果（见表4）。表4 不同算法的计算结果算法计算结果列主元Guass消去法0.8409-0.29970.01445选主元LU分解法0.8388-0.30190.01445三对角线性方程组的追赶法0.8304-0.27230.2165由表4可看出，列主元Gauss消去法的计算精度较高，数值稳定性比较好，但是它要求的存储量要大。采用三对角线性方程组的追
9、赶法所需的存储空间很小，计算量也大大的减小，局限性是只能针对三对角形式的线性方程组，对于上例所示的方程组，由于它不是三对角矩阵，因此得出的结果与精确解相比偏差较大，若改用三对角矩阵进行分析，可得出较精确的值。选主元LU分解法，与三角分解法相比，精度得到了提高。4.2 迭代法求解线性方程组的结果分析4.2.1共轭梯度法共轭梯度法是一个迭代方法，所以它适用于稀疏矩阵系统，因为这些系统对于象乔莱斯基分解这样的直接方法太大了。这种系统在数值求解偏微分方程时相当常见。 共梯度法也可以用于求解无约束优化问题。图5 共轭梯度法运行结果图5为采用共轭梯度法求解线性方程组的运行结果。共轭梯度法是介于最速下降法与
10、牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。 4.2.2 GMRES方法GMRES方法是几种常用的Krylov-subspace方法之一，是目前求解大型稀疏非对称方程组的一种常用方法。该方法具有较好的收敛特性，适合求解大规模问题边界元弹性问题所形成的稠密性非对称线性方程组，现实工程中得到越来越多的应用。输入方程组：取，迭代步长，误差，计算结果如5所示所示：表5共轭梯度法运算结果迭代次数绝对残差迭代结果126.141
11、40l.053135l.7857512.7015200.778414l.694174224.6926171.5412231.6117202.9547600.8807241.439404324.5096991.4269601.3352983.226840.9929061.5096054l0.56l2021.8616391.0649361.6188751.2457312.27370350.0000001.000000 2 0000001.0000002.0000001.00000分析表中数据可知当算法迭代到第三次时收敛速度加快，并在第五次迭代后的出精确解。GMRES算法的收敛效果首先取决于方程组系
12、数矩阵的实际分布情况因此我们可以通过对矩阵进行预处理来改善算法的收敛速度。对重新开始迭代步长的选择也是至关重要的，合适的m能够加速GMRES方法的收敛。过小则可能导致迭代的收敛失败过大则导致计算量的成倍增加及收敛速度减缓。另外对于迭代初始向量的选择对于加快算法收敛也有着重要的影响。4.2.3 BiCGSTAB法BICGSTAB法是用来求解非对称的线性方程组，它是Krylov子空间法。BICGSTAB法的收敛速度快，也可用于求解非线性方程组，可以看作是反复使用GMRES法的组合，精确度高。使用这种方法的目的就是要去除BICG方法中使用到来做矩阵-向量乘积以及让CGS中收敛结果不规则的情形变成较为
13、平滑。用来发展非对称线性方程组且避免CGS中非常规的收敛情况。图6 BICGSTAB法运行结果 图6为采用BICGSTAB法运行的结果。针对同一线性方程组对比GMRES方法运行的结果可以发现结果相同，但是二者的残余误差的精确度却不同，GMRES法的是2.598965e-016，而BICGSTAB法的是7.855179e-017。BICGSTAB收敛的速度一般而言要比CGS快，BICGSTAB可以解释为BICG以及反覆使用GMRES(1)的结合。最后产生一个够平滑的收敛结果的最小残向量，其存储空间要求较大。4.3 不同算法求矩阵特征值特征向量的结果分析求解特征值和特征向量主要是采用直接运行的方式
14、，各个算法相互独立。4.3.1 采用Jacobi法求解矩阵特征值和特征向量Jacobi法是求实对称矩阵全部特征值的一种有效方法。它不但能求出特征值，而且同时能求出特征向量，虽然和其他方法相比计算量大了一些，但它是一种可靠的方法，如果矩阵有较多的零元素，或者矩阵本身接近一个对角阵，那么利用Jacobi法更加显示其优越性。输入的矩阵为：允许误差。Jacobi法用平面旋转序列(Givens变换)把矩阵作正交相似变换化为对角矩阵，由于是实对称矩阵，变换的工作量会大大减少。不论实对称矩阵的特征值如何分布，经典Jacobi法总是收敛的，而且当阶数不太高时，收敛的速度还比较快 ，具有较强的数值稳定性。但Ja
15、cobi法不能有效的利用矩阵的各种特殊形状以节省工作量，而且在迭代过程中会破坏原矩阵的特殊形状。每迭代一次都会在非主对角线元素中寻找按模最大的元素，因此也比较费时间。收敛性分析：Jacobi法的收敛性较高，并且对舍入误差有较强的数值稳定性，因而求得的解精度较高，且所求的解的正交性较好。4.3.2 采用QR法求解矩阵特征值和特征向量QR方法是目前计算一般矩阵全部特征值问题的最有效方法之一。有着十分广泛的应用。运行结果为：（1）矩阵A经过拟上三角化后的矩阵：-8.827516758830e-001 -9.933136491826e-002 -1.103349285994e+000 -7.60044358
