數(shù)值分析筆記期末復(fù)習(xí)

1、第一章引論 1、數(shù)值分析研究對象： 數(shù)值分析是計(jì)算數(shù)學(xué)的一個(gè)主要部分，計(jì)算數(shù)學(xué)是數(shù)學(xué)科學(xué)的一個(gè)分支，它研究用計(jì)算 機(jī)求解各種數(shù)學(xué)問題的數(shù)值計(jì)算方法及其理論與軟件實(shí)現(xiàn)。 2、數(shù)值分析特點(diǎn)： 面向計(jì)算機(jī)，要根據(jù)計(jì)算機(jī)特點(diǎn)設(shè)計(jì)切實(shí)可行的有效算法有可靠的理論分析，能任 意逼近并達(dá)到精度要求，對近似計(jì)算要保證收斂性和數(shù)值穩(wěn)定性要有好的計(jì)算復(fù)雜 性，時(shí)間復(fù)雜性好是指節(jié)省時(shí)間，空間復(fù)雜性好是指節(jié)省存貯量，這也是建立算法要研 究的問題。要有數(shù)值試驗(yàn)，即任何一個(gè)算法除了從理論上要滿足上述三點(diǎn)外，還要通 過數(shù)值試驗(yàn)證明是行之有效的。 3、數(shù)值分析實(shí)質(zhì)： 是以數(shù)學(xué)問題為研究對象， 不像純數(shù)學(xué)那樣只研究數(shù)學(xué)本身的理論

2、，而是把理論與計(jì)算 緊密結(jié)合，著重研究數(shù)學(xué)問題的數(shù)值方法及理論。 4、用計(jì)算機(jī)解決科學(xué)計(jì)算問題通常經(jīng)歷以下過程 實(shí)際問題-數(shù)學(xué)模型（應(yīng)用數(shù)學(xué)）-數(shù)值計(jì)算方法-程序設(shè)計(jì)-上機(jī)計(jì)算結(jié)果（計(jì)算數(shù)學(xué)） 5、誤差來源及分類 1模型誤差一一從實(shí)際問題中抽象出數(shù)學(xué)模型 2觀測誤差一一通過測量得到模型中參數(shù)的值（通常根據(jù)測量工具的精度，可以知道 這類誤差的上限值。） 3截?cái)嗾`差當(dāng)數(shù)學(xué)模型得不到精確解時(shí)，要用數(shù)值計(jì)算方法求它的近似解，由此產(chǎn) 生的誤差稱為（截?cái)嗾`差）或（方法誤差） 4舍入誤差一由于計(jì)算機(jī)字長有限,原始數(shù)據(jù)的輸入及浮點(diǎn)數(shù)運(yùn)算過程中都有可能產(chǎn) 生誤差，這樣產(chǎn)生的誤差稱為舍入誤差 6、五個(gè)關(guān)于誤差的概

3、念 1.絕對誤差e（x*） 2.絕對誤差限* 3相對誤差er （x*） 4相對誤差限r(nóng) （X*） （1）定義： （1）定義: （1）定義: （1 ）定義： 若指定一個(gè)適當(dāng)小的正數(shù)，使 若指定一個(gè)適當(dāng)小的正數(shù) 設(shè)某一量的準(zhǔn)確值為 X,近 絕對誤差與準(zhǔn)確值之比 似值為X*，則X*與X之差 |e(x*) | x* x* 則稱 * */ *、e(x*) x* x r (X*),使 叫做近似值 X*的絕對誤差 為近似值 X*的絕對誤差限。 er er(x*),x xx 0 ,/|e(x*) |、 （簡稱誤差），記為 （有時(shí)用X X*表示近似值 稱為X*的相對 l er (x*) |r (x*) |x|

