数值分析线性代数方程组的直接法

数值分析线性代数方程组的直接法第1页，共51页，2023年，2月20日，星期六问题驱动：投入产出分析

投入产出分析是20世纪30年代由美国经济学家首先提出的，它是研究整个经济系统各部门之间“投入”与“产出”关系的线性模型，一般称为投入产出模型。国民经济各个部门之间存在着相互依存的关系，每个部门在运转中将其它部门的成品或半成品经过加工（称为投入）变为自己的产品（称为产出），如何根据各部门之间的投入-产出关系，确定各部门的产出水平，以满足社会的需求，是投入产出综合平衡模型研究的问题，试讨论如下简化问题。

设国民经济仅由农业、制造业和服务业三个部门构成，已知某年它们之间的投入和产出关系、外部需求、初始投入等如表6.1.1所示（数字表示产值，单位为亿元）。第2页，共51页，2023年，2月20日，星期六表6.1.1国民经济各个部门间的关系表中第一行数字表示农业总产出为100亿元，其中15亿元农产品用于农业生产本身，20亿元用于制造业，30亿元用于服务业，剩下的35亿元农产品用于满足外部需求。类似地可以解释第二、三行数字。第一列数字中，15亿元如前所述，30亿元是制造业对农业的投入，20亿元是服务业对农业的投入，35亿元的初始投入包括工资、税收、进口等，总投入100亿元和总产出相等。假定每个部门的产出和投入是成正比的，由表6.1.1能够确定这三个部门的投入产出表，如表6.1.2所示。第3页，共51页，2023年，2月20日，星期六表6.1.2投入产出表表中的第一行，第二列的数字表示生产1个单位产值的制造业产品需要投入0.10个单位的产值的农产品，同样第三行、第一列的数字表示，生产1个单位产值的农产品需要0.20个单位的服务业产值。表6.1.2的数字称为投入系数和消耗系数，如果技术水平没有变化，可以假设投入系数是常数。已知投入系数如表2.1.2所示，若今年对农业、制造业和服务业的外部需求分别为50、150、100亿元，试计算三个部门的总产出分别为多少？第4页，共51页，2023年，2月20日，星期六若共有n个部门，记一定时期内第i个部门的总产出为xi,其中对第j个部门的投入为xij，满足的外部需求为di，则

(6.1.1)记第j个部门的单位产出需要第i个部门的投入为aij，在每个部门的产出与投入成正比的假定下，有(6.1.2)投入系数即为aij，将(6.1.2)式代入(6.1.1)）式得方程组

用矩阵表示为或(6.1.3)因此投入产出模型最终可归结为求解线性方程组的问题，下面介绍求解线性方程组数值方法。第5页，共51页，2023年，2月20日，星期六AX=b（3.1）

第6页，共51页，2023年，2月20日，星期六线性方程组数值解法的分类直接法（适用于中等规模的n阶线性方程组）

◆

Gauss消去法及其变形

◆矩阵的三角分解法迭代法（适用于高阶线性方程组）

◆Jacobi迭代法

◆

Gauss-Seidel迭代法

◆逐次超松弛法

◆共轭斜量法第7页，共51页，2023年，2月20日，星期六§1高斯消去法1．三角形方程组的解法---回代法（3.2）（3.3）

第8页，共51页，2023年，2月20日，星期六2．顺序高斯消去法

基本思想：通过消元将上述方程组化为三角形方程组进行求解。第9页，共51页，2023年，2月20日，星期六消元公式回代公式第10页，共51页，2023年，2月20日，星期六顺序Gauss消去法可执行的前提定理1

给定线性方程组，如果n阶方阵的所有顺序主子式都不为零，即则按顺序Gauss消去法所形成的各主元素均不为零，从而Gauss

消去法可顺利执行。注：当线性方程组的系数矩阵为对称正定或严格对角占优阵时，按Gauss消去法计算是稳定的。第11页，共51页，2023年，2月20日，星期六3、列主元Gauss消去法计算步骤：1、输入矩阵阶数n，增广矩阵

A(n,n+1);2、对于(1)按列选主元：选取l使

