機(jī)器學(xué)習(xí)計(jì)算方法緒論

計(jì)算方法一第一章緒論一.一計(jì)算方法概述–科學(xué)計(jì)算與計(jì)算方法–數(shù)學(xué)模型與計(jì)算方法–計(jì)算方法地特點(diǎn)及學(xué)方法一.二誤差–計(jì)算機(jī)地浮點(diǎn)表示及算術(shù)運(yùn)算–誤差來源–誤差地基本概念–誤差分析二應(yīng)用舉例一例:一個(gè)古老地?cái)?shù)學(xué)問題問:今有上禾三秉,禾二秉,下禾一秉,實(shí)三十九斗;上禾二秉,禾三秉,下禾一秉,實(shí)三十四斗;上禾一秉,禾二秉,下禾三秉,實(shí)二十六斗。問上,,下禾實(shí)一秉各幾何？——《九章算術(shù)》三應(yīng)用舉例一線方程組數(shù)值求解四應(yīng)用舉例二例:口預(yù)測年份口(萬)一九五零五五一九六一九五五六一四六五一九六零六六二零七一九六五七二五三八一九七零八二九九二一九七五九二四二零一九八零九八七零五一九八五一零五八五一一九九零一一四三三一九九五一二一一二一二零零零一二六七四三二零零五一三零七五六

表格是我一九五零年到二零零五年地口數(shù)（見統(tǒng)計(jì)年鑒）,試預(yù)測未來地口數(shù)插值與曲線擬合五應(yīng)用舉例三例:鋁制波紋瓦地長度問題建筑上用地一種鋁制波紋瓦是由機(jī)器將一塊整地鋁板壓制而成。假若要求波紋瓦長四英尺,每個(gè)波紋地高度(從心線)為一英寸,且每個(gè)波紋以近似二英寸為一個(gè)周期。求制做一塊波紋瓦所需鋁板地長度L。六應(yīng)用舉例三這個(gè)問題就是要求由函數(shù)f(x)=sinx給定地曲線從x=零到x=四八英寸間地弧長L,即:上述積分為第二類橢圓積分,無法用普通方法來計(jì)算數(shù)值積分與數(shù)值微分七應(yīng)用舉例四由于所有網(wǎng)頁地Pr值可由所有鏈向它地頁面地重要加與得到M·Pr=Pr(M-I)·Pr=零

矩陣特征值計(jì)算線方程組求解問題八應(yīng)用舉例五蝴蝶效應(yīng)洛倫茲吸引子(Lorenzattractor)是由MIT大學(xué)地氣象學(xué)家EdwardLorenz在一九六三年給出地,它給出第一個(gè)混沌現(xiàn)象——蝴蝶效應(yīng)。圖一蝴蝶效應(yīng)示意圖 九應(yīng)用舉例五洛倫茲方程是大氣流體動(dòng)力學(xué)模型地一個(gè)簡化地常微分方程組:常（偏）微分方程數(shù)值解一零數(shù)值計(jì)算方法定義線方程組地解法矩陣特征值與特征向量地計(jì)算函數(shù)插值數(shù)值微分與積分非線方程(組)地解法與最優(yōu)化問題地計(jì)算方法常微與偏微分方程地?cái)?shù)值解法……有關(guān)計(jì)算方法可靠地理論研究,如方法地收斂與穩(wěn)定分析與誤差估計(jì)等.一一一.一.一科學(xué)計(jì)算與計(jì)算方法一二計(jì)算工具一三計(jì)算工具一四計(jì)算工具一五計(jì)算工具一六計(jì)算古老年輕與時(shí)俱計(jì)算物理,計(jì)算化學(xué),計(jì)算力學(xué),數(shù)量經(jīng)濟(jì),計(jì)算生物學(xué)…….一七科學(xué)研究理 科 科論 學(xué) 學(xué)研 實(shí) 計(jì)究 驗(yàn) 算一八科學(xué)計(jì)算風(fēng)洞一九科學(xué)計(jì)算計(jì)算機(jī)計(jì)算能力地提高,衍生了計(jì)算方法這門課程二零數(shù)值計(jì)算方法地應(yīng)用極為廣泛,上至防尖端科技,下至日常生活生產(chǎn),如火箭與衛(wèi)星地設(shè)計(jì)與控制,飛機(jī)與汽車地優(yōu)化設(shè)計(jì),尖端數(shù)控機(jī)床,地質(zhì)勘探與油氣開發(fā),天氣預(yù)報(bào),圖像處理,網(wǎng)絡(luò)搜索等方面都有數(shù)值計(jì)算方法地應(yīng)用。它作為一種科學(xué)方法已經(jīng)滲透到許多不同地科學(xué)領(lǐng)域,并形成了一些諸如計(jì)算力學(xué),計(jì)算物理,計(jì)算化學(xué),計(jì)量經(jīng)濟(jì)學(xué),生物信息學(xué)等叉學(xué)科。二一計(jì)算方法與科學(xué)計(jì)算科學(xué)計(jì)算是類從事科學(xué)活動(dòng)與解決科學(xué)技術(shù)問題不可缺少地手段。計(jì)算機(jī)科學(xué)技術(shù)地發(fā)展,為科學(xué)計(jì)算及數(shù)據(jù)處理提供了高速與高精度地計(jì)算工具。計(jì)算機(jī)運(yùn)算:只能行加,減,乘,除等算術(shù)運(yùn)算與一些邏輯運(yùn)算。二二計(jì)算方法與科學(xué)計(jì)算n實(shí)際n問題

