數(shù)值分析(計算方法)

數(shù)值分析——插值、擬合與數(shù)值微積分主講：劉敬剛2/4/20231

數(shù)值分析(計算方法)介紹考慮如下線性方程組

或者：其中,由克萊姆法則可知(1)有唯一的解，而且解為：(1)一、引例

2/4/20232若行列式用按行（列）展開的方法計算，用克萊姆法則求解（1）需做乘除法的次數(shù):

當(dāng)方程組階數(shù)較高時，計算量很大，因此克萊姆法則通常僅有理論上的價值，計算線性方程組的解還要考慮:首先看一個簡單的例子：（若是更高階的方程組呢？）人類的計算能力是計算工具和計算方法效率的乘積，提高計算方法的效率與提高計算機硬件的效率同樣重要?？茖W(xué)計算已用到科學(xué)技術(shù)和社會生活的各個領(lǐng)域中，成為繼實驗和理論研究之后的第三種研究方法。數(shù)值解法=算法+計算機。2/4/20233二、研究對象和主要內(nèi)容2/4/20234數(shù)值計算方法，是一種研究如何求解數(shù)學(xué)問題數(shù)值近似解的方法，是在計算機上使用的解數(shù)學(xué)問題的方法，簡稱計算方法。包括直接方法和迭代方法!數(shù)值計算方法的計算對象是線性代數(shù)，微積分，常微分方程中的數(shù)學(xué)問題。內(nèi)容包括：求解線性方程組的數(shù)值方法;計算矩陣特征值和特征向量的數(shù)值方法;非線性方程和非線性方程組的迭代解法;插值與擬合;數(shù)值微積分;常微分方程數(shù)值解等問題。

2/4/20235三、特點2/4/20236數(shù)值計算方法既有數(shù)學(xué)類課程中理論上的抽象性和嚴謹性，又有實用性和實驗性等技術(shù)特征，它是一門理論性和實踐性都很強的課程。在20世紀70年代，大多數(shù)學(xué)校僅在數(shù)學(xué)系的計算數(shù)學(xué)專業(yè)和計算機系開設(shè)計算方法這門課程。隨著計算機技術(shù)的迅速發(fā)展和普及，現(xiàn)在計算方法課程幾乎已成為所有理工科大學(xué)生的一門必修課程。學(xué)習(xí)過程中應(yīng)該注意以下幾個方面：認清算法的計算對象；掌握基本的計算方法及其原理；用C++語言編制程序，在計算機上對算法進行驗證；對于算法要勤思考多比較！2/4/20237參考書目：1鐘爾杰.數(shù)值分析.高等教育出版社,2004.2顏慶津.數(shù)值分析.修訂版.北京航空航天大學(xué)出版社,2000.3李慶揚.數(shù)值分析.清華大學(xué)出版社,2001.4白峰杉.數(shù)值計算引論.高等教育出版社,2004.5王能超.計算方法.北京:高等教育出版社,2005.2/4/202381、算法設(shè)計技術(shù)2、誤差3、數(shù)值計算中需要注意的一些問題4、算法的穩(wěn)定性5、病態(tài)問題內(nèi)容:數(shù)值分析的基本概念2/4/20239§1.1

算法設(shè)計技術(shù)

古希臘哲學(xué)家Zeno(芝諾)在兩千多年前提出過一個駭人聽聞的命題：一個人不管跑得多快，也追不上爬在他前面的一只烏龜。這就是著名的Zeno悖論。Zeno在論證這個命題時采取了如下形式的邏輯推理：設(shè)人與龜同時同向起跑，如果龜不動，那么人經(jīng)過某段時間便能追上它；但實際上在這段時間內(nèi)龜又爬了一段路程，從而人又得重新追趕，如下圖所示，這樣每追趕一次所歸結(jié)的是同樣類型的追趕問題，因而這種追趕過程“永遠”不會終結(jié)。

引例2/4/202310耐人尋味的是，盡管Zeno悖論的論斷極其荒謬，但從算法設(shè)計思想的角度來看它卻是極為精辟的。Zeno悖論將人龜追趕問題表達為一連串追趕步的逐步逼近過程。設(shè)人與龜?shù)乃俣确謩e為與，記表示逼近過程的第步人與龜?shù)拈g距，另以表示相應(yīng)的時間，相鄰兩步的時間差。Zeno悖論將人龜追趕問題分解為一追一趕兩個過程：追的過程：先令龜不動，計算人追上龜所費的時間趕的過程：再令人不動，計算龜在這段時間內(nèi)爬行的路程tkSk-1SkVvtk-1vV圖示:人龜追趕過程2/4/202311若以人和龜之間的距離定義問題的規(guī)模大小，則上述過程將問題規(guī)模壓縮了倍：由于龜?shù)乃俣冗h遠小于人的速度，故很小，因此按上述步驟很快問題的規(guī)模就可以忽略不計，從而得到人追上龜所花時間，Zeno的解釋可用如下過程表示：——Zeno算法可見，Zeno算法的設(shè)計思想是，將人龜追趕計算化歸為簡單的行程計算的重復(fù)，它的設(shè)計方法是逐步壓縮計算模型的規(guī)模，這種“化大為小”的設(shè)計策略稱為規(guī)?？s減技術(shù)，簡稱縮減技術(shù)。

