基于MATLAB地科学计算—线性方程组.doc

科学计算—理论、方法
及其基于MATLAB的程序实现与分析
三、解线性方程组(线性矩阵方程)
解线性方程组是科学计算中最常见的问题。所说的“最常见”有两方面的含义:
问题的本身是求解线性方程组;
许多问题的求解需要或归结为线性方程组的求解。
关于线性方程组
(1)
其求解方法有两类:
直接法:高斯消去法(Gaussian Elimination);
间接法:各种迭代法(Iteration)。
1、高斯消去法
引例
考虑如下(梯形)线性方程组:
高斯消去法的求解思路:把一般的线性方程组(1)化成(上或下)梯形的形式。
2)高斯消去法——示例
考虑如下线性方程组:
第一个方程的两端乘加到第二个方程的两端,第一个方程的两端乘
-1加到第三个方程的两端,得
2) 第二个方程的两端乘加到第三个方程的两端,得
从上述方程组的第三个方程依此求解,得
3)高斯消去法的不足及其改进——高斯(全、列)主元素消去法
在上例中,由于建模、计算等原因,,实际求解的方程组为
注:数值稳定的算法
高斯列主元素消去法就是在消元的每一步选取(列)主元素—一列中绝对值最大的元取做主元素,高斯列主元素消去法是数值稳定的方法。
列主元素消去法的基本思想:在每轮消元之前,选列主元素(绝对值最大的元素),使乘数.
列主元素消去法的步骤:设已经完成第1步到第步的按列选主元、交换两行、消元计算,得到矩阵
.
第步计算如下:对于,
(1) 选列主元素,即确定使;
(2) 如果,则方程组解不唯一,或者接近奇异矩阵,停止运算;
(3) 如果,则交换第行与第行元素;
(4) 消元计算:

(5) 回代计算:
完全主元素消去法即是每次选主元时,依次按行、列选取绝对值最大的元素作为主元素,然后交换两行、两列,再进行消元计算.
完全主元素消去法的步骤:设已经完成第1步到第步的选主元、交换行和列、消元计算,得到矩阵
.
第步计算选主元素的范围为,即确定使.
第步计算如下:对于,
(1) 选主元素,即确定使;
(2) 如果,则方程组解不唯一,或者接近奇异矩阵,停止运算;
(3) 如果,则交换第行与第行元素;如果,则交换第列与第列元素;
(4) 消元计算:

(5) 回代求解.
【注】完全主元消去法是解低阶稠密矩阵方程组的有效方法,但完全主元消去法解方程组,在选主元素时要化费较多的计算机时间,行主元消去法与列主元消去法运算量大体相同,实际计算时,用列主元消去法即可满足一定的精度要求.
对同一数值问题,用不同的计算方法,,如果计算过程中舍入误差能得到控制,对计算结果影响较小,则称此算法是数值稳定的;否则,如果计算过程中舍入误差增长迅速,计算结果受舍入误差影响较大,,我们解数值问题时,应选择和使用数值稳定的算法,否则如果使用数值不稳定的算法,就可能导致计算失败.
4)高斯列主元素消去法的MATLAB实现:,意为.
例
open LinearEquiation02
LinearEquiation02
一个典型的例子: Hilbert矩阵:
注: 非奇异矩阵的条件数:
5)LU分解(LU Factorization)(高斯消去法、Doolittle分解)
高斯消去法的消元过程,从代数运算的角度看就是用一个下三角矩阵左乘方程组的系数矩阵A,且乘积的结果为上三角矩阵,即
(2)
.
.
第一步:利用A的第一行、第一列元素确定U的第一行、,
,
,
得到
,. ()
设已经计算出U的第1至r -1行元素,L的第1至r -1列元素,现在要计算U的第r行元素及L的第r列元素.
第r步:利用A的第r行、第r列剩下的元素确定U的第r行、,有
,
得U的第r行元素为
. ()
由
,
得
. ()
例5 用LU分解法求解方程组
.
解对系数矩阵A进行LU分解,
.
由,有.
,.
因此
.
解方程组,得.
解方程组,得.
6) LU 分解的MATLAB实现:或
例
A=rand(5);
[L,U,P]=lu(A)
A=rand(5);
[L,U,P]=lu(A)
L=P\L
当是主对角占优的三对角矩阵时,基于Doolittle分解可得到解这类方程组的追赶法。
2、Chol