消元法、主元素法

1、123线性方程组的直接解法第 五 章4 第五章 线性方程组的直接解法高斯消元法矩阵三角分解法主元素法追赶法平方根法134255一、高斯消元法预备知识问题的由来消元法的过程分析消元法的目标回代过程算法消元法的计算量例题分析6高 斯 消 元 法预备知识引例引 例 1求前n个正整数的平方和 .解析函数满足条件将其代入它所满足的第1个等式整理比较对应系数可得方程组不妨设有3次多项式当f (n)是 k 次多项式，是 次.7高 斯 消 元 法预备知识引例由第三个方程可解出代入第二个方程解出再代入第一个方程解出8高 斯 消 元 法预备知识引例引 例 2二次函数 的图像经过3个已知点（1,1），（2,2），（

2、3,0），求 . 解析设所求二次函数为，其待定系数满足解此方程组得，则思 考 在一次智力测验中，老师写出某个数列的前两项为1，2，让学生按照前两项的规律写出第3项，有人写3，有人写4，老师都判为正确，有一个学生组出答案为0，老师判为错误. 试给出某个数列的通项公式使这个数列的前3项依次是1，2，0. 来说明这个学生的答案也是正确的. 并按照这个通项式写出第4项.9高 斯 消 元 法预备知识线性方程组的形式线性方程组的一般形式：矩阵形式为：10预备知识线性方程组的常见分类高 斯 消 元 法根据方程组的解析解的情况有唯一解：适定方程组不存在解：超定方程组无穷多解：欠定方程组根据方程组的形式和规模大

3、型（高阶）稀疏方程组大型（高阶）稠密方程组小型（低阶）稀疏方程组小型（低阶）稠密方程组本章始终假设 方程组有唯一解11预备知识线性方程组的解析解法高斯消元法设有线性方程组: 如何求解方程组?如果线性方程组中的方程个数与未知量个数相同，并且其系数矩阵满秩，那么可有以下三种求解方法：（1）克拉默（Cramer）法则；（2）逆矩阵；（3）高斯消元法。 12预备知识Cramer法则高斯消元法当 时，当 时，优点：收敛、稳定、结论可靠缺点：计算量过大计算量：13预备知识线性方程组的数值解法高 斯 消 元 法常用的数值解法：直接法、迭代法直接法：如果不考虑计算过程中的舍入误差，则通过有限步运算可以得到方程

4、 组的精确解。直 接 法小型稠密矩阵高斯消元法主元素法三角分解法追赶法平方根法高斯消元法主元素法三角分解法追赶法平方根法高斯消元法主元素法三角分解法追赶法平方根法14预备知识线性方程组的数值解法高 斯 消 元 法迭代法：采用逐次逼近的方法，即从一个初始解出发，按照某种迭代格式，逐步 逼近方程组的解，直至满足精度要求为止。迭 代 法 Jacobi迭代法Gauss-Seidel迭代法松弛迭代法大型稀疏矩阵15预备知识几种特殊矩阵高 斯 消 元 法3. 对角形矩阵非零元素只在主对角线上出现1. 上三角形矩阵非零元素只出现在主对角线及其上（或右）方2. 下三角形矩阵非零元素只出现在主对角线及其下（或左

5、）方4. 对称矩阵反对称矩阵设16预备知识几种特殊矩阵高 斯 消 元 法设6. 上Hessenberg矩阵 时， 即5. 对称正定矩阵7. 按行对角占优矩阵8. 三对角矩阵对任意非零向量，17 中国古法 李文汉教授证明 适合范围低阶稠密矩阵方程组 特 点 一般三角问题的由来高 斯 消 元 法18程序设计高 斯 消 元 法消元引 例用消元法解方程组求解过程相当于回代19 程序设计程序设计高 斯 消 元 法A=1,1,1,0,4,-1,2,-2,1;MatrixForm%x=x1,x2,x3;b=6,5,1;LinearSolveA,bSolveA.x=b1, 2, 3x1 - 1, x2 - 2

6、, x3 - 3答 案解线性方程组，给出的解为向量形式20 消元法的目标高 斯 消 元 法上三角方程组的一般形式是： 21高斯消元法的通用程序设计基于Mathematica9.01阶数 n=2矩阵 A=3常数项 b=22高 斯 消 元 法 消元法的过程分析对n阶线性方程组：转化为等价的（同解）的三角形方程组称消元过程。逐次计算出 称回代过程。23高 斯 消 元 法 消元法的过程分析若 ：(第2行) (第1行)(新第2行)(第3行) (第1行)(新第3行)(第n行) (第1行)(新第n行)相当于第i个方程减第1个方程数新的第i方程同解！第1方程不动！ 统一记号24高 斯 消 元 法 消元法的过程

7、分析 上述消元过程除第一个方程不变以外,第2第 n 个方程全消去了变量 ，而系数和常数项全得到新值：25高 斯 消 元 法 消元法的过程分析方程左边方程右边第1步消元算法归纳：若26高 斯 消 元 法 消元法的过程分析第2步消元：对除第一行第一列外的子阵作计算：若方程左边方程右边27高 斯 消 元 法 消元法的过程分析依次进行下去若方程左边方程右边方程左边方程右边28高 斯 消 元 法 回代过程算法29 程序设计程序设计高 斯 消 元 法ClearP1,P2,P3,P4,P5,A,A1,A2,A3,A4,A5,A6A0=1,1,1,0,4,-1,2,-2,1;MatrixForm%b=6,5,1;X=x1,x2,x3;A=1,1,1,6,0,4,-1,5,2,-2,1,1;MatrixForm%;P1=1,0,0,0,1,0,-2,0,1;A1=P1.A;MatrixForm%;P2=1,0,0,0,1/4,0,0,0,1;A2=P2.A1;MatrixForm%;消元法举例说明P3=1,0,0,0,1,0,0,4,1;A3=P3.A2;MatrixForm%;P4=1,0,0,0,1,0,0,0,1/(-2);A4=P4.A3;MatrixForm%;P5=1,0,-1,0,1,1/4,0,0,1;A5=P5.A4;Mat