數值分析電子課件工科研究生公共課程數學系列第1章緒論內容提要：1.1數值分析研究對象與特點1.2數值計算的誤差1.3誤差定性分析與避免誤差危害1.1數值分析研究對象與特點一、數值分析研究對象計算機解決科學計算問題時經歷的過程實際問題模型設計算法設計問題的解上機計算程序設計求方程求根牛頓法

程序設計解上機計算實例

數值分析的內容包括函數的數值逼近、數值微分與數值積分、非線性方程數值解、數值線性代數、常微和偏微數值解等。數值分析研究對象以及解決問題方法的廣泛適用性，著名流行軟件如Maple、Matlab、Mathematica等已將其絕大多數內容設計成函數，簡單調用之后便可以得到運行結果。

但由于實際問題的具體特征、復雜性,以及算法自身的適用范圍決定了應用中必須選擇、設計適合于自己特定問題的算法，因而掌握數值方法的思想和內容是至關重要的。

本課程內容包括了微積分、代數、常微分方程的數值方法，必須掌握這幾門課程的基礎內容才能學好這門課程。二、數值分析的特點面向計算機，要根據計算機的特點提供切實可行的有效算法。有可靠的理論分析，能任意逼近并達到精度要求，對近似算法要保證收斂性和數值穩定性，還要對誤差進行分析。這些都是建立在數學理論的基礎上，因此不應片面的將數值分析理解為各種數值方法的簡單羅列和堆積。要有好的計算復雜性，時間復雜性好是指節省時間，空間復雜性好是指節省存儲量，這也是建立算法要研究的問題，它關系到算法能否在計算機上實現。要有數值實驗，即任何一個算法除了從理論上要滿足上述三點外，還要通過數值實驗證明是行之有效的。三、數值分析的學習方法初學可能仍會覺得公式多，理論分析復雜。給出如下的幾點學習方法。認識建立算法和對每個算法進行理論分析是基本任務，主動適應公式多和講究理論分析的特點。注重各章節所研究算法的提出，掌握方法的基本原理和思想，要注意方法處理的技巧及其與計算機的結合。理解每個算法建立的數學背景、數學原理和基本線索，而且對一些最基本的算法要非常熟悉。要通過例子，學習使用各種數值方法解決實際計算問題。為掌握本課的內容，還應做一些理論分析和計算練習。1.2數值計算的誤差一、誤差的來源

在運用數學方法解決實際問題的過程中，每一步都可能帶來誤差。1、模型誤差在建立數學模型時，往往要忽視很多次要因素，把模型“簡單化”，“理想化”，這時模型就與真實背景有了差距，即帶入了誤差。2、測量誤差數學模型中的已知參數，多數是通過測量得到。而測量過程受工具、方法、觀察者的主觀因素、不可預料的隨機干擾等影響必然帶入誤差。3、截斷誤差數學模型常難于直接求解，往往要近似替代，簡化為易于求解的問題，這種簡化帶入誤差稱為方法誤差或截斷誤差。4、舍入誤差計算機只能處理有限數位的小數運算，初始參數或中間結果都必須進行四舍五入運算，這必然產生舍入誤差。誤差分析是一門比較艱深的專門學科。在數值分析中主要討論截斷誤差及舍入誤差。但一個訓練有素的計算工作者，當發現計算結果與實際不符時，應當能診斷出誤差的來源，并采取相應的措施加以改進，直至建議對模型進行修改。二、絕對誤差、相對誤差與有效數字1、絕對誤差與絕對誤差限誤差是有量綱的量，量綱同x，它可正可負。誤差一般無法準確計算，只能根據測量或計算情況估計出它的絕對值的一個上界，這個上界稱為近似值x*的誤差限，記為ε*。2、相對誤差與相對誤差限

3、有效數字

定義3如果近似值x*的誤差限是它某一數位的半個單位，我們就說x*準確到該位，從這一位起直到前面第一個非零數字為止的所有數字稱x的有效數字.4、絕對誤差，相對誤差與有效數字的關系

