數(shù)值分析綜述-《數(shù)值分析與算法》徐士良(共3頁(yè))

1、第2章 矩陣與線性代數(shù)方程組一般的線性代數(shù)方程組，A非奇異可根據(jù)Cramer法則求解方程唯一解但是它的計(jì)算量很大。高斯消元法的算法時(shí)間復(fù)雜度是O(n3)，可以解一系列的線性方程；所占數(shù)據(jù)空間符合原地工作的原則。但是算法對(duì)數(shù)值計(jì)算不穩(wěn)定（當(dāng)分母為0或很小時(shí)）?？梢杂迷谟?jì)算機(jī)中來(lái)解決數(shù)千條及未知數(shù)。不過(guò)，如果有過(guò)百萬(wàn)條時(shí)，這個(gè)算法會(huì)十分費(fèi)時(shí)。解決高斯法中的不穩(wěn)定性，在每次歸一化前增加選主元（列選主元、全選主元）過(guò)程。但是列選主元法仍不穩(wěn)定，不適求解大規(guī)模線性代數(shù)方程組。全選主元的高斯消去法，則在復(fù)雜度降低的同時(shí)能夠避免舍入誤差，保證數(shù)值穩(wěn)定性。高斯-約當(dāng)消去法算法產(chǎn)生出來(lái)的是一個(gè)，而不是高斯消元法

2、中的。相比起高斯消元法，此算法的效率比較低，卻可把方程組的解用矩陣一次過(guò)表示出來(lái)。線性代數(shù)方程組的迭代解法簡(jiǎn)單迭代法：迭代格式發(fā)散但迭代值序列不一定發(fā)散，但收斂格式收斂，迭代值序列收斂于方程組的準(zhǔn)確解與選取迭代初值無(wú)關(guān)。雅可比迭代法: 計(jì)算公式簡(jiǎn)單，且計(jì)算過(guò)程中原始矩陣A始終不變，比較容易并行計(jì)算。但是收斂速度較慢，而且占據(jù)的存儲(chǔ)空間較大，所以工程中一般不直接用雅克比迭代法，而用其改進(jìn)方法。高斯-賽德?tīng)柕ǎ狠^上面的迭代復(fù)雜，但是矩陣的條件相對(duì)寬松。松弛法： 需要根據(jù)經(jīng)驗(yàn)去調(diào)整， 收斂速度依賴松弛參數(shù)的選擇，收斂條件的要求更寬松。共軛梯度法：是介于與法之間的一個(gè)方法，它僅需利用一階

3、信息，但克服了最速下降法收斂慢的缺點(diǎn)，又避免了牛頓法需要存儲(chǔ)和計(jì)算Hesse并求逆的缺點(diǎn)，在各種優(yōu)化算法中，共軛梯度法是非常重要的一種。其優(yōu)點(diǎn)是所需存儲(chǔ)量小，具有步收斂性，穩(wěn)定性高，而且不需要任何外來(lái)參數(shù)。共軛梯度法不僅是解決大型最有用的方法之一，也是解大型非線性最優(yōu)化最有效的之一。第3章 矩陣特征值乘冪法計(jì)算絕對(duì)值最大的特征值：其收斂速度受限于最大與次大特征值比值絕對(duì)值的大小，實(shí)際應(yīng)用中采用加速技術(shù)。求對(duì)稱特征值的雅克比方法96：每進(jìn)行一次選裝變換錢都需要在飛對(duì)角線的元素中選取絕對(duì)值最大的元素，很費(fèi)時(shí)間，雅克比過(guò)關(guān)法對(duì)此做了改進(jìn)。QR方法求一般實(shí)矩陣的全部特征值98下100下：重復(fù)多次進(jìn)行Q

4、R分解費(fèi)時(shí)，計(jì)算工作量很大。一般先進(jìn)行相似變換然后進(jìn)行QR分解。但是這樣仍然收斂速度慢，一般是線性收斂。實(shí)際應(yīng)用中使用雙重步QR變換將帶原點(diǎn)的QR算法中相鄰兩步合并一步，加速收斂避免復(fù)數(shù)運(yùn)算。第4章 非線性方程與方程組二分法：每次運(yùn)算后，區(qū)間長(zhǎng)度減少一半，是線形收斂。優(yōu)點(diǎn)是簡(jiǎn)單，但是不能計(jì)算復(fù)根和重根。簡(jiǎn)單迭代法：直接的方法從原方程中隱含的求出x，從而確定迭代函數(shù)j(x)，這種迭代法收斂速度較慢，迭代次數(shù)多。埃特金迭代法113中：對(duì)簡(jiǎn)單迭代進(jìn)行改進(jìn)，使在其不滿足收斂條件下迭代過(guò)程也收斂，在其收斂時(shí)加快收斂速度，減少迭代次數(shù)降低時(shí)間復(fù)雜度。牛頓迭代法：其最大優(yōu)點(diǎn)是在方程f(x) = 0的單根附近

