計算方法第一章緒論課件

參考資料《數(shù)值分析》李慶揚、王能超、易大義華中理工大學出版社1982年計算方法—算法設(shè)計及其MATLAB實現(xiàn)王能超，高等教育出版社2005年計算機數(shù)值計算方法及程序設(shè)計周煦機械工業(yè)出版社《數(shù)值方法》金一慶陳越機械工業(yè)出版社《計算方法引論》徐萃薇高等教育出版社計算方法精品課網(wǎng)站

考核方式一、平時占10分1．平時表現(xiàn)占10分，扣分標準如下（扣到0為止）：(1)曠課1次扣2分;(2)遲到、早退1次扣1分;(3)違反課堂紀律扣1~3分;(4)替答到扣3分，被替扣2分;(5)上機聊天、玩游戲、帶耳機等發(fā)現(xiàn)一次扣1分。(6)作業(yè)不及格或沒交一次扣1分。二、實驗一表占40（二表占20）分以最后的實驗上機考試分數(shù)為準，成績以百分制給出，最后折合。上機考試使用機試系統(tǒng)。程序填空和程序改錯各1題。三、期末筆試一表占50分（二表占70分）筆試試卷以百分制給出，最后折合。第8周課內(nèi)時間考?？茖W計算的意義科學計算與科學實驗、科學理論并列為科學方法論的三大組成部分。關(guān)鍵時期和代表性的人物1.Galileo(1564-1642)是實驗物理的開創(chuàng)者，倡導(dǎo)科學的數(shù)學化，為近代科學制訂了具體而有效的程序，通過關(guān)鍵實驗，演繹基本原理，達到認識世界的目的，霍金稱他為近代科學奠基人。Kepler（1571-1630）對行星數(shù)據(jù)的計算和分析，提出行星運動三大定律，是按此程序研究的一個成功典范?？茖W計算的意義2.Newton（1642-1725）開創(chuàng)了微積分，提出了力學的三大定律，特別是萬有引力定律，是科學發(fā)展進入理論思維的標志。Einstein（1878-1955）提出的相對論是這種理論思維的頂峰，在幾個世紀中，實驗方法和理論分析一直強有力地推動著科技的發(fā)展，科學家們也沒有停止過使用科學計算來進行研究，但由于以前沒有計算機，計算只能是小規(guī)模的。科學計算的意義V.Neumann(1903-1957)1945年研制的第一臺計算機帶來了科學研究的新的革命，將科學家從繁重的勞動中解放出來，目前，科學計算已發(fā)展成為一種研究方法，“科學計算與實驗、理論三足鼎立，相輔相成，成為當今科學活動的三大方法。1、一個兩千年前的例子今有上禾三秉，中禾二秉，下禾一秉，實三十九斗；上禾二秉，中禾三秉，下禾一秉，實三十四斗；上禾一秉，中禾二秉，下禾三秉，實二十六斗。問上、中、下禾實一秉各幾何？答曰：上禾一秉九斗四分斗之一。中禾一秉四斗四分斗之一。下禾一秉二斗四分斗之三。-------《九章算術(shù)》1、一個兩千年前的例子線性方程組的數(shù)值方法！3、全球定位系統(tǒng)（GlobalPositioningSystem,GPS)全球定位系統(tǒng)：在地球的任何一個位置，至少可以同時收到4顆以上衛(wèi)星發(fā)射的信號

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

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

A：B：C：

第1章引論1.1計算方法的研究內(nèi)容與意義1.2誤差1.3數(shù)值方法的穩(wěn)定性與算法設(shè)計原則算法研究的意義引例1計算n次多項式的值1.如果不設(shè)計算法需進行的運算次數(shù)為：2.若簡單設(shè)計一下算法這樣的算法只需作n次乘法和n次加法運算，這種方法稱為秦九韶算法。n(n+1)/2次乘法和n次加法。秦九韶算法算法：從已知出發(fā)，經(jīng)過有限次四則運算及規(guī)定的運算順序構(gòu)成的完整的計算步驟。輸入多項式的次數(shù)n和系數(shù)（an,an-1,…,a1,a0）及xs=an做循環(huán)i=n-1，……，0s=s*x+ai輸出s此算法要求上機完成2、秦九韶的“大衍求一術(shù)”，領(lǐng)先高斯554年，被康托爾稱為“最幸運的天才”秦九韶所發(fā)明的“大衍求一術(shù)”，即現(xiàn)代數(shù)論中一次同余式組解法，是中世紀世界數(shù)學的最高成就，比西方1801年著名數(shù)學家高斯（Gauss，1777—1855年）建立的同余理論早554年，被西方稱為“中國剩余定理”。秦九韶不僅為中國贏得無尚榮譽，也為世界數(shù)學作出了杰出貢獻。3、秦九韶的任意次方程的數(shù)值解領(lǐng)先霍納572年秦九韶在《數(shù)書九章》中除“大衍求一術(shù)”外，還創(chuàng)擬了正負開方術(shù)，即任意高次方程的數(shù)值解法，也是中世紀世界數(shù)學的最高成就，秦九韶所發(fā)明的此項成果比1819年英國人霍納（W·G·Horner，1786—1837年）的同樣解法早572年。秦九韶的正負方術(shù)，列算式時，提出“商常為正，實常為負，從常為正，益常為負”的原則，純用代數(shù)加法，給出統(tǒng)一的運算規(guī)律，并且擴充到任何高次方程中去。此外，秦九韶還改進了一次方程組的解法，用互乘對減法消元，與現(xiàn)今的加減消元法完全一致；同時秦九韶又給出了籌算的草式，可使它擴充到一般線性方程中的解法。在歐洲最早是1559年布丟（Buteo，約1490—1570年，法國）給出的，他開始用不很完整的加減消元法解一次方程組，比秦九韶晚了312年，且理論上的不完整也遜于秦九韶。秦九韶還創(chuàng)用了“三斜求積術(shù)”等，給出了已知三角形三邊求三角形面積公式，與海倫（Heron，公元50年前后）公式完全一致。秦九韶還給出一些經(jīng)驗常數(shù)，如筑土問題中的“堅三穿四壤五，粟率五十，墻法半之”等，即使對現(xiàn)在仍有現(xiàn)實意義。秦九韶還在十八卷77問“推計互易”中給出了配分比例和連鎖比例的混合命題的巧妙且一般的運算方法，至今仍有意義。算法研究的意義1.克萊姆法則，n=20時計算量為(n+1)n!(n-1)=9.7×1020，理論上可行，用每秒3千億次的計算機要算100年。2.用高斯消元法，計算量為2670算法研究是非常必要的，算法研究包括算法設(shè)計和算法分析。。引例2求n階線性方程組的解1.2誤差

