理學(xué)數(shù)值分析學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1理學(xué)理學(xué)(lxu)數(shù)值分析數(shù)值分析第一頁，共119頁?？巳R姆（克萊姆（CramerCramer）法：）法： 一種一種(y zhn)(y zhn)解線性代數(shù)方程解線性代數(shù)方程組的直接法組的直接法11112211211222221122 nnnnnnnnnnna x a xa xba x a xa xba x a xa xb階線性方程組： , X ,11Tn nijAXbTA nn , , ) , , )(x(bxbab矩陣表示記為這里第1頁/共119頁第二頁，共119頁。 det( )0det() (1,2, )det( )iiAAxinA根據(jù)克萊姆(cramer)法則，若方程組系數(shù)行列

2、式不為零，即，則該方程組有唯一解。其解為1 (1)!nnnnnn這種方法需要計(jì)算行列式并作，而每個(gè)階個(gè) 階次除行列式計(jì)算需作法次乘法。3530,2.38 10nn如需次乘法。理論較大時(shí)，實(shí)上是絕對正確際計(jì)算，但不可行。計(jì)算量十分驚人!在實(shí)際在實(shí)際(shj)中如何利用計(jì)算機(jī)這一強(qiáng)有力工具求解線性方程中如何利用計(jì)算機(jī)這一強(qiáng)有力工具求解線性方程？第2頁/共119頁第三頁，共119頁。3.1 消元法消元法 計(jì)算機(jī)解線性方程組的一種計(jì)算機(jī)解線性方程組的一種(y zhn)直接法直接法思路：思路：1 1）先將）先將A A化為上三角化為上三角(snjio)(snjio)陣陣 ( (消消元元) ) 2 2）再回

3、代求解）再回代求解 。 ( (回代回代) )=高斯消元法高斯消元法第3頁/共119頁第四頁，共119頁。消元消元記記,)()1()1(nnijaAA )1()1(1)1(.nbbbbStep 1：設(shè)設(shè) ，計(jì)算因子，計(jì)算因子0)1(11 a)., 2(/)1(11)1(11niaamii 將增廣矩陣將增廣矩陣，得到，得到)1(1)1(1)1(12)1(11.baaan)2(A) 2(b).,2,()1(11)1()2()1(11)1()2(njibmbbamaaiiijiijij 其中其中Step k：設(shè)設(shè) ，計(jì)算因子，計(jì)算因子且計(jì)算且計(jì)算0)( kkka)., 1(/)()(nkiaamkkk

4、kikik )., 1,()()()1()()()1(nkjibmbbamaakkikkikikkjikkijkij 共進(jìn)行共進(jìn)行(jnxng) (jnxng) ？ 步步n 1 )()2(2)1(121)()2(2)2(22)1(1)1(12)1(11.nnnnnnnnbbbxxxaaaaaa第4頁/共119頁第五頁，共119頁?；卮卮?)()(/nnnnnnabx 0)( nnna 如果如果 ?沒有沒有(mi yu)唯唯一解一解.) 1., 1()(1)()( niaxabxiiinijjiijiii0)( iiia 如果如果 ?定理定理(dngl) 若若A的所有順序主子式的所有順序主子式

5、 均不為均不為0，則高斯消元無需，則高斯消元無需換行即可進(jìn)行到底換行即可進(jìn)行到底(do d)，得到唯一解。，得到唯一解。iiiiiaaaaA.)det(1111 事實(shí)上，只要事實(shí)上，只要 A 非奇異，即非奇異，即 A 1 存在，則可通過逐次存在，則可通過逐次消元及行交換，將方程組化為三角形方程組，求出唯消元及行交換，將方程組化為三角形方程組，求出唯一解。一解。第5頁/共119頁第六頁，共119頁。問題(wnt)?第6頁/共119頁第七頁，共119頁。例：例：單精度解方程組單精度解方程組 211021219xxxx 精確解為精確解為 和和 .1000.00. 1101191 x8個(gè)個(gè).8999.

6、99. 0212 xx8個(gè)個(gè)用單精度用單精度(8位位)高斯消元法計(jì)算高斯消元法計(jì)算(j sun)：911212110/ aam999212210101010.0 . 011 ma8個(gè)個(gè)92121012 mb 9991010011100, 112 xx原因：小主元原因：小主元 導(dǎo)致計(jì)導(dǎo)致計(jì)算算(j sun)失敗。失敗。（大數(shù)（大數(shù)(d sh)吃吃小數(shù)）小數(shù)）（大數(shù)吃小數(shù)）（大數(shù)吃小數(shù)）（結(jié)果差異很大（結(jié)果差異很大）第7頁/共119頁第八頁，共119頁。全主元消去法全主元消去法每一步選絕對值最大的元素為主元素每一步選絕對值最大的元素為主元素，保證，保證 。1| ikmStep k: 選選取取|ma

7、x |0 ;kkijijkinkjnaa If ik k then 交換交換(jiohun)第第 k 行與第行與第 ik 行行; If jk k then 交換交換(jiohun)第第 k 列與第列與第 jk 列列; 消元消元列主元消去法列主元消去法省去換列的步驟省去換列的步驟(bzhu)，每次僅選一列中最大的元。，每次僅選一列中最大的元。0|max|, iknikkiaak 在在第第k kn n行，行，第第k kn n列選列選擇擇kki ja第8頁/共119頁第九頁，共119頁。在第一行在第一行是個(gè)小數(shù)是個(gè)小數(shù)(xiosh)，仍是小，仍是小主元主元 導(dǎo)致導(dǎo)致計(jì)算失敗計(jì)算失敗例：例： 2111

8、11091,112 xx 110211 11102119 0,112 xx例例： 2111010199 99991010010101注意：這兩個(gè)方程組注意：這兩個(gè)方程組在數(shù)學(xué)上在數(shù)學(xué)上嚴(yán)格等價(jià)嚴(yán)格等價(jià)。 取取a21為主元，為主元，避免避免(bmin)大大吃小吃小第9頁/共119頁第十頁，共119頁。(GaussLU由由消消元元法法加加上上列列主主元元 或或全全主主元元）法法有有分分解解： 矩陣矩陣(j zhn)(j zhn)三角分解法三角分解法11121n21222n313212(1)nn111 U 1nnn nALULuuuluulllllu L單位單位(dnwi)下三角下三角矩陣矩陣U上三

9、角矩陣上三角矩陣第10頁/共119頁第十一頁，共119頁。11121314111213142121222324222344313231323334333441424341424344441000100010001000aaaauuuulaaaauuullaaaauulllaaaau1112131421112112222113232114243111311232223113322333311432243441114112422241134223433341144224433444uuuul ul uul uul uul ul ul ul ul uul ul uul ul ul ul ul ul

10、ul ul ul uu直接直接(zhji)(zhji)計(jì)算計(jì)算 A A 的的 LU LU 分分解：解：第11頁/共119頁第十二頁，共119頁。1212111313111414111i1111 , , ; , i2,nilla ula ula ula u列111111212131314141j1 , , , ; , j1, ,n juuauauauaua行直接直接(zhji)(zhji)比對等式兩端矩比對等式兩端矩陣元素陣元素2222211223232113242421142j221132323112224242411222i22u2 - , - , - ; - , j2, ,n 2 (-)

11、, (-) ; (-jjilua l uua l uua l uua l ula l uula l uula行列i21222) i3, , n.l uu第12頁/共119頁第十三頁，共119頁。i111111 , i2, , j1, ,n , njjiuala uk-1ikk-1kjkmkmimkm 11 jk , 2, 3, , ( )/ ik1, , , n n ikmkkjmjknuallal uuu對計(jì)算一般一般(ybn)計(jì)算公式：計(jì)算公式：第13頁/共119頁第十四頁，共119頁。LULU分解系數(shù)的計(jì)算分解系數(shù)的計(jì)算(j (j sun)sun)順序順序2131413242433331

12、11213222344211323211121314212211121122223243132333441424314111213141442144441000100010001000aaaauuul uuaaauul uullaallluaaaaaaauuuuuluuuulul311232224112422231133223333114322434311141114114422443344441134223433432l ul ul ul ul ul uul ul uul ull ul uul ulll uuuuu按顏色順序依次計(jì)算按顏色順序依次計(jì)算給定矩陣給定矩陣A A，如何計(jì)算，如何計(jì)算

13、(j sun)(j sun)其對應(yīng)的其對應(yīng)的L L矩陣和矩陣和U U矩陣？矩陣？第14頁/共119頁第十五頁，共119頁。Matlab的符號計(jì)算 思考題：習(xí)題(xt)2，寫出4階三對角矩陣的LU分解公式第15頁/共119頁第十六頁，共119頁。112221313212(1)1111121n22222nnn111 1 UXnnnnn nnnybybLYbybxyxyYxylllllluuuuuu 利用利用(lyng)LU(lyng)LU分解求解線性方分解求解線性方程組程組Y L b , UXY AXbLbUX即: 思路思路(sl)：第16頁/共119頁第十七頁，共119頁。11-11 , 2,

14、3, , (1) Y iiijijjinybyybl求解：1ijii , in 1, , 1 (2) x nnnniijij nyxuyxu xu求解：兩步算法兩步算法(sun (sun f)f)：第17頁/共119頁第十八頁，共119頁。12312314 2521831520 xxx 100123 2100143510024ALU 計(jì)解解：用用分分解解算算公公式式得得例：用三角分解例：用三角分解(fnji)(fnji)法求解線性方程法求解線性方程 (14,18,20)(14, 10, 72) ,(14, 10, 72)(1,2,3) .TTTTLyyUxx求解第18頁/共119頁第十九頁，共

15、119頁。PALU0321ALULU分解：分解：111203uu212111?aluMatlab中中LU分解函數(shù)分解函數(shù)(hnsh)“l(fā)u()”。 調(diào)用方式：調(diào)用方式：“L,U,P = lu(A)” 思考：利用思考：利用 MATLAB中的幫助文件中的幫助文件“ help lu” ， 查看查看lu函數(shù)的幫助文檔，說明函數(shù)的幫助文檔，說明(shumng)其中其中L, U, P 各是各是 什么矩陣。什么矩陣。 L, U, P, A如何構(gòu)成等式。如何構(gòu)成等式。置換矩陣置換矩陣n更一般形式：更一般形式：第19頁/共119頁第二十頁，共119頁。由線性代數(shù)由線性代數(shù)(xin xn di sh)(xin x

16、n di sh)知，對稱正定陣的幾知，對稱正定陣的幾個(gè)重要性質(zhì)：個(gè)重要性質(zhì)： A1 亦對稱亦對稱(duchn)正定正定，且，且 aii 0 A 的順序的順序(shnx)主子陣主子陣 Ak 亦對稱亦對稱正定正定 A 的特征值的特征值 i 0 A 的的全部順序主子式全部順序主子式 det ( Ak ) 0 3.2 3.2 Cholesky Cholesky 分解分解（平方根法）（平方根法）： 的分解法的分解法一個(gè)矩陣一個(gè)矩陣 A = ( aij )n n ，如果，如果 aij = aji稱為稱為對稱陣對稱陣。即。即A=AT定義：定義：一個(gè)矩陣一個(gè)矩陣 A 稱為稱為正定陣正定陣，如果，如果 對任意非

17、零對任意非零向量向量 都成立。都成立。 0 xAxTx定義：定義：第20頁/共119頁第二十一頁，共119頁。u 若若A A為為n n階滿秩方陣，則有階滿秩方陣，則有ATAATA為對稱為對稱(duchn)(duchn)正定正定矩陣矩陣() ()0TTTx A AxAxAx 又又 ATA ATA為對稱為對稱(duchn)(duchn)矩陣矩陣0TTx A Ax 由于由于(yuy)A滿秩，即方程滿秩，即方程 A x = 0 只有只有0解，所以任意非零向量解，所以任意非零向量有：有：根據(jù)正定矩陣定義，根據(jù)正定矩陣定義，則有則有A AT TA A為對稱正定矩陣為對稱正定矩陣對稱正定矩陣對稱正定矩陣Ch

18、oleskyCholesky分解：分解：證明：證明： 第21頁/共119頁第二十二頁，共119頁。先將對稱先將對稱(duchn) (duchn) 正定陣正定陣 A A 做做 LU LU 分解：分解：U =uij=u11uij / uii111u22unn記為記為DU A 對稱對稱TUL 即即1122()TTALDLDLDL記記 D1/2 =11u22unnuWhy is uii 0?Since det(Ak) 02/1LDL 則則 仍是下三角陣仍是下三角陣TLLA n nLR定理定理 設(shè)矩陣設(shè)矩陣A對稱正定，則存在唯一下三角陣對稱正定，則存在唯一下三角陣 ，其，其對角元素為正，使得對角元素為正

19、，使得 ，A的這種分解稱為的這種分解稱為Cholesky 分解分解。TALL 對于對稱正定陣對于對稱正定陣 A ，從，從 可知對任意可知對任意k i 有有 。即即 L 的元素不會(huì)增大，的元素不會(huì)增大，誤差可控誤差可控，。 ikikiila12iiikal |稱為稱為(chn wi)Cholesky 分解分解單位單位(dnwi)上三角陣上三角陣第22頁/共119頁第二十三頁，共119頁。 LULU分解和分解和CholeskyCholesky矩陣矩陣(j zhn)(j zhn)分解的關(guān)系：分解的關(guān)系：l已知已知LU分解求分解求cholesky分分解解： 其中其中 D1/2 =11u22unnu2/

20、1LDL L如何計(jì)算如何計(jì)算D D？U U矩陣的矩陣的對角線元素，或?qū)蔷€元素，或 的對角線元素平方的對角線元素平方。12LLD1/21/21/2()( )TTTUDLDLDDLl已知已知cholesky分解分解，求求LU分解分解：:TTAAxbA AxA b如如果果秩秩，有有 滿則 第23頁/共119頁第二十四頁，共119頁。例例對矩陣對矩陣 A = 進(jìn)行進(jìn)行Cholesky分解。分解。410141014程序程序A=4,1,0;1,4,1;0,1,4;P=chol(A)P = 2.0000 0.5000 0 0 1.9365 0.5164 0 0 1.9322結(jié)果結(jié)果是是( )TL第24頁/

21、共119頁第二十五頁，共119頁。n 為了研究線性方程組近似為了研究線性方程組近似(jn s)(jn s)解的誤差估計(jì)和迭代法的收斂性，引進(jìn)解的誤差估計(jì)和迭代法的收斂性，引進(jìn)向量（矩陣）的范數(shù)的概念。向量（矩陣）的范數(shù)的概念。衡量衡量(hng ling)向向量或矩陣量或矩陣 “大小大小”的概念的概念概念是概念是長度和距離概念長度和距離概念的推廣的推廣第25頁/共119頁第二十六頁，共119頁。 向量向量(xingling)范數(shù)（范數(shù)（Vector norm）Rn空間的空間的向量范數(shù)向量范數(shù) | | 對任意對任意 滿足下列條件滿足下列條件：nRyx ,00|;0|) 1 ( xxx（正定性（正定

22、性(dng xng)|) 2(xx C 對任意對任意(rny)(齊次性齊次性) |) 3(yxyx （三角不等式三角不等式)常用向量范數(shù)常用向量范數(shù)：11niixx（ 1 范 數(shù) ）1/ 22212niixx（ 范數(shù)或歐氏范數(shù)）1/1ppnpipixx（ 范數(shù)）m axiixx（范 數(shù) ）n定義：定義：第26頁/共119頁第二十七頁，共119頁。000011,0;00niixxxx1xx0 xaaxxx yxy不滿足性質(zhì)不滿足性質(zhì) 2 2aaxx不滿足性質(zhì)不滿足性質(zhì) 1 10 xx0n例：判斷例：判斷(pndun)下面定義式是否是向量范下面定義式是否是向量范數(shù)數(shù)（1）（2）第27頁/共119頁

23、第二十八頁，共119頁。12xx12xx向量不能比大小向量不能比大小向量通過定義范向量通過定義范數(shù)比大小數(shù)比大小 最重要的用途最重要的用途(yngt)之一：分析向量收斂性，定義向量之一：分析向量收斂性，定義向量的極限：的極限：向量序列向量序列 于向量于向量 ,是指對每一個(gè)是指對每一個(gè) 1 i n 都有都有 。)(kx*x*)(limikikxx 可以理解為可以理解為0|*|)( xxk可理解為對任何向可理解為對任何向量量(xingling)范數(shù)范數(shù)都成立。都成立。定義：定義：第28頁/共119頁第二十九頁，共119頁。收斂收斂(shulin)意義意義上的等價(jià)，即在不上的等價(jià)，即在不同范數(shù)下的收

24、斂同范數(shù)下的收斂(shulin)性是一致性是一致的的定理定理Rn 上一切范數(shù)都等價(jià)。上一切范數(shù)都等價(jià)。1212,0 nststsxxRc cc xxcx：設(shè)和是上的任意兩種向量范數(shù)，則存在常數(shù)，使得 向量范數(shù)的等價(jià)向量范數(shù)的等價(jià)(dngji)性定理（性定理（79頁定理頁定理3A.1）：）：利用向量范數(shù)的等價(jià)性定理，很容易得到下列推論：利用向量范數(shù)的等價(jià)性定理，很容易得到下列推論：推論：向量序列推論：向量序列(xli)在某范數(shù)下收斂，則在任意范數(shù)下收斂。在某范數(shù)下收斂，則在任意范數(shù)下收斂。第29頁/共119頁第三十頁，共119頁。 矩陣矩陣(j zhn)(j zhn)范數(shù)（范數(shù)（Matrix n

25、ormMatrix norm）Rm n空間的空間的矩陣范數(shù)矩陣范數(shù) | | 對任意對任意 滿足：滿足：nmRBA ,00|;0|) 1 ( AAA（正定性（正定性(dng xng)|) 2(AA C 對任意對任意(rny)(齊次性齊次性) |) 3(BABA （三角不等式三角不等式)(4) | AB | | A | | B | （相容相容 ( (當(dāng)當(dāng) m = n 時(shí)時(shí))定義：定義：意味多個(gè)矩陣（向量）運(yùn)算意味多個(gè)矩陣（向量）運(yùn)算時(shí)，誤差是可控的時(shí)，誤差是可控的第30頁/共119頁第三十一頁，共119頁。Frobenius 范數(shù)與范數(shù)與向量向量(xingling)2范數(shù)相容范數(shù)相容矩陣矩陣(j

26、zhn) ATA 的最大的最大特征根特征根常用常用(chn yn)矩陣范數(shù)：矩陣范數(shù)：1. Frobenius 范數(shù)范數(shù) ninjijFaA112| 向量向量| |2的直接推廣的直接推廣 對方陣對方陣 以及以及 有有nnRA nRx 22|xAxAF 2. 算子算子范數(shù)范數(shù) 由向量范數(shù)由向量范數(shù) | |p 導(dǎo)出的關(guān)于矩陣導(dǎo)出的關(guān)于矩陣 A Rn n 的的 p 范數(shù)范數(shù):pxpppxAxxAApx|max|max|10| 則則ppppppxAxABAAB| 常用算子常用算子范數(shù)有范數(shù)有： njijaAni1|max|1（行和范數(shù)行和范數(shù)） niijaAnj11|max|1（列和范數(shù)列和范數(shù)）)(

27、|max2AAAT （譜范數(shù)譜范數(shù) ）稱為稱為算子范數(shù)（算子范數(shù)（誘導(dǎo)范數(shù)）誘導(dǎo)范數(shù)）滿足相容性滿足相容性向量范數(shù)向量范數(shù)第31頁/共119頁第三十二頁，共119頁。我們我們(w men)只關(guān)心有相容性的范數(shù)，算子范數(shù)總是只關(guān)心有相容性的范數(shù)，算子范數(shù)總是相容的。相容的。即使即使(jsh) A中元素全為實(shí)數(shù)，其特征根和相應(yīng)特征向量中元素全為實(shí)數(shù)，其特征根和相應(yīng)特征向量 仍可能是復(fù)數(shù)。將上述定義中絕對值換成復(fù)數(shù)模均成立。仍可能是復(fù)數(shù)。將上述定義中絕對值換成復(fù)數(shù)模均成立。否則，必存在某個(gè)向量范數(shù)否則，必存在某個(gè)向量范數(shù)| |v 使得使得 對任意對任意A 成立。成立。vvFxxAAx|max|0 注

28、：注：Freebies范數(shù)不是范數(shù)不是(b shi)算子范數(shù)算子范數(shù)021|1max1|xnvFivI xInx設(shè)設(shè)AI（單位陣），（單位陣），其其| |F為：為：| |F不是算不是算子范數(shù)子范數(shù)第32頁/共119頁第三十三頁，共119頁。例：已知矩陣?yán)阂阎仃?j zhn)A(j zhn)A，求算子，求算子1 1范數(shù)和算子范數(shù)和算子范范數(shù)。數(shù)。1max2161236 654 15789 1415 2416 ()16.712497TAAAAA A所以，行和范數(shù)為 ，列和范數(shù)為和列 和行第33頁/共119頁第三十四頁，共119頁。 任意離散有限線性算子任意離散有限線性算子(sun z)可表示為