4、e* e(X*) x* x 慶。 （2）性質(zhì)： X*的精度或準(zhǔn)確值的所在范圍。 （2）性質(zhì)： 則稱r（x*）為近似值X*的相 （1）絕對誤差e（X*）可正可 ） （2）性質(zhì)： （1）相對誤差是個(gè)無量綱量。值 小者精度咼。 對誤差限。 負(fù)（2） |e（x*） |的大小標(biāo)志 （1）在實(shí)際問題中，絕對誤差一 （2）性質(zhì)： 著x*的精確度 （3）絕對誤 般是有量綱的，絕對誤差限也是 （2）由于準(zhǔn)確值x未知，故實(shí)際 當(dāng)|er（x*） |較小時(shí)，可用下式 差e（x*）未知 有量綱的。 冋題中，當(dāng)ler（x*） |較小時(shí)， （3）判斷： （2）絕對誤差限是正的，有無窮 e( x*) 計(jì)算 多個(gè)【則比 *大的

5、任意正數(shù)均 常取 er (x*) 絕對誤差是誤差的絕對 是絕對誤差 X* / *(x*) r(X*) 值？（錯(cuò)） 限】 |X | 5有效數(shù)字 (1)定義：若近似值x*的絕對誤差限是某一位的半個(gè)單位，該位到x*的第一位非零數(shù) 字一共有n位，則稱近似值 x*有n位有效數(shù)字，或說 x*精確到該位。注意：近似值后 面的零不能隨便省去！ 1 (2) 例題：取x1*= 3作為n的近似值，則|e | 0.1415L- 10: 一個(gè)有效數(shù)字 2 1 2 取x2* =3.14作為n的近似值，則|3| 0.00159L- 1 :三個(gè)有效數(shù)字 2 1 4 取x3* =3.1416作為n的近似值，則 6 | .734

6、L 1 :五個(gè)有效數(shù)字 2 它們的誤差都不超過末位數(shù)字的半個(gè)單位。 (3) 性質(zhì)：(1)有效數(shù)字越多，則絕對誤差越小 (2)有效數(shù)字越多，則相對誤差越小 有效數(shù)字的位數(shù)可刻畫近似數(shù)的精確度！ 6、一元函數(shù)的誤差估計(jì) 問題：設(shè)y=f(x), x的近似值為x*，則y的近似值y*的誤差如何計(jì)算? e(y*) dy f (x*)dx f (x*) e(x*) er(y*) dy f (x*) e(x*) f (x*) x* f(x*)而 er(x*) e(y*) f (x*)e(x*) er(y*) x* f(x*)f(x*) U(x*) 故相應(yīng)的誤差限計(jì)算如下 (y*) f (x*) (x*) r(

7、y*) f (x*) x* f(x*) r(x*) 7、二元函數(shù)的誤差估計(jì) 問題：設(shè)y=f(x1, x2) , x1, x2的近似值為x1*, x2* ，則y的誤差如何計(jì)算? e(y*) y* y f(x；,x；) f(xX2)df(x*1,x*2) f(x)x*2) e(x*J f(x*1 X*2) e(x*2) X1X2 e(y*)如芻Xi)空必2亦)上3 |e(x*i) 仝空 |e(x*2) Xx2x1x2 故絕對誤差限為 (y*)(x*ix*2)(x*i)(x*ix*2)(x*2) x1x2 8、多元函數(shù)的誤差估計(jì) f(X*i,X*2, L ,X*n) Xn e(x*n) f(X*i,

8、X*2,L ,X*n) e(y*) y* ye(x*J X f(X*i,X*2,L ,X*n) -e(x*i) 9、加減乘除運(yùn)算的誤差估計(jì) 加法 減法 乘法 除法 絕 對 誤 差 e(x.| x2) e(x1) e(x2) e(x1 x2)e(x1) e(x2) e( x1 x2) x2e(x1) x1e(x2) X1X2e(xJ X1e(X2) e( )2 x2x2 絕 對 誤 差 限 (X1 X2)(X1)(X2) (X1 X2)(X1)(X2) (X1X2)X2 (X1)X(X2) 胳、|X2 (X1) X (X2) () 2 X2X2 相 對 誤 差 /、e(xj e(X2) er(x

9、1 X2) ， X-| x2 /、e(為)e(X2) 0(X1 X2)丿丿 x1 x2 er(X1X2)0(X1) e(X2) U ()0(X1)0(X2) X2 相 對 誤 差 限 r(X1 X2)普十 |X1 X2I r(X1 X2)占21 |X1 X2 r(X1X2)r(xjr(X2) r(XjX2),為)r(X2) 4,插值問題 (1 )定義：初始數(shù)據(jù)的誤差或計(jì)算中的舍入誤差在計(jì)算過程中的傳播，因算法不同而異。 一個(gè)算法，如果計(jì)算結(jié)果受誤差的影響小，就稱該算法具有較好的數(shù)值穩(wěn)定性 (一) 要避免相近兩數(shù)相減 e In x e In x In 1 x sin(x ) sinx 2cos(

10、x 2)sin 2 x121 3. e 1 x x x L 2 6 (二) 要防止大數(shù)“吃掉”小數(shù)，注意保護(hù)重要數(shù)據(jù) 、， b sign(b) Jb2 4ac “9 X10 2a cc109 , X1 X2 X29 1 aa 捲 10 求和時(shí)從小到大相加，可使和的誤差減小。若干數(shù)相加，采用絕對值較小者先加的算法，結(jié) 果的相對誤差限較小 y 54321 1000.4 1 00.3 100.4 1054322 (三) 注意簡化計(jì)算步驟，減少運(yùn)算次數(shù)，避免誤差積累(秦九韶) 巳(x)0.0625x4 0.425x3 1.215x2 1.912x 2.1296 (0.0625X 0.425)x 1.1

11、25)x 1.912)x 2.1296 (四) 要避免絕對值小的數(shù)作除數(shù) 胳、|x2)(為)|xj (X2) () X2x2 1 cosx sin x sin x1cosx x_x(x1、x) .X 1X (五) 設(shè)法控制誤差的傳播 許多算法具有遞推性。遞推法運(yùn)算過程較規(guī)律，但多次遞推必然導(dǎo)致誤差的積累。 En 1 nEn 1 巳 1/e n 2,3丄,9 e(齊次性) 3)|x y| |x| |y|,x,yRn(三角不等式) 則稱IxI為向量的范數(shù) 在Rnxn上的矩陣A=(aj), 設(shè)對任意矩陣 ARnxn,按一定的規(guī)則有一實(shí)數(shù)與之 對應(yīng)，記為I AI,若I AI滿足 1) |A| 0當(dāng)且僅

