電子科大MATLAB第4節(jié)算法介紹

1、第四節(jié)第四節(jié) 算法介紹算法介紹算法（Algorithm） Algorithm is an effective method for solving a problem using a finite sequence of instructions. （comes from Wikipedia） 算法是利用有限（計算機）指令解決問題的有效方法。算法是利用有限（計算機）指令解決問題的有效方法。 有效性：必須能得到正確結(jié)果；有效性：必須能得到正確結(jié)果； 有限性：時間、空間（內(nèi)存空間）范圍有限；有限性：時間、空間（內(nèi)存空間）范圍有限； 計算機指令：計算機指令： 算術(shù)指令：算術(shù)指令： +，-，*，/，,

2、 比較指令：比較指令： , = =, =, , 控制指令：控制指令：for , if, while, , 賦值指令：賦值指令： =，算法（Algorithm）不是有限不是有限指令指令23100000011111.1!2!3!1000000!xexxxx 改進 2：有有限？限？21111!2!xexx 改進 1：算法？算法？有有限？限？有有效效?有有效效？xe例：設(shè)計算法，用計算機計算函數(shù)2311111.1!2!3!xnexxxxn 算法原理：泰勒定理算法優(yōu)嗎？如何評價算法的優(yōu)劣？算法優(yōu)嗎？如何評價算法的優(yōu)劣？算法研究的主要問題 算法研究中的主要問題：算法研究中的主要問題： 算法的實現(xiàn)：如何設(shè)計

3、算法能夠解決一類問題算法的實現(xiàn)：如何設(shè)計算法能夠解決一類問題 算法的誤差：算法的結(jié)果與真實結(jié)果有多大差距算法的誤差：算法的結(jié)果與真實結(jié)果有多大差距 算法的運算效率：如何能夠更快地解決問題算法的運算效率：如何能夠更快地解決問題 算法的穩(wěn)定性：當輸入存在誤差時，算法是否還能得到較好的結(jié)算法的穩(wěn)定性：當輸入存在誤差時，算法是否還能得到較好的結(jié)果。果。誤差的基本概念絕對誤差絕對誤差（absolute error ）：真實值與近似值差的絕對值。絕對誤差限絕對誤差限（精度，accuracy）：絕對誤差的范圍；相對誤差相對誤差（relative error）：絕對誤差與精確值之比（如果精確值未知，計算時用近

4、似值代替）。相對誤差限相對誤差限：相對誤差的范圍;有效數(shù)字有效數(shù)字：若近似值x*的誤差限是某一位的半個單位，該位到x*的第一位非零數(shù)字共n位，則稱x*有n位有效數(shù)字。 真實值：1.3333，計算值：1.350，有三位有效數(shù)字 計算值：1.390，小數(shù)點后第二位差大于半個單位0.5，則只有兩位有效數(shù)字。誤差的基本概念例：真實值=00123.000456 要求保留5位有效數(shù)字：00123.00（最前面最前面0不計，最后不計，最后0不省不?。?絕對誤差=|真實值-近似值| = 0.000456， 相對誤差= 0.000456 / 00123.000456 =3.7073e-006 保留7位有效數(shù)字：

5、00123.0005（四舍五入四舍五入） 絕對誤差=0.0000440.00005（絕對誤差不大于其最末數(shù)字的半個絕對誤差不大于其最末數(shù)字的半個單位單位） 相對誤差= 0.000044 / 00123.000456 = 3.5772e-007算法的誤差 算法的誤差包括：算法的誤差包括： 模型誤差 測量誤差 舍入誤差舍入誤差 截斷誤差截斷誤差舍入誤差（Roundoff Errors） 舍入誤差：由于數(shù)據(jù)輸入位數(shù)有限及計算機精度有限而導(dǎo)致的誤差。 計算機中的數(shù)包括兩類： 用來表示整數(shù)的數(shù)： int，unsigned int，long，short， 用來表示小數(shù)的數(shù)浮點數(shù)：float ，double

6、。 當利用浮點數(shù)表示無限小數(shù)時，不可避免地需要舍去小數(shù)點某位以后的數(shù)據(jù)，從而引入了舍入誤差。浮點數(shù)標準：IEEE 754 浮點數(shù)：IEEE 754（1985）: Standard for Binary Floating-Point Arithmetic（可在google上下載該文檔）。 在matlab幫助文件搜索欄中輸入：“ IEEE 754 ”，可得到IEEE 754的介紹。浮點數(shù)浮點數(shù)包括：半精度（16位）、單精度（32位）、雙精度（64位）和四精度（128位）。規(guī)范：IEEE 754標準：類似于科學(xué)計數(shù)法，共計264個數(shù)，其中包含：NaN，Inf等非數(shù)字標記。1023( 1) 2(1)s