(2)如果，交换A(n,n+1)的第k行与第l

行元素(3)

消元计算：3、回代计算第12页，共51页，2023年，2月20日，星期六4．无回代过程的主元消去法(Gauss-Jordan)第一步：选主元，在第一列中选绝对值最大的元素，设第k行为主元行，将主元行换至第一行，将第一个方程中x1的系数变为1，并从其余n–1个方程中消去x1。第二步：在第二列后n–1个元素中选主元，将第二个方程中

x2的系数变为1，并从其它n–1个方程中消去x2。第k步：在第k列后n–k个元素中选主元，换行，将第k个方程xk的系数变为1，从其它n-1个方程中消去变量xk…………第13页，共51页，2023年，2月20日，星期六消元公式为：对k=1,2,…,按上述步骤进行到第n步后，方程组变为：即为所求的解第14页，共51页，2023年，2月20日，星期六注：无回代的Gauss消元法实际上就是将方程组的系数矩阵化为行最简形矩阵。第15页，共51页，2023年，2月20日，星期六5．无回代消去法的应用（1）解线性方程组系设要解的线性方程组系为：AX=b1,AX=b2,…AX=bm上述方程组系可以写为AX=B=(b1,…,bm)第16页，共51页，2023年，2月20日，星期六因此 X=A-1B即为线性方程组系的解。

在计算机上只需要增加几组右端常数项的存贮单元，其结构和解一个方程组时一样。行系数右端第17页，共51页，2023年，2月20日，星期六（2）求逆矩阵设A=(aij)nn是非奇矩阵，A

0，且令由于AA-1=AX=I因此，求A-1的问题相当于解下列线性方程组相当于（1）中m=n,

B=I的情形。

第18页，共51页，2023年，2月20日，星期六（3）求行列式的值用高斯消去法将

A化成上三角形第19页，共51页，2023年，2月20日，星期六例

用Gauss-Jordan消去法解方程组

，并求出

其中解：把系数矩阵、单位矩阵和右端项组成增广矩阵，对增广矩阵实行Gauss-Jordan消元过程。第20页，共51页，2023年，2月20日，星期六故，系数矩阵的逆为第21页，共51页，2023年，2月20日，星期六§2解三对角方程组的追赶法第22页，共51页，2023年，2月20日，星期六第23页，共51页，2023年，2月20日，星期六§3矩阵的三角分解法

高斯消元法的矩阵形式

每一步消去过程相当于左乘初等下三角矩阵Lk第24页，共51页，2023年，2月20日，星期六记第25页，共51页，2023年，2月20日，星期六A

的

LU

分解(LUfactorization)第26页，共51页，2023年，2月20日，星期六定理2：（矩阵的三角分解）设A为nn实矩阵，如果求解AX=b用顺序高斯消去法能够完成（即），则矩阵A可分解为单位下三角矩阵L与上三角矩阵U的乘积。

A=LU且这种分解是唯一的。第27页，共51页，2023年，2月20日，星期六注：（1）L为单位下三角阵而U为一般上三角阵的分解称为Doolittle

分解（2）L为一般下三角阵而U为单位上三角阵的分解称为Crout分解。

第28页，共51页，2023年，2月20日，星期六Doolittle分解法：通过比较法直接导出L和U的计算公式。思路第29页，共51页，2023年，2月20日，星期六LU分解求解线性方程组第30页，共51页，2023年，2月20日，星期六直接三角分解法解AX=b的计算公式对于r=2,3,…,n计算（2）计算U的第r行元素

（3）计算L的第r列元素(r

n)(1)第31页，共51页，2023年，2月20日，星期六(4)(5)第32页，共51页，2023年，2月20日，星期六例用矩阵的三角分解法解方程组第33页，共51页，2023年，2月20日，星期六Doolittle分解法的变形紧凑格式的Doolittle分解法例所以第34页，共51页，2023年，2月20日，星期六紧凑格式的列主元Doolittle分解法例第35页，共51页，2023年，2月20日，星期六§4平方根法1．矩阵的LDR分解定理3：如果n阶矩阵A的所有顺序主子式均不等于零，则矩阵A存在唯一的分解式A=LDR，其中L和R分别是n阶单位下三角阵和单位上三角阵，D是对角元素不为零的n阶对角阵，上述分解称为A的LDR分解。第36页，共51页，2023年，2月20日，星期六2．平方根法

