第1章数值计算引论课件

数值计算方法第第1 1章章 数值计算引论数值计算引论第第2 2章章 非线性方程的数值解法非线性方程的数值解法第第3 3章章 线性代数方程组的数值解法线性代数方程组的数值解法第第4 4章章 插值法插值法第第5 5章章 曲线拟合的最小二乘法曲线拟合的最小二乘法第第6 6章章 数值积分和数值微分数值积分和数值微分第第7 7章章 常微分方程初值问题的数值解法常微分方程初值问题的数值解法数值计算方法数值计算方法第1章 数值计算引论数值计算方法 第第1 1章章数值计算引论1.1 数值计算方法 1.2 误差的来源1.3 近似数的误差表示法1.4 数值运算误差分析1.5 数值稳定性和减小运算误差 第第1 1章章 数值计算引论 数值计算方法与误差分析数值计算方法与误差分析 理工科大学本科生理工科大学本科生 科学研究。科学研究。现代科学研究的三大手段现代科学研究的三大手段 理论分析、科学实验、科学计算。理论分析、科学实验、科学计算。1.11.1数值计算方法数值计算方法1.1.1 1.1.1 数值计算方法及其主要内容数值计算方法及其主要内容 1.1.课程名称：科学与工程数值计算方法课程名称：科学与工程数值计算方法 简称：科学计算、科学与工程计算、数值分简称：科学计算、科学与工程计算、数值分析、计算方法、数值计算方法。析、计算方法、数值计算方法。科学与工程：从实用的角度，将科学研究与科学与工程：从实用的角度，将科学研究与工程技术上遇到的实际问题用数学模型来描述，工程技术上遇到的实际问题用数学模型来描述，以便进行定量的分析、研究。以便进行定量的分析、研究。第1章 数值计算引论 数值：数、数字，由数值：数、数字，由0-90-9十个数字、小数点和十个数字、小数点和正负号等组成的数。正负号等组成的数。计算方法：解题的方法。可以用自然语计算方法：解题的方法。可以用自然语言、数学语言或约定的符号语言来描述。言、数学语言或约定的符号语言来描述。计算：只能包括计算机能够直接处理的计算：只能包括计算机能够直接处理的运算运算,即加减乘除等基本运算。即加减乘除等基本运算。数值计算：相对于非数值计算，如查表、数值计算：相对于非数值计算，如查表、排序等。用（排序等。用（0-90-9十个数字、小数点、正负号等组十个数字、小数点、正负号等组成的）数，通过计算机进行加减乘除等基本运算。成的）数，通过计算机进行加减乘除等基本运算。2 2。数值算法：对科学研究与工程技术上遇到。数值算法：对科学研究与工程技术上遇到的实际数学问题的解法归结为用数值进行加减乘除的实际数学问题的解法归结为用数值进行加减乘除等基本运算，并有确定运算顺序，完整而准确的描等基本运算，并有确定运算顺序，完整而准确的描述称为数值算法。述称为数值算法。数值计算方法是研究用数字计算机解决数值计算方法是研究用数字计算机解决数学问题的数值算法及其理论的一门课程。数学问题的数值算法及其理论的一门课程。数值：数、数字，由0-9十个数字、小数点和正负号等 3.主要内容：工程上遇到的数学问题 数值计算的误差分析 非线性方程 线性方程组 插值法 最小二乘法 数值积分和数值微分 常微分方程1.1.2 用计算机解题的步骤 当给定一个科学研究与工程技术上遇到的实际问题时，首先根据专业知识建立实际问题的数学模型，即模型化（modeling)或建模。然后对数学模型进行求解。数学模型（包括公式、表格、图形等）求解有两条途径：求解析解和数值解。3.主要内容：工程上遇到的数学问题 求解析解，解以表达式表示，这是准确解。求数值解，解是以一些离散点上取值的形式表示，多数情况下，数值解是近似的，求数值解要用计算机。求数学模型数值解的方法称为数值计算方法。选择计算方法以后进行程序设计，即用程序语言把算法编成程序，然后上机得出数值解。实际问题-数学问题(建模)-构造数值计算方法-程序设计-上机计算-数值解-结果分析 求解析解，解以表达式表示，这是准确解。数值计算的基本方法(补)离散化插值法迭代法逼近法数值计算的基本方法(补)离散化1 离散化方法设f(x)是定义在a,b上的连续函数，当它们的表达式很复杂，甚至写不出来时，我们可以选择若干个离散点x0,x1,xna,b 求出f(x)在这些点处的函数值或函数值的近似值fi=f(xi)i=0,1,n,从而得到一个如下的函数值列表：xx0 x1xnyf(x0)f(x1)f(xn)1 离散化方法设f(x)是定义在a,b上的连续函数，当它2 插值方法对于任意给出的某个函数y=f(x)的函数值列表:我们可以构造一个简单函数，比如n次多项式pn(x)，满足条件pn(xi)=yi,i=0,1,n 并利用pn(x)近似表示f(x)。提示：由于pn(x)是一个多项式函数，用它在某一点处的函数值、导数值、区间上的定积分等来近似未知函数y=f(x)的值、微分、定积分xx0 x1xnyy0y1yn2 插值方法对于任意给出的某个函数y=f(x)的函数值列表3 函数逼近设f(x)是满足某种特定条件的函数，表达式比较复杂甚至写不出来，但是我们可以把它表示为一个简单函数系列 fn(x),n=1,2,的极限,即 lim fn(x)=f(x)(n)这样我们就可以根据不同的精度要求选取适当大的正数N,利用fN(x)近似替代f(x)。提示：如果f(x)可以展为泰勒级数，那么我们可以取fn(x)为f(x)的泰勒展式前n+1项。3 函数逼近设f(x)是满足某种特定条件的函数，表达式比较4 迭代的方法如要计算某个真值x*，可构造一个序列xn,n=0,1,2,，该序列满足：x0 已知；有一个简单函数(t)，且xn+1=(xn)，n=0,1,2,lim xn=x*(n)则，可反复利用xn+1=(xn)，经过N 次迭代后，用xn+1 作为x*的近似值。4 迭代的方法如要计算某个真值 x*，可构造一个序列xn实例：求5的平方根的迭代格式1.初值x0=2，xn+1=2+1/(xn+2)简单迭代法2.初值x0=2，xn+1=（xn+1/xn)/2 牛顿迭代法请大家练习用两种迭代法求解的结果实例：求5的平方根的迭代格式1.1.3 算法及算法的评价算法：为解决某一特定问题或完成某个特定任务而设计或规定的一个有限步的操作指令序列称为算法。提示：算法具有如下一些特征：输入：有0个或多个输入输出：有一个或多个输出(处理结果)确定性：每步定义都是确切、无歧义的有穷性：算法应在执行有穷步后结束有效性：每一步操作均可由有限次最基本的运算来完成。1.1.3 算法及算法的评价算法：为解决某一特定问题或完成算法的描述：自然语言：流程图：伪代码：算法的评价：程序的可读性好；节省计算时间节省存储空间数值稳定性与收敛性算法的描述：关于算法的评价 既然研究典型的数学问题的计算方法、或者说数值解方法最后都要用“算法”来描述，所以对具体的计算方法的评价也就转化为对算法的评价。一个算法的好坏可用下面几个指标来刻划程序的可读性好；节省计算时间节省存储空间数字稳定性好 关于算法的评价 既然研究典型的数学问题的计算方法收敛速率的描述在一个迭代过程中，如果我们有其中c为非零常数，则称xn p阶收敛于x*。术语：当p=1时，称算法具有线性速率收敛；当1p2时，称算法具有超线性收敛速率；当p=2时，称算法具有二次终结性质或二次收敛速率。收敛速率的描述在一个迭代过程中，如果我们有1.1.4 程序的基本结构本书程序的基本结构采用模块化程序设计思想主要分四大模块FormProblem()：主要完成程序的参数（常量）设置Operation()：完成算法的基本操作ShowTable()：完成计算结果（含中间结果）的屏幕输出SaveTable()：计算结果的保存（写文件）1.1.4 程序的基本结构本书程序的基本结构误差的来源即产生误差的原因。主要有四种：误差的来源即产生误差的原因。主要有四种：1.1.模模型型误误差差-建建立立的的数数学学模模型型和和实实际际的的距距离离，客观量的准确值与数学模型的准确解的差。客观量的准确值与数学模型的准确解的差。例如自由落体运动方程例如自由落体运动方程1-2 1-2 1-2 1-2 误差的来源误差的来源误差的来源即产生误差的原因。主要有四种：1-2 误差的来源2.观测误差：数学模型当中的参数或常数常常是是观测或实验来的，这样必然有误差，称为观测误差或测量误差，由观测数据而产生的误差。例如自由落体运动方程2.观测误差：数学模型当中的参数或常数常常是是观测或实验来的3.截断误差(方法误差)-数学模型的准确解与利用数值计算方法得到的准确解之差。无穷过程用有穷项代替例如:无穷级数取前n项代替截断误差用有限的过程代替无限的过程，和用简单的计算问题代替复杂的计算问题所产生 的误差。3.截断误差(方法误差)-数学模型的准确解与利用数值计算4.舍入误差：计算工具字长是有限位，在计算时只能对有限位数字进行运算，超过这个位数时，要舍入，于是产生舍入误差。原始数据、中间步骤和最终结果都可能产生舍入误差。如圆周率3.14159265 一般实数不能精确存储，例如：在10位十进制数限制下：4.舍入误差：计算工具字长是有限位，在计算时只能对有限位数1-3 近似数的误差表示1-3 近似数的误差表示第1章数值计算引论课件第1章数值计算引论课件第1章数值计算引论课件第1章数值计算引论课件第1章数值计算引论课件1.3.2 相对误差1.3.2 相对误差第1章数值计算引论课件第1章数值计算引论课件第1章数值计算引论课件第1章数值计算引论课件1.3.3 有效数字：由绝对误差决定。有效数字：由绝对误差决定。1.3.3 有效数字：由绝对误差决定。若近似值x*的绝对误差(限)是某位的半个单位，则说 x*精确到该位，若从该位到 x*的左面第一位非零数字一共有n位，则称近似值x*有n位有效数字。若近似值x*的绝对误差(限)是某位的半个单位第1章数值计算引论课件第1章数值计算引论课件 1.用四舍五入得到的近似数的误差限是末位的半个单位。近似数的误差限是末位的半个单位，则有n位有效数字。因此用四舍五入得到的近似数是有效数字。2.在公式运算中，要先区分准确量和近似数。准确数有无穷多位有效数字.3.有效数字位与小数点后有多少位数无直接关系。1.用四舍五入得到的近似数的误差限是末位的半个单位。1.3.4 有效数字与相对误差1.3.4 有效数字与相对误差第1章数值计算引论课件第1章数值计算引论课件第1章数值计算引论课件 1.定理给出的是一个充分条件，而不是必要条件。定理的逆命题不成立。2.在实际应用时，为了要使所取近似数的相对误差满足一定要求，可以用定理，确定所取近似数应具有有效数字的位数。1.定理给出的是一个充分条件，而不是必要条件。定理的第1章数值计算引论课件第1章数值计算引论课件 1.1.定理给出的是一个充分条件，而不是必要条件。定理的定理给出的是一个充分条件，而不是必要条件。定理的逆命题不成立。即若近似数有逆命题不成立。即若近似数有n n位有效数字，相对误差不一定满位有效数字，相对误差不一定满足定理。足定理。2.2.在实际应用时，为了要使所取近似数具有在实际应用时，为了要使所取近似数具有n n位有效数字，位有效数字，要求所取近似数的相对误差满足定理的要求。要求所取近似数的相对误差满足定理的要求。1.定理给出的是一个充分条件，而不是必要条件。定理的 1.4 1.4 数值运算误差分析数值运算误差分析 函数运算误差函数运算误差 算术运算误差算术运算误差 1.4 数值运算误差分析1.4 数值运算误差分析函数y=f(x1,x2)的全微分为：若x1,x2的准确值为x1*,x2*,则y的准确值为y*=f(x1*,x2*)又 的dx1x1*-x1=dx2 x2*-x2=dy y*-y=故：相对误差：1.4 数值运算误差分析函数y=f(x1,x2)的全微分和差积商的误差估计：(x1x2)=(x1)(x2)(x1x2)=x2(x1)+x1(x2)(x1/x2)=(x1)/x2-(x2)x1/x22(x1x2)=(x1/(x1x2）)(x1)(x2/(x1x2）)(x2)(x1x2)=(x1)+(x2)(x1/x2)=(x1)-(x2)和差积商的误差估计：利用条件数估算误差定义：设y=f(t)是在某个x附近连续可微的实函数，也称为是一个数学问题，记称cond(f,x)为数学问题y=f(t)在t=x处的条件数，也可简称为数学问题 y=f(x)的条件数。注释 在表示一个数学问题的条件数时，有时候需要明确指出f的自变量x，以及f(x)在x=x0处的条件数，这时，也可以把条件数更具体地表示为)()(),cond(xfxfxxf=)()(),(cond0000 xfxfxxxf=利用条件数估算误差定义：设y=f(t)是在某个x附近连续可微计算数学问题的条件数举例 例：试求tan(x)在x=/6处的条件数。计算数学问题的条件数举例分析：记(x0)、(x0)和f(x0)、f(x0)分别为x0和f(x0)的绝对误差和相对误差，则有 (x0)=(x0)/x0 f(x0)=f(x0)/f(x0)利用f(x0)=f(x0)(x0),即得结论1：f(x0)=condf(x),x0(x0)分析：记(x0)、(x0)和f(x0)、f(x结论2：如果一个数学问题y=f(x)的条件数的绝对值|condf(x),x0|1，那么有|f(x)|1，则数学问题是不稳定的，或者说是病态的，输入值的微小误差可以导致输出值的较大的误差结论2：复合函数的条件数：假设函数关系y=f(x)是通过一个中间变量u复合而成的，即y=y(u)，u=u(x)。利用复合函数的求导规则 我们有亦即：condy(u(x),x0=condy(u),u0 condu(x),x0 复合函数的条件数：1.5 1.5 数值稳定性和减小运算误差数值稳定性和减小运算误差 在计算过程中误差不会扩大或对计算结果的精度要在计算过程中误差不会扩大或对计算结果的精度要求影响不大。求影响不大。减小运算误差减小运算误差:1 1 要避免两相近数相减。要避免两相近数相减。2 2 要防止大数吃掉小数要防止大数吃掉小数 。3 3 要避免除数绝对值远小于被除数绝对值要避免除数绝对值远小于被除数绝对值 。4 4 注意简化计算步骤，减少运算次数注意简化计算步骤，减少运算次数 。1.5 数值稳定性和减小运算误差例：计算积分例：计算积分写成递推公式写成递推公式 误差传递规律误差传递规律公式改为公式改为 则误差按规律则误差按规律逐渐缩小逐渐缩小1.5.1 1.5.1 数值稳定性数值稳定性:一个算法，如果计算结果受误差的影一个算法，如果计算结果受误差的影响小，就称这个算法具有较好的数值稳定性。否则，就称数响小，就称这个算法具有较好的数值稳定性。否则，就称数值稳定性不好。因此要设法控制误差的传播值稳定性不好。因此要设法控制误差的传播 。例：计算积分写成递推公式 误差传递规律公式改为 则误差按规律1.5.2 1.5.2 减小运算误差减小运算误差1.1.要避免相近两数相减要避免相近两数相减 13.5846-13.5839=0.000713.5846-13.5839=0.00076 6位有效数字变成了位有效数字变成了1 1位有效数字。损失了有效数字的位数。位有效数字。损失了有效数字的位数。当当x x接近于接近于0 0时，应时，应1.5.2 减小运算误差1.要避免相近两数相减当x接近于0例例 解一元二次方程解一元二次方程a x2+bx+c=0，其中其中-b ,c2 2 要防止大数要防止大数“吃掉吃掉”小数，注意保护重要物理参数。小数，注意保护重要物理参数。在在8位十进制计算机上计算。要规格化和对阶。位十进制计算机上计算。要规格化和对阶。结果，结果，大数大数“吃掉吃掉”小数。小数。类似地类似地改变计算方法改变计算方法例 解一元二次方程a x2+bx+c=0，其中-一元二次方程根的表示方法假如一元二次方程有绝对值不同的两个实根，记sign(b)表示取b符号，记x1为绝对值较小的那一个实根，也就是分子是同号两数相减的那一个；x2为绝对值较大的那一个实根，从而有对于求x1来说，可以把分子有理化，从而得到一元二次方程根的表示方法假如一元二次方程有绝对值不同的两个实求一元二次方程根数值解的具体方法如果记那么x1，x2还可进一步简单地表示为x1=c/Quad(a,b,c)，x2=Quad(a,b,c)/a其中x1，x2分别为一元二次方程的绝对值较小，较大的根。求解Quad(a,b,c)的c语言函数可以说明为double Quad(double a,double b,double c)求一元二次方程根数值解的具体方法如果记例例 在在5位十进制计算机上计算位十进制计算机上计算在在5位十进制计算机上计算。要规格化和对阶。位十进制计算机上计算。要规格化和对阶。结果，结果，大数大数“吃掉吃掉”小数。小数。改变计算方法，按绝对值由小到大相加。改变计算方法，按绝对值由小到大相加。例 在5位十进制计算机上计算在5位十进制计算机上计算。要规3 3 注意简化计算步骤，减少运算次数，避免误差积累注意简化计算步骤，减少运算次数，避免误差积累 例：计算例：计算 的值。的值。又如又如只需只需14次乘法。次乘法。3 注意简化计算步骤，减少运算次数，避免误差积累 例：计算多项式的值计算方法对于一般形式的多项式A(x)=a0+a1x+anxn把它表示为：PolyValue(x,A,n)=a0+a1x+anxn其中A是(2.1)式给出的多项式A(x)的系数构成的(行)向量，亦即：A=(a0,a1,an)程序设计时，可以把A说明为一个n+1维数组，此时约定A0存放a0，A1存放a1，An存放an。函数声明：double PolyValue(double x,double*A,int n)多项式的值计算方法对于一般形式的多项式1 逐项求和算法思想：按次数由低到高的顺序逐项求和。用变量power存放x的各次幂，并利用xk=xxk-1来简化计算。源程序：（见下页）1 逐项求和算法思想：按次数由低到高的顺序逐项求和。用变量pdouble PolyValue(double x,double*A,int n)double power=1.0,y;int k;y=A0;for(k=1;k=0;k-)y=y*x+Ak;return y;算法的计算量：乘法：n次，加法：n次。double PolyValue(double x,dou秦九韶算法的补充说明秦九韶算法现在已经越来越受到重视，还有更重要的原因。假设计算一个基于泰勒展式的多项式的值，不失一般性可以假设它的各项都是正的，注意到级数收敛的必要条件是它的通项将趋近于零。当计算的项数比较大时采用秦九韶算法可明显地提高精度（实际计算表明可以保证精度）。秦九韶算法的补充说明