第二章解线性代数方程组 的直接方法 21高斯( Gauss消去法 22主元素法 23直接三角分解法 2.4追赶法 25平方根法与改进的平方根法 2.6误差分析 西华师范大学 《计算方法》 数学与信息学院
2.1问题概述 2.1.1问题提出 线性代数方程组 aux t a 1242 INN b a21x1+a2x2+…+a2xN=b2 aM11+aM2x2+…+aMxN 用矩阵形式表示: Ax= b A n x 2-3 系数矩阵 未知向量右顶端 西华师范大学 《计算方法》 数学与信息学院
当M-N时,如果A非奇异,则方程组 (2-1)存在唯一解。根据 Cramer法则, 方程组的解可以表示为: det(a) X (i=1,2 12 det(a) n(1+ li, 2 其中4,2…4n是1.2n的不同排 列。根据上述行列式的计算方法:每个n 阶行列式需要做(n-1n!次乘法 计算一个n阶方程组需要n+1个行列式 因此总共需要(n+1)(n-1)n!次乘法和n次除 法。 西华师范大学 《计算方法》 数学与信息学院
!"#$ % &'(%)*+ ,- .(%)/01 23 *+-. /0-(%) 4567/0 23829
当n=25,则 N≈9678995066×1027 其计算量非常之大,用计算机来做也是 望洋兴叹。 求解线性代数方程组的方法可以分为 两类: 1.直接法:就是在不考虑舍入误差的 情况下,经过有限步的四则运算就可以 求出方程组的准确解的方法。 2.迭代法:就是用某种极限过程去逼 近方程组的准确解的方法。也就是先给 出一个解的初始近似值,然后按照一定 的法则求出解的更加准确的近似值的方 法 西华师范大学 《计算方法》 4 数学与信息学院
!"#$% &'( ) *+!(,-./01234 56789:;,"# ? @A ! B C!(,DEF;9GH I @A !,JK ?LM NOIPQRSTULV !? WX@A IPQ !
2.1高斯( Gauss)消元法 The technique for solving systems of linear algebraic equations that we shall describe in this section was developed by Carl Friedrich Gauss and was first published in his Theoria motus corporum coelestium in sectionibus conics solem bientium(1809) 西华师范大学 《计算方法》 数学与信息学院
!"!#$%&'(')*#+(,( ('& )#)+-#"$%#'(!.(!)) ("#-#!#(("#'.(*)'/-, )0##"!1%(( .(&#(/%-)#(! #!#( 2 !'# '%( "'/'% "')(#% # ("#'#-%( "'#"#( (') -##% 3
为了说明高斯消元法的思想,我们 首先看一个例子 例:求解以下线性方程组: x1+2x+3x2=2 2x1+3x2+4x3=3 3x1+4xn2+4x2=3 西华师范大学 《计算方法》 数学与信息学院
!
第1步:将第一个方程保持不 变,首先,用一2乘以第1个 方程加到第2个方程上,再用 2乘以第1个方程加到第3 个方程上,得到等价方程组: x1+2x2+3x3=2 1x2-2x 2x,-5X2=-3 西华师范大学 《计算方法》 数学与信息学院
"#$%" &'( ) *+,-"# ./", 0 1* +,-"# ./"2 0 3/45 !
第2步:将第一个和第二个方程 保持不变,然后用一2乘以第2 个方程加到第3个方程上,消去 第3个方程中的x2,得到等价 方程组: x1+2x2+3x3=2 1x-2 3 观察发现:新的方程组的系数矩阵 是一个上三角矩阵。 西华师范大学 《计算方法》 数学与信息学院
",$%"6"7 &'() 89*+,-", ./"2 0 : "2 ; 3/45 ! ?@ ! ABCD E0FGCD
这样,可以从最后一个方程开始 逐个回代求解: 3=1,x2=-1,x1=1 西华师范大学 《计算方法》 数学与信息学院
HI JKL9 MN OPQ
以上求解的思想是:首先逐次消去 变量,将原方程组转化为同解的上 三角方程组,这个过程称为消元过 程;然后按照与方程相反的顺序求 解该上三角方程组,这个过程称为 回代过程 称为高斯消元法。 (Gauss Elimination) 西华师范大学 《计算方法》 数学与信息学院
0 EOR: )S %T !UVW 0 FG ! HX YX Z89[\] ^_ `a b0FG ! HX Y PQX ++Y 1%((4)# ##'