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

浙江大学研究生学位课程,实用数值计算方法,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.存储结构 数组在计算机内存中总是一维存放的 但是它的顺序在不同的高级语言中不 一定相同。,浙江大学研究生学位课程,实用数值计算方法,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,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阶矩阵。定义,浙江大学研究生学位课程,实用数值计算方法,8,3.1.3,|x|2,图3.1 向量范数的几何意义,浙江大学研究生学位课程,实用数值计算方法,9,3.1.3 这样定义的矩阵范数具有性质：,显然，这样定义的矩阵范数与向量范数 的定义方法有关。前面三种常用的向量范数相应的矩阵范数是,浙江大学研究生学位课程,实用数值计算方法,10,3.1.3,另外，关于范数有一个很重要的等价定理：定理：有穷线性空间上的一切范数都是 等价的。即对任意两种范数 有关系式：,浙江大学研究生学位课程,实用数值计算方法,11,3.1.4 线性代数方程组的性态 线性方程组(3-2)的解完全由A和b确定。在实际问题中:由于各种原因，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 换言之，的大小 表示问题的病态程度 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 消去法中，每一步消元过程 相当于对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 例：设,浙江大学研究生学位课程,实用数值计算方法,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分 解。上述结果表明，非奇异矩阵总是 能进行选主元的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 的各阶主子矩阵均非奇异。现在我们直接从 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所存放的元素是：,容易证明：1.即是Gauss消去法中各次的主元素。,浙江大学研究生学位课程,实用数值计算方法,32,3.2.1 2.如果 A 的各阶主子矩阵均非奇异，上述过程可以一直进行到底。矩阵 A 除了以上介绍的 LU 分解以外，还有一种重要的分解方法可以用于求解 线性方程组。即 QR 分解。定理：任意矩阵 A，总是以分解成正交 矩阵 Q 与上三角矩阵 R 的乘积：如果 A 是非奇异的，则在规定R的对角元 素的符号下，分解式是唯一的。如果，则 Q 是正交矩阵,浙江大学研究生学位课程,实用数值计算方法,33,3.2.1 常见的有 Householder 正交三角分解 有了正交三角分解以后，解方程组 就变得非常简单：,用 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,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 迭代改进 由前面讨论，我们知道，由于各种原因，特别是方程组本身的病态，将会导致解与真 解之间的误差不能达到令人满意的程度。有 各种处理病态方程组的方法。这里介绍一种 简单实用的方法。它还可以用于一般方程组 的高精度求解。该方法的基本思想是利用迭 代逐步改善解的精度（关键在于在迭代过程 中有些运算需用双精度进行）迭代改善过程的框图如下：,浙江大学研究生学位课程,实用数值计算方法,38,3.2.2,是,否,图 3.3 迭代改善过程,浙江大学研究生学位课程,实用数值计算方法,39,3.2.2 由上图可知，迭代改进的计算，只要 在开始时作一次三角分解。以后只是反复 求解三角方程组就可以获得解的改善。关于解的改善的程度有以下结论：假设在浮点数的尾数是 t 位（二进制）的 计算机上用消去法计算。A 的条件数为 一般可设 则：经过一次迭代，解的精度近似地改善 了 t-p 位。因此迭代次数 k 满足 k(t-p)t 就够了。或近似地用估算式：,浙江大学研究生学位课程,实用数值计算方法,40,3.2.3 奇异值分解（SVD）解方程组时，常常会出现奇异或十分 接近于奇异的情况。用通常的Gauss消去法 或者LDU分解法难以得到满意的解。对这 类问题，我们有一个有效的方法，它叫奇 异值分解法 Singular Value Decomposition 它不但可以诊断出问题所在，而且有时能 给出一个有用的数值结果。SVD方法基于下面这个线性代数定理，由于定理本身不是我们研究的重点，这里 不加证明。,浙江大学研究生学位课程,实用数值计算方法,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,但是，如果其中有一些 或十分接近于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.如果奇异，则有,使得,浙江大学研究生学位课程,实用数值计算方法,45,3.2.3,所有满足（3-25）的x全体称的零空间。零空间的维数称为零度。.所有存在原象x,使得（3-24）成立的向量b的全体称为的域。域的维数称为的秩。.如果非奇异，则零空间只有零向量；零度；的秩；如果奇异，则零度0;秩N;但可以证明：零度秩。现在再看看分解的意义。,浙江大学研究生学位课程,实用数值计算方法,46,3.2.3分解事实上分别构造了的零空间和域的各一组正交基。由所有 对应的的第j列向量是张成域的一组正交基。由所有对应的的第j列向量是张成零空间的一组正交组。现在考虑（3-24）的解。如果 的域，则方程有无穷解。因为零空间的任何向量的,浙江大学研究生学位课程,实用数值计算方法,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,浙江大学研究生学位课程,实用数值计算方法,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,浙江大学研究生学位课程,实用数值计算方法,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）式可作为误差估计式，并且说 明|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 Gauss-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,浙江大学研究生学位课程,实用数值计算方法,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阶方阵为可约矩阵，如果存在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方法收敛。,浙江大学研究生学位课程,实用数值计算方法,72,3.4 稀疏矩阵 前面介绍了直接法和迭代法。但是实 践中如何选择计算方法是一个很复杂的问 题。需要考虑的因素很多，主要有：1.方程组的性质；（病态、对角占优、正定等）2.相类似问题出现的次数；3.方程组的阶数；4.计算机的容量、字长、运算速度等；5.系数矩阵的结构；（稀疏、三对角等）6.对结果的精度要求。,浙江大学研究生学位课程,实用数值计算方法,73,3.4 迭代法是解超高阶线性代数方程组 的重要方法之一，但是它也有缺点：不适合解病态问题；精度不高；收敛速度依赖于加速因子的选取；收敛性不能保证；所需乘除运算量大。在这些方面，相对来说，直接法运算 步骤一定，运算次数有限，精度高。对解 大型稀疏矩阵问题可以利用和保持系数矩 阵的稀疏性来降低存储容量和缩短计算时 间。,浙江大学研究生学位课程,实用数值计算方法,74,3.4.3 但是，为了保持系数矩阵的稀疏性。必须 使用特殊的计算方法和高级程序设计技术。近年来在这方面有较大的发展。其优越性 大大超过了迭代法。在这一节里，不详细介绍计算方法，只给出一些常用的标准稀疏矩阵形式。同 时给出一种一般稀疏矩阵的存储结构。这 一节里还给出一个有效的计算公式。,浙江大学研究生学位课程,实用数值计算方法,75,3.4.1 稀疏矩阵的结构和存储 从本质上讲，解稀疏问题的方法与 一般Gausss消去法LU分解法并没有什么 不同，只不过前者更注重于运算过程中 对零元素填入量的控制。稀疏系数矩阵问题的直接法必定依 赖于矩阵的稀疏形状，下面列举的是常 见的标准的稀疏矩阵。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.稀疏矩阵的存储 一般矩阵的存储方式有两种：满存和 部分存储。稀疏矩阵则采用后一种方式。稀疏矩阵的种类不同，所采用的存储 方法也不一样，但是不论采用什么方法，它 的标准有两条：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,图 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)对称矩阵的存储 因为 故只要存储 即可。任何形状的矩阵，包括稀疏的 和非稀疏的，只要是对称的。均可节省将近一半的存储量。,浙江大学研究生学位课程,实用数值计算方法,84,3.4.2 Sherman-Morrison&Woodburg 公式 我们知道，矩阵求逆问题等价于解 一个线性方程组。如果我们已经得到矩 阵A 的逆矩阵A-1。现在想在A上作个小 小变动。如：一个元素、一行、一列，或者部分元素，那么是否可以不再做复 杂的求逆运算，而只是在原来的A-1的基 础上作些适当的运算就可得到变动后的 矩阵的逆呢？回答是肯定的。假定矩阵变化为：,浙江大学研究生学位课程,实用数值计算方法,85,3.4.2 附带复习一下内积，外积的定义：,内积、外积均有结合律,（叉积）,（点积）(或：uv),浙江大学研究生学位课程,实用数值计算方法,86,3.4.2 这里 uv 是外积，它表示A的变动。Sherman-Morrison公式给出了一个计算 的方法：,这里 从（3-44）（3-45）式可以看出，给了 A-1和u，v只需作矩阵的乘积运算和一 个向量的加法：,浙江大学研究生学位课程,实用数值计算方法,87,3.4.2,Sherman-Morrison公式可以直接应用 于一类稀疏线性方程组上。如果我们已经 有一个有效的算法得到矩阵A的逆（如A 是三对角阵。或者其他标准稀疏形状的 矩阵），那么要解A的稍作变动的矩阵 决定的方程组，只要运用一次或多次 Sherman-Morrison 公式即可。但对有些稀疏问题，这个公式并不能 直接运用。理由很简单，因为A-1不可能在 机器内部全部都储存着。在实际运用中这 个公式还有变化。,浙江大学研究生学位课程,实用数值计算方法,88,3.4.2 变化一：求解求解线性系统问题：首先可以对A用有效的方法解两个辅助 问题：得到了向量y和z后，（3-48）的解既是：,浙江大学研究生学位课程,实用数值计算方法,89,3.4.2,浙江大学研究生学位课程,实用数值计算方法,90,3.4.18 变化二.即Woodbury 公式 当在标准稀疏矩阵上添加的元素不只 是一行或一列时，我们就不能简单地重复 上述过程。因为新的 A-1 并没有存储下来。这时要用 Woodbury 公式：,（3-51）式主要是计算 因此可以看到，（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.21(2)计算PP矩阵的逆(3)再解辅助方程组(4)得方程组（3-53）的解 因为：,浙江大学研究生学位课程,实用数值计算方法,94,2.5 特殊矩阵 在很多问题中，我们会遇到特殊类型 的矩阵。对于这些具有特殊性质的矩阵，不仅存储方式上应予研究并很好利用其性 质以节省存储，在计算方法上也要利用它 们的好的性质以减少运算量和提高算法稳 定性。在这一节里，我们研究几种特殊矩阵，对称、正定、带状，和三对角矩阵。由第二节的定理知，若 的各阶主子式,浙江大学研究生学位课程,实用数值计算方法,95,3.5 同样我们可以证明，若对称矩阵的各阶主子式其中是单位下三角阵，为对角矩阵。这个分解叫做对称矩阵的分解。对一般非奇异对称矩阵，则存在排列矩阵，使故可通过选主元方式达到分解。解线性问题可转化为解三个简单的线性问题：,浙江大学研究生学位课程,实用数值计算方法,96,3.5如果是正定矩阵，则是对称的并且的各阶主子式不等于。因此，存在且故可令：从而 这里是下三角矩阵。这种分解叫做对称 正定矩阵的平方根分解。,浙江大学研究生学位课程,实用数值计算方法,97,3.5,浙江大学研究生学位课程,实用数值计算方法,98,3.5 平方根分解的算法如下：,浙江大学研究生学位课程,实用数值计算方法,99,3.5这个算法的另一个优越性是不用选主元。但是从（3-60）知道，这个算法在求 要进行平方根运算。为了避免开方运算，有时我们仍要用分解。在 3.5 中，引入了带宽为2m+1的带状矩阵。他们满足：当 带状矩阵当 mn 时才有意义。带的宽度依赖于方程组未知量的次序和方程的顺序。,浙江大学研究生学位课程,实用数值计算方法,100,3.5 例如，m=1 的三对角方程的矩阵,若的相邻任意两行交换一下，则带宽从增加到。对带状矩阵，有以下定理：,浙江大学研究生学位课程,实用数值计算方法,101,3.5我们在上述定理中假定的分解存在。事实上未必总是如此，可能需要交换方程。这就可能要增加带的宽度。但不可能增大倍。但有些实际问题中遇到的带型矩阵性质是比较好的，并不需要选主元。三对角矩阵（m=1）在带状矩阵中占有重要的位置。若（3-62）中的各阶主子式，则可用追赶法很方便求解Axb。所幸的是实际应用中，有很大一类矩阵是对角占优矩阵，因而各主子式。,浙江大学研究生学位课程,实用数值计算方法,102,第三章习题,浙江大学研究生学位课程,实用数值计算方法,103,浙江大学研究生学位课程,实用数值计算方法,104,浙江大学研究生学位课程,实用数值计算方法,105,