第三章线性代数方程组.ppt

《第三章线性代数方程组.ppt》由会员分享，可在线阅读，更多相关《第三章线性代数方程组.ppt（105页珍藏版）》请在三一文库上搜索。

1、浙江大学研究生学位课程,实用数值计算方法,1,第三章 线性代数方程组,3.1 问题概述 3.2 直接法 3.3 迭代法 3.4 稀疏矩阵 3.5 其他特殊形式的矩阵,浙江大学研究生学位课程,实用数值计算方法,2,3.1 问题概述 3.1.1 问题提出 线性代数方程组,系数矩阵,未知向量,右顶端,浙江大学研究生学位课程,实用数值计算方法,3,当M=N时，如果A非奇异，则方程组（3-1） 存在唯一解。 3.1.2 矩阵的存储与结构 1. 存储方式 a.满存方式 N2个实数 b.部分存储方式 非零元素个数 稀疏矩阵、对称矩阵、块状矩阵 2. 存储结构 数组在计算机内存中总是一维存放的 但是它的顺序在

2、不同的高级语言中不 一定相同。,浙江大学研究生学位课程,实用数值计算方法,4,3.1.2 例如，FORTRAN语言中的矩阵是按列 存放的：,3. 存储方式与存储结构是不同的两个概念 4. 矩阵的逻辑维数与物理维数 逻辑维数：实际参与计算的矩阵阶数 物理维数：该矩阵可能出现的最大阶数 例如，调用一个子程序，计算一个44矩阵 的转置，调用形式为： CALL MATINV（A, AI, NL, NP） 这里，NL是逻辑维数，=4。而NP是物理 维数，即数组A的实际定义维数。,浙江大学研究生学位课程,实用数值计算方法,5,3.1.2 假定NP=6，则44矩阵存放于66矩阵中：,NL,NP,NL=4,

3、NP=6 NP,NP Dimension A(6,6) A内存放 44矩阵 NLNL 求A( i,j ) 1 i,j 4 但地址是： （j-1）NP +i,浙江大学研究生学位课程,实用数值计算方法,6,3.1.3 向量范数、矩阵范数 定义1. 对于任一向量是 ，按照一定 规则确定一个实数与它对应。 该实数记为 ， 若 满足下面三个性质： 那么实数 称为向量x的范数。 设 ，则它常用的几 种范数有：,浙江大学研究生学位课程,实用数值计算方法,7,3.1.3,可以验证，以上定义的几种范数均满足 三个范数的性质。它们的几何意义见图3.1 从向量范数出发可以定义矩阵范数。 定义2：设A为nn阶矩阵。定

4、义,浙江大学研究生学位课程,实用数值计算方法,8,3.1.3,|x|2,图3.1 向量范数的几何意义,浙江大学研究生学位课程,实用数值计算方法,9,3.1.3 这样定义的矩阵范数具有性质：,显然，这样定义的矩阵范数与向量范数 的定义方法有关。 前面三种常用的向量范数相应的矩阵范数是,浙江大学研究生学位课程,实用数值计算方法,10,3.1.3,另外，关于范数有一个很重要的等价定理： 定理：有穷线性空间上的一切范数都是 等价的。即对任意两种范数 有关系式：,浙江大学研究生学位课程,实用数值计算方法,11,3.1.4 线性代数方程组的性态 线性方程组(3-2) 的解完全由A和b确定。 在实际问题中:

5、 由于各种原因，A和b是有误差 研究A和b的微小摄动对解x的影响十分重要的 这种影响的大小反映了问题的“性态”。 在（3-2）中，如果A-1存在，则解可表示为 x=A-1b 又设 为A,b的微小摄动，而 是由 此而使x产生的误差。即,浙江大学研究生学位课程,实用数值计算方法,12,3.1.3 示例 在4位字长的计算机上解方程组,浙江大学研究生学位课程,实用数值计算方法,13,3.1.3 现给出一般情形的估计式 设 则可以证明以下估计式 其中 可见，k(A)近似表示了方程组求解的误差的 相对放大率,浙江大学研究生学位课程,实用数值计算方法,14,3.1.3 换言之， 的大小 表示问题的病态程度

