分析02-線性方程組直接解法.ppt

第二章線性方程組直接解法 2 1 第二章 線性方程組直接解法 第二章線性方程組直接解法 2 2 第二章目錄 1 Gauus消元法 2 主元素法2 1引入主元素法的必要性2 2列主元素法2 3全主元素法2 4解三對角方程組的追趕法 3 矩陣分解法3 1Gauss消去法的矩陣形式3 2矩陣的三角分解3 3直接三角分解法 4 平方根法與改進(jìn)的平方根法 5 矩陣求逆 6 方程組的性態(tài)和條件數(shù) 第二章線性方程組直接解法 2 3 線性方程組的概念 在科學(xué)研究和工程技術(shù)中所提出的計(jì)算問題中 線性方程組的求解問題是基本的 常見的 很多問題如插值函數(shù) 最小二乘數(shù)據(jù)擬合 構(gòu)造求解微分方程的差分格式等 都包含了解線性方程組問題 因此 線性方程組的解法在數(shù)值計(jì)算中占有較重要的地位 設(shè)n階線性方程組 其矩陣形式為 Ax b 2 2 其中 第二章線性方程組直接解法 2 4 求解Ax b 曾經(jīng)學(xué)過高斯 Gauss 消元法 克萊姆 Cramer 法則 矩陣變換法等 但已遠(yuǎn)遠(yuǎn)滿足不了實(shí)際運(yùn)算的需要 主要體現(xiàn)兩個(gè)方面 一是運(yùn)算的快速和準(zhǔn)確 其次是方程組的個(gè)數(shù)增大時(shí)的計(jì)算問題 如何建立能在計(jì)算機(jī)上可以實(shí)現(xiàn)的有效而實(shí)用的解法 具有極其重要的意義 我們也曾指出過 Cramer法則在理論上是絕對正確的 但當(dāng)n較大時(shí) 在實(shí)際計(jì)算中卻不能用 線性方程組的概念 續(xù) 如果線性方程組Ax b的系數(shù)行列式不為零 即det A 0 則該方程組有唯一解 第二章線性方程組直接解法 2 5 線性方程組的數(shù)值解法 解線性方程組的數(shù)值方法大致分為兩類 請注意 由于在計(jì)算中某些數(shù)據(jù)實(shí)際上只能用有限位小數(shù) 即不可避免地存在著舍入誤差的影響 因而即使是準(zhǔn)確解法 也只能求到近似解 直接法在求解中小型線性方程組 100個(gè) 特別是系數(shù)矩陣為稠密型時(shí) 是常用的 非常好的方法 直接法 指假設(shè)計(jì)算過程中不產(chǎn)生含入誤差 經(jīng)過有限步四則運(yùn)算可求得方程組準(zhǔn)確解的方法 2 迭代法 從給定的方程組的一個(gè)近似值出發(fā) 構(gòu)造某種算法逐步將其準(zhǔn)確化 一般不能在有限步內(nèi)得到準(zhǔn)確解 這一章介紹計(jì)算機(jī)上常用的直接法 它們都是以Gauss消元法為基本方法 即先將線性方程組化為等價(jià)的三角形方程組 然后求解 第二章線性方程組直接解法 2 6 1Gauss消元法 Gauss消元法是最基本的一種方法 下例說明其基本思想 例1 解線性方程組 解 消去x1 進(jìn)行第一次消元 首先找乘數(shù) 以 12乘第一個(gè)方程加到第二個(gè)方程 以18乘第一個(gè)方程加到第三個(gè)方程上可得同解方程組 第二章線性方程組直接解法 2 7 例1 續(xù) 上述Gauss消元法的基本思想是 先逐次消去變量 將方程組化成同解的上三角形方程組 此過程稱為消元過程 然后按方程相反順序求解上三角形方程組 得到原方程組的解 此過程稱為回代過程 再消一次元得 二次消元后將方程化為倒三角形式 然后進(jìn)行回代容易解出 x3 3 x2 2 x1 1 我們的目的 是要總結(jié)歸納出一般情況下的n階線性方程組的消元公式和回代求解公式 從而得到求解n階線性方程組的能順利在計(jì)算機(jī)上實(shí)現(xiàn)的行之有效的算法 第二章線性方程組直接解法 2 8 Gauss消元法的基本步驟1 4階 為能更清楚地得到算法 下面以4階線性方程組為例總結(jié)求解步驟 并且很容易地可推廣至一般的n階線性方程組 第二章線性方程組直接解法 2 9 可以檢查 分別以 li1乘第一個(gè)方程加到第i個(gè)方程上可以完成第一次消元 得同解方程組 變化以后的方程組系數(shù)及右邊的常數(shù)項(xiàng)可總結(jié)出如下的計(jì)算公式 Gauss消元法的基本步驟2 4階 第二章線性方程組直接解法 2 10 Gauss消元法的基本步驟3 4階 以方程組中第i個(gè)方程減去第二個(gè)方程乘li2 i 3 4 完成第二次消元 上標(biāo)為3的系數(shù)和右端項(xiàng)可由下面公式計(jì)算 第二章線性方程組直接解法 2 11 Gauss消元法的基本步驟4 4階 第三步 消元 4階方程組需進(jìn)行3次消元 將上述A 3 X b 3 中最后一個(gè)方程中的x3消為零 然后可回代求解 由于A 4 為上三角形 所以可按變量的逆序逐步回代求原方程組的解 上述消元 回代求解過程很容易推廣到一般的n階線性方程組 經(jīng)過上述消元步驟 得到同解的上三角形方程組 A 4 x b 4 第二章線性方程組直接解法 2 12 Gauss消元法的消元過程1 2 n階 一般地 設(shè)n階方程組 消元過程為 第二章線性方程組直接解法 2 13 Gauss消元法的消元過程3 n階 第k步消元后同解方程組中上標(biāo)為k 1的元素的計(jì)算公式見下屏 第二章線性方程組直接解法 2 14 照此消元下去 完成n 1次消元后 可將原方程組化成同解的上三角形方程組如下 Gauss消元法的消元過程3 n階 第二章線性方程組直接解法 2 15 Gauss消元法的回代過程 n階 回代過程 逐步回代求得原方程組的解 第二章線性方程組直接解法 2 16 Gauss消元法的計(jì)算量 由于在計(jì)算機(jī)中作乘除運(yùn)算量所需時(shí)間遠(yuǎn)大于作加減運(yùn)算所需時(shí)間 故只考慮作乘除運(yùn)算量 由消元法步驟知 第k次消元需作n k次除法 作 n k n k 1 次乘法 故消元過程中乘除法運(yùn)算量為 所以Gauss消去法的乘除法總運(yùn)算量為 第二章線性方程組直接解法 2 17 Gauss法與Cramer法則的計(jì)算量比較 Gauss消元法的乘除法總運(yùn)算量為 與我們曾經(jīng)介紹的Cramer法則的乘除法總運(yùn)算量 n2 1 n n相比 由下表可知 當(dāng)階數(shù)越高時(shí) Gauss消元法所需乘除法次數(shù)比Cramer法則要少得多 Gauss消元法的優(yōu)缺點(diǎn) 但其計(jì)算過程中 要求akk k 稱為主元素 均不為零 因而適用范圍小 只適用于從1到n 1階順序主子式均不為零的矩陣A 計(jì)算實(shí)踐還表明 Gauss消元法的數(shù)值穩(wěn)定性差 當(dāng)出現(xiàn)小主元素時(shí) 會(huì)嚴(yán)重影響計(jì)算結(jié)果的精度 甚至導(dǎo)出錯(cuò)誤的結(jié)果 Gauss消元法簡單易行 第二章線性方程組直接解法 2 18 2主元素法 2 1引入主元素的必要性對線性方程組AX b 若其系數(shù)行列式det A 0 則該方程組有唯一解 但是這一條件不能保證所有主元素都不等于零 只要某一主元素等于零 就不能用Gauss消元法求解該方程組 即使所有主元素不等于零 但某一主元素的絕對值很小時(shí) Gauss消元法也是不適用的 如下例 例2 第二章線性方程組直接解法 2 19 例2 續(xù)1 解 為減小誤差 計(jì)算過程中保留3位有效數(shù)字 按Gauss消元法步驟 第一次消元后得同解方程組 第二次消元后得同解方程組 回代得解 x3 2 02 x2 2 40 x1 5 80 容易驗(yàn)證 方程組 3 8 的準(zhǔn)確解為 x1 2 60 x2 1 00 x3 2 0 顯然兩種結(jié)果相差很大 第二章線性方程組直接解法 2 20 若在解方程組前 先交換方程的次序 如將 2 8 交換一行與二行改寫成如下所示 再用Gauss消元法 順序消元后得同解方程組 回代得解 x3 2 00 x2 1 00 x1 2 60 與準(zhǔn)確解相同 例2 續(xù)2 第二章線性方程組直接解法 2 21 例2兩種解法的誤差分析 在例2中 對 2 8 的方程進(jìn)行順序消元時(shí) 主元a 1 11 0 50 a 2 22 0 100都比較小 以它們作除數(shù)就增長了舍入誤差 而導(dǎo)致計(jì)算結(jié)果不準(zhǔn)確 產(chǎn)生上述現(xiàn)象的原因在于舍入誤差 當(dāng) a k kk 很小時(shí) 進(jìn)行第k次消元 要用 a k kk 作除數(shù) 這樣就可能增大舍入誤差造成溢出停機(jī) 或者導(dǎo)致錯(cuò)誤的結(jié)果 為了在計(jì)算過程中 抑制舍入誤差的增長 應(yīng)盡量避免小主元的出現(xiàn) 如例2的第二種解法 通過交換方程次序 選取絕對值大的元素作主元基于這種思想而導(dǎo)出主元素法 第二章線性方程組直接解法 2 22 2 2列主元素法 為簡便起見 對方程組 2 1 用其增廣矩陣 表示 并直接在增廣矩陣上進(jìn)行運(yùn)算 列主元素法的具體步驟如下 第二章線性方程組直接解法 2 23 列主元素法 如此經(jīng)過n 1步 增廣矩陣 2 9 被化成上三角形 然后由回代過程求解 在上述過程中 主元是按列選取的 故稱為列主元法 例2中的第二種解法就是按列主元法進(jìn)行的 第二章線性方程組直接解法 2 24 2 3全主元素法 經(jīng)過n k次消元后 得到與方程組 2 1 同解的上三角形方程組 再由回代過程求解 第二章線性方程組直接解法 2 25 主元素法舉例 例6 計(jì)算過程保留三位小數(shù) 第二章線性方程組直接解法 2 26 2 4解三對角方程組的追趕法 在很多問題中 需要解如下形式的三對角方程組 三對角方程組的系數(shù)矩陣為三對角陣 對于這種特殊而又簡單的方程組 用前面介紹的方法求解由于有大量的零元素既占內(nèi)存又浪費(fèi)計(jì)算時(shí)間 顯然很不經(jīng)濟(jì) 充分注意到三對角方程組的特點(diǎn) 根據(jù)順序消元的思想導(dǎo)出一個(gè)簡便的算法 追趕法 第二章線性方程組直接解法 2 27 追趕法的解題步驟 首先進(jìn)行順序消元 且每步將主元系數(shù)化為1 將方程組化為 其中系數(shù)按下式計(jì)算 然后回代求解 得 上述追趕法能進(jìn)行到底 第二章線性方程組直接解法 2 28 追趕法舉例 用追趕法解下列三對角方程組 例4 解 首先將方程組化為 先追 然后回代 趕 求解 x5 0 x4 30 7 x3 6 7 x2 12 7 x1 0 可以看出 追趕法本質(zhì)上還是順序消元法 但由于計(jì)算過程中只涉及系數(shù)矩陣的非零元 因此大大節(jié)約了計(jì)算機(jī)內(nèi)存與計(jì)算量 按乘除法次數(shù)進(jìn)行比較 Gauss消元法約為n3 3 全主元法為n3 2 而追趕法僅為5n 3次 可見追趕法是求解三對角方程組的非常好的方法 第二章線性方程組直接解法 2 29 3矩陣分解法 如果用矩陣形式表示 Gauss消元法的消元過程是對方程組 2 1 的增廣矩陣 A b 進(jìn)行一系列的初等行變換 將系數(shù)矩陣A化成上三角矩陣的過程 也等價(jià)于用一串初等變換陣去左乘增廣矩陣 因此 消元過程可以通過矩陣運(yùn)算來實(shí)現(xiàn) 緊接下屏 3 1Gauss消元法的矩陣形式 事實(shí)上 Gauss消元法的第一次消元相當(dāng)于用初等矩陣 第二章線性方程組直接解法 2 30 第二次消元相當(dāng)于用初等矩陣 第k次消元相當(dāng)于用初等矩陣 Gauss消元法的矩陣形式 第二章線性方程組直接解法 2 31 經(jīng)過n 1步消元后得到 因?yàn)長k k 1 2 n 1 均為非奇異陣 故它們的逆矩陣存在 容易求出 這說明 在的條件下 消元過程實(shí)際上是把系數(shù)矩陣A分解成單位下三角陣與上三角矩陣的乘積的過程 Gauss消元法的矩陣形式 續(xù) 第二章線性方程組直接解法 2 32 杜利特爾 Doolittle 分解 LU分解 事實(shí)上 只要A非奇異 由上述結(jié)論 它一定可以分解成兩個(gè)三角形矩陣的乘積 即 A LU 上述分解稱為杜利特爾 Doolittle 分解 也稱為LU分解 當(dāng)系數(shù)矩陣完成三角分解后 對于求解方程組 Ax b 消元過程相當(dāng)于分解A LU及求解三角形方程組Ly b 回代過程則是求解另一個(gè)三角形方程組Ux y 因此 解線性方程組問題可轉(zhuǎn)化為矩陣的三角分解問題 其中 L為單位下三角矩陣 U為上三角矩陣 第二章線性方程組直接解法 2 33 3 2矩陣的三角分解 正如Gauss消元法要在一定條件下才能進(jìn)行到底一樣 矩陣A也必須滿足一定條件才能進(jìn)行三角分解 設(shè)A為n階方陣 若A的順序主子式Ai i 1 2 n 1 均不為零 則矩陣A存在唯一的Doolittle分解 定理2 1 存在性證明 唯一性證明 下面討論如何對A進(jìn)行LU分解 1行1列 由于兩個(gè)矩陣相等就是它們的對應(yīng)元素都相等 因此通過比較A與LU的對應(yīng)元素 即可得到直接計(jì)算L U的元素的公式 A LU即 緊接下屏 第二章線性方程組直接解法 2 34 對A進(jìn)行LU分解 由矩陣乘法規(guī)則及比較 2 11 兩端的元素 得 即可由 2 12 求出U的第一行 L的第一列 下面討論一般情況 即 U的第i行 L的第j列 第二章線性方程組直接解法 2 35 一般情況下 可由 對A進(jìn)行LU分解 r行r列 計(jì)算過程應(yīng)按U第1行 L第1列 第1框 U第2行 L第2列 第2框 的順序 具體分解步驟見下屏 得到計(jì)算uij和lij的公式 第二章線性方程組直接解法 2 36 對A進(jìn)行LU分解的具體步驟 1 計(jì)算U的第1行 L的第1列 亦稱為計(jì)算第1框 2 計(jì)算U的第r行 L的第r列 r 2 n 即第r框 第二章線性方程組直接解法 2 37 矩陣A的LU分解舉例 解 按分解公式 2 13 一框一框分解 每框計(jì)算時(shí)先行后列 所以 例5 第二章線性方程組直接解法 2 38 三角分解的緊湊格式 根據(jù)式 2 13 的特點(diǎn) 矩陣的三角分解可按以下格式及順序進(jìn)行 這種格式既便于記憶 又便于計(jì)算 稱為緊湊格式 見下表2 1 第二章線性方程組直接解法 2 39 1 計(jì)算順序 將aij uij lij按表2 1列好 計(jì)算時(shí)按框從外到內(nèi)進(jìn)行 每一框中先算行 從左向右依次計(jì)算uij 再算列 自上而下求lij 三角分解的緊湊格式 2 計(jì)算方法 按行計(jì)算時(shí) 需將所求元uij的對應(yīng)元aij逐次減去uij所在行左面各框的元素lij乘以uij所在列上面各框相應(yīng)的元uij 按列計(jì)算lij時(shí) 在作上述運(yùn)算后還需除以lij所在框的對角元lij 說明 第二章線性方程組直接解法 2 40 三角分解的緊湊格式舉例 例4中矩陣A的三角分解按緊湊格式計(jì)算 結(jié)果見下表2 2 由表可得 第二章線性方程組直接解法 2 41 3 3直接三角分解法 若線性方程組Ax b的系數(shù)矩陣A完成三角分解 A LU 那么解方程組Ax b等價(jià)于求解兩個(gè)三角形方程組Ly b Ux y 即由 再由 可解得 第二章線性方程組直接解法 2 42 直接三角分解法 續(xù) 容易看出 式 2 14 與式 2 13 的運(yùn)算規(guī)律相同 或者由 可知 若將b作A的最后一列處理 在將A化為上三角陣的同時(shí) 也將b化作了y 故在利用三角分解求解方程組Ax b時(shí) 只需將右端向量b列在表2 1的最后一列 按uij的計(jì)算方法即可求出yk 或在式 2 13 中求uij時(shí) 增加一列 j算到n 1 下表2 3是求解線性方程Ax b的緊湊格式 其計(jì)算順序與計(jì)算方法與三角分解相同 按表2 3計(jì)算后 再按式 2 15 即可求出方程組的解 第二章線性方程組直接解法 2 43 緊湊格式解線性方程組舉例 例6 解 按表2 3計(jì)算 表2 3 第二章線性方程組直接解法 2 44 所以 緊湊格式解線性方程組舉例 續(xù) 第二章線性方程組直接解法 2 45 三角分解法的幾點(diǎn)說明 1 用三角分解法求線性方程的乘除法運(yùn)算量也是n3 3數(shù)量級 由于在求出uij lij和yi后 aij和bi無需保留 故上機(jī)計(jì)算時(shí) 可把L U和y存在A b所占的單元 回代時(shí)x取代y 整個(gè)計(jì)算過程中不需要增加新的存貯單元 3 完成A LU分解后可以較容易地求出行列式 A 的值 2 從三角分解法的推導(dǎo)及例中可以看出 系數(shù)矩陣的三角分解與右端項(xiàng)無關(guān) 因而在計(jì)算多個(gè)系數(shù)矩陣為A而右端不同的線性方程組系時(shí) 用三角分解法更為簡便 如可用于求逆矩陣 第二章線性方程組直接解法 2 46 三角分解法的幾點(diǎn)說明 續(xù) 6 分解法的優(yōu)點(diǎn)除上述2 3外 還有 a 可求解A2z b 因?yàn)樗鉇2計(jì)算量大 可用 b 可根據(jù)A的形狀設(shè)計(jì)算法 當(dāng)A為大型稀疏 且非零元素有規(guī)律如帶狀 三對角等 作分解時(shí)能充分利用A的特點(diǎn) L U能保持A的原狀 即L與A的下三角相同 U與A的上三角形狀相同 4 三角分解法一般也可采用選主元的技術(shù) 以使算法更具數(shù)值穩(wěn)定性 5 也可以把矩陣A分解成一個(gè)下三角矩陣與一個(gè)單位上三角矩陣的乘積 矩陣的這種分解稱為克勞特 Crout 分解 第二章線性方程組直接解法 2 47 4平方根法與改進(jìn)的平方根法 對稱正定矩陣概念 工程實(shí)際問題的計(jì)算中 線性方程組的系數(shù)矩陣常常具有對稱正定性 即其各階順序主子式及全部特征值均大于零 矩陣的這一特性使它的三角分解也有更簡單的形式 從而導(dǎo)出一些特殊的解法 5 A的所有順序主子式均為正數(shù) 即det Ak 0 k 1 2 n 4 A的所有特征值 0 3 A的對角線元素aii 0 i 1 2 n 2 A是非奇異陣 且A 1也是對稱正定陣 1 A的所有順序主子矩陣Ak k 1 2 n 也是對稱正定陣 若A為對稱正定矩陣 則 第二章線性方程組直接解法 2 48 4 1平方根法 定理2 2 證明 首先A可直接作LU分解 記為A LU1 其中 第二章線性方程組直接解法 2 49 定理2 2 續(xù) 其中U0是單位上三角陣 則由A的對稱性可得 再由唯一性得U0 LT 所以A LDLT 并且這種分解是唯一的 又由于U1的對角線元素Ukk就是Gauss消元法的主元素 由于LD1 2是下三角陣 因此有推論 第二章線性方程組直接解法 2 50 Choleskg分解1 推論 若A是對稱正定矩陣 則存在唯一的主對角線元素都為正的下三角陣L 使得 A LLT 矩陣的這種分解稱為Choleskg分解 用比較法可以導(dǎo)出L的計(jì)算公式 設(shè) 比較A與LLT的相應(yīng)元素 即由A LLT可得 計(jì)算順序按列進(jìn)行 因此 第二章線性方程組直接解法 2 51 Choleskg分解2 當(dāng)完成矩陣A的Cholesky分解后 求解方程組AX b就轉(zhuǎn)化求 求解對稱正定線性方程組的方法稱為平方根法 也稱為Cholesky分解法 這種方法無需選主元 計(jì)算過程也是穩(wěn)定的 由于A的對稱性 平方根法的乘除運(yùn)算量為n3 6數(shù)量級 約為直接分解法的一半 上機(jī)計(jì)算時(shí) 所需存貯單元也少 只要存貯A的下三角部分和右端項(xiàng)b 計(jì)算中L存放于A的存貯單元 y x存放在b的存貯單元 平方根法的不足之處在于需作n次開方運(yùn)算 它們的解分別為 第二章線性方程組直接解法 2 52 平方根法舉例 用平方根法解對稱正定方程組 例7 解 先分解系數(shù)矩陣A 只對A的下三角部分運(yùn)算即可 所以只存放A的下三角部分 第二章線性方程組直接解法 2 53 4 2改進(jìn)的平方根法 由定理2 2 對稱正定矩陣A又可以作如下分解 其中 L是單位下三角陣 D是對角陣 U DLT 由于U DLT 即 比較兩邊的對應(yīng)元素可得 首先由緊湊格式的三角分解可得 第二章線性方程組直接解法 2 54 改進(jìn)的平方根法說明 基于上述LDLT分解的方法稱為改進(jìn)的平方根法 其乘除運(yùn)算量與Cholesky分解相當(dāng) 且避免了開方運(yùn)算 計(jì)算順序按先行后列逐層分解計(jì)算 對稱正定陣A完成A ADLT LU分解后 求解方程組 Ax b 就轉(zhuǎn)化為求解 并且由于求y和求U的最后一列的算法完全相同 所以可將y視為U的最后一列進(jìn)行計(jì)算 按上述算法 當(dāng)A為對稱正定陣時(shí) 單位下三角陣L的元素不必按緊湊格式方法去求解 而只需在求得U的第k行元素后 以它們?nèi)コ評kk即得相應(yīng)的L的第k列元素 這樣就大大減少了計(jì)算量 第二章線性方程組直接解法 2 55 改進(jìn)的平方根法舉例 用改進(jìn)的平方根法求解方程組 例8 解 對增廣矩陣 Ab 逐層分解可得 則Ux y為 改進(jìn)平方根法由于對矩陣A無正定要求 只要ukk 0 k 1 2 n 即可 而正定要求ukk 0 k 1 2 n 因此是求解對稱方程組常用的方法 第二章線性方程組直接解法 2 56 5Gauss Jordan消元法求矩陣的逆 Gauss消元法有許多變形 列主元素法是其中之一 在列主元法的基礎(chǔ)上還可對算法進(jìn)行如下的修改 在消元過程中選主元后 先將主元化為1 然后將主元所在列上 下方各元素均化為0 這樣消元的結(jié)果使系數(shù)矩陣化為了單位陣 無需回代就得到了原方程之解 這種無回代過程的列主元素法稱為Gauss Jordan消元法 Gauss Jordan消元法比順序消去法計(jì)算量大一點(diǎn) 實(shí)踐中使用不多 但用它求逆陣卻十分方便 因?yàn)橄^程實(shí)質(zhì)上就是對系數(shù)矩陣A實(shí)行初等變換 將A化為單位陣 相當(dāng)于對A左乘了一系列的初等變換陣M1 M2 Mn 1 Mn 使 緊接下屏 第二章線性方程組直接解法 2 57 Gauss Jordan消元法求矩陣的逆 續(xù)1 這表明同樣的一組初等變換在將A化為I的同時(shí) 可將I化為A 1 即有 因此 以Gauss Jordan消元法求A的逆陣 就是要找到Mi i 1 2 n 以它們逐個(gè)左乘 A I 逐列將A的對角線上的元素化為1 而其余元素化為0 最終將A化為單位陣 則I化為A的逆陣A 1 第二章線性方程組直接解法 2 58 Gauss Jordan消元法求矩陣的逆 續(xù)2 設(shè)增廣陣為 第二章線性方程組直接解法 2 59 這里aij 1 a1j 上述aij 2 的計(jì)算與Gauss消元法基本上相同 僅僅由于m11與Gauss消元法中的乘數(shù)l11不相同引起第一行元素a1j 2 與aij 2 計(jì)算不相同 假若把增廣陣中I的各列視為A的第n 1列 第n 2列 那么上述計(jì)算公式中的第二個(gè)下標(biāo)可擴(kuò)充到2n Gauss Jordan消元法求矩陣的逆 續(xù)3 第二章線性方程組直接解法 2 60 Gauss Jordan消元法求逆陣 續(xù)4 第二章線性方程組直接解法 2 61 Gauss Jordan消元法求逆陣 續(xù)5 第二章線性方程組直接解法 2 62 設(shè)經(jīng)過k 1步后得到 Gauss Jordan消元法求逆陣 續(xù)6 第二章線性方程組直接解法 2 63 Gauss Jordan消元法求逆陣 續(xù)7 其中 第二章線性方程組直接解法 2 64 Gauss Jordan消元法求逆陣 續(xù)8 完成n步消元后 A 1放在原A的位置 第二章線性方程組直接解法 2 65 Gauss Jordan法求逆陣的具體步驟 按上述緊縮存貯原則 可節(jié)省存貯單元 同時(shí)還使得整個(gè)計(jì)算更簡單了 可總結(jié)求逆步驟如下 上述1 2是求第k列元素 構(gòu)成Mk 即求主列 第二章線性方程組直接解法 2 66 計(jì)算其他元素 但少k列 k行 用上述Gauss Jordan法求逆陣 計(jì)算量約為n3 是Gauss消元法的3倍 為保證方法穩(wěn)定性 還可選列主元 若仍按上述緊縮存貯原則 則最后需按行交換的相反次序作列交換才能得到A 1 Gauss Jordan法求逆陣的具體步驟 續(xù) 第二章線性方程組直接解法 2 67 Gauss Jordan法求逆陣舉例 例9 解 按緊縮存貯方式 逐次計(jì)算結(jié)果與存貯如下 第一步 k 1 在第一列中選主元 交換1 2行 得 k 2在第二列對角元下選主元 交換2 3行由1 2先計(jì)算第2列 由3計(jì)算其他元素 除2列2行外 而由4計(jì)算剩下的第2行的元素 這里k 2的第2列第行稱為主列 主行 第三步 k 3以a33 1 6為主元 消元后得 交換2 3列 最后 按行交換的相反次序進(jìn)行列交換 先交換2 3列 再交換1 2列得A 1 第二章線性方程組直接解法 2 68 6方程組的性態(tài)與條件數(shù) 無論用哪種方法求解線性方程組 一般情況下都會(huì)產(chǎn)生誤差 本節(jié)討論線性方程組解的誤差 方程組的解為一組數(shù) 稱為解向量 近似解向量與準(zhǔn)確解向量之差稱為誤差向量 為了估計(jì)誤差向量的大小 首先需引入衡量向量與矩陣大小的度量 范數(shù) 第二章線性方程組直接解法 2 69 6 1向量與矩陣的范數(shù) 這三個(gè)性質(zhì)刻畫了向量長度的基本特征 并可以用其將平面向量長度的概念推廣到一般n維向量 于是有如下定義 定義1 下屏將給出范數(shù)的種類 第二章線性方程組直接解法 2 70 常用的向量范數(shù) 容易證明它們都滿足上述三條性質(zhì) 可以看出 2范數(shù)是平面向量長度計(jì)算公式在形式上的推廣 也是線性代數(shù)中的內(nèi)積定義 此處引入多種范數(shù)來刻畫向量的大小 是為了在不同情況下用不同的范數(shù)研究問題 向量范數(shù)的證明 只對第三條 對 范數(shù) 前面2條顯然 對第三條 由于對任意實(shí)數(shù)x y 絕對值不等式 x y x y 成立 因而有 分別稱為向量x的2范數(shù) 1范數(shù) 無窮范數(shù) 第二章線性方程組直接解法 2 71 對2范數(shù) 利用實(shí)數(shù)的柯西不等式 于是 有 常用的向量范數(shù) 續(xù) 第二章線性方程組直接解法 2 72 Rn中范數(shù)的等價(jià)性 例如可證明如下等價(jià)性 所以 2范數(shù)與 范數(shù)是等價(jià)的 不難證明 亦即1范數(shù)與 范數(shù)是等價(jià)的 事實(shí)上 Rn中任意兩種范數(shù)都是等價(jià)的 第二章線性方程組直接解法 2 73 向量的誤差 有了向量范數(shù) 就可以用它來表示方程組解向量的誤差 設(shè)x是方程組Ax b的準(zhǔn)確解向量 是近似解向量 則 顯然 范數(shù)不同 其誤差值是不一樣的 分別稱為的關(guān)于P范數(shù)的絕對誤差與相對誤差 第二章線性方程組直接解法 2 74 矩陣范數(shù) 定義2 對任意n階方陣A aij n n 若對應(yīng)一個(gè)非負(fù)實(shí)數(shù) A 滿足 則稱 A 為矩陣A的范數(shù) 與向量范數(shù)定義比較 前三條性質(zhì)只是向量范數(shù)定義的推廣 而第四條性質(zhì)則是矩陣乘法性質(zhì)的要求 它使矩陣范數(shù)在數(shù)值計(jì)算中使用更方便 第二章線性方程組直接解法 2 75 常用的矩陣范數(shù) 常用的矩陣范數(shù)有 它們分別叫做矩陣的 范數(shù) 1范數(shù) 2范數(shù) F范數(shù) 矩陣E范數(shù)是向量2范數(shù)的推廣 矩陣 范數(shù) 1范數(shù)計(jì)算容易 而矩陣2范數(shù)與ATA的特征值有關(guān) 所以又稱為譜范數(shù) 它的計(jì)算較困難 但因?yàn)樗幸恍┖玫男再|(zhì) 所以也是常用的范數(shù) 第二章線性方程組直接解法 2 76 常用的矩陣范數(shù) 續(xù) 可以證明 這些范數(shù)都滿足定義2 以 A 為例 前2條性質(zhì)顯然成立 而對 第二章線性方程組直接解法 2 77 最大行和矩陣范數(shù)的證明 第二章線性方程組直接解法 2 78 最大行和矩陣范數(shù)的證明 續(xù) 第二章線性方程組直接解法 2 79 范數(shù)的相容性 在誤差估計(jì)中 由于矩陣與向量會(huì)同時(shí)用到 我們總希望有上面的不等式成立 但對任意的向量范數(shù)與矩陣范數(shù)卻未必如此 因而特別地把滿足此不等式的范數(shù)稱為相容的 可以證明 上述常用的范數(shù)是相容的 即有 在使用范數(shù)時(shí) 應(yīng)選用相容的矩陣范數(shù)與向量范數(shù) 分別稱為的關(guān)于P范數(shù)的絕對誤差與相對誤差 有了矩陣范數(shù) 就可以用它描述矩陣的誤差 設(shè)是A的近似矩陣 稱為的殘差陣 則 第二章線性方程組直接解法 2 80 求范數(shù)舉例 例10 第二章線性方程組直接解法 2 81 6 2舍入誤差的影響及算法的穩(wěn)定性 前面曾介紹了多種解線性方程組的方法 由于計(jì)算機(jī)字長的限制 無論哪種方法 求解的每一步幾乎都可能引入新的舍入誤差 這些誤差隨著計(jì)算的推進(jìn)而向前傳播 算法不同誤差的累積情況不一樣 舍入誤差對解的影響不大的算法稱為數(shù)值穩(wěn)定的算法 可以證明 主元素法 約當(dāng)消去法 Cholesky分解法和追趕法都是數(shù)值穩(wěn)定的算法 第二章線性方程組直接解法 2 82 可以看出 后兩個(gè)方程組與第一個(gè)方程組相比 系數(shù)矩陣或右端向量僅有0 0005以下的誤差 但準(zhǔn)確解卻相差很大 6 3方程組的性態(tài)和條件數(shù) 數(shù)值穩(wěn)定的算法是否一定能求得精度比較高的解呢 回答是不一定 解的精度還與方程組本身的性態(tài)有關(guān) 下面來考察幾個(gè)例 例11 第二章線性方程組直接解法 2 83 方程組的性態(tài)和條件數(shù) 續(xù)1 例12 若其系數(shù) 常數(shù)項(xiàng)改用三位有效數(shù)字的小數(shù)表示 則方程組為 第二章線性方程組直接解法 2 84 右端項(xiàng)b產(chǎn)生0 1 的變化 引起解的變化最大變化184 初始數(shù)據(jù)的誤差 相對 0 3 0 003 而解的相對誤差卻超過50 例13 方程組的性態(tài)和條件數(shù) 續(xù)2 第二章線性方程組直接解法 2 85 方程組的性態(tài)討論 病態(tài) 良態(tài) 在許多實(shí)際問題中 線性方程組的系數(shù)矩陣和右端項(xiàng)的元素大多為前面計(jì)算的結(jié)果 因此上述例中的微小誤差是避免不了 而對上述例中的方程組 無論用多么穩(wěn)定的算法求解 計(jì)算中產(chǎn)生的微小誤差就使解面目全非 所以這些方程組的性態(tài)是很差的 當(dāng)方程組Ax b的系數(shù)矩陣與右端向量b的微小變動(dòng) 小擾動(dòng) 而引起解嚴(yán)重失真時(shí) 稱此方程組為病態(tài)方程組 其系數(shù)矩陣A稱為病態(tài)矩陣 否則稱為良態(tài)方程組 A稱為良態(tài)矩陣 為了定量刻畫方程組 病態(tài) 的程度 下面對方程組Ax b在系數(shù)矩陣A及右端項(xiàng)b有擾動(dòng)的幾種情形進(jìn)行討論 第二章線性方程組直接解法 2 86 此不等式表明 當(dāng)右端項(xiàng)有擾動(dòng)時(shí) 解的相對誤差不超過b的相對誤差的倍 首先考察右端項(xiàng)b的擾動(dòng)對解的影響 設(shè)b有擾動(dòng) b A為準(zhǔn)確 記引起解x的擾動(dòng)為 x 即 方程組的性態(tài)討論 病態(tài) 良態(tài) 續(xù) 第二章線性方程組直接解法 2 87 方程組的性態(tài)討論 續(xù)2 當(dāng)b為精確的而A有微小擾動(dòng) A時(shí) 在 A充分小時(shí)也同樣可推得 緊接下屏討論 第二章線性方程組直接解法 2 88 方程組的性態(tài)討論 續(xù)3 第二章線性方程組直接解法 2 89 方程組的性態(tài)討論續(xù) 3 而當(dāng)A b同時(shí)有微小擾動(dòng) A b時(shí) 則可進(jìn)一步導(dǎo)出更一般的誤差估計(jì)式 注意到 第二章線性方程組直接解法 2 90 在 b充分小時(shí) 此式右端實(shí)際上即為 方程組的性態(tài)討論續(xù) 4 第二章線性方程組直接解法 2 91 矩陣的條件數(shù) 在三種情況下得到的這三個(gè)不等式反映了解的相對誤差與A及b的相對誤差的關(guān)系 數(shù) A A 1 越小 解的相對誤差也越小 反之?dāng)?shù) A A 1 越大 解的相對誤差也越大 實(shí)際上這個(gè)數(shù)反映了解對方程組原始數(shù)據(jù)的敏感程度 揭示了矩陣A和方程組本身的性態(tài) 稱之為方程組或矩陣A的條件數(shù) 記作 cond A 越大 A的病態(tài)程度越嚴(yán)重 至于cond A 多大才算病態(tài) 這是一個(gè)相對概念 沒有一個(gè)嚴(yán)格的數(shù)量界限 第二章線性方程組直接解法 2 92 判斷病態(tài)矩陣的幾點(diǎn)參考 求條件數(shù)要計(jì)算逆陣的范數(shù) 很不方便 如下一些現(xiàn)象可作為判斷病態(tài)矩陣的參考 1 在用主元消去法時(shí)消元過程出現(xiàn)小主元 如例12 2 矩陣A中元素間數(shù)量級相差很大 3 A的行列式det A 滿足 行列式值相對很大 4 矩陣的某些行 或列 近似相關(guān) 如例11 第二章線性方程組直接解法 2 93 利用條件數(shù)判斷矩陣的性態(tài)舉例 A的條件數(shù)很大 所以方程組是病態(tài)的 的特例 它是典型的 病態(tài) 陣 n越大 病態(tài) 越嚴(yán)重 如n 6時(shí) cond A 29 106 對嚴(yán)重 病態(tài) 的方程組 即使用主元素法求解也難以保證數(shù)值穩(wěn)定性 第二章線性方程組直接解法 2 94 第二章 結(jié)束 第二章線性方程組直接解法 2 95 定理3 1存在性證明 當(dāng)i 1 因?yàn)锳1 a11 0由3 1的討論 存在矩陣 假定結(jié)論對j k 1成立 即 按歸納法原理 存在初等矩陣L1 Ln 1 使得 唯一性證明 返回 第二章線性方程組直接解法 2 96 定理3 1唯一性證明 返回 對于唯一性 假定A有兩種Dolittle分解 由于單位下 上 三角陣的逆仍是單位下三角陣 而為上三角陣 它們不可能相等 若要相等 必定有