如果A为对称正定矩阵，则存在一个实的非奇异下三

角矩阵，使A=LLT，且当限定的对角元素为正时，这种分解是唯一的，称为矩阵A的cholesky分解。定理4：（对称正定矩阵的三角分解）第37页，共51页，2023年，2月20日，星期六将对称

正定阵

A做LU

分解U=uij=u11uij/uii111u22unn记为

A对称即记D1/2=则仍是下三角阵，且有对称正定阵cholesky分解的实现第38页，共51页，2023年，2月20日，星期六用平方根法解对称正定线性代数方程组的算法（1）对矩阵A进行Cholesky分解，即A=LLT，由矩阵乘法：对于i=1,2,…,n计算第39页，共51页，2023年，2月20日，星期六（2）求解下三角形方程组

（3）求解LTX=y第40页，共51页，2023年，2月20日，星期六3．改进平方根法

其中第41页，共51页，2023年，2月20日，星期六改进平方根法解对称正定方程组的算法第42页，共51页，2023年，2月20日，星期六令LTX=y，先解下三角形方程组LDY=b得解上三角形方程组LTX=Y得第43页，共51页，2023年，2月20日，星期六求解时，A和的误差对解有何影响？设A精确，有误差，得到的解为，即绝对误差放大因子又相对误差放大因子§5线性方程组的性态和解的误差分析第44页，共51页，2023年，2月20日，星期六§6ErrorAnalysisfor.

设精确，A有误差，得到的解为，即

Waitaminute…

Whosaidthat(I+A1A)isinvertible?(只要A充分小，使得是关键的误差放大因子，称为A的条件数，记为cond(A),越则A越病态，难得准确解。大第45页，共51页，2023年，2月20日，星期六例：Hilbert阵cond(H2)=27cond(H3)748cond(H6)=2.9106cond(Hn)asn注：现在用Matlab数学软件可以很方便求矩阵的状态数!定义2:设线性方程组的系数矩阵是非奇异的,如果cond(A)越大,就称这个方程组越病态.反之,cond(A)越小,就称这个方程组越良态.第46页，共51页，2023年，2月20日，星期六一般判断矩阵是否病态，并不计算A1，而由经验得出。行列式很大或很小（如某些行、列近似相关）；元素间相差大数量级，且无规则；主元消去过程中出现小主元；特征值相差大数量级。第47页，共51页，2023年，2月20日，星期六近似解的误差估计及改善：设的近似解为，则一般有cond(A)误差上限改善方法(1)：Step1:近似解Step2:Step3:Step4:若可被精确解出，则有就是精确解了。经验表明：若A不是非常病态（例如：），则如此迭代可达到机器精度；但若A病态，则此算法也不能改进。第48页，共51页，2023年，2月20日，星期六改善方法(2)对方程组进行预处理，即适当选择非奇异对角阵D，C,使求解Ax=b的问题转化为求解等价方程组DAC[C-1x]=Db,且使DAC的条件数得到改善。（P88，例3.10）用双精度进行计算，以便改善和减轻病态矩阵的影响。第49页，共51页，2023年，2月20日，星期六历史与注记

高斯(CarlFriedrichGauss,1777-1855)高斯是德国数学家、物理学家、天文学家。1777年生于德国布伦瑞克，1855年在哥廷根逝世。高斯是近代数学奠基者之一，在历史上影响之大，可以和阿基米德、牛顿、欧拉并列，有“数学王子”之称。1795年进入格丁根大学学习。1798年转入黑尔姆施泰特大学，1799年获博士学位。1807年以后一直在格丁根大学任教授和哥廷根天文台台长，一直到逝世。1833年和物理学家W.E.韦伯共同建立地磁观测台，组织磁学学会以联系全世界的