北工大數(shù)值分析課件

1、數(shù)值分析 Numerical Analysis董君良董君良北京工業(yè)大學北京工業(yè)大學 / 理學院理學院計 算 方 法話說數(shù)學話說數(shù)學 數(shù)學是什么數(shù)學是什么？1 1. 數(shù)學是關(guān)于數(shù)和形的學問數(shù)學是關(guān)于數(shù)和形的學問 l 數(shù)數(shù) 代數(shù)代數(shù)：數(shù)量關(guān)系的科學：數(shù)量關(guān)系的科學, 有序思有序思 維占主導維占主導, 培養(yǎng)邏輯推理能力；培養(yǎng)邏輯推理能力； l形形 幾何幾何：空間形式的科學：空間形式的科學, 空間想空間想 象、形象思維占主導象、形象思維占主導, 培養(yǎng)直覺培養(yǎng)直覺 能力和洞察力能力和洞察力.數(shù)學是一門研究現(xiàn)實世界中數(shù)量關(guān)系和空間數(shù)學是一門研究現(xiàn)實世界中數(shù)量關(guān)系和空間形式的科學形式的科學 -恩格斯恩格斯數(shù)

2、學的三大核心領(lǐng)域數(shù)學的三大核心領(lǐng)域 分析分析 (Mathematical Analysis)代數(shù)代數(shù) (Algebra)幾何幾何 (Geometry)2. 數(shù)學科學按內(nèi)容可分成五大學科數(shù)學科學按內(nèi)容可分成五大學科 應用數(shù)學應用數(shù)學 (Applied mathematics)著限于說明自然現(xiàn)象，解決實際問題，是純粹數(shù)學與科學技術(shù)之間的橋梁 純粹數(shù)學純粹數(shù)學 (Pure mathematics)專門研究數(shù)學本身的內(nèi)部規(guī)律 撇開具體內(nèi)容，以純粹形式研究 計算數(shù)學計算數(shù)學 (Computation mathematics)運籌與控制運籌與控制 (Operation & control)概率論與

3、數(shù)理統(tǒng)計概率論與數(shù)理統(tǒng)計 ( Probability & mathematical statistics)數(shù)值分析是計算數(shù)學的一個主要部分數(shù)值分析是計算數(shù)學的一個主要部分, , 它研究用它研究用計算機計算機求求解各種數(shù)學問題的數(shù)值計算解各種數(shù)學問題的數(shù)值計算方法方法及其及其理論理論與軟件與軟件實現(xiàn)實現(xiàn). . 從單變量到多變量從單變量到多變量, 從低維到高維從低維到高維; 從線性到非線性從線性到非線性; 從局部到整體從局部到整體, 從簡單到復雜從簡單到復雜; 從連續(xù)到間斷從連續(xù)到間斷, 從穩(wěn)定到分岔從穩(wěn)定到分岔; 從精確到隨機、到模糊從精確到隨機、到模糊; 計算機的使用計算機的使用. 首

