李慶揚(yáng)版數(shù)值分析 全套ppt課件

1、數(shù)值分析講義（李慶揚(yáng)等《數(shù)值分析》）,臨港四校研究生課程,,第1章 緒 論（不考）,內(nèi)容提要：1.1 數(shù)值分析研究對(duì)象與特點(diǎn)1.2 數(shù)值計(jì)算的誤差1.3 誤差定性分析與避免誤差危害,1.1 數(shù)值分析研究對(duì)象與特點(diǎn)一、數(shù)值分析研究對(duì)象計(jì)算機(jī)解決科學(xué)計(jì)算問題時(shí)經(jīng)歷的過程,實(shí)際問題,模型設(shè)計(jì),算法設(shè)計(jì),問題的解,上機(jī)計(jì)算,程序設(shè)計(jì),,,,,,,求,,方程求根,,牛頓法,,,,程序設(shè)計(jì),,解,上機(jī)計(jì)算,實(shí)例,數(shù)值分析的內(nèi)容包括函數(shù)

2、的數(shù)值逼近、數(shù)值微分與數(shù)值積分、非線性方程數(shù)值解、數(shù)值線性代數(shù)、常微和偏微數(shù)值解等。數(shù)值分析研究對(duì)象以及解決問題方法的廣泛適用性，著名流行軟件如Maple、Matlab、Mathematica等已將其絕大多數(shù)內(nèi)容設(shè)計(jì)成函數(shù)，簡單調(diào)用之后便可以得到運(yùn)行結(jié)果。 但由于實(shí)際問題的具體特征、復(fù)雜性, 以及算法自身的適用范圍決定了應(yīng)用中必須選擇、設(shè)計(jì)適合于自己特定問題的算法，因而掌握數(shù)值方法的思想和內(nèi)容是至關(guān)重要的。 本課程內(nèi)

3、容包括了微積分、代數(shù)、常微分方程的數(shù)值方法，必須掌握這幾門課程的基礎(chǔ)內(nèi)容才能學(xué)好這門課程。,二、數(shù)值分析的特點(diǎn)面向計(jì)算機(jī)，要根據(jù)計(jì)算機(jī)的特點(diǎn)提供切實(shí)可行的有效算法。有可靠的理論分析，能任意逼近并達(dá)到精度要求，對(duì)近似算法要保證收斂性和數(shù)值穩(wěn)定性，還要對(duì)誤差進(jìn)行分析。這些都是建立在數(shù)學(xué)理論的基礎(chǔ)上，因此不應(yīng)片面的將數(shù)值分析理解為各種數(shù)值方法的簡單羅列和堆積。要有好的計(jì)算復(fù)雜性，時(shí)間復(fù)雜性好是指節(jié)省時(shí)間，空間復(fù)雜性好是指節(jié)省存儲(chǔ)量，這也

4、是建立算法要研究的問題，它關(guān)系到算法能否在計(jì)算機(jī)上實(shí)現(xiàn)。要有數(shù)值實(shí)驗(yàn)，即任何一個(gè)算法除了從理論上要滿足上述三點(diǎn)外，還要通過數(shù)值實(shí)驗(yàn)證明是行之有效的。,三、數(shù)值分析的學(xué)習(xí)方法 初學(xué)可能仍會(huì)覺得公式多，理論分析復(fù)雜。給出如下的幾點(diǎn)學(xué)習(xí)方法。認(rèn)識(shí)建立算法和對(duì)每個(gè)算法進(jìn)行理論分析是基本任務(wù)，主動(dòng)適應(yīng)公式多和講究理論分析的特點(diǎn)。注重各章節(jié)所研究算法的提出，掌握方法的基本原理和思想，要注意方法處理的技巧及其與計(jì)算機(jī)的結(jié)合。理解每個(gè)算法

5、建立的數(shù)學(xué)背景、數(shù)學(xué)原理和基本線索，而且對(duì)一些最基本的算法要非常熟悉。要通過例子，學(xué)習(xí)使用各種數(shù)值方法解決實(shí)際計(jì)算問題。為掌握本課的內(nèi)容，還應(yīng)做一些理論分析和計(jì)算練習(xí)。,1.2 數(shù)值計(jì)算的誤差,一、誤差的來源 在運(yùn)用數(shù)學(xué)方法解決實(shí)際問題的過程中，每一步都可能帶來誤差。1、模型誤差 在建立數(shù)學(xué)模型時(shí)，往往要忽視很多次要因素，把模型“簡單化”，“理想化”，這時(shí)模型就與真實(shí)背景有了差距，即帶入了誤差。2、測量誤差 數(shù)學(xué)

