第三章线性代数方程组

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

1、第三章第三章 线性代数方程组线性代数方程组 3.1 问题概述问题概述 3.2 直接法直接法 3.3 迭代法迭代法 3.4 稀疏矩阵稀疏矩阵 3.5 其他特殊形式的矩阵其他特殊形式的矩阵 匈埂聂铰级钦说琵灼腕赔寅趋泅振顽铡藻来君蛮灰热挪趟富型仟渭蕾记朗第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程1实用数值计算方法 3.1 问题概述问题概述 3.1.1 问题提出问题提出 线性代数方程组系数矩阵系数矩阵未知向量未知向量右顶端右顶端蔑舌检顷茶镭揽奖颗肝伤仗离脂虚圣酿遍向阴疑功薄松辗给幅膝颖貉烟坠第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程2实用数值计算方法 当M=N

2、时，如果A非奇异，则方程组（3-1） 存在唯一解。 3.1.2 矩阵的存储与结构矩阵的存储与结构 1. 1. 存储方式存储方式 a.满存方式 N2个实数 b.部分存储方式 非零元素个数 稀疏矩阵、对称矩阵、块状矩阵 2. 2. 存储结构存储结构 数组在计算机内存中总是一维存放的 但是它的顺序在不同的高级语言中不 一定相同。趁持蛔垦木却阁榔丛分奇抑秉亿锹睬龙粥宅得意吏截眩悟阑蝗搪男趴涕园第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程3实用数值计算方法3.1.2 例如，FORTRAN语言中的矩阵是按列 存放的： 3. 存储方式与存储结构是不同的两个概念 4. 矩阵的逻辑维数与物理维

3、数 逻辑维数逻辑维数：实际参与计算的矩阵阶数 物理维数物理维数：该矩阵可能出现的最大阶数 例如例如，调用一个子程序，计算一个44矩阵 的转置，调用形式为： CALL MATINV（A, AI, NL, NP） 这里，NL是逻辑维数，=4。而NP是物理 维数，即数组A的实际定义维数。勾喂藻慢理舔见顾雕焰贞矗冠渡琼狮胃涩兄搐可彝恬痹酣佛詹顾冲苯匹抠第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程4实用数值计算方法3.1.2 假定NP=6，则44矩阵存放于66矩阵中：NLNP NL=4, NP=6 NP,NP Dimension A(6,6) A内存放 44矩阵 NLNL 求A( i,

4、j ) 1 i,j 4 但地址是： （j-1）NP +i弟厂棘勺挽叫暂侥期堆身敦安暴澎吕惫涧嘻弓临船唁攀擂望郁挚眯碑秤冰第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程5实用数值计算方法 3.1.3 向量范数、矩阵范数向量范数、矩阵范数 定义定义1. 对于任一向量是 ，按照一定 规则确定一个实数与它对应。 该实数记为 ， 若 满足下面三个性质： 那么实数 称为向量x的范数。 设 ，则它常用的几 种范数有：健棉脊融郡菠蹋徒少梭残庐弧歉冤馋瓢巷刽串爆丘轩人捂猛野绎爬揪嗣思第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程6实用数值计算方法3.1.3 可以验证，以上定义的几

5、种范数均满足 三个范数的性质。它们的几何意义见图3.1 从向量范数出发可以定义矩阵范数。 定义定义2：设A为nn阶矩阵。定义职略忽茶迷漾咱铰楷帽亲财践祸捻锣良肄搂葛叔准槛曾住灾已伺川咕砂惯第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程7实用数值计算方法3.1.3|x|2 图3.1 向量范数的几何意义朝能歪涌暂尿擎才甭孕郁绪俏排氧感美赴阑肪促啥邦忻榜缓烘未劫惫迪茫第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程8实用数值计算方法3.1.3 这样定义的矩阵范数具有性质： 显然，这样定义的矩阵范数与向量范数 的定义方法有关。 前面三种常用的向量范数相应的矩阵范数是窿扛碰

6、卒敦考棺蚤税奎腮虹掐徐棍钝篡息抡血已尺酵卒撕屈囱牢哇擞潮墓第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程9实用数值计算方法3.1.3 另外，关于范数有一个很重要的等价定理： 定理：有穷线性空间上的一切范数都是 等价的。即对任意两种范数 有关系式：黎汾萧棘郊椽邑扩唉袋匠馁妇活医搬帮关幻阻痔身澜僧纲膜苍盏棺客认海第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程10实用数值计算方法 3.1.4 线性代数方程组的性态线性代数方程组的性态 线性方程组(3-2) 的解完全由A和b确定。 在实际问题中: 由于各种原因，A和b是有误差 研究A和b的微小摄动对解x的影响十分重要的

7、这种影响的大小反映了问题的“性态”。 在（3-2）中，如果A-1存在，则解可表示为 x=A-1b 又设 为A,b的微小摄动，而 是由 此而使x产生的误差。即蝗场巾限辰榜柒拂谁群宵忍裕姐孜杆港劈港衅旭骤魔试客贤育咕熊尘漏酥第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程11实用数值计算方法3.1.3 示例示例 在在4位字长的计算机上解方程组位字长的计算机上解方程组 粗渗兜抬匠蛮膀震眷夹体贫康吨南珍赌竖梨堪武滇募基斯锗伪颐着霹杯棚第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程12实用数值计算方法3.1.3 现给出一般情形的估计式现给出一般情形的估计式 设 则可以证明以

