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

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

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

3、4.相對誤差限（1）定義：設(shè)某一量的準(zhǔn)確值為x，近似值為x*，則x*與x之差叫做近似值x*的絕對誤差(簡稱誤差)，記為（2）性質(zhì)：(1)絕對誤差e(x*) 可正可負(fù) (2) |e(x*) |的大小標(biāo)志著x*的精確度 (3) 絕對誤差e(x*) 未知（3）判斷：絕對誤差是誤差的絕對值？（錯）（1）定義：若指定一個適當(dāng)小的正數(shù)，使則稱為近似值 x* 的絕對誤差限。(有時用表示近似值x*的精度或準(zhǔn)確值的所在范圍。)（2）性質(zhì)：(1)在實(shí)際問題中，絕對誤差一般是有量綱的，絕對誤差限也是有量綱的。(2)絕對誤差限是正的，有無窮多個【則比大的任意正數(shù)均是絕對誤差限】（1）定義：絕對誤差與準(zhǔn)確值之比稱為x*

4、的相對誤差。（2）性質(zhì)：(1)相對誤差是個無量綱量。值小者精度高。(2)由于準(zhǔn)確值x未知，故實(shí)際問題中，當(dāng) | 較小時，常取（1）定義：若指定一個適當(dāng)小的正數(shù) ，使則稱為近似值 x*的相對誤差限。（2）性質(zhì)：當(dāng)|較小時，可用下式計算5.有效數(shù)字（1）定義：若近似值x*的絕對誤差限是某一位的半個單位，該位到x*的第一位非零數(shù)字一共有n位，則稱近似值x*有n位有效數(shù)字，或說x*精確到該位。注意：近似值后面的零不能隨便省去?。?）例題：取x1*= 3作為的近似值，則：一個有效數(shù)字 取 x2* =3.14 作為的近似值，則：三個有效數(shù)字 取 x3* =3.1416作為的近似值，則：五個有效數(shù)字 它們的

5、誤差都不超過末位數(shù)字的半個單位。（3）性質(zhì)：(1)有效數(shù)字越多，則絕對誤差越小 (2)有效數(shù)字越多，則相對誤差越小 有效數(shù)字的位數(shù)可刻畫近似數(shù)的精確度！6、一元函數(shù)的誤差估計問題：設(shè)y=f(x)，x的近似值為x*，則y的近似值 y*的誤差如何計算？故相應(yīng)的誤差限計算如下7、二元函數(shù)的誤差估計問題：設(shè)y=f(x1, x2)， x1, x2的近似值為x1*, x2* ，則y的誤差如何計算？ 故絕對誤差限為8、多元函數(shù)的誤差估計9、加減乘除運(yùn)算的誤差估計加法減法乘法除法絕對誤差絕對誤差限相對誤差相對誤差限10、算法的數(shù)值穩(wěn)定性概念及運(yùn)算（1）定義：初始數(shù)據(jù)的誤差或計算中的舍入誤差在計算過程中的傳播，

6、因算法不同而異。一個算法，如果計算結(jié)果受誤差的影響小，就稱該算法具有較好的數(shù)值穩(wěn)定性11、設(shè)計算法的五個原則(一) 要避免相近兩數(shù)相減(二) 要防止大數(shù)“吃掉”小數(shù)，注意保護(hù)重要數(shù)據(jù)求和時從小到大相加，可使和的誤差減小。若干數(shù)相加，采用絕對值較小者先加的算法，結(jié)果的相對誤差限較小(三) 注意簡化計算步驟，減少運(yùn)算次數(shù)，避免誤差積累（秦九韶）(四) 要避免絕對值小的數(shù)作除數(shù)(五) 設(shè)法控制誤差的傳播許多算法具有遞推性。遞推法運(yùn)算過程較規(guī)律，但多次遞推必然導(dǎo)致誤差的積累。 第二章 逼近問題1，函數(shù)逼近1、插值問題： 求一條曲線嚴(yán)格通過數(shù)據(jù)點(diǎn)2、曲線擬合問題： 求一條曲線在一定意義下靠近數(shù)據(jù)點(diǎn) 2，