5、具有平方收斂，收斂速度快。而且該法還可以用來(lái)求方程的重根、復(fù)根。缺點(diǎn)：初值的選擇會(huì)影響收斂結(jié)果。牛頓下山法：保證函數(shù)值穩(wěn)定下降，且有牛頓法的收斂速度。第5章 代數(shù)插值法Lagrange插值Lagrange插值是n次多項(xiàng)式插值，其成功地用構(gòu)造插值基函數(shù)的 方法解決了求n次多項(xiàng)式插值函數(shù)問(wèn)題?；舅枷雽⒋蟮膎次多項(xiàng)式插值函數(shù)pn(x)改寫成另一種表示方式，再利用插值條件確定其中的待定函數(shù)，從而求出桿值多項(xiàng)式。拉格朗日插值法的公式結(jié)構(gòu)整齊緊湊，在理論分析中十分方便，然而在計(jì)算中，當(dāng)插值點(diǎn)增加或減少一個(gè)時(shí)，所對(duì)應(yīng)的基本多項(xiàng)式就需要全部重新計(jì)算，于是整個(gè)公式都會(huì)變化，非常繁瑣。這時(shí)可以用重心拉格朗日插

6、值法或來(lái)代替。此外，當(dāng)插值點(diǎn)比較多的時(shí)候，拉格朗日插值多項(xiàng)式的次數(shù)可能會(huì)很高，因此具有的特點(diǎn)，也就是說(shuō)盡管在已知的幾個(gè)點(diǎn)取到給定的數(shù)值，但在附近卻會(huì)和“實(shí)際上”的值之間有很大的偏差。這類現(xiàn)象也被稱為，解決的辦法是分段用較低次數(shù)的插值多項(xiàng)式。優(yōu)點(diǎn)：簡(jiǎn)單，缺點(diǎn)：產(chǎn)生一堆數(shù)，不保證穩(wěn)定性Newton插值Newton插值也是n次多項(xiàng)式插值，它提出另一種構(gòu)造插值多項(xiàng)式的方法，與Lagrange插值相比，具有承襲性和易于變動(dòng)節(jié)點(diǎn)的特點(diǎn)。易于使用編程實(shí)現(xiàn)。 基本思想將待求的n次插值多項(xiàng)式Pn（x）改寫為具有承襲性的形式，然后利用插值條件（1）確定Pn（x）的待定系數(shù)，以求出所要的插值函數(shù)。Aitken插值法

7、實(shí)際中常需要精度（139下）要求來(lái)選取插值結(jié)點(diǎn)，埃特金逐步插值解決了此問(wèn)題。優(yōu)點(diǎn)在于可根據(jù)精度的要去逐步提高插值的階，在插值過(guò)程中只需要逐步將兩個(gè)地階的插值結(jié)果進(jìn)行線性組合即可，計(jì)算比較方便。Hermite插值Hermite插值是利用未知函數(shù)f(x)在插值節(jié)點(diǎn)上的函數(shù)值及導(dǎo)數(shù)值來(lái)構(gòu)造插值多項(xiàng)式的,起其提法為:給定n+1個(gè)互異的節(jié)點(diǎn)x0,x1,xn上的函數(shù)值和導(dǎo)數(shù)值不少實(shí)際的問(wèn)題不但要求在節(jié)點(diǎn)上的函數(shù)值相等，而且還要求對(duì)應(yīng)的導(dǎo)數(shù)值也相等,甚至要求高階導(dǎo)數(shù)也相等,滿足這種要求的插值多項(xiàng)式就是埃爾米特插值多項(xiàng)式。樣條插值樣條插值是使用一種名為的特殊進(jìn)行插值的形式。由于樣條插值可以使用低階多項(xiàng)式樣條實(shí)

