第第7章章 解线性方程组的直接法解线性方程组的直接法1 1 引言引言两种两种方程组（按系数矩阵的阶方程组（按系数矩阵的阶n）：）：1、低阶稠密矩阵：、低阶稠密矩阵：2、高阶稀疏矩阵（大型稀疏矩阵）、高阶稀疏矩阵（大型稀疏矩阵）直接法直接法间接法或称迭代法间接法或称迭代法 直接法：直接法：计算过程中没有舍入误差，经过有限步算术运算可计算过程中没有舍入误差，经过有限步算术运算可选主元消去法选主元消去法求得方程组的精确解。求得方程组的精确解。三角分解法三角分解法实际中有实际中有舍入误差舍入误差高斯消去法PPT课件7.2 7.2 高斯消去法高斯消去法解：解： （古老或古典方法）（古老或古典方法） 基本思想方法：基本思想方法：例例3 用消去法解方程组用消去法解方程组由由行初等变换行初等变换将系数矩阵约化为上三角将系数矩阵约化为上三角矩阵；矩阵；用用回代回代的方法求解方程组。的方法求解方程组。（1）消元：）消元：（2）回代求解，得）回代求解，得高斯消去法PPT课件m个方程，个方程，n个未知数的线性方程组的个未知数的线性方程组的高斯消去法高斯消去法：若记若记高斯消去法PPT课件（1）第）第1步步(k=1)，计算公式为：计算公式为：（m-1)(n-1)次乘法运算次乘法运算高斯消去法高斯消去法：设设 ，计算乘数，计算乘数 (m-1)次除法运算次除法运算对增广矩阵对增广矩阵 施行施行行行初等变换：初等变换：（m-1)次乘法运算次乘法运算高斯消去法PPT课件记为记为 （2 2）第）第k步（步（ ） 设已完成上述消元过程第设已完成上述消元过程第1 1步，步，第第2步，步，第，第k-1-1步，（设步，（设 ）得到与原方程组）得到与原方程组 等价的方程组等价的方程组高斯消去法PPT课件其中其中 元素计算公式为：元素计算公式为： 计算乘数计算乘数第第 k步计算：步计算： 对对 施行施行行行初等变换初等变换,使使 第第k列列 以下元素约化为零，以下元素约化为零， 与与 前前k行元素相同，行元素相同， 左上角左上角 阶阵阶阵为上三角阵。为上三角阵。（m-k)次乘法运算次乘法运算（m-k）次除法运算次除法运算（m-k)(n-k)次乘法运算次乘法运算即即 ，得到与原方程组等价的方程组，得到与原方程组等价的方程组高斯消去法PPT课件 （3 3）继续上述约化过程，）继续上述约化过程， （i） 当当m n时时，s = n，且设且设 ，则，则 （ii）当当m = n时，时， s = n-1,且设且设 ，则，则直到完成第直到完成第S步计算，得到与原方程组等价的方程组步计算，得到与原方程组等价的方程组其中其中 为上梯形，具有以下三种情况：为上梯形，具有以下三种情况：高斯消去法PPT课件 (iii) (iii)当当m n时，时，s = m-1，且设，且设 , ,则则 说明：说明： (1)上述约化过程，可用矩阵变换来叙述，因上述约化过程，可用矩阵变换来叙述，因 由由 约化到约化到 , ,实际上是由乘数实际上是由乘数 构成初构成初与与 相乘得到相乘得到 ，即即 等下三角阵等下三角阵高斯消去法PPT课件 即即高斯消去法PPT课件为高斯变换，为高斯变换，（上梯形）（上梯形）条件下存在高斯变换条件下存在高斯变换 ，使将，使将A 约化为上梯形。约化为上梯形。因此上述约化过程，用矩阵变换来叙述为因此上述约化过程，用矩阵变换来叙述为 （2）元素元素 称为约化的称为约化的主元素主元素，且原方程组约化为等价方，且原方程组约化为等价方由由消元过程消元过程和和回代过程回代过程构成了构成了高斯消去法高斯消去法。程组程组 过程称为过程称为消元过程消元过程，用用回代法回代法解（解（3 3.9 9）高斯消去法PPT课件 （3 3）若）若Ax=b, ,其中其中 非奇异矩阵，这时非奇异矩阵，这时 可能为零。可能为零。所以所以A第第1 1列一定存在元素列一定存在元素此时可交换（此时可交换（ ）第）第1 1 行与第行与第i1行元素（即行元素（即 ），），然后进行消元计算。于是然后进行消元计算。于是 ，且，且 右下角矩阵为右下角矩阵为n-1阶阶时，时，可采用上述方法同样处理。可采用上述方法同样处理。非奇异矩阵。当非奇异矩阵。当 时，直接进行消元计算时，直接进行消元计算, ,当当 （用高斯变换约化）（用高斯变换约化）结论：结论：定理定理6 6则存在初等下三角阵则存在初等下三角阵 ,使使(上梯形上梯形). (1)如果如果 ，则通过高斯消去法（不进行，则通过高斯消去法（不进行定理定理7 7交换两行的初等变换）交换两行的初等变换）将将 化为等价的三角方程组。化为等价的三角方程组。高斯消去法PPT课件 回代计算：回代计算： 消元计算：消元计算： （2）如果）如果A为非奇异矩阵，则可通过带行交换的高斯消去为非奇异矩阵，则可通过带行交换的高斯消去Ganss消去法中消去法中注：注：则要求在算法中增加一判断框，并要交换两行元素（或者说交换则要求在算法中增加一判断框，并要交换两行元素（或者说交换两个方程）。两个方程）。法，将法，将 化为等价的三角形方程组（化为等价的三角形方程组（3.12）。）。高斯消去法PPT课件计算量：计算量： 回代计算回代计算量量： 消元计算量消元计算量(k=1,2,n-1 1)：除法：除法：乘除法：乘除法：乘法：乘法：高斯消去法PPT课件定理定理8 8（2 2）若）若反之亦对。反之亦对。（1 1）若）若 顺序主子式顺序主子式 ，则，则（必要性（必要性 ） 证明：证明：用归纳法证明。用归纳法证明。 当当 时，时， 显然成立，显然成立， 假设对假设对 时成立，即时成立，即 ,下证对下证对k 成立，即成立，即 由归纳法假设由归纳法假设再由再由Ganss消去法消去法 ，得，得 是否是零，可以根据顺序主子式来判断。是否是零，可以根据顺序主子式来判断。高斯消去法PPT课件 反之，若反之，若即定理对即定理对k亦成立。亦成立。由由Ganss消去法知消去法知(3.13)(3.13)成立，则成立，则 高斯消去法PPT课件 （2 2）若）若于是于是,对对k= = 1,2 2,n时，时，(3.13)成成 理解理解高斯消去法并高斯消去法并会用该方法解方程组会用该方法解方程组。 立，则立，则高斯消去法PPT课件3 3 高斯消去法高斯消去法（古老或古典方法）（古老或古典方法）高斯消去法高斯消去法： 第第k步（步（ ） 设已完成上述消元过程第设已完成上述消元过程第1 1步，步，第第2步，步，第，第k-1-1步，（设步，（设 ）得到与原方程组）得到与原方程组 等价的方程组等价的方程组高斯消去法PPT课件其中其中 元素计算公式为：元素计算公式为： 计算乘数计算乘数第第 k步计算：步计算： 对对 施行施行行行初等变换初等变换,使使 第第k列列 以下元素约化为零，以下元素约化为零，（m-k)次乘法运算次乘法运算（m-k）次除法运算次除法运算（m-k)(n-k)次乘法运算次乘法运算即即 ，得到与原方程组等价的方程组，得到与原方程组等价的方程组 说明：说明： (1)上述约化过程，可用矩阵变换来叙述，因上述约化过程，可用矩阵变换来叙述，因 由由 约化到约化到 , ,实际上是由乘数实际上是由乘数 构成初构成初与与 相乘得到相乘得到 ，即即 等下三角阵等下三角阵高斯消去法PPT课件 或或高斯消去法PPT课件