計(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)站

考核方式一、平時(shí)占10分1．平時(shí)表現(xiàn)占10分，扣分標(biāo)準(zhǔn)如下（扣到0為止）：(1)曠課1次扣2分;(2)遲到、早退1次扣1分;(3)違反課堂紀(jì)律扣1~3分;(4)替答到扣3分，被替扣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í)間考?？茖W(xué)計(jì)算的意義科學(xué)計(jì)算與科學(xué)實(shí)驗(yàn)、科學(xué)理論并列為科學(xué)方法論的三大組成部分。關(guān)鍵時(shí)期和代表性的人物1.Galileo(1564-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è)成功典范?？茖W(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)行研究，但由于以前沒(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)的三大方法。1、一個(gè)兩千年前的例子今有上禾三秉，中禾二秉，下禾一秉，實(shí)三十九斗；上禾二秉，中禾三秉，下禾一秉，實(shí)三十四斗；上禾一秉，中禾二秉，下禾三秉，實(shí)二十六斗。問(wèn)上、中、下禾實(shí)一秉各幾何？答曰：上禾一秉九斗四分斗之一。中禾一秉四斗四分斗之一。下禾一秉二斗四分斗之三。-------《九章算術(shù)》1、一個(gè)兩千年前的例子線性方程組的數(shù)值方法！3、全球定位系統(tǒng)（GlobalPositioningSystem,GPS)全球定位系統(tǒng)：在地球的任何一個(gè)位置，至少可以同時(shí)收到4顆以上衛(wèi)星發(fā)射的信號(hào)

表示地球上一個(gè)接收點(diǎn)R的當(dāng)前位置，衛(wèi)星Si的位置為，則得到下列非線性方程組

非線性方程組的數(shù)值方法記為其中6、人口預(yù)測(cè)下面給出的是中國(guó)1900年到2000年的人口數(shù)，我們的目標(biāo)是預(yù)測(cè)未來(lái)的人口數(shù)（數(shù)據(jù)量較大時(shí)）19505519619606620719708299219809870519901143332000126743曲線擬合7、鋁制波紋瓦的長(zhǎng)度問(wèn)題建筑上用的一種鋁制波紋瓦是用一種機(jī)器將一塊平整的鋁板壓制而成的.假若要求波紋瓦長(zhǎng)4英尺,每個(gè)波紋的高度(從中心線)為1英寸,且每個(gè)波紋以近似2π英寸為一個(gè)周期.求制做一塊波紋瓦所需鋁板的長(zhǎng)度L.A，B，C是三種蛋白質(zhì)，其反應(yīng)如下：8、生物化學(xué)反應(yīng)的例子常微分方程的數(shù)值方法我們通過(guò)建?？梢缘玫饺缦路匠探M

A：B：C：

