数值分析第5章1-3节

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第5章 解线性方程组的直接方法,1,5.1,引言与预备知识,引言,线性方程组的数值解法一般有两类：,1. 直接法,经过有限步算术运算，可求得方程组精确解的方法(若,计算过程中没有舍入误差).,但实际计算中由于舍入误差的存在和影响，这种方法也只能求得线性方程组的近似解.,2,2. 迭代法,是用某种极限过程去逐步逼近线性方程组精确解的方法.,3,向量和矩阵,用 表示全部 实矩阵的向量空间， 表,示全部 复矩阵的向量空间.,这种实数排成的矩形表，称为 行 列矩阵.,称为 维列向量.,4,其中 为 的第 列.,其中 为 的第 行.,也可写成行向量的形式,写成列向量的形式,5,(5) 单位矩阵,矩阵的基本运算：,(1) 矩阵加法,(2) 矩阵与标量的乘法,(3) 矩阵与矩阵乘法,(4) 转置矩阵,6,(6) 非奇异矩阵,设,如果 存在，,则称 为非奇异矩阵.,如果 均为非奇异矩阵，,其中,如果,则称 是,的逆矩阵，,记为,且,则,(7) 矩阵的行列式,设,则 的行列式可按任一行(或列)展开，,7,其中 为 的代数余子式，,行列式性质：,即,的余子式.,为元素,8,特殊矩阵,设,(1) 对角矩阵,(2) 三对角矩阵,(3) 上三角矩阵,(4) 上海森伯格（,Hessenberg,）阵,(5) 对称矩阵,9,(6) 埃尔米特矩阵,(7) 对称正定矩阵,(8) 正交矩阵,(9) 酉矩阵,(10) 初等置换阵,由单位矩阵 交换第 行与第 行(或交换第 列与第 列)，得到的矩阵记为 ,且,10,(11) 置换阵,定理1,设 ，,(1) 对任何 方程组 有惟一解.,（为交换 第 行与第 行得到的矩阵）；,（为交换 第 列与第 列得到的矩阵）；,由初等置换阵的乘积得到的矩阵.,则下述命题等价：,(2) 齐次方程组 只有惟一解 .,(4) 存在.,(5) 的秩,(3),11,定理2,设 为对称正定阵，则,(1) 为非奇异矩阵，且 亦是对称正定阵.,(2) 记 为 的顺序主子阵，则,亦是对称正定矩阵，,其中,(3) 的特征值,(4) 的顺序主子式都大于零，即,12,定理3,设 为对称矩阵.,或 的特征值,定理4,(,Jordan,标准型),设 为 阶矩阵，则存在一个,非奇异矩阵 使得,如果,则 为,对称正定阵.,13,其中,为若当（,Jordan,）块.,(1) 当 的若当标准型中所有若当块 均为一阶时，,此标准型变成对角矩阵.,14,(2) 如果 的特征值各不相同，则其若当标准型必为,对角阵,15,5.2,高斯消去法,16,高斯消去法,设有线性方程组,（2.1）,或写为矩阵形式,17,简记为,例1,解,消去(2.4)中的未知数 得到,将方程(2.2)乘上 加到方程(2.4)上去，,第2步.,用消去法解方程组,第1步.,将方程(2.3)加到方程(2.5)上去，消去方程,(2.5)中的未知数,18,得到与原方程组等价的三角形方程组,显然，方程组(2.6)是容易求解的，解为,上述过程相当于,19,其中用 表示矩阵的第 行.,由此看出，用消去法解方程组的,基本思想,是用逐次消,去未知数的方法把原方程组 化为与其,等价的,三角,形方程组，而求解三角形方程组可用回代的方法.,上述过程就是用行的初等变换将原方程组系数矩阵化,为简单形式(上三角矩阵)，从而将求解原方程组(2.1)的,问题转化为求解简单方程组的问题.,20,或者说，对系数矩阵 施行一些左变换(用一些简单矩,阵)将其约化为上三角矩阵.,下面讨论求解一般线性方程组的高斯消去法.,将(2.1)记为,(1) 第1步,设 首先计算乘数,（2.1）,其中,用 乘(2.1)的第一个方程，加到第 个方程上，,消去(2.1)的从第2个方程到第 个方程中的未知数,21,得到与(2.1),等价的,方程组,（2.7）,简记为,其中 的元素计算公式为,22,(2) 第 次消元,设上述第1步，第 步消元过程计算已经完成，,（2.8）,即已计算好与(2.1),等价的,方程组,简记为,23,设 计算乘数,加到第 个方程,用 乘(2.8)的第 个方程，,消去从第 个方程到第 个方程中的未知数 得到与,元素的计算公式为,显然 中从第1行到第 行与 相同.,(2.1),等价的,方程组,(2.9),24,(3) 继续上述过程，且设,直到完成第 步消元计算.,最后得到,与原方程组等价的,简单方程组,其中 为上梯形.,特别当 时，,与原方程组等价的,方程组为,即,（2.10）,25,如果 是非奇异矩阵，且,由(2.1)约化为(2.10)的过程称为,消元过程,.,求解三角形方程组(2.10)，得到求解公式,（2.11）,(2.10)的求解过程(2.11)称为,回代,.,如果 由于 为非奇异矩阵，所以 的第一列一定有元素不等于零.,26,例如 于是交换两行元素(即 ），将,调到(1,1)位置，然后进行消元计算，这时 右下角矩阵,为 阶非奇异矩阵.,继续这过程，高斯消去法照样可进行计算.,27,定理5,设 其中,(1) 如果,将 约化为,等价的三角形方程组,(2.10).,则可通过高斯消去法,(a) 消元计算,（2.10）,且计算公式如下：,28,(b) 回代计算,(2) 如果 为非奇异矩阵，则可通过高斯消去法(及交,换两行的初等变换)将方程组 约化为(2.10).,（2.10）,29,算法1,(高斯算法),对于,(1) 如果 则计算停止,(2) 对于,(a),(b) 对于,本算法用高斯方法将 约化为上梯形，且,覆盖 ，乘数 覆盖 .,设,如果,30,当 时，总共大约需要 次乘法运算.,数 称为约化的,主元素,.,算法2,(回代算法),上三角阵，,设 其中 为非奇异,本算法计算 的解.,对于,(1),算法1第 步需要作 次除法， 次乘法，因此，本算法(从第1步到第 步消元计算总的计算量)大约需要 次乘法(对相当大的 ).,31,(2) 对于,(3),这个算法需要 乘除法运算.,高斯消去法对于某些简单的矩阵可能会失败，,由此，需要对算法1进行修改，,例如,在什么条件下才能保证,首先需要研究原来的矩阵,32,定理6,约化的主元素 的充要条件,是矩阵 的顺序主子式,即,（2.12）,证明,显然，当 时，定理6成立.,现设定理6充分性对 是成立的，求证定理6充分性对 亦成立.,首先利用归纳法证明定理6的充分性.,33,设,可用高斯消去法将 约化到 ，,且有,于是由归纳法假设有,即,34,（2.13）,由设,定理6充分性对 亦成立.,显然，由假设,利用(2.13)式，,则有,利用(2.13)式亦可,推出,35,推论,如果 的顺序主子式,则,36,于是对(2.1)施行第一次消元后化为(2.7)，,矩阵的三角分解,下面借助矩阵理论进一步对消去法作些分析，从而建,立高斯消去法与矩阵因式分解的关系.,设(2.1)的系数矩阵 的各顺序主子式均不为零.,由于对 施行行的初等变换相当于用初等矩阵左乘 ，,这时 化为,化为,即,37,其中,一般第 步消元，,化为 ,化为 ，,相当于,其中,38,重复这过程，最后得到,（2.14）,记上三角矩阵 为 ，由(2.14)得到,39,其中,为单位下三角矩阵.,这就是说，高斯消去法实质上产生了一个将 分解为,两个三角矩阵相乘的因式分解，于是得到如下重要定理，,它在解方程组的直接法中起着重要作用.,40,定理7,设 为 阶矩阵，,证明,现在在 为非奇异矩阵的假定下证明惟一性，,设,其中 为单位下三角矩阵， 为上三角矩阵.,(矩阵的,LU,分解),如果 的,顺序主子式,则 可分解为一个单位,下三角矩阵 和一个上三角矩阵 的乘积，,且这种分解是,惟一的.,根据以上高斯消去法的矩阵分析，存在性已得证，,41,上式右边为上三角矩阵，左边为单位下三角矩阵，从而上式,两边都必须等于单位矩阵，,例2,由高斯消去法，,由于 存在，故,故 惟一性得证.,对于例1，系数矩阵,故,42,43,例3,5.3,高斯主元素消去法,由高斯消去法知道，在消元过程中可能出现,即使主元素 但很小时，用其作除数，会导致其他元素数量级的严重增长和舍入误差的扩散，最后也使得计算解不可靠.,这时消去法将无法进行；,求解方程组,44,用4位浮点数进行计算.,解法1,用高斯消去法,精确解舍入到4位有效数字为,45,计算解为,显然计算解是一个很坏的结果，不能作为方程组的近似解.,其原因是我们在消元计算时用了小主元 0.001，使得约化后的方程组元素数量级大大增长，经再舍入使得在计算(3,3)元素时发生了严重的相消情况，因此经消元后得到的三角形方程组就不准确了.,46,解法2,交换行，避免绝对值小的主元作除数.,47,得计算解为,这个例子告诉我们，在采用高斯消去法解方程组时，,小主元可能产生麻烦，故应避免采用绝对值小的主元素,对一般矩阵来说，最好每一步选取系数矩阵(或消元后,的低阶矩阵)中绝对值最大的元素作为主元素，以使高斯消,去法具有较好的数值稳定性. 这就是,全主元素消去法,.,在选主元时要花费较多机器时间，目前主要使用的是,列主元消去法.,48,本节主要介绍列主元消去法，并假定(2.1)的 为非奇异的.,49,列主元素消去法,设方程组(2.1)的增广矩阵为,首先在 的第一列中选取绝对值最大的元素作为主元素，,例如,50,重复上述过程，,然后交换 的第1行与第 行，经第1次消元计算得,约化为,设已完成第 步的选主元素，交换两行,及消元计算，,51,其中 的元素仍记为 , 的元素仍记为 .,第 步选主元素(在 右下角方阵的第1列内选)，,即确定 ，使,交换 第 行与 行的元素，再进行消元计算，,最后将原方程组化为,52,回代求解,算法3,(列主元素消去法),设 . 本算法用具有行交换的列主元素消去法，,消元结果冲掉 ，乘数 冲掉 ，计算解 冲掉常数项,行列式存放在 中.,1.,53,2. 对于,(1) 按列选主元,(2) 如果 ，则计算停止,(3) 如果 则转(4),交换行：,(4) 消元计算,对于,54,(a),(b) 对于,(c),(5),3. 如果 ，则计算停止,4. 回代求解,55,5.,例3的解法2用的就是列主元素消去法.,列主元素消去法也可用矩阵运算描述：,（3.1）,其中 的元素满足 是初等置,换阵.,56,利用(3.1)得到,则有,若记,考虑 时的 .,（3.2）,（3.1）,57,为单位下三角阵，其元素的绝对值不超过1.,记,由(3.2)得到,其中 为排列矩阵， 为单位下三角阵， 为上三角阵.,其中,58,这说明对(2.1)应用列主元素消去法相当于对 先,进行一系列行交换后对 再应用高斯消去法.,定理8,如果 为非奇异矩阵，,则存在排列矩阵 使,其中 为单位下三角阵， 为上三角阵.,编程时， 的元素存放在数组 的下三角部分， 的元,素存放在 的上三角部分，由记录主行的整型数组 可,知 的情况.,而在实际计算中只能在计算过程中做行的交换.,(列主元素的三角分解定理),59,高斯-若当消去法,高斯消去法中，若同时消去对角线下方和上方的元素，,设用高斯-若当消去法已完成 步， 化为等价,方程组 ，其中,这种方法称为,高斯-若当,(,Gauss-Jordan,),消去法,.,60,在第 步计算时 对上述矩阵第 行的上、下都进行消元.,1. 按列选主元素，即确定 使,2. 换行(当 时)交换 第 行与第 行元素.,3. 计算乘数,( 可保存在存放 的单元中).,61,5. 计算主行,上述过程结束后有,4. 消元计算,62,用高斯-若当方法将 约化为单位矩阵，计算解就在,常数项位置得到，用不着回代求解，计算量大约需要,次乘除法，比高斯消去法大，但用高斯-若当方法求矩阵,的逆矩阵还是比较合适的.,定理9,设 为非奇异矩阵，,方程组 的增广矩阵为 .,如果对 应,用高斯-若当方法化为 ，,则 .,事实上，求 的逆矩阵 ，即求 阶矩阵 ，,其中 为单位矩阵.,(高斯-若当法求逆矩阵),使,63,于是求解 等价于求解 个方程组,可用高斯-若当方法求解,将 按列分块,64,例4,的逆矩阵.,解,用高斯-若当方法求,65,且,66,为了节省内存单元，可不必存放单位矩阵，,经消元计算，最后再调整一下列就可在 的位置得到,.,注意第 步消元时，由 的第 列,计算,且冲掉,存放在 的第二列位置，,存放在 的,存放在,的第1列，,第3列.,67,在 位置最后得到矩阵 (其中 为排列阵)的,逆矩阵 ，,于是,68,