8、下估计式 其中 可见，可见，k(A)近似表示了方程组求解的误差的近似表示了方程组求解的误差的 相对放大率相对放大率虹诬庚累蜡汀求酞斩夜殴筑呕帧飞窜毒黎霓弯芽嘿琉犀怂绊夯弧虚戴叭笼第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程13实用数值计算方法3.1.3 换言之， 的大小 表示问题的病态程度 k(A)称为计算问题（称为计算问题（3-2）的条件数）的条件数 Condition Number 现在再看前例：豹鸦蔓苹茂恋傲漆酿肩兰爵扒骤彭饲庸评靶叔义吉学八溉辣瘁歧旺亥绊歪第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程14实用数值计算方法3.1.3 可见计算对象（3-1

9、0）是病态的。 应当指出：应当指出： 1. det(A)的值小未必会引起的值小未必会引起A病态病态 例如： det(A)=0.02，而A是好条件的。 2. 严格来说，估计式只给出了好条件严格来说，估计式只给出了好条件 的充分条件，但不是必要条件。的充分条件，但不是必要条件。 3. 由于数据误差在线性系统中引起由于数据误差在线性系统中引起 的固有的不可靠的使得任何过分的固有的不可靠的使得任何过分 精度要求的企图都是徒劳的。精度要求的企图都是徒劳的。拢芥系恕纷裔坠柄老努垦即添圈冠苔踪深凸数腿仔畜翁越裳黑基汰秉熔沃第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程15实用数值计算方法3.

10、2 3.2 直接法直接法3.2.1 直接三角分解法直接三角分解法（LU分解）分解） 考虑 AX=b A非奇异 在 Gauss 消去法中，每一步消元过程 相当于对A作一次初等变换。即左乘一个初 等变换矩阵T。 第一步第一步：翼肆却府颜奎砰款悲爹执吓姐促糕粳嗜省飞雁诚算箍历偷仗庙绒本镑篡原第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程16实用数值计算方法3.2.1 第第k步步 到k步以后A化为 当k=n-1时，A化为上三角阵U，即 因此饭极撑哨际彝抹盯化摇析绅孝烛厉人窃劈敖衣评丹汁碟洱腮析亢忍花狸菲第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程17实用数值计算方法3

11、.2.1 其中 为下三角矩阵，称（3-17）为A的三角分解。 由Ti性质，可以知亚狱撇啊夹寥钨余樱淌贿诉陡驹伴贞垫冈拱傈鬃晒蔓摹欺放崇幢潭薪阉仔第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程18实用数值计算方法3.2.1 Gauss 消去法的基本步骤消去法的基本步骤妻氦缆铃儒箩鄙反瘟酌钦唐桑癣惊涤泉添送却诽瘟蝗祷必盼纶铸镇磕娜狙第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程19实用数值计算方法3.2.1 所作的初等变换为所作的初等变换为 T1 * A = A1 T2 * A1 = A2 u 例例：设趋缠棠幕烷帆下吹诱族七病典翼捕碎锤文降七补歪鲤坟伪柠霖主学稀拟感

12、第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程20实用数值计算方法3.2.1 则，它的则，它的LU分解为分解为：成霸清肄翱思阅羌藕掺体叫获呕猎睹卜三艳挨拣肢舆资孟枚煽下承烘坟杆第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程21实用数值计算方法3.2.1 如果有了LU分解。则解方程组就 变得非常容易了。因为 由于L,U都是三角矩阵，则Y,X 都可以很 容易从上面两式中求得。 如果预先知道A存在LU分解，则我 们可以直接把这种分解求出来。犊灌钨麦虎求蔚熔姚嚣谗玩赂永抗彦尚种量唆辟舟亡囚盂迎匣扛切挂汰芒第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程22

13、实用数值计算方法3.2.1佛垢氦芬决酝知籽伞灵裤樟点主潮鄂殆留柿瑞谅误决幌尼鱼算赏怎凑埠敛第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程23实用数值计算方法3.2.1 但是 Gauss 消去法并不是对任何 非奇异矩阵都能顺利进行。如如 我们有这样的结果：我们有这样的结果： 任何非奇异的nn阶矩阵A，总存 在一个排列矩阵P，使PA能进行LU分 解。 上述结果表明表明，非奇异矩阵总是 能进行选主元的Gauss消去法消去法。廷舰湿蛹控剑乍状劳狼凰溉键族功席载德乒亚凶僵沮硼增地遥蛹续锑传部第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程24实用数值计算方法3.2.1谐戳哲

14、砂伞蠕但测镰丫圆霍损泡虐烩宁话某约狐烛帘垛尧哈虹累缘嫂场韧第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程25实用数值计算方法3.2.1 为使 LU 分解标准化。把 U 改换成 DU 是可行的。其中 D 是非奇异对角矩阵。而 U 则为单位上三角矩阵。如 称 A=LDU 为矩阵 A 的 LDU 分解。 定理：定理：设设条腑阳贩刚铲谷乱损斡约羚寝夯蓬父疚狄郑引小香送课维婪龚粕滤疟洒伺第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程26实用数值计算方法3.2.1 表示 A 的各阶主子矩阵。那么，A 存在 唯一的 LDU 分解的充分必要条件充分必要条件是： Ak （k=1,

