第一章(矩陣與數(shù)值分析)

矩陣與數(shù)值分析

大連理工大學(xué)工科碩士基礎(chǔ)課程任課教師：金光日（1班）

計(jì)算機(jī)科學(xué)計(jì)算

（第二版）

張宏偉金光日施吉林董波編

高等教育出版社

課程須知學(xué)時(shí)：48學(xué)分：3基礎(chǔ)：微積分、線性代數(shù)、程序設(shè)計(jì)語言（建議掌握Matlab或C語言）環(huán)節(jié):課堂授課+課外上機(jī)實(shí)驗(yàn)考核：期末考試70%；平時(shí)作業(yè)20%；數(shù)值實(shí)驗(yàn)10%.第1章緒論1.1

計(jì)算機(jī)科學(xué)計(jì)算研究對(duì)象與特點(diǎn)

科學(xué)計(jì)算----現(xiàn)代意義下的計(jì)算數(shù)學(xué)，主要研究在計(jì)算機(jī)上計(jì)算的有效算法及其相關(guān)理論。科學(xué)計(jì)算、理論計(jì)算和實(shí)驗(yàn)----三大科學(xué)方法。

主要內(nèi)容包括：微分方程數(shù)值解法

計(jì)算數(shù)學(xué)-----研究用計(jì)算機(jī)求解各種數(shù)學(xué)問題的數(shù)值計(jì)算方法及其理論與軟件實(shí)現(xiàn)。數(shù)值代數(shù)數(shù)值逼近

三、討論數(shù)值算法的時(shí)空復(fù)雜性：既要時(shí)間復(fù)雜性好（指節(jié)省時(shí)間），又要空間復(fù)雜性好（指節(jié)省存儲(chǔ)量）。這也是建立算法要研究的問題，它關(guān)系到算法能否在計(jì)算機(jī)上實(shí)現(xiàn)。

具體任務(wù)：

一、構(gòu)造在計(jì)算機(jī)上可行的有效算法。

二、給出可靠的理論分析：進(jìn)行誤差分析，討論數(shù)值算法的收斂性和數(shù)值穩(wěn)定性。

四、進(jìn)行數(shù)值實(shí)驗(yàn)，即任何一個(gè)算法除了從理論上要滿足上述三點(diǎn)外，還要通過數(shù)值試驗(yàn)證明是行之有效的。

考察線性方程組的解法

早在18世紀(jì)Cramer已給出了求解法則：

什么是有效算法？…，（D≠0），Cramer’sRule

從理論上講Cramer法則是一個(gè)求線性方程組的數(shù)值方法，且對(duì)階數(shù)不高的方程組行之有效。但是理論正確的數(shù)值方法在計(jì)算機(jī)上是否實(shí)際可行呢？在算法中的乘、除運(yùn)算次數(shù)將大于使用每秒一億次的串行計(jì)算機(jī)計(jì)算,完成運(yùn)算耗時(shí)約30萬年!21?。s9.7×1020次）以求解20階線性方程組為例，如果用Cramer法則求解，都能很快完成。

尋求新的數(shù)值方法----計(jì)算機(jī)科學(xué)計(jì)算生命力的來源。

隨著科學(xué)技術(shù)的發(fā)展，出現(xiàn)的數(shù)學(xué)問題也越來越多樣化，有些問題用Gauss消去法求解達(dá)不到精度，甚至算不出結(jié)果，從而促使人們對(duì)Gauss消去法進(jìn)行改進(jìn)，又出現(xiàn)了Gauss主元消去法，大大提高了消去法的計(jì)算精度。

Cramer算法是“實(shí)際計(jì)算不了”的。為此，人們研究出著名的Gauss消去法，它的計(jì)算過程已作根本改進(jìn)，使得上述例子的乘、除運(yùn)算僅為3060次，這在任何一臺(tái)電子計(jì)算機(jī)上1.2誤差分析與數(shù)值方法的穩(wěn)定性

1.2.1誤差來源與分類

用計(jì)算機(jī)解決科學(xué)計(jì)算問題時(shí)經(jīng)常采用的處理方式是將連續(xù)的問題離散化、用有限代替無限等，并且用數(shù)值分析所處理的一些數(shù)據(jù)，不論是原始數(shù)據(jù)，還是最終結(jié)果，絕大多數(shù)都是近似的，因此在此過程中，誤差無處不在．誤差主要來源于以下四個(gè)方面：

