NC-2-1.ppt

1、1,第2章 線性方程組的解法,計(jì)算方法/數(shù)值計(jì)算,胡小兵 E-mail: 重慶大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,2,主要內(nèi)容,線性方程組的直接解法； 向量與矩陣的范數(shù)、條件數(shù)的概念; 線性方程組的迭代解法.,3,在自然科學(xué)和工程技術(shù)中，很多問(wèn)題歸結(jié)為解線性方程組。,線性方程組,有的問(wèn)題的數(shù)學(xué)模型中雖不直接表現(xiàn)為含線性方程組，但它的數(shù)值解法中將問(wèn)題“離散化”或“線性化”為線性方程組。因此線性方程組的求解是數(shù)值分析課程中最基本的內(nèi)容之一。,4,線性方程組,(2.1),(2.2),若|A| 0, (2.2)的解存在且唯一。,5,線性方程組的解法,直接法：經(jīng)過(guò)有限次的算術(shù)運(yùn)算，可以求得(2.1)的精確解（假定計(jì)算過(guò)

2、程沒(méi)有舍入誤差）。如克萊姆算法。但該法對(duì)高階方程組計(jì)算量太大。實(shí)用的直接法中具有代表性的算法是高斯消元法。,迭代法：它將(2.1)變形為某種迭代公式，給出初始解x0，用迭代公式得到近似解的序列xk, k=0, 1, 2, 在一定的條件下xkx* (精確解)。,注意：迭代法需考慮收斂條件和收斂速度問(wèn)題。,6,高斯(Gauss)消元法,高斯消元法是將線性方程組通過(guò)初等變換化為上三角形方程組，再回代得其解。是一種直接方法。,第一步，將(2.3)乘-2加到(2.4)；(2.3)乘-1加到(2.5), 得到：,7,高斯消元法,第二步,將(2.6)乘-2/3加到(2.7),得到:,回代：解(2.8)得x3

