数值计算方法第一章

1、黑龙江科技大学黑龙江科技大学1数值计算方法徐 晶 理学院数学系理学院数学系Mobile :-mail: Office: 理学院数学系理学院数学系210黑龙江科技大学黑龙江科技大学2& 教材教材 (Text Book)数值计算方法数值计算方法 令锋令锋 傅守忠傅守忠 等编著等编著 （国防工业出版社）（国防工业出版社） & 参考书目参考书目 (Reference) 数值分析数值分析 王金铭王金铭 刘艳秋刘艳秋 陈欣陈欣 大连理工大学出版社大连理工大学出版社 数值分析数值分析 李庆扬李庆扬 王能超王能超 易大义易大义 华中科技大学出版社华中科技大学出版社 计

2、算方法典型例题与解法计算方法典型例题与解法 高培旺等高培旺等 国防科技大学出版社国防科技大学出版社 计算方法典型例题与分析计算方法典型例题与分析 孙守忠孙守忠 科学出版社科学出版社教材及参考书教材及参考书黑龙江科技大学黑龙江科技大学l微积分微积分l线性代数线性代数l常微分方程常微分方程lC C、C+C+语言语言预备知识预备知识黑龙江科技大学黑龙江科技大学教学进度教学进度课次课次 教学内容教学内容1 1第第1 1章章 数值计算方法概论数值计算方法概论2 22.12.1对分区间法对分区间法 2.22.2简单迭代法简单迭代法3 32.3 2.3 加速收敛迭代法加速收敛迭代法 2.42.4牛顿迭代法牛

3、顿迭代法 2.52.5正割法正割法4 43.1 Gauss3.1 Gauss列主元消去法列主元消去法5 53.2 LU3.2 LU分解法分解法 6 63.3 3.3 三对角方程组的追赶法三对角方程组的追赶法7 74.14.1向量范数与矩阵范数向量范数与矩阵范数 8 84.2 Jacobi4.2 Jacobi迭代法迭代法 4.3 Gauss-Seidel4.3 Gauss-Seidel迭代法迭代法9 94.4 4.4 迭代法的收敛性迭代法的收敛性 4.54.5逐次超松弛迭代法逐次超松弛迭代法10105.15.1代数插值法及其唯一性代数插值法及其唯一性 5.2 Lagrange5.2 Lagran

4、ge插值法插值法1111 5.3 Newton5.3 Newton插值法插值法 5.4 5.4 HermiteHermite插值法插值法1212 5.5 5.5 三次样条插值法三次样条插值法13135.65.6最小二乘拟合法最小二乘拟合法14146.16.1插值型求积公式插值型求积公式 6.26.2三个常用的求积公式及其误差三个常用的求积公式及其误差 15156.36.3复化求积公式复化求积公式16166.4 Romberg6.4 Romberg求积公式求积公式6.5 Gauss6.5 Gauss求积公式求积公式 6.66.6数值微分法数值微分法 17177.1 Euler7.1 Euler方

5、法方法 7.2 7.2 高阶高阶TaylorTaylor方法方法18187.3 7.3 Runge-KuttaRunge-Kutta法法 黑龙江科技大学黑龙江科技大学51. 闭卷考试占闭卷考试占60%2. 出勤占出勤占10%3. 测验及平时作业占测验及平时作业占30%成绩构成成绩构成黑龙江科技大学黑龙江科技大学 一、数值计算方法一、数值计算方法 能够做什么？黑龙江科技大学黑龙江科技大学263234323923zyxzyxzyx今有上禾三秉，中禾二秉，下禾一秉，今有上禾三秉，中禾二秉，下禾一秉，实三十九斗；实三十九斗； 上禾二秉，中禾三秉，下禾一秉，上禾二秉，中禾三秉，下禾一秉，实三十四斗；实三

6、十四斗； 上禾一秉，中禾二秉，下禾三秉，上禾一秉，中禾二秉，下禾三秉，实二十六斗。实二十六斗。问上、中、下禾实一秉各几何？问上、中、下禾实一秉各几何？答曰：上禾一秉九斗四分斗之一。中禾答曰：上禾一秉九斗四分斗之一。中禾一秉四斗四分斗之一。下禾一秉二斗四一秉四斗四分斗之一。下禾一秉二斗四分斗之三。分斗之三。-九章算术九章算术1 1、一个两千年前的例子、一个两千年前的例子黑龙江科技大学黑龙江科技大学nnnnnnaaaaaaaaa212222111211bxAnnbbbxxx2121黑龙江科技大学黑龙江科技大学2 2、天体力学中的、天体力学中的KeplerKepler方程方程x是行星运动的轨道，它是

