误差理论 .ppt

误差理论 现在学习的是第1页，共55页2联系方式办公电话：办公电话：87543986手机：手机：15327417949E-mail：现在学习的是第2页，共55页3约法三章请在课堂上不要影响他人的正常听课；请在课堂上不要影响他人的正常听课；请不要在上课期间接打手机、小灵通等；请不要在上课期间接打手机、小灵通等；请按时、认真地完成课后作业；请按时、认真地完成课后作业；请请按按时时进进入入课课堂堂听听课课，有有事事需需要要提提前前写写请请假假条并由本人亲自交给教师。条并由本人亲自交给教师。现在学习的是第3页，共55页4数值分析的研究内容计计算算机机的的出出现现与与发发展展使使生生产产实实践践和和科科学学研研究究中中的的各各类数学问题的数值求解成为可能。类数学问题的数值求解成为可能。研研究究数数学学问问题题的的数数值值解解法法及及其其理理论论的的一一门门学学科科，包包括括数数值值方方法法的的设设计计、分分析析和和有有关关理理论论基基础础以以及及算算法法的的程序实现程序实现。数数值值解解法法的的实实质质：将将数数学学问问题题简简化化为为对对有有限限位位数数的的四四则则运运算算；这这种种简简化化是是一一种种近近似似解解法法，与与数数学学问问题题理论上的正确解或多或少地存在差异。理论上的正确解或多或少地存在差异。现在学习的是第4页，共55页5先修课程高等数学（数学分析）高等数学（数学分析）线性代数线性代数计算机应用基础计算机应用基础C 语言程序设计基础语言程序设计基础现在学习的是第5页，共55页6数值分析的分枝数数值值分分析析又又称称：数数值值计计算算方方法法、计计算算数数学学、计计算算方方法法、近近似似计计算算、科科学计算等。学计算等。近近几几十十年年来来由由于于计计算算机机的的发发展展及及其其在在各各科科学学技技术术领领域域的的应应用用推推广广与与深深化化，新新的的计计算算性性学学科科分分支支纷纷纷纷兴兴起起，数数值值分分析析的的分分枝枝有有：最最优优化化方方法法、计计算算几几何何、计计算算概概率率统统计计，计计算算力力学学、计计算算物物理理、计计算算化化学学、计计算算经经济济学学等等等。等。不不论论数数值值分分析析分分枝枝的的背背景景与与含含义义如如何何，要要用用计计算算机机进进行行科科学学计计算算都都必必须须建建立立相相应应的的数数学学模模型型，并并研研究究其其适适合合于于计计算算机机编编程程的的计计算算方方法法；因因此此，计计算算方方法法是是各各种种计计算算性性科科学学的的联联系系纽纽带带和和共共性性基基础础，是是一一门门兼兼有有基基础础性性、应用性和边缘性的数学学科。应用性和边缘性的数学学科。现在学习的是第6页，共55页7数值分析的应用上上至至天天文文，下下至至地地理理，数数值值分分析析的的应应用用无所不在。无所不在。天气预报天气预报遥感监测遥感监测天体运动轨道求解天体运动轨道求解宏观经济调控宏观经济调控股票、彩票股票、彩票现在学习的是第7页，共55页8研究数值方法的主要任务将将计计算算机机上上不不能能执执行行的的运运算算转转化化为为在在计计算算机机上上可可执行的运算；执行的运算；针针对对所所求求解解的的数数值值问问题题研研究究在在计计算算机机上上可可执执行行的的且有效的计算公式；且有效的计算公式；由由于于可可能能采采用用了了近近似似等等价价运运算算，一一般般需需要要对对结结果果进进行行误误差差分分析析，即即数数值值问问题题的的性性态态及及数数值值方方法法的的收敛性、稳定性等。收敛性、稳定性等。现在学习的是第8页，共55页9数值计算方法的特点面向计算机面向计算机算算法法只只能能包包括括：加加、减减、乘乘、除除运运算算以以及及逻辑逻辑运算运算可靠的理论分析可靠的理论分析主主要要的的理理论论分分析析：误误差差、稳稳定定性性、收收敛敛性、计算量、存储量性、计算量、存储量要求具有良好的计算复杂性要求具有良好的计算复杂性时间复杂性、空间复杂性时间复杂性、空间复杂性数值实验验证算法的正确性数值实验验证算法的正确性现在学习的是第9页，共55页10计算机解决实际问题的步骤建立数学模型建立数学模型构造或选择数值计算方法构造或选择数值计算方法编写程序上机计算编写程序上机计算获取近似解获取近似解对近似解进行误差分析对近似解进行误差分析现在学习的是第10页，共55页11近似计算的基本方法离散化离散化将求连续变量的问题转化为求离散变量的问题。将求连续变量的问题转化为求离散变量的问题。例如：求解例如：求解xy0abxixi+1第 i 个小区间的面积约等于：现在学习的是第11页，共55页12近似计算的基本方法（续）递推法递推法将将一一个个比比较较复复杂杂的的计计算算过过程程转转化化为为简简单单过过程程的的多多次重复。次重复。采用递推公式采用递推公式递推至递推至 k=n即可求出即可求出 pn(x)例如：计算多项式例如：计算多项式现在学习的是第12页，共55页13近似计算的基本方法（续）近似替代法近似替代法将将无无限限过过程程的的数数学学问问题题用用计计算算机机的的有有限限次次计计算算近近似替代。似替代。例如：例如：现在学习的是第13页，共55页14学习方法树立信心，克服树立信心，克服“怕怕”的思想；的思想；掌掌握握典典型型数数值值计计算算算算法法的的基基本本原原理理、适适用用范范围围、优缺点；优缺点；多多看看书书、多多思思考考、多多练练习习、及及时时复复习习，在在复复习习基础上做一定量的习题；基础上做一定量的习题；注重基本概念及基本方法，不要死记硬背；注重基本概念及基本方法，不要死记硬背；理论与实践相结合，常上机操作。理论与实践相结合，常上机操作。现在学习的是第14页，共55页15主要教学内容误差基本理论误差基本理论多项式插值方法多项式插值方法数值积分和数值微分数值积分和数值微分常微分方程的数值解法常微分方程的数值解法方程求根的数值解法方程求根的数值解法现在学习的是第15页，共55页16参考书目关关治治，陈陈景景良良.数数值值计计算算方方法法.清清华华大大学学出版社，出版社，1990 年年邓邓建建中中，刘刘之之行行.计计算算方方法法.西西安安交交通通大大学出版社，学出版社，2001 年年张张世世禄禄.计计算算方方法法.电电子子科科技技大大学学出出版版社社，2000 年年徐徐萃萃微微编编.计计算算方方法法引引论论（第第二二版版）.高高等教育出版社，等教育出版社，2002 年年现在学习的是第16页，共55页17考核方式出勤表现：出勤表现：10%作业或小测验：作业或小测验：10%上机实习：上机实习：10%闭卷期末考试：闭卷期末考试：70%共计：共计：100分分现在学习的是第17页，共55页18一误差基本理论误差的来源误差的来源绝对误差、绝对误差限绝对误差、绝对误差限有效数字有效数字相对误差、相对误差限相对误差、相对误差限算法运算的误差限算法运算的误差限近似计算应遵循的原则近似计算应遵循的原则若干值得注意的问题若干值得注意的问题现在学习的是第18页，共55页19生生产产实实践践和和科科学学研研究究中中，误误差差是是普普遍遍存存在在的的；数数值值计计算算方方法法的的立立足足点点是是允允许许有有误误差差，关关键键在在于于能否将误差控制在许可的范围内。能否将误差控制在许可的范围内。模型误差（忽略次要因素，简化问题）模型误差（忽略次要因素，简化问题）观测误差（测量器具的精度和观测手段有限）观测误差（测量器具的精度和观测手段有限）截断误差（计算机只能进行有限次运算）截断误差（计算机只能进行有限次运算）舍入误差（计算机对数据表示的限制）舍入误差（计算机对数据表示的限制）误差的来源现在学习的是第19页，共55页20误差的来源（续）现现 实实 世世 界界 研研究究对对象象测测量量数数据据数学模型数学模型的的 建建 立立计算方法计算方法的的 构构 造造数值运算数值运算的的 执执 行行测测量量误误差差模模型型误误差差截截断断误误差差舍舍入入误误差差结果结果结果结果现在学习的是第20页，共55页21绝对误差、绝对误差限将将某某个个研研究究量量的的准准确确值值记记为为 x，其其近近似似值值记记为为 x*。称称 x*与与 x 的差：的差：e e(x*)=)=x*-x为近似值为近似值 x*的的绝对误差，简称，简称误差绝对误差是有量纲的；绝对误差是有量纲的；绝绝对对误误差差可可为为正正，也也可可为为负负。e e(x*)0，称称x*是是x的的强强近似值，反之为近似值，反之为弱弱近似值；近似值；|e e(x*)|的的大大小小标标志志着着 x*的的精精确确度度；一一般般地地，在在同同一一量量的的不同近似值中，不同近似值中，|e e(x*)|越小则越小则 x*的精确度越高。的精确度越高。现在学习的是第21页，共55页22绝对误差、绝对误差限（续）|e e(x*)|=|x*-x|我们称我们称 为为 x*的的绝对误差限。由由于于准准确确值值 x 一一般般无无法法确确切切知知道道，因因此此绝绝对对误误差差的的准准确确值值也也不不能能求求出出。但但根根据据实实际际测测量量、计计算算的的情情况况可可以以事事先先估估计计出出绝绝对对误误差差绝绝对对值值的的上上界界。即即事事先先指指定定某某个个正正数数 ，使得：，使得：x 所在的范围所在的范围绝对误差限是绝对误差限是不唯一的不唯一的显然：显然：0且：且：x*-x x*+或：或：x=x*现在学习的是第22页，共55页23绝对误差、绝对误差限（续）例例如如：根根据据毫毫米米刻刻度度尺尺的的制制造造精精度度可可知知它它的的测测量量结果的绝对误差限不超过结果的绝对误差限不超过 0.5mm若若 x*和和 y*哪个更精确呢？哪个更精确呢？准确值分别是准确值分别是 18 和和 100 吗吗?12.3 mm12.8 mm现在学习的是第23页，共55页24有效数字定定义义：如如果果近近似似数数 x*的的绝绝对对误误差差限限不不大大于于 0.5 10-j则则称称近近似似数数 x*准准确确到到小小数数点点后后第第 j 位位，从从这这个个小小数数点点后后第第 j 位位数数字字直直到到最最左左边边第第一一个个非非 0 数数字字之之间间的的所所有有数数字字都都称称为为 x*的的有有效效数数字。字。x*的的有有效效数数字字位位数数为为 k+j 位位x*的绝对误差限不超过的绝对误差限不超过 xk+j 这一位单位的一半这一位单位的一半j 个个 0现在学习的是第24页，共55页25有效数字（续）一般地，将一般地，将 x*转化成为计算机浮点数的形式：转化成为计算机浮点数的形式：如果如果|e e (x*)|=)|=|x*-x|0.5 0.5 10m-l，其中：，其中：1 l n 则则 x*具有具有 l 位有效数字。位有效数字。规格化指 数现在学习的是第25页，共55页26有效数字（续）例：例：x=3.141592653，则近似数，则近似数现在学习的是第26页，共55页27有效数字（续）通通常常用用四四舍舍五五入入法法得得到到的的近近似似数数从从末末位位向向前前算算起起至至第一个非第一个非 0 数字均是有效数字。数字均是有效数字。有有效效数数字字越越多多，绝绝对对误误差差的的绝绝对对值值就就越越小小，计计算算结结果也越精确。果也越精确。0.001683 位有效数字位有效数字35.1855 位有效数字位有效数字精确到精确到 0.00135.18506 位有效数字位有效数字精确到精确到 0.0001现在学习的是第27页，共55页28有效数字（续）两类问题：两类问题：根据近似数的有效数字估算其绝对误差限。根据近似数的有效数字估算其绝对误差限。例如：例如：已知已知 x*=0.009876，因它有，因它有 4 位有效数字，则位有效数字，则现在学习的是第28页，共55页29有效数字（续）两类问题：两类问题：根据绝对误差限计算近似数的有效数字位数。根据绝对误差限计算近似数的有效数字位数。如果已知如果已知则近似数则近似数 x*有几位有效数字？有几位有效数字？例如：例如：已知已知则则 x*有有 8 位有效数字位有效数字如果如果现在学习的是第29页，共55页30相对误差、相对误差限绝绝对对误误差差限限并并不不能能完完全全反反映映出出两两个个不不同同近近似似值值的近似程度。的近似程度。这这里里 x*的的绝绝对对误误差差限限小小于于 y*的的绝绝对对误误差差限限，但但 400 m 作作为为 y 的的近近似似值值比比 0.4 m 作作为为 x 的的近近似似值值的的近近似似程程度更好。度更好。例如：例如：现在学习的是第30页，共55页31相对误差、相对误差限（续）相对误差相对误差：由于准确值由于准确值 x 一一般无法知道，在实际计算中可以取：般无法知道，在实际计算中可以取：相对误差相对误差可正可负可正可负现在学习的是第31页，共55页32相对误差、相对误差限（续）相对误差限相对误差限：相对误差的绝对值的上界：相对误差的绝对值的上界相对误差、相对误差限是无量纲的量。相对误差、相对误差限是无量纲的量。相相对对误误差差限限比比绝绝对对误误差差限限能能更更好好地地刻刻画画近近值值数数的的近似程度。近似程度。相对误差限相对误差限是不唯一的是不唯一的现在学习的是第32页，共55页33相对误差限与有效数字的关系证明：因为因为 x*有有 n 位有效数字，则位有效数字，则定理1.1 假设近似数假设近似数 ，其其中中 x1 0，x*的有效数字的位数为的有效数字的位数为 n，则，则 x*的相对误差限为：的相对误差限为：现在学习的是第33页，共55页34相对误差限与有效数字的关系（续）定理定理1 1.2 2 假设近似数假设近似数 ，其其中中 x1 0，x*的相对误差限为：的相对误差限为：证明证明：因为：因为则则 x*具有具有 n 位有效数字。位有效数字。现在学习的是第34页，共55页35相对误差限与有效数字的关系（续）即应取即应取 4 位有效数字，开方后的近似值的相对误差不超位有效数字，开方后的近似值的相对误差不超过过 0.1%例例：要要使使 的的相相对对误误差差不不超超过过 0.1%，应应取取几几位位有有效数字？效数字？解解：的的首首位位数数是是 x1=4，设设它它的的近近似似值值的的有有效效数数字字位数为位数为 n，则它的相对误差应满足：，则它的相对误差应满足：现在学习的是第35页，共55页36加减法的误差限现在学习的是第36页，共55页37加减法的误差限（续）现在学习的是第37页，共55页38同号同号异号异号异号，且两者的绝对值非常接近时异号，且两者的绝对值非常接近时非常大非常大现在学习的是第38页，共55页39乘法的误差限（续）现在学习的是第39页，共55页40除法的误差限（续）现在学习的是第40页，共55页41除法的误差限（续）当当除除数数绝绝对对值值较较小小时时，商商的的绝对误差的绝对值将非常大绝对误差的绝对值将非常大现在学习的是第41页，共55页42现在学习的是第42页，共55页43幂、对数的误差限请同学们自己推导请同学们自己推导现在学习的是第43页，共55页44近似计算应遵循的原则加减法加减法小小数数位位数数多多的的数数四四舍舍五五入入，并并且且比比小小数数位位数数少少的数多一位的数多一位运运算算结结果果保保留留的的小小数数位位数数与与原原近近似似数数中中小小数数位位数少者相同数少者相同小数点后有小数点后有 5 位位小数点后有小数点后有 3 位位结果：结果：现在学习的是第44页，共55页45近似计算应遵循的原则（续）乘除法各各因因子子保保留留的的位位数数比比有有效效数数字字位位数数最最少少的的因因子子的的位位数多一位数多一位运运算算结结果果的的有有效效数数字字位位数数与与有有效效数数字字位位数数最最少少的因子的位数相同的因子的位数相同4 位有效数字位有效数字2 位有效数字位有效数字结果：结果：现在学习的是第45页，共55页46近似计算应遵循的原则（续）幂运算幂运算运运算算结结果果保保留留的的有有效效数数字字位位数数与与原原近近似似数数的的有有效效数数字位数相同字位数相同3 位有效数字位有效数字结果：结果：对数运算运运算算结结果果保保留留的的有有效效数数字字位位数数与与原原近近似似数数中中真真数数的的有有效效数字位数相同数字位数相同4 位有效数字位有效数字结果：结果：现在学习的是第46页，共55页47近似计算应遵循的原则（续）中间运算结果中中间间结结果果所所保保留留的的位位数数应应比比上上述述原原则则中中提提及及的的位数多取一位位数多取一位最最后后一一次次计计算算时时，对对这这多多取取的的一一位位进进行行四四舍舍五五入入现在学习的是第47页，共55页48若干值得注意的问题防止两个相近的数相减两个相近的数相减两个相近的数相减,会使有效数字的位数严重损失，会使有效数字的位数严重损失，在在算法设计中算法设计中,若可能出现两个相近数相减若可能出现两个相近数相减,则改变计算公式，则改变计算公式，如使用三角变换、有理化等如使用三角变换、有理化等恒等恒等变换变换只有只有 2 位有效位有效数字了数字了现在学习的是第48页，共55页49若干值得注意的问题（续）避免除数的绝对值 被除数的绝对值除数稍有一点误差，则计算结果会出现较大变化除数稍有一点误差，则计算结果会出现较大变化现在学习的是第49页，共55页50若干值得注意的问题（续）防止大数“吃掉”小数在字长为在字长为8，基底为，基底为10的计算机上利用求根公式的计算机上利用求根公式机器吃了因此计算机求解的结果为：因此计算机求解的结果为：例例:方程的精确解为方程的精确解为现在学习的是第50页，共55页51若干值得注意的问题（续）实际编程应采用以下的公式：实际编程应采用以下的公式：符号函数符号函数现在学习的是第51页，共55页52若干值得注意的问题（续）简化计算步骤，减少运算次数 如秦九韶、高斯法、如秦九韶、高斯法、FFT 等等只需要只需要 14 次乘法，而不是次乘法，而不是 254 次乘法次乘法采用递推公式采用递推公式直接计算需要直接计算需要次乘法次乘法和和 n 次加法次加法只只需需要要 n 次次乘乘法法和和 n 次加法次加法现在学习的是第52页，共55页53若干值得注意的问题（续）现在学习的是第53页，共55页54若干值得注意的问题（续）乘法n=20加法n=20(1)n!(n-1)4.62 1019n!-12.43 1018(2)n!(e-1)4.18 1018n!-12.43 1018(3)(n-1)(n2+n+3)/32.68 103n(n-1)(2n-1)/62.47 103假假设设用用主主频频为为 2.8G 的的计计算算机机进进行行计计算算，并并假假设设该该计计算算机机每每秒执行秒执行 2.8 109 次乘法，则：次乘法，则：方法方法(1)需要：需要：523.2年年方法方法(2)需要：需要：47.3年年方法方法(3)需要：需要：0.96微秒微秒现在学习的是第54页，共55页55作业课本课本 P14：12357现在学习的是第55页，共55页