第三章 线性代数方程组的解法ppt课件.ppt

1,第三章 线性代数方程组的解法,序,本章主要讨论n阶线性代数方程组,的解法。,其矩阵形式为,其中,非奇异阵（即 ）,未知向量,右端向量（常数向量）,由克拉默（Cramer）法则知，上述方程组有唯一解，其解为：,2,但是这种计算方法在实际应用中对于高阶方程组却不能用，,如果用每秒计算一亿次的计算机计算也要算30多万年，,计算机上解线性方程组的数值方法大致可分为两种：,直接法（精确解法）：,迭代法：,通过某种极限过程去逐次逼近方程组的精确解的方法。,3,1 高斯消元法与选主元技巧,一、高斯消元法,1、三角形方程组,定义,系数矩阵是三角形矩阵的方程组，例如,当 时，方程组有唯一解.,求解过程可采用逆推方式，称之为回代过程（消元过程）。,2、高斯消元法（顺序消元法）,特点：,4,解,（消元过程用增广矩阵的行初等变换来表示）,第一次消元,第二次消元,然后回代，解得：,推至一般，,对线性代数方程组（*），,记,5, 消元过程, 当 时，,记,得,其中,这样，就得到了一个与原方程组 同解的方程组,6, 当 时，,再对 进行消元，又得,其中,这样，就得到了一个与原方程组 同解的方程组,7, 重复以上过程，,在完成第 次消元后，,当 时，,记,得,其中,第k次消元为：,8, 如此作下去，,当 时，,即, 回代过程,把上式自下向上回代，即得方程组的解。,综上所述，有,定理1,若约化主元素,计算公式如下:,这种解方程组的方法称为高斯消元法。,9,10, 回代求解, 消元计算,对 依次计算：,11,注,由上面公式可得，整个高斯消元法的消元过程中，,乘法运算次数为：,除法运算次数为：,回代过程中，乘法运算次数为：,除法运算次数为：,12,二、列主元消元法,序,若第k步中主元素,则消元过程就无法进行；,即使,用顺序消元法解(用具有舍入的4位浮点数进行计算)，,第一次消元,消元过程：,但若其绝对值相对较小(此时称 为小主元),13,回代求解：得,显然答案是错误的，,如果选用2.000作为约化主元素（即先交换两个方程的位置），,然后再进行消元，则有,交换两行,第一次消元,再回代求解，则得,由此，,这种消元法称为主元消元法。,按选取主元素的方法不同，主元素消去法可分为以下几种：,14,完全主元消元法：,列主元素消元法最为常用，其应用的步骤一般为：,第一步，,行主元消元法：,列主元消元法：,第一次消元后得增广矩阵,第二步，,15,依次进行下去，,经过 步选主元与消元，,解,顺序消去法,第一次消元,16,回代求解，得,列主元素消去法,交换两行,第一次消元,交换两行,17,第二次消元,回代求解，得,列主元素方法在解决一般线性方程组中有广泛的应用.,18,2 三角分解法,一、矩阵的三角分解,1. 定义,三角分解的常用形式为：,其中：L为下三角阵，U为上三角阵。,19,2. 矩阵的三角分解基本定理,定理2,设n 阶矩阵,若A的顺序主子式,即,则存在唯一的杜利特尔（Doolittle）分解,其中：L为单位下三角阵，U为非奇异的上三角阵。,20,21,22,23,24,25,26,27,注,二、杜利特尔（Doolittle）分解法（直接三角分解法）,设方程组 的系数矩阵的各阶顺序主子式都不等于零，,即,由定理2，有,存在唯一的杜利特尔（Doolittle）分解：,记为,28,第一步，,第二步，,求U的第一行元素和L的第一列元素。,显有,由,求U的第二行元素和L的第二列元素。,由,由,依次计算下去，,设U的前 行和L的前 列已经求出，,方法如下：,29,即,即,所以，有,30,注,杜利特尔（Doolittle）分解的计算特点为：,以上计算方法称为杜利特尔（Doolittle）分解。,U的元素按行求，L的元素按列求；,每次计算出的L、U的元素放入A的相应位置上即可。,这种记录方法称为紧凑格式。,31,令,则解 即等价于求解,计算公式如下：,32,综上，用杜利特尔分解解方程组 的方法如下：, 对A实现杜利特尔分解 ：, 先计算U的第一行元素，再计算L的第一列元素：, 当 时，求U的第k行和L的第k列的元素：,33,解,由,得,由,得,由,得,当k=2时，,34,所以，有,由,由,35,三、解三对角方程组的追赶法,1、三对角方程组,形如,的方程组称之为三对角线方程组，,简记为,2、三对角矩阵的三角分解,36,37,由矩阵乘法原理，可直接求出L和U中的各元素，,方法如下：,用L的第i 行乘以U 的第i-1 列,用L的第一行乘以U 的第一、二列,用L的第i 行乘以U 的第i 列,用L的第i 行乘以U 的第i+1列,由此，有,求出,即可完成A的三角分解。,38, 对A实现三角分解 ：,递推公式为：,由,39,得递推公式为：,得递推公式为：,由,40,解,由公式,得,41,42,3 向量与矩阵的范数,一、向量的范数, 非负性：, 齐次性：, 三角不等式：,对任意的实数 与向量X，都有,对任何向量X与Y，都有,定义,若存在X 的某一实数值函数,记为,满足,则称 为n 维空间 上X 的范数（模或长度）。,43,向量X 的“1”范数：,向量X 的“2”范数：,向量X 的 范数：,解,44,证,即,45,二、矩阵的范数,设矩阵, 非负性：,定义1,若存在A 的某一实数值函数,记为,满足, 齐次性：,对任意的实数 ，都有, 三角不等式：,对 都有, 矩阵乘法不等式：,对 都有,则称 为n 维空间 上A的的范数（模或长度）。,定义2,满足,成立，,则称 和 是相容的(或称向量和矩阵的范数具有相容性).,46,定义3,相应的定义一个矩阵A的实值函数,为矩阵A的范数，并称为矩阵A的算子范数。,（可以证明 满足定义1中的四条，此不证）。,设矩阵,其常用的算子范数有以下三种：,矩阵A 的“1”范数：,又称为列模或列范数,各列元素的绝对值的和的最大者,47,矩阵A 的 范数：,矩阵A 的“2”范数：,又称为谱模或谱范数,其中 是矩阵 的最大的特征值 ，,各行元素的绝对值的和的最大者,又称为行模或行范数,48,解,根据定义，有,的特征方程为,得,49,4 迭代法,一、迭代法及其有关概念,对于给定的方程组,其中A为n 阶非奇异阵，b为n元非零向量，,即,将其转化为等价的方程组,通过依次迭代计算,就得到一个由向量构成的序列,其中,设方程组的精确解为,50,若,即,即所得的向量序列收敛于方程组的解向量，,这就是求方程组的满足精度要求的近似解的迭代法，,其中,B,迭代矩阵,迭代公式或迭代过程,迭代序列,若迭代序列收敛，则称迭代法收敛，否则称迭代法发散。,显然，迭代法的等价形式是不唯一的，,以下讨论三种迭代法：,雅可比（Jacobi）迭代法、,高斯赛德尔（Gauss-Seidel）迭代法,超松弛迭代法（简称SOR迭代）,51,二、雅可比（ Jacobi ）迭代法,对于方程组：,其中A非奇异，且,将其改写成等价形式,即,52,构造相应的迭代公式:,即,53,就得到一个由向量构成的序列,其中,若,则对于给定的允许误差，只要k适当大，,就可作为方程组的满足精度要求的近似解。,这种求方程组的的近似解的方法称为雅可比（Jacobi）迭代法。,解,等价形式为,54,迭代公式为,逐次迭代，结果如下表：,取,55,其中,则方程组 可写成,所以，有,因为,所以D可逆，,所以，有,所以，得雅可比迭代法的矩阵形式的迭代公式：,56,三、高斯赛德尔迭代法,把雅可比迭代公式进行改进，即,即,这种迭代法就称为高斯赛德尔迭代法。,57,所以高斯赛德尔迭代法的矩阵形式的迭代公式为：,类似于雅可比迭代法，,把方程组 写成,有,解,等价形式为,58,逐次迭代，结果如下表：,取,对应的高斯赛德尔迭代公式为：,59,四、迭代法的收敛条件与误差估计,定义,即,定理4,矩阵A的谱半径不超过A的任何一种算子范数,证,设 为A的任一特征值，X为对应于 的A的特征向量，,即,此即说明A的任一特征值的模都不超过,所以,60,定理5,则,证,61,62,注, 式(2)、给出了迭代过程中的误差估计式。,63,定理6,或按列严格对角占优，即,64,注,定理8,65,解,66,由,即,得,所以,同理，得,所以,由定理8知，,用雅可比迭代法求解，迭代过程收敛；,用高斯赛德尔迭代法求解，迭代过程发散。,67,五、逐次超松弛迭代法（SOR迭代法）,SOR迭代法是高斯赛德尔迭代法一种改进。,高斯赛德尔迭代法为,即,68,把高斯赛德尔迭代公式改写成：,进而改写成：,这种迭代法称为逐次超松弛迭代法（简称为SOR迭代法），,69,SOR迭代法的矩阵形式为：,其中,称为逐次超松弛迭代矩阵，,定理9,证,70,定理10,71,解,迭代公式为,计算如下：,取,72,5 方程组的状态(与解的迭代改善),一、方程组的状态与矩阵的条件数,例9,其解为：,其解为：,其解为：,73, 仅b有扰动 时,设相应的方程组 的解为,为方程组解的扰动，则,即,由向量和矩阵范数的相容性，有,又,74,所以,此式说明解的相对误差不超过常数向量相对误差的 倍。,设相应的方程组 的解为,为方程组解的扰动，则,此式说明解的相对误差不超过系数矩阵相对误差的 倍。,75,定义1,称 为矩阵A的条件数，,记为,即,由矩阵的范数的类型知，通常使用的A的条件数有：,A的“1”条件数,A的“”条件数,A的“2”条件数,76,解,又,77,由,得,定义2,若 相对地很小，则称 为“良态”方程组。,78, 用消去法消元时出现小主元；, 系数行列式的绝对值相对较小；, 系数矩阵中元素数值相差很大且没有一定规律；, 出现了相对很大的解。,如果确实有病态方程组如何处理？,79,*5.3 近似解的迭代改善法,80,作业习题三,2，4，5，8,9,1011(2),12,1314(2).,