算法的設(shè)計精髓：“簡單”的重復(fù)生成復(fù)雜！2/4/202312則計算結(jié)果即為所求的和值：

（3）數(shù)列求和問題：

（1）1直接法的縮減技術(shù)若用bk表示前k項的部分和，則有

（2）2/4/202313這樣，如果定義和式的項數(shù)為數(shù)列求和問題的規(guī)模，則所求和值為（1）的退化情形。因之，只要令和式的規(guī)模逐次減1，最終當(dāng)規(guī)模為1時即可直接得出所求的和值，而這樣設(shè)計出來的算法就是累加求和算法（2）?？梢?，上述累加求和算法的設(shè)計思想是將多項求和（1）化歸為兩項求和（2）的重復(fù)，最終加工成一項和式（3）（(1)的退化情形）,從而得出和值。2/4/202314考慮利用縮減技術(shù)可得如下算法：算法流程圖——考慮問題12/4/2023152迭代法的校正技術(shù)易得人追上龜所花的時間是有些問題的“大事化小”過程似乎無法了結(jié)。Zeno悖論強調(diào)人“永遠”趕不上龜正是為了突出這層含義。這是一類無限逼近的過程，適于用所謂預(yù)報校正技術(shù)來處理。

設(shè)人龜起初相距，兩者的速度分別為和，則有方程（1）2/4/202316注意到v是個小量，設(shè)△t也是個小量，則可從上式中略去v△t，即令校正量△t滿足如下方程(近似)設(shè)解t*有某個預(yù)報值t0，希望提供校正量△t，使校正值t1=t0+△t能更好的滿足所給方程（1），即使得求解上述方程即可定出校正值

2/4/202317進一步視t1為新的預(yù)報值，重復(fù)實施上述手續(xù)，求出新的校正值t2，再由t2定t3，如此反復(fù)可生成一系列近似值

t1,t2,t3,…這就規(guī)定了一個迭代過程，

(2)Zeno悖論所描述的逼近過程正是這種迭代過程，當(dāng)k→∞時，tk→t*（——考慮問題2

）。大家知道，任何形式的重復(fù)都可看成是“時間”的量度。Zeno在刻畫人龜追趕問題中設(shè)置了兩個“時鐘”：一個是日常的鐘，另外Zeno又將迭代次數(shù)視為另一種時鐘，不妨稱之為Zeno鐘。Zeno公式（2）表明，當(dāng)Zeno鐘趨于∞時人才能追上龜，Zeno正是據(jù)此斷言人永遠追不上龜。

2/4/202318給定，求開方值的問題就是要求解方程

設(shè)給定某個預(yù)報值，希望借助于某種簡單方法確定校正量，使校正值能夠比較準確地滿足方程（1），即使成立，設(shè)校正量是個小量，舍去上式中的高階小量，令，從中定出，繼而可得校正值：（1）利用校正技術(shù)，設(shè)計求解（）的算法。近似2/4/202319反復(fù)實施這種預(yù)報校正手續(xù)，即可導(dǎo)出開方公式：從某個初值出發(fā)，利用上式反復(fù)迭代，即可獲得滿足精度要求的開方值。

校正技術(shù)的基本思想：刪繁就簡，逐步求精！——考慮問題32/4/202320其中，3算法優(yōu)化的松弛技術(shù)對于給定的預(yù)報值

，校正值為據(jù)此有

，兩端同除以

，有由于為人龜追趕問題的精確解，再考察Zeno算法：可見，精確解等于任給預(yù)報值同它的校正值的加權(quán)平均：2/4/202321即通過適當(dāng)選取權(quán)系數(shù)來調(diào)整校正量，以加工得到更高精度的，這種基于校正量的調(diào)整與松動的方法通常稱為松弛技術(shù)。

可以看到，這里任意一對迭代值經(jīng)過上述手續(xù)松弛即可得到問題的精確解。這種加工效果是奇妙的。在實際計算中常?？梢垣@得目標值F*的兩個相伴的近似值F0與F1，將它們加工成更高精度的結(jié)果的方法之一就是取兩者的某種加權(quán)平均作為改進值：

