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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

，兩端同除以

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

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

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

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

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

返回2/4/202323§1.2誤差

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

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

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

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

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

2/4/202325稱為近似值的相對(duì)誤差的一個(gè)上界,稱為近似值的相對(duì)誤界

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

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

絕對(duì)誤差限是0.01的半個(gè)單位，且，

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

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

例

設(shè)近似值

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

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

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

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

（1）計(jì)算與十個(gè)之和，即，采用以下兩種計(jì)算方法

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

計(jì)算得（錯(cuò)）

2）（正確）

（2）（錯(cuò)）

（3）（錯(cuò)）

（正確）

2/4/202333例2計(jì)算