絕對誤差與相對誤差：由兩者定義可知。

絕對誤差與有效數字：絕對誤差不超過末位有效數字的半個單位。有效數字與相對誤差限定理說明有效數位越多，相對誤差限越小。定理也給出了相對誤差限的求法。三、數值運算的誤差估計1、四則運算2、函數誤差當自變量有誤差時計算函數值也產生誤差，可以利用函數的泰勒展開式進行估計。1.3誤差定性分析與避免誤差危害一、病態問題與條件數1、病態問題：對一個數值問題本身如果輸入數據有微小擾動（即誤差），引起輸出數據（即問題解）相對誤差很大，就是病態問題。二、算法的穩定性

用一個算法進行計算，由于初始數據誤差在計算中傳播使計算結果誤差增長很快就是數值不穩定的，先看下例。計算結果：n法一(A)法二(B)01234567890.63210.36790.26420.20740.17040.14800.11200.2160-0.72807.5520.63210.36790.26430.20730.17080.14550.12680.11210.10350.0684三、避免誤差危害的若干原則1、要避免除數絕對值遠遠小于被除數絕對值的除法。用絕對值小的數作除數舍入誤差會增大，如計算x/y，若0<|y|<<|x|，則可能對計算結果帶來嚴重影響，應盡量避免。2、要避免兩相近數相減

在數值中兩相近數相減有效數字會嚴重損失。例如，x=532.65，y=532.52都具有五位有效數字，但x-y=0.13只有兩位有效數字。通過改變算法可以避免兩相近數相減。3、要防止“大數”吃掉小數

數值運算中參加運算的數有時數量級相差很大，而計算機位數有限，如不注意運算次序就可能出現大數“吃掉”小數的現象，影響計算結果的可靠性。

如用六位浮點數計算某市的工業總產值，原始數據是各企業的工業產值，當加法進行到一定程度，部分和超過100億元（0.1×1011），再加產值不足10萬元的小企業產值，將再也加不進去。而這部分企業可能為數不少，合計產值相當大.這種情況應將小數先分別加成大數，然后相加，結果才比較正確。這個例子告訴我們，在計算機數系中，加法的交換律和結合律可能不成立，這是在大規模數據處理時應注意的問題。4、注意簡化計算步驟，減少運算次數

減少算術運算的次數不但可計算機的計算時間，還能減少誤差的積累效應。使參加運算的數字精度應盡量保持一致，否則那些較高精度的量的精度沒有太大意義。誤差及算法誤差算法數值穩定性概念算法設計注意要點分類度量傳播舍入誤差的產生及定義截斷誤差的產生及定義絕對誤差（限）相對誤差（限）有效數字三者的聯系一元函數n元函數計算函數值問題的條件數二元算術運算知識結構圖一第2章插值法內容提要2.1引言2.2拉格朗日插值2.3均差與牛頓插值公式2.4埃爾米特插值2.5分段低次插值2.6三次樣條插值2.1引言許多實際問題都用函數y=f(x)來表示某種內在規律的數量關系。若已知f(x)在某個區間[a,b]上存在、連續，但只能給出[a,b]上一系列點的函數值表時，或者函數有解析表達式，但計算過于復雜、使用不方便只給出函數值表（如三角函數表、對數表等）時，為了研究函數的變化規律，往往需要求出不在表上的函數值。因此我們希望根據給定的函數表做一個既能反映函數f(x)的特性，又便于計算的簡單函數P(x)，用P(x)近似f(x)。這就引出了插值問題。1、提出問題（插值法的定義）2、幾何意義、外插、內插P(x)

f(x)x*(外插)x0x1x(內插)x2x3P(x*)

f(x*)3、插值的種類選取不同的函數族構造

P(x)得到不同類型的插值若P(x)是次數不超過n的代數多項式，就稱為多項式插值；若P(x)為分段的多項式，就稱為分段插值；若P(x)為三角多項式，就稱為三角插值。本章只討論多項式插值與分段插值。主要研究內容為如何求出插值多項式，分段插值函數；討論插值多項式P(x)的存在唯一性、收斂性及估計誤差等。4、多項式插值問題插值多項式的存在唯一性