6、模型中的已知參數(shù)，多數(shù)是通過測量得到。而測量過程受工具、方法、觀察者的主觀因素、不可預(yù)料的隨機(jī)干擾等影響必然帶入誤差。,3、截?cái)嗾`差 數(shù)學(xué)模型常難于直接求解，往往要近似替代，簡化為易于求解的問題，這種簡化帶入誤差稱為方法誤差或截?cái)嗾`差。,4、舍入誤差 計(jì)算機(jī)只能處理有限數(shù)位的小數(shù)運(yùn)算，初始參數(shù)或中間結(jié)果都必須進(jìn)行四舍五入運(yùn)算，這必然產(chǎn)生舍入誤差。,誤差分析是一門比較艱深的專門學(xué)科。在數(shù)值分析中主要討論截?cái)嗾`差及舍入誤差。但一個(gè)訓(xùn)練有素

7、的計(jì)算工作者，當(dāng)發(fā)現(xiàn)計(jì)算結(jié)果與實(shí)際不符時(shí)，應(yīng)當(dāng)能診斷出誤差的來源，并采取相應(yīng)的措施加以改進(jìn)，直至建議對(duì)模型進(jìn)行修改。二、絕對(duì)誤差、相對(duì)誤差與有效數(shù)字1、絕對(duì)誤差與絕對(duì)誤差限,誤差是有量綱的量，量綱同 x，它可正可負(fù)。 誤差一般無法準(zhǔn)確計(jì)算，只能根據(jù)測量或計(jì)算情況估計(jì)出它的絕對(duì)值的一個(gè)上界，這個(gè)上界稱為近似值 x* 的誤差限，記為ε*。,2、相對(duì)誤差與相對(duì)誤差限,3、有效數(shù)字 定義3 如果近似值x*的誤差限是它某一數(shù)位的半

8、個(gè)單位，我們就說 x *準(zhǔn)確到該位，從這一位起直到前面第一個(gè)非零數(shù)字為止的所有數(shù)字稱 x 的有效數(shù)字.,,,4、絕對(duì)誤差，相對(duì)誤差與有效數(shù)字的關(guān)系 絕對(duì)誤差與相對(duì)誤差：由兩者定義可知。,絕對(duì)誤差與有效數(shù)字：絕對(duì)誤差不超過末位有效數(shù)字的半個(gè)單位。,有效數(shù)字與相對(duì)誤差限,定理說明有效數(shù)位越多，相對(duì)誤差限越小。定理也給出了相對(duì)誤差限的求法。,三、數(shù)值運(yùn)算的誤差估計(jì)1、四則運(yùn)算,2、函數(shù)誤差 當(dāng)自變量有誤差時(shí)計(jì)算函

9、數(shù)值也產(chǎn)生誤差，可以利用函數(shù)的泰勒展開式進(jìn)行估計(jì)。,,1.3 誤差定性分析與避免誤差危害一、病態(tài)問題與條件數(shù)1、病態(tài)問題：對(duì)一個(gè)數(shù)值問題本身如果輸入數(shù)據(jù)有微小擾動(dòng)（即誤差），引起輸出數(shù)據(jù)（即問題解）相對(duì)誤差很大，就是病態(tài)問題。,二、算法的穩(wěn)定性 用一個(gè)算法進(jìn)行計(jì)算，由于初始數(shù)據(jù)誤差在計(jì)算中傳播使計(jì)算結(jié)果誤差增長很快就是數(shù)值不穩(wěn)定的，先看下例。,計(jì)算結(jié)果：,,,,,,n,法一 (A),法二 (B),012345

10、6789,0.63210.36790.26420.20740.17040.14800.11200.2160-0.72807.552,0.63210.36790.26430.20730.17080.14550.12680.11210.10350.0684,三、避免誤差危害的若干原則1、要避免除數(shù)絕對(duì)值遠(yuǎn)遠(yuǎn)小于被除數(shù)絕對(duì)值的除法。 用絕對(duì)值小的數(shù)作除數(shù)舍入誤差會(huì)增大，如計(jì)算 x/y，

11、若0<|y|<<|x|，則可能對(duì)計(jì)算結(jié)果帶來嚴(yán)重影響，應(yīng)盡量避免。,2、要避免兩相近數(shù)相減 在數(shù)值中兩相近數(shù)相減有效數(shù)字會(huì)嚴(yán)重?fù)p失。例如，x=532.65，y=532.52都具有五位有效數(shù)字，但x - y=0.13只有兩位有效數(shù)字。通過改變算法可以避免兩相近數(shù)相減。,3、要防止“大數(shù)”吃掉小數(shù) 數(shù)值運(yùn)算中參加運(yùn)算的數(shù)有時(shí)數(shù)量級(jí)相差很大，而計(jì)算機(jī)位數(shù)有限，如不注意運(yùn)算次序

12、就可能出現(xiàn)大數(shù)“吃掉”小數(shù)的現(xiàn)象，影響計(jì)算結(jié)果的可靠性。 如用六位浮點(diǎn)數(shù)計(jì)算某市的工業(yè)總產(chǎn)值，原始數(shù)據(jù)是各企業(yè)的工業(yè)產(chǎn)值，當(dāng)加法進(jìn)行到一定程度，部分和超過100億元 （0.1×1011），再加產(chǎn)值不足10萬元的小企業(yè)產(chǎn)值，將再也加不進(jìn)去。而這部分企業(yè)可能為數(shù)不少，合計(jì)產(chǎn)值相當(dāng)大.這種情況應(yīng)將小數(shù)先分別加成大數(shù)，然后相加，結(jié)果才比較正確。這個(gè)例子告訴我們，在計(jì)算機(jī)數(shù)系中，加法的交換律和結(jié)合律可能不成立，這是在大規(guī)模

13、數(shù)據(jù)處理時(shí)應(yīng)注意的問題。,4、注意簡化計(jì)算步驟，減少運(yùn)算次數(shù) 減少算術(shù)運(yùn)算的次數(shù)不但可計(jì)算機(jī)的計(jì)算時(shí)間，還能減少誤差的積累效應(yīng)。使參加運(yùn)算的數(shù)字精度應(yīng)盡量保持一致，否則那些較高精度的量的精度沒有太大意義。,誤差及算法,,誤差,算法,,數(shù)值穩(wěn)定性概念,算法設(shè)計(jì)注意要點(diǎn),,分類,度量,傳播,,舍入誤差的產(chǎn)生及定義,截?cái)嗾`差的產(chǎn)生及定義,,絕對(duì)誤差（限）,相對(duì)誤差（限）,有效數(shù)字,三者的聯(lián)系,,一元函數(shù),n元函數(shù),計(jì)算函數(shù)