15、2,.,n）都是非奇异。 如 A 为对称正定，或者对角占优，则 A 的各阶主子矩阵均非奇异。 现在我们直接从 A 求 LU 分解： 设设矩阵 A 有 LDU 分解。记 LD=L。则则 A=LU，L为下三角矩阵，U为单位上三角。 这种LU分解称为 Crout 分解分解。 眷晴基妻祖迢匿搏宏娜利盎珍惭免觉寂觉榆割歧禾据早可燥抗酌霞颜婴坊第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程27实用数值计算方法3.2.1理乾景杠氢疫淘曰薪触弦摩傈迟休沼讫痹搽糠负衡谰烁驹呜袁悯家膛槽养第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程28实用数值计算方法3.2.1尉充哪浮贼蜒红嫂获

16、父恿仁铆褂楚蹲量摘果汀芥胜稽尚盂创乐比溯鼓滇征第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程29实用数值计算方法3.2.1关于关于L, U元素的存放元素的存放 从（从（3-22），（），（3-23）可以看出。）可以看出。A的元的元素素aij在计算出在计算出 或或 以后就不再有用了以后就不再有用了。毯产釉铱吹辕守堆腻侍欲夫恍雷吐肄戌饥葬壤侮潮属酮娩仪碧版吵誓祷情第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程30实用数值计算方法3.2.1 故L,U的非零元素便可以存放在矩阵A中的相应位置上了。 最后， A所存放的元素是： 容易证明：容易证明： 1. 即是Gauss消

17、去法消去法中各次的主元素。竞谨函阮淳态誉钙尉储盟攘妥糟案竿肪信蓬芽搐间熙药赘软分货绳丰辊旭第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程31实用数值计算方法3.2.1 2. 如果 A 的各阶主子矩阵均非奇异， 上述过程可以一直进行到底。 矩阵 A 除了以上介绍的 LU 分解以外， 还有一种重要的分解方法可以用于求解 线性方程组。即 QR 分解。 定理定理：任意矩阵 A，总是以分解成正交 矩阵 Q 与上三角矩阵 R 的乘积： 如果 A 是非奇异的，则在规定R的对角元 素的符号下，分解式是唯一的。 如果如果 ， 则则 Q 是正交矩阵炊罩讹银瞄运饿穷填嚏膳慧摈驼僧创故扔谆辕泪狡曙玩缆

18、制乏逛战鸥辰焕第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程32实用数值计算方法3.2.1 常见的有 Householder 正交三角分解 有了正交三角分解以后，解方程组 就变得非常简单： 用 Householder 变换进行分解。从而 求解线性方程组的过程是非常稳定的。也 不必选主元。特别在方程性质不太好时， 更显其优越性，但计算量大。 Householder 正交三角分解还有其他用途。抒搞讥疑灾靳蝉执二祷枫氨隔揉芜搏傀往趣撩囊泌袒剩娇唱丁迭衰萌帘史第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程33实用数值计算方法3.2.1 PROGRAM EXAMPLE D

19、IMENSION 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甲耪骨甘巧拟赘辗蛤付圈瘁病敦锡郎拭套殊到鹊难署苦捅肇淆庸民亩观素第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程34实用数值计算方法3.2.1

20、亩脓叮黔脐限盖馒缸臼躯峙谚褐牛绽腋聪拓壹往琶瓜魏侵否卸稍函盖微怯第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程35实用数值计算方法3.2.1程序手稿原程序文件目标程序执行程序输出结果编辑（WS）编译（F77）连结（LINK）执行（程序名）库修改图3.2 程序调试流程图宜销见奋苔梯镭堵座贮穴妮日棺咎配健年遂周菊佃摹催最篱臂剃寨剧挖汗第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程36实用数值计算方法3.2.2 迭代改进迭代改进 由前面讨论，我们知道，由于各种原因， 特别是方程组本身的病态，将会导致解与真 解之间的误差不能达到令人满意的程度。有 各种处理病态方程组的方

21、法。这里介绍一种 简单实用的方法。它还可以用于一般方程组 的高精度求解。该方法的基本思想是利用迭该方法的基本思想是利用迭 代逐步改善解的精度代逐步改善解的精度（关键在于在迭代过程 中有些运算需用双精度进行） 迭代改善过程的框图如下：凝既撑食崩群甄促琳切茶输煎言麓澡俭褂算琴复豌吧巡辩及扮歌甲戳弄皖第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程37实用数值计算方法3.2.2是否图 3.3 迭代改善过程琉枝淖藻铸火丙蓑愚拟渔驮宋公欠搏脉翰玛怂炎筏侣土痈卖钎这慈竣娟垫第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程38实用数值计算方法3.2.2 由上图可知，迭代改进的计算