6、k(A)称为计算问题（3-2）的条件数 Condition Number 现在再看前例：,浙江大学研究生学位课程,实用数值计算方法,15,3.1.3 可见计算对象（3-10）是病态的。 应当指出： 1. det(A)的值小未必会引起A病态 例如： det(A)=0.02，而A是好条件的。 2. 严格来说，估计式只给出了好条件 的充分条件，但不是必要条件。 3. 由于数据误差在线性系统中引起 的固有的不可靠的使得任何过分 精度要求的企图都是徒劳的。,浙江大学研究生学位课程,实用数值计算方法,16,3.2 直接法 3.2.1 直接三角分解法（LU分解） 考虑 AX=b A非奇异 在 Gauss 消

7、去法中，每一步消元过程 相当于对A作一次初等变换。即左乘一个初 等变换矩阵T。 第一步：,浙江大学研究生学位课程,实用数值计算方法,17,3.2.1 第k步,到k步以后A化为 当k=n-1时，A化为上三角阵U，即 因此,浙江大学研究生学位课程,实用数值计算方法,18,3.2.1 其中 为下三角矩阵，称（3-17）为A的三角分解。 由Ti性质，可以知,浙江大学研究生学位课程,实用数值计算方法,19,3.2.1 Gauss 消去法的基本步骤,浙江大学研究生学位课程,实用数值计算方法,20,3.2.1 所作的初等变换为,T1 * A = A1,T2 * A1 = A2 u 例：设,浙江大学研究生学位

8、课程,实用数值计算方法,21,3.2.1 则，它的LU分解为：,浙江大学研究生学位课程,实用数值计算方法,22,3.2.1 如果有了LU分解。则解方程组就 变得非常容易了。因为,由于L,U都是三角矩阵，则Y,X 都可以很 容易从上面两式中求得。 如果预先知道A存在LU分解，则我 们可以直接把这种分解求出来。,浙江大学研究生学位课程,实用数值计算方法,23,3.2.1,浙江大学研究生学位课程,实用数值计算方法,24,3.2.1 但是 Gauss 消去法并不是对任何 非奇异矩阵都能顺利进行。如 我们有这样的结果： 任何非奇异的nn阶矩阵A，总存 在一个排列矩阵P，使PA能进行LU分 解。 上述结果

9、表明，非奇异矩阵总是 能进行选主元的Gauss消去法。,浙江大学研究生学位课程,实用数值计算方法,25,3.2.1,浙江大学研究生学位课程,实用数值计算方法,26,3.2.1 为使 LU 分解标准化。把 U 改换成 DU 是可行的。其中 D 是非奇异对角矩阵。而 U 则为单位上三角矩阵。如,称 A=LDU 为矩阵 A 的 LDU 分解。 定理：设,浙江大学研究生学位课程,实用数值计算方法,27,3.2.1 表示 A 的各阶主子矩阵。那么，A 存在 唯一的 LDU 分解的充分必要条件是： Ak （k=1,2,.,n）都是非奇异。 如 A 为对称正定，或者对角占优，则 A 的各阶主子矩阵均非奇异。

10、 现在我们直接从 A 求 LU 分解： 设矩阵 A 有 LDU 分解。记 LD=L。则 A=LU，L为下三角矩阵，U为单位上三角。 这种LU分解称为 Crout 分解。,浙江大学研究生学位课程,实用数值计算方法,28,3.2.1,浙江大学研究生学位课程,实用数值计算方法,29,3.2.1,浙江大学研究生学位课程,实用数值计算方法,30,3.2.1,关于L, U元素的存放 从（3-22），（3-23）可以看出。A的元素aij在计算出 或 以后就不再有用了。,浙江大学研究生学位课程,实用数值计算方法,31,3.2.1 故L,U的非零元素便可以存放在矩阵A中的相应位置上了。 最后， A所存放的元素是

11、：,容易证明： 1. 即是Gauss消去法中各次的主元素。,浙江大学研究生学位课程,实用数值计算方法,32,3.2.1 2. 如果 A 的各阶主子矩阵均非奇异， 上述过程可以一直进行到底。 矩阵 A 除了以上介绍的 LU 分解以外， 还有一种重要的分解方法可以用于求解 线性方程组。即 QR 分解。 定理：任意矩阵 A，总是以分解成正交 矩阵 Q 与上三角矩阵 R 的乘积： 如果 A 是非奇异的，则在规定R的对角元 素的符号下，分解式是唯一的。 如果 ， 则 Q 是正交矩阵,浙江大学研究生学位课程,实用数值计算方法,33,3.2.1 常见的有 Householder 正交三角分解 有了正交三角分

