消元法、主元素法

1、123線性方程組的直接解法第 五 章4 第五章 線性方程組的直接解法高斯消元法矩陣三角分解法主元素法追趕法平方根法134255一、高斯消元法預(yù)備知識(shí)問題的由來消元法的過程分析消元法的目標(biāo)回代過程算法消元法的計(jì)算量例題分析6高 斯 消 元 法預(yù)備知識(shí)引例引 例 1求前n個(gè)正整數(shù)的平方和 .解析函數(shù)滿足條件將其代入它所滿足的第1個(gè)等式整理比較對(duì)應(yīng)系數(shù)可得方程組不妨設(shè)有3次多項(xiàng)式當(dāng)f (n)是 k 次多項(xiàng)式，是 次.7高 斯 消 元 法預(yù)備知識(shí)引例由第三個(gè)方程可解出代入第二個(gè)方程解出再代入第一個(gè)方程解出8高 斯 消 元 法預(yù)備知識(shí)引例引 例 2二次函數(shù) 的圖像經(jīng)過3個(gè)已知點(diǎn)（1,1），（2,2），（

2、3,0），求 . 解析設(shè)所求二次函數(shù)為，其待定系數(shù)滿足解此方程組得，則思 考 在一次智力測驗(yàn)中，老師寫出某個(gè)數(shù)列的前兩項(xiàng)為1，2，讓學(xué)生按照前兩項(xiàng)的規(guī)律寫出第3項(xiàng)，有人寫3，有人寫4，老師都判為正確，有一個(gè)學(xué)生組出答案為0，老師判為錯(cuò)誤. 試給出某個(gè)數(shù)列的通項(xiàng)公式使這個(gè)數(shù)列的前3項(xiàng)依次是1，2，0. 來說明這個(gè)學(xué)生的答案也是正確的. 并按照這個(gè)通項(xiàng)式寫出第4項(xiàng).9高 斯 消 元 法預(yù)備知識(shí)線性方程組的形式線性方程組的一般形式：矩陣形式為：10預(yù)備知識(shí)線性方程組的常見分類高 斯 消 元 法根據(jù)方程組的解析解的情況有唯一解：適定方程組不存在解：超定方程組無窮多解：欠定方程組根據(jù)方程組的形式和規(guī)模大

3、型（高階）稀疏方程組大型（高階）稠密方程組小型（低階）稀疏方程組小型（低階）稠密方程組本章始終假設(shè) 方程組有唯一解11預(yù)備知識(shí)線性方程組的解析解法高斯消元法設(shè)有線性方程組: 如何求解方程組?如果線性方程組中的方程個(gè)數(shù)與未知量個(gè)數(shù)相同，并且其系數(shù)矩陣滿秩，那么可有以下三種求解方法：（1）克拉默（Cramer）法則；（2）逆矩陣；（3）高斯消元法。 12預(yù)備知識(shí)Cramer法則高斯消元法當(dāng) 時(shí)，當(dāng) 時(shí)，優(yōu)點(diǎn)：收斂、穩(wěn)定、結(jié)論可靠缺點(diǎn)：計(jì)算量過大計(jì)算量：13預(yù)備知識(shí)線性方程組的數(shù)值解法高 斯 消 元 法常用的數(shù)值解法：直接法、迭代法直接法：如果不考慮計(jì)算過程中的舍入誤差，則通過有限步運(yùn)算可以得到方程

4、 組的精確解。直 接 法小型稠密矩陣高斯消元法主元素法三角分解法追趕法平方根法高斯消元法主元素法三角分解法追趕法平方根法高斯消元法主元素法三角分解法追趕法平方根法14預(yù)備知識(shí)線性方程組的數(shù)值解法高 斯 消 元 法迭代法：采用逐次逼近的方法，即從一個(gè)初始解出發(fā)，按照某種迭代格式，逐步 逼近方程組的解，直至滿足精度要求為止。迭 代 法 Jacobi迭代法Gauss-Seidel迭代法松弛迭代法大型稀疏矩陣15預(yù)備知識(shí)幾種特殊矩陣高 斯 消 元 法3. 對(duì)角形矩陣非零元素只在主對(duì)角線上出現(xiàn)1. 上三角形矩陣非零元素只出現(xiàn)在主對(duì)角線及其上（或右）方2. 下三角形矩陣非零元素只出現(xiàn)在主對(duì)角線及其下（或左

5、）方4. 對(duì)稱矩陣反對(duì)稱矩陣設(shè)16預(yù)備知識(shí)幾種特殊矩陣高 斯 消 元 法設(shè)6. 上Hessenberg矩陣 時(shí)， 即5. 對(duì)稱正定矩陣7. 按行對(duì)角占優(yōu)矩陣8. 三對(duì)角矩陣對(duì)任意非零向量，17 中國古法 李文漢教授證明 適合范圍低階稠密矩陣方程組 特 點(diǎn) 一般三角問題的由來高 斯 消 元 法18程序設(shè)計(jì)高 斯 消 元 法消元引 例用消元法解方程組求解過程相當(dāng)于回代19 程序設(shè)計(jì)程序設(shè)計(jì)高 斯 消 元 法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 消元法的目標(biāo)高 斯 消 元 法上三角方程組的一般形式是： 21高斯消元法的通用程序設(shè)計(jì)基于Mathematica9.01階數(shù) n=2矩陣 A=3常數(shù)項(xiàng) b=22高 斯 消 元 法 消元法的過程分析對(duì)n階線性方程組：轉(zhuǎn)化為等價(jià)的（同解）的三角形方程組稱消元過程。逐次計(jì)算出 稱回代過程。23高 斯 消 元 法 消元法的過程分析若 ：(第2行) (第1行)(新第2行)(第3行) (第1行)(新第3行)(第n行) (第1行)(新第n行)相當(dāng)于第i個(gè)方程減第1個(gè)方程數(shù)新的第i方程同解！第1方程不動(dòng)！ 統(tǒng)一記號(hào)24高 斯 消 元 法 消元法的過程

7、分析 上述消元過程除第一個(gè)方程不變以外,第2第 n 個(gè)方程全消去了變量 ，而系數(shù)和常數(shù)項(xiàng)全得到新值：25高 斯 消 元 法 消元法的過程分析方程左邊方程右邊第1步消元算法歸納：若26高 斯 消 元 法 消元法的過程分析第2步消元：對(duì)除第一行第一列外的子陣作計(jì)算：若方程左邊方程右邊27高 斯 消 元 法 消元法的過程分析依次進(jìn)行下去若方程左邊方程右邊方程左邊方程右邊28高 斯 消 元 法 回代過程算法29 程序設(shè)計(jì)程序設(shè)計(jì)高 斯 消 元 法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