2/4/202322有一種情況特別引人注目：若所提供的一對近似值與有優(yōu)劣之分，譬如優(yōu)而劣，這時就采用如下松弛方式：

即在松弛過程中張揚的優(yōu)勢而抑制的劣勢，這種設(shè)計策略稱作外推松弛技術(shù)，簡稱超松弛。

總之，超松弛的設(shè)計機理是優(yōu)劣互補，化粗為精。松弛技術(shù)的關(guān)鍵在于松弛因子的選取，而這往往是相當(dāng)困難的。

返回2/4/202323§1.2誤差

1誤差的分類2/4/2023242誤差和有效數(shù)字(1)誤差

定義設(shè)是準確值，是的一個近似值，記，稱為近似值的絕對誤差，簡稱誤差。

若已知的一個上界為，即，則稱為近似值的絕對誤差界，簡稱誤差界（越小表示近似程度越高）。

注:用絕對誤差來刻畫近似數(shù)的精確程度不能反映它在原數(shù)中所占的比例。

例,，可是與真值相差一個數(shù)量級。

2/4/202325稱為近似值的相對誤差的一個上界,稱為近似值的相對誤界

上例中，易見近似程度并不高！也可以記為2/4/202326(2)誤差估計

函數(shù)計算的誤差估計算數(shù)運算的誤差估計2/4/202327解

絕對誤差限是0.01的半個單位，且，

有三位有效數(shù)字，分別是1，3，8；有一位有效數(shù)字，為3；沒有有效數(shù)字。

(3)有效數(shù)字定義設(shè)是數(shù)的近似值，如果的絕對誤差限是它的某一位的半個單位，且從該位到的第一位非零數(shù)字共有位，則稱作為的近似有位有效數(shù)字。

例

設(shè)近似值

，其絕對誤差限都是0.005，求各個近似值各有幾位有效數(shù)字？同一真值的不同近似值，有效數(shù)字越多，它的絕對誤差和相對誤差都越小。

②用單精度浮點型變量進行計算的結(jié)果有七位有效數(shù)字，雙精度浮點型變量有16位有效數(shù)字注：2/4/2023283浮點數(shù)（1）浮點數(shù)“數(shù)”在計算機中是以二進制表示的，一個非零二進制數(shù)的一般描述形式為：其中di（i=1,2,…,t）為0或1，稱為尾數(shù)，且d1≠0；2為基數(shù)，s稱為階碼且滿足L≤s

≤U，這說明計算機只能表示有限個數(shù)且是有限精度，這個實數(shù)的子集稱為浮點數(shù)，記作F。不難驗證對于F中任意不為零的數(shù)f，有其中m=2L-1，M=2U(1-2-t)，因此計算機上的計算會有溢出現(xiàn)象：上溢和下溢！浮點數(shù)在接近其下界m處比較稠密，而在接近其上界M處比較稀疏！因此，在計算中通常都是使用相對誤差來控制精度！由于計算機的有限精度而造成的誤差稱為舍入誤差！2/4/202329（2）截斷誤差和舍入誤差考慮計算一元可微函數(shù)f(x)在x0處導(dǎo)數(shù)的近似方法：因此近似方法（1）的誤差為考慮方法（1）：由泰勒展開，可得從而有——截斷誤差考慮問題42/4/202330通過實驗發(fā)現(xiàn)，隨著h減小，通過（1）計算的導(dǎo)數(shù)近似值與真值的誤差是先減小后增大，這種現(xiàn)象是什么原因造成的呢？其原因就在于計算機是有限精度的，隨著h的減小，舍入誤差逐漸被放大，并且最終成為引起誤差的主導(dǎo)因素?。ㄒ笊蠙C體會舍入誤差的影響）要學(xué)好數(shù)值分析課程一定要真正理解舍入誤差，特別是舍入誤差在算法中的傳播和對最終結(jié)果的影響！同理可以討論近似方法（2）的截斷誤差，以及隨著h的減小，其誤差的變化情況！返回那么是不是h越小，計算誤差就越小呢？——考慮問題52/4/202331§1.3

數(shù)值計算中需要注意的問題1浮點數(shù)的加法設(shè)兩個浮點數(shù)相加：首先比較它們的階碼，若階碼相同則尾數(shù)相加，相加后若尾數(shù)大于1則階碼進位；若階碼不等，則以相對大的階碼為標準，將階碼小的浮點數(shù)進行移位，直到階碼一致，再按階碼相同時的規(guī)則進行相加！例1假設(shè)計算機只能存放三位十進制數(shù)字，設(shè)在該計算機上進行如下運算

（1）計算與十個之和，即，采用以下兩種計算方法

2/4/2023321），，則即為所求，

計算得（錯）

2）（正確）

（2）（錯）

（3）（錯）

（正確）

2/4/202333例2計算