1、中國(guó)礦業(yè)大學(xué)環(huán)境與測(cè)繪學(xué)院6/3/2022測(cè)繪軟件設(shè)計(jì)與實(shí)現(xiàn)內(nèi)容概要內(nèi)容概要數(shù)值分析研究對(duì)象與特點(diǎn)線性方程組解法曲線擬合與函數(shù)逼近一、數(shù)值分析研究對(duì)象與特點(diǎn)1.1 數(shù)值分析的定義及其主要內(nèi)容數(shù)值分析的定義及其主要內(nèi)容數(shù)值分析也稱為計(jì)算方法，是計(jì)算數(shù)學(xué)的一個(gè)主要組成部分計(jì)算數(shù)學(xué)是數(shù)學(xué)科學(xué)的一個(gè)分支，主要研究用計(jì)算機(jī)求解各種數(shù)學(xué)問(wèn)題的數(shù)值計(jì)算方法及其理論與軟件實(shí)現(xiàn)數(shù)值分析的主要內(nèi)容數(shù)值分析的內(nèi)容包括函數(shù)的數(shù)值分析的內(nèi)容包括函數(shù)的數(shù)值逼近數(shù)值逼近、數(shù)值微分與數(shù)值積分?jǐn)?shù)值微分與數(shù)值積分、非線性方程數(shù)值解非線性方程數(shù)值解、數(shù)值線性代數(shù)數(shù)值線性代數(shù)、常微和偏微數(shù)值解法常微和偏微數(shù)值解法等等1.1 數(shù)值分析

2、的定義及其主要內(nèi)容數(shù)值分析的定義及其主要內(nèi)容雖然數(shù)值分析也是以數(shù)學(xué)問(wèn)題為研究對(duì)象，但它不像純數(shù)學(xué)那樣只研究數(shù)學(xué)本身的理論，而是把理論與計(jì)算緊密結(jié)合，著重研究數(shù)學(xué)問(wèn)題的數(shù)值方法及其理論數(shù)值分析不是各種數(shù)值方法的簡(jiǎn)單羅列和堆積，是一門內(nèi)容豐富，研究方法深刻，有自身理論體系的課程數(shù)值分析既有純數(shù)學(xué)高度抽象性與嚴(yán)密科學(xué)性的特點(diǎn)，又有應(yīng)用數(shù)學(xué)的廣泛性與實(shí)際試驗(yàn)的高度技術(shù)性的特點(diǎn)，是一門與計(jì)算機(jī)使用密切結(jié)合的實(shí)用性很強(qiáng)的數(shù)學(xué)課程1.2 數(shù)值分析的特點(diǎn)數(shù)值分析的特點(diǎn)面向計(jì)算機(jī)，能根據(jù)計(jì)算機(jī)特點(diǎn)提供切實(shí)可行的有效算法。有可靠的理論分析，能任意逼近并達(dá)到精度要求，對(duì)近似算法要保證收斂性和數(shù)值穩(wěn)定性，還要對(duì)誤差進(jìn)

3、行分析要有好的計(jì)算復(fù)雜性，時(shí)間復(fù)雜性好是指節(jié)省時(shí)間；空間復(fù)雜性好是指節(jié)省存儲(chǔ)量，這也是建立算法要研究的問(wèn)題，它關(guān)系到算法能否在計(jì)算機(jī)上實(shí)現(xiàn)要有數(shù)值實(shí)驗(yàn)，即任何一個(gè)算法除了從理論上要滿足上述三點(diǎn)外，還要通過(guò)數(shù)值試驗(yàn)證明是行之有效的1.3 數(shù)值計(jì)算的若干原則數(shù)值計(jì)算的若干原則使用數(shù)值穩(wěn)定的算法在運(yùn)算過(guò)程中舍入誤差不增長(zhǎng)的算法稱為數(shù)值穩(wěn)定的算在運(yùn)算過(guò)程中舍入誤差不增長(zhǎng)的算法稱為數(shù)值穩(wěn)定的算法，否則稱為數(shù)值不穩(wěn)定的算法法，否則稱為數(shù)值不穩(wěn)定的算法避免絕對(duì)值很小的數(shù)作為除數(shù)避免兩相近的數(shù)相減通過(guò)改變計(jì)算公式的形式或算法，可以避免或減少有效通過(guò)改變計(jì)算公式的形式或算法，可以避免或減少有效數(shù)字的損失數(shù)字的損

