第五版數(shù)值分完整析課件

數(shù)值分析電子課件工科研究生公共課程數(shù)學(xué)系列第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ì)算問(wèn)題時(shí)經(jīng)歷的過(guò)程實(shí)際問(wèn)題模型設(shè)計(jì)算法設(shè)計(jì)問(wèn)題的解上機(jī)計(jì)算程序設(shè)計(jì)求方程求根牛頓法

程序設(shè)計(jì)解上機(jī)計(jì)算實(shí)例

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

但由于實(shí)際問(wèn)題的具體特征、復(fù)雜性,以及算法自身的適用范圍決定了應(yīng)用中必須選擇、設(shè)計(jì)適合于自己特定問(wèn)題的算法，因而掌握數(shù)值方法的思想和內(nèi)容是至關(guān)重要的。

本課程內(nèi)容包括了微積分、代數(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ù)值方法的簡(jiǎn)單羅列和堆積。要有好的計(jì)算復(fù)雜性，時(shí)間復(fù)雜性好是指節(jié)省時(shí)間，空間復(fù)雜性好是指節(jié)省存儲(chǔ)量，這也是建立算法要研究的問(wèn)題，它關(guān)系到算法能否在計(jì)算機(jī)上實(shí)現(xiàn)。要有數(shù)值實(shí)驗(yàn)，即任何一個(gè)算法除了從理論上要滿足上述三點(diǎn)外，還要通過(guò)數(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è)算法建立的數(shù)學(xué)背景、數(shù)學(xué)原理和基本線索，而且對(duì)一些最基本的算法要非常熟悉。要通過(guò)例子，學(xué)習(xí)使用各種數(shù)值方法解決實(shí)際計(jì)算問(wèn)題。為掌握本課的內(nèi)容，還應(yīng)做一些理論分析和計(jì)算練習(xí)。1.2數(shù)值計(jì)算的誤差一、誤差的來(lái)源

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

3、有效數(shù)字

定義3如果近似值x*的誤差限是它某一數(shù)位的半個(gè)單位，我們就說(shuō)x*準(zhǔn)確到該位，從這一位起直到前面第一個(gè)非零數(shù)字為止的所有數(shù)字稱x的有效數(shù)字.4、絕對(duì)誤差，相對(duì)誤差與有效數(shù)字的關(guān)系

絕對(duì)誤差與相對(duì)誤差：由兩者定義可知。

絕對(duì)誤差與有效數(shù)字：絕對(duì)誤差不超過(guò)末位有效數(shù)字的半個(gè)單位。有效數(shù)字與相對(duì)誤差限定理說(shuō)明有效數(shù)位越多，相對(duì)誤差限越小。定理也給出了相對(duì)誤差限的求法。三、數(shù)值運(yùn)算的誤差估計(jì)1、四則運(yùn)算2、函數(shù)誤差當(dāng)自變量有誤差時(shí)計(jì)算函數(shù)值也產(chǎn)生誤差，可以利用函數(shù)的泰勒展開式進(jìn)行估計(jì)。1.3誤差定性分析與避免誤差危害一、病態(tài)問(wèn)題與條件數(shù)1、病態(tài)問(wèn)題：對(duì)一個(gè)數(shù)值問(wèn)題本身如果輸入數(shù)據(jù)有微小擾動(dòng)（即誤差），引起輸出數(shù)據(jù)（即問(wèn)題解）相對(duì)誤差很大，就是病態(tài)問(wèn)題。二、算法的穩(wěn)定性

用一個(gè)算法進(jìn)行計(jì)算，由于初始數(shù)據(jù)誤差在計(jì)算中傳播使計(jì)算結(jié)果誤差增長(zhǎng)很快就是數(shù)值不穩(wěn)定的，先看下例。計(jì)算結(jié)果：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、要避免除數(shù)絕對(duì)值遠(yuǎn)遠(yuǎn)小于被除數(shù)絕對(duì)值的除法。用絕對(duì)值小的數(shù)作除數(shù)舍入誤差會(huì)增大，如計(jì)算x/y，若0<|y|<<|x|，則可能對(duì)計(jì)算結(jié)果帶來(lái)嚴(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ù)字。通過(guò)改變算法可以避免兩相近數(shù)相減。3、要防止“大數(shù)”吃掉小數(shù)