12、當(dāng)A 0時(shí)才有| A0；正定性) 2) |cA |c|A, c R;(齊次性) 3) A B A |B ,(三角不等式) 4) |AB| |A|B|,(相容性) 則稱I AI為矩陣的范數(shù) xmax Xj稱為g范數(shù)或最大范數(shù) 1丨 1 i n 【絕對值最大的元素】 n Il A maxaij稱為g范數(shù)或行范數(shù) I n j 1 【所有元素絕對值之和最大的一行】 n I|x|l|x| i 1 n1 X 2( X2)2 i 1 稱為1范數(shù) 稱為2范數(shù) Xi 1 p)? 稱為p 范數(shù) 【所有值絕對值的 P次方求和，再開 P次方】 n | max| aij | 稱為1范數(shù)或列范數(shù) j n i 1 【所有元

13、素絕對值之和最大的一列】 IIX2 J max(ATA)稱為 2范數(shù) 【ata的最大特征值開平方】 n1 UAL(Xj2)2稱為 Frobennius 范數(shù) i,j 1 【所有元素平方和開平方】 定義： 如果Rn中有兩個(gè)范數(shù)|x|s與|兇|t ,存在常數(shù) m, M0，使對任意n維向量x 有 m|x|L |x|LM|x|L 則稱這兩個(gè)范數(shù)等價(jià) 性質(zhì)： 對兩種等價(jià)范數(shù)而言，某向量序列在其中一種 范數(shù)意義下收斂時(shí)，則在另一種范數(shù)意義下也收斂。 定理： Rn上的任意兩個(gè)范數(shù)等價(jià)?！咀ⅲ航窈笱芯肯?量序列的收斂性時(shí)，可在任何一種范數(shù)意義下研 究?！?3、“病態(tài)”方程組 1定義: AlZ 當(dāng)一個(gè)方程組，由