4、失1.3 數(shù)值計(jì)算的若干原則數(shù)值計(jì)算的若干原則防止大數(shù)吃掉小數(shù)編制程序時(shí)，要合理安排計(jì)算順序，防止重要的參數(shù)被編制程序時(shí)，要合理安排計(jì)算順序，防止重要的參數(shù)被“吃掉吃掉”簡(jiǎn)化計(jì)算步驟，減少運(yùn)算次數(shù)提高算法的運(yùn)行效率提高算法的運(yùn)行效率9 . 01 . 05123410001iiiA二、線性方程組解法2.1 引題引題已知線性方程組a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 .an1x1+an2x2+annxn=bn求解x1、x2、xn的值？2.2 線性方程組的解法線性方程組的解法直接法在沒有舍入誤差的情況下，經(jīng)有限四則運(yùn)算求解其準(zhǔn)確在沒有舍入誤差的情況下，經(jīng)

5、有限四則運(yùn)算求解其準(zhǔn)確值的方法值的方法迭代法類似于方程求根的迭代法類似于方程求根的迭代法先給出一個(gè)解的初始近似值，按一定的法則逐步將其精先給出一個(gè)解的初始近似值，按一定的法則逐步將其精化化2.2 線性方程組的解法線性方程組的解法直接法高斯消去法（主元消去法、高斯高斯消去法（主元消去法、高斯-約當(dāng)消去法）約當(dāng)消去法）矩陣分解法矩陣分解法迭代法雅可比迭代法雅可比迭代法高斯高斯-賽德爾迭代法賽德爾迭代法2.3 消去法消去法高斯順序消去法列主元素法高斯約當(dāng)消去法求矩陣的逆2.3.1 高斯順序消去法高斯順序消去法消去法就是按特定的順序進(jìn)行的矩陣初等變換方法，當(dāng)消元按自然順序進(jìn)行時(shí)，稱為高斯順序消去法例：

6、2x1+x2+x3=7 4x1+5x2-x3=11 x1-2x2+x3=02.3.1 高斯順序消去法高斯順序消去法第一步：消元此線性方程組的此線性方程組的增廣矩陣增廣矩陣為為 對(duì)增廣矩陣進(jìn)行初等行變換，使系數(shù)矩陣化為上三角形對(duì)增廣矩陣進(jìn)行初等行變換，使系數(shù)矩陣化為上三角形01171211541125 . 3375 . 05 . 203301120117121154112131221,24rrrr6372003301125 . 3375 . 05 . 203301122335 . 2rr2.3.1 高斯順序消去法高斯順序消去法第二步：得同解方程組2x1+x2+x3=7 3x2-3x3=-3 -2

7、x3=-6第三步：對(duì)上三角形方程組進(jìn)行回代求解x3=(-6)/(-2)=3x2=(-3+3x3)/3=2x3=(7-x2-x3)/2=1高斯順序消去法的計(jì)算機(jī)算法高斯順序消去法的計(jì)算機(jī)算法增廣矩陣經(jīng)k-1步消元后，增廣矩陣化為)0(1,)0(1, 1)0(,)0(1 ,)0(, 1)0(1 , 1nnnnnnnaaaaaa)1(1,)1(1,)1(1, 2)0(1, 1)1(,)1(,)1(,)1(,)1(, 2)1(2, 2)0(, 1)0(2, 1)0(1 , 1knnknknnknnkknknkkkknnaaaaaaaaaaaaa高斯順序消去法的計(jì)算機(jī)算法高斯順序消去法的計(jì)算機(jī)算法第k步

8、消元：設(shè) ，以第k行為基礎(chǔ)，將以后各行中的 化為0，為此先計(jì)算然后以第i行減去第k行乘以li,k，即于是得0)1(,kkka)1(,kkia)1(,)1(,/kkkkkikiaal)1(,)1(,)(,kjkkikjikjialaa) 1, 1(nkj)(1,)(1, 1)1(1,)0(1, 1)(,)(, 1)(, 1)(1, 1)1(,)1(,)0(, 1)0(2, 1)0(1 , 1knnknkknknknnknkknkkkkknkkkknaaaaaaaaaaaaa高斯順序消去法的計(jì)算機(jī)算法高斯順序消去法的計(jì)算機(jī)算法經(jīng)n-1步消元后，增廣矩陣化為自下往上逐步回代即可求得真解)1(1,)1

