數(shù)值計(jì)算方法復(fù)習(xí)提綱

1、數(shù)值計(jì)算方法復(fù)習(xí)提綱第一章 數(shù)值計(jì)算中的誤差分析1了解誤差及其主要來(lái)源，誤差估計(jì)；2了解誤差(絕對(duì)誤差、相對(duì)誤差)和有效數(shù)字的概念及其關(guān)系；3掌握算法及其穩(wěn)定性，設(shè)計(jì)算法遵循的原則。1、 誤差的來(lái)源模型誤差觀測(cè)誤差截?cái)嗾`差舍入誤差2誤差與有效數(shù)字絕對(duì)誤差 E（x）=x-x 絕對(duì)誤差限 相對(duì)誤差 有效數(shù)字若，稱(chēng)有n位有效數(shù)字。有效數(shù)字與誤差關(guān)系（1） m一定時(shí)，有效數(shù)字n越多，絕對(duì)誤差限越??；（2） 有n位有效數(shù)字，則相對(duì)誤差限為。選擇算法應(yīng)遵循的原則1、 選用數(shù)值穩(wěn)定的算法，控制誤差傳播；例 x2、 簡(jiǎn)化計(jì)算步驟，減少運(yùn)算次數(shù)；3、 避免兩個(gè)相近數(shù)相減，和接近零的數(shù)作分母；避免第二章 線(xiàn)性方程

2、組的數(shù)值解法1了解Gauss消元法、主元消元法基本思想及算法；2掌握矩陣的三角分解，并利用三角分解求解方程組；（Doolittle分解；Crout分解；Cholesky分解；追趕法） 3掌握迭代法的基本思想，Jacobi迭代法與Gauss-Seidel迭代法；4掌握向量與矩陣的范數(shù)及其性質(zhì),迭代法的收斂性及其判定 。本章主要解決線(xiàn)性方程組求解問(wèn)題，假設(shè)n行n列線(xiàn)性方程組有唯一解，如何得到其解？ 兩類(lèi)方法，第一是直接解法，得到其精確解；第二是迭代解法，得到其近似解。一、 Gauss消去法1、 順序auss消去法記方程組為：消元過(guò)程：經(jīng)步消元，化為上三角方程組第步若回代過(guò)程：、auss消去法避免回

3、代，消元時(shí)上下同時(shí)消元、auss列主元消去法例 ：說(shuō)明直接消元，出現(xiàn)錯(cuò)誤由順序auss消去法，得；auss列主元消去法原理：每步消元前，選列主元，交換方程。算法：將方程組用增廣矩陣表示。（1）消元過(guò)程：對(duì)k=1,2,n-1,選主元，找 如果，則矩陣A奇異，程序結(jié)束；否則執(zhí)行3。如果，則交換第k行與第行對(duì)應(yīng)的元素位置， 消元，對(duì)i=k+1, ,n,計(jì)算 對(duì)j=L+1, ,n+1,計(jì)算 （2）回代過(guò)程：1若則矩陣A奇異，程序結(jié)束；否則執(zhí)行。2 舉例說(shuō)明。4、消元法應(yīng)用（1）行列式計(jì)算；（2）矩陣求逆。二、利用矩陣三角分解求解線(xiàn)性方程組1、求解原理線(xiàn)性方程組寫(xiě)成矩陣形式為：AX=b若A=LU，則LU

4、X= b，記UX=Y則LY= b若L、U為特殊矩陣，則求解線(xiàn)性方程組變?yōu)榻鈨蓚€(gè)特殊線(xiàn)性方程組問(wèn)題。2、 Doolittle分解L為下三角矩陣, U為上三角矩陣,不一定能分解,分解也不一定唯一;設(shè)L或U是單位三角矩陣, 若能分解,則可分解唯一.L是單位下三角矩陣,稱(chēng)為Doolittle分解; U是單位上三角矩陣,稱(chēng)為Crout分解；定理: n階矩陣A有唯一分解的充要條件為A的前n-1階主子式都不為0.Doolittle分解算法：由矩陣乘法：得到：算法特點(diǎn)：先計(jì)算U的行，再計(jì)算L的列，交替進(jìn)行；存儲(chǔ)時(shí)可用緊湊格式。矩陣分解后，解兩個(gè)三角方程組：LY= b，UX=Y3、Crout分解若L為下三角矩陣

5、，U是單位上三角矩陣，則稱(chēng)Crout分解；算法特點(diǎn)：先計(jì)算L的列，再計(jì)算U的行，交替進(jìn)行。4、正定對(duì)稱(chēng)矩陣的平方根法（Cholesky分解）（1） 正定對(duì)稱(chēng)矩陣性質(zhì)與判定：定義：是n階對(duì)稱(chēng)矩陣，若對(duì)任意非零向量，有，則稱(chēng)A為正定對(duì)稱(chēng)矩陣； 判定：A為n階正定對(duì)稱(chēng)矩陣充要條件A的各階順序主子式大于0。（2） Cholesky分解定理：設(shè)A為n階正定對(duì)稱(chēng)矩陣，則存在唯一主對(duì)角線(xiàn)元素都是正數(shù)的下三角陣L，使得.Cholesky分解算法：5、 追趕法 三對(duì)角矩陣的特殊分解三對(duì)角方程組的追趕法：追的過(guò)程LY=D趕的過(guò)程UX=Y§2 線(xiàn)性方程組的迭代解法一、 Jacobi迭代公式例： 其解為 方

6、程變形得到迭代公式 給初值計(jì)算，觀察解的變化。一般地，對(duì)線(xiàn)性方程組若，則可從第i個(gè)方程中解出,得到Jacobi迭代公式：簡(jiǎn)記為：二、 Gauss-Seidel迭代公式三、 SOR迭代公式四、 迭代公式的矩陣表示 §3 迭代公式的收斂性一、 向量與矩陣的范數(shù)與性質(zhì)1、 向量范數(shù)定義：向量，對(duì)應(yīng)非負(fù)實(shí)數(shù)，滿(mǎn)足三條件：（1）非負(fù)性 （2）齊次性 （3）三角不等式 稱(chēng)為向量范數(shù)2、 常見(jiàn)向量范數(shù)1范數(shù) 2范數(shù) 范數(shù) 3、 矩陣范數(shù)定義：方陣，對(duì)應(yīng)非負(fù)實(shí)數(shù)，滿(mǎn)足三條件：（1）非負(fù)性 （2）齊次性 （3）三角不等式 （4）絕對(duì)值不等式 稱(chēng)為矩陣范數(shù)；向量范數(shù)與矩陣范數(shù)相容性：4、常見(jiàn)矩陣范數(shù)1范

7、數(shù)，列范數(shù) ： 范數(shù)，行范數(shù) ： 2范數(shù)，譜范數(shù) ：F范數(shù)：舉例計(jì)算二、 迭代公式收斂性的判定1、 向量的極限2、 矩陣的譜半徑： 為特征值；3、收斂性的判定收斂的充要條件：迭代公式收斂的充要條件為譜半徑。判定定理1：若則迭代公式收斂。判定定理2：若對(duì)方程AX=b的系數(shù)矩陣A為對(duì)角占優(yōu)，則Jacobi迭代公式，Gauss-Seidel迭代公式收斂；判定定理3：若對(duì)方程AX=b的系數(shù)矩陣A為對(duì)稱(chēng)正定，則Gauss-Seidel迭代公式收斂；Jacobi迭代公式收斂與Gauss-Seidel迭代公式收斂關(guān)系舉例：第三章 非線(xiàn)性方程的數(shù)值解法1了解二分法的原理與算法；2掌握一般迭代法的基本思想及其收

8、斂性判定 ；3掌握Newton切線(xiàn)法、弦截法，并用它們求方程近似根的方法。本章問(wèn)題：求方程f(x)=0的根§1 二分法一、 根的存在性定理：函數(shù)f(x)在區(qū)間a，b連續(xù)，且f(a).f(b)<0,則方程f(x)=0在區(qū)間a，b有根。方程的根存在，不一定唯一，若在區(qū)間a，b上有唯一根，稱(chēng)區(qū)間a，b為根隔離區(qū)間。二、 二分法（區(qū)間逐次分半法）原理：通過(guò)計(jì)算根隔離區(qū)間中點(diǎn)，將區(qū)間分半，縮小區(qū)間，得到方程近似根數(shù)列。 取 §2 迭代法一、 迭代原理迭代法是一種逐次逼近法，由提供的遞推公式計(jì)算，逐次精確，直到滿(mǎn)足精度要求。方程f(x)=0變形為，得到遞推公式-簡(jiǎn)單迭代公式稱(chēng)為迭

9、代函數(shù)給初值計(jì)算，得到數(shù)列，若，則稱(chēng)迭代收斂，否則發(fā)散。例：求方程寫(xiě)出兩個(gè)簡(jiǎn)單迭代公式：（1） （2）觀察計(jì)算得到數(shù)列的收斂性。迭代法的幾何解釋?zhuān)憾?迭代收斂性判定收斂性定理：設(shè)方程的迭代函數(shù)在a，b滿(mǎn)足：（1）當(dāng)時(shí)，；（2）在a，b可導(dǎo)，且，則（1）方程在a，b有唯一根； （2）迭代公式收斂，即；（3）誤差估計(jì)。說(shuō)明可根據(jù)迭代函數(shù)的導(dǎo)數(shù)判斷迭代收斂性。三、 迭代公式的加速§3 Newton 迭代法一、Newton切線(xiàn)公式幾何作法迭代公式例：利用解二次方程推導(dǎo)近似計(jì)算的公式。由Newton切線(xiàn)公式 三、 Newton弦截公式Newton切線(xiàn)公式的缺點(diǎn)及改進(jìn)幾何作法迭代公式Newto

10、n弦截公式是兩步公式。第五章 插值法1. 掌握代數(shù)插值問(wèn)題及其解存在唯一性，Lagrange插值多項(xiàng)式構(gòu)造及其余項(xiàng)，插值基函數(shù)性質(zhì)；2. 掌握差商的概念及其性質(zhì)，Newton插值多項(xiàng)式構(gòu)造，兩種插值法之間的區(qū)別與聯(lián)系；3了解差分與等距節(jié)點(diǎn)插值多項(xiàng)式公式；4. 掌握Hermite 插值問(wèn)題及其構(gòu)造方法。本章問(wèn)題：函數(shù)復(fù)雜，或無(wú)表達(dá)式，構(gòu)造簡(jiǎn)單函數(shù)來(lái)代替。§1 Lagrange插值一、代數(shù)插值問(wèn)題及插值多項(xiàng)式存在唯一條件1、代數(shù)插值問(wèn)題：已知在區(qū)間a,b中互異的n+1個(gè)點(diǎn)的函數(shù)值，求次數(shù)n次多項(xiàng)式且滿(mǎn)足，（i=0,1,n）.2、插值多項(xiàng)式存在唯一條件：定理：存在唯一條件是n+1個(gè)節(jié)點(diǎn)互異

11、。二、Lagrange插值構(gòu)造1、線(xiàn)形插值（n=1）幾何解釋?zhuān)焕貌逯祷瘮?shù)構(gòu)造：基函數(shù)：一次多項(xiàng)式滿(mǎn)足 -1次Lagrange插值多項(xiàng)式例1：求過(guò)點(diǎn)（4，2），（9，3）的1次Lagrange插值多項(xiàng)式，并計(jì)算近似值。2、拋物插值（n=2）幾何解釋?zhuān)焕貌逯祷瘮?shù)構(gòu)造：基函數(shù)：二次多項(xiàng)式滿(mǎn)足 -2次Lagrange插值多項(xiàng)式例2：求過(guò)點(diǎn)（1，1），（4，2），（9，3）的2次Lagrange插值多項(xiàng)式，并計(jì)算近似值。3、一般情形：利用插值基函數(shù)構(gòu)造：基函數(shù)：n次多項(xiàng)式滿(mǎn)足 -n次Lagrange插值多項(xiàng)式三、插值余項(xiàng)定理：若則插值誤差，其中。§2 分段插值一、分段線(xiàn)性插值在區(qū)間a，

12、b，分為n個(gè)區(qū)間,i=0,1,2n-1每個(gè)區(qū)間由直線(xiàn)代替曲線(xiàn)，形成分段線(xiàn)性插值函數(shù)，二、分段拋物插值§3 Newton 插值一、差商及其性質(zhì)定義：一階差商：二階差商：K階差商：性質(zhì)：（1）差商可由節(jié)點(diǎn)函數(shù)值表示；（2）差商值與節(jié)點(diǎn)次序無(wú)關(guān)。二、Newton 插值多項(xiàng)式由差商定義。依次帶入- Newton 插值多項(xiàng)式計(jì)算時(shí)先造差商表；三、余項(xiàng)§4 差分與等距節(jié)點(diǎn)插值多項(xiàng)式一、差分及其性質(zhì)：二、等距節(jié)點(diǎn)插值多項(xiàng)式§5 Hermite 插值一、帶導(dǎo)數(shù)的插值多項(xiàng)式1、問(wèn)題：求次數(shù)不超過(guò)3次多項(xiàng)式；2、利用基函數(shù)構(gòu)造二、一般情形1、問(wèn)題：求次數(shù)不超過(guò)2n+1次多項(xiàng)式2、利用

13、基函數(shù)構(gòu)造見(jiàn)教材第七章 數(shù)值微積分1. 了解數(shù)值求積基本思想；2. 掌握Newton-Cotes公式（梯形公式，Simpson公式，Cotes公式）推導(dǎo)及誤差；3. 了解Romberg 求積公式原理；4了解數(shù)值微分的方法。本章問(wèn)題：數(shù)值積分問(wèn)題求定積分 不能使用微積分公式情形存在問(wèn)題：（1）f(x)表達(dá)式復(fù)雜，原函數(shù)更復(fù)雜； （2）f(x)表達(dá)式不復(fù)雜，但原函數(shù)復(fù)雜；（3）原函數(shù)不存在； （3）f(x)無(wú)表達(dá)式§1 Newton-Cotes公式一、 數(shù)值求積基本思想1、 不利用原函數(shù)，直接利用函數(shù)值積分中值定理：為平均高度；機(jī)械求積方法：為求積節(jié)點(diǎn)；為求積系數(shù)。2、 幾個(gè)簡(jiǎn)單求積公式

14、左矩形公式右矩形公式中矩形公式梯形公式二、 Newton-Cotes公式1、公式推導(dǎo)由Lagrange插值多項(xiàng)式代替函數(shù)f(x)記則求積系數(shù)的計(jì)算：-為Cotes系數(shù)；- Newton-Cotes求積公式2、Cotes系數(shù)性質(zhì)對(duì)稱(chēng)性：權(quán)性：3、常用公式n=1梯形公式：n=2Simpson,拋物公式：n=4Cotes公式： 4誤差估計(jì)：見(jiàn)教材 舉例說(shuō)明。 §2 Romberg 求積公式一、復(fù)化梯形公式將積分區(qū)間a,b， n等份，步長(zhǎng)誤差估計(jì)：二、梯形公式遞推化三、Romberg 求積公式由梯形公式修正，提高精度§3 Gauss型求積公式一、代數(shù)精確度定義：若求積公式對(duì)任意m次

15、代數(shù)多項(xiàng)式精確成立，而對(duì)m+1次代數(shù)多項(xiàng)式不精確成立，稱(chēng)求積公式具有m次代數(shù)精確度。判定：求積公式具有m次代數(shù)精確度求積公式對(duì)精確成立；而對(duì) 不精確成立。例：梯形公式具有1次代數(shù)精確度；定理1：n+1個(gè)節(jié)點(diǎn)的插值型求積公式代數(shù)精確度至少為n；定理2；Newton-Cotes公式代數(shù)精確度至少為n；當(dāng)n為偶數(shù)時(shí)，可達(dá)n+1次代數(shù)精確度。二、Gauss型求積公式定義：若n+1個(gè)節(jié)點(diǎn)求積公式具有2n+1次代數(shù)精確度，則稱(chēng)為Gauss型求積公式，節(jié)點(diǎn)為Gauss點(diǎn)。Gauss點(diǎn)的特性：見(jiàn)教材第八章 常微分方程數(shù)值解1. 掌握 Euler方法（Euler公式，梯形公式，Euler預(yù)估-校正公式），局部截?cái)嗾`差，公式的階；2. 了解 Runge-Kutta 方法的基本思想及四階經(jīng)典Runge-Kutta 公式；3. 掌握線(xiàn)性多步方法的原理與公式推導(dǎo)。本章問(wèn)題：一階常微分方程初值問(wèn)題 解的存在性定理：解析解的概念數(shù)值解的概念§1 Euler方法一、 Euler公式導(dǎo)數(shù)離散化由向前差商代替導(dǎo)數(shù)得記為 - Euler顯式公式由向后差商代替導(dǎo)數(shù)得記為 - Euler隱式公式由中心差商代替導(dǎo)數(shù)得記為 - Euler兩步公式二、 Euler預(yù)估-校正公式梯形公式預(yù)估：校正：三、 誤差估計(jì)1 局部截?cái)嗾`差2 公