数值分析：第一章绪论.ppt

武汉大学数学与统计学院武汉大学数学与统计学院邓爱姣邓爱姣Email:第一章第一章 绪论绪论第二章方程第二章方程求根求根第三章线性方程组第三章线性方程组的的解法解法第四章插值方法第四章插值方法第五章数值积分第五章数值积分第六章常微分方程的数值解第六章常微分方程的数值解本课程的主要内容本课程的主要内容1.1 1.1 计算方法概论计算方法概论第一章第一章:绪论绪论计算方法数值算法：计算方法数值算法：利用计算机求解数学问题近似解的方法。利用计算机求解数学问题近似解的方法。步骤：步骤：实际问题建立数学模型提供计算方法实际问题建立数学模型提供计算方法设计程序上机计算获取近似结果设计程序上机计算获取近似结果数值分析数值分析 能够做什么？研究使用计算机求解各种科学与工程研究使用计算机求解各种科学与工程计算问题的数值方法（近似方法），对计算问题的数值方法（近似方法），对求得的解的精度进行评估，以及如何在求得的解的精度进行评估，以及如何在计算机上实现求解等。计算机上实现求解等。数值分析课程中所讲述的各种数值方数值分析课程中所讲述的各种数值方法在科学与工程计算、信息科学、管理法在科学与工程计算、信息科学、管理科学、生命科学等交叉学科中有着广泛科学、生命科学等交叉学科中有着广泛的应用的应用应用问题举例1、一个两千年前的例子今有上禾三秉，中禾二秉，下禾一秉，今有上禾三秉，中禾二秉，下禾一秉，实三十九斗；实三十九斗；上禾二秉，中禾三秉，下禾一秉，上禾二秉，中禾三秉，下禾一秉，实三十四斗；实三十四斗；上禾一秉，中禾二秉，下禾三秉，上禾一秉，中禾二秉，下禾三秉，实二十六斗。实二十六斗。问上、中、下禾实一秉各几何？问上、中、下禾实一秉各几何？答曰：上禾一秉九斗四分斗之一。中禾答曰：上禾一秉九斗四分斗之一。中禾一秉四斗四分斗之一。下禾一秉二斗四一秉四斗四分斗之一。下禾一秉二斗四分斗之三。分斗之三。-九章算术九章算术1、一个两千年前的例子本课程第三章的内容：本课程第三章的内容：线性方程组的数值方法！线性方程组的数值方法！2、天体力学中的Kepler方程x是行星运动的轨道，它是时间t 的函数本课程第二章的内容：非线性方程的数值解法全球定位系统：在地球的任何一个位置，至少可以同时收到4颗以上卫星发射的信号 3、全球定位系统（Global Positioning System,GPS)表示地球上一个接收点R的当前位置，卫星Si的位置为 ，则得到下列非线性方程组 非线性方程组的数值方法非线性方程组的数值方法记为记为其中其中4、已经测得在某处海洋不同深度处的水温如下：深度（M）466 741 950 1422 1634水温（oC）7.04 4.28 3.40 2.54 2.13根据这些数据，希望合理地估计出其它深度（如500米，600米，1000米）处的水温本课程第四章的内容：插值法5、人口预测 下面给出的是中国1900年到2000年的人口数，我们的目标是预测未来的人口数（数据量较大时）19505519619606620719708299219809870519901143332000126743本课程第四章的内容：曲线拟合6、铝制波纹瓦的长度问题、铝制波纹瓦的长度问题 建筑上用的一种铝制波纹瓦是用一种机建筑上用的一种铝制波纹瓦是用一种机器将一块平整的铝板压制而成的器将一块平整的铝板压制而成的.假若要求波纹瓦长假若要求波纹瓦长4 4英尺英尺,每个波纹的高度每个波纹的高度(从从中心线中心线)为为1 1英寸英寸,且每个波纹以近似且每个波纹以近似2 2英寸英寸为一个周期为一个周期.求制做一块波纹瓦所需铝板的求制做一块波纹瓦所需铝板的长度长度L.L.这个问题就是要求由函数这个问题就是要求由函数f(x)=sin x给定的给定的曲线从曲线从x=0到到x=48英寸间的英寸间的弧长弧长L.由微积分学我们知道由微积分学我们知道,所求的弧长可表示为所求的弧长可表示为:上述积分称为第二类椭圆积分上述积分称为第二类椭圆积分,它不能用普它不能用普通方法来计算通方法来计算.本课程第五章的内容：数值积分7、生物化学反应的例子 A，B，C是三种蛋白质，其反应如下：我们通过建模可以得到如下方程组 A：B：C：本课程第六章的内容：常微分方程的数值方法用用计算机解决实际问题的步骤计算机解决实际问题的步骤 建立数学模型建立数学模型 选择数值方法选择数值方法 编写程序编写程序 上机计算结果上机计算结果步骤：步骤：实际问题建立数学模型提供计算方法实际问题建立数学模型提供计算方法设计程序上机计算获取近似结果设计程序上机计算获取近似结果数值分析的特点1、方法是近似的；2、与计算机不能分离：上机实习（掌握一门语言：C语言或Fortran语言，会用一种数学软件：Matlab或Mathematica，Maple）数值算法的数值算法的要求要求:1.仿真性：模型尽可能仿真实际问题仿真性：模型尽可能仿真实际问题;操作性差的例子：操作性差的例子：求解求解2020阶线性方程组，用阶线性方程组，用CramerCramer法则要用法则要用 次乘法运算次乘法运算,用每秒用每秒1 1亿次的计算机计算亿次的计算机计算,大约需算大约需算3030多万年多万年;但用消元法只须但用消元法只须30003000次乘法运算，只要几秒钟。次乘法运算，只要几秒钟。2.可操作性：程序简单、计算时间较少、计算机容易实现可操作性：程序简单、计算时间较少、计算机容易实现;3.实用性：近似解满足精度要求。实用性：近似解满足精度要求。公式一：公式一：(不实用的例不实用的例子子)：计算：计算记为记为则初始误差则初始误差?!考察第考察第n n步的误差步的误差造成这种情况的是造成这种情况的是不稳定的算法不稳定的算法。公式二：公式二：方法：先估计一个方法：先估计一个IN,再反推要求的再反推要求的In(n N)。可取可取迅速积累，误差呈递增走势。迅速积累，误差呈递增走势。可见初始的小扰动可见初始的小扰动取取 我们仅仅是幸运吗我们仅仅是幸运吗?考察反推一步的误差：考察反推一步的误差：以此类推，对以此类推，对 n N 有有：误差逐步递减误差逐步递减,这样的算法称为这样的算法称为稳定的算法稳定的算法。1.2 向量和矩阵范数向量和矩阵范数 Rn 空间的空间的向量范数向量范数|对任意对任意 满足下列条件：满足下列条件：（正定性正定性)对对任意任意(齐次性齐次性)（三角不等式三角不等式)常用向量范数常用向量范数 (设设1 p 0 使得使得，则称则称|A 和和|B 等价等价。定理定理1.2.1 Rn 上一切范数都等价。上一切范数都等价。可以理解为对任何可以理解为对任何向量范数都成立。向量范数都成立。二二.矩阵范数矩阵范数Rm n空间的空间的矩阵范数矩阵范数|对任意对任意 满足：满足：（正定性正定性)对对任意任意(齐次性齐次性)（三角不等式三角不等式)(4)*|AB|A|B|（相容相容 当当 m=n 时时)定义1.2.4常用矩阵范数：常用矩阵范数：Frobenius 范数范数 向量向量|2的直接推广的直接推广 对方阵对方阵 以及以及 有有算子算子范数范数 由向量范数由向量范数|p 导出关于矩阵导出关于矩阵 A Rn n 的的 p 范数范数:则则特别有：特别有：（行和范数行和范数）（列和范数列和范数）（谱范数谱范数）矩阵矩阵 A AT TA A 的最大的最大特征值特征值,又叫又叫A AT TA A的谱半径的谱半径(设设1 p 0,存在算子范数存在算子范数|使得使得|A|(A)+)+。设设：AAkk=lim是指是指ijkijkaa=)(lim对对所有所有 1 i,j n 成立。成立。定义定义1.2.5 Ak 0 0 (A)1 1定理定理1.2.5设设：AAkk=lim是指是指ijkijkaa=)(lim对对所有所有 1 i,j n 成立。成立。证明：证明：若不然，则若不然，则 有非零解，即存在非零向量有非零解，即存在非零向量 使得使得 若矩阵若矩阵 B 对某个算子范数满足对某个算子范数满足|B|1，则必有，则必有可逆；可逆；定理定理1.2.61.3 1.3 误差基础知识误差基础知识右端是截断误差右端是截断误差!一一 .误差来源（分类）误差来源（分类）1.1.模型误差。模型误差。2.2.观测误差。观测误差。3.3.截断误差，如截断误差，如舍入误差很小，本课程将研究它在舍入误差很小，本课程将研究它在运算过程中是否能被有效控制。运算过程中是否能被有效控制。4.4.舍入误差。计算机字长有限，一般实数不能精确存储，舍入误差。计算机字长有限，一般实数不能精确存储，于是产生舍入误差。于是产生舍入误差。例如：在例如：在1010位十进制数限制下：位十进制数限制下：1 1绝对误差绝对误差。设。设x为为准确值，准确值，为为近似值。则称近似值。则称 e=x-x*为为x*的绝对误差。如果的绝对误差。如果 则称则称 为为x*的绝对误差限。的绝对误差限。二误差基本概念二误差基本概念2 2相对误差相对误差。称。称 为为 的相对误差。的相对误差。实用中，常用实用中，常用 表示表示 的相对误差。的相对误差。如果如果 则称则称 为为 的相对误差限的相对误差限。3 3定义定义1.3.1(1.3.1(有效数字有效数字)则说则说 具有具有n位有效数字，分别是位有效数字，分别是若若 ，则称，则称 为有效数。为有效数。或称或称 准确到准确到 位位,例例1.3.11.3.1 设设x*=0.02700.0270是是某某数数 x 经经“四四舍舍五五入入”所所得得，则则 误差误差 e 不超过不超过 x*末位的半个单位，即：末位的半个单位，即：又又x*=0.270 x10=0.270 x10-1-1,故该不等式又可写为故该不等式又可写为由有效数字定义可知由有效数字定义可知,x*有有3 3位有效数字，位有效数字，分别是分别是2,72,7，0 0。例例1.3.21.3.2 设设 x=32.93,=32.93,x*=32.89=32.89。则则 x*=0.3289x10=0.3289x102 2,故故x*有有3 3位有效数字，分别是位有效数字，分别是3 3，2 2，8 8。由于由于x*中的数字中的数字9 9不是有效数字，故不是有效数字，故x*不是有效数。不是有效数。三、有效数位与误差的关系三、有效数位与误差的关系1.1.有效数位有效数位n越多越多,则绝对误差则绝对误差e越小越小(由定义由定义1.3.1)1.3.1)2.2.定理定理1.3.11.3.1 若近似数若近似数x*具有具有n位有效数字，则位有效数字，则 (1.2)(1.2)反之，反之，若若 则则x*至少有至少有n位有效数字。位有效数字。两边除以两边除以 得得 (1.4)(1.4)1.1.一元函数情形一元函数情形 设设 则则 ，由，由TaylorTaylor展开公式展开公式 （1.3）四、数值运算的误差估计四、数值运算的误差估计(1.3)(1.3)和（和（1.41.4）给出了由自变量的误差引起的函）给出了由自变量的误差引起的函数值的误差的近似式（数值的误差的近似式（误差传播误差传播）。）。2.2.多元函数情形多元函数情形设设 ，,则则由多元函数的由多元函数的TaylorTaylor展开公式类似可得展开公式类似可得 （1.51.5）（1.61.6）在（在（1.61.6）式中，分别取）式中，分别取,可得可得（1.71.7）（1.81.8）（1.91.9）例例1.3.3 1.3.3 测得某桌面的长测得某桌面的长a的近似值的近似值a*=120cm,=120cm,宽宽b的近似值的近似值b*=60cm=60cm。若已知若已知|e(a*)|0.2cm,|)|0.2cm,|e(b*)|0.1cm)|0.1cm。试求近试求近似面积似面积s*=a*b*的绝对误差限与相对误差限。的绝对误差限与相对误差限。解解:面积面积s=ab,在公式（在公式（1.51.5）中）中,将将 换为换为 s=ab,则则相对误差限为相对误差限为1.4 1.4 选用算法应遵循的原则选用算法应遵循的原则1.1.尽量简化计算步骤，减少乘除运算的次数尽量简化计算步骤，减少乘除运算的次数。2.2.防止大数防止大数“吃掉吃掉”小数小数3.3.尽量避免相近数相减尽量避免相近数相减4.4.避免绝对值很小的数做分母避免绝对值很小的数做分母5.5.选用数值稳定性好的算法选用数值稳定性好的算法，以控制舍入误差增长，以控制舍入误差增长