《数值分析第二章》PPT课件.ppt

1、2.1 Gauss消去法,高斯消元法步骤： (1) 首先将增广阵 A, b 化为上三角阵; (2) 用三角方程组，回代求解 .,解 (1) 化上三角方程组, , , , ,(2)回代过程. 得到同解方程组后,如下求解,从下向上逐步求解,把x3的值代入求x2,用x3, x2的值求x1,上三角方程组：,对应增广阵的变化,(-2)r1 + r3 r3,r2 + r3 r3,上三角阵,高斯消元法的基本思想,将原方程组逐次消去未知元， 变为与之同解的上三角方程组， 再回代求解 。,用矩阵语言叙述是，仅用行初等变换把增广阵约化为上三角阵，对上三角方程组，回代求解 。,高斯消元法的一般性叙述,根据下面的上三

2、角方程组,逐次回代求解 xk,(2.5),2.1.1 顺序Gauss消去法,在使用高斯消去法的过程中，仅对方程组做行倍加变换，就是顺序高斯消去法。,1.消元过程 对于 k =1,2,n -1 执行 (1)如果 ,则算法失效,停止计算;否则转(2) (2)对于 i = k +1,k +2,n 计算,算法如下：记,Mi k 行乘数,第 k 次消元后, 增广阵变为,2.回代过程,顺序高斯消去法求解n 元线性方程组的乘除运算总次数为,顺序高斯消去法计算过程中出现的 称为主元素. 出现 消元过程就进行不下去了.,即使 detA 0，也可能对某个 k n， 出现 . 下面的定理给出了避免出现这种情况的条件

3、。,定理2.1 顺序高斯消去法的前 n1 个主元 均不为零的充要条件是 Ax b 的系数矩阵 A 的前 n 1个顺序主子式,证 因为, 第 k 个顺序主子式 Dk 等于前 k 个主元之积!,例子,此式 解释,又第 k 个主元被顺序主子式所确定:,注解：方程组(2.1) 的系数矩阵 A 的 n 个顺序主子式 Dk 均不为零，保证了主元均不为零, 使顺序消去法得以进行。,但，当遇到某个主元的绝对值很小时，将使行乘数 -mik 的绝对值很大，则舍入误差的积累会很大，计算出的近似解会有很大的误差。,顺序高斯消去法的数值稳定性是没有保证的!,顺序主元消去法可能计算失败之例,例：单精度解方程组,用Gaus

4、sian Elimination计算：,8个,小主元 /* Small pivot element */可能导致计算失败。,大数吃小数!,2.1.2 列主元 Gauss 消去法,定义 使用高斯消去法的过程中，在第 k 次消元前，先对第 k 个增广阵 A(k), b(k) 做交换二行的变换，把 中绝对值最大的元素换到 (k, k) 位置，再消元。此方法叫列主元高斯消去法。其算法如下：记,1.消元过程 对于k =1,2,n -1执行 (1)选行号ik，使 (2)交换第 k 行与第 ik 行（中数值）。,(3)对于 i = k +1,k +2,n 计算,2.回代过程,注解：此算法中的 称为第 k 个

5、列主元素，它的值总要被换到位置 (k, k) 。,定理2.2 设方程组 (2.1) 的系数矩阵 A 非奇异，则用列主元素消去法求解方程组时，各个列主元素 均不为零。,证 设有一个列主元素 为零，当消元进行到第 r 次时，由行列式性质，容易知道，系数矩阵 A 的行列式有下面的形状:,矛盾于 A 非奇异。,评论：列主元素消去法，所需条件较少，仅仅要求方程组的系数矩阵 A 非奇异。 而且，对一般的方程组，它还具有良好的数值稳定性，其计算量与顺序消去法的计算量相当。,例1 在四位十进制的限制下，分别用 顺序消去法 与 列主元素消去法 求解下列方程组,解 用顺序消去法的消元过程：,回代后，得,(-1/0

6、.012)r1 + r2 r2 (-3200/0.012)r1 + r3 r3,完全失真 !,原方程组：,近似解：,-2.1278e+005,检验,列主元素,列主元素法的消元过程：,回代后，得,列主元素,由此看出，列主元法的精度明显高于顺序消去法 !,原方程组：,近似解：,检验,数学符号 x0,x1, , xm, 0 x,1x, , nx, , a x0 x1 xmb , f (x) a0 a1x amxm, a1 a2 ak a1, , am, L0 x, L1x, , Lnx, k=0,1, , n (x) , x0 n 20 a x b k 1, nm, q 0, q 1, (a) 0 n k 0 f (x)Ca, b (xj,yj),j=0,1,m, A, ARnn, b, bRn,A , ij ( f p*, f p*), , | x a | (a) 0.5 10m n, n k , a1 0,mZ, ARn n , | k | p 1,2, max p h (b a) / n , a, b n, (6.