29、矩陣形式可表示為矩陣形式?？杀硎緸榭杀硎緸榫仃囆问骄仃囆问?00000( )( )00.0000aay nax nxya1)1)尺度算尺度算子：子：LTI：線性時(shí)不變系統(tǒng)：線性時(shí)不變系統(tǒng)(xtng)n為什么叫做為什么叫做“算子范數(shù)算子范數(shù)”？線性時(shí)不變算子線性時(shí)不變算子的矩陣表示的矩陣表示第34頁/共119頁第三十五頁，共119頁。11000(1)(2)(1)01 .00(2)(3)(2)( )(1)( )00.10.00011(1)( )(1)00001( )0( )xxxxxxy nx nx nx nx nx nx nx n2)2)差分差分(ch (ch fn)fn)算子算子1111(1)

30、10000(1)(1)(2)11.00(2).( )( )11.00.( )11110(1)11111( )( )nniinixxxxxy nx ix ix nx nx i3)3)累加算子累加算子(sun z)(sun z)不考慮邊界不考慮邊界問題問題第35頁/共119頁第三十六頁，共119頁。00000(1)010.00(2)(1)( )(1)01.00.00.00(1)(2)00010( )(1)xxxy nx nx nx nx nx n 4)4)時(shí)移算子時(shí)移算子(sun z)(sun z)用用D表示表示線性微分方程012012(1)(2)(1)(2)012012(1)(2) ( )(1)