12、解以后，解方程组 就变得非常简单：,用 Householder 变换进行分解。从而 求解线性方程组的过程是非常稳定的。也 不必选主元。特别在方程性质不太好时， 更显其优越性，但计算量大。 Householder 正交三角分解还有其他用途。,浙江大学研究生学位课程,实用数值计算方法,34,3.2.1 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) CALL LUBKSB(A,N,NP,IND

13、,B) WRITE(*,*) B C(1)=1. C(2)=2. C(3)=3. CALL LUBKSB(A,N,NP,IND,C) WRITE (*,*) C STOP END,浙江大学研究生学位课程,实用数值计算方法,35,3.2.1,浙江大学研究生学位课程,实用数值计算方法,36,3.2.1,程序手稿,原程序文件,目标程序,执行程序,输出结果,编辑（WS）,编译（F77）,连结（LINK）,执行（程序名）,库,修改,图3.2 程序调试流程图,浙江大学研究生学位课程,实用数值计算方法,37,3.2.2 迭代改进 由前面讨论，我们知道，由于各种原因， 特别是方程组本身的病态，将会导致解与真

14、解之间的误差不能达到令人满意的程度。有 各种处理病态方程组的方法。这里介绍一种 简单实用的方法。它还可以用于一般方程组 的高精度求解。该方法的基本思想是利用迭 代逐步改善解的精度（关键在于在迭代过程 中有些运算需用双精度进行） 迭代改善过程的框图如下：,浙江大学研究生学位课程,实用数值计算方法,38,3.2.2,是,否,图 3.3 迭代改善过程,浙江大学研究生学位课程,实用数值计算方法,39,3.2.2 由上图可知，迭代改进的计算，只要 在开始时作一次三角分解。以后只是反复 求解三角方程组就可以获得解的改善。 关于解的改善的程度有以下结论： 假设在浮点数的尾数是 t 位（二进制）的 计算机上用

15、消去法计算。A 的条件数为 一般可设 则：经过一次迭代，解的精度近似地改善 了 t-p 位。因此迭代次数 k 满足 k(t-p)t 就够了。 或近似地用估算式：,浙江大学研究生学位课程,实用数值计算方法,40,3.2.3 奇异值分解（SVD） 解方程组时，常常会出现奇异或十分 接近于奇异的情况。用通常的Gauss消去法 或者LDU分解法难以得到满意的解。对这 类问题，我们有一个有效的方法，它叫奇 异值分解法 Singular Value Decomposition 它不但可以诊断出问题所在，而且有时能 给出一个有用的数值结果。 SVD方法基于下面这个线性代数定理， 由于定理本身不是我们研究的重

16、点，这里 不加证明。,浙江大学研究生学位课程,实用数值计算方法,41,3.2.3,定理：对任意MN矩阵A，这里MN，它都可以分解成下列形式： A=UWVT 其中：U是MN列正交矩阵； V是NN 正交矩阵； W是NN对角矩阵。且对角元素非负。 即：,浙江大学研究生学位课程,实用数值计算方法,42,3.2.3,由于V是方阵，故它还是行正交即 不管矩阵A是否奇异。SVD分解都能做到。而且它“几乎”是唯一的。即允许 U，V的列进行变换并进行W相应交换的前提下是唯一的。 如果A是NN方阵，则U，V，W都是方阵。且分解式可写为：,浙江大学研究生学位课程,实用数值计算方法,43,3.2.3,但是，如果其中有

