第三章 线性方程组数值解法

§1 问题的提出 线性方程组： 系数矩阵、未知向量、常向量： 矩阵表示：

增广矩阵表示： 克莱姆法则：由线性代数的理论，对于方程组，若系数行列式不为零，则有唯一解

解方程组需要计算n+1个n阶行列式，每个行列式的乘法运算次数是 n! ,因此总的乘法次数是（n+1）! 。 克莱姆法则计算工作量测算： 解方程组需要计算n+1个n阶行列式，每个行列式的乘法运算次数是 n! ,因此总的乘法次数是（n+1）! 。 若n=20,则（n+1）!大约是 5.109*1019, 这在每秒运算1010的计算机上要连续计算162年。 线性方程组的解法分为两类： 1. 直接法：（适合于中小规模的方程组） 2. 迭代法：（适合于大规模的方程组） 高斯消去法 追赶法 列主元高斯消去法 雅可比迭代法 高斯-赛德尔迭代法

§2 消去法 回代求解 3.1 三角方程组的解法 Ux=y，U为上三角矩阵 （2.1） 若det U≠0,即Uii ≠0(i=1,2,…,n),则（2.1)有唯一解： 回代求解

回代过程所需运算次数：

3.2 高斯消去法 思路：将一般线性方程组Ax=b转化为三角方程组Ux=y求解，即消元。 过程：

第1步消元 实质：矩阵行变换，将第1行的(-li1)倍加到第i行上。

矩阵观点：

第k步消元：将第k行的(-lik)倍加到第i行上。 akk(k)≠0为主元

矩阵观点：

第n-1步消元: 最终得到与原方程组同解的三角方程组。

高斯消元法 = 消元 + 回代 LU分解

高斯消元法运算量分析 第k步消元需 次乘除运算， 次加减运算。 消元过程运算量： 高斯消去法总运算量： 运算量对比：取n=20，高斯消元法需6284次,而克莱姆法则需5*1019次。

例1. 用高斯消去法解线性方程组

3.4 列主元高斯消去法 出发点： 解决办法：1. 换行 2. 选列主元

选列主元： 优点：保证舍入误差不扩散，方法稳定。

例2. 用列主元高斯消去法解线性方程组

作业 P81习题3：第1（2）、3（2）题

§4 向量范数和矩阵范数 出发点：借助范数概念，度量向量和矩阵的大小，用于判断迭代法的收敛性及误差分析。 4.1 向量范数 非负性 齐次性 4.1 向量范数 非负性 齐次性 三角不等式

4.2 矩阵范数

作业 P83习题3：第12、13、14题

§5 迭代法 基本思想：类似于方程求根。

5.1 迭代法及其收敛性

定理3.2 （充分条件判别法） 给定方程组 ， 若 ，则：

定理3.2 （充要条件判别法） 给定方程组 ， 则迭代格式 对任意初值 都收敛的充要条件 为： 。

假设方程组 的系数矩阵 的对角元 5.2 雅可比（Jacobi）迭代法

5.2 高斯-赛德尔（Gauss-Seidel）迭代法

定理3.4 （充分条件判别法） 对于线性方程组 ， （1）若A为严格对角占优阵，则雅可比迭代法和高斯-赛德尔迭代法均收敛； （2）若A为对称正定阵，则高斯-赛德尔迭代法收敛。

作业 P83习题3：第16、17题任选一题 第1~3章作业上交 上机： P221~238

人物介绍 雅可比，C．G．J．(Jacobi Carl Gustar Jacob)1804年12月10日生于德国波 茨坦；1851年2月18日卒于柏林 。数学家，对哲学、古典文学和数学都颇有兴趣。 现代数学中的许多定理、公式和函数恒等式、方程、积分、曲线、矩阵、根式、 行列式以及许多数学符号都冠以雅可比的名字 雅可比最重要的贡献是和挪威数学家N．H．阿贝尔(Abel)相互独立地创立和发 展了椭圆函数理论； 在柯尼斯堡大学的18年间，雅可比不知疲倦地工作着，在科学研究和教学上都 做出惊人的成绩．《纯粹和应用数学》杂志(Crelle’s Journal fürdie reine und angewardte Mathematik)上，平均每期有三篇雅可比的文章．打破了常规的 教学方法．他还开创了学术讨论班，这在当时数学界还是很新奇的事物． 1848年革命期间，由于他在一次即席演讲中得罪了王室而失去津贴．当维也纳 大学决定聘请他时，普鲁士当局意识到他的离开将会造成的损失，因而恢复了 他的待遇． 1851年初雅可比在患流行性感冒还未痊愈时，又得了天花，不久去世．

卡尔·弗里德里希·高斯（JohannCarlFriedrichGauss）（1777年—1855），生于 不伦瑞克，卒于哥廷根，德国著名数学家、物理学家、天文学家、大地测量学家。 高斯被认为是最重要的数学家，并有数学王子的美誉。 3岁时便能够纠正他父亲的借债账目。 9岁时采用50对构造成和101的数列求和方法计算1到100的和。 12岁时，已经开始怀疑元素几何学中的基础证明。 16岁时，预测在欧氏几何之外必然会产生一门完全不同的几何学。 导出了二项式定理的一般形式，将其成功的运用在无穷级数，并发展了数学分析 的理论。 19岁时，第一个成功的用尺规构造出了规则的17角形。 63岁的高斯开始学习俄语，并最终掌握了这门外语。 1855年2月23日清晨，高斯于睡梦中去世。 在他死后，有20部这样的笔记被发现，即使这20部笔记，也不是高斯全部的笔记。 下萨克森州和哥廷根大学图书馆已经将高斯的全部著作数字化并置于互联网上。