31、(2)( )(1)(2) a x na x na x nb y nb y nb y na Ia Da Dxb Ib Db DyDD可記為：其中，為一階，二階時(shí)移算子線性時(shí)不變算子線性時(shí)不變算子(sun z)的矩陣表示的矩陣表示第36頁/共119頁第三十七頁，共119頁。0 0010 20 (1)1011121(1)(1) 0(1)1(122222222210222) 2(1) (1)2.( )( ).jjjjNNNNjjjjNNNNNjkiNijjNNjjNNNNNNNNNeeeeeeeey kex ieeee (0)(0)(1)(1) .(1)(2)(1)(1)xyxyx Ny Nx Ny

32、N5)5)傅立葉變換傅立葉變換(binhun)(binhun)線性時(shí)變線性時(shí)變(sh bin)算子的矩陣表示算子的矩陣表示第37頁/共119頁第三十八頁，共119頁。譜半徑譜半徑 （討論特征（討論特征(tzhng)(tzhng)根與根與范數(shù)的關(guān)系范數(shù)的關(guān)系 ）矩陣矩陣A的的譜半徑譜半徑記為記為 (A) = ，其中，其中 i 為為 A 的特征根。的特征根。|max1ini ReIm (A)定義定義(dngy)：特征特征(tzhng)根根中最大的模中最大的模為譜半徑為譜半徑n矩陣范數(shù)的性質(zhì)矩陣范數(shù)的性質(zhì)第38頁/共119頁第三十九頁，共119頁。所以所以(suy)2-范數(shù)范數(shù)亦稱為譜范數(shù)。亦稱為譜

