計(jì)算方法第一章緒論.ppt

1、計(jì)算方法,參考資料,數(shù)值分析李慶揚(yáng)、王能超、易大義 華 中理工大學(xué)出版社1982年 計(jì)算方法算法設(shè)計(jì)及其MATLAB實(shí)現(xiàn) 王能超 ，高等教育出版社 2005年 計(jì)算機(jī)數(shù)值計(jì)算方法及程序設(shè)計(jì) 周煦 機(jī)械工業(yè)出版社 數(shù)值方法金一慶 陳越 機(jī)械工業(yè)出版社 計(jì)算方法引論徐萃薇 高等教育出版社 計(jì)算方法精品課網(wǎng)站 /mathews/numerical.html,考核方式,一、平時(shí)占10分 1平時(shí)表現(xiàn)占10分，扣分標(biāo)準(zhǔn)如下（扣到0為止）： (1)曠課1次扣2分; (2) 遲到、早退1次扣1分; (3)違反課堂紀(jì)律扣13分; (4)替答到扣3分，被替扣2分;

2、(5)上機(jī)聊天、玩游戲、帶耳機(jī)等發(fā)現(xiàn)一次扣1分。 (6) 作業(yè)不及格或沒(méi)交一次扣1分。 二、實(shí)驗(yàn)一表占40（二表占20）分 以最后的實(shí)驗(yàn)上機(jī)考試分?jǐn)?shù)為準(zhǔn)，成績(jī)以百分制給出，最后折合。上機(jī)考試使用機(jī)試系統(tǒng)。程序填空和程序改錯(cuò)各1題。 三、期末筆試一表占50分（二表占70分） 筆試試卷以百分制給出，最后折合。第8周課內(nèi)時(shí)間考。,上機(jī)要求,按學(xué)號(hào)坐(見上機(jī)安排) 課前把程序?qū)懺诩埳匣蛘甙芽仗詈?教材和實(shí)驗(yàn)講義都帶著 保存自己調(diào)好的程序 交2次實(shí)驗(yàn)報(bào)告 牛頓迭代、曲線擬合,科學(xué)計(jì)算的意義,科學(xué)計(jì)算與科學(xué)實(shí)驗(yàn)、科學(xué)理論并列為科學(xué)方法論的三大組成部分。 關(guān)鍵時(shí)期和代表性的人物 1.Galileo(1564

3、-1642)是實(shí)驗(yàn)物理的開創(chuàng)者，倡導(dǎo)科學(xué)的數(shù)學(xué)化，為近代科學(xué)制訂了具體而有效的程序，通過(guò)關(guān)鍵實(shí)驗(yàn)，演繹基本原理，達(dá)到認(rèn)識(shí)世界的目的，霍金稱他為近代科學(xué)奠基人。 Kepler（1571-1630）對(duì)行星數(shù)據(jù)的計(jì)算和分析，提出行星運(yùn)動(dòng)三大定律，是按此程序研究的一個(gè)成功典范。,科學(xué)計(jì)算的意義,2.Newton（1642-1725）開創(chuàng)了微積分，提出了力學(xué)的三大定律，特別是萬(wàn)有引力定律，是科學(xué)發(fā)展進(jìn)入理論思維的標(biāo)志。 Einstein（1878-1955）提出的相對(duì)論是這種理論思維的頂峰，在幾個(gè)世紀(jì)中，實(shí)驗(yàn)方法和理論分析一直強(qiáng)有力地推動(dòng)著科技的發(fā)展，科學(xué)家們也沒(méi)有停止過(guò)使用科學(xué)計(jì)算來(lái)進(jìn)行研究，但由于以

4、前沒(méi)有計(jì)算機(jī)，計(jì)算只能是小規(guī)模的。,科學(xué)計(jì)算的意義,V.Neumann(1903-1957)1945年研制的第一臺(tái)計(jì)算機(jī)帶來(lái)了科學(xué)研究的新的革命，將科學(xué)家從繁重的勞動(dòng)中解放出來(lái)，目前，科學(xué)計(jì)算已發(fā)展成為一種研究方法，“科學(xué)計(jì)算與實(shí)驗(yàn)、理論三足鼎立，相輔相成，成為當(dāng)今科學(xué)活動(dòng)的三大方法。,計(jì)算方法能做什么應(yīng)用問(wèn)題舉例,1、一個(gè)兩千年前的例子,今有上禾三秉，中禾二秉，下禾一秉，實(shí)三十九斗； 上禾二秉，中禾三秉，下禾一秉，實(shí)三十四斗； 上禾一秉，中禾二秉，下禾三秉，實(shí)二十六斗。 問(wèn)上、中、下禾實(shí)一秉各幾何？ 答曰：上禾一秉九斗四分斗之一。中禾一秉四斗四分斗之一。下禾一秉二斗四分斗之三。-九章算術(shù),1