實(shí)際問題數(shù)學(xué)模型計(jì)算機(jī)數(shù)值結(jié)果編程實(shí)現(xiàn)算法數(shù)值計(jì)算方法計(jì)算機(jī)科學(xué)計(jì)算的流程圖模型誤差截?cái)嗾`差或稱為方法誤差觀測誤差舍入誤差

模型誤差和觀測誤差不在本課程的討論范圍。

這里主要討論算法的截?cái)嗾`差與舍入誤差，而截?cái)嗾`差將結(jié)合具體算法討論。

觀測誤差通常也歸結(jié)為舍入誤差。

1.2.2誤差的基本概念

設(shè)為精確值，因此誤差也未知。稱

通常準(zhǔn)確值是未知的，為近似值的絕對(duì)誤差，簡稱誤差。為的一個(gè)近似值，絕對(duì)誤差界（限）誤差可正可負(fù)。絕對(duì)誤差（誤差）

則叫做近似值的誤差界（限）。定義定義

設(shè)為精確值，為的一個(gè)近似值，若有常數(shù),使得

例如，用毫米刻度的米尺測量一長度，讀出和該長度接近的刻度，是的近似值，它的誤差限是，于是如讀出的長度為，則知.

雖然從這個(gè)不等式不能知道準(zhǔn)確的是多少，但可知絕對(duì)誤差界（限）結(jié)果說明在區(qū)間內(nèi).

對(duì)于一般情形，即也可以表示為

但要注意的是，絕對(duì)誤差的大小并不能完全表示近似值的好壞.實(shí)際計(jì)算中，如果真值未知時(shí)，

若，稱為近似值的相對(duì)誤差。作為的相對(duì)誤差，條件是較小。通常取相對(duì)誤差（誤差）則將近似值的誤差與準(zhǔn)確值的比值定義

相對(duì)誤差也可正可負(fù)，其絕對(duì)值的上界叫做相對(duì)誤差界（限）。當(dāng)絕對(duì)誤差界為時(shí)，相對(duì)誤差界取為是的平方項(xiàng)級(jí)，故可忽略不計(jì)。相對(duì)誤差界（限）這是由于,其近似值

,求

已知，因此其絕對(duì)誤差界為：相對(duì)誤差界為：不是唯一的。我們要注意它們的作用。的絕對(duì)誤差界和相對(duì)誤差界。解：0.00030.0002。此例計(jì)算中不難發(fā)現(xiàn)，絕對(duì)誤差界和相對(duì)誤差界并例1

當(dāng)準(zhǔn)確值位數(shù)比較多時(shí)，常常按四舍五入的原則取的前幾位得到近似值，

取3位

取5位它們的誤差界的一種取法：

例如誤差界的取法（1-4）中的一個(gè)數(shù)字，為整數(shù)，（1-5）則稱為的具有位有效數(shù)字的近似值。定義1.3

設(shè)為精確值，為的一個(gè)近似值，表為可以是有限或無限小數(shù)形式，其中是0到9如果為正整數(shù)，由于，而的具有4位有效字的近似值。，因也只是e的具有4位有效數(shù)字的近似值。作為的近似值，也具有4位有效數(shù)字。這是因?yàn)椋喝绻〗浦低瑯游覀兛梢苑治龀觯运窃诶?中，

如果一個(gè)近似值是由精確值經(jīng)四舍五入得到的，那么，從這個(gè)近似值的末尾數(shù)向前數(shù)起直到再無非零數(shù)字止，所數(shù)到的數(shù)字均為有效數(shù)字。有效數(shù)字位數(shù)與小數(shù)點(diǎn)的位置無關(guān)。

一般來說，絕對(duì)誤差與小數(shù)位數(shù)有關(guān)，相對(duì)誤差與有效數(shù)字位數(shù)有關(guān)。

下列近似值的絕對(duì)誤差限均為0.005，問它們各有幾位有效數(shù)字？解：則由

例2

有5位有效數(shù)字；

有1位有效數(shù)字；

即無有效數(shù)字。

即其表達(dá)形式如（1-4）（2）如果

（1-5）（1）如果有位有效數(shù)字，則

則至少具有位有效數(shù)字。

為某個(gè)精確值，為它的一個(gè)近似值，設(shè)實(shí)數(shù)定理1.1因?yàn)榻Y(jié)論（1）成立。證所以如果有位有效數(shù)字，那么

再由（1-5），由定義1.3知，至少具有位有效數(shù)字。

1.2.3函數(shù)值計(jì)算的誤差估計(jì)

則可用Taylor展開的相差不太大，方法來估計(jì)其誤差。

其中與之間。如果在如果用近似

即有從而設(shè)一元函數(shù)具有二階連續(xù)導(dǎo)數(shù)，自變量的一個(gè)近似值為的二次項(xiàng)，得到的一個(gè)近似誤差:則可忽略的近似值分別為，則其中

所以可以近似估計(jì)誤差界:元函數(shù)，自變量如果為現(xiàn)將上述估計(jì)式應(yīng)用到四則運(yùn)算.特別地,當(dāng)時(shí),(1)加法

兩個(gè)近似數(shù)相加，其運(yùn)算結(jié)果的精度不比原始數(shù)據(jù)的任何一個(gè)精度高。(2)減法應(yīng)避免兩個(gè)相近的數(shù)相減。

兩個(gè)近似數(shù)相減，其運(yùn)算結(jié)果的精度不比原始數(shù)據(jù)的任何一個(gè)精度高。

應(yīng)避免大數(shù)作乘數(shù)。(3)乘法(4)除法

應(yīng)避免小數(shù)作除數(shù)。練習(xí)已知均為有效數(shù)字，求的相對(duì)誤差界。解：取得由已知，從而如果，則，用上述公式計(jì)算時(shí)總之，兩者其中之一必將會(huì)損失有效數(shù)字。一元二次方程例有兩個(gè)根，其求根公式為,如果，則有如果，則有一般解二次方程其中是b的符號(hào)函數(shù)。（設(shè)

均不為零），應(yīng)取方程的根為若取三位有效數(shù)字計(jì)算，有，則由習(xí)慣的公式，有三位有效數(shù)字。，只有一位有效數(shù)字。．例而，如果改用公式，計(jì)算有的精確值是具有二位有效數(shù)字。時(shí)發(fā)生了兩個(gè)相近數(shù)相減，造成其原因?yàn)樵谟?jì)算有效數(shù)字損失。

用某一種數(shù)值方法求一個(gè)問題的數(shù)值解，如果在方法的計(jì)算過程中舍入誤差在一定條件下能夠得到控制（或者說舍入誤差的增長不影響產(chǎn)生可靠的結(jié)果），則稱該算法是數(shù)值穩(wěn)定的；否則，即出現(xiàn)與數(shù)值穩(wěn)定相反的情況，則稱之為數(shù)值不穩(wěn)定的.1.2.5數(shù)值方法的穩(wěn)定性和避免誤差危害的基本原則1.數(shù)值方法的穩(wěn)定性由于則遞歸算法如下：1.2.計(jì)算積分例題解：計(jì)算出由計(jì)算出由

設(shè)的近似值為，然后按方法1計(jì)算的近似值

，如果最初計(jì)算時(shí)誤差為遞推過程的舍入誤差不記，并記，則有由此可見，用該方法計(jì)算時(shí)，，那么計(jì)算時(shí)產(chǎn)生的舍入誤差放大了倍，因此，該方法是數(shù)值不穩(wěn)定的。按方法2計(jì)算時(shí)，

記初始誤差為，則有生的舍入誤差為時(shí)產(chǎn)若計(jì)算方法2不會(huì)放大舍入誤差。因此，該方法是數(shù)值穩(wěn)定的。

為了用數(shù)值方法求得數(shù)值問題滿意的近似解，在數(shù)值運(yùn)算中應(yīng)注意下面兩個(gè)基本原則。2、避免誤差危害的基本原則(I)避免有效數(shù)字的損失（3）避免小數(shù)做除數(shù)或大數(shù)做乘數(shù)。

在四則運(yùn)算中為避免有效數(shù)字的損失，應(yīng)注意以下事項(xiàng)：（1）在做加法運(yùn)算時(shí)，應(yīng)防止“大數(shù)吃小數(shù)”；（2）避免兩個(gè)相近數(shù)相減；在五位十進(jìn)制的計(jì)算機(jī)上計(jì)算

解計(jì)算機(jī)作加減法時(shí)，先將所相加數(shù)階碼對(duì)齊，根據(jù)因其中的舍入結(jié)果為0，所以上式的計(jì)算結(jié)果是。這種現(xiàn)象被稱為“大數(shù)吃小數(shù)”。后一種方法的結(jié)果是正確的，前一種方法的舍入誤差影響太大。例字長舍入，再加減。規(guī)范化和階碼對(duì)齊后的數(shù)表示為相加，再和63015相加，即

次序，先把1000個(gè)1000個(gè)，那么上式用如果用63015依次加各個(gè)如果改變運(yùn)算例如在八位十進(jìn)制計(jì)算機(jī)上，計(jì)算為9位尾數(shù)左移變成機(jī)器零，這便說明用小數(shù)做除數(shù)或用3.712與在計(jì)算機(jī)上做和時(shí)，大數(shù)做乘數(shù)時(shí)，容易產(chǎn)生大的舍入誤差，應(yīng)盡量避免。

3.712由于階碼升就是所求的值。如果直接逐項(xiàng)求和計(jì)算，需要大約次乘法運(yùn)算,即例如，多項(xiàng)式求值運(yùn)算，設(shè)若取，

(II)減少運(yùn)算次數(shù)次

次

則有遞推公式：總的計(jì)算量需進(jìn)行次乘法。若將公式變成如下遞推公式，即令若令則有遞推公式：總的計(jì)算量為

次乘法。就是所求的的值。3910501-31-1501-31-1令X=227810220242212279158157以上計(jì)算過程稱之為秦九韶算法利用計(jì)算，要計(jì)算十萬項(xiàng)的和，計(jì)算量很大，另一方面舍入誤差的積累也十分嚴(yán)重。取只須計(jì)算前9項(xiàng)的和，截?cái)嗾`差便小于，若要精確到如果改用級(jí)數(shù)例