33、范數(shù)。定理定理對任意算子范數(shù)對任意算子范數(shù) | | 有有|)(AA 證明證明(zhngmng)：由算子范數(shù)的相容性，得到由算子范數(shù)的相容性，得到|xAxA 將任意一個(gè)特征根將任意一個(gè)特征根 所對應(yīng)的特征向量所對應(yīng)的特征向量 代入代入u| |AuAuA |uu 定理定理若若A對稱矩陣，則有對稱矩陣，則有)(|2AA 證明證明(zhngmng)：)()(|2maxmax2AAAAT A對稱對稱若若 是是 A 的一個(gè)特征根，則的一個(gè)特征根，則 2 必是必是 A2 的特征根。的特征根。因因 任意性，則有任意性，則有1( )max | |i niAA 若若 （最大特征根），（最大特征根），則則 02 必

34、是必是 A2 的最的最大特征根。大特征根。0( ) |A222max00|()( )AAA計(jì)算計(jì)算2-范數(shù)的范數(shù)的一種方法一種方法第39頁/共119頁第四十頁，共119頁。后面分析病態(tài)后面分析病態(tài)(bngti)問題問題時(shí)要用時(shí)要用非奇異非奇異(qy)陣陣若矩陣若矩陣(j zhn) B 對某個(gè)算子范數(shù)滿足對某個(gè)算子范數(shù)滿足 |B| 1，則必，則必有有定理定理BI 可逆；可逆； |111BBI 證明：證明： 若不然，則若不然，則 有非零解，即存在非零有非零解，即存在非零向量向量 使得使得 0)( xBI0 x00 xxB 1|00 xxB1| B 1()()IIB IB11()()IBB IB11

35、)()( BIBIBI|)(|1|)(|11 BIBBI根據(jù)算子范根據(jù)算子范數(shù)定義數(shù)定義：0| max|xBxBx 0|max1|xBxx111|()|(1 |)11 |IBBIBB第40頁/共119頁第四十一頁，共119頁。A 4321例例 ，X=-3 5T，分別，分別(fnbi)求求A、X的的“1-范數(shù)范數(shù)”和和“無窮大范數(shù)無窮大范數(shù)”613 , 24max1A712 , 34maxA8|5|3|1X5|5|,3max|XMatlab:A=4,-3;2,1X=-3 5norm(A,1), norm(A,inf)norm(X,1), norm(X,inf)第41頁/共119頁第四十二頁，共1

36、19頁。3.4 解線性方程組的迭代法解線性方程組的迭代法 迭代法（迭代法（iterative method iterative method ）迭代法是從初始猜測值開始，通過依次逼近迭代法是從初始猜測值開始，通過依次逼近(bjn)獲得問題解的獲得問題解的方法。方法。(Iterative method: attempts to solve a problem by finding successive approximations to the solution starting from an initial guess；（；（comes from wikipedia） )n應(yīng)用很廣：應(yīng)用很廣

37、：n線性方程組求解、非線性方程求解、非線性方程組求解、特征線性方程組求解、非線性方程求解、非線性方程組求解、特征值求解、最優(yōu)化方法、分形等，以及數(shù)字信號處理中的維納濾值求解、最優(yōu)化方法、分形等，以及數(shù)字信號處理中的維納濾波、卡爾曼濾波等等波、卡爾曼濾波等等(dn dn)都要用到迭代法都要用到迭代法n典型方法：典型方法：n數(shù)值計(jì)算：數(shù)值計(jì)算：Jacobi法、法、Gauss-Seidel法、法、Newton迭代法、最快迭代法、最快下降法（下降法（Steepest Descent）第42頁/共119頁第四十三頁，共119頁。迭代法解一般迭代法解一般(ybn)(非線性非線性)方程方程迭代迭代(di d

38、i)序列的基本公式：序列的基本公式：(1)( )0(),kkxxxa (x)為：任意為：任意n維空間到維空間到n維空間的函數(shù)。維空間的函數(shù)。 當(dāng)當(dāng) (x)為線性函數(shù)時(shí)，上式即為線性方程為線性函數(shù)時(shí)，上式即為線性方程(xin xn fn chn)(組組) 的迭代公式。的迭代公式。如何利用迭代法解方程？如何利用迭代法解方程？迭代法基本原理：迭代法基本原理：如果迭代序列如果迭代序列x（k+1）= (x（k） ) 收斂，收斂，則其極限點(diǎn)則其極限點(diǎn)x*為方程為方程 (x)= x 的解。的解。x*稱為函數(shù)稱為函數(shù) (x)的的不動(dòng)點(diǎn)（不動(dòng)點(diǎn)（fixed point）第43頁/共119頁第四十四頁，共119頁

39、。迭代函數(shù)的構(gòu)造：對于一般迭代函數(shù)的構(gòu)造：對于一般(ybn)(ybn)的非線性方程的非線性方程f(x)=0f(x)=0例例1 1：用迭代法求解：用迭代法求解(qi ji)(qi ji)方程方程 2 x = 1 2 x = 1構(gòu)造迭代構(gòu)造迭代(di di)(di di)函數(shù)：函數(shù)：11 102112(1 1.5 )312xxxxxxxxx (1)( )1(1)( )2(1)( )3(1)( )4( )11( )(1)/3(1)/3( )2(1 1.5 )2(1 1.5)( )(1 10 )/12(1 10)/12kkkkkkkkxxxxxxxxxxxxxxxx ( )0( )f xf xxx(

40、)0( )a f xa f xxx或或即迭代函數(shù)為即迭代函數(shù)為 (x)= f(x)+x 或或 (x)= af(x)+x 迭代函數(shù)迭代函數(shù):第44頁/共119頁第四十五頁，共119頁。迭代函數(shù)迭代函數(shù)(hnsh)的構(gòu)造的構(gòu)造迭代法的步驟迭代法的步驟(bzhu)：1、寫出迭代方程、寫出迭代方程2、迭代、迭代clear allclose allclcformat long% 迭代迭代(di di)法求解法求解2x=1x0 = 0 % 迭代迭代(di di)初值初值N = 30 % 迭代迭代(di di)次數(shù)次數(shù)% 方法方法1：f(x) = 1 - xx1(1) = x0;for iii = 2 :

41、N x1(iii) = 1 - x1(iii - 1);endfigure;plot(x1, o-)title(f(x) = 1 - x)第45頁/共119頁第四十六頁，共119頁。振蕩振蕩(zhndng)序列序列收斂收斂(shulin)序列序列發(fā)散發(fā)散(fsn)序序列列收斂序列收斂序列迭代法的核心問題：迭代法的核心問題：迭代函數(shù)收不收斂迭代函數(shù)收不收斂收斂速度快不快收斂速度快不快第46頁/共119頁第四十七頁，共119頁。 借助于計(jì)算機(jī)，用迭代法對分形借助于計(jì)算機(jī)，用迭代法對分形(fn xn)(fn xn)的研究更的研究更加簡單化加簡單化例例2 2：迭代法用于分形：迭代法用于分形(fn xn

42、)(fractal)(fn xn)(fractal)研究研究 分形分形(fn xn)是一種粗糙的或分裂的幾何形狀，其每一部分都是是一種粗糙的或分裂的幾何形狀，其每一部分都是整體的縮小比例的復(fù)制（自相似性）整體的縮小比例的復(fù)制（自相似性） 分形分形(fn xn)是具有自相似性的幾何形狀。是具有自相似性的幾何形狀。分形（分形（FractalFractal）理論，是現(xiàn)代數(shù)學(xué)的一）理論，是現(xiàn)代數(shù)學(xué)的一個(gè)新分支，但其本質(zhì)卻是一種新的世個(gè)新分支，但其本質(zhì)卻是一種新的世界觀和方法論。界觀和方法論。 A fractal is a rough or fragmented geometric shape that

43、 can be split into parts, each of which is (at least approximately) a reduced-size copy of the whole, a property called self-similarityNOVA紀(jì)錄片：紀(jì)錄片： hunting the hidden dimension “尋找隱藏的維度尋找隱藏的維度” 430， 2630 ，3000 分形應(yīng)用：分形應(yīng)用： 計(jì)算機(jī)虛擬現(xiàn)實(shí)技術(shù)；天線設(shè)計(jì)；醫(yī)學(xué)；計(jì)算機(jī)虛擬現(xiàn)實(shí)技術(shù)；天線設(shè)計(jì)；醫(yī)學(xué)； 第47頁/共119頁第四十八頁，共119頁。分形分形(fn xn) fractal科

44、赫雪花（Koch snowflake）：1、初始(ch sh)為正三角形；2、將每條邊等分三段；3、以中段為底向外做等邊三角形4、移除被三等分的邊的中段。5、如此迭代。第48頁/共119頁第四十九頁，共119頁。曼德勃羅集（Mandelbrot）第49頁/共119頁第五十頁，共119頁。3.4 思路思路(sl)：將線性方程將線性方程 改寫為等價(jià)形式改寫為等價(jià)形式bxA xM xg(1)( ) (k=0,1,2,)kkxM xg(0),nxR從而建立代迭格從而建立代迭格式式)(kx按迭代格式按迭代格式進(jìn)行迭代，得到向量序列進(jìn)行迭代，得到向量序列 。當(dāng)。當(dāng)k充分大時(shí)，以充分大時(shí)，以x(k)作為方程

45、組作為方程組 的近似解，這就是求線性方程的近似解，這就是求線性方程組的迭代法。組的迭代法。M稱為迭代矩陣。稱為迭代矩陣。任取初始向量任取初始向量bxA 優(yōu)點(diǎn)優(yōu)點(diǎn)(yudin)：可人為：可人為控制精度特別適合控制精度特別適合于大型稀疏陣列，于大型稀疏陣列，但存在收斂性問題但存在收斂性問題求解求解bxA 第50頁/共119頁第五十一頁，共119頁。 如何建立迭代格式？如何建立迭代格式？ 收斂速度？收斂速度？ 向量序列的收斂條件？向量序列的收斂條件？ 誤差誤差(wch)估估計(jì)？計(jì)？n研究研究(ynji)內(nèi)內(nèi)容：容：第51頁/共119頁第五十二頁，共119頁。與直接解法與直接解法(ji f)的比較的比

46、較直接直接(zhji)法法: 經(jīng)過有限次運(yùn)算后可求得方程經(jīng)過有限次運(yùn)算后可求得方程組精確解的方法組精確解的方法(不計(jì)舍入誤差不計(jì)舍入誤差!)第52頁/共119頁第五十三頁，共119頁。直接法比較適用于中小型方程組。對高階方程組直接法比較適用于中小型方程組。對高階方程組，既使系數(shù)矩陣是稀疏的，但在運(yùn)算中很難保持，既使系數(shù)矩陣是稀疏的，但在運(yùn)算中很難保持(boch)稀疏性，因而有存儲(chǔ)量大，程序復(fù)雜等不稀疏性，因而有存儲(chǔ)量大，程序復(fù)雜等不足。足。迭代法則能保持矩陣的稀疏性，具有計(jì)算迭代法則能保持矩陣的稀疏性，具有計(jì)算(j sun)簡單，簡單，編制程序容易的優(yōu)點(diǎn)，并在許多情況下收斂較快。故能有編制程序

47、容易的優(yōu)點(diǎn)，并在許多情況下收斂較快。故能有效地解一些高階方程組。效地解一些高階方程組。第53頁/共119頁第五十四頁，共119頁。( )( )( )( )lim-0lim kkknnkkkxRxxxxxxRx設(shè)為為數(shù)則稱斂記為義 中的向量序列，向量，如果 其中向量范，序列收于 ， 定： 收斂收斂(shulin)(shulin)問題問題( )( )( )( )( )( )1( )( )lim-0lim-010-max-0lim0(1,2, , )lim(kkkkkkkkiijjj nkiikkiikxxxxxxinxxxxxxxxiL nxxi 義斂對數(shù)則證由由定定， 收 收于于 ，即即 根根據(jù)

48、據(jù)，必必有有：而而任任意意，有有由由極極限限存存在在準(zhǔn)準(zhǔn)得得 即即 向向量量范范 的的等等價(jià)價(jià) 性性：1,2, , )L n第54頁/共119頁第五十五頁，共119頁。( )( )( )( )( )12(1)2,(,) ,( ,lim(1,)2, ,knknkkkiikkTTnnRxRxxxxxxx xiLxxxn斂當(dāng)僅當(dāng)中中的的向向量量序序列列收收于于中中的的向向量量且且 其其 ： 理理中中 定定 。)()( )( llimi-0mkkkkkkAnAnAAAAAA設(shè)為 階陣為 階陣為陣數(shù)義則稱斂陣記為 方 方序序列列，方方，如如果果 其其中中矩矩范范，序序列列收收于于矩矩， 定定： 第55頁

49、/共119頁第五十六頁，共119頁。( )( )( )()(1,2lim( ,1, ),()2, , )kijijkkjkkijiAakLAanAAaai jL n設(shè)為 階陣則陣斂陣條為證 均 均方方，矩矩序序列列收收于于矩矩的的充充要要件件 定 定理理 ：明明略略。(1)( )( )(1)( ),limlimkkkkkkkxMxgxxxMxAxxMxgbxg產(chǎn)斂點(diǎn)組則 若 若按按生生的的向向量量序序列列收收于于向向量量有有 即即極極程程限限是是方方 的的解解。定理表明：向量序列和矩陣序列的收斂定理表明：向量序列和矩陣序列的收斂(shulin)可以歸結(jié)為對應(yīng)的分量或?qū)?yīng)元素序列的收斂可以歸結(jié)為