5、、一個(gè)兩千年前的例子,線性方程組的數(shù)值方法！,2、天體力學(xué)中的Kepler方程,x是行星運(yùn)動(dòng)的軌道，它是時(shí)間t 的函數(shù),非線性方程的數(shù)值解法,3、全球定位系統(tǒng)（Global Positioning System, GPS),全球定位系統(tǒng)：在地球的任何一個(gè)位置，至少可以同時(shí)收到4顆以上衛(wèi)星發(fā)射的信號(hào),表示地球上一個(gè)接收點(diǎn)R的當(dāng)前位置，衛(wèi)星Si的位置為 ，則得到下列非線性方程組,非線性方程組的數(shù)值方法,記為,其中,4、已經(jīng)測(cè)得在某處海洋不同深度處的水溫如下： 深度（M） 466 741 950 1422 1634 水溫（oC）7.04 4.28 3.40 2.54 2.13 根據(jù)這些數(shù)據(jù)，希望合理

6、地估計(jì)出其它深度（如500米，600米，1000米）處的水溫,插值法,6、人口預(yù)測(cè),下面給出的是中國(guó)1900年到2000年的人口數(shù)，我們的目標(biāo)是預(yù)測(cè)未來(lái)的人口數(shù)（數(shù)據(jù)量較大時(shí)）,曲線擬合,7、鋁制波紋瓦的長(zhǎng)度問(wèn)題,建筑上用的一種鋁制波紋瓦是用一種機(jī)器將一塊平整的鋁板壓制而成的.,假若要求波紋瓦長(zhǎng)4英尺,每個(gè)波紋的高度(從中心線)為1英寸,且每個(gè)波紋以近似2英寸為一個(gè)周期. 求制做一塊波紋瓦所需鋁板的長(zhǎng)度L.,這個(gè)問(wèn)題就是要求由函數(shù)f(x)=sin x給定的曲線從x=0到x=48英寸間的弧長(zhǎng)L. 由微積分學(xué)我們知道,所求的弧長(zhǎng)可表示為:,上述積分稱為第二類橢圓積分,它不能用普通方法來(lái)計(jì)算.,數(shù)值

7、積分,A，B，C是三種蛋白質(zhì)，其反應(yīng)如下：,8、生物化學(xué)反應(yīng)的例子,常微分方程的數(shù)值方法,我們通過(guò)建?？梢缘玫饺缦路匠探M,第1章 引論,1.1 計(jì)算方法的研究?jī)?nèi)容與意義 1.2 誤差 1.3 數(shù)值方法的穩(wěn)定性與算法設(shè)計(jì)原則,1.1計(jì)算方法的研究?jī)?nèi)容與意義,計(jì)算方法研究的內(nèi)容 研究用計(jì)算機(jī)解決數(shù)學(xué)問(wèn)題的數(shù)值方法和理論。 計(jì)算機(jī)解決實(shí)際問(wèn)題的步驟 實(shí)際問(wèn)題 建立數(shù)學(xué)模型 選擇數(shù)值算法 編程計(jì)算結(jié)果 主要任務(wù) 算法設(shè)計(jì)及其理論分析和編程實(shí)現(xiàn) 算法設(shè)計(jì)：計(jì)算速度、存貯量等 算法分析：收斂性、穩(wěn)定性及誤差分析等 講授內(nèi)容 非線性方程求根、線性方程組求解、插值與擬合、數(shù)值積分、常微分方程初值問(wèn)題的數(shù)值解法