17、一些 或十分接 近于0，即A奇异或接近奇异，那么A-1 就难以求得。因此，SVD分解可以通过 判断 的大小来分析A的性态。 当A是奇异时，我们就考虑,在某种意义下的解。,浙江大学研究生学位课程,实用数值计算方法,44,3.2.3 由代数知识，有 当 rank(A)rank(A,b)时， （3-24）为矛盾方程组。无解。 当 rank(A)=rank(A,b)时， （3-24）有无穷多解。 在这些解中。有一个最小长度解 在某些场合是有意义的。 在求这个解以前，先介绍几个重要的概念。 1.（3-24）定义了一个从向量空间x到向 量空间b的线性映射A。 2. 如果奇异，则有 ,使得,浙江大学研究生学

18、位课程,实用数值计算方法,45,3.2.3,所有满足（3-25）的x全体称的零空间。 零空间的维数称为零度。 . 所有存在原象x, 使得（3-24）成立的向量 b的全体称为的域。域的维数称为的秩。 . 如果非奇异，则零空间只有零向量； 零度；的秩； 如果奇异，则零度0; 秩N; 但可以证明：零度秩。 现在再看看分解的意义。,浙江大学研究生学位课程,实用数值计算方法,46,3.2.3 分解事实上分别构造了的零 空间和域的各一组正交基。 由所有 对应的的第j列向量 是张成域的一组正交基。 由所有 对应的的第j列向量 是张成零空间的一组正交组。 现在考虑（3-24）的解。如果 的域， 则方程有无穷解

19、。因为零空间的任何向量的,浙江大学研究生学位课程,实用数值计算方法,47,3.2.3,故任意的域中向量b可以由 线性表示， 即这样的 张成域的一组基。,（1）,浙江大学研究生学位课程,实用数值计算方法,48,3.2.3,（2）,浙江大学研究生学位课程,实用数值计算方法,49,3.2.3,浙江大学研究生学位课程,实用数值计算方法,50,3.2.3,浙江大学研究生学位课程,实用数值计算方法,51,3.2.3,浙江大学研究生学位课程,实用数值计算方法,52,3.2.3,以上讨论用图表示如下：,A,图 3.4 解空间示意图,浙江大学研究生学位课程,实用数值计算方法,53,3.2.3,浙江大学研究生学位

20、课程,实用数值计算方法,54,3.2.3,浙江大学研究生学位课程,实用数值计算方法,55,3.3 迭代法 迭代法适用于解高阶稀疏非病 态方程组。它只需要存储非零元素。 但对有些问题，迭代可能发散 或收敛很慢。 3.3.1 Jacobi 迭代法 设有方程组 其中A是NN非奇异矩阵。故有唯一解。 把（3-26）改写成迭代形式,浙江大学研究生学位课程,实用数值计算方法,56,于是设X(0)是一个任意的初始迭代向量。 代入（3-27）的右边，得到新的向量记为X(1)： 一般地有： 我们得到向量序列 如果 收敛于 X ，即： 则向量 X 是（3-27）的解。 现讨论解的求法及收敛性,3.3.1,浙江大学

21、研究生学位课程,实用数值计算方法,57,3.3.1 设矩阵A的对角元素 。记 则D非 奇异。将A表示成和式 其中：,浙江大学研究生学位课程,实用数值计算方法,58,3.3.1,利用（3-29）式的矩阵符号。Jacobi 法可以 表示成： 这里B 是 Jacobi 迭代矩阵。其定义为,Jacobi 方法收敛的充要条件是： 迭代矩阵B的谱半径,浙江大学研究生学位课程,实用数值计算方法,59,3.3.1,浙江大学研究生学位课程,实用数值计算方法,60,3.3.1 现在讨论一下Jacobi方法的收敛速度 的快慢及影响速度的因素。,浙江大学研究生学位课程,实用数值计算方法,61,3.3.1 （3-34）

22、式可作为误差估计式，并且说 明|B|越小，x(k) 收敛越快。（3-35）式说 明了只要|B|不是很小，当相邻两次迭代向 量x(k) 和 x(k-1) 很接近时，解 x* 和 x(k) 也是很 接近的。因此，可以用 | x(k)- x(k-1)| 作为 迭代终止的判别式。这个结论对逐次逼 近法也成立。 特别，应该指出，以上讨论的收敛性 及收敛速度均是对一般迭代式（3-27）而 言。因此，其结论对以后要讨论的G-S迭 代法和SOR法也成立。,浙江大学研究生学位课程,实用数值计算方法,62,3.3.1 Jacobi 迭代法的计算步骤：,浙江大学研究生学位课程,实用数值计算方法,63,3.3.2 G