14、于系數(shù)矩陣 A或右端常數(shù)項(xiàng)b的微小變化，引起方程組 Ax=b解的 巨大變化，則稱此方程組為“病態(tài)” 方程組， 矩陣A稱為“病態(tài)”矩陣，否則稱方程組為“良 態(tài)”方程組，A為“良態(tài)”矩陣 2、如何劃分“病態(tài)”的程度: 條件數(shù): 設(shè)A為非奇異陣，稱 -1 cond(A) v=|A | v|A| v (v =1,2, 為矩陣A的 條件數(shù)。 5 I|x| |A1| |A| 俱 |b| cond(A|【b】 |b| ILII I|x| cond(A)U AJ 【A】 |A| | A 1 cond(A) |A| 則系數(shù)矩陣 A的條件數(shù)刻劃了方程組的“病態(tài)”程度。條件數(shù)愈大，方程組的“病態(tài)” A的條件數(shù)相對地

15、小，則方程組 程度愈大，也就愈難得到方程組的比較準(zhǔn)確的解；當(dāng)矩陣 是“良態(tài)”的。 4、線性方程組解法 向量序列的收斂性 矩陣序列的收斂性 定義1 設(shè)x (k)為Rn中的向量序列，x Rn, 設(shè)A (k)為n階方陣序列，A為n階 如果 lim |x(k)x| 0 其中 |.| 為向 k 方陣，如果lim |A(k)A| 0其中|.|為 k 量范數(shù)，則稱序列x (n)收斂于x，記 矩陣范數(shù)，則稱序列A(n)收斂于A,記 為 im x(k)x 為 lim A(k)A k 定理1 R1中的向量序列x (k)收斂于R1中的向 量x當(dāng)且僅當(dāng) lim x(k)xi(i 1,2,., n) (k)/(k)(k

16、)(k) T x(X1 ,X2，Xn ), x(X1,X2，,Xn)T 設(shè) A、= (a ij) (k=1,2,),A = (a ij ) 均為n階方陣，則矩陣序列A(n)收斂于 矩陣A的充要條件為 lim a(k)aij(i, j 1,2,.,n) k 直 接 消 去 法 高斯 直接 消去 法 主元 素法 高斯 約當(dāng) 消去 法 a( )二 11 12 - X1 a；?. a22n ? X2 O M ann) Xn 基本思想：用逐次消去未知數(shù)的方法把原來方程組 AX=b化為與其等價(jià)的三角形方程組，而求解三角形方 程組就容易了！ 高斯消去法的特點(diǎn)訂消元和回代不同步！ 使用高斯消去法的條件:使用高

17、斯消去法要求在每步 消元時(shí)akk0, 定理:約化的主元素 akkk)0 (i=1,2,n)的充要 條件是矩陣A的順序主子式 Di 0(i1,2,., n) 定理6 :如果n階矩陣A的所有順序主子式均不為零， 則可通過高斯消去法(不進(jìn)行交 換兩行的初等變換)，將方程組約化為三 角形方程組。 定理6:如果A為n階非奇異矩陣，則可通過高斯消 去法(及交換兩行的初等變換)將方程組 Ax=b化為 三角形方程組。 在采用高斯消去法解方程組時(shí)，小主元可能產(chǎn) 生麻煩，故應(yīng)避免采用絕對值小的主元素。 對一般矩陣，最好每一步選取系數(shù)矩陣(或 消元后的低階矩陣)中絕對值最大的元素作 為主元素，以使高斯消去法具有較好

18、的數(shù)值 穩(wěn)定性！ 列主元素法： 選主元時(shí)僅考慮按列選取，然后換行使之變到主元位 置上，再進(jìn)行消元計(jì)算。列主元消去法的特點(diǎn)： (1)能夠得到較高精度要求的解； (2 )計(jì)算量大大減少 高斯一一約當(dāng)消去法定義： (k n 1,n 2,.,2,1) 推論：如果A的順序主子式不等于0，則 anD1 (k) eg (k 23,n) akkDk Dk 1 完全主兀素法： a11a12. a1n * b a22. a2n c y2 b2甘出 其屮y1,y2,，y i為 O M M ann yn bn 未知數(shù)X1,X2, ,X調(diào)換后的次序。 【第一步：首先在 A 中選取絕對值最大的元素作為主元素；然后交換到第