8、 算法研究的意義,算法研究的意義,引例1 計(jì)算n次多項(xiàng)式的值,1. 如果不設(shè)計(jì)算法需進(jìn)行的運(yùn)算次數(shù)為：,2. 若簡(jiǎn)單設(shè)計(jì)一下算法,這樣的算法只需作n次乘法和n次加法運(yùn)算， 這種方法稱為秦九韶算法。,n(n+1)/2次乘法和n次加法。,秦九韶算法,算法：從已知出發(fā)，經(jīng)過(guò)有限次四則運(yùn)算及規(guī)定的運(yùn)算順序構(gòu)成的完整的計(jì)算步驟。 輸入多項(xiàng)式的次數(shù)n和系數(shù)（ an,an-1,a1 ,a0）及x s= an 做循環(huán) i=n-1，0 s=s*x+ai 輸出s 此算法要求上機(jī)完成,秦九韶簡(jiǎn)介,秦九韶（公元12021261），字道古，安岳人。秦九韶與李冶、楊輝、朱世杰并稱宋元數(shù)學(xué)四大家。其父秦季棲，進(jìn)士出身，官至

9、上部郎中、秘書少監(jiān)。秦九韶聰敏勤學(xué)。宋紹定四年（1231），秦九韶考中進(jìn)士，先后擔(dān)任縣尉、通判、參議官、州守、同農(nóng)、寺丞等職。先后在湖北、安徽、江蘇、浙江等地做官，1261年左右被貶至梅州（今廣東梅縣），不久死于任所。他在政務(wù)之余，對(duì)數(shù)學(xué)進(jìn)行虔心鉆研，并廣泛搜集歷學(xué)、數(shù)學(xué)、星象、音律、營(yíng)造等資料，進(jìn)行分析、研究。 宋淳祜四至七年（1244至1247），他在為母親守孝時(shí)，把長(zhǎng)期積累的數(shù)學(xué)知識(shí)和研究所得加以編輯，寫成了聞名的巨著數(shù)學(xué)九章，并創(chuàng)造了“大衍求一術(shù)”。這 不僅在當(dāng)時(shí)處于世界領(lǐng)先地位，在近代數(shù)學(xué)和現(xiàn)代電子計(jì)算設(shè)計(jì)中，也起到了重要作用，被稱為“中國(guó)剩余定理”。他所論的“正負(fù)開方術(shù)”，被稱為“

10、秦九韶程序”?，F(xiàn)在，世界各國(guó)從小學(xué)、中學(xué)到大學(xué)的數(shù)學(xué)課程，幾乎都接觸到他的定理、定律和解題原則。秦九韶在數(shù)學(xué)方面的研究成果，比英國(guó)數(shù)學(xué)家取得的成果要早500多年。,秦九韶的數(shù)學(xué)成就及對(duì)世界數(shù)學(xué)的貢獻(xiàn)主要表現(xiàn)在：,1、秦九韶的數(shù)書九章是一部劃時(shí)代的巨著 秦九韶潛心研究數(shù)學(xué)多年，在湖州守孝三年，所寫成的世界數(shù)學(xué)名著數(shù)學(xué)九章，癸辛雜識(shí)續(xù)集稱作數(shù)學(xué)大略，永樂(lè)大典稱作數(shù)學(xué)九章。全書九章十八卷，九章九類：“大衍類”、“天時(shí)類”、“田域類”、“測(cè)望類”、“賦役類”、“錢谷類”、“營(yíng)建類”、“軍旅類”、“市物類”，每類9題（9問(wèn)）共計(jì)81題（81問(wèn)），該書內(nèi)容豐富至極，上至天文、星象、歷律、測(cè)候，下至河道、水

11、利、建筑、運(yùn)輸，各種幾何圖形和體積，錢谷、賦役、市場(chǎng)、牙厘的計(jì)算和互易。許多計(jì)算方法和經(jīng)驗(yàn)常數(shù)直到現(xiàn)在仍有很高的參考價(jià)值和實(shí)踐意義，被譽(yù)為“算中寶典”。該書著述方式，大多由“問(wèn)曰”、“答曰”、“術(shù)曰”、“草曰”四部分組成：“問(wèn)曰”，是從實(shí)際生活中提出問(wèn)題；“答曰”，給出答案；“術(shù)曰”，闡述解題原理與步驟；“草曰”，給出詳細(xì)的解題過(guò)程。此書已為國(guó)內(nèi)外科學(xué)史界公認(rèn)的一部世界數(shù)學(xué)名著。此書不僅代表著當(dāng)時(shí)中國(guó)數(shù)學(xué)的先進(jìn)水平，也標(biāo)志著中世紀(jì)世界數(shù)學(xué)的最高水平。我國(guó)數(shù)學(xué)史家梁宗巨評(píng)價(jià)道：“秦九韶的數(shù)書九章（1247年）是一部劃時(shí)代的巨著，內(nèi)容豐富，精湛絕倫。特別是大衍求一術(shù)（不定方程的中國(guó)獨(dú)特解法）及高次