秦九韶是一位既重視理論又重視實(shí)踐，既善于繼承又勇于創(chuàng)新的數(shù)學(xué)家．他所提出的大衍求一術(shù)和正負(fù)開方術(shù)及其名著《數(shù)書九章》，是中國數(shù)學(xué)史上光彩奪目的一頁，對(duì)后世數(shù)學(xué)發(fā)展產(chǎn)生了廣泛的影響．美國著名科學(xué)史家G．薩頓(Sarton，1884－1956)說過，秦九韶是“他那個(gè)民族，他那個(gè)時(shí)代，并且確實(shí)也是所有時(shí)代最偉大的數(shù)學(xué)家之一”．秦九韶的數(shù)學(xué)成就及對(duì)世界數(shù)學(xué)的貢獻(xiàn)主要表現(xiàn)在以下方面：

1、秦九韶的《數(shù)書九章》是一部劃時(shí)代的巨著

2、秦九韶的“大衍求一術(shù)”，領(lǐng)先高斯554年，被康托爾稱為“最幸運(yùn)的天才”

3、秦九韶的任意次方程的數(shù)值解領(lǐng)先英國人霍納（W·G·Horner，1786—1837年）572年

秦九韶（公元1202－1261），字道古，安岳人。南宋大數(shù)學(xué)家秦九韶與李冶、楊輝、朱世杰并稱宋元數(shù)學(xué)四大家。秦九韶聰敏勤學(xué)。宋紹定四年（1231），秦九韶考中進(jìn)士，先后擔(dān)任縣尉、通判、參議官、州守、同農(nóng)、寺丞等職。先后在湖北、安徽、江蘇、浙江等地做官，1261年左右被貶至梅州（今廣東梅縣），不久死于任所。

克萊姆（GabrielCramer）

生于：公元1704年瑞士日內(nèi)瓦卒于：公元1752年法國巴尼奧勒

十八世紀(jì)瑞士數(shù)學(xué)家，精于數(shù)學(xué)和幾何學(xué)。早年在日內(nèi)瓦讀書，1724年起在日內(nèi)瓦加爾文學(xué)院任教，

1734年成為幾何學(xué)教授，1750年任哲學(xué)教授。他一生未婚，專心治學(xué)，平易近人且德高望重，先后當(dāng)選為倫敦皇家學(xué)會(huì)、柏林研究院和法國、意大利等學(xué)會(huì)的成員。主要著作是1750年出版《代數(shù)曲線的分析引論