7、插值問題1、定義：求一個簡單函數(shù)(x)作為f(x)的近似表達(dá)式，以滿足我們稱這樣的問題為插值問題； 并稱(x)為 f (x)的插值函數(shù)； f (x)為被插函數(shù)， x0 , x1, x2, , xn是插值節(jié)(基)點(diǎn)；是插值原則.3，插值多項式1、定義：求一個次數(shù)不超過n的多項式使?jié)M足插值原則(條件)稱Pn(x)為 f (x)的n次插值多項式2、定理：在n+1個互異節(jié)點(diǎn)處滿足插值原則且次數(shù)不超過n的多項式Pn(x)存在并且唯一。注：若不將多項式次數(shù)限制為 n ，則插值多項式不唯一。也是一個插值多項式，其中可以是任意多項式。4,插值問題拉格朗日差值牛頓插值二次插值基函數(shù)一階差商k階差商零階差商1.差

8、商與節(jié)點(diǎn)的排列次序無關(guān)，稱為差商的對稱性2.高階差商可由低階差商反復(fù)作一階差商得到，計算具有遞推性3.若f(x)在a, b上存在n階導(dǎo)數(shù)，則為了使得|n+1(x)|盡可能小一些，插值基點(diǎn)的選取原則是：使x盡可能位于區(qū)間Ix的中部，這里Ix是包含x以及所用基點(diǎn)的最小閉區(qū)間。1.計算量省，便于程序設(shè)計2.具有承襲性的插值公式，便于理論分析埃爾米特差值插值條件中除函數(shù)值插值條件外，還有導(dǎo)數(shù)值插值條件，即已知：2n+2個條件求:一個次數(shù)不超過2n+1的多項式H2n+1(x)解法1：基函數(shù)法解法2：承襲法分段低次插值原因：當(dāng)插值基點(diǎn)無限加密時，Pn(x)也只能在很小范圍內(nèi)收斂，這一現(xiàn)象稱為龍格(Rung

9、e)現(xiàn)象，它表明通過增加基點(diǎn)來提高逼近程度是不宜的。定義：設(shè)在a,b上給出插值條件：求一個折線插值函數(shù)Ih(x)滿足xix0x1xnf(xi)f0f1fn1°Ih(x)是a,b上的連續(xù)函數(shù)2°Ih(xk)=fk，k = 0,1,n3°Ih(x)在每個小區(qū)間xk,xk+1上是線性函數(shù)則稱Ih(x)為分段線性插值函數(shù)數(shù)學(xué)表達(dá)： 性質(zhì)：1°分段線性插值多項式是分段函數(shù)；2°可以預(yù)見，但n充分大時，Ih(x)能很好逼近f(x)。3°Ih(x)有一個缺點(diǎn)：在插值點(diǎn)處有尖點(diǎn)，即一階導(dǎo)數(shù)不連續(xù)，不夠光滑。解決辦法：三次埃爾米特插值三次樣條插值兩種構(gòu)

10、造方法5，最小二乘法1、 定義：已知：一組實(shí)驗(yàn)數(shù)據(jù)（xi，yi）(i=0,1,m)，且觀測數(shù)據(jù)有誤差求：自變量x與因變量y之間的函數(shù)關(guān)系y=F(x) ，不要求y=F(x)經(jīng)過所有點(diǎn)，而只要求在給定點(diǎn)上誤差按某種標(biāo)準(zhǔn)最小。2、 度量標(biāo)準(zhǔn)：(1)使殘差的最大絕對值為最小 (2)使殘差的絕對值之和為最小 (3)使殘差的平方和為最小 3、最小二乘法多項式擬合已知：一組數(shù)據(jù)（xi，yi）(i = 0,1,m) 求：在次數(shù)不超過n的多項式中找一個函數(shù)，使誤差平方和最小，即這里：解： 故： 解得：4、最小二乘法非多項式擬合參數(shù)線性 已知：一組數(shù)據(jù)（xi，yi）(i = 0,1,m)求：在函數(shù)類中找一個函數(shù)