14、值問題的條件數(shù),二元算術(shù)運(yùn)算,知識(shí)結(jié)構(gòu)圖一,第2章 插 值 法,內(nèi)容提要2.1 引言2.2 拉格朗日插值2.3 均差與牛頓插值公式2.4 埃爾米特插值2.5 分段低次插值2.6 三次樣條插值,2.1 引言 許多實(shí)際問題都用函數(shù) y=f(x) 來表示某種內(nèi)在規(guī)律的數(shù)量關(guān)系。若已知 f(x) 在某個(gè)區(qū)間 [a,b] 上存在、連續(xù)，但只能給出 [a,b] 上一系列點(diǎn)的函數(shù)值表時(shí)，或者函數(shù)有解析表達(dá)式

15、，但計(jì)算過于復(fù)雜、使用不方便只給出函數(shù)值表（如三角函數(shù)表、對(duì)數(shù)表等）時(shí)，為了研究函數(shù)的變化規(guī)律，往往需要求出不在表上的函數(shù)值。因此我們希望根據(jù)給定的函數(shù)表做一個(gè)既能 反映函數(shù) f(x) 的特性，又便于計(jì)算的簡單函數(shù) P(x)，用 P(x) 近似 f(x)。這就引出了插值問題。,1、提出問題（插值法的定義）,,,,,,,2、幾何意義、外插、內(nèi)插,,,,,,,,,,P(x) ? f(x),x*(外插),x0,x1,x(內(nèi)插),x2,x3

16、,P(x*) ? f(x*),3、插值的種類 選取不同的函數(shù)族構(gòu)造 P(x) 得到不同類型的插值若 P(x) 是次數(shù)不超過 n 的代數(shù)多項(xiàng)式，就稱為多項(xiàng)式插值；若 P(x) 為分段的多項(xiàng)式，就稱為分段插值；若 P(x) 為三角多項(xiàng)式，就稱為三角插值。 本章只討論多項(xiàng)式插值與分段插值。主要研究內(nèi)容為如何求出插值多項(xiàng)式，分段插值函數(shù)；討論插值多項(xiàng)式 P(x) 的存在唯一性、收斂性及估計(jì)誤差等。4、多項(xiàng)式插值

17、問題,插值多項(xiàng)式的存在唯一性,定理1 (存在唯一性) 滿足插值條件的不超過 n 次的插值多項(xiàng)式是存在唯一的。,2.2 拉格朗日插值一、線性插值與拋物插值1、線性插值,2、拋物插值,,求解基函數(shù),二、拉格朗日插值多項(xiàng)式 上面針對(duì) n=1 和 n=2 的情況，得到了一次和二次插值多項(xiàng)式，這種用基函數(shù)表示的方法很容易推廣到一般情況。下面討論如何構(gòu)造 n+1 個(gè)節(jié)點(diǎn)的 n 次插值多項(xiàng)式。,,定理表明：(1) 插值誤差與節(jié)點(diǎn)

