第1章数值计算引论

数值计算方法第1章数值计算引论第2章非线性方程的数值解法第3章线性代数方程组的数值解法第4章插值法第5章曲线拟合的最小二乘法第6章数值积分和数值微分第7章常微分方程初值问题的数值解法数值计算方法

第1章数值计算引论1.1数值计算方法1.2误差的来源1.3近似数的误差表示法1.4数值运算误差分析1.5数值稳定性和减小运算误差

第1章数值计算引论

数值计算方法与误差分析理工科大学本科生————科学研究。现代科学研究的三大手段————

理论分析、科学实验、科学计算。1.1数值计算方法1.1.1数值计算方法及其主要内容

1.课程名称：科学与工程数值计算方法简称：科学计算、科学与工程计算、数值分析、计算方法、数值计算方法。科学与工程：从实用的角度，将科学研究与工程技术上遇到的实际问题用数学模型来描述，以便进行定量的分析、研究。

数值：数、数字，由0-9十个数字、小数点和正负号等组成的数。计算方法：解题的方法。可以用自然语言、数学语言或约定的符号语言来描述。计算：只能包括计算机能够直接处理的运算,即加减乘除等基本运算。数值计算：相对于非数值计算，如查表、排序等。用（0-9十个数字、小数点、正负号等组成的）数，通过计算机进行加减乘除等基本运算。

2。数值算法：对科学研究与工程技术上遇到的实际数学问题的解法归结为用数值进行加减乘除等基本运算，并有确定运算顺序，完整而准确的描述称为数值算法。

数值计算方法是研究用数字计算机解决数学问题的数值算法及其理论的一门课程。3.主要内容：工程上遇到的数学问题

数值计算的误差分析非线性方程线性方程组插值法最小二乘法数值积分和数值微分常微分方程1.1.2用计算机解题的步骤当给定一个科学研究与工程技术上遇到的实际问题时，首先根据专业知识建立实际问题的数学模型，即模型化（modeling)或建模。然后对数学模型进行求解。数学模型（包括公式、表格、图形等）求解有两条途径：求解析解和数值解。

求解析解，解以表达式表示，这是准确解。求数值解，解是以一些离散点上取值的形式表示，多数情况下，数值解是近似的，求数值解要用计算机。求数学模型数值解的方法称为数值计算方法。选择计算方法以后进行程序设计，即用程序语言把算法编成程序，然后上机得出数值解。实际问题-----数学问题(建模)---构造数值计算方法---

程序设计---上机计算---数值解---结果分析数值计算的基本方法(补)离散化插值法迭代法逼近法1离散化方法设f(x)是定义在[a,b]上的连续函数，当它们的表达式很复杂，甚至写不出来时，我们可以选择若干个离散点

x0,x1,…,xn∈[a,b]

求出f(x)在这些点处的函数值或函数值的近似值

fi=f(xi)i=0,1,…,n,

从而得到一个如下的函数值列表：xx0x1…xnyf(x0)f(x1)…f(xn) 2插值方法对于任意给出的某个函数y=f(x)的函数值列表:

我们可以构造一个简单函数，比如n次多项式pn(x)，满足条件

pn(xi)=yi,i=0,1,…,n

并利用pn(x)近似表示f(x)。提示：由于pn(x)是一个多项式函数，用它在某一点处的函数值、导数值、区间上的定积分等来近似未知函数y=f(x)的值、微分、定积分xx0x1…xnyy0y1…yn3函数逼近设f(x)是满足某种特定条件的函数，表达式比较复杂甚至写不出来，但是我们可以把它表示为一个简单函数系列{fn(x),n=1,2,…}的极限,即

limfn(x)=f(x)(n∞)

这样我们就可以根据不同的精度要求选取适当大的正数N,利用fN(x)近似替代f(x)。提示：如果f(x)可以展为泰勒级数，那么我们可以取fn(x)为f(x)的泰勒展式前n+1项。4迭代的方法如要计算某个真值