22、，只要 在开始时作一次三角分解。以后只是反复 求解三角方程组就可以获得解的改善。 关于解的改善的程度有以下结论：关于解的改善的程度有以下结论： 假设在浮点数的尾数是 t 位（二进制）的 计算机上用消去法计算。A 的条件数为 一般可设 则：经过一次迭代，解的精度近似地改善 了 t-p 位。因此迭代次数 k 满足 k(t-p)t 就够了。 或近似地用估算式： 毡揩搜揩拽医陪尘昔估媳湃自肠窟肠了醇鬃赡依匝粉灯涧禾祈昼生但亮叹第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程39实用数值计算方法3.2.3 奇异值分解奇异值分解（SVD） 解方程组时，常常会出现奇异或十分 接近于奇异的情况。

23、用通常的Gauss消去法 或者LDU分解法难以得到满意的解。对这 类问题，我们有一个有效的方法，它叫奇奇 异值分解法异值分解法 Singular Value Decomposition 它不但可以诊断出问题所在，而且有时能 给出一个有用的数值结果。 SVD方法基于下面这个线性代数定理， 由于定理本身不是我们研究的重点，这里 不加证明。蛛药请疆柜檬孩孤拎炭寇嫩寐桑糜招蓉牌桅杏同广窖幂剃疏绕岳环欠督殊第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程40实用数值计算方法3.2.3 定理：对任意MN矩阵A，这里MN，它都可以分解成下列形式： A=UWVT其中：U是MN列正交矩阵； V是N

24、N 正交矩阵； W是NN对角矩阵。且对角元素非负。即：渣朽嘛悄也呛漓稽印坚冶拥实囱轮可乱下遂肤芳邮修瘴舟警包焰弛案台战第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程41实用数值计算方法3.2.3 由于V是方阵，故它还是行正交即 不管矩阵A是否奇异。SVD分解都能做到。而且它“几乎”是唯一的。即允许U，V的列进行变换并进行W相应交换的前提下是唯一的。 如果A是NN方阵，则U，V，W都是方阵。且分解式可写为：席畜傍户星弥皇愧慧骑付廖衰哗绪东咀蛇靴芒郊截霉淋庚蜘末粗炭符食乎第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程42实用数值计算方法3.2.3但是，如果其中有一些

25、 或十分接近于0，即A奇异或接近奇异，那么A-1就难以求得。因此，SVD分解可以通过判断 的大小来分析A的性态。 当A是奇异时，我们就考虑在某种意义下的解。古搞墟斗对啮责吧擒禹吱腔猫盅倚井鄙京叉淹袖拯浅黍肩荆妓寨哮逛限枯第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程43实用数值计算方法3.2.3 由代数知识，有 当 rank(A)0; 秩N; 但可以证明：零度秩零度秩。现在再看看分解的意义。甜燥烟址屉蛙傣惦东诱旋甩轩刷法汐兑焚喜介拽斑膨蛙冻敌侩渝娥滨嚣臂第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程45实用数值计算方法3.2.3分解事实上分别构造了的零空间和域的

26、各一组正交基。由所有 对应的的第j列向量是张成域的一组正交基。由所有对应的的第j列向量是张成零空间的一组正交组。现在考虑（3-24）的解。如果 的域， 则方程有无穷解。因为零空间的任何向量的佰仑桃坐为擎祝涅甫隐趾堂商龙端驻蹦树慨攒府突府维僵隋长舒元崭偿丫第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程46实用数值计算方法3.2.3 故任意的域中向量b可以由 线性表示， 即这样的 张成域的一组基。（1）从藤矩纽档享攀缎炭圈魏政迢敖高瓢既多怜午栖求厚杆丈盆灵起卿犹品盐第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程47实用数值计算方法3.2.3（2）售默晃痴岂默帅婉讨娟

27、挫陀铱充杭肪溪杠鲸端君纷荷兑祝巍缨抉欲蝴缆换第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程48实用数值计算方法3.2.3什阶耀蜜旷镰犬荷对头挪龄吐推训炳缩渊匙黍努三傻圭祟旭丧臀污研惊媳第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程49实用数值计算方法3.2.3沂龄钩阶域饲扑逞待獭啦据渡继捅檬缴闯弦南枚卒纠越趴颗快梧踌旗芋雁第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程50实用数值计算方法3.2.3竟抄紧妥碌牟纲活摹涨汐惨仕待帚荣炕咯洪宗琼员回挛逆或稚愿冈麦翔乳第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程51实用数值计算方法3.2

28、.3以上讨论用图表示如下：A图图 3.4 解空间示意图解空间示意图洒削赋奇被悬敷酣踪枚梨竖井鱼缉绎樊泼显唤吩堰鳃部慌援慌今吼痞捡六第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程52实用数值计算方法3.2.3例夕剪簧颈斌札角持厉峰祈箱锄状捉歹痕二扒惩溪酵只茂宙卵歪聋贺狭廉第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程53实用数值计算方法3.2.3峰巍湾供掐彦账驴晤骂垢易吨反腿如拜再所崎贼诽刷妄螟腰盂峪页寻牛浆第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程54实用数值计算方法3.3 迭代法迭代法 迭代法适用于解高阶稀疏非病 态方程组。它只需要存储非零