18、和點(diǎn) x 之間的距離有關(guān), 節(jié)點(diǎn)距離 x 越近,插值誤差一般情況下越小。 (2) 若被插值函數(shù) f(x) 本身就是不超過 n 次的多項(xiàng)式, 則有f(x)≡g(x)。,3、應(yīng)用舉例,用二次插值計(jì)算 ln(11.25) 的近似值,并估計(jì)誤差。,例2-2 給定函數(shù)值表,在區(qū)間[10,12]上lnx 的三階導(dǎo)數(shù) (2/x3) 的上限 M3=0.002,可得誤差估計(jì)式,注：實(shí)際上,ln(11.25)=2.420368,

19、 |R2(11.25)|=0.000058,0,?,分析：求解如上問題等價(jià)于求解x關(guān)于y的反函數(shù)問題。,2.3 均差與牛頓插值公式一、均差及其性質(zhì) 問題的引入：拉格朗日插值多項(xiàng)式，公式結(jié)構(gòu)緊湊，理論分析方便，但插值節(jié)點(diǎn)增減時(shí)全部插值及函數(shù)均要隨之變化，實(shí)際計(jì)算不方便，希望把公式表示為如下形式。,,,1、均差定義,2、均差的基本性質(zhì),2、均差的基本性質(zhì),2、均差的基本性質(zhì),均差計(jì)算表,,,,,,,,例如 由函數(shù)y=

20、?(x)的函數(shù)表寫出均差表.,解 均差表如下,二、牛頓插值公式,,,解 由差商表知?[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 對(duì)例如中的 ?(x),求節(jié)點(diǎn)為 x0,x1 的

21、一次插值，x0,x1,x2 的二次插值和 x0,x1,x2,x3 的三次插多項(xiàng)式.,例2-7 給出 f(x) 的函數(shù)表，求4次牛頓插值多項(xiàng)式，并計(jì)算f(0.596) 的近似值。,,,,,,,,,,,,2.4 埃爾米特插值 不少實(shí)際的插值問題不但要求在節(jié)點(diǎn)上函數(shù)值相等，而且還要求對(duì)應(yīng)的導(dǎo)數(shù)值也相等，甚至要求高階導(dǎo)數(shù)也相等，滿足這種要求的插值多項(xiàng)式就是埃爾米特（Hermite）插值多項(xiàng)式。,y=L10(x),,y=L

22、10(x),,解法二（用重節(jié)點(diǎn)的均差表建立埃爾米特多項(xiàng)式）,,2.5 分段低次插值一、高次插值的病態(tài)性質(zhì) 一般總認(rèn)為Ln(x)的次數(shù)n越高逼近f(x)的精度越好，但實(shí)際上并非如此。這是因?yàn)閷?duì)任意的插值節(jié)點(diǎn)，當(dāng)n->∞時(shí)， Ln(x)不一定收斂于f(x)。20世紀(jì)初龍格（Runge）就給了一個(gè)等距節(jié)點(diǎn)插值多項(xiàng)式Ln(x)不一定收斂于f(x)的例子。,y=L10(x),,,,x,,1,,,,y=L10(x),o,-1,0.

23、5,,y,1.5,,,,,,,1,龍格現(xiàn)象,二、分段線性插值分段線性插值就是通過插值點(diǎn)用折線段連接起來逼近f(x).,分段線性插值,三、分段拋物插值,三、分段拋物插值,2.6 三次樣條插值 樣條曲線實(shí)際上是由分段三次曲線并接而成，在連接點(diǎn)即樣點(diǎn)上要求二階導(dǎo)數(shù)連續(xù)，從數(shù)學(xué)上加以概括就得到數(shù)學(xué)樣條這一概念。下面我們討論最常用的三次樣條函數(shù)。一、三次樣條函數(shù),y=L10(x),,每個(gè)小區(qū)間上要確定4個(gè)待定系數(shù)，共有n個(gè)小

24、區(qū)間，故應(yīng)確定4n個(gè)參數(shù)。,y=L10(x),,二、三次樣條插值函數(shù)的建立,y=L10(x),,y=L10(x),,y=L10(x),,y=L10(x),,系數(shù)矩陣為嚴(yán)格對(duì)角占優(yōu)陣，方程組有為一解。求法見5.3節(jié)追趕法。,y=L10(x),,y=L10(x),,知識(shí)結(jié)構(gòu)圖二,插值法,,工具,分段多項(xiàng)式插值,,,存在唯一性,多項(xiàng)式插值,Hermite插值,,,插值公式,誤差估計(jì),,,差商、差分,Lagrange插值基及函數(shù),

25、,定義性質(zhì),定義性質(zhì),導(dǎo)數(shù)型差商型,,Lagrange插值多項(xiàng)式Newton插值多項(xiàng)式 等距節(jié)點(diǎn)插值公式,存在唯一性誤差估計(jì) 插值公式,分段線性插值（公式、誤差估計(jì)、收斂性）,分段三次Hermite插值（公式、誤差估 計(jì)、收斂性）,三次樣條插值（公式、存在唯一