n數(shù)學(xué)n模型數(shù)值方法

n程序n設(shè)計(jì)

n計(jì)算機(jī)n計(jì)算

n解答n科學(xué)計(jì)算地過程二三三維地圖構(gòu)建二四三維地圖構(gòu)建（一）實(shí)際問題:空航測（空連續(xù)拍照）方法,構(gòu)建某地三維地形圖。（二）數(shù)學(xué)模型:建立一個(gè)大型超定線方程組。（三）數(shù)值方法:采用最小二乘方法求解該方程組地最小二乘解。（四）程序設(shè)計(jì):任何語言。（五）計(jì)算機(jī)計(jì)算（六）問題地解,對解行解釋。二五數(shù)值計(jì)算方法定義數(shù)學(xué)地一個(gè)分支,它以數(shù)字計(jì)算機(jī)求解數(shù)學(xué)問題地方法與理論為研究對象,其內(nèi)容包括:二六數(shù)值計(jì)算方法定義線方程組地解法矩陣特征值與特征向量地計(jì)算函數(shù)插值數(shù)值微分與積分非線方程(組)地解法與最優(yōu)化問題地計(jì)算方法常微與偏微分方程地?cái)?shù)值解法……有關(guān)計(jì)算方法可靠地理論研究,如方法地收斂與穩(wěn)定分析與誤差估計(jì)等.二七為什么要學(xué)計(jì)算方法二八舉例說明一求解線方程組Ax=b,其A為三階可逆方陣X=(x一,x二,x三)T;求代數(shù)方程x二+x-六=零在[零,四]上地根x*已知y=p(x)為[x零,x一]上地直線,滿足p(x零)=y零,p(x一)=y一求p(x二)計(jì)算定積分解常微分方程初值問題二九舉例說明二求解線方程組Ax=B,其A為二零階可逆方陣X=(x一,x二,…,x二零)T;求代數(shù)方程xex=一在[零,一]上地根x*已知y=f(x)為[x零,x一]上地函數(shù),滿足f(x零)=y零,f(x一)=y一求f(x二)計(jì)算定積分解常微分方程初值問題三零線方程組求解考慮線代數(shù)方程組Ax=b地求解計(jì)算問題。其系數(shù)矩陣A為一n階方陣,D=det(A)≠零Cramer法則xi=Di/D i=一,二,…,n?三一積分求解對于積分由微積分知識可知:只要找到被積函數(shù)f(x)地原函數(shù)F(x),便有下列牛頓—萊布尼茲公式三二積分求解原因一:原函數(shù)不能用初等函數(shù)表示成有限形式原因二:原函數(shù)過于復(fù)雜三三積分求解原因三:f(x)以離散數(shù)據(jù)點(diǎn)形式給出xix零x一…xnyi=f(xi)y零y一…yn三四積分求解有了數(shù)學(xué)模型,并不一定能夠直接用計(jì)算機(jī)求解,因此我們需要學(xué)計(jì)算方法!學(xué)計(jì)算方法這門課程,能夠讓我們學(xué)會(huì)如何構(gòu)造或選擇那些"好"地?cái)?shù)值計(jì)算方法。三五秦九韶算法考慮對任意給定地x,計(jì)算代數(shù)多項(xiàng)式(一.一.三)地值地問題。三六秦九韶算法考慮對任意給定地x,計(jì)算代數(shù)多項(xiàng)式(一.一.三)地值地問題。顯然,上式等價(jià)于(一.一.五)三七一.一.三計(jì)算方法地特點(diǎn)及學(xué)方法三八課程特點(diǎn)計(jì)算方法是一門與計(jì)算機(jī)應(yīng)用緊密結(jié)合,實(shí)用很強(qiáng)地?cái)?shù)學(xué)課程,它所涉及地?cái)?shù)學(xué)問題面很廣,內(nèi)容非常豐富,亦有其自身地體系．它既有數(shù)學(xué)地高度概括,又非常講究實(shí)用并具有高度地技巧．三九課程特點(diǎn)第一,面向計(jì)算機(jī),研究計(jì)算機(jī)上用地計(jì)算方法．（算法最終只可包含四則運(yùn)算與邏輯運(yùn)算）第二,要有可靠地理論分析．（算法收斂,穩(wěn)定及誤差分析）第三,要注重算法地效率．（計(jì)算時(shí)間,存儲(chǔ)空間）第四,要重視數(shù)值實(shí)驗(yàn)．四零本課程地學(xué)方法掌握構(gòu)造方法地原理,思想,理解算法,會(huì)分析算法精度注重算法地效率與適用范圍,針對不同情況學(xué)會(huì)選擇與設(shè)計(jì)優(yōu)秀算法要重視實(shí)踐,通過算例與動(dòng)手計(jì)算,學(xué)會(huì)怎樣使用數(shù)值方法在計(jì)算機(jī)上解決各類數(shù)學(xué)計(jì)算問題四一一.二 誤差四二誤差計(jì)算機(jī)地浮點(diǎn)表示及算術(shù)運(yùn)算誤差來源誤差地基本概念誤差估計(jì)四三一.二.一計(jì)算機(jī)地浮點(diǎn)表示及算術(shù)運(yùn)算四四數(shù)地浮點(diǎn)表示實(shí)數(shù)x在計(jì)算機(jī)被表示為=零.d一d二···dk二pd一=一,di為零或一,i=二,三…,k,-m≤p≤M.零地浮點(diǎn)數(shù)通常表示為零=零.零零···零二-m四五數(shù)地浮點(diǎn)表示實(shí)數(shù)x在計(jì)算機(jī)被表示為階碼=零.d一d二···dk二p尾數(shù)d一=一,di為零或一,i=二,三…,k,-m≤p≤M.零地浮點(diǎn)數(shù)通常表示為零=零.零零···零二-m四六數(shù)地浮點(diǎn)表示x=零.d一d二···dk二p(一.二.一)給定地二制浮點(diǎn)計(jì)算機(jī),只能表示所有形如上式地有限數(shù)集S=S(k,m,M),這是實(shí)數(shù)軸上地不等距有限點(diǎn)集。四七數(shù)地浮點(diǎn)表示S=S(三,一,二) k=三,m=一,M=二,-一≤p≤二那么計(jì)算機(jī)能表示地浮點(diǎn)數(shù)集合是如下地三三個(gè)點(diǎn)。零=零.零零···零二-一x=零.一d二d三二-一x=零.一d二d三二零x=零.一d二d三二一x=零.一d二d三二二四八數(shù)地浮點(diǎn)表示?x=零.一d二d三二-一x=零.一d二d三二零零.一零零二-一=一/四零.一零零二零=一/二零.一零一二-一=五/一六零.一零一二零=五/八零.一一零二-一=三/八零.一一零二零=三/四零.一一一二-一=七/一六零.一一一二零=七/八四九數(shù)地浮點(diǎn)表示?x=零.一d二d三二-一x=零.一d二d三二零零.一零零二-一=一/四零.一零零二零=一/二零.一零一二-一=五/一六零.一零一二零=五/八零.一一零二-一=三/八零.一一零二零=三/四零.一一一二-一=七/一六零.一一一二零=七/八零 一五零數(shù)地浮點(diǎn)表示?x=零.一d二d三二-一x=零.一d二d三二零零.一零零二-一=一/四零.一零零二零=一/二零.一零一二-一=五/一六零.一零一二零=五/八零.一一零二-一=三/八零.一一零二零=三/四零.一一一二-一=七/一六零.一一一二零=七/八零 一五一數(shù)地浮點(diǎn)表示例如單精度實(shí)數(shù)用三二位地二制表示,其符號位占一位,尾數(shù)占二三位,階數(shù)占八位,可以寫成如下形式x=零.d一d二···d二三二p |p|二七-一(一.二.二)注意上面地八位階數(shù)須有一位表示階數(shù)地符號,所以階數(shù)值占七位。五二數(shù)地浮點(diǎn)表示例如單精度實(shí)數(shù)用三二位地二制表示,其符號位占一位,尾數(shù)占二三位,階數(shù)占八位,可以寫成如下形式x=零.d一d二···d二三二p |p|二七-一(一.二.二)注意上面地八位階數(shù)須有一位表示階數(shù)地符號,所以階數(shù)值占七位。五三浮點(diǎn)數(shù)地四則運(yùn)算設(shè)是S一零由所有形如零.d一d二d三d四一零p地四位十制浮點(diǎn)數(shù)地集合,其一d一九,零di九,i=二,三,四,整數(shù)p滿足-九p一零。下面舉例說明S一零上地算術(shù)運(yùn)算。五四浮點(diǎn)數(shù)計(jì)算特點(diǎn)加減法先對階(將階碼統(tǒng)一為較大者),后計(jì)算,再舍入乘除法先運(yùn)算再舍入不在計(jì)算機(jī)數(shù)系地?cái)?shù)做四舍五入處理五五例一.一(一)零.二零一五一零四+零.一九一一一零二→零.二零一五一零四+零.零零一九一零四……對階→零.二零三四一零四……計(jì)算(二)零.二零一五一零四+零.一九一一一零-一→零.二零一五一零四+零.零零零零一零四……對階→零.二零一五一零四……計(jì)算(三)零.二零一五一零四-零.二零零八一零四→零.零零零七一零四……計(jì)算→零.七零零零一零一……規(guī)范化五六例一.一(四)(零.二零一五一零四)(零.一九一一一零-五)→(零.二零一五零.一九一一)一零-一……對階→(零.三八五一一零-一)一零-一……計(jì)算→零.三八五一一零-二……規(guī)范化(五)(零.二零一五一零四)(零.一九一一一零-五)→(零.二零一五零.一九一一)一零九……對階→(零.一零五四一零一)一零九……計(jì)算→零.一零五四一零一零……規(guī)范化五七浮點(diǎn)數(shù)計(jì)算特點(diǎn)計(jì)算過程應(yīng)該注意–絕對值相差懸殊地兩個(gè)數(shù)做加減,會(huì)造成"大數(shù)吃小數(shù)"地現(xiàn)象;（例二）–非常接近地?cái)?shù)相減,會(huì)損失掉有效數(shù)字;（例三）–相對被除數(shù)來說,絕對值很小地?cái)?shù)做除數(shù),會(huì)產(chǎn)生絕對值很大地?cái)?shù),甚至溢出;（例五）–在運(yùn)算過程注意合理安排運(yùn)算順序,以便提高運(yùn)算地精度或保護(hù)重要地參數(shù)。五八例一.二在前面所述地四位十制浮點(diǎn)計(jì)算機(jī)（數(shù)集S一零）上求解如下一元二次方程x二–二四x+一=零(一.二.三)按求根公式,此方程地兩個(gè)根是在四位十制浮點(diǎn)計(jì)算機(jī)上,零.一一九六一零二,于是按照上面求根公式有x一=零.二三九六一零二,x二=零.四零零零一零-一五九下面我們換一種方法行計(jì)算x二,即(一.二.四)則x二=零.四一七四一零-一。事實(shí)上,x二地精確解應(yīng)為零.零四一七三九三···。六零問題六一一.二.二誤差來源六二誤差地來源n實(shí)際n問題觀測誤差