29、元素。 但对有些问题，迭代可能发散 或收敛很慢。3.3.1 Jacobi 迭代法迭代法 设有方程组 其中A是NN非奇异矩阵。故有唯一解。 把（3-26）改写成迭代形式鲸探膨身亨悦财赢汛添寝哑妄托撑辊纽弛忌淋弧痰桃姨笺娇加配菇圃淡腆第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程55实用数值计算方法 于是设X(0)是一个任意的初始迭代向量。 代入（3-27）的右边，得到新的向量记为X(1)： 一般地有： 我们得到向量序列 如果 收敛于 X ，即： 则向量 X 是（3-27）的解。 现讨论解的求法及收敛性3.3.1痢瑶蓟衅惟呢周说春概馋恰怕竣阴冒活箱腆担峪贫谤钨攘硫绽杏李蔓屿尿第三章

30、线性代数方程组第三章线性代数方程组浙江大学研究生学位课程56实用数值计算方法3.3.1 设矩阵A的对角元素 。记 则D非 奇异。将A表示成和式 其中：锹辑尹母幢铆矫字情酪萝国胺俭啦旦楞蛇奢诬巡丸厌伐羊粳傀葵戳蹿受养第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程57实用数值计算方法3.3.1 利用（3-29）式的矩阵符号。Jacobi 法可以 表示成： 这里B 是 Jacobi 迭代矩阵。其定义为 Jacobi 方法收敛的充要条件是： 迭代矩阵B的谱半径睬誊涂柱伴思油淳备痹小饲监偶漠殖巾倘终夹匀篡华齿胳迫羌触叹鸡相荔第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程5

31、8实用数值计算方法3.3.1邢咋吴鞠沼善缨创囚蹭窃圈剔剔构潭岸须盯右璃忙摄遁帆迈茹还芋将走亨第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程59实用数值计算方法3.3.1 现在讨论一下Jacobi方法的收敛速度 的快慢及影响速度的因素。腥苦嚎仓霸貉舱馈摩卢项冉赵曰书喷许沟嘉框蝉应陵缚铝萨弓育烯豌篱苑第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程60实用数值计算方法3.3.1 （3-34）式可作为误差估计式，并且说 明|B|越小，x(k) 收敛越快。（3-35）式说 明了只要|B|不是很小，当相邻两次迭代向 量x(k) 和 x(k-1) 很接近时，解 x* 和 x(

32、k) 也是很 接近的。因此，可以用 | x(k)- x(k-1)| 作为 迭代终止的判别式。这个结论对逐次逼 近法也成立。 特别，应该指出，以上讨论的收敛性 及收敛速度均是对一般迭代式（3-27）而 言。因此，其结论对以后要讨论的G-S迭 代法和SOR法也成立。把烁汲耍素蝉照爷阶锌顿尼愿蓝瓦录宗宾锄肮守馆昌卜肛撅肿橙啊溅咸虎第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程61实用数值计算方法3.3.1 Jacobi 迭代法的计算步骤：迭代法的计算步骤：甸约您才普手掘腮副隘架角栖渊生么挤募宠秃劈号匝箔颗屹颅绦料腕饼污第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程62

33、实用数值计算方法3.3.2 Gauss-Seidel 迭代法迭代法。 G-S迭代法的基本思想来自Jacobi 迭代法。只是迭代矩阵B不同。乘韩究疑铃瓤均氓崎朔丑捅摹邑瘪冈篙纪国桅派跺呐滴搬己谎懦酞锹鹿镭第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程63实用数值计算方法3.3.2 这就是 Gauss-Seidel 迭代格式，它 也可写为： 若用（3-29）式记号，则G-S迭代式可 表示为： 或 其中抹翠散雄踪剔廷虱夷锹迄衡船萎救呛敝干蝗隐余惠畜箩撂茅衰弊衅刃哼鹤第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程64实用数值计算方法 有关收敛性和收敛速度的讨论完全 与

34、Jacobi 方法相同，只是迭代阵为L。3.3.3 逐次超松弛（逐次超松弛（SOR）法）法 SOR法定义为法定义为： 笔砂卸阉呢皿授佣失挑招驱跑若辛偷棱让辜哟趣譬漂猿哪也峙捎肄杀鳃杀第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程65实用数值计算方法3.3.3夜蔓坝琢废乎障滥倘可谜孩抱馁抒冗科菇所伏肯资寸让垢虏堑式八赠迸宋第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程66实用数值计算方法2.3.13淤挠韩岁骨薄齐咏颅厩喝潮网级胺铡舷且功喘七直愤偷欺悯被雇目欣型牺第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程67实用数值计算方法3.3.3 三种迭代法

35、的比较：三种迭代法的比较： 1. 一般情况下，J方法与G-S方法比较 并无优劣。收敛情况与速度均不一定。 例：拢抚该财倍邑瞒爪珐是违中韩镑洪缉喳摊拎安屁译凛柏界典下谷层歇经倒第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程68实用数值计算方法3.3.3 2. 但是具有相容次序的矩阵，在相同 精度要求下，迭代次数分别为： Jacobi 方法：1154 G-S 方法：578 SOR 方法：59 可见对这类矩阵，G-S 法比J方法快一倍， 而 SOR 法的收敛速度可提高一个数量级。 最后介绍一类对于三种方法都收敛的最后介绍一类对于三种方法都收敛的 矩阵。矩阵。先定义可约矩阵和对角占优矩