7、exf 浮點數(shù)表示符號符號位位 sb631023( 1) 2(1) 27.56640625sexf 指數(shù)位指數(shù)位 eb62 b52e =1027尾數(shù)尾數(shù) f b51 b01345812111111222222f浮點數(shù)的轉(zhuǎn)換 例：將“7.5”轉(zhuǎn)換為64位浮點數(shù)二進制表示021117.5( 1) 2 (1)248 S=0e=2+1023=1025f = 0.5+0.25+0.1250 10000000001 1110.0實驗：編程將64位浮點數(shù)轉(zhuǎn)化為二進制數(shù)，驗證本例結(jié)果是否正確。浮點數(shù)的性質(zhì) 浮點數(shù)是什么數(shù)？ 實數(shù)？ 有理數(shù)？ 有限小數(shù)？ 有多少個不同的浮點數(shù)？ 264（64位，每位有兩個狀態(tài)，

8、“0”和“1”） 浮點數(shù)是由264個有限小數(shù)（包含整數(shù)）構(gòu)成的集合？ 錯。IEEE 定義了一些異常值，inf （無窮）和 NaN（“非數(shù)字”） 浮點數(shù)精度是多少？ eps=2-52 = 2.2204E-16 最大的浮點數(shù)是多少？ realmax =（2-esp）21023 = 1.7977E+308 最小的浮點數(shù)是多少？ -realmax = -1.7977E+308 最小的正浮點數(shù)是多少？ realmin = 2-1022 2-52 =4.9407e-324（精確）浮點數(shù)的誤差例：eps是相對誤差？絕對是相對誤差？絕對誤差？誤差？1023( 1) 2(1)sexf 浮點數(shù)的誤差例：判斷：判斷

9、：1、eps是是 x 的絕對誤差的絕對誤差2、eps是是 x 的相對誤差的相對誤差3、eps是是 f 的絕對誤差的絕對誤差4、eps是是 f 的絕對誤差限的絕對誤差限5、 eps是是 f 的精度的精度思考：思考：1 1、浮點數(shù)的絕對誤差不同；浮點數(shù)絕對值越大，絕對誤差越大。、浮點數(shù)的絕對誤差不同；浮點數(shù)絕對值越大，絕對誤差越大。2 2、浮點數(shù)的、浮點數(shù)的相對誤差不大于相對誤差不大于eps。舍入誤差的注意事項1.避免相近二數(shù)相減易減小有效數(shù)字避免相近二數(shù)相減易減小有效數(shù)字2.避免小分母避免小分母 : 分母小會造成浮點溢出分母小會造成浮點溢出3.求和時從小到大相加，可使和的誤差減小求和時從小到大相

10、加，可使和的誤差減小4.簡化計算步驟，減少運算次數(shù)，避免誤差積累。簡化計算步驟，減少運算次數(shù)，避免誤差積累。5.選用穩(wěn)定的算法選用穩(wěn)定的算法截斷誤差設(shè)計算法，計算指數(shù)函數(shù)：設(shè)計算法，計算指數(shù)函數(shù)：xye232011111.1!2!3!20!yxxxx 截斷誤差（截斷誤差（truncation error ）：利用有限次運算近似無限（較）：利用有限次運算近似無限（較多）次運算中引入的誤差。多）次運算中引入的誤差。212211-.21!22!xeyxx截斷截斷誤差誤差2112020 . 20-121!21 19 . 1xeyx改進算法，仍然用泰勒定理，計算改進算法，仍然用泰勒定理，計算 x=20.

11、4當當 x=20截斷誤差算法結(jié)果：算法結(jié)果：？= esp截斷誤差clear allclose all% clcformat long% 浮點數(shù)浮點數(shù)% 浮點數(shù)的二進制表示浮點數(shù)的二進制表示display(浮點數(shù)的二進制表示浮點數(shù)的二進制表示)x = 7.5fid = fopen(conv.bin, w);fwrite(fid, x, double);fclose(fid);fid = fopen(conv.bin, r);B = fread(fid, 1, ubit64);fclose(fid);Bin = dec2bin(B, 64)% 例例 2.3display(例子例子 2.3)disp