第1章引論1.1計(jì)算方法的研究?jī)?nèi)容與意義1.2誤差1.3數(shù)值方法的穩(wěn)定性與算法設(shè)計(jì)原則算法研究的意義引例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）及xs=an做循環(huán)i=n-1，……，0s=s*x+ai輸出s此算法要求上機(jī)完成2、秦九韶的“大衍求一術(shù)”，領(lǐng)先高斯554年，被康托爾稱為“最幸運(yùn)的天才”秦九韶所發(fā)明的“大衍求一術(shù)”，即現(xiàn)代數(shù)論中一次同余式組解法，是中世紀(jì)世界數(shù)學(xué)的最高成就，比西方1801年著名數(shù)學(xué)家高斯（Gauss，1777—1855年）建立的同余理論早554年，被西方稱為“中國(guó)剩余定理”。秦九韶不僅為中國(guó)贏得無(wú)尚榮譽(yù)，也為世界數(shù)學(xué)作出了杰出貢獻(xiàn)。3、秦九韶的任意次方程的數(shù)值解領(lǐng)先霍納572年秦九韶在《數(shù)書九章》中除“大衍求一術(shù)”外，還創(chuàng)擬了正負(fù)開方術(shù)，即任意高次方程的數(shù)值解法，也是中世紀(jì)世界數(shù)學(xué)的最高成就，秦九韶所發(fā)明的此項(xiàng)成果比1819年英國(guó)人霍納（W·G·Horner，1786—1837年）的同樣解法早572年。秦九韶的正負(fù)方術(shù)，列算式時(shí)，提出“商常為正，實(shí)常為負(fù)，從常為正，益常為負(fù)”的原則，純用代數(shù)加法，給出統(tǒng)一的運(yùn)算規(guī)律，并且擴(kuò)充到任何高次方程中去。此外，秦九韶還改進(jìn)了一次方程組的解法，用互乘對(duì)減法消元，與現(xiàn)今的加減消元法完全一致；同時(shí)秦九韶又給出了籌算的草式，可使它擴(kuò)充到一般線性方程中的解法。在歐洲最早是1559年布丟（Buteo，約1490—1570年，法國(guó)）給出的，他開始用不很完整的加減消元法解一次方程組，比秦九韶晚了312年，且理論上的不完整也遜于秦九韶。秦九韶還創(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.7×1020，理論上可行，用每秒3千億次的計(jì)算機(jī)要算100年。2.用高斯消元法，計(jì)算量為2670算法研究是非常必要的，算法研究包括算法設(shè)計(jì)和算法分析。。引例2求n階線性方程組的解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*-ε≤x≤x*+ε在工程中常記為x=x*±ε2.誤差的基本概念定義1.2近似值x*的誤差與其準(zhǔn)確值x之比稱為近似值x*的相對(duì)誤差。均稱為相對(duì)誤差限實(shí)際中經(jīng)常用代替相對(duì)誤差限相對(duì)誤差絕對(duì)值的任一個(gè)上界定義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.1×10k≤于是(1)若x*具有n位有效數(shù)字，則即≤10k證明(2)若則于是x*至少具有n位有效數(shù)字。思考定理的結(jié)論可以再精確一些精確到什么程度？如何證明？提示：從證明的過(guò)程，考慮修正定理的結(jié)論10k-1=0.1×10k≤≤10k10k-1=0.a1×10k≤≤0.(a1+1)10k=(a1+1)*10k-11.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ì)算x2555.采用穩(wěn)定的算法采用穩(wěn)定的算法例1.2計(jì)算積分解：根據(jù)分步積分公式，可得即有兩種方法：1.先求I0，再求I1，I2，……，I92.先求I9，再求I8，I7，……，I0例1.2計(jì)算積分(1)先計(jì)算，然后使用遞推公式設(shè)計(jì)算值的誤差為易證，若則由此可見(jiàn)，若計(jì)算時(shí)產(chǎn)生了誤差，則用該方法計(jì)算時(shí)將誤差放大了9!=362880倍，因此該數(shù)值方法不可取。這就是不穩(wěn)定的算法。由于誤差傳播引起的危害。誤差的傳播與積累例3：蝴蝶效應(yīng)——一只蝴蝶在巴西扇動(dòng)翅膀，有可能會(huì)在美國(guó)的德克薩斯引起一場(chǎng)龍卷風(fēng)？！BXMG以上是一個(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è)月后出現(xiàn)比狂風(fēng)還厲害的龍卷風(fēng)！1979年12月，洛倫茲（Lorenz）在華盛頓的美國(guó)科學(xué)促進(jìn)會(huì)的一次講演中提出：一只蝴蝶在巴西扇動(dòng)翅膀，有可能會(huì)在美國(guó)的德克薩斯引起一場(chǎng)龍卷風(fēng)。例1.2計(jì)算積分(2)先計(jì)算，然后用由(1.2)得到的遞推公式計(jì)算顯然，如果在計(jì)算時(shí)產(chǎn)生誤差則用該方法計(jì)算時(shí)的誤差為

第1章小結(jié)學(xué)習(xí)數(shù)值算法，領(lǐng)悟一條基本原理，區(qū)分兩類基本算法，掌握三種基本技術(shù)。計(jì)算機(jī)算法的設(shè)計(jì)原理都是將復(fù)雜化歸為簡(jiǎn)單的重復(fù)，或說(shuō)通過(guò)簡(jiǎn)單的重復(fù)生成復(fù)雜。計(jì)算機(jī)上的算法大致分為直接法和迭代法兩大類。直接法通過(guò)有限步計(jì)算直接得出問(wèn)題的解，而迭代法則通過(guò)某種迭代過(guò)程逐步逼近所求的解。數(shù)值算法的設(shè)計(jì)技術(shù)大致有三種：化大為小的縮減技術(shù)，化難為易的校正技術(shù)及化粗為精的松弛技術(shù)，縮減技術(shù)和校正技術(shù)分別適用于直接法和迭代法的設(shè)計(jì)，而恰當(dāng)?shù)厥褂?/p>