数值分析第5章4-5节.ppt

《数值分析第5章4-5节.ppt》由会员分享，可在线阅读，更多相关《数值分析第5章4-5节.ppt（65页珍藏版）》请在三一办公上搜索。

1、1,5.4 矩阵三角分解法,直接三角分解法,将高斯消去法改写为紧凑形式，可以直接从矩阵 的元素得到计算 元素的递推公式，而不需任何中间步骤，,一旦实现了矩阵 的 分解，那么求解 的问题就等价于求解两个三角形方程组,求,求,这就是直接三角分解法.,2,1.不选主元的三角分解法,设 为非奇异矩阵，且有分解式,（4.1）,其中 为单位下三角阵，为上三角阵，即,的元素可以由 步直接计算定出，其中第 步定出 的第 行和 的第 列元素.,3,设已经定出 的第1行到第 行元素与 的第1列到第 列元素.,由(4.1)有,由(4.1)，利用等式两边元素比较及当 时，,有,故,4,又由(4.1)有,用直接三角分解

2、法解(要求 的所有顺序主子式都不为零)的计算公式.,计算 的第 行和 的第 列元素,5,求解 的计算公式：,（4.4）,（4.5）,6,例5,解,用直接三角分解法解,用分解公式(4.2)(4.3)计算,7,按(4.4)求解,从而,得,求解,得,8,当 计算好后 就不用了，故可将 仍存放在 的相应位置.,例如,最后在存放 的数组中得到 的元素.,直接分解法大约需要 次乘除法，和高斯消去法计算量基本相同.,再考虑存储问题,9,如果已经有了 的 分解，则求解具有相同系数的方程组 是相当方便的，每解一个方程组 仅需要增加 次乘除法运算.,矩阵 的分解公式(4.2)，(4.3)又称为杜利特尔分解.,2.

3、选主元的三角分解法,从直接三角分解公式可看出当 时计算将中断，,或者当 绝对值很小时，按分解公式计算可能引起舍入误差的累积.,如果 非奇异，可通过交换 的行实现矩阵 的 分解.,10,采用与列主元消去法类似的方法，将直接三角分解法修改为(部分)选主元的三角分解法.,设第 步分解已完成，这时有,11,第 步分解需用到(4.2)及(4.3)式，,于是有,引进量,取 交换 的 行与 行元素，,于是有,由此再进行第 步分解计算.,12,算法4,1.对于,(1)计算,(2)选主元,(选主元的三角分解法),(4)计算 的第 行元素，的第 列元素,(3)交换 的 行与 行元素,13,求解,2.对于,(1),

4、(2)如果 则转(3),14,(3)(继续循环),3.,4.,利用算法4的结果 可以计算 的逆矩阵,步骤：,(1)计算上三角矩阵的逆阵,(2)计算,15,上述方法求 大约需要 次乘法运算.,(3)交换 列(利用 最后记录).,16,平方根法,平方根法是利用对称正定矩阵的三角分解而得到的求解对称正定方程组的一种有效方法.,设 为对称矩阵，且 的所有顺序主子式均不为零，由,定理7知，可惟一分解为,为了利用 的对称性，将 再分解为,17,其中 为对角阵，为单位上三角阵.,（4.6）,又,于是,由分解的惟一性,得,代入(4.6)得到对称矩阵 的分解式,18,定理10,设 为 阶对称阵，,且 的所有顺序

5、主子式均不为零，,则 可惟一分解为,其中 为对角阵，为单位下三角阵.,设 为对称正定矩阵，则在分解式 中，的对角元素 均为正数.,事实上，由 的对称正定性，有,于是,(对称阵的三角分解定理),19,由定理6得到,其中 为下三角矩阵.,20,定理11,如果 为 阶对称正定矩阵，则存在一个实的非奇异下三角阵,可以用直接分解方法来确定计算 元素的递推公式.,(对称正定矩阵的三角分解或Cholesky分解),使,因为,21,其中,于是得到解对称正定方程组 的平方根法计算公式：,对于,由矩阵乘法及,按等式两边对应元素相等，得,2.,22,求解 即求解两个三角形方程组：,4.,由计算公式1知,所以,23,

6、于是,当求出 的第 列元素时，的第 行元素也算出.,所以平方根法约需 次乘除法，大约为一般直接分解法计算量的一半.,于是不选主元素的平方根法是一个数值稳定的方法.,24,由于 为对称阵，因此在计算机实现时只需存储 的下三角部分.,下三角部分共需存储 个元素，可按行主序用一维数组存放，,即,矩阵元素 在一维数组中表示为 的元素存放在 的相应位置.,用平方根法解对称正定方程组时，需要用到开方运算.,为了避免开方，用定理10的分解式,25,即,由矩阵乘法，,并注意 得,26,于是得到计算 的元素及 的对角元素公式：,对于,2.,为避免重复计算，引进,由(4.9)得到按行计算 元素的公式：,27,对于

7、,1.,2.,计算出 的第 行元素 后，,存放在 的第 行相应位置，,然后再计算 的第 行元素，,存放在 的第 行.,的对角元素存放在 的相应位置.,28,对称正定矩阵 按 分解和按 分解计算量差不多，但 分解不需要开方计算.,例如,29,5.,计算公式(4.10)，(4.11)称为改进的平方根法.,求解 计算公式,30,追赶法,实际问题中，通常要求解系数矩阵为对角占优的三对角线方程组,（4.12）,简记为,其中，当,31,利用矩阵的直接三角分解法推导解三对角线方程组（4.12)的计算公式.,其中 为下三角矩阵，为单位上三角矩阵.,由系数阵 的特点，可以将 分解为两个三角阵的乘积，,即,32,