12、lay(x = 4/3-1)x = 4/3-1display(y = 3 * x)y = 3 * xdisplay(z = 1 - y)z = 1 - y% 例例 2.3.1display(例子例子 2.3.1)display(4000000/3 - 1333333)x = 4000000/3 - 1333333display(y = 3 * x)y = 3 * xdisplay(絕對誤差：絕對誤差：z = 1 - y)z = 1 - ydisplay(相對誤差：相對誤差：z1 = z / (4000000/3)z1 = z / (4000000/3)% pp 36 習(xí)題習(xí)題4display(

13、第第 36頁頁 習(xí)題習(xí)題4 - )a = 1;b = -100000000;c = 1;display(a = 1; b = -100000000; c = 1;)display( )display(x1 = (-b + sqrt(b * b - 4 * a * c) / 2 / a)x1 = (-b + sqrt(b * b - 4 * a * c) / 2 / adisplay(x2 = (-b - sqrt(b * b - 4 * a * c) / 2 / a)x2 = (-b - sqrt(b * b - 4 * a * c) / 2 / adisplay(y1 = 2 * c / (

14、-b + sqrt(b * b - 4 * a * c)y1 = 2 * c / (-b + sqrt(b * b - 4 * a * c)display(y2 = 2 * c / (-b - sqrt(b * b - 4 * a * c)y2 = 2 * c / (-b - sqrt(b * b - 4 * a * c)display(第第 36頁頁 習(xí)題習(xí)題4 - 計算相對誤差，結(jié)果檢驗計算相對誤差，結(jié)果檢驗 - )display(z1 = (a * x1 * x1 + b * x1 + c) / x1)z1 = (a * x1 * x1 + b * x1 + c) / x1display

15、(z2 = (a * x2 * x2 + b * x2 + c) / x2)z2 = (a * x2 * x2 + b * x2 + c) / x2display(z3 = (a * y1 * y1 + b * y1 + c) / y1)z3 = (a * y1 * y1 + b * y1 + c) / y1display(z4 = (a * y2 * y2 + b * y2 + c) / y2)z4 = (a * y2 * y2 + b * y2 + c) / y2% 例例 2.4x = 0.988:0.0001:1.012;y = x.7-7*x.6+21*x.5-35*x.4+35*x.

16、3-21*x.2+7*x-1;plot(x,y)截斷誤差clear allclose allclc% 計算指數(shù)函數(shù)display(計算指數(shù)函數(shù))% 算法 1 display(算法 1：)display( ) x = 20;display(strcat(x = , num2str(x) display( ) e1 = exp(x);display(strcat(真實值 = exp(x) = , num2str(e1, %e) display( ) e2 = 1;for iii = 1 : 20 e2 = e2 + 1 / factorial(iii) * x iii; ende2;display

17、(strcat(計算值 = , num2str(e2, %e) display( ) d2 = abs(e1 - e2);display(strcat(絕對誤差 = , num2str(d2, %e) display( ) % 算法 2display(算法 2：)xi = round(x);xr = x - xi;e0 = exp(1);e3 = 1;for iii = 1 : 20 e3 = e3 + 1 / factorial(iii) * xr iii;ende3 = (e0)xi) * e3;display(strcat(計算值 = , num2str(e3, %e) display(

18、 ) d3 = e1 - e3;display(strcat(絕對誤差 = , num2str(d3, %e) display( )20.4200.40.4.yee eee e e算法改進：算法改進：算法的運算量算法所需要執(zhí)行指令的數(shù)目。算法所需要執(zhí)行指令的數(shù)目。例：分析例：分析計算函數(shù)計算函數(shù) 的運算量（不考慮算法優(yōu)化）的運算量（不考慮算法優(yōu)化）xye01y 11yx 2212xyx 233123!xxyx 加法0123乘法0025 算法運算量分析，更關(guān)注隨著問題維數(shù)增加，計算量的變化規(guī)律，即問算法運算量分析，更關(guān)注隨著問題維數(shù)增加，計算量的變化規(guī)律，即問題復(fù)雜度的階數(shù)題復(fù)雜度的階數(shù) O(n

19、?)，例子中，加法復(fù)雜度為，例子中，加法復(fù)雜度為O(n)，乘法復(fù)雜度為，乘法復(fù)雜度為O(n2)n(1)/2-1n n復(fù)雜度是復(fù)雜度是 O(n2)算法的運算量2乘法、乘法、3加加5乘法、乘法、3加加成功案例 降低算法運算量的成功案例：降低算法運算量的成功案例： 快速傅立葉變換（快速傅立葉變換（FFT）；）； 采用蝶形運算，將采用蝶形運算，將DFT的運算量從的運算量從O(n2)降低到降低到O(nlog(n)）；）； 思考：假設(shè)思考：假設(shè)n = 10000， DFT運算量大概是運算量大概是FFT 的多少倍，體會的多少倍，體會運算復(fù)雜度降低對算法效率的影響。運算復(fù)雜度降低對算法效率的影響。蝶形運算算法的穩(wěn)定性 算法的誤差：算法的誤差： 在輸入數(shù)據(jù)準確的前提下，在輸入數(shù)據(jù)準確的前提下，算法計算結(jié)果與真實結(jié)果的差。算法計算結(jié)果與真實結(jié)果的差。 算法