11、，使誤差平方和最小，即這里：已知：一組數(shù)據(jù)（xi，yi），且每個點(diǎn)對應(yīng)權(quán)因子wi >0, (i=1,2,m).求：在函數(shù)類中找一個函數(shù) ，使誤差平方和最小，即這里：最小二乘法非多項式擬合參數(shù)非線性 第三章 定積分1，求解定積分問題方法：（求曲邊梯形面積）舊：（1）牛頓萊布尼茲公式 【需要尋求原函數(shù)的困難】【已知點(diǎn)離散】新：（2）機(jī)械求積公式 【多項式機(jī)械求積公式】*【解決原函數(shù)的困難】【中矩形公式】*【解決原函數(shù)的困難】【梯形公式】*【解決原函數(shù)的困難】【插值型求積公式】*【解決離散問題】2，代數(shù)精度 （1）目的：數(shù)值求積方法是近似方法，為了保證精度，我們自然希望公式能對“盡可能多”的函

12、數(shù)準(zhǔn)確成立，這就提出了所謂代數(shù)精度的概念。（2）定義：若某個求積公式對于次數(shù)m的多項式均能夠準(zhǔn)確成立，但對于m+1次多項式就不一定準(zhǔn)確，則稱該求積公式有m次代數(shù)精度。若某個求積公式對于1, x, xm 均能夠準(zhǔn)確成立，但對于xm+1就不準(zhǔn)確成立，則稱該求積公式有m次代數(shù)精度。（3）定理：當(dāng)n為偶數(shù)時，牛頓柯特斯公式至少有n+1次代數(shù)精度。注：在實(shí)際應(yīng)用時，出于對計算復(fù)雜性和計算速度的考慮，我們常常使用低階偶數(shù)求積公式，代替高一階的奇數(shù)求積公式。3，插值求積公式（1）定理：具有n+1個求積節(jié)點(diǎn)的機(jī)械求積公式至少有n次代數(shù)精度的充分必要條件是，它是插值型的。試總結(jié)證明機(jī)械求積公式是插值型求積公式的

13、方法。（2）求積公式的余項若求積公式的代數(shù)精度為m，則余項形如其中K是不依賴于f(x)的待定參數(shù)。3，牛頓柯特斯求積公式梯形，辛普森，柯特斯1、 定義【牛頓柯特斯】梯形公式辛甫生(Simpson)公式柯特斯(Cotes)公式一階【2次代數(shù)精度】令f(x)=x2二階【3次代數(shù)精度】令f(x)=x4四階【5次代數(shù)精度】4，復(fù)化求積公式1、 定義：為了提高精度通?？砂逊e分區(qū)間分成若干子區(qū)間，再在每個子區(qū)間上用低階求積公式。這種方法稱為復(fù)化求積法。 復(fù)化求積法就是先用低階的牛頓柯特斯公式求得每個子區(qū)間xk, xk+1上的積分 Ik，然后再求和，用 作為所求積分I的近似值。即復(fù)化梯形公式復(fù)化辛甫生公式復(fù)

14、化柯特斯公式 復(fù)化辛甫生公式精度優(yōu)于復(fù)化梯形公式5，高斯求積公式1、 定義：機(jī)械求積公式含有2n+2個待定參數(shù)：若適當(dāng)選擇這些參數(shù)使求積公式具有2n+1次代數(shù)精度，則這類公式稱為高斯公式。中矩形公式是2、 高斯點(diǎn)定義：高斯公式的求積節(jié)點(diǎn)稱為高斯點(diǎn)。3、 求一點(diǎn)的高斯公式 設(shè)一點(diǎn)高斯公式為則其代數(shù)精度應(yīng)為4、 求二點(diǎn)的高斯公式再設(shè)兩點(diǎn)高斯公式為代數(shù)精度應(yīng)為5、 高斯點(diǎn)的性質(zhì)：定理：對于插值型求積公式(4.1)，其節(jié)點(diǎn)是高斯點(diǎn)的充要條件是以這些點(diǎn)為零點(diǎn)的多項式與任意次數(shù)不超過n的多項式P(x)均正交，即【證明看習(xí)題】6、 高斯勒讓得公式 特別地，取a, b=-1, 1，其上高斯公式為：下面求對應(yīng)的