數(shù)值運(yùn)算中參加運(yùn)算的數(shù)有時(shí)數(shù)量級(jí)相差很大，而計(jì)算機(jī)位數(shù)有限，如不注意運(yùn)算次序就可能出現(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)行到一定程度，部分和超過(guò)100億元（0.1×1011），再加產(chǎn)值不足10萬(wàn)元的小企業(yè)產(chǎn)值，將再也加不進(jìn)去。而這部分企業(yè)可能為數(shù)不少，合計(jì)產(chǎn)值相當(dāng)大.這種情況應(yīng)將小數(shù)先分別加成大數(shù)，然后相加，結(jié)果才比較正確。這個(gè)例子告訴我們，在計(jì)算機(jī)數(shù)系中，加法的交換律和結(jié)合律可能不成立，這是在大規(guī)模數(shù)據(jù)處理時(shí)應(yīng)注意的問(wèn)題。4、注意簡(jiǎn)化計(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ù)值問(wèn)題的條件數(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í)際問(wèn)題都用函數(shù)y=f(x)來(lái)表示某種內(nèi)在規(guī)律的數(shù)量關(guān)系。若已知f(x)在某個(gè)區(qū)間[a,b]上存在、連續(xù)，但只能給出[a,b]上一系列點(diǎn)的函數(shù)值表時(shí)，或者函數(shù)有解析表達(dá)式，但計(jì)算過(guò)于復(fù)雜、使用不方便只給出函數(shù)值表（如三角函數(shù)表、對(duì)數(shù)表等）時(shí)，為了研究函數(shù)的變化規(guī)律，往往需要求出不在表上的函數(shù)值。因此我們希望根據(jù)給定的函數(shù)表做一個(gè)既能反映函數(shù)f(x)的特性，又便于計(jì)算的簡(jiǎn)單函數(shù)P(x)，用P(x)近似f(x)。這就引出了插值問(wèn)題。1、提出問(wèn)題（插值法的定義）2、幾何意義、外插、內(nèi)插P(x)

f(x)x*(外插)x0x1x(內(nèi)插)x2x3P(x*)

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

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

定理1(存在唯一性)滿足插值條件的不超過(guò)n次的插值多項(xiàng)式是存在唯一的。2.2拉格朗日插值一、線性插值與拋物插值1、線性插值y=f(x)L1(x)yxxk+1xk02、拋物插值求解基函數(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)和點(diǎn)x之間的距離有關(guān),節(jié)點(diǎn)距離x越近,插值誤差一般情況下越小。

(2)若被插值函數(shù)f(x)本身就是不超過(guò)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,|R2(11.25)|=0.0000580

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

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

不少實(shí)際的插值問(wèn)題不但要求在節(jié)點(diǎn)上函數(shù)值相等，而且還要求對(duì)應(yīng)的導(dǎo)數(shù)值也相等，甚至要求高階導(dǎo)數(shù)也相等，滿足這種要求的插值多項(xiàng)式就是埃爾米特（Hermite）插值多項(xiàng)式。

y=L10(x)y=L10(x)解法二（用重節(jié)點(diǎn)的均差表建立埃爾米特多項(xiàng)式）2.5分段低次插值一、高次插值的病態(tài)性質(zhì)一般總認(rèn)為L(zhǎng)n(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)