定理1(存在唯一性)滿足插值條件的不超過n次的插值多項式是存在唯一的。2.2拉格朗日插值一、線性插值與拋物插值1、線性插值y=f(x)L1(x)yxxk+1xk02、拋物插值求解基函數二、拉格朗日插值多項式

上面針對n=1和n=2的情況，得到了一次和二次插值多項式，這種用基函數表示的方法很容易推廣到一般情況。下面討論如何構造n+1個節點的n次插值多項式。定理表明：(1)插值誤差與節點和點x之間的距離有關,節點距離x越近,插值誤差一般情況下越小。

(2)若被插值函數f(x)本身就是不超過n次的多項式,則有f(x)≡g(x)。

3、應用舉例用二次插值計算ln(11.25)的近似值,并估計誤差。例2-2給定函數值表在區間[10,12]上lnx的三階導數(2/x3)的上限M3=0.002,可得誤差估計式注：實際上,ln(11.25)=2.420368,|R2(11.25)|=0.0000580

?分析：求解如上問題等價于求解x關于y的反函數問題。2.3均差與牛頓插值公式一、均差及其性質問題的引入：拉格朗日插值多項式，公式結構緊湊，理論分析方便，但插值節點增減時全部插值及函數均要隨之變化，實際計算不方便，希望把公式表示為如下形式。1、均差定義2、均差的基本性質2、均差的基本性質2、均差的基本性質均差計算表例如由函數y=(x)的函數表寫出均差表.解均差表如下二、牛頓插值公式解由差商表知[x0,x1]=-2,[x0,x1,x2]=3,[x0,x1,x2,x3]=-1,于是有N1(x)=5-2(x+2)=1-2xN2(x)=1-2x+3(x+2)(x+1)=3x2+7x+7N3(x)=3x2+7x+7-(x+2)(x+1)(x-1)=-x3+x2+8x+9例2-6

對例如中的(x),求節點為x0,x1的一次插值，x0,x1,x2的二次插值和x0,x1,x2,x3的三次插多項式.

例2-7給出f(x)的函數表，求4次牛頓插值多項式，并計算f(0.596)的近似值。2.4埃爾米特插值

不少實際的插值問題不但要求在節點上函數值相等，而且還要求對應的導數值也相等，甚至要求高階導數也相等，滿足這種要求的插值多項式就是埃爾米特（Hermite）插值多項式。

y=L10(x)y=L10(x)解法二（用重節點的均差表建立埃爾米特多項式）2.5分段低次插值一、高次插值的病態性質一般總認為Ln(x)的次數n越高逼近f(x)的精度越好，但實際上并非如此。這是因為對任意的插值節點，當n->∞時，Ln(x)不一定收斂于f(x)。20世紀初龍格（Runge）就給了一個等距節點插值多項式Ln(x)不一定收斂于f(x)的例子。

y=L10(x)

x1y=L10(x)o-10.5y1.51龍格現象二、分段線性插值分段線性插值就是通過插值點用折線段連接起來逼近f(x).分段線性插值三、分段拋物插值三、分段拋物插值2.6三次樣條插值

樣條曲線實際上是由分段三次曲線并接而成，在連接點即樣點上要求二階導數連續，從數學上加以概括就得到數學樣條這一概念。下面我們討論最常用的三次樣條函數。一、三次樣條函數y=L10(x)每個小區間上要確定4個待定系數，共有n個小區間，故應確定4n個參數。y=L10(x)二、三次樣條插值函數的建立y=L10(x)y=L10(x)y=L10(x)y=L10(x)系數矩陣為嚴格對角占優陣，方程組有為一解。求法見5.3節追趕法。y=L10(x)y=L10(x)知識結構圖二插值法工具分段多項式插值存在唯一性多項式插值Hermite插值插值公式誤差估計差商、差分Lagrange插值基及函數定義性質定義性質導數型差商型Lagrange插值多項式Newton插值多項式等距節點插值公式存在唯一性誤差估計插值公式分段線性插值（公式、誤差估計、收斂性）分段三次Hermite插值（公式、誤差估計、收斂性）三次樣條插值（公式、存在唯一性、誤差估計、收斂性）第三章函數逼近內容提要3.1基本概念3.2最佳平方逼近3.3曲線擬合的最小二乘法3.1基本概念