12、代數(shù)方程的數(shù)值解法，在世界數(shù)學(xué)史上占有崇高的地位。那時(shí)歐洲漫長(zhǎng)的黑夜猶未結(jié)束，中國(guó)人的創(chuàng)造卻像旭日一般在東方發(fā)出萬(wàn)丈光芒?！?2、秦九韶的“大衍求一術(shù)”，領(lǐng)先高斯554年，被康托爾稱為“最幸運(yùn)的天才” 秦九韶所發(fā)明的“大衍求一術(shù)”，即現(xiàn)代數(shù)論中一次同余式組解法，是中世紀(jì)世界數(shù)學(xué)的最高成就，比西方1801年著名數(shù)學(xué)家高斯（Gauss，17771855年）建立的同余理論早554年，被西方稱為“中國(guó)剩余定理”。秦九韶不僅為中國(guó)贏得無(wú)尚榮譽(yù)，也為世界數(shù)學(xué)作出了杰出貢獻(xiàn)。 3、秦九韶的任意次方程的數(shù)值解領(lǐng)先霍納572年 秦九韶在數(shù)書九章中除“大衍求一術(shù)”外，還創(chuàng)擬了正負(fù)開方術(shù)，即任意高次方程的數(shù)值解法，

13、也是中世紀(jì)世界數(shù)學(xué)的最高成就，秦九韶所發(fā)明的此項(xiàng)成果比1819年英國(guó)人霍納（WGHorner，17861837年）的同樣解法早572年。秦九韶的正負(fù)方術(shù)，列算式時(shí)，提出“商常為正，實(shí)常為負(fù)，從常為正，益常為負(fù)”的原則，純用代數(shù)加法，給出統(tǒng)一的運(yùn)算規(guī)律，并且擴(kuò)充到任何高次方程中去。 此外，秦九韶還改進(jìn)了一次方程組的解法，用互乘對(duì)減法消元，與現(xiàn)今的加減消元法完全一致；同時(shí)秦九韶又給出了籌算的草式，可使它擴(kuò)充到一般線性方程中的解法。在歐洲最早是1559年布丟（Buteo，約14901570年，法國(guó)）給出的，他開始用不很完整的加減消元法解一次方程組，比秦九韶晚了312年，且理論上的不完整也遜于秦九韶。

14、 秦九韶還創(chuàng)用了“三斜求積術(shù)”等，給出了已知三角形三邊求三角形面積公式，與海倫（Heron，公元50年前后）公式完全一致。秦九韶還給出一些經(jīng)驗(yàn)常數(shù)，如筑土問(wèn)題中的“堅(jiān)三穿四壤五，粟率五十，墻法半之”等，即使對(duì)現(xiàn)在仍有現(xiàn)實(shí)意義。秦九韶還在十八卷77問(wèn)“推計(jì)互易”中給出了配分比例和連鎖比例的混合命題的巧妙且一般的運(yùn)算方法，至今仍有意義。,算法研究的意義,1.克萊姆法則， n=20時(shí)計(jì)算量為(n+1)n!(n-1) = 9.71020， 理論上可行，用每秒3千億次的計(jì)算機(jī)要算100年。 2. 用高斯消元法，計(jì)算量為2670 算法研究是非常必要的，算法研究包括算法設(shè)計(jì)和算法分析。,。,引例2 求n階線

15、性方程組的解,1.2 誤差 （本章重點(diǎn)：P11-P17）,誤差 近似值與準(zhǔn)確值之差，稱為誤差。 1. 誤差的來(lái)源： 模型誤差 測(cè)量誤差 截?cái)嗾`差 舍入誤差 我們只討論截?cái)嗾`差和舍入誤差。,2. 誤差的基本概念,定義1.1 設(shè)x為準(zhǔn)確值，x*為其近似值， 稱E=x-x*為近似值x*的絕對(duì)誤差，簡(jiǎn)稱誤差。,稱為x*的絕對(duì)誤差限，簡(jiǎn)稱誤差限，也叫精度。由誤差限可知準(zhǔn)確值x的范圍,x* - xx* + ,在工程中常記為 x= x* ,2. 誤差的基本概念,定義1.2 近似值x*的誤差與其準(zhǔn)確值x之比,稱為近似值x*的相對(duì)誤差。,均稱為相對(duì)誤差限,實(shí)際中經(jīng)常用,代替相對(duì)誤差限,相對(duì)誤差絕對(duì)值的任一個(gè)上界