26、 性、誤差估計(jì)、收斂性）,第三章函數(shù)逼近,內(nèi)容提要3.1 基本概念3.2 最佳平方逼近3.3 曲線擬合的最小二乘法,3.1基本概念,,,,,,,,,x0,x3,x5,x7,,,,x1,x4,x6,x2,f(x),p(x),,,2、范數(shù)與賦范線性空間,3、內(nèi)積與內(nèi)積空間,1、最佳平方逼近,3.2 最佳平方逼近,,,,一、最小二乘法及其計(jì)算,3.3 曲線擬合的最小二乘法,,,例3-3 已知實(shí)測數(shù)據(jù)表如下,求它的擬合曲線,例

27、3-4 已知實(shí)測數(shù)據(jù)表如下,確定數(shù)學(xué)模型 y=aebx,用最小二乘法確定a，b。,分析：根據(jù)給定數(shù)據(jù)描圖也可確定擬合曲線方程，但它不是線性形式。因此首先要將經(jīng)驗(yàn)曲線線性化。本題可以采取等式兩邊取對(duì)數(shù)的形式線性化。數(shù)據(jù)表中的數(shù)值也相應(yīng)的轉(zhuǎn)化為取對(duì)數(shù)之后的數(shù)值，見下表。,知識(shí)結(jié)構(gòu)圖三,函數(shù)逼近理論,,預(yù)備知識(shí),,范數(shù)（定義、常用范數(shù)）,內(nèi)積（定義、柯西-施瓦茨不等 式、內(nèi)積誘導(dǎo)范數(shù)）,正交多項(xiàng)式（性質(zhì)、正交

28、化方法、常用正 交多項(xiàng)式的定義和性質(zhì)）,,函數(shù)逼近方法,,最佳一致逼近多項(xiàng)式,最佳平方逼近,,定義存在唯一性定理切比雪夫定理最佳一次逼近多項(xiàng)式的確定,最小二乘擬合,,定義法方程組和平方誤差基于正交基的最佳平方逼近,,離散內(nèi)積定義法方程組及哈爾條件基于正交基的最小二乘擬合,第四章 數(shù)值積分和數(shù)值微分,內(nèi)容提要4.1 引言4.2 牛頓-柯特斯公式4.3 復(fù)化求積公式4.4 龍

29、貝格求積公式4.5 高斯求積公式4.6 數(shù)值微分,4.1 引言一、數(shù)值求積的基本思想 對(duì)定義在區(qū)間［a,b］上的定積分,但有時(shí)原函數(shù)不能用初等函數(shù)表示，有時(shí)原函數(shù)又十分復(fù)雜，難于求出或計(jì)算；另外如被積函數(shù)是由測量或數(shù)值計(jì)算給出的一張數(shù)據(jù)表示時(shí)，上述方法也不能直接運(yùn)用。因此有必要研究積分的數(shù)值計(jì)算問題。,積分中值定理告訴我們：,平均高度,,梯形公式,,平均高度,中矩形公式,,平均高度,更一般地，我們構(gòu)造具

30、有下列形式的求積公式,求積節(jié)點(diǎn),,,求積系數(shù),這類數(shù)值方法通常稱為機(jī)械求積，其特點(diǎn)是將積分求值問題歸結(jié)為函數(shù)值的計(jì)算，這就避開了牛頓-萊布尼茲公式需要尋求原函數(shù)的困難。,二、代數(shù)精度的概念,利用代數(shù)精度的概念構(gòu)造求積公式,三、插值型的求積公式,4.2 牛頓-柯特斯公式一、牛頓-柯特斯公式的導(dǎo)出,柯特斯系數(shù),,牛頓-柯特斯公式的代數(shù)精度,4.3 復(fù)合求積公式 一、問題與基本思想 在使用牛頓-柯特斯公式時(shí)將導(dǎo)致求積系數(shù)出