3、, 將x3代入(2.6)得x2, 將x2, x3代入(2.3)得 x1, 得到解 x*=(2, 1, -1)T,8,高斯消元法,容易看出，第一步和第二步相當(dāng)于增廣矩陣:b在作行變換，用ri表示增廣陣A:b的第 i 行:,9,高斯消元法-思路,思路：逐次消去未知數(shù)的系數(shù)，將Ax=b化為等價(jià)的三角形方程組，然后回代解之。,10,高斯消元法-思路,設(shè)第 k-1（k=1,2,n-1） 步消元后的系數(shù)矩陣記為：,第 k 次消元，化為0,i=k+1,k+2,n 第 i 行消元系數(shù),11,高斯消元法步驟,1. 消元,令,對(duì)k =1到n-1, 若 , 進(jìn)行:,12,高斯消元法步驟,2. 回代,若 , 則:,(

4、i=n-1,n-2,1) (2.10),消元過(guò)程要求： 回代過(guò)程則進(jìn)一步要求：,13,高斯(Gauss)消元法,定理2.1 Ax=b能用高斯消元法解的充要條件是A的各階順序主子式不為零。,A的各階順序主子式：,14,Gauss消元法問(wèn)題,問(wèn)題1：消元時(shí)可能出現(xiàn) 的情況，高斯消元法失效。,問(wèn)題2：即使 ，但 ，此時(shí)用它作除數(shù),也會(huì)導(dǎo)致其它元素?cái)?shù)量級(jí)嚴(yán)重增加，帶來(lái)舍入誤差的擴(kuò)散，使解嚴(yán)重失真。,15,解決思路,怎么辦？,列主元高斯消元法,基本思想：每次從所在列對(duì)角線及以下元素中選擇絕對(duì)值最大的元素作為主元進(jìn)行消元運(yùn)算。,16,列主元Gauss消元法,設(shè)已用列主元消元法完成Ax=b的第k-1次消元(

5、1kn-1), 此時(shí)方程組Ax=bA(k)x=b(k)，有如下形式:,(2.12),17,列主元Gauss消元法, 在方框內(nèi)的一列內(nèi)選出絕對(duì)值最大者，即確定ik：,若 ，則必有方框內(nèi)的元素全為零，此時(shí)易證A=A(k)=0，即方程組Ax=b無(wú)確定解,進(jìn)行第 k 次消元前，先進(jìn)行、兩個(gè)步驟:,18,列主元Gauss消元法,然后，用高斯消元法進(jìn)行消元：從k=1到k=n-1,就完成了消元過(guò)程，只要A0，列主元高斯消元法必可進(jìn)行下去。,19,高斯-若當(dāng)消元法,(2.13）,是高斯消元法的一種變形。同時(shí)消去對(duì)角元上方和下方的元素，而且將對(duì)角元化為1。設(shè)已完成k-1步,于是Ax=b化為等價(jià)方程組A(k)x=

6、b(k)，增廣陣為：,20,高斯-若當(dāng)消元法,1.按列選主元，確定ik使,2.換行，交換增廣陣第 k 行和第 ik 行,(j=k, k+1,n),在第 k 步計(jì)算時(shí)，考慮將第 k 行上下的第 k 列元素都化為零, 且akk化為1。對(duì)k=1,2,n,21,高斯-若當(dāng)消元法,3 計(jì)算乘數(shù) mik= - aikakk (i=1,2,n, ik) mkk=1akk (2.14),4 消元 aij=aij+mikakj (i=1,2,n,且ik,j=k+1,n) bi=bi+mikbk (i=1,2,n,且ik) (2.15),5 主行計(jì)算 akj=akjmkk (j=k,k+1,n) bk=bkmkk

7、 (2.16),22,高斯-若當(dāng)消元法,顯然xi=bi（i=1,2,n）就是Ax=b的解。,當(dāng)k = n時(shí),23,高斯-若當(dāng)消元法,高斯-若當(dāng)消元法解方程組并不比高斯消元法優(yōu)越,但用于矩陣求逆是適宜的,實(shí)際上它是初等變換方法求逆的一種規(guī)范化算法:,例3 已知 ，求,24,高斯-若當(dāng)消元法,25,高斯-若當(dāng)消元法,26,高斯-若當(dāng)消元法,所以,Gauss-Jordan法的Matlab程序見(jiàn)課本P13頁(yè)。,27,矩陣三角分解,三角分解：設(shè) ，若存在下三角矩陣L和一個(gè)上三角陣U使得 A=LU，則稱LU為矩陣A的三角分解.,L - 下三角矩陣 U - 上三角矩陣,28,矩陣的Doolittle分解,D

8、oolittle分解：限定L是單位下三角矩陣（對(duì)角線為1的下三角矩陣）。,矩陣L與U滿足一定條件，才能保證分解的唯一性。,29,矩陣三角分解條件,定理2.2 若矩陣A的各階順序主子式非零，則A可進(jìn)行Doolittle分解和Crout分解，且這種分解是唯一的。,利用LU分解解線性方程組:,LUx = b,令 Ux = y, 則 Ly = b,Ax = b,兩個(gè)等價(jià)的三角形方程組容易求解,30,Doolittle分解,方法1：用不帶行交換Gauss消元法。其中L的下三角元素就是由消元運(yùn)算的乘數(shù)因子組成，U是消元運(yùn)算結(jié)束后的上三角矩陣。,分解方法：,方法2：用矩陣乘法原理推出計(jì)算公式。,31,Doo

9、little分解-思路,比較等式兩邊的第一行得：,u1j = a1j,比較等式兩邊的第一列得：,比較等式兩邊的第二行得：,比較等式兩邊的第二列得：,( j = 1, n ),( i = 2, n ),( j = 2, n ),( i = 3, n ),繼續(xù)下去,32,利用矩陣乘法做Doolittle分解,1、計(jì)算U 的第一行： ；,2、計(jì)算L 的第 一列： ；,3、對(duì)k = 2,3,n 進(jìn)行以下的計(jì)算：,（2.14）,（2.15）,33,回代求解線性方程組,4、解,（2.16）,5、解,（2.17）,34,例子,例2.3 用LU分解方法求解方程組,解: 由公式(2.14)(2.15),35,例

10、子,于是化為兩個(gè)方程組,用(2.16)式解第一個(gè)方程組 ，代入第二個(gè)方程組，用(2.17)式解之得,36,矩陣的Crout分解,Crout分解：限定U為單位上三角矩陣（對(duì)角線為1的上三角矩陣）。,37,2、計(jì)算U 的第一行： ；,3、對(duì) k=2,3,n 進(jìn)行以下的計(jì)算：,Crout分解,1、計(jì)算L 的第 一列， ；,38,Crout分解,4、解,5、解,39,平方根法,定理2.3 設(shè)矩陣A對(duì)稱正定，則存在三角分解A=LLT，L是非奇異下三角矩陣，且當(dāng)限定的對(duì)角元為正時(shí)，這種分解是唯一的。,稱為對(duì)稱正定矩陣的Cholesky分解。,L,LT,40,平方根法 -計(jì)算公式,1、計(jì)算L的第一列：,2、對(duì) k = 2, 3, n 進(jìn)行以下的計(jì)算：,41,平方根法 - 計(jì)算公式,3、解,4、解,42,追趕法,在三次樣條插值，常微分方程的邊值問(wèn)題等都?xì)w結(jié)為求解系數(shù)矩陣為對(duì)角占優(yōu)的三對(duì)角方程組 Ax = f，即:,其中|i-j|1時(shí)，aij=0，且滿足如下的對(duì)角占優(yōu)條件: (1) |b1|c1|0, |bn|an|0 (2) |bi|ai|+|ci|, aici0, i=2,3,n-1.,43,追趕法,對(duì)A作