9、(1,)0(1, 1)1(,)1(,)1(,0, 1)0(1 , 1nnnknknnnnknkkkknaaaaaaaa)1(,)1(1,/nnnnnnnaaxnkjkkkjkjkknkkaxaax1)1(,)1(,)1(1,/) 1 , 2, 1(nnj高斯順序消去法的計(jì)算機(jī)算法高斯順序消去法的計(jì)算機(jī)算法由行列式的初等變換與矩陣初等變換的關(guān)系可知，順序消元法的每一步保持系數(shù)行列式不變，因此，原方程組之系數(shù)行列式的值為 ，可在求解過(guò)程中逐步累乘求得。)1(,)1(2, 2)0(1 , 1nnnaaa高斯順序消去法流程圖高斯順序消去法流程圖2.3.2 列主元素法列主元素法單精度解方程組單精度解方程

10、組 10-9x1+x2=1 x1+x2=2/* 精確解精確解: */.1000.00. 1101191x8個(gè)個(gè).8999.99. 0212xx8個(gè)個(gè)用高斯消去法計(jì)算用高斯消去法計(jì)算：999212210101010.0 . 011la8個(gè)個(gè)92121012lb911212110/aal 9991010011100, 112 xx小主元可能導(dǎo)小主元可能導(dǎo)致計(jì)算失敗。致計(jì)算失敗。8個(gè)個(gè)列主元素法可以有效解決這一問(wèn)題！2.3.2 列主元素法列主元素法高斯順序消去法的弱點(diǎn)當(dāng)主元當(dāng)主元 時(shí)，消元過(guò)程不能繼續(xù)進(jìn)行；時(shí)，消元過(guò)程不能繼續(xù)進(jìn)行；當(dāng)主元當(dāng)主元 時(shí)，消元過(guò)程可以進(jìn)行，但是計(jì)算時(shí)，消元過(guò)程可以進(jìn)行，但

11、是計(jì)算時(shí)，出現(xiàn)時(shí)，出現(xiàn)很小的數(shù)作除數(shù)很小的數(shù)作除數(shù)的現(xiàn)象，使得的現(xiàn)象，使得舍入誤差增大，嚴(yán)重情況下導(dǎo)致解的失真。舍入誤差增大，嚴(yán)重情況下導(dǎo)致解的失真。 列主元素法為了提高算法的數(shù)值穩(wěn)定性，在消去過(guò)程中，為了提高算法的數(shù)值穩(wěn)定性，在消去過(guò)程中，應(yīng)選取絕應(yīng)選取絕對(duì)值盡可能大的元素作為主元對(duì)值盡可能大的元素作為主元，基于此思想實(shí)現(xiàn)的算法，基于此思想實(shí)現(xiàn)的算法成為列主元素法。成為列主元素法。0)1(,kkka0)1(,kkka)1(,)1(,/kkkkkikiaal2.3.2 列主元素法列主元素法在消元的第k步，首先在第k列下放所有元素 ， ， 中取絕對(duì)值最大者為主元，設(shè)則選 為主元，若 ，則交換第r

12、行與第k行，而后再進(jìn)行消元。實(shí)際計(jì)算中，當(dāng) 很小時(shí)，求解結(jié)果將嚴(yán)重失真，繼續(xù)計(jì)算已無(wú)意義，因此可設(shè)一閾值，當(dāng) 時(shí)則停止計(jì)算。)1(,kkka)1(, 1kkka)1(,kkna)1(,)1(,maxkkinikkkraa)1(,kkrakr )1(,kkra )1(,kkra2.3.2.1 列主元素法的基本步驟列主元素法的基本步驟第一步：選主元：在選主元：在ai1（i=1, , n)中選取絕對(duì)值最大的元素作為主元素，中選取絕對(duì)值最大的元素作為主元素，即確定即確定 i，使，使 交換行：即當(dāng)交換行：即當(dāng)i1時(shí)，交換第時(shí)，交換第i行與第行與第1行元素；行元素；消元計(jì)算：消元計(jì)算：li1=ai1/a1