31、現(xiàn)負(fù)數(shù)(當(dāng)n≥8時(shí),牛頓.柯特斯求積系數(shù)會(huì)出現(xiàn)負(fù)數(shù))，因而不可能通過提高階的方法來提高求積精度。為了提高精度通常采用將積分區(qū)間劃分成若干個(gè)小區(qū)間，在各小區(qū)間上采用低次的求積公式(梯形公式或辛普森公式)，然后再利用積分的可加性，把各區(qū)間上的積分加起來，便得到新的求積公式，這就是復(fù)化求積公式的基本思想。本節(jié)只討論復(fù)化的梯形公式和復(fù)化的辛普森公式。,二、復(fù)合梯形公式,三、復(fù)合辛普森公式,4.4 龍貝格求積公式 一、梯形法的遞推化 (變

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

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

34、 一、一般理論,4.6 數(shù)值微分一、中點(diǎn)方法與誤差分析 數(shù)值微分就是要用函數(shù)值的線性組合近似函數(shù)在某點(diǎn)的導(dǎo)數(shù)值。由導(dǎo)數(shù)定義差商近似導(dǎo)數(shù)得到數(shù)值微分公式。,二、插值型的求導(dǎo)公式,知識(shí)結(jié)構(gòu)圖四,數(shù)值積分與數(shù)值微分,,數(shù)值積分,,基本概念,牛頓-柯特斯公式,復(fù)合求積公式,,數(shù)值微分,,中點(diǎn)方法,插值型求導(dǎo)公式,龍貝格求積公式,高斯求積公式,第五章 解線性方程組的直接方法,內(nèi)容提要5.1 引言與預(yù)備知

35、識(shí)5.2 高斯消去法5.3 高斯列主元消去法5.4 矩陣三角分解法5.5 向量與矩陣的范數(shù)5.6 誤差分析,5.1 引言,關(guān)于線性方程組的數(shù)值解法一般有兩類：1、直接解法：經(jīng)過有限次的算術(shù)運(yùn)算，可求得方程組精確解的方法（若計(jì)算過程中沒有舍入誤差）。但實(shí)際計(jì)算中由于舍入誤差的存在和影響，這種方法也只能求得線性方程組的近似解。本章主要研究此類問題的解法。2、迭代法：用某種極限過程去逐步逼近現(xiàn)行方程組精確解的方法。迭

36、代法具有需要計(jì)算機(jī)的存儲(chǔ)單元較少、程序設(shè)計(jì)簡單、原始系數(shù)矩陣在計(jì)算過程中始終不變等優(yōu)點(diǎn)。,,,,5.2 高斯消去法,,,,在求解三角方程組,得,高斯消去法的條件,5.3 高斯主元素消去法,列主元消去法,,,,,,,,5.4 矩陣三角分解法,Ax=b是線性方程組,A是n×n方陣,并設(shè)A的各階順序主子式不為零。令 A(1)=A,當(dāng)高斯消元法進(jìn)行第一步后,相當(dāng)于用一個(gè)初等矩陣左乘A(1) 。不難看出，這個(gè)初等矩陣為,重復(fù)

37、這個(gè)過程，最后得到,一般地,這就是說，高斯消去法實(shí)質(zhì)上產(chǎn)生了一個(gè)將A分解為兩個(gè)三角形矩陣相乘的因式分解，于是我們得到如下重要定理。,,當(dāng)A進(jìn)行LU分解后，Ax=b就容易解了. 即Ax=b等價(jià)于:,,,,,追趕法 在一些實(shí)際問題中， 例如解常微分方程邊值問題，熱傳導(dǎo)方程以及船體數(shù)學(xué)放樣中建立三次樣條函數(shù)等，都會(huì)要求解系數(shù)矩陣為對(duì)角占優(yōu)的三對(duì)角線方程組,其中|i-j|>1時(shí),aij=0,且滿足如下的對(duì)角占優(yōu)條件:(1)

38、|b1|>|c1|>0,|bn|>|an|>0(2)|bi|≥|ai|+|ci|, aici≠0, i=2,3,…,n-1.,5.5 向量和矩陣的范數(shù),定義1 ( 向量范數(shù)) x 和 y 是 Rn 中的任意向量 , 向量范數(shù)‖?‖是定義在 Rn上的實(shí)值函數(shù), 它滿足:,(1) ‖ x ‖≥0, 并且當(dāng)且僅當(dāng) x=0 時(shí), ‖ x ‖=0;,(2) ‖k x ‖=|k| ‖ x ‖, k 是一個(gè)實(shí)數(shù);,(3

39、) ‖ x + y ‖≤ ‖ x ‖+ ‖ y ‖,常使用的向量范數(shù)有三種,設(shè) x=(x1,x2,…,xn)T,常使用的矩陣范數(shù)有三種,設(shè) x=(x1,x2,…,xn)T,5.6 誤差分析,知識(shí)結(jié)構(gòu)圖五,直接法解方程組,,高斯消去法,矩陣的正交三角化及應(yīng)用,,,,定義常用范數(shù)范數(shù)的性質(zhì),初等反射陣平面旋轉(zhuǎn)變換矩陣矩陣的QR分解應(yīng)用：求解超定方程組,高斯消去法高斯若當(dāng)消去法列主元消去法,矩陣三角分

40、解法,LU分解平方根分解LDLT分解,追趕法解三對(duì)角方程組,向量和矩陣的范數(shù),,矩陣條件數(shù)及迭代改善法,第六章解線性代數(shù)方程組的迭代法,內(nèi)容提要6.1 引言6.2 基本迭代法6.3 迭代法的收斂性,即AX=b 其中A為非奇異矩陣，當(dāng)A為低階稠密矩陣時(shí)，線性方程組用直接法(如高斯消去法和三角分解法)是有效的，但對(duì)于由工程技術(shù)中產(chǎn)生的大型稀疏矩陣方程組（A的階數(shù)n很大，但零元素較多），利用迭代法求解是適合的。在計(jì)算機(jī)內(nèi)存和

41、運(yùn)算兩方面，迭代通常都可利用A中有大量零元素的特點(diǎn)。,考慮線性方程組,6.1 引言,本章將介紹迭代法的一般理論及雅可比迭代法、高斯—塞德爾迭代法、超松弛迭代法，研究它們的收斂性。,,,6.2 基本迭代,,,,一、雅可比迭代法,,,,,二、高斯—塞德爾迭代法,SOR迭代法的計(jì)算公式:對(duì)k=0,1,…,,三、逐次超松馳(SOR)迭代法,,說明: 1)ω=1,即為GS（高斯-賽德爾迭代法）; 2)ω>1，稱為超松