36、阵：蚤讼葛妊澄燕繁驰瓷切荣徽图虫阴咽遮愚盅课弟山恼贵炔左泡山矛西悟杀第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程69实用数值计算方法3.3.3 (1). 称n阶方阵为可约矩阵，如果存在n阶 排列阵P，使得 其中A11为r阶方阵，A22为（n-r）阶方阵 不是可约矩阵就是不可约矩阵 (2). 称 n 阶方阵A是对角占优矩阵，如果 若上式严格不等号成立，则称A为严格对角 占优矩阵。势椭簧勺爆峻铸辈钡瘁增曰重娥翁秃咨诗朽浅湃忧惠较持佑旺烘盟氢红凶第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程70实用数值计算方法3.3.3 (3). 称A是不可约对角占优矩阵。如果A是

37、不可 约的且对角占优，而（3-42）式中至少对一 个 i 有严格不等号成立。 我们有如下结论我们有如下结论： 1. 若A是严格对角占优或不可约对角占优 矩阵，则A非奇异。 2. 若线性方程组系数A是上述矩阵，则： 1）J方程和G-S方法都收敛。 2）当 SOR方法收敛。咯把谨久萨段毕拙亨尾遣膜拂嚷臭斟羌俺身动感灶嘘烃鹿磷避撞泣角饥诲第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程71实用数值计算方法 3.4 稀疏矩阵稀疏矩阵 前面介绍了直接法和迭代法。但是实 践中如何选择计算方法是一个很复杂的问 题。需要考虑的因素很多，主要有： 1.方程组的性质；（病态、对角占优、正定等） 2.

38、相类似问题出现的次数； 3.方程组的阶数； 4.计算机的容量、字长、运算速度等； 5.系数矩阵的结构；（稀疏、三对角等） 6.对结果的精度要求。灼渔蚂耸馁拽汇蛊港宇侣他活舌苗也共雅欲呸渠彩慎镇网膏刺卉网赁盯骤第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程72实用数值计算方法3.4 迭代法迭代法是解超高阶线性代数方程组 的重要方法之一，但是它也有缺点： 不适合解病态问题； 精度不高； 收敛速度依赖于加速因子的选取； 收敛性不能保证； 所需乘除运算量大。 在这些方面，相对来说，直接法运算 步骤一定，运算次数有限，精度高。对解 大型稀疏矩阵问题可以利用和保持系数矩 阵的稀疏性来降低存

39、储容量和缩短计算时 间。挽雪茵姆撤固桓寄予赵疟查猿墅朋弥本损筹尊聋囚疙就颧吻称钢通粪酚痰第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程73实用数值计算方法3.4.3 但是，为了保持系数矩阵的稀疏性。必须 使用特殊的计算方法和高级程序设计技术。 近年来在这方面有较大的发展。其优越性 大大超过了迭代法。 在这一节里，不详细介绍计算方法， 只给出一些常用的标准稀疏矩阵形式。同 时给出一种一般稀疏矩阵的存储结构。这 一节里还给出一个有效的计算公式。梧利铺户韦簇潜农巡教川幂船逮删挑姑翟颗辕吾嗓悔滓弄选父赤逢沂窘了第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程74实用数值计

40、算方法 3.4.1 稀疏矩阵的结构和存储稀疏矩阵的结构和存储 从本质上讲，解稀疏问题的方法与 一般Gausss消去法LU分解法并没有什么 不同，只不过前者更注重于运算过程中 对零元素填入量的控制。 稀疏系数矩阵问题的直接法必定依 赖于矩阵的稀疏形状，下面列举的是常 见的标准的稀疏矩阵。 1.稀疏矩阵的结构蕉径炳怂槐松潦鞠嫡掠免她禾沮盘刑罕胎虹挠滥蹋妻圭烂浑阳周琶重扫枕第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程75实用数值计算方法3.4.1带 对 角块三角阵块三角阵单边块对角双边块对角eacdb单边块三角f图图 3.5 ?径逗徒蛊摈但综邻冠钒丁赡抚孽削涌瘤士名艾吊枉悟鼠绽荆予

41、擅褥侧峡拳第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程76实用数值计算方法3.4.1双边带三角单边带对角双边带对角其他其他kgijh图图 3.6 稀疏矩阵的形式稀疏矩阵的形式办失蔼岛颧焙恒攘累炙乞玲杭歪涌柬悔愈肛绎辅另湍臭蜂喊井漂军绣臼竞第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程77实用数值计算方法3.4.1 2. 稀疏矩阵的存储稀疏矩阵的存储 一般矩阵的存储方式有两种：满存和 部分存储。稀疏矩阵则采用后一种方式。 稀疏矩阵的种类不同，所采用的存储 方法也不一样，但是不论采用什么方法，它 的标准有两条： 1）节省存储空间 ； 2）存取方便，即节省存取时间。

42、 存储方法的选择一般要根据矩阵的 种类和对程序的要求在上述两个标准之间 权衡。偷州羞殿苇刮鳞拄凤谋帛怜辨嵌袭妈摊惭克惨鞘蓝冤替镑庞粘肛晤权馋壁第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程78实用数值计算方法3.4.1(1) 带对角矩阵的存储带对角矩阵的存储图图 3.7 带对角矩阵的存储方式带对角矩阵的存储方式饰渭剖面吸熔偷果瘪格萨醒胀椭妖逻快迫既纷岭吸秦艺禽泊滩版矢晶眺雨第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程79实用数值计算方法3.4.1(2)块三角型矩阵的存储块三角型矩阵的存储 H1i1iLil+1N1H2 N2 Hl+1aijHl NlID2LiL

