《計算方法》定理公式總結歸納

第一章1.設某量的準確值為x，近似值為x*，則稱e(x*)=x-x*為近似值x*的絕對誤差；|e(x*)|=|x-x*|≤ε,稱ε為x*的絕對誤差限；稱為x*的相對誤差；εr為x*的相對誤差限。2.對數(shù)學問題而言，如果輸入數(shù)據(jù)有微小擾動，引起輸出數(shù)據(jù)（即數(shù)學問題的解）有很大擾動，則稱數(shù)學問題是病態(tài)問題，否則稱為良態(tài)問題。3.4.定義：一個算法如果輸入數(shù)據(jù)有擾動（即有誤差），而計算過程中舍入誤差不增長，則稱此算法是數(shù)值穩(wěn)定的，否則稱此算法為不穩(wěn)定的。（誤差的定性分析法：即研究算法的數(shù)值穩(wěn)定性）5.數(shù)值計算中值得注意的問題：（1）防止相近的兩數(shù)相減(2)防止大數(shù)吃小數(shù)(3)防止接近零的數(shù)做除數(shù)(4)注意計算步驟的簡化,減小運算次數(shù)6.誤差的來源：1、模型誤差2、觀測誤差3、截斷誤差4、舍入誤差實際問題的真解與數(shù)學模型之間有誤差，這種誤差稱為模型誤差(描述誤差)由于測量工具的精度、觀測方法或客觀條件的限制,使數(shù)據(jù)含有測量誤差,這類誤差叫做觀測誤差或數(shù)據(jù)誤差在數(shù)值求解數(shù)學問題時，常常用有限過程逼近無限過程，用能計算的問題代替不能計算的問題。這種精確公式用近似公式代替時,所產(chǎn)生的誤差叫截斷誤差。由于計算機字長有限，一般實數(shù)不能精確存儲，于是產(chǎn)生舍入誤差。第二章6.如果在區(qū)間[a,b]內方程f(x)=0只有一個根，稱[a,b]為隔根區(qū)間。求隔根區(qū)間有兩種方法有描圖法和逐步搜索法。7.二分法就是將方程的有根區(qū)間對分，然后再選擇比原來區(qū)間縮小一半的有根區(qū)間，如此繼續(xù)下去，直到得到滿足精度要求的根為止的一種簡單的區(qū)間方法。定理2.1：f(x)在[a,b]內連續(xù)，α是方程f(x)在隔根區(qū)間[a,b]內的根，則由二分法產(chǎn)生的數(shù)列{xn}收斂于方程的根α,且有誤差估計式二分法控制誤差ε常用的方法有(1)先計算對分次數(shù)再對分。由計算得得到滿足誤差要求的最少對分次數(shù)。(2)事后誤差估計法,先對分再判斷所得中點是否滿足誤差要求(3)由于故可用來判斷誤差。8.迭代法的求解步驟(1)建立迭代公式。由公式f(x)=0出發(fā)將其分解為等價形式x=φ(x),式中φ(x)叫做方程的迭代函數(shù).(2)進行迭代計算。由初值x0出發(fā)，按迭代函數(shù)進行計算稱為迭代公式。數(shù)列{xn},稱為迭代序列。該過程稱為迭代過程.9若從任何可取的初值出發(fā)都能保證收斂，則稱它為大范圍收斂。如若為了保證收斂性必須選取初值充分接近于所要求的根，則稱它為局部收斂。定理2.2（收斂定理）：設方程x=φ(x)，如果設方程x=φ(x)，如果(1)迭代函數(shù)φ(x)在區(qū)間[a,b]可導；(2)當x?[a,b]時，φ(x)?[a,b]；(3)對于任意的x?[a,b]，有。則有=1\*GB3①方程x=φ(x)在區(qū)間[a,b]上有唯一的根α；=2\*GB3②對于任意的初值x0?[a,b]，由迭代公式產(chǎn)生的數(shù)列{xn}收斂于方程的根α。=3\*GB3③=4\*GB3④誤差估計定理2.3（迭代法的局部收斂定理）：設α是方程x=φ(x)的根，如果(1)迭代函數(shù)φ(x)在α的鄰域可導；(2)在α的某個鄰域S={x:|x-α|≤δ},對于任意的x?S有則對于任意的初值x0?S，迭代公式xn+1=φ(xn)產(chǎn)生的數(shù)列{xn}，收斂于方程的根α。（這時稱α的S領域具有局部收斂性。）收斂法控制誤差ε的方法有：(1)先計算滿足誤差要求的迭代次數(shù)n，再迭代。由可得(2)事后誤差估計法。由于因而可用|xn-xn-1|≤ε來控制迭代過程。10.迭代-加速公式：埃特金加速公式:定理2.4：如果由迭代公式xn+1=φ(xn)產(chǎn)生的數(shù)列{xn}滿足(1)收斂于根α；(2)則由埃特金加速公式產(chǎn)生的數(shù)列{xn}比數(shù)列較快地收斂于根α，即11.牛頓迭代公式：定理2.5（牛頓迭代法的局部收斂定理）設α是方程f(x)=0的根，如果(1)函數(shù)f(x)=0在α的鄰域有連續(xù)的二階導數(shù)(2)在α的鄰域f’(x)≠0則存在α的某個鄰域，對于任意的初始值，由牛頓迭代公式產(chǎn)生的數(shù)列收斂于根α。定理2.6（牛頓迭代法收斂定理）設α是方程f(x)=0在隔根區(qū)間[a,b]內的根，且滿足,連續(xù)且不變號；(2)選取初始值使。則由牛頓迭代公式產(chǎn)生的數(shù)列收斂于根α。12.定義:設數(shù)列收斂于α,令誤差,如果存在某個實數(shù)及正常數(shù)C，使則稱數(shù)列p階收斂，也稱相應的迭代法為p階方法。當且時，稱數(shù)列為線性收斂.當p=2時，稱數(shù)列平方收斂（或二階收斂）.當p>1時，稱數(shù)列為超線性收斂。定理2.7:（1）在定理2.3的條件下，且在根α的某個鄰域內有，則迭代法是線性收斂的。（2）在定理2.6的條件下，牛頓迭代法是平方收斂的。13.單點弦截法迭代公式:；雙點弦截法迭代公式：定理2.8:設α是方程f(x)=0在隔根區(qū)間[a,b]內的根，且滿足(1)連續(xù)且不變號；(2)選取初始值，使。選定a，b中的一個，則x1為另一個。則有單點弦截迭代法公式產(chǎn)生的數(shù)列收斂于根α。（單點弦截法的收斂階為1）。定理2.9:設方程f(x)=0，如果(1)f(x)在根α的某個鄰域具有連續(xù)的二階導數(shù)，且f’(x)≠0;(2)任取x0,x1屬于該鄰域。則由雙點弦截迭代法公式產(chǎn)生的數(shù)列收斂于根α。（雙點弦截法是超線性收斂，收斂階為(1+5第三章14.高斯消元法的求解過程可大致分為兩個階段:(1)把原方程組化為上三角形方程組,稱之為“消元”過程;(2)用逆次序逐一求出上三角方程組(原方程組的等價方程組)的解,稱之為“回代”過程.15.定義3.1:設A為n階矩陣，L為n階下三角陣，U為n階上三角陣。如果A=LU，則說明矩陣A實行了三角分解或LU分解。16.定義3.2:如果L為單位下三角陣，U為上三角陣，則稱該三角分解為杜里特（Doolittle）分解；如果L為下三角陣，U為單位上三角陣，則稱A=LU為克勞特（Crout）分解。定理3.1：n階（n≥2）矩陣A有唯一杜里特分解（或克勞特分解）的充要條件是A的前n-1個順序主子式都不為零。定理3.2:設A為對稱正定矩陣，則有非奇異下三角陣L，使A=LLT;當限定L的對角元全為正時，這種分解是唯一的。17.直接三角分解法公式（Doolittle）：18.平方根法求解公式：19.追趕法的分解形式及公式：20.定義3.3設迭代矩陣B為n階矩陣，為矩陣B的特征值，稱為矩陣B的譜半徑。定理3.3：設簡單迭代公式為對于任意的初始向量和g，該簡單迭代法都收斂的充要條件是：定理3.4：設簡單迭代公式為如果或，則簡單迭代法對任意初始向量和g都收斂。21.定義3.4設，如果矩陣A滿足條件或者即A的每一行（列）對角線上的元素的絕對值都嚴格大于同行（列）其它元素絕對值之和，則稱A為嚴格對角占優(yōu)矩陣。定理3.5：如果線性方程組的系數(shù)矩陣A是嚴格對角占優(yōu)矩陣，則雅克比迭代法對任意的初始向量和g都收斂。定理3.6：設有賽德爾迭代公式記矩陣。如果或，則簡單迭代法對任意初始向量和g都收斂。22.定義：設V是數(shù)域F上的線性空間，，若存在唯一實數(shù)與其對應，且滿足以下三條公理，(1)正定性：(2)齊次性：(3)三角不等式：則實數(shù)稱為向量x的范數(shù)。把定義了范數(shù)的線性空間稱為賦范線性空間。23.（1）向量的1-范數(shù)：;(2)向量的2-范數(shù)：;(3)向量的∞范數(shù)：。均可表示為p范數(shù)的形式：。（定理：有限維空間中的范數(shù)等價。）24.定義：設向量序列，若存在，使得稱向量序列收斂于25.定義：基本迭代法產(chǎn)生的迭代序列，如果對任取初始向量都有，則稱此迭代法是收斂的，否則是發(fā)散的。（在Rn中，點列的收斂等價于每個分量的收斂。即。）26.迭代終止標準：(1)絕對誤差標準。給出容許誤差界ε，當時,p=1,2,∞,終止迭代，解取為。常取p=∞，(2)相對誤差標準。給出容許誤差界ε，(3)給出最大迭代次數(shù)，當?shù)K止，給出失敗信息。特征值上界定理：設A∈Rn×n,對于定理：如果迭代格式的迭代矩陣B滿足，則有以下的誤差估計式：，27.估計迭代次數(shù)的方法：28.Jacobi迭代的矩陣格式：；分量形式：29.Gauss-Seidel迭代的矩陣形式：；分量形式：30.收斂準則：一般收斂原則:，實用準則：由A來直接判斷（充分準則）{準則1：A嚴格對角占優(yōu)Jacobi迭代法，Gauss-Seidel迭代法收斂；準則2：Jacobi迭代法，Gauss-Seidel迭代法收斂。準則3：A對稱正定Gauss-Seidel迭代法收斂；準則4：若A對稱正定，則2D-A是對稱正定Jacobi迭代法收斂。}注意：對一個任意給定的系數(shù)矩陣1.Jacobi迭代法和Gaussss-Seidel迭代法可能同時收斂，或同時不收斂，或者一個收斂而另一個不收斂。2在都收斂的情況下，其收斂的速度也不一定是哪一種一定快。3.A對稱正定，Gauss-Seidel一定收斂，但2D-A不一定也是對稱正定，所以Jacobi法未必收斂。31.SOR迭代的矩陣形式分量形式：w=1，為Gauss-seidel迭代法；w>1，超松弛迭代法；w<1低松弛迭代法。32.SOR迭代收斂準則{一般準則：，實用準則：用w加速，收斂性于w直接有關。定理：SOR方法收斂的必要條件是0<w<2。}33.SOR法收斂性的結論：(1)SOR方法收斂的必要條件是0<w<2;(2)若系數(shù)陣A對稱正定，則當0<w<2時，SOR方法收斂;(3)若系數(shù)陣A嚴格對角占優(yōu)，則當0<w≤時，SOR方法收斂。第五章定理5.1：在n+1個互異節(jié)點處滿足插值條件的次數(shù)不高于n的多項式存在且唯一。33.定義5.1：若n次多項式在n+1個插值節(jié)點上滿足插值條件：則稱這n+1個n次多項式為插值節(jié)點上的n次插值基函數(shù)。34.插值基函數(shù)的性質：性質一：；性質二：是由插值節(jié)點唯一確定的n次函數(shù)；性質三：插值基函數(shù)與插值節(jié)點個數(shù)相同。35．Language插值：定理5.2：若f(n)(x)在區(qū)間[a,b]上連續(xù)，f(n+1)(x)在(a,b)存在，Ln(x)為在節(jié)點a￡x0<x1<……<xn￡b上滿足插值條件的插值多項式，則對于任意的x?(a,b),其插值余項為其中。36.定義5.2：給定函數(shù)f(x)在互異節(jié)點x0<x1<……<xn處的函數(shù)值分別f(x0),f(x1),……,f(xn),稱為在處的一階差商。稱為在處的二階差商。一般地，稱為在上的k階差商。即的k-1階差商的差商稱為k階差商（差商也常稱為均差）。37.差商的性質：1.2.差商與插值節(jié)點的排列順序無關，即，一般地，在k階差商中，任意調換節(jié)點的次序，其值不變。3.差商與導數(shù)的關系：38.差商表：39．牛頓插值：40.定義5.3：設，為等距節(jié)點上的函數(shù)值，其中稱為步長，則稱為在處以h為步長的一階向前差分。稱為在處以h為步長的二階向前差分。一般地，稱為在處以h為步長的m階向前差分。41.差分的性質：性質1：各階差分可用函數(shù)值線性表示，其計算公式為：其中：；性質2：差分與差商滿足下述關系；性質3:差分與導數(shù)滿足關系：。42.等距節(jié)點插值：43.埃爾米特插值：定理5.3：若在上存在2n+2階導數(shù)，則其插值余項，式中44.定義5.4：設在區(qū)間上取n+1個節(jié)點若函數(shù)S(x)滿足(1)在整個區(qū)間上具有二階連續(xù)導數(shù)；(2)在每個小區(qū)間上是x的三次多項式；(3)。則稱為的三次樣條插值函數(shù)。45.用節(jié)點處一階導數(shù)表示的三次樣條插值函數(shù)的構造步驟：用公式計算出。由公式：，以及第一類邊界條件：或第二類邊界條件：計算出。計算公式如下：（第一類邊界條件）或（第二類邊界條件）最后將代入，。46.用節(jié)點處二階導數(shù)表示的三次樣條插值函數(shù)的構造步驟：用公式計算出。由公式：以及第一類邊界條件：或第二類邊界條件：計算出。計算公式如下：（第一類邊界條件）或（第二類邊界條件）最后將代入，。第六章47.定義：當線性方程組的系數(shù)矩陣的秩與增廣矩陣的秩不等時，方程組無解，這時次方程組稱為矛盾方程組。稱為偏差。定理6.1：設n元實函數(shù)在點的某個鄰域內連續(xù)，且有一階二階連續(xù)的偏導數(shù)，如果(1)(2)矩陣是正（負）定矩陣，則是n元實函數(shù)的極?。ù螅┲?。定理6.2：設非齊次線性方程組的系數(shù)矩陣，若，則：(1)矩陣是對稱正定矩陣；(2)n階線性方程組有唯一的解。定理6.3：設矛盾方程組的系數(shù)矩陣A的秩為n，則二次函數(shù)一定存在最小值。48.定義：線性方程組稱為正則方程組。定理6.4：設互異，且，則正則方程組有唯一的解。49.通常用均方差與最大偏差來判斷擬合曲線的優(yōu)劣。第七章50.定義：在積分區(qū)間上取一系列的點，設，用被積函數(shù)在這些點上的函數(shù)值的線性組合來作為積分的近似值：，此式稱為數(shù)值求積公式，其中的個點稱為節(jié)點，稱為求積系數(shù)。稱為求積公式的截斷誤差。51．牛頓科-特斯求積公式：，稱為科特斯系數(shù)。稱為牛頓-科特斯公式的截斷誤差。52.梯形公式（n=1）：53.辛浦生公式（n=2）：54.科特斯公式（n=4）：55.科特斯系數(shù)表：k=0K=1K=2K=3K=4n=11/21/2n=21/64/61/6n=31/83/83/81/8n=47/9032/9012/9032/907/9056.定義7.1：如果求積公式對于任何不高于m次的代數(shù)多項式都準確成立（即），而對某個m+1次的代數(shù)多項式不準確成立（即）,則稱該求積公式具有m次代數(shù)精確度，簡稱代數(shù)精度。定理：n為偶數(shù)的牛頓-科特斯求積公式具有n+1次代數(shù)精度，n為奇數(shù)的牛頓-科特斯求積公式具有n次代數(shù)精度。定理7.1：設在區(qū)間上具有連續(xù)的二階導數(shù)，則梯形公式的截斷誤差為：。定理7.2:設在區(qū)間上具有連續(xù)的四階導數(shù)，則辛浦生公式的截斷誤差為：。57.科特斯公式的截斷誤差為：58.待定系數(shù)法：給定n+1個節(jié)點，如果要構造至少具有n次代數(shù)精度的求積公式，只要對于都準確成立，則可得到含求積系數(shù)的代數(shù)方程組：方程組的系數(shù)行列式是范德蒙行列式，其值不為零，因而可求得唯一解。59.復化求積公式的基本思想：把積分區(qū)間分成若干小區(qū)間，在每個小區(qū)間上采用次數(shù)不高的插值公式，如梯形公式或拋物線公式，構造出相應的求積公式，然后再把它們加起來得到整個區(qū)間上的求積公式。復化求積公式克服了高次Newton-Cotes公式計算不穩(wěn)定的問題，其運算簡單且易于在計算機上實現(xiàn)。常用的復化求積公式是復化梯形公式和復化拋物線公式。60.復化梯形公式：61.復化辛浦生公式：式中62.復化科特斯公式：式中定理7.3：設在區(qū)間上具有連續(xù)的二階導數(shù)，則復化梯形公式的截斷誤差為：。（若，則有誤差估計式：。）63.復化辛浦生公式的截斷誤差：，若則有誤差估計式：。64.復化柯特斯公式的截斷誤差：，若，則有誤差估計式：。65.區(qū)間逐次半分求積法：(1)對于梯形公式：假定在區(qū)間上變化不大，則有。遞推公式為：(2)對于辛浦生公式，假定在區(qū)間上變化不大，則有。(3)對于科特斯公式，假定在區(qū)間變化不大，則有66.外推法的幾個公式：，67.龍貝格求積公式：68.結論：由梯形序列外推得到辛浦生序列、由辛浦生序列外推得到科特斯序列以及由科特斯序列外推得到龍貝格序列，每次外推都可以使誤差階提高二階。69.龍貝格求積算法的計算步驟：(1)算出，，根據(jù)公式計算；(2)將分半，算出后，根據(jù)公式計算，再根據(jù)公式計算；(3)再將區(qū)間對分，算出以及，并根據(jù)和算出，再由公式計算；(4)將區(qū)間再次分半，計算，并由公式計算；(5)將區(qū)間再次分半，類似上述過程計算。重復上述過程可計算得到一直算到龍貝格序列中前后兩項之差的絕對值不超過給定的誤差限為止。70.定義7.2：把具有個節(jié)點的具有次代數(shù)精確度的插值型求積公式稱為高斯型求積公式，節(jié)點稱為高斯點，稱為高斯系數(shù)。定理7.4：對于插值型求積公式，其節(jié)點為高斯點的充要條件是以這些點為零點的多項式與任意的次數(shù)不超過n的多項式在區(qū)間上正交，即。71.n次勒讓德多項式：其性質有：(1)次勒讓德多項式與任意的次數(shù)不超過次的多項式在區(qū)間上正交；(2)次勒讓德多項式的個零點都在區(qū)間內。72.結論：當積分區(qū)間為時，插值型求積公式的代數(shù)精確度為的充要條件是與任意次數(shù)不超過的多項式在區(qū)間上正交。73.高斯-勒讓德求積公式：（為次勒讓德多項式的零點。求積系數(shù)可用待定系數(shù)法或按求出：）74.對于積分，可通過變量代換將積分轉化為上的積分，，然后用高斯