19、 行、第一列的位置；再進(jìn)行第一次消元，】完全主元素 消去法的缺點(diǎn)：在選主元素時(shí)要花費(fèi)較多機(jī)器時(shí)間。時(shí) 時(shí)紀(jì)錄X順序的變化情況 yn bn ann J yk (bk n akj yj) akk j k 1 (k n 1,n 2,. -,2,1) 1 0 . 0 x1 (n) 0 1 . 0 x2 (n) 02 O M M 0 0 . 1Xn 護(hù) 直 接 角 法 直接三角 分解法 A LU 定理：（矩陣的LU分解） 設(shè)A為n階矩陣，如果 A的順序主子式 （i = 1,2,n -1）, 則A可分解為一個(gè) 單位下三角矩陣q和一個(gè)U|的 乘積，且這種分解是唯一的。注：若A實(shí)現(xiàn) 了 LU 分解，則 Ax

20、= b （LU）x=b Ly = b Ux = y 1 0 0 U11 u12 U13 A l21 1 0 ? 0 U22 U23 LU l31 l32 1 0 0 U33 單位下三角陣上三角陣 1 0 0 1 1 1 A 0 1 0 ? 0 4 1 LU 2 1 1 0 0 2 1 0 0 y1 6 y1 0 1 0 ? y2 5 解得 y2 2 1 1 y3 1 y3 1 1 1 y1 治 0 4 1 ? x2 y2 解得 X2 0 0 2 X3 y3 X3 6 5 6 1 2 3 平方根法 平方根法適用于I系數(shù)矩陣為對稱正定陣勺方 程組的求解。 定理 1（_對稱陣的三角分解定理 ） 設(shè)A

21、為n階對稱陣，且A的所有順序主子式均 其中 l21 l31 l32 lt 13 L23 1 不為零，則A可唯一分解為 A=LDL a=ldL 為單位下三角陣，D為對角陣 A=LL 追趕法 定理2（ 對稱正定陣的三角分解定理 ） 設(shè)A為n階對稱陣，且A的所有順序主子式均 大于零，則存在一個(gè)非奇異下三角陣L使 A=LL,當(dāng)限定L的對角元素為正時(shí)，這種 分解是唯一的。Cholesky分解 追趕法適用于系數(shù)矩陣為三對角陣的方程組 的求解。 利用系數(shù)矩陣的特點(diǎn)，可以將A分解為兩個(gè)三 角陣的乘積， L為下三角矩陣，U 為單位上三角矩陣。 I11 I21 ln1 I22 ln2 U12 1 U13 U23

