数值分析1-3.ppt

3误差定误差定性分析性分析与避免与避免误差危误差危害害一、算法的数值稳定性概念一、算法的数值稳定性概念二、设计算法的若干原则二、设计算法的若干原则1.定义：算法定义：算法 所谓所谓算法算法，是指对一些数据按某种，是指对一些数据按某种规定的顺序进行的运算序列。规定的顺序进行的运算序列。一、算法的数值稳定性概念一、算法的数值稳定性概念 对同一问题，选用不同的算法，所对同一问题，选用不同的算法，所得结果的精度往往大不相同。得结果的精度往往大不相同。请看下例请看下例例例：用四位有效数字计算如下：用四位有效数字计算如下y的值的值解解：y的精确值是的精确值是0.0158074374，算法算法1：直接计算，则：直接计算，则 结果只有一位有效数字，其相对误结果只有一位有效数字，其相对误差大于差大于26%。算法算法2：作适当变形后计算作适当变形后计算结果具有四位有效数字，其相对误差结果具有四位有效数字，其相对误差不超过不超过0.02%。2.定义：数值稳定性定义：数值稳定性初初始始数数据据的的误误差差或或计计算算中中的的舍舍入入误误差差在在计计算算过过程程中中的的传传播播，因因算算法法不不同同而而异异。一一个个算算法法，如如果果计计算算结结果果受受误误差差的的影影响响小小，就就称称该该算算法法具具有有较较好好的的数数值稳定性值稳定性二、设计算法的若干原则二、设计算法的若干原则(一一)要避免相近两数相减要避免相近两数相减例：例：a1=0.12345，a2=0.12346，各有各有5位有位有效数字。效数字。而而 a2 a1=0.00001，只剩下只剩下1位有效数位有效数字。字。|很小，很小，几种经验性避免方法：几种经验性避免方法：很小，很小，(二二)要防止大数要防止大数“吃掉吃掉”小数，注意小数，注意保护重要数据保护重要数据例：例：用单精度计算用单精度计算 的根。的根。精确解为精确解为 算法算法1 1：利用求根公式利用求根公式在计算机内，在计算机内，109存为存为0.1 1010，1存为存为0.1 101。做加法时，做加法时，两加数的指数先向大指数对齐，再将浮点部分相加。即两加数的指数先向大指数对齐，再将浮点部分相加。即1 的指数部分须变为的指数部分须变为1010，则：，则：1=0.0000000001 1010，取，取单精度时就成为：单精度时就成为：109+1=0.10000000 1010+0.00000000 1010=0.10000000 1010大数吃小数大数吃小数?算法算法2：先解出：先解出 再利用再利用注：注：求和时从小到大相加，可使和的误差减小。求和时从小到大相加，可使和的误差减小。例例：在：在5位浮点十进制计算机上，计位浮点十进制计算机上，计算算y=54 321+0.4+0.3+0.4解解：若按从左到右的顺序进行计算，：若按从左到右的顺序进行计算，后三位在对阶过程变为后三位在对阶过程变为 后三个数都在对阶过程中变为零，后三个数都在对阶过程中变为零，得出含有较大误差的结果得出含有较大误差的结果 y=54321。但若按从右到左的顺序进行计算但若按从右到左的顺序进行计算，后三位在对阶过程变为后三位在对阶过程变为 这种算法避免了大数这种算法避免了大数“吃掉吃掉”小数！小数！一般地，有如下原则一般地，有如下原则 若干数相加，采用绝对值较小者若干数相加，采用绝对值较小者先加的算法，结果的相对误差限较先加的算法，结果的相对误差限较小小(三三)注意简化计算步骤，减少运算次注意简化计算步骤，减少运算次数，避免误差积累数，避免误差积累例例：计算多项式的值：计算多项式的值解解：如果先计算各项然后相加，则：如果先计算各项然后相加，则乘法次数乘法次数=4+3+2+1=10，加法次数，加法次数=4但如但如改用下式计算改用下式计算 则只需做则只需做4次乘法和次乘法和4次加法。计次加法。计算量大大减少！算量大大减少！秦九韶算法是中国秦九韶算法是中国南宋南宋时期的数学家时期的数学家秦九韶秦九韶提提出的一种出的一种多项式多项式简化简化算法算法。在西方被称作。在西方被称作霍纳霍纳算法算法（Horner algorithm或或Horner scheme），），是以是以英国数学家威廉英国数学家威廉乔治乔治霍纳霍纳命名的命名的.秦九韶作于秦九韶作于1240年的数书九章已经运用十年的数书九章已经运用十进制和零，领先于英国数学家威廉进制和零，领先于英国数学家威廉乔治乔治霍纳霍纳(William George Horner)于于1819年发表的解高年发表的解高次代数方程的方法。次代数方程的方法。注：注：第二种方法称为第二种方法称为“秦九韶算法秦九韶算法”通常，计算如下通常，计算如下n次多项式的值次多项式的值如果先计算各项然后相加，则如果先计算各项然后相加，则 乘法次数乘法次数=n+(n-1)+2+1 =n(n+1)/2 加法次数加法次数=n若采用若采用“秦九韶算法秦九韶算法”，则，则 乘法次数乘法次数=n 加法次数加法次数=n两两种种算算法法的的乘乘法法运运算算次次数数随随n的的变变化化见下表：见下表：n=2n=3n=4n=5方法方法1 1361015方法方法2 22345(四四)要避免绝对值小的数作除数要避免绝对值小的数作除数 可知，当除数可知，当除数x2接近于零时，商的接近于零时，商的绝对误差就可能很大。因此要避免绝绝对误差就可能很大。因此要避免绝对值小的数作除数。对值小的数作除数。由商的绝对误差限由商的绝对误差限例：例：当当x接近于接近于0时，时，的分子、分母都接近的分子、分母都接近0，为避免绝对，为避免绝对值小的数作除数，可将原式变形为值小的数作除数，可将原式变形为例：例：当当x很大时，很大时，的分母接近的分母接近0，为避免绝对值小的数，为避免绝对值小的数作除数，可将原式变形为作除数，可将原式变形为(五五)设法控制误差的传播设法控制误差的传播许多算法具有递推性。递推法运算过许多算法具有递推性。递推法运算过程较规律，但多次递推必然导致误差程较规律，但多次递推必然导致误差的积累。的积累。例：例：计算积分计算积分解：解：利用分部积分公式利用分部积分公式有有从而有递推公式从而有递推公式又因为又因为这这说说明明由由初初始始值值E1的的误误差差在在计计算算过过程程中中绝绝对对值值会会迅迅速速扩扩大大。因因此此这这个个算法不可靠！算法不可靠！则则误差传递规律是误差传递规律是但若将但若将公式改为公式改为则则误差按规律误差按规律逐步缩小，从而逐步缩小，从而 所所以以只只要要适适当当选选择择初初值值E9，再再由由公公式式依依次次计计算算E8,E7,E1,便便可可以以得得到到比比较较精精确确的的结结果果。因因此此这这个算法是稳定的！个算法是稳定的！本章作业本章作业:习习题题 1 1，2 2，3 3，4 4，6 6，9 9，11 11，1212第一章第一章 复习复习一、主要内容一、主要内容(省略省略)二、典型题解析二、典型题解析二、典型题解析二、典型题解析例例1 用用最最小小刻刻度度为为毫毫米米的的卡卡尺尺测测量量直直杆杆甲甲和和直直杆杆乙乙，分分别别读读出出长长度度a=312mm和和b=24mm，问问a,b的的绝绝对对误误差差限限、相相对对误误差差限限各各是是多多少少？两两直直杆杆实实际际长长度度x和和y在在什么范围内？什么范围内？解：解：由于绝对误差限是测量工具最小单由于绝对误差限是测量工具最小单位的一半，故位的一半，故故故两直杆实际长度两直杆实际长度x和和y的取值范围为的取值范围为即即同理同理注注：本本题题x与与y有有相相同同的的绝绝对对误误差差限限，但但相相对对误误差差限限不不同同，相相对对误误差差限限越越小小越越精精确。确。例例2 设设a=-2.18和和b=2.1200是是分分别别由由准准确确值值x和和y经经过过四四舍舍五五入入而而得得到到的的近近似似值值，问：问：各各是多少？是多少？解解：由由于于凡凡是是由由准准确确值值经经过过四四舍舍五五入入而而得得到到的的近近似似值值，其其绝绝对对误误差差限限等等于于该该近近似值末位的半个单位。故似值末位的半个单位。故因此相对误差限为因此相对误差限为例例3 下下列列近近似似值值的的绝绝对对误误差差限限都都是是0.005，问：各个近似值有几位有效数字？问：各个近似值有几位有效数字？分分析析 按按有有效效数数字字的的定定义义，根根据据绝绝对对误误差差限限，并并将将其其取取为为某某位位的的半半个个单单位位，从从中中就就可可看看出出有有效效数数字的个数字的个数解解：由由题题意意，近近似似值值的的绝绝对对误误差差限限都都是是0.005，由于，由于故近似值精确到小数点后第二位，根据故近似值精确到小数点后第二位，根据有效数字的定义有效数字的定义有有三位有效数字三位有效数字1,3,8有有一位有效数字一位有效数字3没有有效数字没有有效数字例例4 按按四四舍舍五五入入原原则则写写出出下下列列各各数数具具有有5位有效数字的近似值：位有效数字的近似值：解：解：由于有效数字的计算是从第一位非由于有效数字的计算是从第一位非零数字算起，故零数字算起，故具有具有5位有效数字的近似数是位有效数字的近似数是例例5 设设x=105%，试试求求函函数数f(x)=x1/n的相对误差限。的相对误差限。分析分析 这是标准的一元函数误差的传这是标准的一元函数误差的传播问题，只需利用公式直接计算。播问题，只需利用公式直接计算。解解 由由x=105%知知近近似似值值x*=10，绝绝对对误差限误差限由于由于故故因此当因此当x*=10时时即即x*=10相对误差限相对误差限注：注：从本例可以看出，对于函数从本例可以看出，对于函数x1/n，函数值的相对误差限约是自变量函数值的相对误差限约是自变量相对误差限的相对误差限的1/n倍。倍。由由例例6 设设 x=1.300.005,y=0.8710.0005，如果用如果用作作为为f(x,y)的的近近似似值值，则则 能能有有几几位位有有效效数字？数字？解解 而而故故所以所以将将数据代入数据代入得得这这说明说明精确到小数点后第二位，故能有两位有精确到小数点后第二位，故能有两位有效数字效数字4，9。例例7 请请给给一一种种算算法法计计算算2256要要求求乘乘法次数尽可能少。法次数尽可能少。分析分析 如果逐个相乘要用如果逐个相乘要用255次乘法。要次乘法。要尽可能减少运算量，一种思路是尽可能减少运算量，一种思路是尽可能尽可能运用已经算出的结果运用已经算出的结果。如。如2256=(2128)2，当当2128计算出来之后，再需一次乘法便可计算出来之后，再需一次乘法便可得得2256；而；而2128=(264)2，同样的，当同样的，当264计计算出来后，再需一次乘法就可以计算出算出来后，再需一次乘法就可以计算出2128；依次类推，这样就可得到一种乘法依次类推，这样就可得到一种乘法次数少得多的算法。次数少得多的算法。解解 这样这样共计共计算算 8次乘次乘法就法就可以可以计算计算出结出结果果