矩陣與數值分析

大連理工大學工科碩士基礎課程任課教師：金光日（1班）

計算機科學計算

（第二版）

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

高等教育出版社

課程須知學時：48學分：3基礎：微積分、線性代數、程序設計語言（建議掌握Matlab或C語言）環節:課堂授課+課外上機實驗考核：期末考試70%；平時作業20%；數值實驗10%.第1章緒論1.1

計算機科學計算研究對象與特點

科學計算----現代意義下的計算數學，主要研究在計算機上計算的有效算法及其相關理論?？茖W計算、理論計算和實驗----三大科學方法。

主要內容包括：微分方程數值解法

計算數學-----研究用計算機求解各種數學問題的數值計算方法及其理論與軟件實現。數值代數數值逼近

三、討論數值算法的時空復雜性：既要時間復雜性好（指節省時間），又要空間復雜性好（指節省存儲量）。這也是建立算法要研究的問題，它關系到算法能否在計算機上實現。

具體任務：

一、構造在計算機上可行的有效算法。

二、給出可靠的理論分析：進行誤差分析，討論數值算法的收斂性和數值穩定性。

四、進行數值實驗，即任何一個算法除了從理論上要滿足上述三點外，還要通過數值試驗證明是行之有效的。

考察線性方程組的解法

早在18世紀Cramer已給出了求解法則：

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

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

尋求新的數值方法----計算機科學計算生命力的來源。

隨著科學技術的發展，出現的數學問題也越來越多樣化，有些問題用Gauss消去法求解達不到精度，甚至算不出結果，從而促使人們對Gauss消去法進行改進，又出現了Gauss主元消去法，大大提高了消去法的計算精度。

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

1.2.1誤差來源與分類

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

實際問題數學模型計算機數值結果編程實現算法數值計算方法計算機科學計算的流程圖模型誤差截斷誤差或稱為方法誤差觀測誤差舍入誤差

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

這里主要討論算法的截斷誤差與舍入誤差，而截斷誤差將結合具體算法討論。

觀測誤差通常也歸結為舍入誤差。

1.2.2誤差的基本概念

設為精確值，因此誤差也未知。稱

通常準確值是未知的，為近似值的絕對誤差，簡稱誤差。為的一個近似值，絕對誤差界（限）誤差可正可負。絕對誤差（誤差）

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

設為精確值，為的一個近似值，若有常數,使得

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

雖然從這個不等式不能知道準確的是多少，但可知絕對誤差界（限）結果說明在區間內.

對于一般情形，即也可以表示為

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

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

相對誤差也可正可負，其絕對值的上界叫做相對誤差界（限）。當絕對誤差界為時，相對誤差界取為是的平方項級，故可忽略不計。相對誤差界（限）這是由于,其近似值

,求

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

當準確值位數比較多時，常常按四舍五入的原則取的前幾位得到近似值，

取3位

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

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

設為精確值，為的一個近似值，表為可以是有限或無限小數形式，其中是0到9如果為正整數，由于，而的具有4位有效字的近似值。，因也只是e的具有4位有效數字的近似值。作為的近似值，也具有4位有效數字。這是因為：如果取近似值同樣我們可以分析出，所以它是在例1中，

如果一個近似值是由精確值經四舍五入得到的，那么，從這個近似值的末尾數向前數起直到再無非零數字止，所數到的數字均為有效數字。有效數字位數與小數點的位置無關。

一般來說，絕對誤差與小數位數有關，相對誤差與有效數字位數有關。

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

例2

有5位有效數字；

有1位有效數字；

即無有效數字。

即其表達形式如（1-4）（2）如果

（1-5）（1）如果有位有效數字，則

則至少具有位有效數字。

為某個精確值，為它的一個近似值，設實數定理1.1因為結論（1）成立。證所以如果有位有效數字，那么

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

1.2.3函數值計算的誤差估計

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

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

即有從而設一元函數具有二階連續導數，自變量的一個近似值為的二次項，得到的一個近似誤差:則可忽略的近似值分別為，則其中

所以可以近似估計誤差界:元函數，自變量如果為現將上述估計式應用到四則運算.特別地,當時,(1)加法

兩個近似數相加，其運算結果的精度不比原始數據的任何一個精度高。(2)減法應避免兩個相近的數相減。

兩個近似數相減，其運算結果的精度不比原始數據的任何一個精度高。

應避免大數作乘數。(3)乘法(4)除法

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

均不為零），應取方程的根為若取三位有效數字計算，有，則由習慣的公式，有三位有效數字。，只有一位有效數字。．例而，如果改用公式，計算有的精確值是具有二位有效數字。時發生了兩個相近數相減，造成其原因為在計算有效數字損失。

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

設的近似值為，然后按方法1計算的近似值

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

記初始誤差為，則有生的舍入誤差為時產若計算方法2不會放大舍入誤差。因此，該方法是數值穩定的。

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

在四則運算中為避免有效數字的損失，應注意以下事項：（1）在做加法運算時，應防止“大數吃小數”；（2）避免兩個相近數相減；在五位十進制的計算機上計算

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

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

3.712由于階碼升就是所求的值。如果直接逐項求和計算，需要大約次乘法運算,即例如，多項式求值運算，設若取，

(II)減少運算次數次

次

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

次乘法。就是所求的的值。3910501-31-1501-31-1令X=227810220242212279158157以上計算過程稱之為秦九韶算法利用計算，要計算十萬項的和，計算量很大，另一方面舍入誤差的積累也十分嚴重。取只須計算前9項的和，截斷誤差便小于，若要精確到如果改用級數例

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

1、秦九韶的《數書九章》是一部劃時代的巨著

2、秦九韶的“大衍求一術”，領先高斯554年，被康托爾稱為“最幸運的天才”

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

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

克萊姆（GabrielCramer）

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

十八世紀瑞士數學家，精于數學和幾何學。早年在日內瓦讀書，1724年起在日內瓦加爾文學院任教，

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