x0x3x5x7x1x4x6x2f(x)p(x)2、范數與賦范線形空間3、內積與內積空間1、最佳平方逼近3.2最佳平方逼近一、最小二乘法及其計算3.3曲線擬合的最小二乘法例3-3已知實測數據表如下,求它的擬合曲線0xy2468642例3-4

已知實測數據表如下,確定數學模型y=aebx,用最小二乘法確定a，b。分析：根據給定數據描圖也可確定擬合曲線方程，但它不是線性形式。因此首先要將經驗曲線線性化。本題可以采取等式兩邊取對數的形式線性化。數據表中的數值也相應的轉化為取對數之后的數值，見下表。知識結構圖三函數逼近理論預備知識范數（定義、常用范數）內積（定義、柯西-施瓦茨不等式、內積誘導范數）正交多項式（性質、正交化方法、常用正交多項式的定義和性質）函數逼近方法最佳一致逼近多項式最佳平方逼近定義存在唯一性定理切比雪夫定理最佳一次逼近多項式的確定最小二乘擬合定義法方程組和平方誤差基于正交基的最佳平方逼近離散內積定義法方程組及哈爾條件基于正交基的最小二乘擬合第四章數值積分和數值微分內容提要4.1引言4.2牛頓-柯特斯公式4.3復化求積公式4.4龍貝格求積公式4.5高斯求積公式4.6數值微分4.1引言一、數值求積的基本思想對定義在區間［a,b］上的定積分但有時原函數不能用初等函數表示，有時原函數又十分復雜，難于求出或計算；另外如被積函數是由測量或數值計算給出的一張數據表示時，上述方法也不能直接運用。因此有必要研究積分的數值計算問題。積分中值定理告訴我們：平均高度f(ζ)

a

ζ

b

yxy=f(x)0

a

f((a+b)/2)

b

yxy=f(x)0

a

b

yxy=f(x)0梯形公式平均高度中矩形公式平均高度更一般地，我們構造具有下列形式的求積公式求積節點求積系數這類數值方法通常稱為機械求積，其特點是將積分求值問題歸結為函數值的計算，這就避開了牛頓-萊布尼茲公式需要尋求原函數的困難。二、代數精度的概念利用代數精度的概念構造求積公式三、插值型的求積公式4.2牛頓-柯特斯公式一、牛頓-柯特斯公式的導出柯特斯系數牛頓-柯特斯公式的代數精度4.3復合求積公式

一、問題與基本思想在使用牛頓-柯特斯公式時將導致求積系數出現負數(當n≥8時,牛頓.柯特斯求積系數會出現負數)，因而不可能通過提高階的方法來提高求積精度。為了提高精度通常采用將積分區間劃分成若干個小區間，在各小區間上采用低次的求積公式(梯形公式或辛普森公式)，然后再利用積分的可加性，把各區間上的積分加起來，便得到新的求積公式，這就是復化求積公式的基本思想。本節只討論復化的梯形公式和復化的辛普森公式。二、復合梯形公式三、復合辛普森公式4.4龍貝格求積公式

一、梯形法的遞推化(變步長求積法)

于是可以逐次對分形成一個序列{T1,T2,T4,T8,…},此序列收斂于積分真值I。當|T2n-Tn|<ε時，取T2n為I的近似值。以上算法稱為變步長求積法。但由于此序列收斂太慢。下節我們將其改造成為收斂快的序列。二、龍貝格算法如何提高收斂速度以節省計算量是龍貝格算法要討論的中心問題。這樣我們從收斂較慢的{Tn}序列推出了收斂較快的{Sn}序列。可以證明{Sn}序列實際上就是逐次分半的復化辛普森公式序列。

