数值分析实验报告
一、 实验3.1 题目:
考虑线性方程组b Ax =,n n R A ?∈,n R b ∈,编制一个能自动选取主元,又能手动选取主元的求解线性代数方程组的Gauss 消去过程。
(1)取矩阵????????????
????=6816816816 A ,??
?
??
???
????????=1415157 b ,则方程有解()T x 1,,1,1*?=。取10=n 计算矩阵的条件数。分别用顺序Gauss 消元、列主元Gauss 消元和完全选主元Gauss 消元方法求解,结果如何?
(2)现选择程序中手动选取主元的功能,每步消去过程都选取模最小或按模尽可能小的元素作为主元进行消元,观察并记录计算结果,若每步消去过程总选取按模最大的元素作为主元,结果又如何?分析实验的结果。
(3)取矩阵阶数n=20或者更大,重复上述实验过程,观察记录并分析不同的问题及消去过程中选择不同的主元时计算结果的差异,说明主元素的选取在消去过程中的作用。
(4)选取其他你感兴趣的问题或者随机生成的矩阵,计算其条件数,重复上述实验,观察记录并分析实验的结果。
1. 算法介绍
首先,分析各种算法消去过程的计算公式, 顺序高斯消去法:
第k 步消去中,设增广矩阵B 中的元素()
0k kk a ≠(若等于零则可以判定系数
矩阵为奇异矩阵,停止计算),则对k 行以下各行计算()
()
,1,2,,k ik
ik k kk
a l i k k n a ==++,
分别用ik l -乘以增广矩阵B 的第k 行并加到第1,2,
,k k n ++行,
则可将增广矩阵B 中第k 列中()
k kk
a 以下的元素消为零;重复此方法,从第1步进行到第n-1步,则可以得到最终的增广矩阵,即()()(),n n n B A
b ??=?
?; 列主元高斯消去法:
第k 步消去中,在增广矩阵B 中的子方阵()()()()k k
kk
kn
k k nk
nn a a a a ???
??
?????
中,选取()k k i k a 使得()(k)
max k k
i k ik k i n
a a ≤≤=,当k i k ≠时,对B 中第k 行与第k i 行交换,然后按照和顺序消去
法相同的步骤进行。重复此方法,从第1步进行第n-1步,就可以得到最终的增广矩阵,即(
)
()()111,n n n B A b ??=?
?; 完全主元高斯消去法:
第k 步消去中,在增广矩阵B 中对应的子方阵()()()()k k
kk
kn
k k nk
nn a a a a ???
??
?????
中,选取()k k k i j a 使得()(k)
max k k k i j ij k i n
k j n
a a ≤≤≤≤=,若k i k ≠或k j k ≠,则对B 中第k 行与第k i 行、第k 列与第
k j 列交换,然后按照和顺序消去法相同的步骤进行即可。重复此方法,从第1步
进行到第n-1步,就可以得到最终的增广矩阵,即()
()()222,n n n B
A b ??=?
?; 接下来,分析回代过程求解的公式,容易看出,对上述任一种消元法,均有以下计算公式:
()()()
()
()1;
;1,2,
,1
n
n
n n nn
n
n n k kj
j
j k k n kk
b x a b a
x x k n n a
=+=-=
=--∑
2. 实验程序的设计
一、输入实验要求及初始条件;
二、计算系数矩阵A 的条件数及方程组的理论解; 三、对各不同方法编程计算,并输出最终计算结果。
3. 计算结果及分析
(1)
先计算系数矩阵的条件数,结果如下,
12()2557.500000,()1727.556025,()2557.50000cond A cond A cond A ∞===
可知系数矩阵的条件数较大,故此问题属于病态问题, b 或A 的扰动都可能引起解的较大误差;
采用顺序高斯消去法,计算结果为:
最终解为x=(1.0000, 1.0000, 1.0000, 1.0001, 0.9998, 1.0004, 0.9993, 1.0012, 0.9979, 1.0028)T
使用无穷数衡量误差,得到*X X ε∞
=-=2.0401e-14,可以发现,采用顺
序高斯消元法求得的解与精确解之间误差较小。通过进一步观察,可以发现,
按照顺序高斯消去法计算时,其选取的主元值和矩阵中其他元素大小相近,因
此顺序高斯消去法方式并没有对结果造成特别大的影响。 若采用列主元高斯消元法,则结果为:
最终解为x=(1.0000, 1.0000, 1.0000, 1.0000, 1.0000, 1.0000, 1.0000, 1.0000, 1.0000, 1.0000)T
同样使用无穷数衡量误差,有*X X ε∞
=-=0;
若使用完全主元高斯消元法,则结果为
最终解x=(1.0000, 1.0000, 1.0000, 1.0000, 1.0000, 1.0000, 1.0000, 1.0000, 1.0000, 1.0000)T
同样使用无穷数衡量误差,有*X X ε∞
=-=0;
(2)
若每步都选取模最小或尽可能小的元素为主元,则计算结果为
最终解x=(1.0000 1.0000 1.0000 1.0001 0.9998 1.0004 0.9993 1.0012 0.9979 1.0028)T
使用无穷数衡量误差,有*X X ε∞
=-为2.0401e-14;而完全主元消去法
的误差为*X X ε∞
=-=0。
从(1)和(2)的实验结果可以发现,列主元消去法和完全主元消去法都得到了精确解,而顺序高斯消去法和以模尽量小的元素为主元的消去法没有得到精确解。在后两种消去法中,由于程序计算时的舍入误差,对最终结果产生了一定的影响,但由于方程组的维度较低,并且元素之间相差不大,所以误差仍比较小。
为进一步分析,计算上述4种方法每步选取的主元数值,并列表进行比较,结果如下:
从上表可以发现,对这个方程组而言,顺序高斯消去选取的主元恰好事模尽量小的元素,而由于列主元和完全主元选取的元素为8,与4在数量级上差别小,所以计算过程中的累积误差也较小,最终4种方法的输出结果均较为精确。
在这里,具体解释一下顺序法与模最小法的计算结果完全一致的原因。该矩阵在消元过程中,每次选取主元的一列只有两个非零元素,对角线上的元素为4左右,而其正下方的元素为8,该列其余位置的元素均为0。在这样的情况下,默认的主元也就是该列最小的主元,因此两种方法所得到的计算结果是一致的。
理论上说,完全高斯消去法的误差最小,其次是列主元高斯消去法,而选取模最小的元素作为主元时的误差最大,但是由于方程组的特殊性(元素相差不大并且维度不高),这个理论现象在这里并没有充分体现出来。
(3)
n=时,重复上述实验过程,各种方法的计算结果如下所示,在这里,20
仍采用无穷数衡量绝对误差ε。
可以看出,此时列主元和完全主元的计算结果仍为精确值,而顺序高斯消去和模尽可能小方法仍然产生了一定的误差,并且两者的误差一致。与n=10时