50、對應(yīng)的分量或?qū)?yīng)元素序列的收斂(shulin)。第56頁/共119頁第五十七頁，共119頁。11112211211222221112,(1,)02,innnnnnnnnniLLLina x a xa xba x a xa xba x a xa xba寫為陣則數(shù) 系系矩矩若若且且 上上述述可可非非奇奇 改改 異異：第57頁/共119頁第五十八頁，共119頁。112213311221123322n112233 nnnnnnnngxb xb xb xgxb xb xb xxb x b xb x-,(, ,1,2, ),(1,2, ).ijiijiiiiiij i jabbgaaL niL ng其其中

51、中第58頁/共119頁第五十九頁，共119頁。1213111121232122123100 0nnnnnnnnnnbbbbgbbbbgBgbbbbg記 若 若 (0)(1)10(1)(2)(1)( )( ), (0,1,2 ,) kkkxxxBxgxxxkxBxg選將繼續(xù)產(chǎn)個(gè)滿（）（）初初值值向向量量代代入入，代代入入，如如此此，就就生生一一向向量量序序列列足足則方程組可簡記則方程組可簡記(jin j)為為 xBxg此過程給出的迭代法稱為此過程給出的迭代法稱為(chn wi)Jacobi迭代法，又稱迭代法，又稱簡單迭代法簡單迭代法第59頁/共119頁第六十頁，共119頁。12112121221

