线性方程组种数值解法

《线性方程组种数值解法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性方程组的四种数值解法(电子科技大学物理电子学院，四川成都610054)摘要：本文介绍了四种求解线性方程组的数值解法:雅克比迭代法、高斯赛德尔迭代法、高斯消去法和改进的平方根法的基本原理和算法流程，通过求解具体方程，对四种求解方法进行了对比。对于雅克比迭代法和高斯赛德尔迭代法，研究了两种算法对求解同一方程组的迭代效率差异，结果表明高斯赛德尔迭代法达到同样精度所需迭代次数较少。对于高斯消去法，通过选择列主元的方法提高算法的准确度，计算结果表明高斯消去法计算精确，且运算复杂度也不是很高。对于改进的平方根法，其运算复

2、杂度低，但对于给定的方程组有着严苛的要求。关键词：雅克比迭代法；高斯赛德尔迭代法；高斯消去法；改进的平方根法；线性方程组引言线性方程组的求解在日常生活和科研中有着极其重要的应用，但在实际运算中，当矩阵的维数较高时，用初等方法求解的计算复杂度随维数的增长非常快，因此，用数值方法求解线性方程组的重要性便显现出来。经典的求解线性方程组的方法一般分为两类：直接法和迭代法。前者例如高斯消去法,改进的平方根法等，后者的例子包括雅克比迭代法，高斯赛德尔迭代法等。这些方法的计算复杂度在可以接受的范围内，因此被广泛采用。一般来说，

3、直接法对于阶数比较低的方程组比较有效；而后者对于比较大的方程组更有效。在实际计算中，几十万甚至几百万个未知数的方程组并不少见。在这些情况下，迭代法有无可比拟的优势。另外，使用迭代法可以根据不同的精度要求选择终止时间，因此比较灵活。在问题特别大的时候，计算机内存可能无法容纳被操作的矩阵，这给直接法带来很大的挑战。而对于迭代法，则可以将矩阵的某一部分读入内存进行操作，然后再操作另外部分。本文使用上述四种算法求解对应的方程组，验证各种算法的精确度和计算速度。1算法介绍1.1雅克比迭代法1.1.1算法理论设线性方程组(1

4、)10/10的系数矩阵A可逆且主对角元素均不为零,令并将A分解成(2)从而(1)可写成令其中.(3)以B1为迭代矩阵的迭代法(公式)(4)称为雅克比(Jacobi)迭代法(公式),用向量的分量来表示,(4)为(5)其中为初始向量.1.1.2算法描述1给定迭代初始向量X0以及误差要求delta2根据雅克比迭代公式计算出下一组向量3判断X是否满足误差要求，即

5、

6、Xk+1–Xk

7、

8、

9、迭代公式可知,在迭代的每一步计算过程中是用的全部分量来计算的所有分量,显然在计算第i个分量时,已经计算出的最新分量没有被利用，从直观上看,最新计算出的分量可能比旧的分量要好些.因此，对这些最新计算出来的第次近似的分量加以利用,就得到所谓解方程组的高斯—塞德尔（Gauss-Seidel）迭代法.把矩阵A分解成(6)其中,分别为的主对角元除外的下三角和上三角部分,于是,方程组(1)便可以写成即其中(7)以为迭代矩阵构成的迭代法(公式)(8)称为高斯—塞德尔迭代法(公式),用变量表示的形式为(9)1.2.2算法描述1给

10、定迭代初始向量X0以及误差要求delta2根据高斯赛德尔迭代公式计算出下一组向量10/103判断X是否满足误差要求，即

11、

12、Xk+1–Xk

13、

14、

15、为阶梯矩阵的过程中可以使用选择列主元的方式减小误差。1.3.2算法描述以4阶为例：第1步消元——在增广矩阵（A，b）第一列中找到绝对值最大的元素，将其所在行与第一行交换，再对（A，b）做初等行变换使原方程组转化为如下形式：第2步消元——在增广矩阵（A，b）中的第二列中（从第二行开始）找到绝对值最大的元素，将其所在行与第二行交换，再对（A，b）做初等行变换使原方程组转化为：10/10第3步消元——在增广矩阵（A，b）中的第三列中（从第三行开始）找到绝对值最大的元素，将其所在行与第二行交换，再对（A，b）做初等行变换

16、使原方程组转化为：按x4àx3àx2àx1的顺序回代求解出方程组的解1.4改进的平方根法1.4.1算法理论当方程的系数矩阵为对称正定时，可以直接做高斯消去法。也就是说对称阵正定矩阵保证能直接作LU分解。由LU分解公式：uli=ali(i=1,2,3,…,n)lil=ail/all(i=1,2,3,…,n)因为A对称：ail=ali(i=1,2,3,…,n)所以：lil=a