8、设,（4.13）,其中 为待定系数.,33,比较(4.13)两边得,（4.14）,用归纳法可以证明,（4.15）,即,由,得,从而由(4.14)可求出,34,时由对角占优的条件，(4.15)是成立的.,现设(4.15)对 成立，求证对 也成立.,由归纳法假设 又由(4.15)及 的对角占优条件，有,也就是,由(4.14)得到,35,确定了，就实现了 的 分解.,求解 等价于求解两个三角形方程组：,解三对角线方程组的追赶法公式：,1.计算 的递推公式,36,2.解,3.解,称计算系数 及,称计算方程组的解 的过程为赶的过程.,的过程为追的过程.,37,定理12,设有三对角线方程组,其中 满足条件

9、,(a)，(b)，(c)，则 为非奇异矩阵且追赶法计算公式中的,满足：,追赶法公式实际上就是把高斯消去法用到求解三对角线方程组上去的结果.,38,计算机实现时只需用三个一维数组分别存储 的三条线元素，此外再用两组工作单元保存 或,由于 特别简单，因此求解的计算公式也非常简单，计算量也很小.,39,将实数,5.5 向量和矩阵的范数,向量范数概念是三维欧氏空间中向量长度概念的推广，在数值分析中起着重要作用.,定义1,（或）.,设,（或复数）,称为向量 的数量积.,40,将非负实数,或,称为向量 的欧氏范数.,定理13,关于范数，成立如下定理.,设,则,41,5.(Cauchy-Schwarz不等式

10、),等号当且仅当 与 线性相关时成立；,6.三角不等式,42,也可以用其他办法来度量向量的“大小”.,向量的欧式范数可以看成是对 中向量“大小”的一种度量.,例如，对于 可以用一个 的函数,来度量 的“大小”，而且这种度量“大小”的方法计算起来比欧氏范数方便.,一般要求度量向量“大小”的函数 满足正定性、齐次性和三角不等式.,43,（5.1）,则称 是(或)上的一个向量范数(或模).,由条件3,定义2,(向量的范数),44,（5.2）,从而有,几种常用的向量范数.,1.向量的-范数(最大范数)：,2.向量的1-范数：,45,3.向量的2-范数：,也称为向量 的欧氏范数.,4.向量的-范数：,其

11、中.,可以证明向量函数 是 上向量的范数,且容易说明上述三种范数是-范数的特殊情况.,46,如果,例6,计算向量 的各种范数.,解,定义3,设 为 中一向量序列，,则称 收敛于向量，,记,记为,47,定理14,(的连续性),证明,设,其中,只需证明当 时.,事实上,48,即,其中,49,定理15,则存在常数,证明,只要就 证明上式成立即可，即证明,存在常数 使,考虑泛函,(向量范数的等价性),有,使得对一切,50,由于 为 上的连续函数，所以 于 上达到最大、最小值，,记 则 是一个有界闭集.,即存在 使得,设 且,则,从而有,（5.3）,显然 上式为,51,即,定理15不能推广到无穷维空间.

12、由定理15可得到结论：,如果在一种范数意义下向量序列收敛时，则在任何一种范数意义下该向量序列均收敛.,52,定理16,证明,而对于 上任一种范数，,于是又有,其中为向量的任一种范数.,显然，,使,由定理15，存在常数,53,向量范数概念可以推广到矩阵.,视 中的矩阵为 中的向量，,称为 的Frobenius范数.,显然满足正定性、齐次性及三角不等式.,定义4,(矩阵的范数),54,（5.4）,则称 是 上的一个矩阵范数(或模).,上面定义的 就是 上的一个矩阵范数.,由于在大多数与估计有关的问题中，矩阵和向量会同时参与讨论，所以希望引进一种矩阵的范数，它和向量范数相联系而且和向量范数相容.,5

13、5,（5.5）,定义5,设,，,给出一种向量范数(如 或)，相应地定义一个矩阵的非负函数,即对任何向量 及 都成立,(矩阵的算子范数),（5.6）,可以验证 满足定义4，所以 是 上矩阵的一个范数，称为 的算子范数.,56,定理17,设 是 上一个向量范数，,（5.7）,证明,由(5.7)，有,由(5.6)相容性条件(5.7)是显然的.,现只验证定义4中条件4.,当 时，有,57,故,显然这种矩阵范数 依赖于具体的向量范数.,也就是说，给出一种具体的向量范数，相应地就可得到一种矩阵范数.,定理18,设,，则,58,其中 表示 的最大特征值.,证明,1.设,不妨设.,则,只就1，3给出证明，2同

14、理.,记,59,这说明对任何非零，,（5.8）,接下来说明有一向量,设，,取向量,有,使,其中,显然,且 的第 个分量为,这说明,60,3.由于对一切,从而 的特征值为非负实数，,（5.9）,为对称矩阵，设 为 的相应于(5.9)的特征向量且，又设 为任一非零向量，,设为,于是有,61,其中 为组合系数，则,另一方面，取，则上式等号成立，故,例7,设，计算 的各种范数.,解,62,对于复矩阵(即)，定理18中的第1,2项显然也成立，3应改为,63,定义6,设 的特征值为,为 的谱半径.,定理19,设,则,即 的谱半径不超过 的任何一种算子范数(对 也对).,称,(特征值上界),证明,设 是 的任一特征值，为相应的特征向量，,则，,由相容性条件(5.7)得,注意到,即得,64,定理20,如果 为对称矩阵，,定理21,如果，,则 为非奇异矩阵，,其中是指矩阵的算子范数.,则,且,证明,若,用反证法.,又由，有,故，,与假设矛盾.,65,从而,