x*，可构造一个序列{xn,n=0,1,2,…}，该序列满足：

x0

已知；有一个简单函数φ(t)，且xn+1=φ(xn)，n=0,1,2,…limxn=x*(n→∞)

则，可反复利用xn+1=φ(xn)，经过N次迭代后，用xn+1

作为x*

的近似值。实例：求5的平方根的迭代格式初值x0=2，xn+1=2+1/(xn+2)简单迭代法初值x0=2，xn+1=（xn+1/xn)/2牛顿迭代法请大家练习用两种迭代法求解的结果1.1.3算法及算法的评价算法：为解决某一特定问题或完成某个特定任务而设计或规定的一个有限步的操作指令序列称为算法。提示：算法具有如下一些特征：输入：有0个或多个输入输出：有一个或多个输出(处理结果)确定性：每步定义都是确切、无歧义的有穷性：算法应在执行有穷步后结束有效性：每一步操作均可由有限次最基本的运算来完成。算法的描述：自然语言：流程图：伪代码：算法的评价：程序的可读性好；节省计算时间节省存储空间数值稳定性与收敛性

关于算法的评价

既然研究典型的数学问题的计算方法、或者说数值解方法最后都要用“算法”来描述，所以对具体的计算方法的评价也就转化为对算法的评价。一个算法的好坏可用下面几个指标来刻划程序的可读性好；节省计算时间节省存储空间数字稳定性好收敛速率的描述在一个迭代过程中，如果我们有

其中c为非零常数，则称{xn}p阶收敛于x*。术语：当p=1时，称算法具有线性速率收敛；当1<p<2时，称算法具有超线性收敛速率；当p=2时，称算法具有二次终结性质或二次收敛速率。1.1.4程序的基本结构本书程序的基本结构采用模块化程序设计思想主要分四大模块FormProblem()：主要完成程序的参数（常量）设置Operation()：完成算法的基本操作ShowTable()：完成计算结果（含中间结果）的屏幕输出SaveTable()：计算结果的保存（写文件）误差的来源即产生误差的原因。主要有四种：1.模型误差---建立的数学模型和实际的距离，客观量的准确值与数学模型的准确解的差。例如自由落体运动方程1-2误差的来源2.观测误差：数学模型当中的参数或常数常常是是观测或实验来的，这样必然有误差，称为观测误差或测量误差，由观测数据而产生的误差。例如自由落体运动方程3.截断误差(方法误差)---数学模型的准确解与利用数值计算方法得到的准确解之差。无穷过程用有穷项代替例如:无穷级数取前n项代替截断误差用有限的过程代替无限的过程，和用简单的计算问题代替复杂的计算问题所产生的误差。4.舍入误差：计算工具字长是有限位，在计算时只能对有限位数字进行运算，超过这个位数时，要舍入，于是产生舍入误差。原始数据、中间步骤和最终结果都可能产生舍入误差。如圆周率3.14159265……

一般实数不能精确存储，例如：在10位十进制数限制下：1-3近似数的误差表示1.3.2相对误差1.3.3有效数字：由绝对误差决定。

若近似值x*的绝对误差(限)是某位的半个单位，则说x*精确到该位，若从该位到x*的左面第一位非零数字一共有n位，则称近似值x*有n位有效数字。

1.用四舍五入得到的近似数的误差限是末位的半个单位。近似数的误差限是末位的半个单位，则有n位有效数字。因此用四舍五入得到的近似数是有效数字。

2.在公式运算中，要先区分准确量和近似数。准确数有无穷多位有效数字.3.有效数字位与小数点后有多少位数无直接关系。1.3.4有效数字与相对误差1.定理给出的是一个充分条件，而不是必要条件。定理的逆命题不成立。

2.在实际应用时，为了要使所取近似数的相对误差满足一定要求，可以用定理，确定所取近似数应具有有效数字的位数。

