1、數值分析數值分析 Numerical Analysis 謝謝 波波 X X 華南理工大學理學院華南理工大學理學院教材教材n應用數值分析應用數值分析 鄭咸義等鄭咸義等 編著編著 （華南理工大學出版社）（華南理工大學出版社）參考書目參考書目 Numerical Analysis:Mathematics of Scientific Computing (Third Edition) David Kincaid & Ward Cheney（機械工業出版社（機械工業出版社) Numerical Analysis (Seventh Edition) Richard L. Burden &

2、J. Douglas Faires （高等教育出版社）（高等教育出版社）科學計算科學計算 Scientific Computingl 現代許多科學、工程、經濟或人文中的復雜問題現代許多科學、工程、經濟或人文中的復雜問題. .需要使用數學、統計與計算器的技術，借助計算機高需要使用數學、統計與計算器的技術，借助計算機高速計算的能力來解決。速計算的能力來解決。u 科學計算是一門工具性、方法性、整合性的新學科，科學計算是一門工具性、方法性、整合性的新學科，是各種科學與工程計算領域（如：氣象、地震、核能是各種科學與工程計算領域（如：氣象、地震、核能技術、石油探勘、航天工程、技術、石油探勘、航天工程、 密

3、碼解譯等）中不可密碼解譯等）中不可缺少的工具。缺少的工具。數學模型數學模型構造算法構造算法編制程序編制程序上機運行上機運行輸出結果輸出結果實際問題實際問題數學化數學化離散化離散化程序化程序化u 科學計算已成為當今科學研究的三種基本手段之科學計算已成為當今科學研究的三種基本手段之一，是數學將觸角伸向其他學科的橋梁。一，是數學將觸角伸向其他學科的橋梁。科學計算科學計算應用舉例應用舉例問：今有問：今有上禾三秉，中禾二秉，下禾一秉，實三十九斗；上禾三秉，中禾二秉，下禾一秉，實三十九斗；上禾二秉，中禾三秉，下禾一秉，實三十四斗；上禾二秉，中禾三秉，下禾一秉，實三十四斗；上禾一秉，中禾二秉，下禾三秉，實二

4、十六斗。上禾一秉，中禾二秉，下禾三秉，實二十六斗。問上、中、下禾實一秉各幾何？問上、中、下禾實一秉各幾何？ 九章算術九章算術3239xyz2334xyz2326xyz例：一個古老的數學問題例：一個古老的數學問題應用舉例應用舉例1112111212222211nnnnnnnnaaaxbaaaxbaaaxb 線性方程組數值求解線性方程組數值求解 教材第五、六章教材第五、六章Axb 應用舉例應用舉例例：人口預測例：人口預測表格中是我國表格中是我國19501950年到年到20052005年的人口數（見年的人口數（見中國統計年鑒），試預測未來的人口數中國統計年鑒），試預測未來的人口數插值與曲線擬合插值與

5、曲線擬合 教材第二、三章教材第二、三章年份年份人口人口(萬萬)1950551961955614651960662071965725381970829921975924201980987051985105851199011433199512112120001267432005130756應用舉例應用舉例矩陣特征值計算矩陣特征值計算 教材第八章教材第八章例：例：Google 搜索引擎搜索引擎1998 年創立，目前市值近年創立，目前市值近2000億億G: Google Matrix, “the worlds largest matrix computation” x: PageRank vector

6、 “The $25,000,000,000 Eigenvector” SIAM Review，2006Gx = x, eTx =1數值分析研究的對象數值分析研究的對象n 數值分析數值分析又叫數值計算方法、計算方法、數又叫數值計算方法、計算方法、數值方法等，其值方法等，其研究對象研究對象是各種數學問題的數值方是各種數學問題的數值方法的設計、分析及其有關的數學理論和具體實現法的設計、分析及其有關的數學理論和具體實現的一門學科，它是一個數學分支的一門學科，它是一個數學分支, , 是科學與工程是科學與工程計算（計算（科學計算科學計算）的理論支持）的理論支持。 n 數值分析是數學，計算機科學與其他學科數