23、auss-Seidel 迭代法。 G-S迭代法的基本思想来自Jacobi 迭代法。只是迭代矩阵B不同。,浙江大学研究生学位课程,实用数值计算方法,64,3.3.2 这就是 Gauss-Seidel 迭代格式，它 也可写为： 若用（3-29）式记号，则G-S迭代式可 表示为： 或 其中,浙江大学研究生学位课程,实用数值计算方法,65,有关收敛性和收敛速度的讨论完全 与 Jacobi 方法相同，只是迭代阵为L。 3.3.3 逐次超松弛（SOR）法 SOR法定义为：,浙江大学研究生学位课程,实用数值计算方法,66,3.3.3,浙江大学研究生学位课程,实用数值计算方法,67,2.3.13,浙江大学研究

24、生学位课程,实用数值计算方法,68,3.3.3 三种迭代法的比较： 1. 一般情况下，J方法与G-S方法比较 并无优劣。收敛情况与速度均不一定。 例：,浙江大学研究生学位课程,实用数值计算方法,69,3.3.3 2. 但是具有相容次序的矩阵，在相同 精度要求下，迭代次数分别为： Jacobi 方法：1154 G-S 方法：578 SOR 方法：59 可见对这类矩阵，G-S 法比J方法快一倍， 而 SOR 法的收敛速度可提高一个数量级。 最后介绍一类对于三种方法都收敛的 矩阵。先定义可约矩阵和对角占优矩阵：,浙江大学研究生学位课程,实用数值计算方法,70,3.3.3 (1). 称n阶方阵为可约矩

25、阵，如果存在n阶 排列阵P，使得 其中A11为r阶方阵，A22为（n-r）阶方阵 不是可约矩阵就是不可约矩阵 (2). 称 n 阶方阵A是对角占优矩阵，如果 若上式严格不等号成立，则称A为严格对角 占优矩阵。,浙江大学研究生学位课程,实用数值计算方法,71,3.3.3 (3). 称A是不可约对角占优矩阵。如果A是不可 约的且对角占优，而（3-42）式中至少对一 个 i 有严格不等号成立。 我们有如下结论： 1. 若A是严格对角占优或不可约对角占优 矩阵，则A非奇异。 2. 若线性方程组系数A是上述矩阵，则： 1）J方程和G-S方法都收敛。 2）当 SOR方法收敛。,浙江大学研究生学位课程,实用

26、数值计算方法,72,3.4 稀疏矩阵 前面介绍了直接法和迭代法。但是实 践中如何选择计算方法是一个很复杂的问 题。需要考虑的因素很多，主要有： 1.方程组的性质；（病态、对角占优、正定等） 2.相类似问题出现的次数； 3.方程组的阶数； 4.计算机的容量、字长、运算速度等； 5.系数矩阵的结构；（稀疏、三对角等） 6.对结果的精度要求。,浙江大学研究生学位课程,实用数值计算方法,73,3.4 迭代法是解超高阶线性代数方程组 的重要方法之一，但是它也有缺点： 不适合解病态问题； 精度不高； 收敛速度依赖于加速因子的选取； 收敛性不能保证； 所需乘除运算量大。 在这些方面，相对来说，直接法运算 步

27、骤一定，运算次数有限，精度高。对解 大型稀疏矩阵问题可以利用和保持系数矩 阵的稀疏性来降低存储容量和缩短计算时 间。,浙江大学研究生学位课程,实用数值计算方法,74,3.4.3 但是，为了保持系数矩阵的稀疏性。必须 使用特殊的计算方法和高级程序设计技术。 近年来在这方面有较大的发展。其优越性 大大超过了迭代法。 在这一节里，不详细介绍计算方法， 只给出一些常用的标准稀疏矩阵形式。同 时给出一种一般稀疏矩阵的存储结构。这 一节里还给出一个有效的计算公式。,浙江大学研究生学位课程,实用数值计算方法,75,3.4.1 稀疏矩阵的结构和存储 从本质上讲，解稀疏问题的方法与 一般Gausss消去法LU分