1.定理给出的是一个充分条件，而不是必要条件。定理的逆命题不成立。即若近似数有n位有效数字，相对误差不一定满足定理。

2.在实际应用时，为了要使所取近似数具有n位有效数字，要求所取近似数的相对误差满足定理的要求。

1.4数值运算误差分析函数运算误差算术运算误差1.4数值运算误差分析函数y=f(x1,x2)的全微分为：

若x1,x2的准确值为x1*,x2*,则y的准确值为y*=f(x1*,x2*)

又的dx1≈x1*-x1=dx2≈x2*-x2=dy≈y*-y=

故：

相对误差：和差积商的误差估计：δ(x1±x2)=δ(x1)±δ

(x2)δ(x1x2)=x2δ(x1)+x1δ(x2)δ(x1/x2)=δ(x1)/x2-δ(x2)x1/x22η(x1±x2)=(x1/(x1±x2）)η(x1)±(x2/(x1±x2）)η(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=)()(']),(cond[0000xfxfxxxf=计算数学问题的条件数举例例：试求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)]=cond[f(x),x0]η(x0)结论2：如果一个数学问题y=f(x)的条件数的绝对值|cond[f(x),x0]|<1，那么有|η[f(x)]|<|η(x)|，这表明相对误差有缩小的趋势；若|cond[f(x)]|>>1，则数学问题是不稳定的，或者说是病态的，输入值的微小误差可以导致输出值的较大的误差复合函数的条件数：假设函数关系y=f(x)是通过一个中间变量u复合而成的，即y=y(u)，u=u(x)。利用复合函数的求导规则

我们有亦即：cond[y(u(x)),x0]=cond[y(u),u0]cond[u(x),x0]

1.5数值稳定性和减小运算误差在计算过程中误差不会扩大或对计算结果的精度要求影响不大。减小运算误差:1要避免两相近数相减。2要防止大数吃掉小数。3要避免除数绝对值远小于被除数绝对值。4注意简化计算步骤，减少运算次数。例：计算积分写成递推公式误差传递规律公式改为

则误差按规律

逐渐缩小

1.5.1数值稳定性:一个算法，如果计算结果受误差的影响小，就称这个算法具有较好的数值稳定性。否则，就称数值稳定性不好。因此要设法控制误差的传播。1.5.2减小运算误差1.要避免相近两数相减

13.5846-13.5839=0.00076位有效数字变成了1位有效数字。损失了有效数字的位数。当x接近于0时，应例解一元二次方程a

x2+bx+c=0

，其中-b,c2要防止大数“吃掉”小数，注意保护重要物理参数。在8位十进制计算机上计算。要规格化和对阶。结果，大数“吃掉”小数。类似地改变计算方法一元二次方程根的表示方法假如一元二次方程有绝对值不同的两个实根，记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语言函数可以说明为doubleQuad(doublea,doubleb,doublec)例在5位十进制计算机上计算在5位十进制计算机上计算。要规格化和对阶。结果，大数“吃掉”小数。改变计算方法，按绝对值由小到大相加。3注意简化计算步骤，减少运算次数，避免误差积累例：计算的值。又如只需14次乘法。多项式的值计算方法对于一般形式的多项式

A(x)=a0+a1x+…+anxn把它表示为：PolyValue(x,A,n)=a0+a1x+…+anxn其中A是(2.1)式给出的多项式A(x)的系数构成的(行)向量，亦即：

A=(a0,a1,…,an)

程序设计时，可以把A说明为一个n+1维数组，此时约定A[0]存放a0，A[1]存放a1，…，A[n]存放an。函数声明：doublePolyValue(doublex,double*A,intn)1逐项求和算法思想：按次数由低到高的顺序逐项求和。用变量power存放x的各次幂，并利用xk=xxk-1来简化计算。源程序：（见下页）doublePolyValue(doublex,double*A,intn){ doublepo