7、时间是行星运动的轨道，它是时间t 的函数的函数.sin0,01xxt 黑龙江科技大学黑龙江科技大学全球定位系统：在地球的任何一个位置，至少可以同时收到4颗以上卫星发射的信号 3、全球定位系统（全球定位系统（Global Positioning System, GPS)Global Positioning System, GPS)黑龙江科技大学黑龙江科技大学02468051002468图 7.8HeightS6S3S4S2S1RS5N-S positions 表示地球上表示地球上一个接收点一个接收点R R的当前位的当前位置，卫星置，卫星S Si i的位置为的位置为 ，则得，则得到下列非线性方程组

8、到下列非线性方程组( , , , )x y z t(,)iiiixyzt222111122222222223333222444422255552226666()()()(t -t)0()()()(t -t)0()()()(t -t)0()()()(t -t)0()()()(t -t)0()()()(t -t)xxyyzzcxxyyzzcxxyyzzcxxyyzzcxxyyzzcxxyyzz0c黑龙江科技大学黑龙江科技大学11221212( ,)0( ,)0( ,)0nnnnf x xxfx xxfx xx( )0F x 记为记为其中，其中，:,nnF DRR12( ,)Tnxx xx黑龙江科技

9、大学黑龙江科技大学4 4、已经测得在某处海洋不同深度处的水温如下：、已经测得在某处海洋不同深度处的水温如下：深度（深度（M M） 466 741 950 1422 1634466 741 950 1422 1634水温（水温（o oC C）7.04 4.28 3.40 2.54 2.137.04 4.28 3.40 2.54 2.13根据这些数据，希望合理地估计出其它深度（如根据这些数据，希望合理地估计出其它深度（如500500米，米，600600米米，10001000米米）处的水温）处的水温. .黑龙江科技大学黑龙江科技大学5、人口预测 下面给出的是中国下面给出的是中国19001900年到年

10、到20002000年的人口数，年的人口数，我们的目标是预测未来我们的目标是预测未来的人口数（数据量较大时）的人口数（数据量较大时）19505519619606620719708299219809870519901143332000126743432231ttty黑龙江科技大学黑龙江科技大学黑龙江科技大学黑龙江科技大学6、铝制波纹瓦的长度问题 建筑上用的一种铝制波纹瓦是用一种机器建筑上用的一种铝制波纹瓦是用一种机器将一块平整的铝板压制而成的将一块平整的铝板压制而成的. .假若要求波纹瓦长假若要求波纹瓦长4 4英尺英尺, ,每个波纹的高度每个波纹的高度( (从从中心线中心线) )为为1 1英寸英寸