16、,定義1.3 設(shè)x*是準(zhǔn)確值x的一個(gè)近似值，把它寫成規(guī)格化形式,x*=,(1.1),(i=1,2,m)為0到9中的某個(gè)數(shù)字，且,若x*的絕對(duì)誤差E滿足,則稱x*有n位有效數(shù)字,其中,定理1.1,定理1.1 設(shè)x*是準(zhǔn)確值x的某個(gè)近似值， 其規(guī)格化形式為(1.1)，,(1) 若x*具有n位有效數(shù)字，則x*的相對(duì)誤差,滿足,(2) 若x*的相對(duì)誤差,滿足,則x*至少具有n位有效數(shù)字。,x*=,(1.1),證明,證 10k -1=0.110k ,于是 (1) 若x*具有n位有效數(shù)字，則,即,10k,證明,(2) 若,則,于是x*至少具有n位有效數(shù)字。,思考,定理的結(jié)論可以再精確一些 精確到什么程度？

17、如何證明？ 提示：從證明的過(guò)程，考慮修正定理的結(jié)論,10k -1=0.110k ,10k,10k -1=0.a110k ,0.(a1+1)10k=(a1+1)*10k-1,1.3 數(shù)值方法的穩(wěn)定性與算法設(shè)計(jì)原則,算法設(shè)計(jì)的方法 算法設(shè)計(jì)的原則,算法設(shè)計(jì)的技術(shù),化大為小的縮減技術(shù) 例如秦九韶算法 化難為易的校正技術(shù) 例如牛頓迭代法求a的算術(shù)平方根 Xk+1= (xk+a/xk)/2 化粗為精的松弛技術(shù) 龍貝格求積算法 千古絕技“割圓術(shù)”,算法設(shè)計(jì)的原則,1. 防止大數(shù)“吃掉”小數(shù),2. 避免兩個(gè)相近數(shù)相減,3. 避免大數(shù)作乘數(shù)和小數(shù)作除數(shù),4. 減少運(yùn)算次數(shù)，避免誤差積累 例1 計(jì)算x255,5

18、.采用穩(wěn)定的算法,采用穩(wěn)定的算法,例1.2 計(jì)算積分,解： 根據(jù)分步積分公式，可得,即,有兩種方法：1.先求I0，再求I1，I2，I9 2. 先求I9，再求I8，I7，I0,例1.2 計(jì)算積分,(1) 先計(jì)算,，然后使用遞推公式,設(shè)計(jì)算值,的誤差為,易證，若,則,由此可見，若計(jì)算,時(shí)產(chǎn)生了誤差，則用該方法計(jì)算,時(shí)將誤差放大了9!=362880倍，因此該數(shù)值方法不可取。這就是不穩(wěn)定的算法。由于誤差傳播引起的危害。,誤差的傳播與積累,例3：蝴蝶效應(yīng) 一只蝴蝶在巴西扇動(dòng)翅膀，有可能會(huì)在美國(guó)的德克薩斯引起一場(chǎng)龍卷風(fēng)？！,BX,MG,以上是一個(gè)病態(tài)問(wèn)題,蝴蝶效應(yīng),先從美國(guó)麻省理工學(xué)院氣象學(xué)家洛倫茲（Lorenz）的發(fā)現(xiàn)談起。為了預(yù)報(bào)天氣，他用計(jì)算機(jī)求解仿真地球大氣的13個(gè)方程式。為了更細(xì)致地考察結(jié)果，他把一個(gè)中間解取出，提高精度再送回。而當(dāng)他喝了杯咖啡以后回來(lái)再看時(shí)竟大吃一驚：本來(lái)很小的差異，結(jié)果卻偏離了十萬(wàn)八千里！計(jì)算機(jī)沒(méi)有毛病，于是，洛倫茲（Lorenz）認(rèn)定，他發(fā)現(xiàn)了新的現(xiàn)象：“對(duì)初始值的極端不穩(wěn)定性”，即：“混沌”，又稱“蝴蝶效應(yīng)”，亞洲蝴蝶拍拍翅膀，將使美洲幾個(gè)月后出