這樣我們從{Cn}序列又推出了收斂更快的{Rn}序列.{Rn}序列也稱為龍貝格序列。我們從收斂較慢的{Tn}序列只用了一些四則運算，便推出了收斂更快的{Sn}序列,{Cn}序列和{Rn}序列。運算順序表這里利用二分3次的數據（它們的精度都很差，只有兩三位有效數字）通過三次加速求得R1=0.9460831,這個結果的每一位數字都是有效數字，可見加速效果是十分顯著的。4.5高斯求積公式

一、一般理論

4.6數值微分一、中點方法與誤差分析數值微分就是要用函數值的線性組合近似函數在某點的導數值。由導數定義差商近似導數得到數值微分公式。二、插值型的求導公式知識結構圖四數值積分與數值微分數值積分基本概念牛頓-柯特斯公式復合求積公式數值微分中點方法插值型求導公式龍貝格求積公式高斯求積公式第五章解線性方程組的直接方法內容提要5.1引言與預備知識5.2高斯消去法5.3高斯列主元消去法5.4矩陣三角分解法5.5向量與矩陣的范數5.6誤差分析5.1引言關于線性方程組的數值解法一般有兩類：1、直接解法：經過有限次的算術運算，可求得方程組精確解的方法（若計算過程中沒有舍入誤差）。但實際計算中由于舍入誤差的存在和影響，這種方法也只能求得線性方程組的近似解。本章主要研究此類問題的解法。2、迭代法：用某種極限過程去逐步逼近現行方程組精確解的方法。迭代法具有需要計算機的存儲單元較少、程序設計簡單、原始系數矩陣在計算過程中始終不變等優點。5.2高斯消去法在求解三角方程組,得高斯消去法的條件5.3高斯主元素消去法列主元消去法5.4矩陣三角分解法Ax=b是線性方程組,A是n×n方陣,并設A的各階順序主子式不為零。令A(1)=A,當高斯消元法進行第一步后,相當于用一個初等矩陣左乘A(1)

。不難看出，這個初等矩陣為重復這個過程，最后得到一般地

這就是說，高斯消去法實質上產生了一個將A分解為兩個三角形矩陣相乘的因式分解，于是我們得到如下重要定理。當A進行LU分解后，Ax=b就容易解了.即Ax=b等價于:

追趕法在一些實際問題中，例如解常微分方程邊值問題，熱傳導方程以及船體數學放樣中建立三次樣條函數等，都會要求解系數矩陣為對角占優的三對角線方程組其中|i-j|>1時,aij=0,且滿足如下的對角占優條件:(1)|b1|>|c1|>0,|bn|>|an|>0(2)|bi|≥|ai|+|ci|,aici≠0,i=2,3,…,n-1.5.5向量和矩陣的范數定義1(向量范數)x和y是Rn中的任意向量,向量范數‖?‖是定義在Rn上的實值函數,它滿足:(1)‖

x

‖≥0,并且當且僅當x=0時,‖

x

‖=0;(2)‖k

x

‖=|k|‖

x

‖,k是一個實數;(3)‖

x+y

‖≤‖

x

‖+‖

y

‖常使用的向量范數有三種,設x=(x1,x2,…,xn)T

常使用的矩陣范數有三種,設x=(x1,x2,…,xn)T

5.6誤差分析知識結構圖五直接法解方程組高斯消去法矩陣的正交三角化及應用定義常用范數范數的性質初等反射陣平面旋轉變換矩陣矩陣的QR分解應用：求解超定方程組高斯消去法高斯若當消去法列主元消去法矩陣三角分解法LU分解平方根分解LDLT分解追趕法解三對角方程組向量和矩陣的范數矩陣條件數及迭代改善法第六章解線性代數方程組的迭代法內容提要6.1引言6.2基本迭代法6.3迭代法的收斂性即AX=b其中A為非奇異矩陣，當A為低階稠密矩陣時，線性方程組用直接法(如高斯消去法和三角分解法)是有效的，但對于由工程技術中產生的大型稀疏矩陣方程組（A的階數n很大，但零元素較多），利用迭代法求解是適合的。在計算機內存和運算兩方面，迭代通常都可利用A中有大量零元素的特點。考慮線性方程組6.1引言本章將介紹迭代法的一般理論及雅可比迭代法、高斯—塞德爾迭代法、超松弛迭代法，研究它們的收斂性。6.2基本迭代一、雅可比迭代法二、高斯—塞德爾迭代法SOR迭代法的計算公式:對k=0,1,…,三、逐次超松馳(SOR)迭代法說明:1)ω=1,即為GS（高斯-賽德爾迭代法）;2)ω>1，稱為超松馳法；