15、高斯點(diǎn)。 對于任意求積區(qū)間a, b如何求？作變換可以化到區(qū)間-1，1上，這時7、 帶權(quán)的高斯公式1、定義：求積公式若該公式具有2n+1次代數(shù)精度，則稱這類公式為帶權(quán)的高斯公式。上述(x)0是權(quán)函數(shù)。2、定理：是高斯點(diǎn)的充要條件是是區(qū)間a, b上關(guān)于(x)的正交多項式。3、特別：若a, b = -1，1，權(quán)函數(shù)是所建立的高斯公式為【切比雪夫高斯公式】【xk是切比雪夫多項式的零點(diǎn)】第四章 解線性方程組1、分類【一般形式】【矩陣形式】 系數(shù)矩陣為低階稠密矩陣（階數(shù)大約不超過150）【直接法】（經(jīng)過有限步算術(shù)運(yùn)算，可求得方程組的精確解的方法，一般用于解系數(shù)矩陣為低階稠密矩陣）系數(shù)矩陣為大型稀疏矩陣（階

16、數(shù)高且零元素較多）【迭代法】（用某種極限過程去逐步逼近精確解的方法，一般用于解系數(shù)矩陣為大型稀疏矩陣）2、范數(shù)向量范數(shù)矩陣范數(shù)類型在Rn上的向量x =(x1, xn)TRn在Rn×n上的矩陣A=(aij),定義設(shè)對任意向量 xRn，按一定的規(guī)則有一實(shí)數(shù)與之對應(yīng)，記為x，若x滿足則稱x為向量的范數(shù)設(shè)對任意矩陣 ARn×n，按一定的規(guī)則有一實(shí)數(shù)與之對應(yīng)，記為A，若A滿足則稱A為矩陣的范數(shù) 稱為范數(shù)或最大范數(shù)【絕對值最大的元素】 稱為1范數(shù) 稱為2范數(shù) 稱為p范數(shù)【所有值絕對值的P次方求和，再開P次方】 稱為范數(shù)或行范數(shù)【所有元素絕對值之和最大的一行】 稱為1范數(shù)或列范數(shù)【所有元

17、素絕對值之和最大的一列】 稱為2范數(shù)【ATA的最大特征值開平方】 稱為Frobennius范數(shù)【所有元素平方和開平方】性質(zhì)定義：如果Rn中有兩個范數(shù) |x|s 與 |x|t ，存在常數(shù)m, M>0，使對任意n維向量x有則稱這兩個范數(shù)等價.性質(zhì)：對兩種等價范數(shù)而言，某向量序列在其中一種范數(shù)意義下收斂時，則在另一種范數(shù)意義下也收斂。定理：Rn上的任意兩個范數(shù)等價?！咀ⅲ航窈笱芯肯蛄啃蛄械氖諗啃詴r，可在任何一種范數(shù)意義下研究。】3、“病態(tài)”方程組1、定義：當(dāng)一個方程組，由于系數(shù)矩陣 A 或右端常數(shù)項 b 的微小變化，引起方程組Ax=b解的巨大變化，則稱此方程組為“病態(tài)”方程組，矩陣A稱為“病態(tài)

18、”矩陣，否則稱方程組為“良態(tài)”方程 組，A為“良態(tài)”矩陣.2、如何劃分“病態(tài)”的程度：條件數(shù)：設(shè)A為非奇異陣，稱cond(A)v=|A-1|v|A|v (v =1, 2, ) 為矩陣A的條件數(shù)。 【b】 【A】則系數(shù)矩陣A的條件數(shù)刻劃了方程組的“病態(tài)”程度。條件數(shù)愈大，方程組的“病態(tài)”程度愈大，也就愈難得到方程組的比較準(zhǔn)確的解；當(dāng)矩陣A的條件數(shù)相對地小，則方程組是“良態(tài)”的。4、 線性方程組解法向量序列的收斂性矩陣序列的收斂性定義1設(shè) x(k) 為Rn中的向量序列，xRn，如果其中|.|為向量范數(shù)，則稱序列 x(n)收斂于 x，記為 設(shè) A(k) 為 n 階方陣序列，A為n階方陣，如果其中|.