28、解法并没有什么 不同，只不过前者更注重于运算过程中 对零元素填入量的控制。 稀疏系数矩阵问题的直接法必定依 赖于矩阵的稀疏形状，下面列举的是常 见的标准的稀疏矩阵。 1.稀疏矩阵的结构,浙江大学研究生学位课程,实用数值计算方法,76,3.4.1,带 对 角,块三角阵,块三角阵,单边块对角,双边块对角,e,a,c,d,b,单边块三角,f,图 3.5 ?,浙江大学研究生学位课程,实用数值计算方法,77,3.4.1,双边带三角,单边带对角,双边带对角,其他,其他,k,g,i,j,h,图 3.6 稀疏矩阵的形式,浙江大学研究生学位课程,实用数值计算方法,78,3.4.1 2. 稀疏矩阵的存储 一般矩阵

29、的存储方式有两种：满存和 部分存储。稀疏矩阵则采用后一种方式。 稀疏矩阵的种类不同，所采用的存储 方法也不一样，但是不论采用什么方法，它 的标准有两条： 1）节省存储空间 ； 2）存取方便，即节省存取时间。 存储方法的选择一般要根据矩阵的 种类和对程序的要求在上述两个标准之间 权衡。,浙江大学研究生学位课程,实用数值计算方法,79,3.4.1 (1) 带对角矩阵的存储,图 3.7 带对角矩阵的存储方式,浙江大学研究生学位课程,实用数值计算方法,80,3.4.1 (2)块三角型矩阵的存储, , , , ,H1,i1,iL,il+1,N1,H2 N2,Hl+1,aij,Hl Nl,ID2L,iL,

30、图 3.8 块三角型矩阵的存储形式,浙江大学研究生学位课程,实用数值计算方法,81,3.4.1 (3) 一般稀疏矩阵的存储,B：一维存储非零元素（按行）,（m）,（m）,JA：B中相应元素所在的列号（A中）,IA：每行第一个非零元素在B中的下标。,（n）,浙江大学研究生学位课程,实用数值计算方法,82,3.4.1 例如：,图 3.9 矩阵A非零元素存放的一般形式,浙江大学研究生学位课程,实用数值计算方法,83,3.4.1 (4) 对称矩阵的存储 因为 故只要存储 即可。 任何形状的矩阵，包括稀疏的 和非稀疏的，只要是对称的。 均可节省将近一半的存储量。,浙江大学研究生学位课程,实用数值计算方法

31、,84,3.4.2 Sherman-Morrison & Woodburg 公式 我们知道，矩阵求逆问题等价于解 一个线性方程组。如果我们已经得到矩 阵A 的逆矩阵A-1。现在想在A上作个小 小变动。如：一个元素、一行、一列， 或者部分元素，那么是否可以不再做复 杂的求逆运算，而只是在原来的A-1的基 础上作些适当的运算就可得到变动后的 矩阵的逆呢？回答是肯定的。 假定矩阵变化为：,浙江大学研究生学位课程,实用数值计算方法,85,3.4.2 附带复习一下内积，外积的定义：,内积、外积均有结合律,（叉积）,（点积）(或：uv),浙江大学研究生学位课程,实用数值计算方法,86,3.4.2 这里 u

32、v 是外积，它表示A的变动。 Sherman-Morrison公式给出了一个计算 的方法：,这里 从（3-44）（3-45）式可以看出，给了 A-1和u，v只需作矩阵的乘积运算和一 个向量的加法：,浙江大学研究生学位课程,实用数值计算方法,87,3.4.2,Sherman-Morrison公式可以直接应用 于一类稀疏线性方程组上。如果我们已经 有一个有效的算法得到矩阵A的逆（如A 是三对角阵。或者其他标准稀疏形状的 矩阵），那么要解A的稍作变动的矩阵 决定的方程组，只要运用一次或多次 Sherman-Morrison 公式即可。 但对有些稀疏问题，这个公式并不能 直接运用。理由很简单，因为A-