22、1 l nn l11 0 0 l11 l12 l13 L l21 l22 0 lt 0 l22 l23 l31 l32 l23 0 0 l33 b1 q a2 b2 C2 A as O O O O cn 1 an bn 1 1 1 雅一般形式 克 比 迭 代 法 高 斯 塞 德 爾 超 松 弛 迭 ai xa2 X? a2iXia22 X2 an1 X1an2 X2 Xi X2 Xn x(0) (k 1) Xi X1 X2 Xn a2nXn annXn b2 bn (ai2X2 (a2iXi ain Xn bi)/aii a2nXnb2)/ a22 an1 X1an2X2an ,n (Xi(0

23、),x20) 1 (bi an 1Xnbn) / ann ,xno)T(初始向量) n 小(k) aijXj ) i 1 j i (a12X2 (a21X1 (an1 X1 an2X2 3)/1 a2nXnb2)/ a22 an ,n 1Xnbn) / ann x(0)(X, x20),xn)t(初始向量) i 1n (k 1)1(k 1)(k)、 Xi(biaijXjajXj ) aiij 1j i 1 X(k+1)=%(k)+ 是G-S法；o X(k1) x(k) co 1 x o 1時(shí)，稱為低松弛; 時(shí)，稱為超松弛法，簡稱 xi (1 )Xi(k) aH (bi 1 (k aij Xj

24、1 1) (i 1,2,., n) 5、迭代法斂散性判斷方法 o =1 時(shí)， SOR法 n (k)、 ajXj) i 1 將方程組記為 Ax = b 其中A非奇異且aii 豐 0 (I=1,2,- n).將A分裂為 A = =D -L-U 其中 a11 0 0ai2.a1n fa22 a210 0. a2n D L U O .O O . ann 011an2.0 0 矩陣形式 x(0) x(k 1) (X1(0) ,x20),.,xrJ0)T(初始向量) BoX(k)f 將方程組記為 Ax = b其中A非奇異且aii豐0(1=1,2, a11 0 0耳2. a1n D a22 日210 0 .

25、 a2n L U O .O O ann an1an2.0 0 n).將A分裂為A = D -L-U 其中 x(0)(x,0) ,x20),., xf(0)T(初始向量) X(k 1) (D L) 1Ux(k)(D L) 1b 用分解式 A = D -L-U,則可寫為 x(k 1)(D L) 1(1)DU)x(k) 1 (D L) b 注： (1) 松弛法是G-S法的一種加速方法； (2) 具有計(jì)算公式簡單，程序設(shè)計(jì)容易; (3) 但需要選擇較好的加速因子。 預(yù)備 定義 已知 定理 定義1:稱迭代公式x(k 1) Bx(k) f中的矩陣B為迭代矩陣. 定義2 :設(shè)A為n階方陣，入(i = 1,

26、為A的特征值，稱特征值模的最大值為矩陣 A的譜半徑，記為 (Amiax| i | 定義2 : 1, 2,., n稱為矩陣A的譜. 定義 3: Ak = AA A 的譜為 1k, 2,., nk( k = 1,2,) 定義 3: Ak = aa-A 的譜半徑為(Ak) max| ik | (A)k 1 i n 定理1:設(shè)A為任意n階方陣，|.|為任意由向量：范數(shù)誘導(dǎo)出的矩陣的范數(shù)，則 (A) |A| 定理2：設(shè)A為n階方陣，則對任意正數(shù),存在一種矩陣范數(shù)|.|,使得| A|(A) 輔助 定理3:設(shè)A為n階方陣，則im Ak 0的充要條 弱件為 (A) 1 定義：若n階方陣A=(a j)滿足 匕|

27、 |aij | (i 1,2,., n)且至少有一個(gè)i 定義 值，使上式中不等號嚴(yán)格成立，則稱A為弱對角占優(yōu)陣。若對所有 格成立，則稱 A為嚴(yán)格對角占優(yōu)陣。 i，不等號均嚴(yán) 定義：如果矩陣A不能通過行的互換和相應(yīng)列的互換成為形式 An 0 A2其中A A 22為方陣，則稱 A為不可約. 收斂 設(shè)有線性方程組 Ax=b,下列結(jié)論成立: 判斷 1. 若A為嚴(yán)格對角占優(yōu)陣或不可約弱對角占優(yōu)陣，則 Jacobi迭代法和 條件 Gauss-Seidel迭代法均收斂。 2. 若A為嚴(yán)格對角占優(yōu)陣，03三1,則松弛法收斂。 3. 推論: 若A為對稱正定陣，03 2,則松弛法收斂.即：若A是對稱正定陣，則松弛

28、 法收斂的充要條件為 03 2。 若迭代矩陣滿足|M|1，則迭代公式產(chǎn)生的向量序列x(k)收斂。 定理：對任意初始向量x和右端項(xiàng)g，由迭代格式x(1)= Mx+ g產(chǎn)生的向量序 列收斂的充要條件為(M) 1 推論：松弛法收斂的必要條件是03 1，稱x*是m重根. 2、求根的兩個(gè)步驟 (1) 確定根的初始近似值(稱之為初始近似根)，一般為一個(gè)包含根的區(qū)間，稱為“有根區(qū)間” 【逐步掃描法：原理：設(shè)f(x)在a, b連續(xù)，且f(a) f(b)0。則由連續(xù)函數(shù)的性質(zhì)知 f (x)=0在(a, b)內(nèi)至少有一個(gè)根。若 f (x)在a, b上單調(diào)，則f (x)=0在(a, b)上有且 僅有一個(gè)根。】 (2

29、) 根的精確化。根據(jù)根的初始近似值按某種方法逐步精確化，直至滿足預(yù)先要求的精度為 止。【二分法簡單迭代法牛頓迭代法弦截法】 2、分類 二分法 原理：若f Ca, b，且f (a ) f (b) 0，則f在(a, b) 上必有一根 x*。 實(shí)施：將方程根的區(qū)間平分為兩個(gè)小區(qū)間，然后判斷根在哪個(gè)小區(qū)間,舍去無根 的區(qū)間，而把有根區(qū)間再一分為二，再判斷根屬于哪個(gè)更小的區(qū)間，如此周而復(fù) 始，直到求出滿足精度要求的近似根。 停止：|兀 1 xj 或 |f(x)| b a 誤差分析：|Xk x* |2k對于給定的精度，可估計(jì)二分法所需的步數(shù)k 優(yōu)點(diǎn)：簡單； 對f (x)要求不高(只要連續(xù)即可). 缺點(diǎn)：無

30、法求復(fù)根及偶重根收斂慢 簡單迭 代法 基本思想： f(x) = 0【同解變形】x = g(x)【構(gòu)造公式】Xk+i = g(xk)【給初值xo ;若xx* 且g(x)連續(xù)】x*就是f(x)=0的根 區(qū)間收斂： 設(shè)方程 x = g(x)有根 x*, g(x)可微，若(I )當(dāng) x a, b時(shí)，g(x) a, b;( II) 0 L 1 使得 | gx)| L 1 對 x a, b成立。 則任取xo a, b，由xk+i = g(xk)得到的序列Xk k0收斂于g(x)在a, b 上的唯一不動點(diǎn)。 注1:定理中的L1非常重要，否則不能保證收斂，且L越小，收斂越快。 注2：為恰當(dāng)估計(jì)| g(X)|，

31、可以把有根區(qū)間取得適當(dāng)小。 補(bǔ)充：1迭代是否收斂除了依賴于迭代函數(shù)外，還依賴于有根區(qū)間。 2.設(shè)方程x=g(x)在區(qū)間a,b內(nèi)有根，若總有| g (x) | 1,則迭代公式對任意 a,b上的初值均發(fā)散。 局部收斂： 定義：設(shè)x*是g(x)的不動點(diǎn)，若存在 x*的某 鄰域B = x | | x x* |, 對X。B迭代產(chǎn)生的序列XkB且收斂到x*，則稱Xk1g(xQ局部收斂. 定理：設(shè)x*是g(x)的不動點(diǎn)，若g(x)在x*的某 鄰域連續(xù)，且有| g x*) | 1時(shí)：超線性收斂，p = 2時(shí)：平方收斂 定理： 設(shè) x* 為 x = g(x)的不動點(diǎn)，若 g(x) Cp(B (x*) , p 2

32、； 且 g (x*). g(p 1(x*)0 ,貝U xk+1 = g(xk)在 B (x*)內(nèi) p 階收斂。 牛頓迭 原理：將非線性方程線性化一一泰勒展開 代法 f (X*)f(X)f (x)(x* X。) f () 2! (x* Xo)2 X f (Xk) k1 Xk f(Xk) 弦截法 局部收斂性 設(shè)f a,b，若X*為f (x)在a,b上的根，且f (x*)0 ,則存在 x*的鄰域B (x*)使得任取初值x0B (x*) Newton Method產(chǎn)生的序列 xk 收斂到x*，且滿足 xk K X xk 2 1 1 Im KHk 有 xnxn f (x*) 2 f (x*) 只要 f

33、(x*)0就有 p 2。重根是線性收斂的。 注：| (1)牛頓法要求初值充分接近根以保證局部收斂性。 (2)牛頓迭代法的主要優(yōu)點(diǎn)是收斂較快，是平方收斂的缺點(diǎn)是公式中需要求f(x) 的導(dǎo)數(shù)。若f(x)比較復(fù)雜，則使用牛頓公式就大為不便。 針對問題：重根問題f(x) (x x*)n q(x) 問題1:若f (x*)0，Newton s Method 是否仍收斂？ K1:有局部收斂性，但重?cái)?shù) n越高，收斂越慢。 問題2:_如何加速重根的收斂？ K2:將求f的重根轉(zhuǎn)化為求另一函數(shù)的單根。令(x) f(x)則f的重根= f (x) 的單根。 下山法： 原理：若由Xk得到的Xk+1不能使I f |減小，則

34、在Xk和Xk+1之間找一個(gè)更好的 點(diǎn) Xk 1 使得 f(Xk1)f (xk) =1 時(shí)就是 Newton s Methoc公式。當(dāng) =1代入效果不好時(shí)，將減半計(jì)算。 Xk 1Xk 常(1 )XkXk f(Xk) f (Xk) 弦截法 Newton s Method 步要計(jì)算 f和f ,相當(dāng)于2個(gè)函數(shù)值，比較費(fèi)時(shí)?，F(xiàn) 用f的值近似f ，可少算一個(gè)函數(shù)值。需要2個(gè)初值xo和X1 切線斜率害憐斜率 f(x) f(Xk) f(Xk1) Xk 1Xk f (Xk )(Xk Xk 1) f(Xk) f(Xk1) Xk Xk 1 弦截法與牛頓法相比較 相同之處：都是線性化方法 不冋之處：牛頓法在計(jì)算 xk

35、+1時(shí)只用到前一步的值 xk，故這種方法稱為單點(diǎn)迭 代法；而弦截法在求xk+1時(shí)要用到前兩步的值 xk和xk-1 ,因此這種方法稱為多 點(diǎn)迭代法。 弦截法的收斂速度 與牛頓法相比，弦截法的收斂速度也是比較快的?？梢宰C明，弦截法具有超線性 收斂速度，收斂階為p -(1 x/5) 1.618 即_xk111|8c 0,(k) 21 xXk |. 第6章解常微分方程 1、定義 yf(x,y)理論上可以證明：只要函數(shù)f(x , y)適當(dāng)光滑一關(guān)于y滿足李普希茲(Lipschitz) y(x。) yo 條件|f(x, y) f(x, y)| L|y y |則初值問題的解存在唯一。 2、兩種解 一般解(解

36、析 解)y=y(xi)在 x=xi處的精確 值 對一些典型的微分方程(可分離變量方程，一階線性方程等等)，有可能找 出它們的一般解表達(dá)式，然后用初始條件確定表達(dá)式中的任意常數(shù)，這樣 y 2x 解即能確定。故解為y=x2 y(0) o 數(shù)值解(近似 解):匸一般解 y=y(x)在 x=x、 處的近似值 由于在實(shí)用上對初值問題，一般是要求得到解在若干點(diǎn)上滿足規(guī)定精確度 的近似值yi，或者是得到一個(gè)滿足精確度要求的便于計(jì)算的近似表達(dá)式。 故常微分方程的數(shù)值解就是求出在若干點(diǎn)上解的近似值。 疋義：扌曰在由初始點(diǎn)xo開始的右干離散的 x值處，即對 XoX1X2y xn, 求出準(zhǔn)確值y(X1),y(x2),y(xn)的近似值y1, y2,，yn yi, y2,，yn 用差 y(x h) y(X)y(x) f(x,y) h 商代 替導(dǎo) 2、三種數(shù)值解法 y 1 V、hf(Xi，yJ yoy(xo)、 o,i,2L yn=yn-l+hf(x o+( n-1)h,y n-l) 使用 泰勒 公式 在微分方程y =f (x, y)中，y是x及 y(x)的函數(shù).由于精確值 y(x+h)在h-0 處的泰勒展式為 h2 y(x h) y(x) hy(x) y(x) 2 h/ 、 h4(、 y (x-y (x) 62