數(shù)值計算方法總復(fù)習(xí)

1、第二章第二章 非線性方程的數(shù)值解法非線性方程的數(shù)值解法常用方法常用方法 1 二分法二分法 2 一般迭代法一般迭代法3 牛頓迭代法牛頓迭代法4 弦截法弦截法 根的隔離；誤差估計；迭代收斂階根的隔離；誤差估計；迭代收斂階2 一般迭代法一般迭代法) 1(0)( xf對對(1)迭代法迭代法 (1) 把（把（1）等價變換為如下形式）等價變換為如下形式 )2()(xgx (2) 建立迭代格式建立迭代格式 )3()(1kkxgx (3) 適當(dāng)選取初始值適當(dāng)選取初始值x 0 ，遞推計算出所需的解。，遞推計算出所需的解。 定理定理2.2 （非局部收斂定理）（非局部收斂定理）如果如果 在在 上上連續(xù)可微且以下條件

2、滿足連續(xù)可微且以下條件滿足： )(xg,ba,)(, ,)1(baxgbax 則則若若1)(, ,)2( Lxgbax對對.)(, ,*1xxxgxbaxkkk收斂于收斂于的解序列的解序列對對那么那么 命題命題2.2 若在區(qū)間若在區(qū)間 內(nèi)內(nèi) ，則對任，則對任何何 ，迭代格式，迭代格式 不收斂。不收斂。 ,ba1 xg)(1kkxgx,0bax 推論推論 設(shè)設(shè) x*= g(x*) ， 若若 g(x) 在在 x* 附近附近連續(xù)可微且連續(xù)可微且 ，則迭代格式，則迭代格式 xk+1= g(xk) 在在 x* 附近局部收斂。附近局部收斂。 1| )(|* xg(2)迭代法的收斂性迭代法的收斂性簡單地代之

3、以簡單地代之以 |1kkxx (3) 迭代法的誤差估計迭代法的誤差估計 3 牛頓迭代法牛頓迭代法 )122()()(1 kkkkxfxfxx其迭代函數(shù)為其迭代函數(shù)為 )132()()()(xfxfxxg牛頓迭代法牛頓迭代法 4 4 弦截法弦截法 , 1 , 0,)()()()(10111 kxxxxxfxfxfxxkkkkkkk弦截法弦截法第三章第三章 線性代數(shù)方程組的數(shù)值解法線性代數(shù)方程組的數(shù)值解法 1 解線性方程組的消去法解線性方程組的消去法2 解線性方程組的矩陣分解法解線性方程組的矩陣分解法3 解線性方程組的迭代法解線性方程組的迭代法給定一個線性方程組給定一個線性方程組)13( bAx

4、nnnnnnnnnnijbbbbxxxxaaaaaaaaaaA2121212222111211,)(這里這里求解向量求解向量 x。 )13( bAx )0(24)0(4)0(42)0(41)0(13)0(3)0(32)0(31)0(12)0(2)0(22)0(21)0(11)0(1)0(12)0(110)0()0(1,)0()0(,nnnnnnnnniiiijijaaaaaaaaaaaaaaaabAabbaa）（則則增增廣廣矩矩陣陣為為：記記）（(1)高斯消去法高斯消去法1.解線性方程組的消去法解線性方程組的消去法 1）消元過程）消元過程： 對對k=1,2, , n 依次計算依次計算) 43

5、() 1, 1;, 2, 1() 1;, 2, 1(/)() 1() 1()() 1() 1()( nkjnkkiaaaankkjaaakjkkkikj ikj ikkkkjkkjk 2) 回代過程回代過程： ) 53() 1 , 1,(1)()(1)(1 nnkxaaxaxnkjjkjkknkknnnn xIbA行初等變換行初等變換這一無回代的消去法稱為這一無回代的消去法稱為高斯高斯- -若當(dāng)若當(dāng)（Jordan）消去法消去法 (2)(2)高斯高斯- -若當(dāng)若當(dāng)（Jordan）消去法消去法 高斯高斯- -若當(dāng)若當(dāng)（Jordan）消去法消去法 一般公式：一般公式： ) 1, 1;, 1, 1,