33、1不可能在 机器内部全部都储存着。在实际运用中这 个公式还有变化。,浙江大学研究生学位课程,实用数值计算方法,88,3.4.2 变化一：求解求解线性系统问题： 首先可以对A用有效的方法解两个辅助 问题： 得到了向量y和z后，（3-48）的解既是：,浙江大学研究生学位课程,实用数值计算方法,89,3.4.2,浙江大学研究生学位课程,实用数值计算方法,90,3.4.18 变化二. 即Woodbury 公式 当在标准稀疏矩阵上添加的元素不只 是一行或一列时，我们就不能简单地重复 上述过程。因为新的 A-1 并没有存储下来。 这时要用 Woodbury 公式：,（3-51）式主要是计算 因此可以看到，

34、（3-51）式把一个NN阵求 逆问题转化为一个P P阵的有求逆问题。由 于 PN, 故问题得以大大简化。,浙江大学研究生学位课程,实用数值计算方法,91,3.4.2,Woodbury公式和连续地运用Sherman- Morrison公式的联系在于： 如果记,则有,浙江大学研究生学位课程,实用数值计算方法,92,3.4.2 上式表明，如果已经求得A-1，计算 的方法有两种： （1）利用（3-51），计算一个 PP 的逆矩阵。 （2）利用（3-47），执行P次。 如果A-1没有存储，则解下列问题 的步骤是 (1) 解P个辅助方程组： 得矩阵,浙江大学研究生学位课程,实用数值计算方法,93,3.4.

35、21 (2) 计算PP矩阵的逆 (3) 再解辅助方程组 (4) 得方程组（3-53）的解 因为：,浙江大学研究生学位课程,实用数值计算方法,94,2.5 特殊矩阵 在很多问题中，我们会遇到特殊类型 的矩阵。对于这些具有特殊性质的矩阵， 不仅存储方式上应予研究并很好利用其性 质以节省存储，在计算方法上也要利用它 们的好的性质以减少运算量和提高算法稳 定性。 在这一节里，我们研究几种特殊矩阵， 对称、正定、带状，和三对角矩阵。 由第二节的定理知，若 的各阶主子式,浙江大学研究生学位课程,实用数值计算方法,95,3.5 同样我们可以证明，若对称矩阵的 各阶主子式 其中 是单位下三角阵，为对角矩阵。

36、这个分解叫做对称矩阵的 分解。 对一般非奇异对称矩阵，则存在排列矩 阵，使 故可通过选主元方式达到 分解。 解线性问题 可转化为 解三个简单的线性问题：,浙江大学研究生学位课程,实用数值计算方法,96,3.5 如果是正定矩阵，则是对称的 并且的各阶主子式不等于。因此， 存在 且 故可令： 从而 这里是下三角矩阵。这种分解叫做对称 正定矩阵的平方根分解。,浙江大学研究生学位课程,实用数值计算方法,97,3.5,浙江大学研究生学位课程,实用数值计算方法,98,3.5 平方根分解的算法如下：,浙江大学研究生学位课程,实用数值计算方法,99,3.5 这个算法的另一个优越性是不用选主元。 但是从（3-6

37、0）知道，这个算法在求 要进行平方根运算。 为了避免开方运算，有时我们仍要用 分解。 在 3.5 中，引入了带宽为2m+1的带 状矩阵。他们满足： 当 带状矩阵当 mn 时才有意义。 带的宽度依赖于方程组未知量的次序 和方程的顺序。,浙江大学研究生学位课程,实用数值计算方法,100,3.5 例如，m=1 的三对角方程的矩阵,若的相邻任意两行交换一下，则带宽从 增加到。 对带状矩阵，有以下定理：,浙江大学研究生学位课程,实用数值计算方法,101,3.5 我们在上述定理中假定的分解存 在。事实上未必总是如此，可能需要交换 方程。这就可能要增加带的宽度。但不可 能增大倍。 但有些实际问题中遇到的带型矩阵性 质是比较好的，并不需要选主元。 三对角矩阵（m=1）在带状矩阵中占 有重要的位置。若（3-62）中的各阶主子式 ，则可用追赶法很方便求解Axb。 所幸的是实际应用中，有很大一类矩阵是 对角占优矩阵，因而各主子式。,浙江大学研究生学位课程,实用数值计算方法,102,第三章 习题,浙江大学研究生学位课程,实用数值计算方法,103,浙江大学研究生学位课程,实用数值计算方法,104,浙江大学研究生学位课程,实用数值计算方法,105,