第二章 解线性方程组的直接法 2.1 直接法与三角形方程组求解§ 2.2 Gauss消去法§ 第二章 解线性方程组的直接法 2.3 Gauss列主元 消去法§ 2.4 直接三角分解法§ 2.5 平方根法§ 2.6 追赶法 (Thomas法 )§ 本章要点 线性方程组的解法类型之一 :直接解法 主要归结为三角形方程组的求解 包括一般线性方程组的 Gauss消去法 、 Gauss列主元法 、 对称正定方程组的平 方根法 、 三对角方程组的追赶法等 涉及到一些三角分解 ： 主要有 Doolittle 分解 、 Crout分解 、 Cholesky分解等 本章应用题 ： 投入产出平衡分析 设国民经济仅由农业 、 制造业和服务业三个部门组成 , 已知某年它们之间的投入产出关系 、 外部需求 、 初始 投入等如下表所示 ： 产出 投入 农业 制造业 服务业 外部需求 总产出 农业 15 20 30 35 100 制造业 30 10 45 115 200 服务业 20 60 / 70 150 初始投入 35 110 75 总投入 100 200 150 表 1. 国民经济个部门之间的关系 产出 投入 农业 制造业 服务业 农业 0.15 0.10 0.20 制造业 0.30 0.05 0.30 服务业 0.20 0.30 0 表 2. 投入产出表 假定每个部门的产出与投入成正比 ,则由表 1可确定 三个部门的投入产出表 ,如表 2. 投入系数 或消耗系数 1) 设有 n 个部门 ,已知投入系数 ,给定外部需求 ,建立 求解个部门总产出的模型 2) 设投入系数如表 2所给 ,如果今年对农业 、 制造业 和服务业的外部需求分别为 50,150,100亿元 ,问这 三个部门的总产出分别为多少 ? 3) 如果三个部门的外部需求分别增加 1个单位 ,他们 的总产出分别增加多少 ? 4) 如果对于任意给定的 、 非负的外部需求 ,都能得到 非负的总产出 ,模型就称为可行的 ,问为使模型可行 , 投入系数应满足什么条件 ? 第二章 解线性方程组的直接法 2.1 直接法与三角形方程组求解§ 实际问题中的线性方程组分类 ： 按系数矩阵中 零元素的个数 ： 稠密线性 方程组 稀疏线性 方程组 按未知量 的个数 ： 高阶线性 方程组 低阶线性 方程组(如 1000) (80%) 按系数矩 阵的形状 对称正定 方程组 三角形 方程组 三对角占 优方程组 一 、 直接法概述 直接法是将原方程组化为一个或若干个三角形 方程组的方法 ， 共有若干种 ． 对于线性方程组 bAx = ? ? ? ? ? ? ? ? ? ? ? ? = nnnn n n aaa aaa aaa A L MMMM L L 21 22221 11211 ? ? ? ? ? ? ? ? ? ? ? ? = nx x x x M2 1 ? ? ? ? ? ? ? ? ? ? ? ? = nb b b b M2 1其中 系数矩阵 未知量向量 常数项 ------------(1) 根据 Cramer(克莱姆 )法则 ,若 0)det( ≠A 有唯一解则方程组 bAx = determinantal ||)det( AA = 行列式的记号 若用初等变换法求解 ,则对其增广矩阵作行初等变换 : ),( bAA = ),( )1()1( bA= ),( )2()2( bA 经过 n-1次 ),( )()( nn bA 为上三角阵目标 ： )(nA 的解不难得到则方程组 )()( nn bxA = bAx = bAx = )()( nn bxA = 同解 即 以上求解线性方程组的方法称为 Gauss消去法 即和两个三角形矩阵 分解成的系数矩阵如果将线性方程组 ,UL AbAx = LUA = 则 bLUx = bLy = yUx = 都是三角 形方程组 上述方法称为直接三角形分解法 ------------(2) 不论是 Gauss消去法还是直接三角形分解法 , 最都归结为解三角形方程组 二 、 三角形线性方程组的解法 bLx = bUx = ? ? ? ? ? ? ? ? ? ? ? ? = nnnn lll ll l L L OMM 21 2221 11 ? ? ? ? ? ? ? ? ? ? ? ? = nn n n u uu uuu U MOL L 222 11211若记 下三角形线性方程组 上三角形线性方程组 的求解思路 ：下三角形方程组 bLx = ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? nnnnn x x x lll ll l M L OMM 2 1 21 2221 11 ? ? ? ? ? ? ? ? ? ? ? ? = nb b b M 2 1 bLx = nnnnnn bxlxlxl =+++ L L 2211 1111 bxl = 2222121 bxlxl =+ iiiiii bxlxlxl =+++ L L 2211 ? ? ? ??? ? 即 回代方向 11 1 1 l bx = ii i j jiji i l xlb x ∑? = ? = 1 1 ni ,,3,2 L=? ? ? ??? ? 的求解思路 ：上三角形方程组 bUx = ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? nnn n n x x x u uu uuu 2 1 222 11211 MO L L ? ? ? ? ? ? ? ? ? ? ? ? = nb b b M 2 1 bUx = 其解为 11212111 bxuxuxu nn =+++ L nnnn bxu = 1,111,1 ????? =+ nnnnnnn bxuxu K ininiiiiii bxuxuxu =+++ ++ L L 11, ? ? ? ??? ? 其解为 : nn n n u bx = ii n ij jiji i u xub x ∑ += ? = 1 1,2,,2,1 L??= nni??? ??? ? 回 代 方 向 ),( bAA = 2.2 Gauss消去法§ 一 、 消元与回代计算 ? ? ? ? ? ? ? ? ? ? ? ? = )1()1()1( 2 )1( 1 )1( 2 )1( 2 )1( 22 )1( 21 )1( 1 )1( 1 )1( 12 )1( 11 nnnnn n n baaa baaa baaa L MMMM L L bAx =对线性方程组 对其增广矩阵施行行初等变换 : ),( )1()1( bA记= 0)det( ≠A如果 ? ? ? ? ? ? ? ? ? ? ? ? = )2()2()2( 2 )2( 2 )2( 2 )2( 22 )1( 1 )1( 1 )1( 12 )1( 11 0 0 nnnn n n baa baa baaa L MMMM L L ),( )2()2( bA 0)1(11 ≠a假定 定义行乘数 nia am i i ,,3,2)1( 11 )1( 1 1 L== 则行第行第 ,1 1imi ×? )1( 11 )1()2( jiijij amaa ?= )1( 11 )1()2( bmbb iii ?= nji ,,3,2, L= ni ,,3,2 L= ),( )1()1( bA 0)1(11 =a如果 0)det( ≠A由于 元素不为零的第一列中至少有一个则 A 行交换后消元的第一行与第则将如 1)1()1()1( 1 ),(,0 1 ibAai ≠ ? ? ? ? ? ? ? ? ? ? ? ? )2()2()2( 2 )2( 2 )2( 2 )2( 22 )1( 1 )1( 1 )1( 12 )1( 11 0 0 nnnn n n baa baa baaa L MMMM L L 且 0)det( ≠? 将化为步后第因此 ),(,1, )1()1( bAk ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = )()()( )()()( )2( 2 )2( 2 )2( 22 )1( 1 )1( 1 )1( 12 )1( 11 k n k nn k nk k k k kn k kk n n baa baa baa baaa L MMM L MMO LL LL ),( )()( kk bA),( )1()1( bA 0)det( ≠? 定义行乘数 nkiaam k kk k ik ik ,,1)( )( L+== 则行第行第 ,ikmki ×? )()()1( k kjik k ij k ij amaa ?= + )()()1( k kik k i k i bmbb ?= + nkji ,,1, L+= nki ,,1 L+= ? ? ? ? ? ? ? ? ? ? ? ? = )()( )2( 2 )2( 2 )2( 22 )1( 1 )1( 1 )1( 12 )1( 11 n n n nn n n ba baa baaa MMO L L ),( )1()1( bA 将化为步后当经过 ),(,1 )1()1( bAnk ?= ),( )()( nn bA 0)det( ≠A由于 nia iii ,,2,10)( L=≠可知 的解 ：因此可得线性方程组 bAx = 有唯一解上三角形方程组因此 )()(, nn bxA = )( )( n nn n n n a bx = 1,2,,2,1 L??= nni? ? ? ??? ? )( 1 )()( i ii n ij j i ij i i i a xab x ∑ += ? = 二 、 Gauss消去法的运算量 计算机作乘除运算所耗时间要远远多于加减运算 且在一个算法中 ， 加减运算和乘除运算次数大体相当 故在衡量一个算法的运算量时只需统计乘除的运算次数 步消元时作第 k 乘法次数 ： 次)1)(( +?? knkn 除法次数 ： 次)( kn ? 数为步消元乘除法运算总次作第 k 次)2)(( +?? knkn 总次数为步消元需作乘除法运算完成全部 1?n ∑? = +?? 1 1 )2)(( n k knkn 6523 23 nnn ?+= 全部回代过程需作乘除法的总次数为 ∑ = +? n i in 1 )1( 22 2 nn += 于是 Gauss消去法的乘除法运算总的次数为 MD 33 2 3 n nn ?+= )(3 2 3 nOn += 数级 很大时当 n 33 2 3 n nn ?+=MD 3 3n ≈ 时如 20=n Gauss消去法乘除法约为 2700次 而如果用 Cramer法则的乘除法运算次数约为 20)120)(120(!20 ++? 20109×≈ 或 2700)120( ×+ 用行列式定义 用行列式性质