x1y=L10(x)o-10.5y1.51龍格現(xiàn)象二、分段線性插值分段線性插值就是通過(guò)插值點(diǎn)用折線段連接起來(lái)逼近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è)小區(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ù)定義性質(zhì)定義性質(zhì)導(dǎo)數(shù)型差商型Lagrange插值多項(xiàng)式Newton插值多項(xiàng)式等距節(jié)點(diǎn)插值公式存在唯一性誤差估計(jì)插值公式分段線性插值（公式、誤差估計(jì)、收斂性）分段三次Hermite插值（公式、誤差估計(jì)、收斂性）三次樣條插值（公式、存在唯一性、誤差估計(jì)、收斂性）第三章函數(shù)逼近內(nèi)容提要3.1基本概念3.2最佳平方逼近3.3曲線擬合的最小二乘法3.1基本概念

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

已知實(shí)測(cè)數(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ì)、正交化方法、常用正交多項(xiàng)式的定義和性質(zhì)）函數(shù)逼近方法最佳一致逼近多項(xiàng)式最佳平方逼近定義存在唯一性定理切比雪夫定理最佳一次逼近多項(xiàng)式的確定最小二乘擬合定義法方程組和平方誤差基于正交基的最佳平方逼近離散內(nèi)積定義法方程組及哈爾條件基于正交基的最小二乘擬合第四章數(shù)值積分和數(shù)值微分內(nèi)容提要4.1引言4.2牛頓-柯特斯公式4.3復(fù)化求積公式4.4龍貝格求積公式4.5高斯求積公式4.6數(shù)值微分4.1引言一、數(shù)值求積的基本思想對(duì)定義在區(qū)間［a,b］上的定積分但有時(shí)原函數(shù)不能用初等函數(shù)表示，有時(shí)原函數(shù)又十分復(fù)雜，難于求出或計(jì)算；另外如被積函數(shù)是由測(cè)量或數(shù)值計(jì)算給出的一張數(shù)據(jù)表示時(shí)，上述方法也不能直接運(yùn)用。因此有必要研究積分的數(shù)值計(jì)算問(wèn)題。積分中值定理告訴我們：平均高度f(wàn)(ζ)

a

ζ

b

yxy=f(x)0

a

f((a+b)/2)

b

yxy=f(x)0

a

b

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

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

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

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

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

一、一般理論

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ù)值微分?jǐn)?shù)值積分基本概念牛頓-柯特斯公式復(fù)合求積公式數(shù)值微分中點(diǎn)方法插值型求導(dǎo)公式龍貝格求積公式高斯求積公式第五章解線性方程組的直接方法內(nèi)容提要5.1引言與預(yù)備知識(shí)5.2高斯消去法5.3高斯列主元消去法5.4矩陣三角分解法5.5向量與矩陣的范數(shù)5.6誤差分析5.1引言關(guān)于線性方程組的數(shù)值解法一般有兩類：1、直接解法：經(jīng)過(guò)有限次的算術(shù)運(yùn)算，可求得方程組精確解的方法（若計(jì)算過(guò)程中沒有舍入誤差）。但實(shí)際計(jì)算中由于舍入誤差的存在和影響，這種方法也只能求得線性方程組的近似解。本章主要研究此類問(wèn)題的解法。2、迭代法：用某種極限過(guò)程去逐步逼近現(xiàn)行方程組精確解的方法。迭代法具有需要計(jì)算機(jī)的存儲(chǔ)單元較少、程序設(shè)計(jì)簡(jiǎn)單、原始系數(shù)矩陣在計(jì)算過(guò)程中始終不變等優(yōu)點(diǎn)。5.2高斯消去法在求解三角方程組,得高斯消去法的條件5.3高斯主元素消去法列主元消去法5.4矩陣三角分解法Ax=b是線性方程組,A是n×n方陣,并設(shè)A的各階順序主子式不為零。令A(yù)(1)=A,當(dāng)高斯消元法進(jìn)行第一步后,相當(dāng)于用一個(gè)初等矩陣左乘A(1)

。不難看出，這個(gè)初等矩陣為重復(fù)這個(gè)過(guò)程，最后得到一般地