52、212120110001010 01001nnnnnnnnBbbbbbbbbbbbb 11111121n1121222n221n1n2nn nnII -D Aaaaaaaaaaaaa1 12 111222(,)(, , , )TTDnbnnng ggb aaagbb同樣11g=D I DbB-A即：第60頁/共119頁第六十一頁，共119頁。1* n0 1 2 g knnJacobigxxxBxxBx（）（ ）（ ），斂，則迭迭代代若若收收 *1*1 () IB xgD AxDAxbb即故如果序列收斂故如果序列收斂, , 則收斂到解則收斂到解. B. B稱迭代稱迭代(di (di di)di)

53、矩陣矩陣. .第61頁/共119頁第六十二頁，共119頁。1231231231027210283542xxxJacobixxxxxx 例 例：用用迭迭代代法法求求解解1(01)(0) 10010100101200.10.21010001 1020.100.2100011150.20.201005 (7.2,8.3,8.4)(0,0,0) ,(7.2,8.3 TTBID AgDxBxgb(1)解：x取取代代入入迭迭代代式式，得得(2)(1)(9)(10.9994,11,8.4)(.9994,9.71,10.70,112.9991.(11,12,13) .)5)2TTTTxBxgxx為精精確確解解

54、第62頁/共119頁第六十三頁，共119頁。(0)(0)(0)(0)112(0)(0)(0)11.(),( ,),(,),2.1.3.1,2, ,4.-,55.,1.(-),(1,2, ),3/niiijjiijjijnniiiNxbAabbbn xxxxkiL nx xxkNkk xxna xai 輸維數(shù)對輸則轉(zhuǎn)轉(zhuǎn)敗許數(shù)則輸入入置置 若若出出停停機(jī)機(jī)；否否精精度度 ，。若若置置；否否，出出最最大大容容迭迭失失信信息息代代次次，停停機(jī)機(jī)。( )(1,kkMxx變兩組單評簡單計(jì)陣）不不改改的的稀稀疏疏性性，需需工工作作元元，存存價(jià)價(jià)：公公式式，每每迭迭代代一一次次只只需需算算一一次次矩矩和和向向

55、量量的的乘乘法法，。第63頁/共119頁第六十四頁，共119頁。(1)( )( )( )112213311(1)( )( )( )221123322 kkkknnkkkknnJacobigxb xb xb xgxb xb xb x組為(k+1)(k)(k+1)(k)x= Bx+g (k =0,1,2, )，x= Bx+g (k =0,1,2, )，用用方方程程代代公公式式表表示示迭迭：(1)( )( )( )1122,)11( )(1 kkkknnnknnnknJacobixxgxb xb xbx時(shí)兩計(jì)。過個(gè)因因此此，在在迭迭代代法法的的算算程程中中需需同同保保留留近近似似解解向向，量量和和第

56、64頁/共119頁第六十五頁，共119頁。(1)( )( )( )112213311(1)( )( )223322(1)(1)211(1)112 kkkknnkkknnknkknngxb xb xb xgxb xbbb xxxx(1)(1)2,11 kkn nnnb xbxg 整個(gè)計(jì)算過程只需用一組（整個(gè)計(jì)算過程只需用一組（n個(gè)）單元存放近似解分量。而且一般個(gè)）單元存放近似解分量。而且一般認(rèn)為新近似解要比老近似解更接近真實(shí)解。認(rèn)為新近似解要比老近似解更接近真實(shí)解。 將已計(jì)算出的將已計(jì)算出的x（k+1）分量替換）分量替換Jacobi 迭代公式迭代公式(gngsh)中中x（k）相應(yīng)分量，這種方法稱

57、為相應(yīng)分量，這種方法稱為Gauss-Seidel迭代。迭代。評價(jià)：評價(jià)： 與與Jacobi 相比，相比， Gauss-Seidel迭代法只需一組工作單元存迭代法只需一組工作單元存放放(cnfng)近似解。近似解。若把迭代公式若把迭代公式(gngsh)改寫為：改寫為：第65頁/共119頁第六十六頁，共119頁。用矩陣用矩陣(j zhn)表示表示 :(1)( )-1( - )-1,( - )kkI L xUxgI LI L 項(xiàng)為移移可可得得 存存在在，上上式式(1)( )( )( )112213311(1)( )( )22332(12)211(1(1)112 kkkknnkkkknnnnnkkgx

58、b xb xb xgxb xxbbxxxb(1)(1)2,11 kkn nnnb xbxg1212,000U000000nnbbb21120000000 00nnLbbb(1)(1)( ) kkkxLxUxg(1)1( )1()()kkxILUxILg第66頁/共119頁第六十七頁，共119頁。12131212323132112111111(1)1( 000000000 , () ()nnnnnnnnkkAaaaaaaLaaUaaaaLD LUD UILD DD LDDLxILUx 陣 來記則 如 如果果用用矩矩表表示示，由由)1()ILg(1)1( )1()()kkxDLUxDLb-1(-

59、)-MD LUGauss Seidel陣為陣式式中中矩矩 迭 迭代代法法的的迭迭代代矩矩。第67頁/共119頁第六十八頁，共119頁。Gauss-Seidel迭代法的解迭代法的解123123123(0)1(0)(0)12311(1)(0)21321310272-10283542(0,0,0) ,11 (2)727.2000101011 (2)(7.200083)9.02001010 TxxxGauss Seidelxxxxxxxxxxbxxxbx（ ）（ ）（ ） 例 例：用用迭迭代代法法求求解解解解：仍仍取取代代入入迭迭代代式式，得得(1)(1)123(5)11()7.20009.02004

60、2)11.6440(10.9989,11.9993,12.9996(11,12,13) .)55Txxbxx（繼續(xù)為如如此此下下去去，精精確確解解(9)(10.9994,11.9994,12.9992)TJacobix迭迭代代法法的的解解：第68頁/共119頁第六十九頁，共119頁。比較比較(bjio)：評價(jià)：評價(jià)： 與與Jacobi 相比，相比， Gauss-Seidel迭代法只需一組工作單元迭代法只需一組工作單元(dnyun)存放近似解。存放近似解。 上例計(jì)算結(jié)果顯示，上例計(jì)算結(jié)果顯示， Gauss-Seidel迭代法比迭代法比Jacobi 迭代效迭代效果好。事實(shí)上，果好。事實(shí)上， 對有些