【教学课件】第三章线性代数方程组.ppt





《【教学课件】第三章线性代数方程组.ppt》由会员分享,可在线阅读,更多相关《【教学课件】第三章线性代数方程组.ppt(105页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第三章第三章 线性代数方程组线性代数方程组 3.1 问题概述问题概述 3.2 直接法直接法 3.3 迭代法迭代法 3.4 稀疏矩阵稀疏矩阵 3.5 其他特殊形式的矩阵其他特殊形式的矩阵 浙江大学研究生学位课程1 3.1 问题概述问题概述 问题提出问题提出 线性代数方程组系数矩阵系数矩阵未知向量未知向量右顶端右顶端浙江大学研究生学位课程2 当M=N时,如果A非奇异,则方程组(3-1)存在唯一解。3.1.2 矩阵的存储与结构矩阵的存储与结构 1.1.存储方式存储方式 a.满存方式 N2个实数 b.部分存储方式 非零元素个数 稀疏矩阵、对称矩阵、块状矩阵 2.2.存储结构存储结构 数组在计算机内存中
2、总是一维存放的 但是它的顺序在不同的高级语言中不 一定相同。浙江大学研究生学位课程3 例如,FORTRAN语言中的矩阵是按列 存放的:3.存储方式与存储结构是不同的两个概念 4.矩阵的逻辑维数与物理维数 逻辑维数逻辑维数:实际参与计算的矩阵阶数 物理维数物理维数:该矩阵可能出现的最大阶数 例如例如,调用一个子程序,计算一个44矩阵 的转置,调用形式为:CALL MATINV(A,AI,NL,NP)这里,NL是逻辑维数,=4。而NP是物理 维数,即数组A的实际定义维数。浙江大学研究生学位课程4 假定NP=6,则44矩阵存放于66矩阵中:NLNP NL=4,NP=6 NP,NP Dimension
3、 A(6,6)A内存放 44矩阵 NLNL 求A(i,j)1 i,j 4 但地址是:(j-1)NP+i浙江大学研究生学位课程5 向量范数、矩阵范数向量范数、矩阵范数 定义定义1.对于任一向量是 ,按照一定 规则确定一个实数与它对应。该实数记为 ,若 满足下面三个性质:那么实数 称为向量x的范数。设 ,则它常用的几 种范数有:浙江大学研究生学位课程6 可以验证,以上定义的几种范数均满足 三个范数的性质。它们的几何意义见图3.1 从向量范数出发可以定义矩阵范数。定义定义2:设A为nn阶矩阵。定义浙江大学研究生学位课程7|x|2 图3.1 向量范数的几何意义浙江大学研究生学位课程8 这样定义的矩阵范
4、数具有性质:显然,这样定义的矩阵范数与向量范数 的定义方法有关。前面三种常用的向量范数相应的矩阵范数是浙江大学研究生学位课程9 另外,关于范数有一个很重要的等价定理:定理:有穷线性空间上的一切范数都是 等价的。即对任意两种范数 有关系式:浙江大学研究生学位课程10 3.1.4 线性代数方程组的性态线性代数方程组的性态 线性方程组(3-2)的解完全由A和b确定。在实际问题中:由于各种原因,A和b是有误差 研究A和b的微小摄动对解x的影响十分重要的 这种影响的大小反映了问题的“性态”。在(3-2)中,如果A-1存在,则解可表示为 x=A-1b 又设 为A,b的微小摄动,而 是由 此而使x产生的误差
5、。即浙江大学研究生学位课程11 示例示例 在在4位字长的计算机上解方程组位字长的计算机上解方程组 浙江大学研究生学位课程12 现给出一般情形的估计式现给出一般情形的估计式 设 则可以证明以下估计式 其中 可见,可见,k(A)近似表示了方程组求解的误差的近似表示了方程组求解的误差的 相对放大率相对放大率浙江大学研究生学位课程13 换言之,的大小 表示问题的病态程度 k(A)称为计算问题(称为计算问题(3-2)的条件数)的条件数 Condition Number 现在再看前例:浙江大学研究生学位课程14 可见计算对象(3-10)是病态的。应当指出:应当指出:1.det(A)的值小未必会引起的值小未
6、必会引起A病态病态 例如:det(A)=0.02,而A是好条件的。2.严格来说,估计式只给出了好条件严格来说,估计式只给出了好条件 的充分条件,但不是必要条件。的充分条件,但不是必要条件。3.由于数据误差在线性系统中引起由于数据误差在线性系统中引起 的固有的不可靠的使得任何过分的固有的不可靠的使得任何过分 精度要求的企图都是徒劳的。精度要求的企图都是徒劳的。浙江大学研究生学位课程153.2 3.2 直接法直接法3.2.1 直接三角分解法直接三角分解法(LU分解)分解)考虑 AX=b A非奇异 在 Gauss 消去法中,每一步消元过程 相当于对A作一次初等变换。即左乘一个初 等变换矩阵T。第一步
7、第一步:浙江大学研究生学位课程16 第第k步步 到k步以后A化为 当k=n-1时,A化为上三角阵U,即 因此浙江大学研究生学位课程17 其中 为下三角矩阵,称(3-17)为A的三角分解。由Ti性质,可以知浙江大学研究生学位课程18 Gauss 消去法的基本步骤消去法的基本步骤浙江大学研究生学位课程19 所作的初等变换为所作的初等变换为 T1 *A =A1 T2 *A1 =A2 u 例例:设浙江大学研究生学位课程20 则,它的则,它的LU分解为分解为:浙江大学研究生学位课程21 如果有了LU分解。则解方程组就 变得非常容易了。因为 由于L,U都是三角矩阵,则Y,X 都可以很 容易从上面两式中求得
8、。如果预先知道A存在LU分解,则我 们可以直接把这种分解求出来。浙江大学研究生学位课程22浙江大学研究生学位课程23 但是 Gauss 消去法并不是对任何 非奇异矩阵都能顺利进行。如如 我们有这样的结果:我们有这样的结果:任何非奇异的nn阶矩阵A,总存 在一个排列矩阵P,使PA能进行LU分 解。上述结果表明表明,非奇异矩阵总是 能进行选主元的Gauss消去法消去法。浙江大学研究生学位课程24浙江大学研究生学位课程25 为使 LU 分解标准化。把 U 改换成 DU 是可行的。其中 D 是非奇异对角矩阵。而 U 则为单位上三角矩阵。如 称 A=LDU 为矩阵 A 的 LDU 分解。定理:定理:设设
9、浙江大学研究生学位课程26 表示 A 的各阶主子矩阵。那么,A 存在 唯一的 LDU 分解的充分必要条件充分必要条件是:Ak(k=1,2,.,n)都是非奇异。如 A 为对称正定,或者对角占优,则 A 的各阶主子矩阵均非奇异。现在我们直接从 A 求 LU 分解:设设矩阵 A 有 LDU 分解。记 LD=L。则则 A=LU,L为下三角矩阵,U为单位上三角。这种LU分解称为 Crout 分解分解。浙江大学研究生学位课程27浙江大学研究生学位课程28浙江大学研究生学位课程29关于关于L,U元素的存放元素的存放 从(从(3-22),(),(3-23)可以看出。)可以看出。A的元的元素素aij在计算出在计
10、算出 或或 以后就不再有用了以后就不再有用了。浙江大学研究生学位课程30 故L,U的非零元素便可以存放在矩阵A中的相应位置上了。最后,A所存放的元素是:容易证明:容易证明:1.即是Gauss消去法消去法中各次的主元素。浙江大学研究生学位课程31 2.如果 A 的各阶主子矩阵均非奇异,上述过程可以一直进行到底。矩阵 A 除了以上介绍的 LU 分解以外,还有一种重要的分解方法可以用于求解 线性方程组。即 QR 分解。定理定理:任意矩阵 A,总是以分解成正交 矩阵 Q 与上三角矩阵 R 的乘积:如果 A 是非奇异的,则在规定R的对角元 素的符号下,分解式是唯一的。如果如果 ,则则 Q 是正交矩阵浙江
11、大学研究生学位课程32 常见的有 Householder 正交三角分解 有了正交三角分解以后,解方程组 就变得非常简单:用 Householder 变换进行分解。从而 求解线性方程组的过程是非常稳定的。也 不必选主元。特别在方程性质不太好时,更显其优越性,但计算量大。Householder 正交三角分解还有其他用途。浙江大学研究生学位课程33 PROGRAM EXAMPLE DIMENSION A(5,5),B(3),IND(3),C(3)DATA B/5.0,3.0,4.0/A(1,1)=4.0 A(3,3)=3.0 N=3 NP=5 CALL LUDCMP(A,N,NP,IND,D)CAL
12、L LUBKSB(A,N,NP,IND,B)WRITE(*,*)B C(1)=1.C(2)=2.C(3)=3.CALL LUBKSB(A,N,NP,IND,C)WRITE(*,*)C STOP END浙江大学研究生学位课程34浙江大学研究生学位课程35程序手稿原程序文件目标程序执行程序输出结果编辑(WS)编译(F77)连结(LINK)执行(程序名)库修改图3.2 程序调试流程图浙江大学研究生学位课程363.2.2 迭代改进迭代改进 由前面讨论,我们知道,由于各种原因,特别是方程组本身的病态,将会导致解与真 解之间的误差不能达到令人满意的程度。有 各种处理病态方程组的方法。这里介绍一种 简单实用
13、的方法。它还可以用于一般方程组 的高精度求解。该方法的基本思想是利用迭该方法的基本思想是利用迭 代逐步改善解的精度代逐步改善解的精度(关键在于在迭代过程 中有些运算需用双精度进行)迭代改善过程的框图如下:浙江大学研究生学位课程37是否图 3.3 迭代改善过程浙江大学研究生学位课程38 由上图可知,迭代改进的计算,只要 在开始时作一次三角分解。以后只是反复 求解三角方程组就可以获得解的改善。关于解的改善的程度有以下结论:关于解的改善的程度有以下结论:假设在浮点数的尾数是 t 位(二进制)的 计算机上用消去法计算。A 的条件数为 一般可设 则:经过一次迭代,解的精度近似地改善 了 t-p 位。因此
14、迭代次数 k 满足 k(t-p)t 就够了。或近似地用估算式:浙江大学研究生学位课程393.2.3 奇异值分解奇异值分解(SVD)解方程组时,常常会出现奇异或十分 接近于奇异的情况。用通常的Gauss消去法 或者LDU分解法难以得到满意的解。对这 类问题,我们有一个有效的方法,它叫奇奇 异值分解法异值分解法 Singular Value Decomposition 它不但可以诊断出问题所在,而且有时能 给出一个有用的数值结果。SVD方法基于下面这个线性代数定理,由于定理本身不是我们研究的重点,这里 不加证明。浙江大学研究生学位课程40 定理:对任意MN矩阵A,这里MN,它都可以分解成下列形式:
15、A=UWVT其中:U是MN列正交矩阵;V是NN 正交矩阵;W是NN对角矩阵。且对角元素非负。即:浙江大学研究生学位课程41 由于V是方阵,故它还是行正交即 不管矩阵A是否奇异。SVD分解都能做到。而且它“几乎”是唯一的。即允许U,V的列进行变换并进行W相应交换的前提下是唯一的。如果A是NN方阵,则U,V,W都是方阵。且分解式可写为:浙江大学研究生学位课程42但是,如果其中有一些 或十分接近于0,即A奇异或接近奇异,那么A-1就难以求得。因此,SVD分解可以通过判断 的大小来分析A的性态。当A是奇异时,我们就考虑在某种意义下的解。浙江大学研究生学位课程43 由代数知识,有 当 rank(A)0;
16、秩N;但可以证明:零度秩零度秩。现在再看看分解的意义。浙江大学研究生学位课程45分解事实上分别构造了的零空间和域的各一组正交基。由所有 对应的的第j列向量是张成域的一组正交基。由所有对应的的第j列向量是张成零空间的一组正交组。现在考虑(3-24)的解。如果 的域,则方程有无穷解。因为零空间的任何向量的浙江大学研究生学位课程46 故任意的域中向量b可以由 线性表示,即这样的 张成域的一组基。(1)浙江大学研究生学位课程47(2)浙江大学研究生学位课程48浙江大学研究生学位课程49浙江大学研究生学位课程50浙江大学研究生学位课程51以上讨论用图表示如下:A图图 3.4 解空间示意图解空间示意图浙江
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 教学课件 教学 课件 第三 线性代数 方程组

限制150内