13、1（i=2, 3, ，n） aijaij-lija11 (i=2, 3, , n; j=i, i+1, , n）第k步：選主元：在選主元：在aik（i=k,n)中選取絕對(duì)值最大的元素作為主元素，即中選取絕對(duì)值最大的元素作為主元素，即確定確定 i，使，使 交換行：即當(dāng)交換行：即當(dāng)ik時(shí)，交換第時(shí)，交換第i行與第行與第k行元素；行元素；消元計(jì)算：消元計(jì)算：lkk = aik / akk（i=k, k+1, ，n） aij aij - lija11 （i=k, k+1, , n; j=k, k+1, , n）。，0|max|1 ,11iniiaa。0|max|iknikikaa2.3.2.2 列主元

14、素法消去過(guò)程列主元素法消去過(guò)程2.3.2.3 嚴(yán)格對(duì)角占優(yōu)矩陣嚴(yán)格對(duì)角占優(yōu)矩陣嚴(yán)格對(duì)角占優(yōu)矩陣滿足如下條件：對(duì)角線上每一元素的絕對(duì)值均大于同行其他元素絕對(duì)值對(duì)角線上每一元素的絕對(duì)值均大于同行其他元素絕對(duì)值之和之和對(duì)角線上每一元素的絕對(duì)值均大于同列其他元素絕對(duì)值對(duì)角線上每一元素的絕對(duì)值均大于同列其他元素絕對(duì)值之和之和若矩陣A對(duì)稱且嚴(yán)格對(duì)角占優(yōu)，則消元過(guò)程中第k步主元必為 ，因此不必選主元，用順序消去法即可), 2 , 1(1niaanijjijii), 2 , 1(1niaanjiiijii)1( kkka2.3.3 高斯高斯約當(dāng)消去法約當(dāng)消去法在消元過(guò)程中選取主元后，先將主元化為1，而后將主元

15、所在列上、下方各元素均化為0，這樣消元的結(jié)果使系數(shù)矩陣化成了單位陣，無(wú)需回代就得到了原方程組的解，這種方法稱之為高斯約當(dāng)消去法。A | I I | B高斯約當(dāng)消去法（矩陣的初等行變換）2.4 矩陣分解法矩陣分解法LU分解法分解法高斯消元法的矩陣形式bAbbbaaaaaaaaa|321333231232221131211)1()1()1(3)1(21)1(33)1(32)1(23)1(22131211|bAbbbaaaaaaayUbbbaaaaaa)2(3)1(21)2(33)1(23)1(22131211|1011)1()1()1(3121)1(bAbAMllM記|111)1()1()2(32

16、)2(yUbAMlM記3 , 201111111irlriaalaikiii行消元第令設(shè)2323)1(22)1(3232)1(2230rlraala行消元第令設(shè)2.4 矩陣分解法矩陣分解法LU分解法分解法對(duì)比以上可見，消元過(guò)程相當(dāng)于下述矩陣乘法運(yùn)算M(2)M(1)A|b=U|y由分塊矩陣乘法可得 M(2)M(1)A=U M(2)M(1)b=y 令 L=(M(2)M(1)-1=(M(1)-1(M(2)-1由直接計(jì)算可知于是A=LU， Ly=b111323121lllL2.4 矩陣分解法矩陣分解法LU分解法分解法可見只要消元過(guò)程能進(jìn)行到底，就有以下等價(jià)關(guān)系只要消元過(guò)程能進(jìn)行到底，就有以下等價(jià)關(guān)系據(jù)

17、此，可以得到LU分解之后矩陣L和U的基本表達(dá)式y(tǒng)UxbLybLUxbAxUxyLUA令111323121lllL )1()1 (2)1 (2211211nnnnnaaaaaaU2.4 矩陣分解法矩陣分解法LU分解法分解法例：求下述矩陣的LU分解所以1256144412A2.4 矩陣分解法矩陣分解法LU分解法分解法有了矩陣A的LU分解計(jì)算公式，解線性方程組Ax=b就轉(zhuǎn)化為依次解下三角方程組Ly=b與上三角方程組Ux=y，其計(jì)算公式如下：nkskkskskkksskskknnkuxuyxnkylby111) 1 , 1,(/ )(), 2 , 1(2.4 矩陣分解法矩陣分解法LU分解法分解法定理一

18、若矩陣A非奇異，則A能分解為L(zhǎng)U的充分必要條件是A的順序主子行列式不為0，即定理二若非奇異矩陣A有LU分解，則此分解是唯一的。0111a0222112112aaaa011112nnnnaaaa2.4.1 LU分解實(shí)例分解實(shí)例已知 ，用LU分解法分別求解下列線性方程組（1）Ax=b；（2）A2z=b30561421932311642538A4321b2.4.1 LU分解實(shí)例分解實(shí)例解：對(duì)方程組A2z=b，若先計(jì)算A2再求解，則計(jì)算量較大，在一般情況下， A2還會(huì)產(chǎn)生新的誤差；若令x=Az，則問(wèn)題轉(zhuǎn)化為依次解Ax=b，Az=x兩個(gè)線性方程組；因此，利用LU分解法，等價(jià)于求解四個(gè)方程組Ly=b，Ux

19、=y，Lw=x，Uz=w，即在求出第（1）題之解x的基礎(chǔ)上很快求出第（2）題之解z。2.4.1 LU分解實(shí)例分解實(shí)例A的LU分解式解Ly=b，得解Ux=y，得第（1）題之解解Lw=x，得解Uz=w，得第（2）題之解16414018. 010172414. 575. 1012586207. 025. 00015 . 000012L10269.25000017242. 215517.210025 . 35 .1402538UTy159739. 0137931. 35 . 11Tx310363442. 61477225. 006691342. 01906432. 0Tw3852601. 010271

20、474. 910840816. 21906432. 022Tz233210534736. 110846045. 51025342. 110179105. 3作業(yè)作業(yè)&數(shù)值實(shí)驗(yàn)一數(shù)值實(shí)驗(yàn)一1、試編程求解如下方程組（列主元素法） （1） （2） （3）對(duì)（1）（2）兩題觀察每步消元結(jié)果的系數(shù)矩陣有何特點(diǎn)，右下方矩陣是否對(duì)稱，列主元在何處等2、對(duì)第1題中的系數(shù)矩陣A進(jìn)行LU分解，并用此分解法解對(duì)應(yīng)的線性方程組9621252724321321321xxxxxxxxx34212565321321321xxxxxxxxx1242222321321321xxxxxxxxx2.5 迭代法迭代法迭代法求

21、解方程的根迭代法求方程組的解2.5.1 迭代法求解方程的根迭代法求解方程的根迭代法的基本思想迭代法是一種重要的迭代法是一種重要的逐次逼近法逐次逼近法將方程將方程f(x)=0化為化為等價(jià)方程等價(jià)方程x=(x)，然后在隔根區(qū)間內(nèi)取一，然后在隔根區(qū)間內(nèi)取一點(diǎn)點(diǎn)x0，按下式計(jì)算，按下式計(jì)算xk+1=(xk) (k = 0, 1, 2 )（1）計(jì)算結(jié)果生成序列計(jì)算結(jié)果生成序列x0, x1, , xk, （2）如果這個(gè)數(shù)列有極限如果這個(gè)數(shù)列有極限 ，顯然，顯然x*就是方程就是方程x=(x)之根。之根。于是，可以從此數(shù)列中求得滿足精度要求的近似根，這種求于是，可以從此數(shù)列中求得滿足精度要求的近似根，這種求根

22、方法稱為根方法稱為迭代法迭代法，式（，式（1）稱為）稱為迭代格式迭代格式，(x)稱為稱為迭代迭代函數(shù)函數(shù)，x0稱為稱為迭代初值迭代初值，數(shù)列（，數(shù)列（2）稱為）稱為迭代序列迭代序列如果迭代序列收斂，則稱迭代格式（如果迭代序列收斂，則稱迭代格式（1）收斂，否則稱迭代）收斂，否則稱迭代格式發(fā)散格式發(fā)散 xxkklim（1） 實(shí)例：迭代法求解方程的根實(shí)例：迭代法求解方程的根例：用迭代法求方程x4+2x2-x-3=0在區(qū)間1, 1.2內(nèi)的實(shí)根解：對(duì)方程進(jìn)行如下三種變形x = 1(x)=(3+x-2x2)1/4x = 2(x)=(x+4)1/2-1) 1/2x = 3(x)=x4+2x2-3分別按以上三

23、種形式建立迭代格式，并取分別按以上三種形式建立迭代格式，并取x0=1進(jìn)行迭代計(jì)算，進(jìn)行迭代計(jì)算，結(jié)果如下結(jié)果如下xk+1 = 1(xk)， x26=x27=1.124123xk+1 = 2(xk)， x6=x7=1.124123xk+1 = 3(xk)， x3=96, x4=8.495307107準(zhǔn)確根：準(zhǔn)確根：x*=1.124123029，可見，可見迭代格式不同，收斂情況也迭代格式不同，收斂情況也不同不同，第二種格式比第一種格式收斂快得多第二種格式比第一種格式收斂快得多，第三種格式不第三種格式不收斂收斂（2）收斂條件與誤差估計(jì)）收斂條件與誤差估計(jì)定理一（收斂條件） 設(shè)(x)(在a, b上存在

24、，且滿足條件：（1）當(dāng)xa, b時(shí)，(x)a, b（2）存在正數(shù)L1，使對(duì)任意的xa, b，|(x)| L 1 則（1）方程x=(x)在a,b上有唯一根x*;（2）對(duì)任意的迭代初值x0a, b，迭代序列xk+1=(xk) (k=0, 1, 2, )收斂于x*。（2）收斂條件與誤差估計(jì)）收斂條件與誤差估計(jì)定理一（收斂條件） 設(shè)(x)(在a, b上存在，且滿足條件：（1）當(dāng)xa, b時(shí)，(x)a, b（2）存在正數(shù)L1，使對(duì)任意的xa, b，|(x)| L 1 則（1）方程x=(x)在a,b上有唯一根x*;（2）對(duì)任意的迭代初值x0a, b，迭代序列xk+1=(xk) (k=0, 1, 2, )收

25、斂于x*。（2）收斂條件與誤差估計(jì)）收斂條件與誤差估計(jì)定理一（收斂條件） 設(shè)(x)(在a, b上存在，且滿足條件：（1）當(dāng)xa, b時(shí)，(x)a, b（2）存在正數(shù)L1，使對(duì)任意的xa, b，|(x)| L 1 則（1）方程x=(x)在a,b上有唯一根x*;（2）對(duì)任意的迭代初值x0a, b，迭代序列xk+1=(xk) (k=0, 1, 2, )收斂于x*。（2）收斂條件與誤差估計(jì)）收斂條件與誤差估計(jì)定理二（誤差預(yù)計(jì)） 若在方程x=(x)之根x*的某鄰域R=x| |x-x*|內(nèi)(x)存在，且存在正常數(shù)L1，使|(x)| L 1，則任取x0R，迭代格式xk+1=(xk)均收斂于x*，且有下列誤差

26、估計(jì)式反之，若在根x*的鄰域R內(nèi)|(x)| 1則迭代必發(fā)散Rx1*1kkkxxLLxx01*1xxLLxxkk（2）收斂條件與誤差估計(jì)）收斂條件與誤差估計(jì)定理二給出了迭代格式在根x*鄰近是否收斂的判定條件定理二強(qiáng)調(diào)，當(dāng)條件|(x)|L1成立時(shí)，迭代初值x0應(yīng)取在根x*的鄰域R中如果對(duì)于任意給定的如果對(duì)于任意給定的x0，迭代格式均收斂，則稱此格式具有全局，迭代格式均收斂，則稱此格式具有全局收斂性收斂性對(duì)根對(duì)根x*的某鄰域的某鄰域 內(nèi)的一點(diǎn)內(nèi)的一點(diǎn)x0，迭代格式收斂，則稱此格式具有局，迭代格式收斂，則稱此格式具有局部收斂性部收斂性在具體解題時(shí)，雖然無(wú)法判在具體解題時(shí)，雖然無(wú)法判別隔根區(qū)間是否是以別

27、隔根區(qū)間是否是以x*為中為中心的鄰域，但只要他足夠小，心的鄰域，但只要他足夠小，在其中在其中|(x)|L1成立，則對(duì)成立，則對(duì)其中任取一點(diǎn)其中任取一點(diǎn)x0必能保證收斂必能保證收斂（2）收斂條件與誤差估計(jì)）收斂條件與誤差估計(jì)另外，定理2中給出的兩個(gè)誤差預(yù)計(jì)式也很有意義，由誤差預(yù)計(jì)式可知，條件式中|(x)|L1，L越小，迭代過(guò)程收斂越快；若L1，但L1，則收斂很慢，此種格式不宜采用如：如：例例3中采用的三種迭代格式，在隔根區(qū)間中采用的三種迭代格式，在隔根區(qū)間(1, 1.2)內(nèi)，有內(nèi)，有根據(jù)定理根據(jù)定理2可知，可知，第三種格式發(fā)散第三種格式發(fā)散，第第1、2種迭代格式收斂種迭代格式收斂，而而第二種迭代

28、格式比第一種迭代格式收斂要快很多第二種迭代格式比第一種迭代格式收斂要快很多，這與實(shí)，這與實(shí)際迭代結(jié)果完全吻合際迭代結(jié)果完全吻合844)( 11. 051544144)( 187. 0)2 . 1213(25. 02 . 1)23(25. 0)( 331124/324/321xxxxxxxxxx（2）收斂條件與誤差估計(jì)）收斂條件與誤差估計(jì)根據(jù)誤差預(yù)計(jì)式 可知，若|xk-xk-1|，則近似解xk有如下的誤差預(yù)計(jì)因此，在正常收斂情況下，即L不十分接近于1時(shí)，可用|xk-xk-1|控制迭代結(jié)束，這種用前后兩次迭代結(jié)果估計(jì)誤差的辦法稱為事后誤差估計(jì)，實(shí)際應(yīng)用中，控制迭代結(jié)束的條件也常取為E 0, f(-

29、2) 0，所以，所以，f()=0在在(-2, -1)之間有一之間有一根，因此，根，因此， ，所以，所以，Jacobi迭代不收斂！迭代不收斂！04/34/34/304/34/34/30)(1ULDMJ1max)(1iniJM（3-1）迭代法的收斂條件實(shí)例）迭代法的收斂條件實(shí)例Gauss-Seidel迭代矩陣為迭代矩陣為令令f() = det(I-MG) = 0 f() = (2-(81/64)+(27/64) = 0得得1=0，2,3=0.6330.146i，進(jìn)而，進(jìn)而，因此，因此，Gauss-Seidel迭代法收斂！迭代法收斂！64/4564/9016/316/904/34/300004/30

30、04/34/3014/34/3014/3001)(11ULDMG1650. 0max)(1iniJM數(shù)值實(shí)驗(yàn)二數(shù)值實(shí)驗(yàn)二Jacobi迭代法與Gauss-Seidel迭代法的收斂性與收斂速度研究用研究用Jacobi迭代法與迭代法與Gauss-Seidel迭代法解下列迭代法解下列Ax=b方程組的收方程組的收斂性，通過(guò)上機(jī)計(jì)算，驗(yàn)證分析是否正確，并觀察右端對(duì)迭代收斂性，通過(guò)上機(jī)計(jì)算，驗(yàn)證分析是否正確，并觀察右端對(duì)迭代收斂是否有影響，比較兩法的收斂速度斂是否有影響，比較兩法的收斂速度（1）（2）（3）34520010042341324112621bbA100512318 . 08 . 08 . 018

31、 . 08 . 08 . 0121bbA6417311bA三、最小二乘曲線、曲面擬合3.1 引題引題在科學(xué)實(shí)驗(yàn)和統(tǒng)計(jì)研究中，往往要從大量的實(shí)驗(yàn)數(shù)據(jù)(xi, yi) (i=0, 1, , m)中尋找其函數(shù)關(guān)系y=f(x)的近似表達(dá)式y(tǒng)=P(x)由于實(shí)驗(yàn)觀測(cè)數(shù)據(jù)不可避免地帶有誤差，甚至是較大的誤差，因此，在尋找y=P(x)的過(guò)程之中，要求其偏差ri=P(xi)-yi (i=0, 1, , m)按照某種標(biāo)準(zhǔn)最小，以反映所給數(shù)據(jù)的總體趨勢(shì)，消除局部波動(dòng)的影響，這就是曲線擬合問(wèn)題，這樣的函數(shù)P(x)稱為擬合函數(shù)。3.2 最小二乘法基本原理最小二乘法基本原理基于最小二乘法的曲線擬合問(wèn)題的具體提法對(duì)給定的數(shù)

32、據(jù)對(duì)給定的數(shù)據(jù)(xi, yi) (i=0, 1, , m)，在取定的函數(shù)類，在取定的函數(shù)類中，求中，求P(xi)，使偏差，使偏差ri=P(xi)-yi (i=0, 1, , m)的平方的平方和為最小，即和為最小，即滿足上式的函數(shù)滿足上式的函數(shù)P(x)叫最小二乘擬合函數(shù)或最小二乘解叫最小二乘擬合函數(shù)或最小二乘解min)(0202miiimiiyxPr3.2.1 多項(xiàng)式擬合多項(xiàng)式擬合對(duì)于給定的一組數(shù)據(jù)(xi, yi) (i=0, 1, , m)，求作n次多項(xiàng)式(n m)使其滿足即將擬合函數(shù)取為多項(xiàng)式，這樣的曲線擬合問(wèn)題叫多項(xiàng)式擬合問(wèn)題，Pn(x)稱為最小二乘擬合多項(xiàng)式。nkkknnnxaxaxaa

33、xP010)( miminkikikiinyxayxPQ02002min)(3.2.1 多項(xiàng)式擬合多項(xiàng)式擬合Q可以看作是a0, a1, , an的多元函數(shù)，因此，上述擬合多項(xiàng)式的構(gòu)造問(wèn)題可以歸結(jié)為多元函數(shù)的極值問(wèn)題由多元函數(shù)極值的必要條件知，aj ( j=0, 1, ,n)滿足即這是關(guān)于系數(shù)a0, a1, , an的線性方程組), 1 , 0(0200njxyxaaQmijiinkkikj ), 1 , 0(000njyxaxnkmiijikmikji3.2.1 多項(xiàng)式擬合多項(xiàng)式擬合將上述關(guān)于系數(shù)的a0, a1, , an線性方程組寫成矩陣形式為稱之為法方程組或正則方程組法方程組的一個(gè)明顯特點(diǎn)

34、是其系數(shù)矩陣為對(duì)稱的，如果它非奇異，那么，法方程組必存在唯一的一組解。從中求出ak(k=0, 1, , n)，即可求得多項(xiàng)式擬合結(jié)果000012100001200001mmmniiiiiimmmmniiiiiiiiimmmmnnnnniiiiiiiiimxxyaaxxxx yaxxxx y 3.2.2 一般最小二乘擬合一般最小二乘擬合實(shí)際應(yīng)用中，針對(duì)所討論問(wèn)題的特點(diǎn)，擬合函數(shù)可能為其他類型如指數(shù)函數(shù)、三角函數(shù)、有理函數(shù)等，待定參數(shù)還可能出現(xiàn)在指數(shù)上、分母中等，這就屬于一般最小二乘擬合問(wèn)題（1） 線性最小二乘擬合線性最小二乘擬合設(shè)0(x), 1(x), , n(x)為n+1個(gè)線性無(wú)關(guān)的函數(shù)，為其

35、所有線性組合生成的函數(shù)集合，記作 = Span0(x), 1(x), , n(x)，任取P(x) ，則有P(x)關(guān)于參數(shù)a0, a1, ,an是線性的對(duì)給定的一組數(shù)據(jù)(xi, yi)(i = 0, 1, 2,m)，在中求P(x)，使其滿足這就是一般的線性最小二乘擬合問(wèn)題nkkkxaxP0)()( miminkikkiiyxayxPQ02002min)()(（1） 線性最小二乘擬合線性最小二乘擬合同多項(xiàng)式擬合類似，上述問(wèn)題歸為多元函數(shù)極值問(wèn)題，由多元函數(shù)極值的必要條件即它是關(guān)于參數(shù)a0, a1, ,an的線性方程組，寫成矩陣形式：), 1 , 0(0)()(200njxyxaaQmiijinki

36、kkj ), 1 , 0()()()(000njyxaxxnkmiiijkmiijikmiiinmiiimiiinmiinmiinimiinimiiinmiimiiimiiinmiiimiiyxyxyxaaaxxxxxxxxxxxxxxx00100100201000102101000001020)()()()()()()()()()()()()()()()()()(法方法方程組程組（1） 線性最小二乘擬合線性最小二乘擬合若記a=(a0, a1, ,an)T y=(y0, y1, ,yn)T則法方程可以表現(xiàn)為 GTGa=GTy如果G的列向量線性無(wú)關(guān)，則法方程組存在唯一解a=(a0, a1, ,an)T ，從而得P(x)即為所求的最小二乘擬合函數(shù)特別地，當(dāng)取k(x)=xk(k=0, 1, n)時(shí)，即為多項(xiàng)式擬合)()()()()()()()()(101111000100mnmmnnxxxxxxxxxGnkkknxaxP0)()(（1） 線性最小二乘擬合實(shí)例一線性最小二乘擬合實(shí)例一已知如下一組數(shù)據(jù)，用最小二乘法求其擬合函數(shù)