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

-.z.數(shù)值計算方法復(fù)習(xí)提綱第一章數(shù)值計算中的誤差分析1．了解誤差及其主要來源，誤差估計；2．了解誤差(絕對誤差、相對誤差)和有效數(shù)字的概念及其關(guān)系；3．掌握算法及其穩(wěn)定性，設(shè)計算法遵循的原則。誤差的來源模型誤差觀測誤差截斷誤差舍入誤差2誤差與有效數(shù)字絕對誤差E〔*〕=*-*絕對誤差限相對誤差有效數(shù)字假設(shè)，稱有n位有效數(shù)字。有效數(shù)字與誤差關(guān)系m一定時，有效數(shù)字n越多，絕對誤差限越??；有n位有效數(shù)字，則相對誤差限為。選擇算法應(yīng)遵循的原則選用數(shù)值穩(wěn)定的算法，控制誤差傳播；例△△*簡化計算步驟，減少運算次數(shù)；防止兩個相近數(shù)相減，和接近零的數(shù)作分母；防止第二章線性方程組的數(shù)值解法1．了解Gauss消元法、主元消元法根本思想及算法；2．掌握矩陣的三角分解，并利用三角分解求解方程組；〔Doolittle分解；Crout分解；Cholesky分解；追趕法〕3．掌握迭代法的根本思想，Jacobi迭代法與Gauss-Seidel迭代法；4．掌握向量與矩陣的*數(shù)及其性質(zhì),迭代法的收斂性及其判定。本章主要解決線性方程組求解問題，假設(shè)n行n列線性方程組有唯一解，如何得到其解？兩類方法，第一是直接解法，得到其準(zhǔn)確解；第二是迭代解法，得到其近似解。Gauss消去法順序Ｇauss消去法記方程組為：消元過程：經(jīng)ｎ－１步消元，化為上三角方程組第ｋ步假設(shè)回代過程：２、Ｇauss—Ｊｏｒｄａｎ消去法防止回代，消元時上下同時消元３、Ｇauss列主元消去法例：說明直接消元，出現(xiàn)錯誤由順序Ｇauss消去法，得；Ｇauss列主元消去法原理：每步消元前，選列主元，交換方程。算法：將方程組用增廣矩陣EQ表示。〔1〕消元過程：對k=1,2,n-1,選主元，找如果，則矩陣A奇異，程序完畢；否則執(zhí)行3。如果，則交換第k行與第行對應(yīng)的元素位置，消元，對i=k+1,,n,計算對j=L+1,,n+1,計算〔2〕回代過程：1．假設(shè)則矩陣A奇異，程序完畢；否則執(zhí)行。2舉例說明。4、消元法應(yīng)用〔1〕行列式計算；〔2〕矩陣求逆。二、利用矩陣三角分解求解線性方程組1、求解原理線性方程組寫成矩陣形式為：A*=b假設(shè)A=LU，則LU*=b，記U*=Y則LY=b假設(shè)L、U為特殊矩陣，則求解線性方程組變?yōu)榻鈨蓚€特殊線性方程組問題。Doolittle分解L為下三角矩陣,U為上三角矩陣,不一定能分解,分解也不一定唯一;設(shè)L或U是單位三角矩陣,假設(shè)能分解,則可分解唯一.L是單位下三角矩陣,稱為Doolittle分解;U是單位上三角矩陣,稱為Crout分解；定理:n階矩陣A有唯一分解的充要條件為A的前n-1階主子式都不為0.Doolittle分解算法：由矩陣乘法：得到：算法特點：先計算U的行，再計算L的列，交替進展；存儲時可用緊湊格式。矩陣分解后，解兩個三角方程組：LY=b，U*=Y3、Crout分解假設(shè)L為下三角矩陣，U是單位上三角矩陣，則稱Crout分解；算法特點：先計算L的列，再計算U的行，交替進展。4、正定對稱矩陣的平方根法〔Cholesky分解〕正定對稱矩陣性質(zhì)與判定：定義：是n階對稱矩陣，假設(shè)對任意非零向量，有，則稱A為正定對稱矩陣；判定：A為n階正定對稱矩陣充要條件A的各階順序主子式大于0。Cholesky分解定理：設(shè)A為n階正定對稱矩陣，則存在唯一主對角線元素都是正數(shù)的下三角陣L，使得.Cholesky分解算法：追趕法三對角矩陣的特殊分解三對角方程組的追趕法：追的過程LY=D趕的過程U*=Y§2線性方程組的迭代解法Jacobi迭代公式例：其解為方程變形得到迭代公式給初值計算，觀察解的變化。一般地，對線性方程組假設(shè)，則可從第i個方程中解出,得到Jacobi迭代公式：簡記為：Gauss--Seidel迭代公式SOR迭代公式迭代公式的矩陣表示§3迭代公式的收斂性向量與矩陣的*數(shù)與性質(zhì)向量*數(shù)定義：向量，對應(yīng)非負實數(shù)，滿足三條件：〔1〕非負性〔2〕齊次性〔3〕三角不等式稱為向量*數(shù)常見向量*數(shù)1*數(shù)2*數(shù)∞*數(shù)矩陣*數(shù)定義：方陣，對應(yīng)非負實數(shù)，滿足三條件：〔1〕非負性〔2〕齊次性〔3〕三角不等式〔4〕絕對值不等式稱為矩陣*數(shù)；向量*數(shù)與矩陣*數(shù)相容性：4、常見矩陣*數(shù)1*數(shù)，列*數(shù)：∞*數(shù)，行*數(shù)：2*數(shù)，譜*數(shù)：F*數(shù)：舉例計算迭代公式收斂性的判定向量的極限矩陣的譜半徑：為特征值；3、收斂性的判定收斂的充要條件：迭代公式收斂的充要條件為譜半徑。判定定理1：假設(shè)則迭代公式收斂。判定定理2：假設(shè)對方程A*=b的系數(shù)矩陣A為對角占優(yōu)，則Jacobi迭代公式，Gauss--Seidel迭代公式收斂；判定定理3：假設(shè)對方程A*=b的系數(shù)矩陣A為對稱正定，則Gauss--Seidel迭代公式收斂；Jacobi迭代公式收斂與Gauss--Seidel迭代公式收斂關(guān)系舉例：第三章非線性方程的數(shù)值解法1．了解二分法的原理與算法；2．掌握一般迭代法的根本思想及其收斂性判定；3．掌握Newton切線法、弦截法，并用它們求方程近似根的方法。本章問題：求方程f(*)=0的根§1二分法根的存在性定理：函數(shù)f(*)在區(qū)間[a，b]連續(xù)，且f(a).f(b)<0,則方程f(*)=0在區(qū)間[a，b]有根。方程的根存在，不一定唯一，假設(shè)在區(qū)間[a，b]上有唯一根，稱區(qū)間[a，b]為根隔離區(qū)間。二分法〔區(qū)間逐次分半法〕原理：通過計算根隔離區(qū)間中點，將區(qū)間分半，縮小區(qū)間，得到方程近似根數(shù)列{。取§2迭代法迭代原理迭代法是一種逐次逼近法，由提供的遞推公式計算，逐次準(zhǔn)確，直到滿足精度要求。方程f(*)=0變形為，得到遞推公式--------簡單迭代公式稱為迭代函數(shù)給初值計算，得到數(shù)列{，假設(shè)，則稱迭代收斂，否則發(fā)散。例：求方程寫出兩個簡單迭代公式：〔1〕〔2〕觀察計算得到數(shù)列{的收斂性。迭代法的幾何解釋：迭代收斂性判定收斂性定理：設(shè)方程的迭代函數(shù)在[a，b]滿足：〔1〕當(dāng)時，；〔2〕在[a，b]可導(dǎo)，且，，則〔1〕方程在[a，b]有唯一根；〔2〕迭代公式收斂，即；〔3〕誤差估計。說明可根據(jù)迭代函數(shù)的導(dǎo)數(shù)判斷迭代收斂性。迭代公式的加速§3Newton迭代法一、Newton切線公式幾何作法迭代公式例：利用解二次方程推導(dǎo)近似計算的公式。由Newton切線公式Newton弦截公式Newton切線公式的缺點及改良幾何作法迭代公式Newton弦截公式是兩步公式。插值法1.掌握代數(shù)插值問題及其解存在唯一性，Lagrange插值多項式構(gòu)造及其余項，插值基函數(shù)性質(zhì)；2.掌握差商的概念及其性質(zhì)，Newton插值多項式構(gòu)造，兩種插值法之間的區(qū)別與聯(lián)系；3．了解差分與等距節(jié)點插值多項式公式；4.掌握Hermite插值問題及其構(gòu)造方法。本章問題：函數(shù)復(fù)雜，或無表達式，構(gòu)造簡單函數(shù)來代替?！?Lagrange插值一、代數(shù)插值問題及插值多項式存在唯一條件1、代數(shù)插值問題：在區(qū)間[a,b]中互異的n+1個點的函數(shù)值，求次數(shù)n次多項式且滿足，〔i=0,1,…n〕.2、插值多項式存在唯一條件：定理：存在唯一條件是n+1個節(jié)點互異。二、Lagrange插值構(gòu)造1、線形插值〔n=1〕幾何解釋；利用插值基函數(shù)構(gòu)造：基函數(shù)：一次多項式滿足----------1次Lagrange插值多項式例1：求過點〔4，2〕，〔9，3〕的1次Lagrange插值多項式，并計算近似值。2、拋物插值〔n=2〕幾何解釋；利用插值基函數(shù)構(gòu)造：基函數(shù)：二次多項式滿足-------2次Lagrange插值多項式例2：求過點〔1，1〕，〔4，2〕，〔9，3〕的2次Lagrange插值多項式，并計算近似值。3、一般情形：利用插值基函數(shù)構(gòu)造：基函數(shù)：n次多項式滿足-------n次Lagrange插值多項式三、插值余項定理：假設(shè)則插值誤差，其中?！?分段插值一、分段線性插值在區(qū)間[a，b]，分為n個區(qū)間,i=0,1,2…n-1每個區(qū)間由直線代替曲線，形成分段線性插值函數(shù)，二、分段拋物插值§3Newton插值一、差商及其性質(zhì)定義：一階差商：二階差商：K階差商：性質(zhì)：〔1〕差商可由節(jié)點函數(shù)值表示；〔2〕差商值與節(jié)點次序無關(guān)。二、Newton插值多項式由差商定義。。。依次帶入-----Newton插值多項式計算時先造差商表；三、余項§4差分與等距節(jié)點插值多項式一、差分及其性質(zhì)：二、等距節(jié)點插值多項式§5Hermite插值一、帶導(dǎo)數(shù)的插值多項式1、問題：求次數(shù)不超過3次多項式；2、利用基函數(shù)構(gòu)造二、一般情形1、問題：求次數(shù)不超過2n+1次多項式2、利用基函數(shù)構(gòu)造見教材數(shù)值微積分1.了解數(shù)值求積根本思想；2.掌握Newton-Cotes公式〔梯形公式，Simpson公式，Cotes公式〕推導(dǎo)及誤差；3.了解Romberg求積公式原理；4．了解數(shù)值微分的方法。本章問題：數(shù)值積分問題求定積分不能使用微積分公式情形存在問題：〔1〕f(*)表達式復(fù)雜，原函數(shù)更復(fù)雜；〔2〕f(*)表達式不復(fù)雜，但原函數(shù)復(fù)雜；〔3〕原函數(shù)不存在；〔3〕f(*)無表達式§1Newton-Cotes公式數(shù)值求積根本思想不利用原函數(shù)，直接利用函數(shù)值積分中值定理：為平均高度；機械求積方法：為求積節(jié)點；為求積系數(shù)。幾個簡單求積公式左矩形公式右矩形公式中矩形公式梯形公式Newton-Cotes公式1、公式推導(dǎo)由Lagrange插值多項式代替函數(shù)f(*)記則求積系數(shù)的計算：-為Cotes系數(shù)；---------Newton-Cotes求積公式2、Cotes系數(shù)性質(zhì)對稱性：權(quán)性：3、常用公式n=1梯形公式：n=2Simpson,拋物公式：n=4Cotes公式：4誤差估計：見教材舉例說明?！?Romberg求積公式一、復(fù)化梯形公式將積分區(qū)間[a,b]，n等份，步長誤差估計：二、梯形公式遞推化三、Romberg求積公式由梯形公式修正，提高精度§3Gauss型求積公式一、代數(shù)準(zhǔn)確度定義：假設(shè)求積公式對任意≤m次代數(shù)多項式準(zhǔn)確成立，而對m+1次代數(shù)多項式不準(zhǔn)確成立，稱求積公式具有m次代數(shù)準(zhǔn)確度。判定：求積公式具有m次代數(shù)準(zhǔn)確度求積公式對準(zhǔn)確成立；而對不準(zhǔn)確成立。例：梯形公式具有1次代數(shù)準(zhǔn)確度；定理1：n+1個節(jié)點的插值型求積公式代數(shù)準(zhǔn)確度至少為n；定理2；Newton-Cotes公式代數(shù)準(zhǔn)確度至少為n；當(dāng)n為偶數(shù)時，可達n+1次代數(shù)準(zhǔn)確度。二、Gauss型求積公式定義：假設(shè)n+1個節(jié)點求積公式具有2n+1次代數(shù)準(zhǔn)確度，則稱為Gauss型求積公式，節(jié)點為Gauss點。Gauss點的特性：見教材常微分方程數(shù)值解1.掌握Euler方法〔Euler公式，梯形公式，Euler預(yù)估-校正公式〕，局部截斷誤差，公式的階；2.了解Runge-Kutta方法的根本思想及四階經(jīng)典Runge-Kutta公式；3.掌握線性多步方法的原理與公式推導(dǎo)。本章問題：一階常微分方程初值問題解的存在性定理：解析解的概念數(shù)值解的概念§1Euler方法Euler公式導(dǎo)數(shù)離散化由向前差商代替導(dǎo)數(shù)得記為-------Euler顯式公式由向后差商代替導(dǎo)數(shù)得記為-------Euler隱式公式由中心差商代替導(dǎo)數(shù)得記為-------Euler兩步公式Euler預(yù)估-