19、|為矩陣范數(shù)，則稱序列 A(n)收斂于A，記為 定理1Rn中的向量序列 x(k)收斂于Rn中的向量 x 當(dāng)且僅當(dāng)設(shè) A(k) = (aij) (k=1, 2, )，A = (aij)均為 n 階方陣，則矩陣序列A(n)收斂于矩陣A的充要條件為直接消去法高斯直接消去法基本思想：用逐次消去未知數(shù)的方法把原來方程組AX=b化為與其等價的三角形方程組，而求解三角形方程組就容易了！高斯消去法的特點(diǎn)：消元和回代不同步！使用高斯消去法的條件：使用高斯消去法要求在每步消元時， 定理：約化的主元素 (i=1,2,n) 的充要條件是矩陣A的順序主子式 定理6：如果 n 階矩陣A的所有順序主子式均不為零，則可通過高

20、斯消去法（不進(jìn)行交換兩行的初等變換），將方程組約化為三角形方程組。定理6：如果A為 n 階非奇異矩陣，則可通過高斯消去法（及交換兩行的初等變換）將方程組 Ax=b 化為三角形方程組。推論：如果A的順序主子式不等于0，則主元素法在采用高斯消去法解方程組時，小主元可能產(chǎn)生麻煩，故應(yīng)避免采用絕對值小的主元素。對一般矩陣，最好每一步選取系數(shù)矩陣（或消元后的低階矩陣）中絕對值最大的元素作為主元素，以使高斯消去法具有較好的數(shù)值穩(wěn)定性！列主元素法：選主元時僅考慮按列選取，然后換行使之變到主元位置上，再進(jìn)行消元計算。列主元消去法的特點(diǎn)：（1）能夠得到較高精度要求的 解 ；（2）計算量大大減少完全主元素法：其中

21、y1,y2,yn為未知數(shù)x1,x2,xn調(diào)換后的次序?！镜谝徊剑菏紫仍贏中選取絕對值最大的元素作為主元素；然后交換到第一行、第一列的位置；再進(jìn)行第一次消元，】完全主元素消去法的缺點(diǎn)：在選主元素時要花費(fèi)較多機(jī)器時間。時時紀(jì)錄x順序的變化情況高斯約當(dāng)消去法高斯約當(dāng)消去法定義：則同時消去對角線上方和下方的元素。高斯約當(dāng)消去法的特點(diǎn)：(1) 消元和回代同時進(jìn)行；(2) 乘除法的次數(shù)要比高斯消去法大，所以通常用于同時求解系數(shù)矩陣相同的多個方程組或求逆矩陣。直接三角法直接三角分解法定理: (矩陣的LU分解)設(shè) A 為 n 階矩陣，如果 A 的順序主子式( i = 1,2,n-1)， 則 A 可分解為一個單

22、位下三角矩陣 L 和一個上三角矩陣 U 的乘積，且這種分解是唯一的。注：若A 實(shí)現(xiàn)了LU分解，則Ax = b (LU)x=b Ly = b Ux = y單位下三角陣 上三角陣 解得解得平方根法 A=LDLTA=LLT平方根法適用于系數(shù)矩陣為對稱正定陣的方程組的求解。定理1 (對稱陣的三角分解定理)設(shè)A為n階對稱陣，且A的所有順序主子式均不為零，則A可唯一分解為 A=LDLT其中L為單位下三角陣，D為對角陣.定理2 (對稱正定陣的三角分解定理)設(shè)A為n階對稱陣，且A的所有順序主子式均大于零，則存在一個非奇異下三角陣 L 使 A=LLT，當(dāng)限定L的對角元素為正時，這種分解是唯一的。Cholesky