6、1() 1;, 2, 1(/)() 1() 1()() 1() 1()(nkjnkkiaaaankkjaaakjkkkikj ikj ikkkkjkkjk定理定理 3.1 如果的各階順序主子式均不為零，即有如果的各階順序主子式均不為零，即有), 3 , 2(0, 01111111nkaaaaDaDkkkkk 即消去法可行。即消去法可行。推論推論 若系數(shù)矩陣若系數(shù)矩陣嚴(yán)格對角占優(yōu)嚴(yán)格對角占優(yōu)，即有，即有 ),2, 1(1niaanjijijii ), 3 , 2(/,1)1(1)0(11nkDDaDakkkkk 則消去法可行，且則消去法可行，且 (3) 選主元素的消去法選主元素的消去法 主元素的

7、選取通常采用兩種方法：主元素的選取通常采用兩種方法： 一種是一種是全主元消去法全主元消去法；另一種是；另一種是列主元消去法列主元消去法。 2 解線性方程組的矩陣分解法解線性方程組的矩陣分解法 一、一、 非對稱矩陣的三角分解法非對稱矩陣的三角分解法 矩陣分解法的基本思想是：矩陣分解法的基本思想是： nnnnllllllL21222111 nnnnuuuuuuU22211211可逆下三角矩陣可逆下三角矩陣可逆上三角矩陣可逆上三角矩陣)0( AbAx對于給定的線性方程組對于給定的線性方程組 LUA （1） 分解分解 bLyyUxbLUxbAx)2(解兩個三角形方程組。解兩個三角形方程組。分分解解。為

8、為單單位位上上三三角角為為下下三三角角，分分解解。為為上上三三角角為為單單位位下下三三角角，CroutULDoolittleUL. 2. 1矩陣的矩陣的Crout分解的計算公式分解的計算公式 010k規(guī)規(guī)定定 ), 1; 1, 2 , 1(/ )(), 2 , 1;, 2 , 1(1111nijnilulauijniulalikiikjikijijjkkjikijij(3-12) nnnnnnaaaaaaaaa212222111211 nnnnllllll21222111 1112112nnuuu 444443434242414134343333323231312424232322222121

9、1414131312121111)()()()()()()()()()()()()()()()(lalalalaualalalauaualalauauaualajilaujialiiijijijij /)()(. 2一一個個內(nèi)內(nèi)積積一一個個內(nèi)內(nèi)積積行行第第列列第第行行第第列列第第行行第第列列第第332211. 1注：注： 3.3.3 對稱正定矩陣的三角分解對稱正定矩陣的三角分解 定義定義 3.1 若若n 階方矩陣階方矩陣 A 具有性質(zhì)具有性質(zhì) 且對任何且對任何n 維維向量向量 成立成立 ，則稱，則稱 A 為對稱正定矩陣。為對稱正定矩陣。 TAA 0 x0 AxxT定理定理3.4 若若A 為對稱

10、正定矩陣，則為對稱正定矩陣，則 (1) A的的k階順序主子式階順序主子式 (2)有且僅有一個單位下三角矩陣有且僅有一個單位下三角矩陣L和對角矩陣和對角矩陣D 使得使得 （3-16）這稱為矩陣的這稱為矩陣的喬里斯基喬里斯基（Cholesky）分解分解。 (3)有且僅有一個下三角矩陣有且僅有一個下三角矩陣 ，使，使 （3-17）這稱為分解矩陣的這稱為分解矩陣的平方根法平方根法。), 2 , 1(0nkDk TLDLA LTLLA 3 解線性方程組的迭代法解線性方程組的迭代法 nnnnnnnnnijffffmmmmmmmmmmM21212222111211)(，其其中中迭代法迭代法思想思想:(1)A

11、x=b ( 3-1)23( fxMx格格式式遞遞推推求求解解。，用用迭迭代代選選取取初初始始向向量量Tnxxxx,)3()0()0(1)0(0)0( (2)建立迭代格式建立迭代格式)263()()1( fxMxkk這稱為這稱為一階定常迭代格式一階定常迭代格式，M 稱為稱為迭代矩陣迭代矩陣。 bAx 約化便得約化便得 ), 2 , 1()(11nixabaxnjijjijiiii 從而可建立迭代格式從而可建立迭代格式對對 （3-23）以分量表示即以分量表示即 )233(), 2 , 1(1 njijijnibxa(1)、Jacob迭代法迭代法雅可比雅可比（Jacobi）迭代迭代 )243()2

12、, 1 , 0;, 2 , 1()(11)() 1( knixabaxnjijkjijiiiki 0000,000121121121nnnnnnnaaaaUaaaL可逆可逆這里這里記記 nnaaaDULDA2211,則雅可比迭代格式（則雅可比迭代格式（3-24）可用矩陣表示為）可用矩陣表示為 MJf JbDxULDxkk1)(1)1()( )253()2 , 1 , 0;, 2 , 1()(1111)() 1() 1( knixaxabaxijnijkjijkjijiiiki用矩陣表示為用矩陣表示為 bLDxULDxkk1)(1)1()()( 對雅可比迭代格式修改得對雅可比迭代格式修改得高斯高

13、斯- -塞德爾塞德爾（Gauss-Seidel）迭代迭代 f G-SMG-S(2) Gauss-Seidel迭代法迭代法例例3.10 分別用雅可比迭代法和高斯分別用雅可比迭代法和高斯-塞德爾迭代法求解塞德爾迭代法求解 線性方程組線性方程組 1015352111021210321xxx解解 相應(yīng)的迭代公式為相應(yīng)的迭代公式為 )(2)(1)1(3)(3)(1)1(2)(3)(2)1(14 . 02 . 021 . 02 . 05 . 11 . 02 . 03 . 0kkkkkkkkkxxxxxxxxx雅可比迭代雅可比迭代高斯高斯-塞德爾迭代塞德爾迭代 ) 1(2) 1(1) 1(3)(3) 1(1

14、) 1(2)(3)(2) 1(14 . 02 . 021 . 02 . 05 . 11 . 02 . 03 . 0kkkkkkkkkxxxxxxxxx令令 取四位小數(shù)迭代計算取四位小數(shù)迭代計算 , 0)0(3)0(2)0(1 xxx由雅可比迭代得由雅可比迭代得 000. 3,000. 2,000. 1)11(3)11(2)11(1 xxx由高斯由高斯-塞德爾迭代得塞德爾迭代得 000. 3,000. 2,000. 1)6(3)6(2)6(1 xxx定理定理 3.5 若一階定常迭代格式（若一階定常迭代格式（3-26）的迭代矩陣）的迭代矩陣 滿足條件滿足條件 nnijmM)()283(1max11

15、 njijnim則該迭代格式對任何初始向量則該迭代格式對任何初始向量 均收斂。均收斂。 )0(x則該迭代格式對任何初始向量則該迭代格式對任何初始向量 均收斂。均收斂。 )0(x)293(1max11 niijnjm 定理定理 3.6 若一階定常迭代格式（若一階定常迭代格式（3-26）的迭代矩陣）的迭代矩陣 滿足條件滿足條件 nnijmM )( 迭代法的收斂性迭代法的收斂性 推論推論 如果線性代數(shù)方程組如果線性代數(shù)方程組 A x = b的系數(shù)矩陣的系數(shù)矩陣 A 為嚴(yán)格對角為嚴(yán)格對角占優(yōu)矩陣，即占優(yōu)矩陣，即)303(), 2 , 1(1njijijiiniaa則相應(yīng)的雅可比迭代法與高斯則相應(yīng)的雅可

16、比迭代法與高斯-塞德爾迭代法對任何初始向塞德爾迭代法對任何初始向量量 均收斂。均收斂。 ) 0 (x 定理定理 3.8 一階定常迭代格式一階定常迭代格式 對任何初對任何初始向量均收斂的始向量均收斂的充分必要條件充分必要條件為其迭代矩陣的譜半徑小于為其迭代矩陣的譜半徑小于1，即，即 fMxxkk )()1(這里這里 為為 M 的特征值的特征值 n,1)313(1max)(1 iniM 第四章第四章 函數(shù)的插值與擬合法函數(shù)的插值與擬合法1 插值多項式的構(gòu)造插值多項式的構(gòu)造2 最小二乘法最小二乘法定義定義 4.1 設(shè)設(shè) y= f(x) 在區(qū)間在區(qū)間a,b上連續(xù)，在上連續(xù)，在a,b內(nèi)內(nèi)n+1個互不個互

17、不 相同的點相同的點 上取值上取值 .求一代數(shù)多項式求一代數(shù)多項式P(x) ，使，使 得得 )(,010bxxaxxxnn nyyy,10)14(), 1 , 0()( niyxPii則稱則稱P(x)為為f(x)的的插值函數(shù)插值函數(shù)1 插值多項式插值多項式定理定理 4.1 在在 n+1 個互異點個互異點 上滿足插值條上滿足插值條 件件 (4-1) 的次數(shù)不超過的次數(shù)不超過n次的插值多項式次的插值多項式 存在且惟一。存在且惟一。 nxxx,10)(xPn 兩種插值多項式形式兩種插值多項式形式 (1) 拉格朗日插值多項式拉格朗日插值多項式 下列列表函數(shù)的多項式下列列表函數(shù)的多項式Ln(x) xx0

18、 x1- xi-1xixi+1- xnyy0y1- yi-1yiyi+1- yn)54()()(000 ninjijjijiniiinxxxxyxlyxL)()()()()()()()()(1210120102010210nnnnnxxxxxxxxxxxxyxxxxxxxxxxxxyxL ) 54()()()()(110110 nnnnnnxxxxxxxxxxxxy010110101)(xxxxyxxxxyxL 線性插值線性插值(n=1)， 拋物插值拋物插值 (n=2) )()()()()()()(1202102210120120102102xxxxxxxxyxxxxxxxxyxxxxxxxx

19、yxL (2)牛頓均差插值多項式牛頓均差插值多項式)()()(,)(,)(,)()(110010102100100 nnxxxxxxxxxxxfxxxxxxxfxxxxfxfxN nkkkxxxxfxf1100)(,)( Ln(x)和和N(x)插值多項式的余項插值多項式的余項 ),()()74(,),()!1()()(1)1(baxbaxxnfxRnnn )64()()(01 njjnxxx )()()()()(xNxfxLxfxRnn )()()(,)(10010nnnxxxxxxxxxxxxfxR )204()(,110 xxxxxfnn 例：已知列表函數(shù)例：已知列表函數(shù),并計算并計算f(

20、0.5)的計算值。的計算值。)()(33xNxL和和作作)()()()()(332211003xlyxlyxlyxlyxL 解：解：)2)(1(61)()()()()(3020103210 xxxxxxxxxxxxxxxxl而而)2)(1)(1(21)()()()()(3121013201 xxxxxxxxxxxxxxxxl)2)(1(21)()()()()(3212023102 xxxxxxxxxxxxxxxxl)1)(1(61)()()()()(2313032103 xxxxxxxxxxxxxxxxlx-1012y111-5375. 1)5 . 0()5 . 0(1)(333 PfxxxP

21、)1)(1(615)2)(1(211)2)(1)(1(211)2)(1(611)()()()()(332211003 xxxxxxxxxxxxxlyxlyxlyxlyxLx-1012y111-5(1)由數(shù)據(jù)表由數(shù)據(jù)表構(gòu)造均差表構(gòu)造均差表kxkf (xk)一階均差一階均差二階均差二階均差三階均差三階均差0-1100-11010-3211-632-5) 1() 1(1)()(,)(,)(,)()()2(21032101021001003 xxxxxxxxxxxxxfxxxxxxxfxxxxfxfxN又解：又解： niiimkkmkmmmyxpxaxaxaaxP02010)()(最最小小。使使經(jīng)經(jīng)驗驗曲曲線線）（求求 niiimmmyxPaaaFmaaa021010(),(1(,最最小小。）元元函函數(shù)數(shù)）使使即即