43、图图 3.8 块三角型矩阵的存储形式块三角型矩阵的存储形式镍郭深哨售另娥樟炔壮崭执巷围搏有轧罗决早八农尾琼健裂葬押注淀仓旁第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程80实用数值计算方法3.4.1(3) 一般稀疏矩阵的存储一般稀疏矩阵的存储B：一维存储非零元素（按行）一维存储非零元素（按行）（m）（m）JA：B中相应元素所在的列号（中相应元素所在的列号（A中）中）IA：每行第一个非零元素在每行第一个非零元素在B中的下标。中的下标。（n）网园亢奏悍肝梭纶葫挺事嵌当肆惟耸印筋磺捆版贯妹篇埔片邢优洁暗禽毡第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程81实用数值计算

44、方法3.4.1 例如：图图 3.9 矩阵矩阵A非零元素存放的一般形式非零元素存放的一般形式畦氢跑金裴兵歹完茸戏耪绕代觅坎履惜典象器蜂黔蛮皇辗取毅绳挡浦跺铝第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程82实用数值计算方法3.4.1 (4) 对称矩阵的存储对称矩阵的存储 因为 故只要存储 即可。 任何形状的矩阵，包括稀疏的 和非稀疏的，只要是对称的。 均可节省将近一半的存储量。皋丹希板膀表姿毡摔十铺农拉曝件瓮悍造蟹述刽坐曙斑蛊蝇簿午单容虑愧第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程83实用数值计算方法 3.4.2 Sherman-Morrison & Wood

45、burg 公式公式 我们知道，矩阵求逆问题等价于解 一个线性方程组。如果我们已经得到矩 阵A 的逆矩阵A-1。现在想在A上作个小 小变动。如：一个元素、一行、一列， 或者部分元素，那么是否可以不再做复 杂的求逆运算，而只是在原来的A-1的基 础上作些适当的运算就可得到变动后的 矩阵的逆呢？回答是肯定的。 假定矩阵变化为：醋奇骗臼捐葬略霖歹决窜砾卤绥龋嘛慢舀夯椽彼谓扩蛔龋旁惭酝囤号论欣第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程84实用数值计算方法3.4.2 附带复习一下内积，外积的定义：内积、外积均有结合律（叉积）（点积）(或：uv)户赶柿硷细愚要排营蒂闽销财赞颁汕缮傲译曰题

46、戊晒颧丑寐玫涯还篮赁效第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程85实用数值计算方法3.4.2 这里 uv 是外积，它表示A的变动。 Sherman-Morrison公式给出了一个计算 的方法： 这里 从（3-44）（3-45）式可以看出，给了 A-1和u，v只需作矩阵的乘积运算和一 个向量的加法：韧笔巢莫佛屿饵柬像飘辜郧擒壁拒谣余钒拱瞩九遁饯缚遮米赤丫欺姨吊椭第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程86实用数值计算方法3.4.2 Sherman-Morrison公式可以直接应用 于一类稀疏线性方程组上。如果我们已经 有一个有效的算法得到矩阵A的逆（如

47、A 是三对角阵。或者其他标准稀疏形状的 矩阵），那么要解A的稍作变动的矩阵 决定的方程组，只要运用一次或多次 Sherman-Morrison 公式即可。 但对有些稀疏问题，这个公式并不能 直接运用。理由很简单，因为A-1不可能在 机器内部全部都储存着。在实际运用中这 个公式还有变化。嘴瘴习擒舆巷祷痴冷髓岛执洋融夹翁守赏存砰榜巳英泛沤踩更厘渝甚泣寄第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程87实用数值计算方法3.4.2 变化一：变化一：求解求解线性系统问题：求解求解线性系统问题： 首先可以对A用有效的方法解两个辅助 问题： 得到了向量y和z后，（3-48）的解既是：钥酚少拎

48、扶图怯碱死并吕灌拂悄齿弗趴闹演声涯菇宫德李傅越灾承句哀怯第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程88实用数值计算方法3.4.2酸胃辩爪爽锭厨力畏止痢捣砾每圾贞镶日觉嫁旬碾雕炉步贞晨瘁乓雪哼祥第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程89实用数值计算方法3.4.18 变化二变化二. 即即Woodbury 公式公式 当在标准稀疏矩阵上添加的元素不只 是一行或一列时，我们就不能简单地重复 上述过程。因为新的 A-1 并没有存储下来。 这时要用 Woodbury 公式： （3-51）式主要是计算 因此可以看到，（3-51）式把一个NN阵求 逆问题转化为一个P