這就是說(shuō)，高斯消去法實(shí)質(zhì)上產(chǎn)生了一個(gè)將A分解為兩個(gè)三角形矩陣相乘的因式分解，于是我們得到如下重要定理。當(dāng)A進(jìn)行LU分解后，Ax=b就容易解了.即Ax=b等價(jià)于:

追趕法在一些實(shí)際問(wèn)題中，例如解常微分方程邊值問(wèn)題，熱傳導(dǎo)方程以及船體數(shù)學(xué)放樣中建立三次樣條函數(shù)等，都會(huì)要求解系數(shù)矩陣為對(duì)角占優(yōu)的三對(duì)角線方程組其中|i-j|>1時(shí),aij=0,且滿足如下的對(duì)角占優(yōu)條件:(1)|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)‖

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)消去法列主元消去法矩陣三角分解法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)存和運(yùn)算兩方面，迭代通常都可利用A中有大量零元素的特點(diǎn)?？紤]線性方程組6.1引言本章將介紹迭代法的一般理論及雅可比迭代法、高斯—塞德爾迭代法、超松弛迭代法，研究它們的收斂性。6.2基本迭代一、雅可比迭代法二、高斯—塞德爾迭代法SOR迭代法的計(jì)算公式:對(duì)k=0,1,…,三、逐次超松馳(SOR)迭代法說(shuō)明:1)ω=1,即為GS（高斯-賽德爾迭代法）;2)ω>1，稱為超松馳法；

ω<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)-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若矩陣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)圖六迭代法解方程組迭代法基本概念高斯-賽德爾迭代法迭代格式收斂條件（充要條件、充分條件四個(gè)）SQR迭代法迭代法收斂速度雅可比迭代法迭代格式收斂條件（充要條件、充分條件四個(gè)）迭代格式收斂條件（充要條件、必要條件、充分條件五個(gè)）第七章解非線性方程求根內(nèi)容提要7.1方程求根與二分法7.2迭代法及其收斂性7.3牛頓法7.4弦截法7.1方程求根與二分法一、引言非線性方程的分類由此可知方程的有根區(qū)間為[1,2][3,4][5,6]求根問(wèn)題的三個(gè)方面：存在性，分布，精確化。二、二分法0xyX*x0aby=f(x)a1b1二分法的優(yōu)點(diǎn)是算法簡(jiǎn)單，且總是收斂的，缺點(diǎn)是收斂太慢,故一般不單獨(dú)將其用于求根，只用其為根求得一個(gè)較好的近似值。7.2迭代法一、不動(dòng)點(diǎn)迭代與不動(dòng)點(diǎn)迭代法上述迭代法是一種逐次逼近法，其基本思想是將隱式方程歸結(jié)為一組顯示的計(jì)算公式，就是說(shuō)，迭代過(guò)程實(shí)質(zhì)上是一個(gè)逐步顯示的過(guò)程。繼續(xù)迭代下去已經(jīng)沒有必要，因?yàn)榻Y(jié)果顯然會(huì)越來(lái)越大，不可能趨于某個(gè)極限。這種不收斂的迭代過(guò)程稱作是發(fā)散的。一個(gè)發(fā)散的迭代過(guò)程，縱使進(jìn)行了千百次迭代，其結(jié)果也毫無(wú)價(jià)值。因此，迭代格式形式不同，有的收斂，有的發(fā)散，只有收斂的迭代過(guò)程才有意義，為此要研究不動(dòng)點(diǎn)的存在性及迭代法的收斂性。二、不動(dòng)點(diǎn)的存在性與迭代法的收斂性三、局部收斂性與收斂階7.3牛頓法一、牛頓法及其收斂性二、牛頓法應(yīng)用舉例三、簡(jiǎn)化牛頓法與牛頓下山法四、重根情形7.4弦截法知識(shí)結(jié)構(gòu)圖七方程近似求根基本概念（單根、重根、有根區(qū)間、不動(dòng)點(diǎn)、收斂階）求根