23、分解追趕法A=LU追趕法適用于系數(shù)矩陣為三對角陣的方程組的求解。利用系數(shù)矩陣的特點(diǎn)，可以將A分解為兩個三角陣的乘積，A=LU，其中L為下三角矩陣，U為單位上三角矩陣。 迭代法雅克比迭代法一般形式矩陣形式將方程組記為 Ax = b其中A非奇異且aii 0 (I=1, 2, , n).將A分裂為 A = D 其中高斯塞德爾將方程組記為 Ax = b其中A非奇異且aii 0 (I=1, 2, , n).將A分裂為 A = D 其中 超松弛迭x(k+1) = x(k) + x <1時，稱為低松弛； =1時，是G-S法； >1時，稱為超松弛法，簡稱SOR法用分解式 A = D，則可寫為注：(

24、1) 松弛法是G-S法的一種加速方法；(2) 具有計算公式簡單，程序設(shè)計容易；(3) 但需要選擇較好的加速因子。5、 迭代法斂散性判斷方法預(yù)備定義定義1：稱迭代公式中的矩陣 B 為迭代矩陣.定義2：設(shè)A為n階方陣，i (i = 1,n)為A的特征值，稱特征值模的最大值為矩陣A的譜半徑，記為 定義2：稱為矩陣A的譜.定義3：Ak = AAA 的譜為 ( k = 1, 2, )定義3：Ak = AAA 的譜半徑為已知定理定理1：設(shè)A為任意n階方陣，|.|為任意由向量:范數(shù)誘導(dǎo)出的矩陣的范數(shù)，則定理2：設(shè)A為n階方陣，則對任意正數(shù)，存在一種矩陣范數(shù)|.|，使得定理3：設(shè)A為n階方陣，則的充要條件為輔

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

26、2。推論：若迭代矩陣滿足 |M|<1，則迭代公式產(chǎn)生的向量序列x(k)收斂。 定理：對任意初始向量 x(0)和右端項g，由迭代格式x(k+1) = Mx(k) + g產(chǎn)生的向量序列收斂的充要條件為推論：松弛法收斂的必要條件是 0<<2值得注意的是：改變方程組中方程的順序，即將系數(shù)矩陣作行交換，會改變迭代法的收斂性。第五章 解非線性方程組1、定義求 f (x) = 0 的根：f(x)為非線性函數(shù)或高次代數(shù)方程，若有數(shù)x*使f(x*) = 0成立，則稱x*為方程f(x) = 0的根(零點(diǎn))。若f(x)可分解為當(dāng)m = 1，稱x*是單根；當(dāng)m > 1，稱x*是m重根.2、求根

27、的兩個步驟(1)確定根的初始近似值(稱之為初始近似根) ，一般為一個包含根的區(qū)間，稱為“有根區(qū)間”【逐步掃描法：原理：設(shè)f(x)在a, b連續(xù)，且f(a) f(b)<0。則由連續(xù)函數(shù)的性質(zhì)知f(x)=0在(a, b)內(nèi)至少有一個根。若f(x)在a, b上單調(diào)，則f(x)=0在(a, b)上有且僅有一個根?！?2)根的精確化。根據(jù)根的初始近似值按某種方法逐步精確化，直至滿足預(yù)先要求的精度為止。【二分法簡單迭代法牛頓迭代法弦截法】2、分類二分法原理：若 f ÎCa, b，且 f (a) · f (b) < 0，則 f 在 (a, b) 上必有一根 x*。實(shí)施：將方程