ω<1，稱為低松馳法；3)SOR方法每迭代一次主要運算量是計算一次矩陣與向量的乘法。例6-3

用SOR迭代法解線性代數方程組6.3迭代法的收斂性一、一階定常迭代法的基本定理

注：定理5中的矩陣是迭代矩陣，常用格式的迭代矩陣如下：1)雅可比迭代法:BJ=D-1(L+U)，fJ=D-1b;2)高斯-賽德爾迭代法:BG=(D-L)-1U，fG==(D-L)-1b;3)SOR迭代法:BSOR=(D-ωL)-1{(1-ω)D+ωU}，fSOR=ω(D-ωL)-1b.例6-4考察用雅可比迭代法求解線性方程組二、某些特殊方程組的迭代收斂性定義3（1）按行嚴格對角占優（2）按行弱對角占優上式至少有一個不等號嚴格成立。定理8(對角占優定理)若矩陣A按行(或列)嚴格對角占優，或按行(或列)弱對角占優且不可約；則矩陣A非奇異。

定理9若矩陣A按行(或列)嚴格對角占優,或按行(或列)弱對角占優不可約；則Jacobi迭代、Gauss-Seidel迭代都收斂。定理12對于線性方程組Ax=b，若(1)A為對稱正定矩陣，(2)0<ω<2，則解Ax=b的SOR迭代收斂。

定理13對于線性代數方程組Ax=b，若A按行(或列)嚴格對角占優，或按行(或列)弱對角占優不可約；則當0<ω≤1時，SOR迭代收斂。知識結構圖六迭代法解方程組迭代法基本概念高斯-賽德爾迭代法迭代格式收斂條件（充要條件、充分條件四個）SQR迭代法迭代法收斂速度雅可比迭代法迭代格式收斂條件（充要條件、充分條件四個）迭代格式收斂條件（充要條件、必要條件、充分條件五個）第七章解非線性方程求根內容提要7.1方程求根與二分法7.2迭代法及其收斂性7.3牛頓法7.4弦截法7.1方程求根與二分法一、引言非線性方程的分類由此可知方程的有根區間為[1,2][3,4][5,6]求根問題的三個方面：存在性，分布，精確化。二、二分法0xyX*x0aby=f(x)a1b1二分法的優點是算法簡單，且總是收斂的，缺點是收斂太慢,故一般不單獨將其用于求根，只用其為根求得一個較好的近似值。7.2迭代法一、不動點迭代與不動點迭代法上述迭代法是一種逐次逼近法，其基本思想是將隱式方程歸結為一組顯示的計算公式，就是說，迭代過程實質上是一個逐步顯示的過程。繼續迭代下去已經沒有必要，因為結果顯然會越來越大，不可能趨于某個極限。這種不收斂的迭代過程稱作是發散的。一個發散的迭代過程，縱使進行了千百次迭代，其結果也毫無價值。因此，迭代格式形式不同，有的收斂，有的發散，只有收斂的迭代過程才有意義，為此要研究不動點的存在性及迭代法的收斂性。二、不動點的存在性與迭代法的收斂性三、局部收斂性與收斂階7.3牛頓法一、牛頓法及其收斂性二、牛頓法應用舉例三、簡化牛頓法與牛頓下山法四、重根情形7.4弦截法知識結構圖七方程近似求根基本概念（單根、重根、有根區間、不動點、收斂階）求根