7、值分析是數學，計算機科學與其他學科交叉的產物交叉的產物。數值分析的任務數值分析的任務u 設計求解各種實際問題的設計求解各種實際問題的高效可靠高效可靠的的數值算法數值算法l 有效：有效：易于在計算機上實現易于在計算機上實現l 可靠可靠：收斂性穩定性等有理論保證：收斂性穩定性等有理論保證l 高效高效：盡可能地節省計算時間和存儲空間：盡可能地節省計算時間和存儲空間u 對求得的結果進行理論分析對求得的結果進行理論分析u數值算法在計算機上的實現數值算法在計算機上的實現數值分析的特點數值分析的特點u 數值算法數值算法u 課程課程目的目的u 學習一些常用的數值方法，掌握數值方法學習一些常用的數值方法，掌握數

8、值方法的基本理論，為進一步研究和使用更復雜的的基本理論，為進一步研究和使用更復雜的數值算法奠定基礎數值算法奠定基礎u初步掌握一種科學計算軟件包的使用方法初步掌握一種科學計算軟件包的使用方法（如（如MatlabMatlab）。）。課程主要內容課程主要內容u 線性代數方程組數值求解的直接法；線性代數方程組數值求解的直接法；u 線性代數方程組數值求解的迭代法；線性代數方程組數值求解的迭代法； 數值代數數值代數u 非線性方程與方程組數值求解；非線性方程與方程組數值求解；u 代數插值法；代數插值法；u 曲線擬合與函數逼近；曲線擬合與函數逼近； 數值逼近數值逼近u 數值積分與數值微分；數值積分與數值微分；

9、u 常微分方程數值求解。常微分方程數值求解。 Matlab Matlab 簡介簡介所需知識所需知識l 微積分微積分l 高等代數、線性代數高等代數、線性代數l 常微分方程常微分方程l Matlab Matlab 編程編程第一章第一章 緒緒 論論主要內容：主要內容：u 一些概念；一些概念；u 數值計算中的誤差數值計算中的誤差u 數值算法設計的若干原則數值算法設計的若干原則；u 數值算法設計的常見思想方法數值算法設計的常見思想方法 數值分析中一些概念數值分析中一些概念 F 數值問題數值問題F 數值解數值解F 算法算法 數值問題、數值解數值問題、數值解 、算法、算法 由一組已知數據（輸入數據），求出一

10、組結果由一組已知數據（輸入數據），求出一組結果數據（輸出數據），使得這兩組數據之間滿足數據（輸出數據），使得這兩組數據之間滿足預先制定的某種關系的問題，稱為預先制定的某種關系的問題，稱為數值問題數值問題。 經過計算機的計算求出的解，或由數值計算公經過計算機的計算求出的解，或由數值計算公式得出的解稱為式得出的解稱為數值解數值解。一般數值解是近似值。一般數值解是近似值。由給定的已知量，經過有限次的四則運算及規由給定的已知量，經過有限次的四則運算及規定的運算順序，求出所關心的未知量的數值解，定的運算順序，求出所關心的未知量的數值解，這樣所構成的整個計算步驟，稱為這樣所構成的整個計算步驟，稱為數值算法

11、數值算法（簡稱（簡稱算法算法）。）。 數值計算中的誤差數值計算中的誤差q用計算機進行實際問題的數值計算時，用計算機進行實際問題的數值計算時，往往求得是問題的近似解，都存在往往求得是問題的近似解，都存在誤差誤差q誤差誤差是人們用來描述數值計算中近似解是人們用來描述數值計算中近似解的精確程度，是科學計算中的一個十分的精確程度，是科學計算中的一個十分重要的概念重要的概念誤差來源誤差來源 從實際問題轉化為數學問題，建立數學模型時，數學從實際問題轉化為數學問題，建立數學模型時，數學模型與實際問題之間出現的誤差稱為模型誤差。模型與實際問題之間出現的誤差稱為模型誤差。 數學模型中一些根據觀測得到的物理量，如

