电子科大MATLAB第4节算法介绍

1、第四节第四节 算法介绍算法介绍算法（Algorithm） Algorithm is an effective method for solving a problem using a finite sequence of instructions. （comes from Wikipedia） 算法是利用有限（计算机）指令解决问题的有效方法。算法是利用有限（计算机）指令解决问题的有效方法。 有效性：必须能得到正确结果；有效性：必须能得到正确结果； 有限性：时间、空间（内存空间）范围有限；有限性：时间、空间（内存空间）范围有限； 计算机指令：计算机指令： 算术指令：算术指令： +，-，*，/，,

2、 比较指令：比较指令： , = =, =, , 控制指令：控制指令：for , if, while, , 赋值指令：赋值指令： =，算法（Algorithm）不是有限不是有限指令指令23100000011111.1!2!3!1000000!xexxxx 改进 2：有有限？限？21111!2!xexx 改进 1：算法？算法？有有限？限？有有效效?有有效效？xe例：设计算法，用计算机计算函数2311111.1!2!3!xnexxxxn 算法原理：泰勒定理算法优吗？如何评价算法的优劣？算法优吗？如何评价算法的优劣？算法研究的主要问题 算法研究中的主要问题：算法研究中的主要问题： 算法的实现：如何设计

3、算法能够解决一类问题算法的实现：如何设计算法能够解决一类问题 算法的误差：算法的结果与真实结果有多大差距算法的误差：算法的结果与真实结果有多大差距 算法的运算效率：如何能够更快地解决问题算法的运算效率：如何能够更快地解决问题 算法的稳定性：当输入存在误差时，算法是否还能得到较好的结算法的稳定性：当输入存在误差时，算法是否还能得到较好的结果。果。误差的基本概念绝对误差绝对误差（absolute error ）：真实值与近似值差的绝对值。绝对误差限绝对误差限（精度，accuracy）：绝对误差的范围；相对误差相对误差（relative error）：绝对误差与精确值之比（如果精确值未知，计算时用近

4、似值代替）。相对误差限相对误差限：相对误差的范围;有效数字有效数字：若近似值x*的误差限是某一位的半个单位，该位到x*的第一位非零数字共n位，则称x*有n位有效数字。 真实值：1.3333，计算值：1.350，有三位有效数字 计算值：1.390，小数点后第二位差大于半个单位0.5，则只有两位有效数字。误差的基本概念例：真实值=00123.000456 要求保留5位有效数字：00123.00（最前面最前面0不计，最后不计，最后0不省不省） 绝对误差=|真实值-近似值| = 0.000456， 相对误差= 0.000456 / 00123.000456 =3.7073e-006 保留7位有效数字：

5、00123.0005（四舍五入四舍五入） 绝对误差=0.0000440.00005（绝对误差不大于其最末数字的半个绝对误差不大于其最末数字的半个单位单位） 相对误差= 0.000044 / 00123.000456 = 3.5772e-007算法的误差 算法的误差包括：算法的误差包括： 模型误差 测量误差 舍入误差舍入误差 截断误差截断误差舍入误差（Roundoff Errors） 舍入误差：由于数据输入位数有限及计算机精度有限而导致的误差。 计算机中的数包括两类： 用来表示整数的数： int，unsigned int，long，short， 用来表示小数的数浮点数：float ，double

6、。 当利用浮点数表示无限小数时，不可避免地需要舍去小数点某位以后的数据，从而引入了舍入误差。浮点数标准：IEEE 754 浮点数：IEEE 754（1985）: Standard for Binary Floating-Point Arithmetic（可在google上下载该文档）。 在matlab帮助文件搜索栏中输入：“ IEEE 754 ”，可得到IEEE 754的介绍。浮点数浮点数包括：半精度（16位）、单精度（32位）、双精度（64位）和四精度（128位）。规范：IEEE 754标准：类似于科学计数法，共计264个数，其中包含：NaN，Inf等非数字标记。1023( 1) 2(1)s

7、exf 浮点数表示符号符号位位 sb631023( 1) 2(1) 27.56640625sexf 指数位指数位 eb62 b52e =1027尾数尾数 f b51 b01345812111111222222f浮点数的转换 例：将“7.5”转换为64位浮点数二进制表示021117.5( 1) 2 (1)248 S=0e=2+1023=1025f = 0.5+0.25+0.1250 10000000001 1110.0实验：编程将64位浮点数转化为二进制数，验证本例结果是否正确。浮点数的性质 浮点数是什么数？ 实数？ 有理数？ 有限小数？ 有多少个不同的浮点数？ 264（64位，每位有两个状态，