4、先是表現(xiàn)在現(xiàn)代數(shù)學的新領(lǐng)域和高層次中，首先是表現(xiàn)在現(xiàn)代數(shù)學的新領(lǐng)域和高層次中，其次是數(shù)學向一切學科與社會部門的滲透和應用。其次是數(shù)學向一切學科與社會部門的滲透和應用?，F(xiàn)代數(shù)學發(fā)展的新趨向現(xiàn)代數(shù)學發(fā)展的新趨向計算機的應用計算機的應用例子例子 求求1 2 35000? function mysum=mysum(n)mysum=0For i=1:1:n mysum=mysum+i;endmysum如果線性方程組如果線性方程組)1(22112222212111212111 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa的系數(shù)行列式不等于零，即的系數(shù)行列式不等于零，即nnnnnnaaaa

5、aaaaaD212222111211 0 ，123123,nnDDDDxxxxDDDD， (2)那么線性方程組那么線性方程組 有解，并且解是唯一的，可有解，并且解是唯一的，可以表示為：以表示為： 1111,11,111,11,1njjnjnn jn jnnaaaaDaaaabb又令q 例：求解一個例：求解一個 n 階線性方程組，如果使用克萊姆法則，階線性方程組，如果使用克萊姆法則，需要計算需要計算 n+1 個個 n 階行列式，在不計加減運算情況下，至階行列式，在不計加減運算情況下，至少需要少需要 n!(n2-1) 次乘除運算。當次乘除運算。當 n=20 時，時，用每秒運算用每秒運算30億次（億

6、次（P4 3.0G）的計算機求解時，大約需的計算機求解時，大約需要要10000年的時間。年的時間。202109.7 1)-(2020!而如果使用高斯（而如果使用高斯（Gauss）消元法，消元法，高斯消去法總的乘除運算量為高斯消去法總的乘除運算量為：3233nnn 大約需要大約需要3060次乘除運算，不到一秒鐘就能完成。次乘除運算，不到一秒鐘就能完成?？茖W計算科學計算q 科學計算科學計算 Scientific Computing (計算科學計算科學 Computational Science)l 使用數(shù)學、統(tǒng)計與計算器的技術(shù)，借助計算機高速計算的使用數(shù)學、統(tǒng)計與計算器的技術(shù)，借助計算機高速計算的

7、能力，來解決現(xiàn)代科學、工程、經(jīng)濟或人文中的復雜問題能力，來解決現(xiàn)代科學、工程、經(jīng)濟或人文中的復雜問題 狹義的科學計算是針對某些特定的數(shù)學問題，設計有效的計算狹義的科學計算是針對某些特定的數(shù)學問題，設計有效的計算方法來求解，即為方法來求解，即為數(shù)值計算數(shù)值計算/數(shù)值分析數(shù)值分析/計算方法計算方法/ /計算數(shù)學計算數(shù)學u 科學計算是一門工具性、方法性、整合性的新學科，是各科學計算是一門工具性、方法性、整合性的新學科，是各種科學與工程計算領(lǐng)域（如：氣象、地震、核能技術(shù)、石油種科學與工程計算領(lǐng)域（如：氣象、地震、核能技術(shù)、石油探勘、航天工程、探勘、航天工程、 密碼解譯等）中不可缺少的工具密碼解譯等）中

8、不可缺少的工具計算數(shù)學計算數(shù)學是科學計算的是科學計算的核心核心與與基礎基礎u 科學計算已成為當今科學研究的三種基本手段之一，是數(shù)科學計算已成為當今科學研究的三種基本手段之一，是數(shù)學將觸角伸向其他學科的橋梁。學將觸角伸向其他學科的橋梁?？茖W計算科學計算u 隨著計算機的高速發(fā)展，數(shù)值計算方法已深入到各個科學隨著計算機的高速發(fā)展，數(shù)值計算方法已深入到各個科學研究領(lǐng)域，計算性交叉學科不斷涌現(xiàn)，如計算力學、計算物研究領(lǐng)域，計算性交叉學科不斷涌現(xiàn)，如計算力學、計算物理、計算化學、計算生物學、計算經(jīng)濟學等理、計算化學、計算生物學、計算經(jīng)濟學等 q 科學計算科學計算u 使用計算機進行科學計算、數(shù)據(jù)處理及分析已

9、成為人類科使用計算機進行科學計算、數(shù)據(jù)處理及分析已成為人類科技活動的主要方法之一。技活動的主要方法之一。熟練地使用計算機進行科學計算，熟練地使用計算機進行科學計算，已成為科技工作者的一項基本技能已成為科技工作者的一項基本技能 科學計算科學計算q 利用計算機解決實際問題通常分下面幾個過程：利用計算機解決實際問題通常分下面幾個過程：實際實際問題問題數(shù)學數(shù)學模型模型數(shù)值數(shù)值方法方法程序程序設計設計上機上機實現(xiàn)實現(xiàn)應用舉例應用舉例問：今有問：今有上禾三秉，中禾二秉，下禾一秉，實三十九斗；上禾三秉，中禾二秉，下禾一秉，實三十九斗；上禾二秉，中禾三秉，下禾一秉，實三十四斗；上禾二秉，中禾三秉，下禾一秉，實

10、三十四斗；上禾一秉，中禾二秉，下禾三秉，實二十六斗。上禾一秉，中禾二秉，下禾三秉，實二十六斗。問上、中、下禾實一秉各幾何？問上、中、下禾實一秉各幾何？ 九章算術(shù)九章算術(shù)3239xyz 2334xyz 2326xyz例：一個古老的數(shù)學問題例：一個古老的數(shù)學問題應用舉例應用舉例1112111212222211nnnnnnnnaaaxbaaaxbaaaxb 線性方程組數(shù)值求解線性方程組數(shù)值求解 教材第五、六章教材第五、六章Axb 應用舉例應用舉例例：人口預測例：人口預測表格中是我國表格中是我國1950年到年到2005年的人口數(shù)（見年的人口數(shù)（見中國統(tǒng)計年鑒），試預測未來的人口數(shù)中國統(tǒng)計年鑒），試預測

11、未來的人口數(shù)插值與曲線擬合插值與曲線擬合 教材第二、三章教材第二、三章年份年份人口人口(萬萬)1950551961955614651960662071965725381970829921975924201980987051985105851199011433199512112120001267432005130756應用舉例應用舉例例：例：鋁制波紋瓦的長度問題鋁制波紋瓦的長度問題建筑上用的一種鋁制波紋瓦是由機器將一塊平整的鋁板壓建筑上用的一種鋁制波紋瓦是由機器將一塊平整的鋁板壓制而成。假若要求波紋瓦長制而成。假若要求波紋瓦長 4 英尺，每個波紋的高度英尺，每個波紋的高度(從中從中心線心線)為為

12、 1 英寸，且每個波紋以近似英寸，且每個波紋以近似 2 英寸為一個周期。英寸為一個周期。求制做一塊波紋瓦所需鋁板的長度求制做一塊波紋瓦所需鋁板的長度 L。應用舉例應用舉例這個問題就是要求由函數(shù)這個問題就是要求由函數(shù) f(x)=sin x給定的曲線從給定的曲線從 x=0 到到 x=48 英寸間的弧長英寸間的弧長 L，即，即:數(shù)值積分與數(shù)值微分數(shù)值積分與數(shù)值微分 教材第四章教材第四章484822001( ) d1(cos ) dLfxxxx 上述積分為第二類橢圓積分，無法用普通方法來計算上述積分為第二類橢圓積分，無法用普通方法來計算應用舉例應用舉例矩陣特征值計算矩陣特征值計算 教材第八章教材第八章

13、例：例：Google 搜索引擎搜索引擎1998 年創(chuàng)立，目前市值近年創(chuàng)立，目前市值近2000億億G: Google Matrix, “the worlds largest matrix computation” x: PageRank vector “The $25,000,000,000 Eigenvector” SIAM Review，2006Gx = x, eTx =1 n搜索引擎：給定關(guān)鍵詞，如何從幾十萬、幾百搜索引擎：給定關(guān)鍵詞，如何從幾十萬、幾百萬的海量網(wǎng)頁中找出最有用的信息萬的海量網(wǎng)頁中找出最有用的信息n解決思路解決思路n網(wǎng)頁索引網(wǎng)頁索引n確定網(wǎng)頁和查詢的關(guān)系確定網(wǎng)頁和查詢的關(guān)系

14、n分類分類線性代數(shù)在線性代數(shù)在Google中的應用中的應用Http網(wǎng)頁鏈接示意圖 n基本原理基本原理“從優(yōu)質(zhì)的網(wǎng)頁鏈接過來的網(wǎng)頁必定從優(yōu)質(zhì)的網(wǎng)頁鏈接過來的網(wǎng)頁必定還是優(yōu)質(zhì)網(wǎng)頁還是優(yōu)質(zhì)網(wǎng)頁”n超鏈接超鏈接AB A 對對B 投一票投一票n若若A的質(zhì)量高（如的質(zhì)量高（如QQ），則該投票分數(shù)高），則該投票分數(shù)高PageRank（衡量網(wǎng)頁質(zhì)量） PageRank示意圖網(wǎng)網(wǎng)頁頁鏈鏈接接矩矩陣陣by “網(wǎng)絡爬蟲”向外的鏈接數(shù)目表示從網(wǎng)頁的超鏈接不存在指向網(wǎng)頁網(wǎng)頁的超鏈接指向網(wǎng)頁存在從網(wǎng)頁iiNjijiiNaaAjijinm)( 0 )(/1)(,Google矩陣矩陣n問題：已知問題：已知Google矩陣（網(wǎng)

15、頁鄰接矩陣），如矩陣（網(wǎng)頁鄰接矩陣），如何求出何求出PageRank?n首先，首先，PageRank可以表示為向量可以表示為向量nR=R1,R2,RnPageRank（衡量網(wǎng)頁質(zhì)量） nPageRank是是Google矩陣的主特征向量矩陣的主特征向量nGoogle矩陣矩陣An記記A=AT（關(guān)注被鏈接）（關(guān)注被鏈接）nA（注意每列為和（注意每列為和1向量）向量）PageRank是主特征向量n由于網(wǎng)頁矩陣規(guī)模巨大（數(shù)量級約為由于網(wǎng)頁矩陣規(guī)模巨大（數(shù)量級約為240 240 ），無），無法采用常規(guī)矩陣運算，因此通常采用迭代的方法求解法采用常規(guī)矩陣運算，因此通常采用迭代的方法求解n令令 x= PageR

16、ank，則，則n求解求解 x=Ax nA的最大特征值為的最大特征值為1(主特征值主特征值)nx是主特征值是主特征值1對應的特征向量對應的特征向量計算方法的任務計算方法的任務q 計算方法計算方法/數(shù)值分析的任務數(shù)值分析的任務u 設計求解各種實際問題的設計求解各種實際問題的高效可靠高效可靠的的數(shù)值方法數(shù)值方法l 有效：易于在計算機上實現(xiàn)有效：易于在計算機上實現(xiàn) 運算只包括加、減、乘、除以及邏輯運算運算只包括加、減、乘、除以及邏輯運算l 可靠：收斂性穩(wěn)定性等有理論保證可靠：收斂性穩(wěn)定性等有理論保證l 高效：盡可能地節(jié)省計算時間和存儲空間高效：盡可能地節(jié)省計算時間和存儲空間 即計算復雜性好即計算復雜性

17、好對于同一問題，不同的算法在計算性能上可對于同一問題，不同的算法在計算性能上可能相差百萬倍或者更多！能相差百萬倍或者更多！u 對求得的對求得的數(shù)值數(shù)值解的精度進行評估解的精度進行評估u 研究數(shù)值算法研究數(shù)值算法在計算機上在計算機上的的實現(xiàn)實現(xiàn)計算方法計算方法例：例：求解一個求解一個 n 階線性方程組，如果使用階線性方程組，如果使用克萊姆法則克萊姆法則，需，需要計算要計算 n+1 個個 n 階行列式，在不計加減運算情況下，至少階行列式，在不計加減運算情況下，至少需要需要 n!(n2-1) 次乘除運算。而使用高斯消去法，只需約次乘除運算。而使用高斯消去法，只需約2n3/3 次乘除運算次乘除運算用每

18、秒運算用每秒運算 30 億次（主頻億次（主頻3.0G）的計算機求解時，大的計算機求解時，大約需要約需要10000年的時間年的時間 22020!(201) 9.710 l 當當 n=20 時，時，如果使用高斯消去法，不到一秒鐘就能完成如果使用高斯消去法，不到一秒鐘就能完成 數(shù)值方法特點數(shù)值方法特點q 數(shù)值分析就是研究數(shù)值問題的算法，其特點數(shù)值分析就是研究數(shù)值問題的算法，其特點u 方法是近似的方法是近似的，所以求出的解是有誤差的，所以求出的解是有誤差的u 與計算機緊密結(jié)合：上機實現(xiàn)與計算機緊密結(jié)合：上機實現(xiàn)l 掌握一門語言：掌握一門語言：C 語言或語言或 Fortran 語言語言l 熟悉一種數(shù)學軟

19、件：熟悉一種數(shù)學軟件：Matlab，Maple 或或 Mathematicau 有可靠的理論分析，有可靠的理論分析，u 有好的計算復雜性有好的計算復雜性u 數(shù)值試驗數(shù)值試驗基本概念基本概念l 解析解、精確解、真解、真值：解析解、精確解、真解、真值：是一種包含分式、三角函是一種包含分式、三角函數(shù)、指數(shù)、對數(shù)甚至無限級數(shù)等數(shù)、指數(shù)、對數(shù)甚至無限級數(shù)等 基本函數(shù)的解的形式基本函數(shù)的解的形式 l 數(shù)值解、近似解：數(shù)值解、近似解：利用數(shù)值分析的方式來求得利用數(shù)值分析的方式來求得 l 數(shù)值算法：求問題的數(shù)值算法：求問題的數(shù)值解數(shù)值解的方法的方法u 算法的可靠性包括：算法的可靠性包括：收斂性收斂性，穩(wěn)定性穩(wěn)

20、定性，誤差估計誤差估計等等u 算法的評價（優(yōu)劣）算法的評價（優(yōu)劣）l 時間時間復雜度（計算機運行時間）復雜度（計算機運行時間）l 空間空間復雜度（所占用的計算機存儲空間）復雜度（所占用的計算機存儲空間）l 邏輯邏輯復雜度（影響程序開發(fā)的周期以及維護的難易程度）復雜度（影響程序開發(fā)的周期以及維護的難易程度）好的算法有可靠的理論分析以及計算復雜性的算法好的算法有可靠的理論分析以及計算復雜性的算法課程信息課程信息數(shù)值分析數(shù)值分析（第五版）（第五版）q 教材教材 ：李慶揚等編著，清華大學出版社，李慶揚等編著，清華大學出版社，2002008 8數(shù)值分析數(shù)值分析全程導學及習題全解（第全程導學及習題全解（第5 5版）版）q 教材配套輔導書教材配套輔導書 ：清華大學出版社，清華大學出版社，20201010參考資料參考資料l 第三種科學方法：計算機時代的科學計算第三種科學方法：計算機時代的科學計算 石鐘慈著，石鐘慈著，清華大學出版社，院士科普書系清華大學出版社，院士科普書系，2000l 科學計算導論科學計算導論（第（第 2 版）（英文影印版）版）（英文影印版） M.T.