28、根的區(qū)間平分為兩個小區(qū)間，然后判斷根在哪個小區(qū)間，舍去無根的區(qū)間，而把有根區(qū)間再一分為二，再判斷根屬于哪個更小的區(qū)間，如此周而復(fù)始，直到求出滿足精度要求的近似根。停止： 或 誤差分析：對于給定的精度 e ,可估計二分法所需的步數(shù) k優(yōu)點(diǎn)：簡單; 對f (x) 要求不高(只要連續(xù)即可) .缺點(diǎn)：無法求復(fù)根及偶重根 收斂慢 簡單迭代法基本思想：f(x) = 0【同解變形】x = g(x)【構(gòu)造公式】xk+1 = g(xk)【給初值x0 ；若xkx*且g(x)連續(xù)】x*就是f(x)=0的根區(qū)間收斂：設(shè)方程 x = g(x)有根x*, g(x)可微，若( I ) 當(dāng) xÎa, b 時， g(

29、x)Îa, b；( II ) $ 0 £ L < 1 使得 | g(x) | £ L < 1 對 " xÎa, b 成立。則任取 x0Îa, b，由 xk+1 = g(xk) 得到的序列收斂于g(x) 在a, b上的唯一不動點(diǎn)。注1：定理中的L<1非常重要，否則不能保證收斂，且L越小，收斂越快。注2：為恰當(dāng)估計 ，可以把有根區(qū)間取得適當(dāng)小。補(bǔ)充：1.迭代是否收斂除了依賴于迭代函數(shù)外，還依賴于有根區(qū)間。2設(shè)方程x=g(x)在區(qū)間a,b內(nèi)有根，若總有,則迭代公式對任意a,b上的初值均發(fā)散。局部收斂：定義：設(shè)x*是g(x)

30、的不動點(diǎn)，若存在 x* 的某d 鄰域 Bd = x | | x - x* | £ d ，對 迭代產(chǎn)生的序列且收斂到x*，則稱局部收斂.定理：設(shè)x*是g(x)的不動點(diǎn)，若g(x)在 x* 的某 鄰域連續(xù)，且有| g(x*) | < 1，則迭代法局部收斂。收斂速度：迭代法的收斂階定義：設(shè)迭代 xk+1 = g(xk) 收斂到g(x) 的不動點(diǎn) x*。設(shè) ek = xk - x*，若則稱該迭代為p 階收斂，其中 C 稱為漸進(jìn)誤差常數(shù)。特別地： p = 1時：線性收斂， p >1時：超線性收斂， p = 2時：平方收斂 定理：設(shè) x* 為x = g(x) 的不動點(diǎn)，若 ，p &#

31、179; 2；且，則 xk+1 = g(xk) 在內(nèi) p 階收斂。牛頓迭代法原理：將非線性方程線性化泰勒展開局部收斂性設(shè) f ÎC2a, b，若 x* 為 f (x) 在a, b上的根，且 f (x*) ¹ 0，則存在 x* 的鄰域使得任取初值Newtons Method產(chǎn)生的序列 xk 收斂到x*，且滿足有只要就有 p ³ 2。重根是線性收斂的。注： (1) 牛頓法要求初值充分接近根以保證局部收斂性。(2)牛頓迭代法的主要優(yōu)點(diǎn)是收斂較快，是平方收斂的缺點(diǎn)是公式中需要求 f(x) 的導(dǎo)數(shù)。若 f(x)比較復(fù)雜，則使用牛頓公式就大為不便。弦截法針對問題：重根問題問題

32、1: 若，Newtons Method 是否仍收斂？K1: 有局部收斂性，但重數(shù) n 越高，收斂越慢。問題2: 如何加速重根的收斂？K2: 將求 f 的重根轉(zhuǎn)化為求另一函數(shù)的單根。令則 f 的重根 = m 的單根。下山法：原理：若由 xk 得到的 xk+1 不能使 | f | 減小，則在 xk 和 xk+1 之間找一個更好的點(diǎn)，使得 l = 1 時就是Newtons Method 公式。當(dāng) l = 1 代入效果不好時，將 l 減半計算。 弦截法Newtons Method 一步要計算 f 和 f ，相當(dāng)于2個函數(shù)值，比較費(fèi)時。現(xiàn)用 f 的值近似 f ，可少算一個函數(shù)值。需要 2 個初值 x0 和 x1切線斜率 » 割線斜率弦截法與牛頓法相比較相同之處：都是線性化方法不同之處：牛頓法在計算xk+1時只用到前一步的值xk，故這種方法稱為單點(diǎn)迭代法；而弦截法在求xk+1時要用到前兩步的值xk和xk-1，因此