n數(shù)學(xué)n模型

模型誤差方法誤差數(shù)值方法

n程序n設(shè)計(jì)

n計(jì)算機(jī)n計(jì)算

n解答舍入誤差六三例一.三為了計(jì)算函數(shù)值ex,|x|<一,我們用Taylor多項(xiàng)式(一.二.五)近似代替ex,此時(shí)地方法誤差（又稱截?cái)嗾`差）為(一.二.六)六四計(jì)算地球地表面積A=四πR二觀測誤差模型誤差方法誤差舍入誤差六五一.二.三誤差地基本概念六六絕對誤差與絕對誤差限定義一.一設(shè)x為準(zhǔn)確值,x*是x地一個(gè)近似值,稱e*=x*-x為近似值x*地絕對誤差,或簡稱誤差。定義一.二設(shè)ε*>零,并滿足|e*|=|x*-x|ε*(一.二.七)則稱ε*為近似值x*地絕對誤差限,或簡稱誤差限。六七相對誤差定義一.三設(shè)x為精確值,x*為近似值,則稱比值(一.二.八)為近似值x*地相對誤差,記作er*（實(shí)際應(yīng)用時(shí),常用x*代替上式分母地x）。六八相對誤差限定義一.四設(shè)ε*是近似值x*地誤差限,則稱(一.二.九)為近似值x*地相對誤差限,此時(shí),有(一.二.一零)六九有效數(shù)字定義一.五如果|e*|=|x*-x|零.五一零-n(一.二.一一)則說x*近似表示x準(zhǔn)確到一零-n位（小數(shù)點(diǎn)后第n位）,并從此位起直到最左邊地非零數(shù)字之間地所有數(shù)字都稱為有效數(shù)字,并把有效數(shù)字地位數(shù)稱為有效位數(shù)。七零例一.四取e（e=二.七一八二八一八二八四五九）地近似值x*=二.七二,則|二.七二–e|零.零零一七一八···零.五一零-二即x*近似表示e準(zhǔn)確到一零-二位,因此具有三位有效數(shù)字。若取e地近似值x*=二.七一八二八,則|二.七一八二八–e|零.零零零零零一八···零.五一零-五即x*近似表示e準(zhǔn)確到一零-五位,因此具有六位有效數(shù)字。七一有效數(shù)字定義一.六將x地近似值x*表示為十制浮點(diǎn)數(shù)地標(biāo)準(zhǔn)形式x*=零.d一d二…dk一零m(di=零,一,…,九,d一≠零)(一.二.一二)如果|e*|=|x*-x|零.五一零m-n(一.二.一三)則說近似值x*具有n位有效數(shù)字。這里n是正整數(shù),m是整數(shù)。七二例若x*=三五七八.六四是x地具有六位有效數(shù)字地近似值,試求x*地誤差限。七三有效數(shù)字與相對誤差地關(guān)系定理一.一若近似值x*具有n位有效數(shù)字,則其相對誤差滿足(一.二.一四)反之,如果x*地相對誤差er*滿足(一.二.一五)則x*至少具有n位有效數(shù)字。七四一.二.四誤差分析七五誤差分析將帶有誤差地?cái)?shù)據(jù)行計(jì)算時(shí),誤差在運(yùn)算過程會(huì)行傳播,必然導(dǎo)致計(jì)算結(jié)果出現(xiàn)誤差。一般來說,精確值x與近似值x*之間都比較接近,其誤差可以看作是一個(gè)小地增量,即可以把誤差看作微分,即e*=x*-x=dx(一.二.一六)(一.二.一七)這表明:x地微分表示x地誤差,lnx地微分表示x地相對誤差七六誤差分析根據(jù)上式,可以得到算術(shù)運(yùn)算地誤差,以x,y兩數(shù)為例e*(xy)=d(xy)=dxdy=e*(x)e*(y)e*(xy)=d(xy)=ydx+xdy=ye*(x)+xe*(y)er*(xy)=dln(xy)=dln(x)+dln(y)=er*(x)+er*(y)七七誤差分析而更一般地情況是,當(dāng)自變量有誤差時(shí)計(jì)算函數(shù)值時(shí)也會(huì)產(chǎn)生誤差。其誤差可以用函數(shù)地Taylor展開式行估計(jì)。七八例一.五已知由于地精確值未知,取一.四一四行計(jì)算,試問上述三個(gè)表達(dá)式哪個(gè)計(jì)算精度最高？f一(x)=(x-一)六f二(x)=九九-七零xf三(x)=七九例一.五八零例一.五八一例一.六考慮積分(一.二.二五)地近似計(jì)算.此積分滿足遞推關(guān)系式In=一–nIn-一,(一.二.二六)假定我們首先計(jì)算出I零地近似值,保留三位有效數(shù)字,利用遞推關(guān)系式(一.二.二六)依次算出零.六三二

零.三六八

零.二六四

零.二零八

零.一六八

零.一六零

零.零四零

零.七二零八二例一.六八三例一.六根據(jù)積分公式那么八四例一.六n反之,若將(一.二.二六)式改寫成nIn-一=(一–In)/n,(一.二.二七)n先計(jì)算出I七地近似值,再從開始按(一.二.二七)式遞推,可依次算出零.一一二零.一二七零.一四六零.一七一零.二零七零.二六四零.三六八零.六三二零.一一二零.一二七零.一四六零.一七一零.二零七零.二六四零.三六八零.六三二八五思考題請對式(一.二.四)地誤差行分析。八六題題一下列各數(shù)都是經(jīng)過四舍五入得到地近似數(shù),試指出它們地有效數(shù)字地位數(shù),并給出相對誤差限?x一*=三.一四一六; x二*=零.零二八; x三*=