12、：電壓、溫數學模型中一些根據觀測得到的物理量，如：電壓、溫度、長度等，不可避免會帶來誤差，稱為觀測誤差度、長度等，不可避免會帶來誤差，稱為觀測誤差。q 模型誤差模型誤差( (描述誤差描述誤差) ) Modeling ErrorModeling Errorq 參數誤差參數誤差( (觀測誤差觀測誤差) ) Measurement ErrorMeasurement Error 計算機在實際計算時，必須在有限的時間內得到計算計算機在實際計算時，必須在有限的時間內得到計算結果，就需要選用適當的數值計算方法求解，由此產生的結果，就需要選用適當的數值計算方法求解，由此產生的誤差稱為截斷誤差或方法誤差。誤差稱

13、為截斷誤差或方法誤差。誤差來源誤差來源例如：例如：函數計算函數計算-計算計算 的近似值的近似值sin x357111sin3!5!7!xxxxxq 截斷誤差截斷誤差( (方法誤差方法誤差) ) Truncation ErrorTruncation Error)(! 51! 31sin553xSxxxx 產生了有限過程代替無限過程的誤差，產生了有限過程代替無限過程的誤差，即截斷誤差或方法誤差。即截斷誤差或方法誤差。截斷誤差是截斷誤差是：79511( )sin( )7!9!R xxSxxx 誤差來源誤差來源 n由于計算機的字長有限，參加運算的數據及其運算結果在由于計算機的字長有限，參加運算的數據及

14、其運算結果在計算機中存放會產生誤差。這種誤差叫計算機中存放會產生誤差。這種誤差叫舍入誤差舍入誤差或或計算誤計算誤差差。n例如例如 在尾數四位的浮點計算機上用在尾數四位的浮點計算機上用0.33330.3333表示表示產生的舍入誤差產生的舍入誤差 10.33330.0000333R q 舍入誤差舍入誤差( (計算誤差計算誤差) ) Roundoff ErrorRoundoff Error注注l 誤差是不可避免的，即要允許誤差，又要誤差是不可避免的，即要允許誤差，又要控制誤差。控制誤差。l 模型誤差模型誤差, , 觀測誤差不是數值分析討論觀測誤差不是數值分析討論的內容的內容, , 數值分析主要研究截

15、斷誤差數值分析主要研究截斷誤差, , 舍入舍入誤差在計算過程中傳播和對計算結果的影響誤差在計算過程中傳播和對計算結果的影響( (誤差分析誤差分析), ), 以提高計算的精度以提高計算的精度. .絕對誤差：絕對誤差：absolute error *()e xxx x x 精確值精確值x x* * 近似值近似值則稱則稱 為為 絕對誤差限絕對誤差限/ /誤差限誤差限l 若存在一個正數若存在一個正數 ，使得，使得工程上通常記為：工程上通常記為：x x = = x x* * |e| = |x* - x| l 絕對誤差絕對誤差 可能取正，也可能取負可能取正，也可能取負l 絕對誤差絕對誤差 越小越具有參考價

16、值越小越具有參考價值l 但但 絕對誤差絕對誤差 卻不能很好地表示近似值的精確程度卻不能很好地表示近似值的精確程度誤差的基本概念誤差的基本概念相對誤差相對誤差相對誤差：相對誤差：relative error x x* er = x l 若存在正數若存在正數 r r，使得，使得 | |e er r| | r r， 則稱則稱 r r為為相對誤差限相對誤差限l 由于真值難以求出，通常也使用下面的定義作為相對誤差由于真值難以求出，通常也使用下面的定義作為相對誤差x xx x* * e er r = = x x* * l 近似值的精確程度取決于近似值的精確程度取決于 相對誤差相對誤差 的大小的大小l 實際

17、計算中我們所能得到的是實際計算中我們所能得到的是 誤差限誤差限 或或 相對誤差限相對誤差限有效數字有效數字 若近似值若近似值 x x* * 的誤差限是某一位的半個單位，的誤差限是某一位的半個單位，且該位到且該位到 x x* * 的第一位非零數字共有的第一位非零數字共有 n n 位，則稱位，則稱 x x* * 有有 n n 位有效數字位有效數字 等價描述等價描述FF用科學計數法，記用科學計數法，記（其中（其中 ）,01 aknaa.ax10021*| 0 5 10k nxx.若若 ,則則x x* *至少有至少有n n 位有效數字位有效數字. .有效數字有效數字例：例： = = 3.1415926

18、5 3.14159265 ，近似值，近似值 x x1 1 = 3.1415= 3.1415，x x2 2 = 3.1416= 3.1416問：問：x x1 1, , x x2 2 分別有幾位有效數字？分別有幾位有效數字？例：例：寫出下列各數的具有寫出下列各數的具有 5 5 位有效數字的近似值位有效數字的近似值 187.9325187.9325，0.0378550.037855，8.0000338.000033187.93，0.037856，8.00004，5注：數字末尾的注：數字末尾的 0 不可以隨意添加或省略！不可以隨意添加或省略！注注n由準確數字通過由準確數字通過“四舍五入四舍五入”得到的

19、近似值都得到的近似值都為有效數字。為有效數字。n可以通過有效數字的位數來確定誤差限。可以通過有效數字的位數來確定誤差限。 例如：例如：若若 x x* *=3587.64=3587.64是是x x的具有六位有效數的具有六位有效數字的近似值，它的絕對誤差限是多少？字的近似值，它的絕對誤差限是多少？ 264*410211021)()6, 4( ,100.358764x*xxxenkn有效數字與相對誤差的關系（有效數字與相對誤差的關系（P4P4） - - n n 位有效數字的近似數位有效數字的近似數 x x * * 其相對誤差：其相對誤差：11(1)11002( )nrxaEa（最左一位），且 (1)

20、11( )11002(1)nrEaxa（最左一位），且 - 相對誤差為相對誤差為 的近似數的近似數 x x * * 至少具有至少具有 n n 位有效數字位有效數字。 n例：要使例：要使 的近似值相對誤差限小的近似值相對誤差限小于于0.1%, 0.1%, 則則 要取幾位有效數字？要取幾位有效數字？假設取假設取 n n位有效數字。位有效數字。20204%1 . 0104214,4 . 42011nexnr基本的誤差估計（基本的誤差估計（P6P6）n函數計算的誤差估計函數計算的誤差估計 1. 1. 2. 2.)()( )()()( )(*xefxxffexexfxferr)(),()(),()()(

21、),()(),(),(*yeyyxffyxexyxffxfeyeyyxfxexyxfyxferrr基本的誤差估計基本的誤差估計n n n 2()( )( )()( )( )1( )( )( )()( )( )rrre xye xeye xyye xxeyxxee xe xyyyxyexyexeyxyxyq 避免相近的數相減避免相近的數相減()( )( )rrrxyexyexeyxyxy 當當x x與與y y相近，相近， 就可能很大，從而導致計就可能很大，從而導致計算結果的有效數字位數的減少算結果的有效數字位數的減少。 ()rexy設計算法時應遵循的一些原則設計算法時應遵循的一些原則arctan

22、 5430arctan 5429y arctan 5430arctan 542911arctanarctan15429543029479471y 用具有舍入功能的八位計算器計算用具有舍入功能的八位計算器計算1.5706122 1.5706121 0.0000001y83.392191110y（1）（2）(1)(1)式的準確值為式的準確值為0.00000003392191 ,0.00000003392191 , q例如例如 設計算法時應遵循的一些原則設計算法時應遵循的一些原則例例 求實系數二次方程求實系數二次方程 的根的根 02cbxax解解 考慮兩種解法考慮兩種解法。 算法算法 1 1：aac

23、bbx2422,11221,24)(axcxaacbbsignbx算法算法 2 2：0101)(bbbsign其中其中signsign表示取數的符號，即表示取數的符號，即對算法對算法1 1，若，若 4ac 4ac ，分子有一個相近數相減，會大分子有一個相近數相減，會大量損失有效數字，從而有一個較大誤差。量損失有效數字，從而有一個較大誤差。2b設計算法時應遵循的一些原則設計算法時應遵循的一些原則l 幾種經驗性避免誤差危害的方法幾種經驗性避免誤差危害的方法：xxxx lnlnln 1xxx 當當 | x | 1 時：時：21 cos2sin2xx 2111126xexxx. 設計算法時應遵循的一些

24、原則設計算法時應遵循的一些原則設計算法時應遵循的一些原則設計算法時應遵循的一些原則q 避免大數吃小數（避免大數吃小數（P13P13） 由于計算機的字長有限，又要作對階處理，在由于計算機的字長有限，又要作對階處理，在數值運算中，如果數據的數量級相差很大，如不注數值運算中，如果數據的數量級相差很大，如不注意運算次序，就可能出現大數意運算次序，就可能出現大數“吃掉吃掉”小數的現象。小數的現象。求和時求和時 從小到大從小到大 相加，可使結果的誤差減小相加，可使結果的誤差減小設計算法時應遵循的一些原則設計算法時應遵循的一些原則q 避免小分母避免小分母21()()xxee xe yyyy可知，當可知，當y

25、 y 接近于接近于0 0時，時， 也可能很大也可能很大。( )xey 計算量：計算量：一個算法所需要的乘法和除法總次一個算法所需要的乘法和除法總次數稱為數稱為計算量計算量。計算量的單位為。計算量的單位為flopflop，表示完，表示完成一次浮點數乘或除法所需要的時間。算法的成一次浮點數乘或除法所需要的時間。算法的計算量可以衡量算法的優劣，因為它體現著算計算量可以衡量算法的優劣，因為它體現著算法的計算效率，通常算法的計算量越小，則算法的計算效率，通常算法的計算量越小，則算法的計算效率越高，因而該算法也越好。法的計算效率越高，因而該算法也越好。 由于計算機做加減法要比乘除法快得多，故由于計算機做加

26、減法要比乘除法快得多，故算法的計算量可以不考慮加減法的時間。算法的計算量可以不考慮加減法的時間。 q 簡化計算簡化計算, ,減少乘除法運算次數減少乘除法運算次數 （P11P11）設計算法時應遵循的一些原則設計算法時應遵循的一些原則設計算法時應遵循的一些原則設計算法時應遵循的一些原則例如例如：計算計算 的值。的值。31x 若將若將 x x 的值逐個相乘，要做的值逐個相乘，要做3030次乘法，若按次乘法，若按計算，只要計算，只要8 8次運算就可以了次運算就可以了。3124816xxx x x x更一般的情況更一般的情況 計算多項式計算多項式 的值。輸入數據為的值。輸入數據為a ai i和和x x，

27、輸出數據為，輸出數據為 p p( (x x) ) 的的值。值。110( )nnnnp xa xaxa若按如下嵌套形式從里向外一層層地計算若按如下嵌套形式從里向外一層層地計算1210( )()nnnp xa xaaxa xaFF算法算法（秦九韶法（秦九韶法或或 Horner算法算法）10(1,2,1,0),( )nnkkkknnuauxuap xu 此為此為秦九韶（宋代數學家）法秦九韶（宋代數學家）法。只需要做。只需要做n n次乘次乘法和法和n n次加法。次加法。設計算法時應遵循的一些原則設計算法時應遵循的一些原則q 選用選用數值穩定數值穩定的算法，控制舍入誤差的傳播的算法，控制舍入誤差的傳播在

28、計算過程中產生的舍入誤差能被控制在一定在計算過程中產生的舍入誤差能被控制在一定的范圍內，且對最后的結果影響不大的算法稱為的范圍內，且對最后的結果影響不大的算法稱為數值穩定算法。數值穩定算法。不是數值穩定的算法稱為不是數值穩定的算法稱為數值不數值不穩定算法。穩定算法。（P9P9）因初始數據的微小變化，導致計算結果的劇烈因初始數據的微小變化，導致計算結果的劇烈變化問題稱為變化問題稱為病態問題病態問題。病態問題也稱為壞問題，。病態問題也稱為壞問題，這類問題通常是問題本身固有的。（這類問題通常是問題本身固有的。（P8P8）.210110,n,dxexeIxnn 例：例：計算計算10011d1063212056 xIex.ee11.nnIn I公式一：公式一：記為記為*0,I則初始誤差則初始誤差 80000 5 10 .eII.39