8、現(xiàn)較小的，這樣就避免了使用高階多項(xiàng)式所出現(xiàn)的，所以樣條插值得到了。它的基本思想（151）：在由兩相鄰結(jié)點(diǎn)所構(gòu)成的每一個(gè)小區(qū)間內(nèi)用低次多項(xiàng)式來(lái)逼近，并且在各結(jié)點(diǎn)的連接處是光滑的（連續(xù)可導(dǎo)）。第6章 函數(shù)逼近與擬合采用最佳一致逼近多項(xiàng)式（181）迭代次數(shù)少，結(jié)果已經(jīng)很優(yōu)了。均方逼近（183、184）：求最佳均方逼近多項(xiàng)式所形成的線性方程組的系數(shù)矩陣是高度病態(tài)的，舍入誤差大，采用廣義多項(xiàng)式就變得簡(jiǎn)單了。一般多項(xiàng)式的基函數(shù)不一定是正交函數(shù)集系，應(yīng)先對(duì)基函數(shù)進(jìn)行正交化，如在最佳均方逼近中采用切比雪夫正交多項(xiàng)式。最小二乘曲線擬合：（185）各觀測(cè)數(shù)據(jù)與擬合曲線的偏差平方和最小，雖然降低了插值點(diǎn)處的準(zhǔn)確性，

9、但是擬合曲線更接近真實(shí)函數(shù)。其應(yīng)用十分廣泛，不僅用于傳統(tǒng)的測(cè)量平差，而且用于最小二乘和最小二乘配置等現(xiàn)代平差理論之中；不僅在測(cè)繪領(lǐng)域中，而且在其他許多科學(xué)和工程技術(shù)領(lǐng)域都已得到廣泛應(yīng)用。第7章 數(shù)值積分與數(shù)值微分梯形公式：會(huì)把圖像當(dāng)作成梯形并估算它的面積。以下就是估算所用的公式如果是一個(gè)（亦即有一個(gè)正值），那么誤差會(huì)是一個(gè)負(fù)數(shù)，也代表梯形公式的估算值高估了真實(shí)數(shù)字。這可以利用一個(gè)幾何圖形代去表達(dá)：梯形不但覆蓋曲線下的面積更超越其范圍。同樣地，如果被積函數(shù)是一個(gè)，梯形公式就會(huì)低估其真實(shí)數(shù)字因?yàn)榍€下部份面積沒(méi)有被計(jì)算在內(nèi)。如果被積函數(shù)中有它的錯(cuò)誤是比較難去估計(jì)。辛普森法則（Simpson'

10、;s rule）是一種方法，是以逼近的方式取代矩形或梯形積分公式，以求得的數(shù)值近似解。其近似值如下：牛頓-柯特斯：假設(shè)已知的值。以點(diǎn)進(jìn)行，求得對(duì)應(yīng)的。對(duì)該次的多項(xiàng)式求積。該積分便可以作為的近似，而由于該拉格朗日多項(xiàng)式的系數(shù)都是常數(shù)（由決定其值），所以積函數(shù)的系數(shù)（即）都是常數(shù)。提高了積分區(qū)間上插值多項(xiàng)式階數(shù)，就提高了求積公式的階數(shù)，有可能提高精度。缺點(diǎn)：對(duì)于次數(shù)較高的多項(xiàng)式而有很大誤差（），不如法。復(fù)化公式：解決多個(gè)點(diǎn)但不穩(wěn)定的問(wèn)題，（198）盡量減小每一個(gè)求積小區(qū)間的長(zhǎng)度。變步長(zhǎng)求積分：（199）合理選擇步長(zhǎng)，可滿足精度要求也不會(huì)引起過(guò)多的誤差積累和過(guò)大的計(jì)算工作量。龍貝格求積法：它是在梯形公式、辛卜生公式和柯特斯公式之間的關(guān)系的基礎(chǔ)上，構(gòu)造出一種加速計(jì)算積分的方法。 作為一種外推算法, 它在不增加計(jì)算量的前提下提高了誤差的精度. 在等距基點(diǎn)的情況下，用計(jì)算機(jī)計(jì)算積分值通常都采用把逐次分半的方法進(jìn)行。這樣，前一次分割得到的函數(shù)值在分半以后仍可被利用,且易于。高斯求積：高斯求積理論中的一個(gè)基本定理斷言：只要把結(jié)點(diǎn)x0,x