11、, ,且每个波纹以近似且每个波纹以近似2 2英寸英寸为一个周期为一个周期. . 求制做一块波纹瓦所需铝板的求制做一块波纹瓦所需铝板的长度长度L.L.黑龙江科技大学黑龙江科技大学 这个问题就是要求由函数这个问题就是要求由函数给定的曲线从给定的曲线从x x=0=0到到x=48=48英寸间的弧长英寸间的弧长L. . 由微积分学我们知道由微积分学我们知道, ,所求的弧长可表示为所求的弧长可表示为: :xxxxfLd)(cos1d)(148024802 上述积分称为第二类椭圆积分上述积分称为第二类椭圆积分, ,它不能用普它不能用普通方法来计算通方法来计算.黑龙江科技大学黑龙江科技大学计算机辅助设计：计算

12、机辅助设计：波音波音777应用三维立应用三维立体建模，数字化设计与有限元计算的体建模，数字化设计与有限元计算的第一架喷气客机。第一架喷气客机。天气预报：天气预报：计算能力的发展将把海洋、大气和生态系计算能力的发展将把海洋、大气和生态系统的综合知识融合成一个气象变化模型。统的综合知识融合成一个气象变化模型。医学与生物工程：医学与生物工程：CT、核磁共振与核磁共振与 Radon 变换；至病基因与药物设计；人变换；至病基因与药物设计；人造生物材料的彷真响应；传染病动力学造生物材料的彷真响应；传染病动力学模型。模型。现代科学计算在工程计算中的应用现代科学计算在工程计算中的应用黑龙江科技大学黑龙江科技大

13、学电子系统自动化设计电子系统自动化设计：大规模集成电路的设计与逻辑检测。大规模集成电路的设计与逻辑检测。材料设计材料设计：性能设计的大规模计算与模拟：设计用性能设计的大规模计算与模拟：设计用于生产新的高热值、高压材料中的化学于生产新的高热值、高压材料中的化学蒸发沉淀反应器。蒸发沉淀反应器。车辆与道路工程设计与模拟车辆与道路工程设计与模拟：车辆与道路相互作用综合系统设计。车辆与道路相互作用综合系统设计。黑龙江科技大学黑龙江科技大学存储与物流系统：存储与物流系统：工农业发展使得产品的存储、交流和时效工农业发展使得产品的存储、交流和时效性极大提高；废物和垃圾问题成为城市生性极大提高；废物和垃圾问题成

14、为城市生活的重大问题。规划计算和系统分析成为活的重大问题。规划计算和系统分析成为常用计算方法。常用计算方法。燃烧与爆炸工程：燃烧与爆炸工程：燃烧对环境的影响；计算流体力学燃烧对环境的影响；计算流体力学与爆炸工程。与爆炸工程。网络设计与计算：网络设计与计算：搜索引擎的设计搜索引擎的设计航空航天工程：航空航天工程：神州飞船系列神州飞船系列信息与通信工程：信息与通信工程：GPS卫星导航卫星导航黑龙江科技大学黑龙江科技大学黑龙江科技大学黑龙江科技大学理论研究理论研究科学实验科学实验科学计算科学计算计算数学计算数学诺贝尔奖得主诺贝尔奖得主, ,计算物理学家计算物理学家 WilsonWilson提出提出

15、现代科学研究的三大支柱现代科学研究的三大支柱黑龙江科技大学黑龙江科技大学 科学方法论的巨大变革科学方法论的巨大变革： 如果说如果说伽利略伽利略和牛顿和牛顿在科学发展史上奠定了实验和理论这在科学发展史上奠定了实验和理论这两大科学方法的支柱，那么由两大科学方法的支柱，那么由冯冯.诺依曼诺依曼研制研制的现代电子计算机把计算推上了人类科学活的现代电子计算机把计算推上了人类科学活动的前沿，使计算成为动的前沿，使计算成为第三种方法第三种方法。黑龙江科技大学黑龙江科技大学黑龙江科技大学黑龙江科技大学建立数学模型选取计算方法编写上机程序计算得出结果黑龙江科技大学黑龙江科技大学数值计算方法是计算数学的一个主要组

16、成部分，数值计算方法是计算数学的一个主要组成部分，“什么是什么是数值计算方法？数值计算方法？”它主要研究使用计算机求解各种科学与工程计算它主要研究使用计算机求解各种科学与工程计算问题的数值方法（近似方法）问题的数值方法（近似方法）;对求得的解的精对求得的解的精度进行评估以及在计算机上实现求解等。度进行评估以及在计算机上实现求解等。 数值计算方法已经成为计算机处理实际问题的数值计算方法已经成为计算机处理实际问题的一个重要手段，从宏观天体运动学到微观分子细一个重要手段，从宏观天体运动学到微观分子细胞学，从工程系统到社会经济系统，无一能离开胞学，从工程系统到社会经济系统，无一能离开数值计算方法。因此

17、，数值计算与计算机模拟被数值计算方法。因此，数值计算与计算机模拟被称为称为“第三种科学研究方法第三种科学研究方法”。黑龙江科技大学黑龙江科技大学黑龙江科技大学黑龙江科技大学分形图分形图混沌图混沌图黑龙江科技大学黑龙江科技大学1、数值逼近数值逼近 插值与拟合、插值与拟合、FFT、数值积分与微分、数值积分与微分2、数值代数、数值代数 代数基础、线性代数方程组的解法、非线性代数方代数基础、线性代数方程组的解法、非线性代数方程（组）的解法、特征值与特征向量程（组）的解法、特征值与特征向量3、微分方程数值解、微分方程数值解 ODE、PDE和有限元法和有限元法4、最优化方法、最优化方法* 无约束优化与约束

18、优化方法无约束优化与约束优化方法 融进了机器学习计算、仿生计算、网络计算、以数据为核融进了机器学习计算、仿生计算、网络计算、以数据为核心的计算和各种普适计算、非线性科学计算等内容。心的计算和各种普适计算、非线性科学计算等内容。传统的数值计算的主要研究内容传统的数值计算的主要研究内容现代计算方法：现代计算方法：黑龙江科技大学黑龙江科技大学数值计算方法的主要特点数值计算方法的主要特点借助计算机提供切实可行的数学算法借助计算机提供切实可行的数学算法.想想的精确度的精确度; ;收敛且稳定收敛且稳定; ;误差可以分析或估计误差可以分析或估计. .所提出的算法必须具有：可靠的理论分析所提出的算法必须具有：

19、可靠的理论分析; ;理理时间复杂性好时间复杂性好_指节省时间；指节省时间；空间复杂性好空间复杂性好_指节省存储量。指节省存储量。计算复杂性好计算复杂性好 通过数值实验证明算法行之有效通过数值实验证明算法行之有效. .黑龙江科技大学黑龙江科技大学F采用采用“近似替代近似替代”方法方法逼近逼近F采用采用“构造性构造性”方法方法F采用采用“离散化离散化”方法方法 把求连续变量的问题转化为求离散变量的问题把求连续变量的问题转化为求离散变量的问题F采用采用“递推化递推化”方法方法 复杂的计算归结为简单过程的多次重复，易复杂的计算归结为简单过程的多次重复，易于用循环结构来实现（迭代法）。于用循环结构来实现

20、（迭代法）。F采用各种采用各种搜索搜索方法方法构造数值算法的主要手段构造数值算法的主要手段黑龙江科技大学黑龙江科技大学 希希 望：望： 求近似解，但方法简单可行，行之有效求近似解，但方法简单可行，行之有效 （计算量小，误差小（计算量小，误差小, ,需存储单元少需存储单元少等）等）, , 以计算机为工具，易在计算机上实现。以计算机为工具，易在计算机上实现。 计算机运算计算机运算: : 只能进行加，减，乘，除等算术运算和一只能进行加，减，乘，除等算术运算和一 些逻辑运算。些逻辑运算。 数值计算方法：数值计算方法： 把求解数学问题转化为按一定次序只进行把求解数学问题转化为按一定次序只进行 加，减，乘

21、，除等基本运算加，减，乘，除等基本运算. .设计数值算法的出发点？设计数值算法的出发点？黑龙江科技大学黑龙江科技大学三、如何学好数值计算方法？三、如何学好数值计算方法？黑龙江科技大学黑龙江科技大学hhhhhhhhhhhhhgggg几点纪律要求几点纪律要求上课至少提前上课至少提前2分钟到教室，不早退分钟到教室，不早退上课期间手机静音上课期间手机静音 课课前预前预习，课习，课后复后复习习，及时解决存在的问题，及时解决存在的问题课堂上认真听讲，适当记笔记，积极回答问题课堂上认真听讲，适当记笔记，积极回答问题作业独立完成，保质保量按时上交作业独立完成，保质保量按时上交有事提前请假，否则，记无故旷课有事

22、提前请假，否则，记无故旷课黑龙江科技大学黑龙江科技大学威尔金森威尔金森（James Hardy .Wilkinson，1919-1986） Wilkinson是数值分析和数值计算的是数值分析和数值计算的开拓者和奠开拓者和奠基人基人。1940 年，开始研究弹道的数学模型与数年，开始研究弹道的数学模型与数值计算。值计算。 1946 年成为年成为Turing 的助手，协助设计的助手，协助设计 Pilot ACE 计算机。计算机。1969年他当选为英国皇家学年他当选为英国皇家学会院士；会院士；1970年工业和应用数学会年工业和应用数学会(s1am)授予他授予他冯冯诺伊曼奖；诺伊曼奖；1987年他获得美

23、国数学会的年他获得美国数学会的chauvenet奖。著名的美国阿尔贡国家实验室曾奖。著名的美国阿尔贡国家实验室曾聘威尔金森为荣誉高级研究员并两次向他授奖。聘威尔金森为荣誉高级研究员并两次向他授奖。 Wilkinson在数值分析研究领域作出了杰出贡献，是数值计算在数值分析研究领域作出了杰出贡献，是数值计算的早期开拓者，其工作加速了数字计算机的早期开拓者，其工作加速了数字计算机 ( 在科学计算中在科学计算中 ) 的的使用。他研究的主要问题是线性代数方程组和矩阵特征值问题使用。他研究的主要问题是线性代数方程组和矩阵特征值问题的数值解法，特别是他的向后误差分析法的数值解法，特别是他的向后误差分析法 (

24、backward error analysis)的创造性工作奠定了数值分析和数值计算早期的理论的创造性工作奠定了数值分析和数值计算早期的理论基础。基础。 1975 年年 J. H. Wilkinson成为第五位图灵奖获得者。成为第五位图灵奖获得者。黑龙江科技大学黑龙江科技大学36l用计算机进行实际问题的数值计算时，往往求用计算机进行实际问题的数值计算时，往往求得是问题的得是问题的近似解近似解，都存在误差。，都存在误差。l误差公理：误差公理：任何测量（观测）都存在误差。任何测量（观测）都存在误差。l误差是不可避免的，即要误差是不可避免的，即要允许允许误差，又要误差，又要控制控制误差。误差。黑龙江

25、科技大学黑龙江科技大学一、一、误差的来源与分类误差的来源与分类 从实际问题中抽象出数学模型从实际问题中抽象出数学模型 模型误差模型误差 Model Error 例例: :质量为质量为m的物体，在重力作用下的物体，在重力作用下, ,自由下落，自由下落， 其下落距离其下落距离s与时间与时间t 的关系是：的关系是： mgtsm 22dd其中其中 g 为重力加速度。为重力加速度。黑龙江科技大学黑龙江科技大学 通过测量得到模型中参数的值通过测量得到模型中参数的值 观测误差观测误差Observation Error 截断误差截断误差 方法误差方法误差 Truncation Error例如，当函数例如，当函

26、数 f x 用用TaylorTaylor多项式多项式 ( )200001!2!nnnfffPxfxxxn 近似代替时，数值方法的截断误差是近似代替时，数值方法的截断误差是 (1)1(1)!nnnnfRxf xPxxn 与与0 0之间。之间。在在x黑龙江科技大学黑龙江科技大学舍入误差舍入误差 Round-off Error 用计算机、计算器和笔算，都只能用有限位用计算机、计算器和笔算，都只能用有限位 = 3.1415926 小数来代替无穷小数或用位数较少的小数来小数来代替无穷小数或用位数较少的小数来代替位数较多的有限小数，如：代替位数较多的有限小数，如：10.33333黑龙江科技大学黑龙江科技大

27、学四舍五入后四舍五入后0000074. 01416. 31000033. 0333. 0312在数值计算方法中，主要研究在数值计算方法中，主要研究和和（包括初始数据的误差）对计算结果的影响！（包括初始数据的误差）对计算结果的影响！黑龙江科技大学黑龙江科技大学二、二、 误差的概念误差的概念1、绝对误差、绝对误差 Absolute Error是近似值是近似值 的的, ,简称为简称为。 *x*( )aExxx若若 近似值偏大，称近似值偏大，称“强近似强近似”或或“盈近盈近似似”若若 近似值偏小，称近似值偏小，称“弱近似弱近似”或或“亏近亏近似似”0)(xEa0)(xEa注注 越小，越小， 精度越高；

28、精度越高；aE*x定义定义1-11-1：设设 是准确值，是准确值， 为为 的一个近似值，的一个近似值，称称 x*xx xx黑龙江科技大学黑龙江科技大学例例1、用毫米刻度尺测量长度为用毫米刻度尺测量长度为 的物体，测得其长度的物体，测得其长度为为 ，是物体实际长度的一个近似值，由于，是物体实际长度的一个近似值，由于直尺以毫米直尺以毫米为为刻度，故误差不超过半个毫米，则有：刻度，故误差不超过半个毫米，则有：mmx123*xmmxxx21123*5 .1235 .122 x5 . 0123xscmc/10997925. 210*scmc/10)000001. 0997925. 2(10scm/100

29、00001. 010*通常记为：通常记为：绝对误差限绝对误差限 例例2 2、真空中光速真空中光速c c的近似值为的近似值为mmx123*x例例1、用毫米刻度尺测量长度为用毫米刻度尺测量长度为 的物体，测得其长度的物体，测得其长度为为 ，是物体实际长度的一个近似值，由于，是物体实际长度的一个近似值，由于直尺以毫米直尺以毫米为为刻度，故误差不超过半个毫米，则有：刻度，故误差不超过半个毫米，则有：mmx123*x黑龙江科技大学黑龙江科技大学axx*x因准确值因准确值 往往无法知道，只能估计：往往无法知道，只能估计：x*aaExx（上界）（上界） 叫做叫做 的的绝对误差限绝对误差限。a*xx,*aax

30、x黑龙江科技大学黑龙江科技大学44 例如，有两个量例如，有两个量 ， 110 x,51000y*10,1;xax则则*1000,5.yay虽然虽然 比比 大大4 4倍，倍，xaya但但/*5/1000yay%5.0比比 / *1/10 xax%10 所以除考虑误差的大小外，还应考虑准确值所以除考虑误差的大小外，还应考虑准确值 本身的大本身的大小小. . x要小得多，这说明要小得多，这说明 近似近似 的程度比的程度比 近似近似 的程度好的程度好. .*yy*xx黑龙江科技大学黑龙江科技大学45定义定义1-21-2：相对误差相对误差 *arExxExx实际计算中，常用下式代替：实际计算中，常用下式

31、代替：*arExxExx2、相对误差：相对误差： Relative Error因实际误差因实际误差 未知，常采用：未知，常采用：相对误差限相对误差限aEr*( )rrxxE xx*arx 近似值的误差近似值的误差 与准确值与准确值x的比值的比值 aE黑龙江科技大学黑龙江科技大学46p 定义定义1-31-3：若近似值：若近似值 的误差限是某一位的半个单位，的误差限是某一位的半个单位， 该位到该位到 的第一位非零数字共有的第一位非零数字共有 位，就说位，就说 有有 位位有效数字有效数字。*x*xn*xn例例1433.x* 231021 * 3 n141635.x* 451021 * 5 n意义：意

32、义：有效数字越多，误差限越小，数值越准确。有效数字越多，误差限越小，数值越准确。3 、有效数字有效数字 significant digits 如果一个近似数的所有数字均为如果一个近似数的所有数字均为。黑龙江科技大学黑龙江科技大学47则则 有有 位有效数字，精确到位有效数字，精确到 。p 类似类似科学计数法科学计数法*xk*120.10nmxa aa 式中式中, (, (小数点后小数点后1 1位）；位）；01 ana,a2可以为零；可以为零； 为整数。为整数。n*1102m kxx如果如果10m k黑龙江科技大学黑龙江科技大学48 有效数字与相对误差的关系有效数字与相对误差的关系FF 有效数字有

33、效数字 相对误差限相对误差限11121102102101001050* nnmnnmra.aaa.a.x*已知已知 x* 有有 n 位位有效数字有效数字，则其，则其相对误差限相对误差限为为FF 相对误差限相对误差限 有效数字有效数字nmmnmnr.aaa.aaxxx 105010)1()1(210100)1(210|*|*|*|111121111110)1(21* nra已知已知 x* 的的相对误差限相对误差限可写为可写为则则可见可见 x* 至少至少有有 n 位位有效数字有效数字。黑龙江科技大学黑龙江科技大学Th1.2Th1.2： *1210.10mnnxx xx x设设反之反之, ,若若 的

34、相对误差的绝对值大于的相对误差的绝对值大于 ，*x1102n其中其中 为整数为整数, , 为正整数为正整数, , 。n10 x m有有 位有效数字。位有效数字。n则则 至至多多*x若若 至多有至多有 位有效数字位有效数字, ,即即 是有效数字是有效数字, ,nx*xn而而 不是有效数字不是有效数字, ,1nx则则 的相对误差的绝对值必大于的相对误差的绝对值必大于 ; ;11102n *x黑龙江科技大学黑龙江科技大学证明：证明：1nx不是有效数字不是有效数字 反之反之,若若 则则 *1102nrxxx *rxxx 1*1102m nx 1110210m nm 11102n *1102nxxx11

35、10102nm11102m n 11102mn1nx不是有效数字，不是有效数字， 即即 至多有至多有 位有效数字位有效数字. *xn黑龙江科技大学黑龙江科技大学51 例例 为使为使 的相对误差小于的相对误差小于0.001%, ,至少应取几位有效数字？至少应取几位有效数字？*解解 假设假设 * 取到取到 n 位有效数字，则其相对误差上限为位有效数字，则其相对误差上限为111021* nra要保证其相对误差小于要保证其相对误差小于0.001%，只要保证其上限满足，只要保证其上限满足%001.01021*11 nra已知已知 a1 = 3，则从以上不等式可解得，则从以上不等式可解得 n 6 log6

36、，即，即 n 6，应取，应取 * = 3.14159。黑龙江科技大学黑龙江科技大学52注意：注意： 准确值经准确值经“四舍五入四舍五入”后，都为有效数字；后，都为有效数字； 有效数字位数相同，误差可能不同；有效数字位数相同，误差可能不同；*112345,x *212.345,x 5 51102a2 51102a例如：例如：但但 相同时，有效位数越多，误差越小。相同时，有效位数越多，误差越小。m 移动小数点时，不要改变有效数字；移动小数点时，不要改变有效数字；例如：例如：210032020300 . 常数、系数、准确数有无数多个有效数字。常数、系数、准确数有无数多个有效数字。例如：例如： ， ，

37、 ， 331黑龙江科技大学黑龙江科技大学53按四舍五入原则写出下列各数具有按四舍五入原则写出下列各数具有5 5位有效数字的位有效数字的近似数：近似数：解：解：按定义，按定义，187.93, 187.93, 的的5 5位有效数字近似数是位有效数字近似数是8.00008.0000，而不是，而不是8 8，000033.8x例例187.9325, 0.03785551, 8.000033, 2.7182818. 187.9325, 0.03785551, 8.000033, 2.7182818. 上述各数具有上述各数具有5 5位有效数字的近似数分别是位有效数字的近似数分别是因为因为8 8只有只有1 1

38、位有效数字位有效数字. .注意：注意：0.037856, 0.037856, 8.0000, 8.0000, 2.7183.2.7183.黑龙江科技大学黑龙江科技大学54加、减、乘、除运算的误差为：加、减、乘、除运算的误差为： 4、 数值运算的误差估计数值运算的误差估计121212122111122222()()(); ()()();1E xxE xE xE x xx E xx E xxxEE xE xxxx （避免绝对值很大的数为乘数）（避免绝对值很大的数为乘数）（避免（避免 为很小的数为除数）为很小的数为除数） 2x（避免两相近数相减运算（避免两相近数相减运算）12121212121212

39、12121212121122rrrrrrrrrrrrxxExxExExxxxxxxExxExExxxxxExxExExxEExExx黑龙江科技大学黑龙江科技大学5、函数的误差估计、函数的误差估计当自变量有误差时，计算函数值也会产生误差，其当自变量有误差时，计算函数值也会产生误差，其误差限可利用函数的误差限可利用函数的TaylorTaylor展开式进行估计。展开式进行估计。设设 是一元函数，是一元函数， 的近似值为的近似值为 , ,以以 近近似似 ，其误差限记作，其误差限记作 ，可用，可用TaylorTaylor展开展开 f xx*x*f x f x*f x 2*2ff xf xfxxxxx*,

40、 x x *2*2ff xf xfxxx黑龙江科技大学黑龙江科技大学假定假定 与与 的比值不太大的比值不太大,可忽略可忽略 的高的高阶项阶项, ,于是可得计算函数的误差限为于是可得计算函数的误差限为 *f x *fx*x *f xfxx 当当 为多元函数时计算为多元函数时计算 , ,如果如果f12,nAf x xx12,nx xx的近似值为的近似值为 , ,则则 的近似为的近似为*12,nx xxA*12,nAf xxx于是函数值于是函数值 的误差的误差 由由TaylorTaylor展开展开, ,*A*e A *f x *fx*x假定假定 与与 的比值不太大的比值不太大,可忽略可忽略 的高的高

41、阶项阶项, ,于是可得计算函数的误差限为于是可得计算函数的误差限为 *f x *fx*x黑龙江科技大学黑龙江科技大学*1;nkkkfAxx*A*1.kkrrkkAxfAxAA *1212,nne AAAf x xxf x xx*12*11,nnnkkkkkkkf x xxfxxexx黑龙江科技大学黑龙江科技大学l*110lmd*80dm*0.2llm*0.1ddmSld *,SSSldld*80 ,110 ,SSdmlmld,SSSlddlld黑龙江科技大学黑龙江科技大学 *0.2 ,0.1 ,lmdm*2280 0.2 110 0.127;Smm*270.31.8800rSSSl dS黑龙江

42、科技大学黑龙江科技大学 数值计算在设计算法时首先关心的是由它产数值计算在设计算法时首先关心的是由它产生的计算结果的稳定性，而算法的稳定性与舍生的计算结果的稳定性，而算法的稳定性与舍入误差是否增长密切相关。一个算法如果输入入误差是否增长密切相关。一个算法如果输入数据有微小扰动（即误差），而在计算过程中数据有微小扰动（即误差），而在计算过程中舍入误差不增长，则称此算法是舍入误差不增长，则称此算法是数值稳定的数值稳定的，否则称其为否则称其为数值不稳定。数值不稳定。 黑龙江科技大学黑龙江科技大学61（3 3）不在计算机数系中的数做四舍五入处理。）不在计算机数系中的数做四舍五入处理。例例 在四位浮点十进

43、制数的计算机上计算在四位浮点十进制数的计算机上计算1+ 104 （1 1）加法先对阶）加法先对阶, ,后运算后运算, ,再舍入；再舍入；（2 2）乘法先运算）乘法先运算, ,再舍入；再舍入；= 0.1000 105 = 104 = 0.10001 105 = 0.00001 105+0.1000 105 ( (对阶对阶，靠高阶靠高阶) )解解 1+ 104 =0.1000 101 +0.1000 105 ( (浮点数形式浮点数形式) )( (运运算算) )( (舍入舍入) )计算机中数的计算特点计算机中数的计算特点黑龙江科技大学黑龙江科技大学例：求定积分的值例：求定积分的值. 10(0,1,2

44、,8)5nnxIdx nx解：解：直接积分可产生递推公式直接积分可产生递推公式若取初值若取初值)2 . 1ln(5ln6lnd51100 xxI)1(51d5551101 nnnInxxxxI黑龙江科技大学黑龙江科技大学可得递推公式可得递推公式)8, 2, 1(,51)2 . 1ln(10nInIInn按公式就可以逐步算出按公式就可以逐步算出101 50.09II 05. 052112II083. 053123II165. 054134II025. 155145II952. 456156II注意此公式注意此公式精确精确成成立，且立，且What happened?!不稳定的算法不稳定的算法 ！0

45、nI 黑龙江科技大学黑龙江科技大学NYBJ蝴蝶效应蝴蝶效应 纽约的一只蝴蝶翅膀一拍，风和日丽纽约的一只蝴蝶翅膀一拍，风和日丽的北京就刮起台风来了？！的北京就刮起台风来了？！这是一个这是一个病态问题病态问题黑龙江科技大学黑龙江科技大学由题设中的递推公式（由题设中的递推公式（1 1）可看出，）可看出， 的误差扩大了的误差扩大了1nI5 5倍后传给倍后传给 ，因而初值，因而初值 的误差对以后各步的误差对以后各步nI0I这就造成这就造成 的计算结果的计算结果严重失真。严重失真。4I计算结果的影计算结果的影响，随着响，随着 的增大愈来愈严重。的增大愈来愈严重。n黑龙江科技大学黑龙江科技大学可求得可求得I

46、9 0.017，按改写后的公式可逐次求得按改写后的公式可逐次求得不妨设不妨设I9 I10，于是由于是由10951501II) 1 , 1,( 51511nnkIkIkknIInn151将将公式公式变为变为黑龙江科技大学黑龙江科技大学I8 0.019 I7 0.021I6 0.024 I8 0.028I4 0.034 I3 0.043I2 0.058 I1 0.088I0 0.182 稳定的算法稳定的算法 ！ 在我们今后的讨论中，在我们今后的讨论中，误差误差将不可回避，将不可回避， 算法的算法的稳定性稳定性会是一个非常重要的话题。会是一个非常重要的话题。黑龙江科技大学黑龙江科技大学注：注：递推公

47、式递推公式(1)的舍入误差以的舍入误差以5的幂次增长进的幂次增长进行传播，因此是行传播，因此是数值不稳定的，数值不稳定的，而递推公式而递推公式(2)的舍入误差在一定范围内以的舍入误差在一定范围内以0.2的幂次进行传的幂次进行传播，随着播，随着n的增大，误差逐步减少，因此该算的增大，误差逐步减少，因此该算法是法是数值稳定的数值稳定的。 因此，可以看出数值不稳定的算法是不能使因此，可以看出数值不稳定的算法是不能使用的，实际计算中对任何输入数据都是数值稳定用的，实际计算中对任何输入数据都是数值稳定的算法，称为的算法，称为无条件稳定。无条件稳定。而对某些数据数值稳而对某些数据数值稳定，对其它数据数值不

48、稳定的算法，称为定，对其它数据数值不稳定的算法，称为条件稳条件稳定定。黑龙江科技大学黑龙江科技大学1. 1. 简化计算步骤，避免误差积累。简化计算步骤，避免误差积累。一般来说，计算机处理下列运算的速度为一般来说，计算机处理下列运算的速度为 exp ,例：例：多项式求值：给定的多项式求值：给定的 x 求下列求下列n次多项式的值。次多项式的值。 nnxaxaxaaxP2210)(解：解：1. 1. 用一般算法，即直接求和法；用一般算法，即直接求和法； 2. 2. 逐项求和法；逐项求和法；3. 3. 秦九韶方法秦九韶方法( (即即HornorHornor算法）；算法）；黑龙江科技大学黑龙江科技大学

49、先计算先计算x2, x3, , xn, 再作线性组合，需做再作线性组合，需做2n-1次次乘法和乘法和n次次加法。加法。解法一：解法一：直接求和法直接求和法解法二：逐项求和法解法二：逐项求和法 按顺序依次计算每一项的值再求和，需做按顺序依次计算每一项的值再求和，需做n(n+1)/2次次乘法和乘法和n次次加法。加法。黑龙江科技大学黑龙江科技大学解法三：秦九韶算法（即解法三：秦九韶算法（即Horner算法）算法）1210( )()nnnp xa xaxaxa xa只需做只需做n次次乘法和乘法和n次次加法。且可以递推实现。加法。且可以递推实现。01,1,2,niin ivavv x ain好处：好处：

50、 节省计算时间；节省计算时间； 减少舍入误差。减少舍入误差。黑龙江科技大学黑龙江科技大学2. .要避免两个相近的数相减要避免两个相近的数相减在数值计算中，两个相近的数作减法时有效数在数值计算中，两个相近的数作减法时有效数字会损失。字会损失。例例: 求求xxy1的的值。值。当当x = 1000，y 的准确值为的准确值为0.01580 放大相对误差限，导致计算结果有较大误差！放大相对误差限，导致计算结果有较大误差！黑龙江科技大学黑龙江科技大学类似地类似地 yxyxlnlnln2sin2cos2sin)sin(xxx(2) 若若将将原式原式改写为改写为xxxxy111则则 y = 0.0158102

51、. 062.3164.3110001001y(1)直接相减直接相减有有3 3位有效数字！位有效数字！只有只有1位有效数字位有效数字 .6121112xxxex当当 | x | 1 时：时：;2sin2cos12xx 黑龙江科技大学黑龙江科技大学3.尽量避免绝对值太小的数作分母尽量避免绝对值太小的数作分母例：例：2 .2718001. 07182. 2如分母变为如分母变为0.0011，也即分母只有，也即分母只有0.0001的变化时的变化时1 .24710011. 07182. 22718.22471.1247.1黑龙江科技大学黑龙江科技大学4. 避免大数避免大数吃吃小数小数精确解为精确解为110

52、291 x,x 算法算法1 1：利用求根公式：利用求根公式aacbbx242010) 110(992xx黑龙江科技大学黑龙江科技大学在计算机内，在计算机内，109存为存为0.1 1010，1存为存为0.1 101。做做加法时，两加数的指数先向大指数对齐，再将浮加法时，两加数的指数先向大指数对齐，再将浮点部分相加。即点部分相加。即1 的指数部分须变为的指数部分须变为1010，则：，则：1 = 0.0000000001 1010，取单精度时就成为：，取单精度时就成为： 109+1=0.10000000 1010+0.00000000 1010=0.10000000 1010024,102422921aacbbxaacbbx黑龙江科技大学黑龙江科技大学算法算法2 2：先解出先解出9211024)( aacbbsignbx再利用再利用11010991221 xacxacxx求和时从小到大相加，可使和的误差减小。求和时从小到大相加，可使和的误差减小。例：例：按从小到大、以及从大到小的顺序分别计算按从小到大、以及从大到小的顺序分别计算1 + 2 + 3 +