（本章重點：P11-P17）誤差近似值與準確值之差，稱為誤差。1.誤差的來源：模型誤差測量誤差截斷誤差舍入誤差我們只討論截斷誤差和舍入誤差。2.誤差的基本概念定義1.1設(shè)x為準確值，x*為其近似值，稱E=x-x*為近似值x*的絕對誤差，簡稱誤差。ε稱為x*的絕對誤差限，簡稱誤差限，也叫精度。由誤差限ε可知準確值x的范圍x*-ε≤x≤x*+ε在工程中常記為x=x*±ε2.誤差的基本概念定義1.2近似值x*的誤差與其準確值x之比稱為近似值x*的相對誤差。均稱為相對誤差限實際中經(jīng)常用代替相對誤差限相對誤差絕對值的任一個上界定義1.3設(shè)x*是準確值x的一個近似值，把它寫成規(guī)格化形式

x*=(1.1)(i=1,2,…,m)為0到9中的某個數(shù)字，且若x*的絕對誤差E滿足則稱x*有n位有效數(shù)字其中定理1.1定理1.1設(shè)x*是準確值x的某個近似值，其規(guī)格化形式為(1.1)，(1)若x*具有n位有效數(shù)字，則x*的相對誤差滿足(2)若x*的相對誤差滿足則x*至少具有n位有效數(shù)字。

x*=(1.1)證明證10k-1=0.1×10k≤于是(1)若x*具有n位有效數(shù)字，則即≤10k證明(2)若則于是x*至少具有n位有效數(shù)字。思考定理的結(jié)論可以再精確一些精確到什么程度？如何證明？提示：從證明的過程，考慮修正定理的結(jié)論10k-1=0.1×10k≤≤10k10k-1=0.a1×10k≤≤0.(a1+1)10k=(a1+1)*10k-11.3數(shù)值方法的穩(wěn)定性與算法設(shè)計原則算法設(shè)計的方法算法設(shè)計的原則算法設(shè)計的技術(shù)化大為小的縮減技術(shù)例如秦九韶算法化難為易的校正技術(shù)例如牛頓迭代法求a的算術(shù)平方根Xk+1=(xk+a/xk)/2化粗為精的松弛技術(shù)龍貝格求積算法千古絕技“割圓術(shù)”算法設(shè)計的原則1.防止大數(shù)“吃掉”小數(shù)2.避免兩個相近數(shù)相減3.避免大數(shù)作乘數(shù)和小數(shù)作除數(shù)4.減少運算次數(shù)，避免誤差積累例1計算x2555.采用穩(wěn)定的算法采用穩(wěn)定的算法例1.2計算積分解：根據(jù)分步積分公式，可得即有兩種方法：1.先求I0，再求I1，I2，……，I92.先求I9，再求I8，I7，……，I0例1.2計算積分(1)先計算，然后使用遞推公式設(shè)計算值的誤差為易證，若則由此可見，若計算時產(chǎn)生了誤差，則用該方法計算時將誤差放大了9!=362880倍，因此該數(shù)值方法不可取。這就是不穩(wěn)定的算法。由于誤差傳播引起的危害。誤差的傳播與積累例3：蝴蝶效應(yīng)——一只蝴蝶在巴西扇動翅膀，有可能會在美國的德克薩斯引起一場龍卷風？！BXMG以上是一個病態(tài)問題蝴蝶效應(yīng)先從美國麻省理工學院氣象學家洛倫茲（Lorenz）的發(fā)現(xiàn)談起。為了預(yù)報天氣，他用計算機求解仿真地球大氣的13個方程式。為了更細致地考察結(jié)果，他把一個中間解取出，提高精度再送回。而當他喝了杯咖啡以后回來再看時竟大吃一驚：本來很小的差異，結(jié)果卻偏離了十萬八千里！計算機沒有毛病，于是，洛倫茲（Lorenz）認定，他發(fā)現(xiàn)了新的現(xiàn)象：“對初始值的極端不穩(wěn)定性”，即：“混沌”，又稱“蝴蝶效應(yīng)”，亞洲蝴蝶拍拍翅膀，將使美洲幾個月后出現(xiàn)比狂風還厲害的龍卷風！1979年12月，洛倫茲（Lorenz）在華盛頓的美國科學促進會的一次講演中提出：一只蝴蝶在巴西扇動翅膀，有可能會在美國的德克薩斯引起一場龍卷風。例1.2計算積分(2)先計算，然后用由(1.2)得到的遞推公式計算顯然，如果在計算時產(chǎn)生誤差則用該方法計算時的誤差為

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