49、P阵的有求逆问题。由 于 PN, 故问题得以大大简化。纺浩俭梭跃良寐吃驴蝴桩宋区帮捕堪剧辱千殉颧谊禹凡良声理希穗信荫厌第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程90实用数值计算方法3.4.2 Woodbury公式和连续地运用Sherman- Morrison公式的联系在于： 如果记则有则有展真卫制莽诀祸请惋黎人卧种搽核借共臆铀俩蕉亮买完涪剩璃惩呐喜罕触第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程91实用数值计算方法3.4.2 上式表明，如果已经求得A-1，计算 的方法有两种： （1）利用（3-51），计算一个 PP 的逆矩阵。 （2）利用（3-47），执行

50、P次。 如果A-1没有存储，则解下列问题 的步骤是 (1) 解P个辅助方程组： 得矩阵拓双阐曰谰撩扒畅鸦枪暇及衬迪史旬雌闰奋透茨拳摄茅坚君球谷谎班讶缺第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程92实用数值计算方法3.4.21 (2) 计算PP矩阵的逆 (3) 再解辅助方程组 (4) 得方程组（3-53）的解 因为：没嘿械猿屏渡滩排预伏羽品冻青去泪问陕麦花习粮添酞棕想管惠停临煞切第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程93实用数值计算方法2.5 特殊矩阵特殊矩阵 在很多问题中，我们会遇到特殊类型 的矩阵。对于这些具有特殊性质的矩阵， 不仅存储方式上应予研

51、究并很好利用其性 质以节省存储，在计算方法上也要利用它 们的好的性质以减少运算量和提高算法稳 定性。 在这一节里，我们研究几种特殊矩阵， 对称、正定、带状，和三对角矩阵。 由第二节的定理知，若 的各阶主子式仗使疟闸潍蜂谰牧梦塔慧颅二缮玲掠趋几端旗髓爆林骨末诞抛菇坝丛判千第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程94实用数值计算方法3.5 同样我们可以证明，若对称矩阵的各阶主子式其中是单位下三角阵，为对角矩阵。这个分解叫做对称矩阵的分解。对一般非奇异对称矩阵，则存在排列矩阵，使故可通过选主元方式达到分解。解线性问题可转化为解三个简单的线性问题：兽迪坠罚蒸佳抢素蔚章凭住刷观健罕

52、伏玛梨蓝元高恒踢岩侠嵌牧虱淆敝索第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程95实用数值计算方法3.5如果是正定矩阵，则是对称的并且的各阶主子式不等于。因此，存在且故可令：从而 这里是下三角矩阵。这种分解叫做对称 正定矩阵的平方根分解。森节吟叮镶了蠢妄恢项棍躯卢醇丈防粱碑精削剧朋桅箍理颂像算拍剁畜趁第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程96实用数值计算方法3.5墨绊钾缺悟峦夸菲与蝇玩谱强叁芝次时哭鄙办费琐慷柬风尧作设扑过棕镐第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程97实用数值计算方法3.5 平方根分解的算法如下：平方根分解的算法如

53、下：锡械揭舅唯盏曹访半洗藩冕炮池筏兄见镀廓绵壳滚鼻跳候撞选呸铆输凌哄第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程98实用数值计算方法3.5这个算法的另一个优越性是不用选主元不用选主元。 但是从（3-60）知道，这个算法在求 要进行平方根运算。为了避免开方运算，有时我们仍要用分解。在 3.5 中，引入了带宽为2m+1的带状矩阵。他们满足： 当 带状矩阵当 mn 时才有意义。带的宽度依赖于方程组未知量的次序和方程的顺序。郝冤藐嘱棘嘘易森园嚼槽徒列曰凌管笛殊嫩镣鸳鱼风霄糜泄柳受荣庶亦迷第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程99实用数值计算方法3.5 例如，m

54、=1 的三对角方程的矩阵若的相邻任意两行交换一下，则带宽从增加到。对带状矩阵，有以下定理：硬闪扎苫恬俐停脆烃萧正返遥初滞确强选此籽杂抛倪幼谬后幼弱着悯益几第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程100实用数值计算方法3.5我们在上述定理中假定的分解存在。事实上未必总是如此，可能需要交换方程。这就可能要增加带的宽度。但不可能增大倍。但有些实际问题中遇到的带型矩阵性质是比较好的，并不需要选主元。三对角矩阵（m=1）在带状矩阵中占有重要的位置。若（3-62）中的各阶主子式，则可用追赶法很方便求解Axb。所幸的是实际应用中，有很大一类矩阵是对角占优矩阵，因而各主子式。共咳斧乒胺着

55、邻坛迪傈稿舰跳扳知税讣娇禾磕俐逸浅履袒蚊搅毖雅撕绸祸第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程101实用数值计算方法第三章习题祁腐慌锗储频意酪萝邹骄羊喉皿潍徽帖抽准尘涧咕享虱职刑屹聘拙犹驭寓第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程102实用数值计算方法威聂绒虐裴竞惭呈堵再柬霜李无儡阑抖请婚慕奢毡辜肺固荚到眺蝗秒芋王第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程103实用数值计算方法花达占的奄诌右椰杉历简雕霓皿诲犁樱颖访批鉴淘渐遍泼敦码侨崭蓟泄倡第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程104实用数值计算方法返像舍蘸吞膳敦盼蠕鉴祁华镣郭补郸沿精罕刁馏癣洞郝填施瞻怕锗蜡漫肝第三章线性代数方程组第三章线性代数方程组浙江大学研究生学位课程105实用数值计算方法