數(shù)值分析緒論P(yáng)PT課件

應(yīng)用問題舉例應(yīng)用問題舉例第1頁/共76頁263234323923zyxzyxzyx今有上禾三秉，中禾二秉，下禾一秉，實(shí)三十九斗； 上禾二秉，中禾三秉，下禾一秉，實(shí)三十四斗； 上禾一秉，中禾二秉，下禾三秉，實(shí)二十六斗。問上、中、下禾實(shí)一秉各幾何？答曰：上禾一秉九斗四分斗之一。中禾一秉四斗四分斗之一。下禾一秉二斗四分斗之三。-九章算術(shù)1、一個(gè)兩千年前的例子第2頁/共76頁nnnnnnaaaaaaaaa212222111211bxAnnbbbxxx2121第3頁/共76頁2 2、天體力學(xué)中的、天體力學(xué)中的KeplerKepler方程方程x是行星運(yùn)動(dòng)的軌道，它是時(shí)間t 的函數(shù).sin0,01xxt 第4頁/共76頁全球定位系統(tǒng)：全球定位系統(tǒng)：在地球的任何在地球的任何一個(gè)位置，至一個(gè)位置，至少可以同時(shí)收少可以同時(shí)收到到4 4顆以上衛(wèi)星顆以上衛(wèi)星發(fā)射的信號(hào)發(fā)射的信號(hào) 3、全球定位系統(tǒng)（全球定位系統(tǒng)（Global Positioning System, Global Positioning System, GPS)GPS)第5頁/共76頁02468051002468圖 7.8HeightS6S3S4S2S1RS5N-S positions 表示地球上一個(gè)接收點(diǎn)R的當(dāng)前位置，衛(wèi)星Si的位置為 ，則得到下列非線性方程組( , , )x y z t(,)iiiixyzt222111122222222223333222444422255552226666()()()(t -t)0()()()(t -t)0()()()(t -t)0()()()(t -t)0()()()(t -t)0()()()(t -t)xxyyzzcxxyyzzcxxyyzzcxxyyzzcxxyyzzcxxyyzz0c第6頁/共76頁11221212( ,)0( ,)0( ,)0nnnnf x xxfx xxfx xx( )0F x 記為其中，:,nnF DRR12( ,)Tnxx xx第7頁/共76頁4 4、已經(jīng)測(cè)得在某處海洋不同深度處的水溫如下：、已經(jīng)測(cè)得在某處海洋不同深度處的水溫如下：深度（深度（M M） 466 741 950 1422 1634466 741 950 1422 1634水溫（水溫（o oC C）7.04 4.28 3.40 2.54 2.137.04 4.28 3.40 2.54 2.13根據(jù)這些數(shù)據(jù)，希望合理地估計(jì)出其它深度（如根據(jù)這些數(shù)據(jù)，希望合理地估計(jì)出其它深度（如500500米，米，600600米，米，10001000米米）處的水溫）處的水溫第8頁/共76頁5 5、用比較簡(jiǎn)單的函數(shù)代替復(fù)雜的函數(shù)、用比較簡(jiǎn)單的函數(shù)代替復(fù)雜的函數(shù)誤差為最小，即距離為最小（在不同的度量意義下）第9頁/共76頁6 6、人口預(yù)測(cè)、人口預(yù)測(cè) 下面給出的是中國(guó)下面給出的是中國(guó)19001900年到年到20002000年的人口數(shù)，年的人口數(shù)，我們的目標(biāo)是預(yù)測(cè)未來我們的目標(biāo)是預(yù)測(cè)未來的人口數(shù)（數(shù)據(jù)量較大的人口數(shù)（數(shù)據(jù)量較大時(shí)）時(shí)）1950551961960662071970829921980987051990114333200012674330/ )1979( ts432231sssy第10頁/共76頁第11頁/共76頁7 7、鋁制波紋瓦的長(zhǎng)度問題、鋁制波紋瓦的長(zhǎng)度問題 建筑上用的一種鋁制波紋瓦是用一種機(jī)器將一塊平整的鋁板壓制而成的.假若要求波紋瓦長(zhǎng)4英尺,每個(gè)波紋的高度(從中心線)為1英寸,且每個(gè)波紋以近似2英寸為一個(gè)周期. 求制做一塊波紋瓦所需鋁板的長(zhǎng)度L.第12頁/共76頁 這個(gè)問題就是要求由函數(shù)這個(gè)問題就是要求由函數(shù)給定的給定的曲線從曲線從x x=0=0到到x x=48=48英寸間的弧長(zhǎng)英寸間的弧長(zhǎng)L.L. 由微積分學(xué)我們知道由微積分學(xué)我們知道, ,所求的弧長(zhǎng)可表示為所求的弧長(zhǎng)可表示為: :dxxdxxfL48024802)(cos1)(1上述積分稱為第二類橢圓積分,它不能用普通方法來計(jì)算.第13頁/共76頁第14頁/共76頁理論研究科學(xué)實(shí)驗(yàn)科學(xué)計(jì)算計(jì)算數(shù)學(xué)諾貝爾獎(jiǎng)得主,計(jì)算物理學(xué)家 Wilson提出 現(xiàn)代科學(xué)研究的三大支柱第15頁/共76頁第16頁/共76頁 科學(xué)方法論的巨大變革： 如果說伽利略和牛頓在科學(xué)發(fā)展史上奠定了實(shí)驗(yàn)和理論這兩大科學(xué)方法的支柱，那么由馮.諾依曼研制的現(xiàn)代電子計(jì)算機(jī)把計(jì)算推上了人類科學(xué)活動(dòng)的前沿，使計(jì)算成為第三種方法。第17頁/共76頁建立數(shù)學(xué)模型選取計(jì)算方法編寫上機(jī)程序計(jì)算得出結(jié)果第18頁/共76頁數(shù)值計(jì)算方法是計(jì)算數(shù)學(xué)的一個(gè)主要組成部分，“什么是數(shù)值計(jì)算方法？”它主要研究使用計(jì)算機(jī)求解各種科學(xué)與工程計(jì)算問題的數(shù)值方法（近似方法）;對(duì)求得的解的精度進(jìn)行評(píng)估以及在計(jì)算機(jī)上實(shí)現(xiàn)求解等。 數(shù)值計(jì)算方法已經(jīng)成為計(jì)算機(jī)處理實(shí)際問題的一個(gè)重要手段，從宏觀天體運(yùn)動(dòng)學(xué)到微觀分子細(xì)胞學(xué)，從工程系統(tǒng)到社會(huì)經(jīng)濟(jì)系統(tǒng)，無一能離開數(shù)值計(jì)算方法。因此，數(shù)值計(jì)算與計(jì)算機(jī)模擬被稱為“第三種研究科學(xué)方法”。第19頁/共76頁第20頁/共76頁分形圖混沌圖第21頁/共76頁一、計(jì)算數(shù)學(xué)的產(chǎn)生和早期發(fā)展計(jì)算數(shù)學(xué)是數(shù)學(xué)的一個(gè)古老的分支，雖然數(shù)學(xué)不僅僅是計(jì)算，但推動(dòng)數(shù)學(xué)產(chǎn)生和發(fā)展的最直接原因還是。 二、二十世紀(jì)計(jì)算數(shù)學(xué)的發(fā)展數(shù)值代數(shù) 最優(yōu)化計(jì)算 數(shù)值逼近 計(jì)算幾何 概率統(tǒng)計(jì)計(jì)算 蒙特卡羅方法 微分方程的數(shù)值解法 微分方程的反演問題 第22頁/共76頁傳統(tǒng)的數(shù)值計(jì)算的主要研究?jī)?nèi)容：1、數(shù)值逼近 插值與擬合、FFT、數(shù)值積分與微分2、數(shù)值代數(shù) 代數(shù)基礎(chǔ)、線性代數(shù)方程組的解法、非線性代數(shù)方程（組）的解法、特征值與特征向量3、微分方程數(shù)值解 ODE、PDE和有限元法4、最優(yōu)化方法 無約束優(yōu)化與有約束優(yōu)化方法 現(xiàn)代計(jì)算方法：融進(jìn)了機(jī)器學(xué)習(xí)計(jì)算、仿生計(jì)算、網(wǎng)絡(luò)計(jì)算、以數(shù)據(jù)為核心的計(jì)算和各種普適計(jì)算、非線性科學(xué)計(jì)算等內(nèi)容。第23頁/共76頁數(shù)值計(jì)算方法的主要特點(diǎn)借助計(jì)算機(jī)提供切實(shí)可行的數(shù)學(xué)算法.想的精確度;收斂且穩(wěn)定;誤差可以分析或估計(jì).所提出的算法必須具有：可靠的理論分析;理時(shí)間復(fù)雜性好_指節(jié)省時(shí)間；空間復(fù)雜性好_指節(jié)省存儲(chǔ)量。計(jì)算復(fù)雜性好 通過數(shù)值實(shí)驗(yàn)證明算法行之有效.第24頁/共76頁F采用“近似替代”方法逼近F采用“構(gòu)造性”方法F采用“離散化”方法 把求連續(xù)變量的問題轉(zhuǎn)化為求離散變量的問題F采用“遞推化”方法 復(fù)雜的計(jì)算歸結(jié)為簡(jiǎn)單過程的多次重復(fù)，易于用循環(huán)結(jié)構(gòu)來實(shí)現(xiàn)（迭代法）。F采用各種搜索方法構(gòu)造數(shù)值算法主要手段第25頁/共76頁如何學(xué)好數(shù)值計(jì)算方法？第26頁/共76頁 希 望： 求近似解，但方法簡(jiǎn)單可行，行之有效 （計(jì)算量小，誤差小,需存儲(chǔ)單元少等）, 以計(jì)算機(jī)為工具，易在計(jì)算機(jī)上實(shí)現(xiàn)。 計(jì)算機(jī)運(yùn)算: 只能進(jìn)行加，減，乘，除等算術(shù)運(yùn)算和一 些邏輯運(yùn)算。 數(shù)值計(jì)算方法： 把求解數(shù)學(xué)問題轉(zhuǎn)化為按一定次序只進(jìn)行 加，減，乘，除等基本運(yùn)算.設(shè)計(jì)數(shù)值算法的出發(fā)點(diǎn)？第27頁/共76頁威爾金森（James Hardy .Wilkinson，1919-1986） Wilkinson是數(shù)值分析和數(shù)值計(jì)算的開拓者和奠基人。1940 年，開始研究彈道的數(shù)學(xué)模型與數(shù)值計(jì)算。 1946 年成為Turing 的助手，協(xié)助設(shè)計(jì) Pilot ACE 計(jì)算機(jī)。1969年他當(dāng)選為英國(guó)皇家學(xué)會(huì)院士；1970年工業(yè)和應(yīng)用數(shù)學(xué)會(huì)(s1am)授予他馮諾伊曼獎(jiǎng)；1987年他獲得美國(guó)數(shù)學(xué)會(huì)的chauvenet獎(jiǎng)。著名的美國(guó)阿爾貢國(guó)家實(shí)驗(yàn)室曾聘威爾金森為榮譽(yù)高級(jí)研究員并兩次向他授獎(jiǎng)。 Wilkinson在數(shù)值分析研究領(lǐng)域作出了杰出貢獻(xiàn)，是數(shù)值計(jì)算的早期開拓者，其工作加速了數(shù)字計(jì)算機(jī) ( 在科學(xué)計(jì)算中 ) 的使用。他研究的主要問題是線性代數(shù)方程組和矩陣特征值問題的數(shù)值解法，特別是他的向后誤差分析法 (backward error analysis)的創(chuàng)造性工作奠定了數(shù)值分析和數(shù)值計(jì)算早期的理論基礎(chǔ)。 1975 年 J. H. Wilkinson成為第五位圖靈獎(jiǎng)獲得者。第28頁/共76頁&教材 現(xiàn)代科學(xué)與工程計(jì)算 孟大志 劉偉（高等教育出版社） &參考書目 數(shù)值分析 孫志忠 袁慰平等（東南大學(xué)出版社,第二版） 應(yīng)用數(shù)值方法 使用MATLAB和C語言 Robert J.Schilling & Sandra L.Harris （機(jī)械工業(yè)出版社） 數(shù)值分析基礎(chǔ)教程 李慶揚(yáng) 編 （高等教育出版社） 現(xiàn)代數(shù)值分析 李慶揚(yáng)、易大義、王能超 編著 （高等教育出版社） 數(shù)值分析與科學(xué)計(jì)算 Jeffery J.Leader 著，張威，劉志軍，李艷紅等譯，（清華大學(xué)出版社) 第29頁/共76頁一、算法的概念 描述算法可以有不同的方式。例如，可以用日常語言和數(shù)學(xué)語言加以敘述，也可以借助形式語言（算法語言）給出精確的說明，也可以用框圖直觀地顯示算法的全貌。 定義：由基本運(yùn)算及運(yùn)算順序的規(guī)定所構(gòu)成的完整的 解題步驟，稱為。第30頁/共76頁例：求解二元一次聯(lián)立方程組22221211212111bxaxabxaxa用行列式解法：首先判別 （1）如果 ，則令計(jì)算機(jī)計(jì)算 , 1222211DababxDababx2111122輸出計(jì)算的結(jié)果x1，x2。（2）如果D= 0，則或是無解，或有無窮多組解。是否為零，存在兩種可能：第31頁/共76頁12212211Daaaa令通過求解過程，可以總結(jié)出算法步驟如下：S2 計(jì)算12212211DaaaaS3 如果0D 則輸出原方程無解或有無窮多組解的信息;否則0D D1212112babax D2121221babaxS1 輸入2122211211,bbaaaaS4 輸出計(jì)算的結(jié)果21,xx第32頁/共76頁輸入2122211211,bbaaaa D=a11a22-a12a21D=0開始DababxDababx/ )(/ )(21111221222211輸出 x1, x2 結(jié) 束 No輸出無解信息Yes第33頁/共76頁二、算法優(yōu)劣的判別 計(jì)算量的大小 存貯量 邏輯結(jié)構(gòu)例：用行列式解法求解線性方程組: n階方程組，要計(jì)算n + 1個(gè)n階行列式的值， 總共需要做n! (n - 1) (n + 1) 次乘法運(yùn)算。 n=20 需要運(yùn)算多少次？n=100?第34頁/共76頁一、誤差的來源與分類 從實(shí)際問題中抽象出數(shù)學(xué)模型 模型誤差例:質(zhì)量為m的物體，在重力作用下,自由下落， 其下落距離s 與時(shí)間t 的關(guān)系是： mgdtsdm22其中 g 為重力加速度。第35頁/共76頁 通過測(cè)量得到模型中參數(shù)的值 觀測(cè)誤差 求近似解 方法誤差 (截?cái)嗾`差）例如，當(dāng)函數(shù) f x 用Taylor多項(xiàng)式 ( )200001!2!nnnfffPxfxxxn 近似代替時(shí)，數(shù)值方法的截?cái)嗾`差是 (1)1(1)!nnnnfRxf xPxxn 與0之間。在x第36頁/共76頁機(jī)器字長(zhǎng)有限 舍入誤差 用計(jì)算機(jī)、計(jì)算器和筆算，都只能用有限位 = 3.1415926 小數(shù)來代替無窮小數(shù)或用位數(shù)較少的小數(shù)來代替位數(shù)較多的有限小數(shù)，如：10.33333第37頁/共76頁四舍五入后0000074. 01416. 31000033. 0333. 031238.12350.00005x在數(shù)值計(jì)算方法中，主要研究和（包括初始數(shù)據(jù)的誤差）對(duì)計(jì)算結(jié)果的影響！第38頁/共76頁二、 誤差的概念1、絕對(duì)誤差與絕對(duì)誤差限( *)*e xx x 例 :若用以厘米為最小刻度的尺去量桌子的長(zhǎng)，大約為1.45米，求1.45米的絕對(duì)誤差。1.45米的絕對(duì)誤差=？不知道！是近似值 的,簡(jiǎn)稱為。 *x定義：設(shè) 是準(zhǔn)確值，為 的一個(gè)近似值，稱 x*xx第39頁/共76頁*xxx*xx*e x*xxx*,xxx*x第40頁/共76頁2、相對(duì)誤差與相對(duì)誤差限定義：設(shè) 是準(zhǔn)確值， 是近似值，是近似值的誤差，x通常取為近似值 的，記作 ，*re*x*e*exxxx稱第41頁/共76頁事實(shí)上，當(dāng) 較小時(shí)*reex 22*1exxee xeexxx xx xe x是 的二次方項(xiàng)級(jí),故可忽略不計(jì).*re相應(yīng)地，若正數(shù)r滿足*rxxx 則稱 為 的相對(duì)誤差限。r*x第42頁/共76頁3 、有效數(shù)字定義：如果nxx1021*則說 近似表示 準(zhǔn)確到小數(shù)后第 位，并從這由上述定義410211416. 35102114159. 3*xxn第 位起直到最左邊的非零數(shù)字之間的一切數(shù)字都稱為并把有效數(shù)字的位數(shù)稱為。n第43頁/共76頁定義 :*121210101010mnnxaaa *若近似值 的誤差限是某一位的半個(gè)單位,*x也即，若*1102m nxx有 位有效數(shù)字。n*x其中， 是1到9中的一個(gè)數(shù)字； 是0到9中一個(gè)數(shù)字； 為整數(shù)，且 1a2naam該位到 的左邊第一位非零數(shù)字共有 位,*xn就說 有 位有效數(shù)字。*xn第44頁/共76頁取 作 的近似值， 就有三位有效數(shù)字；*3.14x *x取 作 的近似值， 就有五位有效數(shù)字。*3.1416x *x第45頁/共76頁4 、誤差限與有效數(shù)字的關(guān)系 則 至少具有 位有效數(shù)字。Th1.1： *xn對(duì)于用 式表示的近似數(shù) ，若 具有 位有效數(shù)字，則其相對(duì)誤差限為反之，若 的相對(duì)誤差限為 *xn*x1*11102nra *x1*11102(1)nra 第46頁/共76頁Th1.2： *1210.10mnnxx xx x設(shè)反之,若 的相對(duì)誤差的絕對(duì)值大于 ，*x1102n其中 為整數(shù), 為正整數(shù), 。n10 x m有 位有效數(shù)字。n則 至多*x若 至多有 位有效數(shù)字,即 是有效數(shù)字,nx*xn而 不是有效數(shù)字,1nx則 的相對(duì)誤差的絕對(duì)值必大于 ;11102n *x第47頁/共76頁證明：1nx不是有效數(shù)字 反之,若 則 *1102nrxxx *rxxx 1*1102m nx 1110210m nm 11102n *1102nxxx1110102nm11102m n 11102mn1nx不是有效數(shù)字， 即 至多有 位有效數(shù)字. *xn第48頁/共76頁、*1x*2x*1x*2x*1212xxxx *121221x xxxxx*1221*122* 22/0()xxxxxxxx第49頁/共76頁、當(dāng)自變量有誤差時(shí)，計(jì)算函數(shù)值也會(huì)產(chǎn)生誤差，其誤差限可利用函數(shù)的Taylor展開式進(jìn)行估計(jì)。設(shè) 是一元函數(shù)， 的近似值為 ,以 近似 ，其誤差限記作 ，可用Taylor展開 f xx*x*f x f x*f x 2*2ff xf xfxxxxx *, x x *2*2ff xf xfxe xx 第50頁/共76頁假定 與 的比值不太大,可忽略 的高階項(xiàng),于是可得計(jì)算函數(shù)的誤差為*fx*fx*x *f xfxx 當(dāng) 為多元函數(shù)時(shí)計(jì)算 ,如果f12,nAf x xx12,nx xx的近似值為 ,則 的近似為*12,nx xxA*12,nAf xxx于是函數(shù)值 的誤差 由Taylor展開,*A*e A第51頁/共76頁*1;nkkkfAxx*A*1.kkrrkkAxfAxAA *1212,nne AAAf x xxf x xx*12*11,nnnkkkkkkkf x xxfxxexx第52頁/共76頁l*110lmd*80dm*0.2llm*0.1ddmSld *,SSSldld*80 ,110 ,SSdmlmld,SSSlddlld第53頁/共76頁 *0.2 ,0.1 ,lmdm*2280 0.2 110 0.127;Smm*270.31.8800rSSSl dS第54頁/共76頁 算法的數(shù)值穩(wěn)定性 數(shù)值計(jì)算在設(shè)計(jì)算法時(shí)首先關(guān)心的是由它產(chǎn)生的計(jì)算結(jié)果的穩(wěn)定性，而算法的穩(wěn)定性與舍入誤差是否增長(zhǎng)密切相關(guān)。一個(gè)算法如果輸入數(shù)據(jù)有微小擾動(dòng)（即誤差），而在計(jì)算過程中舍入誤差不增長(zhǎng)，則稱此算法是數(shù)值穩(wěn)定的，否則稱其為數(shù)值不穩(wěn)定。 第55頁/共76頁例：求定積分 10(0,1,2,8)5nnxIdx nx解：直接積分可產(chǎn)生遞推公式若取初值)2 . 1ln(5ln6lndx51100 xI11105515(1)5nnnxIxdxIxn第56頁/共76頁可得遞推公式)8, 2, 1(,51)2 . 1ln(10nInIInn按公式就可以逐步算出101 50.09II 05. 052112II083. 053123II165. 054134II025. 155145II952. 456156II注意此公式精確成立，且What happened?!不穩(wěn)定的算法 ！0nI 第57頁/共76頁NYBJ蝴蝶效應(yīng) 紐約的一只蝴蝶翅膀一拍，風(fēng)和日麗的北京就刮起臺(tái)風(fēng)來了？！這是一個(gè)病態(tài)問題第58頁/共76頁由題設(shè)中的遞推公式（1）可看出， 的誤差擴(kuò)大了1nI5倍后傳給 ，因而初值 的誤差對(duì)以后各步nI0I這就造成 的計(jì)算結(jié)果嚴(yán)重失真。4I計(jì)算結(jié)果的影響，隨著 的增大愈來愈嚴(yán)重。n第59頁/共76頁可求得I9 0.017，按改寫后的公式可逐次求得不妨設(shè)I9 I10，于是由10951501II) 1 , 1,( 51511nnkIkIkknIInn151將公式變?yōu)榈?0頁/共76頁I8 0.019 I7 0.021I6 0.024 I8 0.028I4 0.034 I3 0.043I2 0.058 I1 0.088I0 0.182 穩(wěn)定的算法 ！ 在我們今后的討論中，誤差將不可回避， 算法的穩(wěn)定性會(huì)是一個(gè)非常重要的話題。第61頁/共76頁注：遞推公式(1)的舍入誤差以5的冪次增長(zhǎng)進(jìn)行傳播，因此是數(shù)值不穩(wěn)定的，而遞推公式(2)的舍入誤差在一定范圍內(nèi)以0.2的冪次進(jìn)行傳播，隨著n的增大，誤差逐步減少，因此該算法是數(shù)值穩(wěn)定的。 因此，可以看出數(shù)值不穩(wěn)定的算法是不能使用的，實(shí)際計(jì)算中對(duì)任何輸入數(shù)據(jù)都是數(shù)值穩(wěn)定的算法，稱為無條件穩(wěn)定。而對(duì)某些數(shù)據(jù)數(shù)值穩(wěn)定，對(duì)其它數(shù)據(jù)數(shù)值不穩(wěn)定的算法，稱為條件穩(wěn)定。第62頁/共76頁 病態(tài)問題和條件數(shù) 如果問題的輸入數(shù)據(jù)有微小擾動(dòng)，就會(huì)引起輸出結(jié)果數(shù)據(jù)（即解）的很大擾動(dòng)，稱這樣的問題為病態(tài)問題。相反的情形稱為良態(tài)問題。對(duì)于病態(tài)的數(shù)學(xué)問題，用通常的算法求數(shù)值解都是不穩(wěn)定的。 病態(tài)和良態(tài)是相對(duì)的，沒有嚴(yán)格的界限，通常用條件數(shù)大小來衡量問題的病態(tài)程度，條件數(shù)越大病態(tài)可能越嚴(yán)重。 條件數(shù)c(x)越大，f(x)的相對(duì)誤差越大，通常認(rèn)為( )1c x時(shí)，問題是病態(tài)的。第63頁/共76頁1.要避免兩個(gè)相近的數(shù)相減在數(shù)值計(jì)算中，兩個(gè)相近的數(shù)作減法時(shí)有效數(shù)字會(huì)損失。例: 求xxy1的值。當(dāng)x = 1000，y 的準(zhǔn)確值為0.01580 第64頁/共76頁類似地 yxyxlnlnln2sin2cos2sin)sin(xxx(2) 若將原式改寫為xxxxy111則 y = 0.01581(1)直接相減有3位有效數(shù)字！只有1位有效數(shù)字第65頁/共76頁2.盡量避免絕對(duì)值太小的數(shù)作分母例：如分母變?yōu)?.0011，也即分母只有0.0001的變化時(shí)第66頁/共76頁3. 避免大數(shù)吃小數(shù)精確解為 算法1：利用求根公式第67頁/共76頁在計(jì)算機(jī)內(nèi)，109存為0.11010，1存為0.1101。做加法時(shí)，兩加數(shù)的指數(shù)先向大指數(shù)對(duì)齊，再將浮點(diǎn)部分相加。即1 的指數(shù)部分須變?yōu)?010，則：1 = 0.0000000001 1010，取單精度時(shí)就成為： 109+1=0.100000001010+0.00000000 1010=0.10000000 1010第68頁/共76頁算法2：先解出再利用求和時(shí)從小到大相加，可使和的誤差減小。例：按從小到大、以及從大到小的順序分別計(jì)算1 + 2 + 3 + + 40 + 109第69頁/共76頁4. 簡(jiǎn)化計(jì)算步驟，避免誤差積累。一般來說，計(jì)算機(jī)處理下列運(yùn)算的速度為例：多項(xiàng)式求值：給定的x 求下列n 次多項(xiàng)式的值。 解：1. 用一般算法，即直接求和法； 2. 逐項(xiàng)求和法；3. 秦九韶方法(即Hornor算法）；第70頁/共76頁算法的遞推性計(jì)算機(jī)上使用的算法常采用遞推化的形式，遞推化的基本思想是把一個(gè)復(fù)雜的計(jì)算過程歸結(jié)為簡(jiǎn)單過程的多次重復(fù)。這種重復(fù)在程序上表現(xiàn)為循環(huán)。遞推化的優(yōu)點(diǎn)是簡(jiǎn)化結(jié)構(gòu)和節(jié)省計(jì)算量。第71頁/共76頁例：用秦九韶方法求多項(xiàng)式解： Ka5-KvK00.008330.00833v0 = a510.041670.04v1 = v0 x+a420.166670.15867v2 = v1x+a330.50.46827v3 = v2x+a2410.90635v4 = v3x+a1510.81873v5 = v4x+a0第72頁/共76頁約翰馮諾依曼 （John von Neumann,1903-1957）美藉匈牙利人，1930年接受了普林斯頓大學(xué)客座教授的職位，西渡美國(guó)。 1931年成為該校終身教授。1933年成為新成立的普林斯頓高等研究院的終身研究員。1951年至1953 年任美國(guó)數(shù)學(xué)會(huì)主席。馮諾依曼是20世紀(jì)少有的數(shù)學(xué)科學(xué)通才，在許多領(lǐng)域都有重要的貢獻(xiàn)，被西方人譽(yù)為“數(shù)學(xué)奇才、計(jì)算機(jī)之父”。馮諾依曼對(duì)人類的最大貢獻(xiàn)是對(duì)計(jì)算機(jī)科學(xué)、計(jì)算機(jī)技術(shù)和數(shù)值分析的開拓性工作。第73頁/共76頁并行計(jì)算 一、 電子計(jì)算機(jī)的并行計(jì)算分類 傳統(tǒng)計(jì)算機(jī)一般采用Von Neumann結(jié)構(gòu)，每一時(shí)刻只有一個(gè)進(jìn)程的算法，即串行算法。 并行計(jì)算機(jī)每一時(shí)刻具有2個(gè)以上的進(jìn)程的算法稱為并行算法。并行機(jī)必須包含2臺(tái)以上處理機(jī)，按指令流是單個(gè)還是多個(gè)并行算法可分為兩類： SIMD算法適用于單指令流多數(shù)據(jù)流系統(tǒng)； MIMD算法適用于多指令流多數(shù)據(jù)流系統(tǒng)。 按照進(jìn)程之間是否同步可將并行算法分為: 同步算法:是指在k個(gè)進(jìn)程的算法中有些進(jìn)程的若干算法必須在另一些進(jìn)程的某些算法之后執(zhí)行； 異步算法:指k個(gè)進(jìn)程間有信息聯(lián)系但不須同步，它只能在一個(gè)具有k臺(tái)處理機(jī)的MIMD系統(tǒng)中實(shí)現(xiàn)。第74頁/共76頁二、并行計(jì)算的算法設(shè)計(jì) 并行算法設(shè)計(jì)的重要原則是“分而治之”。其基本思想是把問題依次劃分為可以獨(dú)立完成的較小問題，將規(guī)模逐次減半的二分技術(shù)是并行算法設(shè)計(jì)的一種基本技術(shù)。 二分算法的設(shè)計(jì)原理是反復(fù)地將所給計(jì)算問題加工成規(guī)模減半的同類計(jì)算問題而計(jì)算?？衫么兴惴▉砀脑旎蛟O(shè)計(jì)并行算法，不少數(shù)值算法包含了可直接利用的并行性。還可以根據(jù)并行算法的特點(diǎn)設(shè)計(jì)具有新思想的新算法，它的出發(fā)點(diǎn)仍然是“分而治之”的原理，符合此原理的區(qū)域、算子、系統(tǒng)的分裂方法和技術(shù)是設(shè)計(jì)和實(shí)現(xiàn)并行處理的重要手段。 此外，異步數(shù)值算法基本上是混亂迭代法，是并行算法最富有特色的組成部分之一。第75頁/共76頁感謝您的觀看！第76頁/共76頁