8、“0”和“1”） 浮点数是由264个有限小数（包含整数）构成的集合？ 错。IEEE 定义了一些异常值，inf （无穷）和 NaN（“非数字”） 浮点数精度是多少？ eps=2-52 = 2.2204E-16 最大的浮点数是多少？ realmax =（2-esp）21023 = 1.7977E+308 最小的浮点数是多少？ -realmax = -1.7977E+308 最小的正浮点数是多少？ realmin = 2-1022 2-52 =4.9407e-324（精确）浮点数的误差例：eps是相对误差？绝对是相对误差？绝对误差？误差？1023( 1) 2(1)sexf 浮点数的误差例：判断：判断

9、：1、eps是是 x 的绝对误差的绝对误差2、eps是是 x 的相对误差的相对误差3、eps是是 f 的绝对误差的绝对误差4、eps是是 f 的绝对误差限的绝对误差限5、 eps是是 f 的精度的精度思考：思考：1 1、浮点数的绝对误差不同；浮点数绝对值越大，绝对误差越大。、浮点数的绝对误差不同；浮点数绝对值越大，绝对误差越大。2 2、浮点数的、浮点数的相对误差不大于相对误差不大于eps。舍入误差的注意事项1.避免相近二数相减易减小有效数字避免相近二数相减易减小有效数字2.避免小分母避免小分母 : 分母小会造成浮点溢出分母小会造成浮点溢出3.求和时从小到大相加，可使和的误差减小求和时从小到大相

10、加，可使和的误差减小4.简化计算步骤，减少运算次数，避免误差积累。简化计算步骤，减少运算次数，避免误差积累。5.选用稳定的算法选用稳定的算法截断误差设计算法，计算指数函数：设计算法，计算指数函数：xye232011111.1!2!3!20!yxxxx 截断误差（截断误差（truncation error ）：利用有限次运算近似无限（较）：利用有限次运算近似无限（较多）次运算中引入的误差。多）次运算中引入的误差。212211-.21!22!xeyxx截断截断误差误差2112020 . 20-121!21 19 . 1xeyx改进算法，仍然用泰勒定理，计算改进算法，仍然用泰勒定理，计算 x=20.

11、4当当 x=20截断误差算法结果：算法结果：？= esp截断误差clear allclose all% clcformat long% 浮点数浮点数% 浮点数的二进制表示浮点数的二进制表示display(浮点数的二进制表示浮点数的二进制表示)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 习题习题4display(

13、第第 36页页 习题习题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页页 习题习题4 - 计算相对误差，结果检验计算相对误差，结果检验 - )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% 计算指数函数display(计算指数函数)% 算法 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算法改进：算法改进：算法的运算量算法所需要执行指令的数目。算法所需要执行指令的数目。例：分析例：分析计算函数计算函数 的运算量（不考虑算法优化）的运算量（不考虑算法优化）xye01y 11yx 2212xyx 233123!xxyx 加法0123乘法0025 算法运算量分析，更关注随着问题维数增加，计算量的变化规律，即问算法运算量分析，更关注随着问题维数增加，计算量的变化规律，即问题复杂度的阶数题复杂度的阶数 O(n

19、?)，例子中，加法复杂度为，例子中，加法复杂度为O(n)，乘法复杂度为，乘法复杂度为O(n2)n(1)/2-1n n复杂度是复杂度是 O(n2)算法的运算量2乘法、乘法、3加加5乘法、乘法、3加加成功案例 降低算法运算量的成功案例：降低算法运算量的成功案例： 快速傅立叶变换（快速傅立叶变换（FFT）；）； 采用蝶形运算，将采用蝶形运算，将DFT的运算量从的运算量从O(n2)降低到降低到O(nlog(n)）；）； 思考：假设思考：假设n = 10000， DFT运算量大概是运算量大概是FFT 的多少倍，体会的多少倍，体会运算复杂度降低对算法效率的影响。运算复杂度降低对算法效率的影响。蝶形运算算法的稳定性 算法的误差：算法的误差： 在输入数据准确的前提下，在输入数据准确的前提下，算法计算结果与真实结果的差。算法计算结果与真实结果的差。 算法