计算方法 第3章 线性方程组数值解法.pptx

计算方法北京工业大学应用数理学院杨中华第三章线性方程组的数值解法线性方程组是应用最为广泛的数学模型,很多复杂问题中都含有线性方程组子问题,因此讨论线性方程组问题的求解很有必要,本章将讨论线性方程组的数值解法。线性方程组的一般形式: 记: 这里 A称为系数矩阵, x称为解向量, b称为右端项。??????????????????? nn nn nn nn nnbxaxaxa bxaxaxa bxaxaxa???????????? 2211 22 2 22 1 21 11 2 12 1 11b Ax?????????????????????????????????????????????? nn nn nn n nb b bbx x xxaaa aaa aaaA????????? 2 12 1 21 2 22 21 1 12 11,, () () 求解线性方程组问题的数值方法可分为两类: 直接解法和迭代解法。直接解法是通过有限次初等运算,求得其解,虽然直接解法的推导过程都是无误差的,但是由于计算机的运算都是有舍入误差的,所求的解其实是一个有误差的近似解。迭代解法则是从某个初始近似解出发,按照一个确定的迭代公式得到一个更好的近似解,反复迭代,直到求得一个满足精度要求的近似解。本章首先讨论线性方程组的直接解法然后再介绍迭代解法。 消去法 1. 顺序 Gauss 消去法首先回顾一下线性代数中所讲的线性方程组消去法过程,然后归纳出消去法的数值算法,请看如下的例子: 求解线性方程组解:求解线性方程组的第一阶段称为消元过程,其方法是第2个方程减去第 1个方程的 1/2 倍,第 3个方程减去第 1个方程的 2倍,得??????????????224 05 6242 321 321 321xxx xxx xxx 第3个方程减去第 2个方程的 7/3 倍,得???????????????? 10 27 363 6242 32 32 321xx xx xxx消去法???????????????3 12 363 6242 3 32 321x xx xxx这一过程就是消元过程,即把方程化为等价的上三角方程(对角线下变为 0)。第一个阶段完成后,进入第二个阶段,称为回代过程, 其方法是:先由第 3个方程解出,将代入第 2个方程解出,再将和代入第 1个方程解出也就解出所有的未知量。如下就是所求的解: 3x 3x 1x 2x 2x 3x4 1,2 3,4 1 321???xxx 归纳以上求解方法,求解线性方程组包括两个过程, 消元过程和回代过程。首先给出回代过程的算法,回代过程其实是一个特殊形式的方程组的求解方法,就是一个上三角线性方程组的求解方法,如: 消去法???????????????????????????????????nn nn kn kn kkkk kk nnkkkk nnkkkkbxa bxaxaxa bxaxaxaxa bxaxaxaxaxa ....... .......... .......... ... ..... .......... .......... .......... ... ... ... ... 11, 2211,22222 1111,112 12 1 11 () 第1步:根据第 n个方程解出,得消去法 nn nna bx?假如已经求出,代入第 k个方程得: 1,1 ,11?????? nn nnnnna xabx 1?nx nx nx第2步:根据已求出的和第 n -1个方程求,得到 11,,, ??knnxxx? kk nkj j kj kkaxabx/)( 1?????回代过程就是对实施这一公式,注意必须从后向前计算方可,所以此过程叫做回代过程。 1,2,,1,???nnk () 算法 上三角线性方程组的回代算法 0) [ 初始化] 设置上三角方程系数矩阵 A,右端项向量 b 1) [ 回代过程] 对于循环 ) 计算 ) 对于循环 ) 计算 2) [ 算法结束]消去法 kk kkaxx/? kkbx? j ijkkxaxx?? nkj,,1??? 1,2,,1,???nnk 再看 Gauss 消去法的消元过程,对于线性方程组的消去法本质上可看作将其增广矩阵用初等行变换化为梯形矩阵的过程。为清楚的表示每次消元前后系数矩阵和右端项的状态, 通常以表示系数矩阵和右端项,其元素分别记作,其中上标(k)表示在第 k次消元前的状态,其初始增广矩阵为: njiba ki k ij,,2,1,,, )()(????????????????????? nn nn nn nn nnbxaxaxa bxaxaxa bxaxaxa ... ... ..