42、馳法； ω<1，稱為低松馳法； 3) SOR方法每迭代一次主要運(yùn)算量是計(jì)算一次矩陣 與向量的乘法。,例6-3 用SOR迭代法解線性代數(shù)方程組,6.3 迭代法的收斂性一、一階定常迭代法的基本定理,注：定理5中的矩陣是迭代矩陣，常用格式的迭代矩陣如下：,1) 雅可比迭代法: BJ=D-1(L+U)，fJ=D-1b;2) 高斯-賽德爾迭代法: BG=(D-L)-

43、1U，fG= =(D-L)-1b;3) SOR迭代法: BSOR=(D-ωL)-1{(1-ω)D+ωU}，fSOR=ω(D-ωL)-1b.,例6-4 考察用雅可比迭代法求解線性方程組,二、某些特殊方程組的迭代收斂性,定義3 （1）按行嚴(yán)格對(duì)角占優(yōu),（2）按行弱對(duì)角占優(yōu),上式至少有一個(gè)不等號(hào)嚴(yán)格成立。,定理8(對(duì)角占優(yōu)定理)若矩陣A按行(或列)嚴(yán)格對(duì)角占優(yōu)，或 按行(或列)弱對(duì)角占優(yōu)且不可約；則矩陣A非奇異。,定理9 若矩

44、陣A按行(或列)嚴(yán)格對(duì)角占優(yōu),或按行(或列)弱對(duì) 角占優(yōu)不可約；則Jacobi迭代、Gauss-Seidel迭代都收斂。,定理12 對(duì)于線性方程組Ax=b，若(1) A為對(duì)稱正定矩陣，(2)0<ω<2，則解Ax=b的SOR迭代收斂。,定理13 對(duì)于線性代數(shù)方程組Ax=b， 若A按行(或列)嚴(yán)格對(duì)角占優(yōu)，或按行(或列)弱對(duì)角占優(yōu)不可約；則當(dāng)0<ω≤1時(shí)，SOR迭代收斂。,知識(shí)結(jié)構(gòu)圖六,迭代法解方程

45、組,,迭代法基本概念,,高斯-賽德爾迭代法,迭代格式收斂條件（充要條件、充分條件四個(gè)）,SQR迭代法,,迭代法收斂速度,雅可比迭代法,,迭代格式收斂條件（充要條件、充分條件四個(gè)）,迭代格式收斂條件（充要條件、必要條件、 充分條件五個(gè)）,第七章解非線性方程求根,內(nèi)容提要7.1 方程求根與二分法7.2 迭代法及其收斂性7.3 牛頓法7.4 弦截法,7.1 方程求根與二分法一、引言,非線

46、性方程的分類,由此可知方程的有根區(qū)間為[1,2] [3,4] [5,6]求根問題的三個(gè)方面：存在性，分布，精確化。,二、二分法,,,,,,0,x,y,X*,x0,,a,b,y=f(x),a1,b1,二分法的優(yōu)點(diǎn)是算法簡單，且總是收斂的，缺點(diǎn)是收斂太慢,故一般不單獨(dú)將其用于求根，只用其為根求得一個(gè)較好的近似值。,7.2 迭代法一、不動(dòng)點(diǎn)迭代與不動(dòng)點(diǎn)迭代法,上述迭代法是一種逐次逼近法，其基本思想是將隱式方程歸結(jié)為一組顯示的計(jì)算公式

47、，就是說，迭代過程實(shí)質(zhì)上是一個(gè)逐步顯示的過程。,繼續(xù)迭代下去已經(jīng)沒有必要，因?yàn)榻Y(jié)果顯然會(huì)越來越大，不可能趨于某個(gè)極限。這種不收斂的迭代過程稱作是發(fā)散的。一個(gè)發(fā)散的迭代過程，縱使進(jìn)行了千百次迭代，其結(jié)果也毫無價(jià)值。因此，迭代格式形式不同，有的收斂，有的發(fā)散，只有收斂的迭代過程才有意義，為此要研究不動(dòng)點(diǎn)的存在性及迭代法的收斂性。,二、不動(dòng)點(diǎn)的存在性與迭代法的收斂性,,,三、局部收斂性與收斂階,7.3 牛頓法一、牛頓法及其收斂性

48、,二、牛頓法應(yīng)用舉例,三、簡化牛頓法與牛頓下山法,四、重根情形,7.4 弦截法,知識(shí)結(jié)構(gòu)圖七,方程近似求根,,基本概念（單根、重根、有根區(qū)間、不動(dòng)點(diǎn)、收斂階）,,求根方法,二分法及其收斂性不動(dòng)點(diǎn)迭代法及其收斂性定理（不動(dòng)點(diǎn)迭代法的加速技巧）牛頓迭代法及其收斂性插值型迭代法（多點(diǎn)迭代）,,弦截法拋物線法,第八章 矩陣特征值問題計(jì)算,內(nèi)容提要8.1 引言8.2 冪法及反冪法,8.1 引言 物理、力

49、學(xué)和工程技術(shù)中很多問題在數(shù)學(xué)上都?xì)w結(jié)為求矩陣的特征值問題。例如，振動(dòng)問題(大型橋梁或建筑物的振動(dòng)、機(jī)械的振動(dòng)、電磁震蕩等)，物理學(xué)中的某些臨界值的確定。它們都?xì)w結(jié)為下述數(shù)學(xué)問題。,8.2 冪法及反冪法,一、冪法冪法是一種求實(shí)矩陣A的按模最大的特征值λ1及其對(duì)應(yīng)的特征向量x1的方法。特別適合于大型稀疏矩陣。,,于是主特征值為：2.5365323；對(duì)應(yīng)特征向量為：(0.7482 0.6497 1) T,二、加速方法,三、反冪法

50、反冪法可求非奇異實(shí)矩陣的按模最小特征值及特征向量。也可用來計(jì)算對(duì)應(yīng)于一個(gè)給定近似特征值的特征向量。,加速后的反冪法計(jì)算公式:,知識(shí)結(jié)構(gòu)圖八,矩陣特征值與特征向量的計(jì)算,,重要概念（特征值，特征向量，正交相似變換， 反射變換，平面旋轉(zhuǎn)變換，QR分解）,,迭代法,冪法（原理、計(jì)算公式、加速技巧）反冪法（原理、計(jì)算方法、加速技巧）,,雅可比方法（原理、方法、收斂性）,,

51、變換法,QR方法,基本QR方法原點(diǎn)平移QR方法雙步原點(diǎn)平移QR方法,第九章 常微分方程初值問題的數(shù)值解法,內(nèi)容提要9.1 引言9.2 簡單的數(shù)值方法與基本概念9.3 龍格-庫塔方法9.4 單步法的收斂性與穩(wěn)定性,9.1 引言 雖然求解微分方程有許多解析方法，但解析方法只能夠求解一些特殊類型的方程，從實(shí)際意義上來講。我們更關(guān)心的是某些 特定的自變量在某一個(gè)定義范圍內(nèi)的一系列離散點(diǎn)上的近似值。一組近似解稱為

52、微分方程在該范圍內(nèi)的數(shù)值解，尋找數(shù)值解的過程稱為數(shù)值求解微分方程。,9.2 簡單的數(shù)值方法與基本概念1、歐拉方法,,,,0,x,y,,P0,,,,,,,,,,,,,P1,P2,Pn-1,Pn,2、后退的歐拉方法,2、后退的歐拉方法,3、梯形方法 等式(3)右端積分中若用梯形公式近似，則得到梯形方法。,4、單步法的局部截?cái)嗾`差與階,5、改進(jìn)的歐拉公式,4、單步法的收斂性,知識(shí)結(jié)構(gòu)圖九,常微分方程初

53、值問題數(shù)值解法,,單步法,,線性多步法,阿達(dá)姆斯顯式與隱式方法米爾尼方法與辛普森方法漢明方法預(yù)測-校正方法,主要方法,,重要概念（截?cái)嗾`差、方法精度、 收斂性、相容性、絕對(duì)穩(wěn)定性等）,主要方法,,歐拉方法梯形方法龍格-庫塔法（包括改進(jìn)的歐拉法）,構(gòu)造方法（數(shù)值積分法、泰勒展開法）,,方程組與高階方程,9.3 龍格-庫塔方法1、顯式龍格-庫塔