数值算法概论

计算方法,ComputationalMethods,数值计算方法,数值分析NumericalAnalysis,计算方法ComputationalMethods,数值算法概论预备知识误差稳定性,第一章绪论,为了解决大规模数值计算问题人类研制出电子计算机ENIAC,计算方法研究用计算机求解数学问题近似解的方法和理论非线性方程求根、线性代数方程组求解、数据插值、数据拟合、数值积分、求微分方程数值解,冯诺依曼,冯诺依曼教授提出了计算机的体系结构,计算机技术发展的同时人类计算能力受到挑战,数值分析应用范围:科学与工程计算、数值模拟、程序设计中基本算法,数值分析适用的软件平台:MATLAB、VB、VC、Java,数学科学可以分为两大体系:一是算法体系;二是演绎体系,计算机程序涉及两个方面:数学模型和算法,程序设计语言和数据结构,内容：非线性方程求根、线性方程组的解法、插值方法、数值积分、常微分方程数值解法目的意义：掌握科学计算知识，掌握几种最基本、典型、通用的数值计算方法。数值算法：利用计算机求解数学问题近似解的方法基础课程：数学分析，线性代数，C语言等计算机语言，MATLAB等计算软件。,参考资料：数值分析孙志忠东南大学出版社数值计算方法丁丽娟北京理工大学出版社计算方法周铁清华大学出版社学习方法：在理解的基础上掌握本书介绍的算法，并要上机操作练习（编程，计算出结果）要求：出勤，课堂，作业，,1.1数值算法概论,用计算机解决实际问题的主要步骤,数值算法：利用计算机求解数学问题近似解的方法。近似解也称数值解或逼近解。,构造算法的要求1、面向数学模型：可靠的理论分析，使算法尽可能地仿真问题的模型（即达到精度要求，保证收敛性稳定性，误差进行分析）；2、面向计算机：算法具有递推性、简洁性、准确性，尽量节省存储量，减少工作量；3、要有数值实验.,模型与算法,例如,计算地球表面积,是一个过分理想化的模型,r由观测统计获得,圆周率取近似.但如果改用椭球面积计算会使计算难度变大.,引例1.求一元二次方程的根。常用公式用这个公式编程并在字长为8位的计算机上计算，得x1=109,x2=0.实际根为x1=109,x2=4.计算机计算结果错误的原因：受机器字长的限制引起的误差造成的。,通过直接计算可以产生递推关系,引例3.计算积分,主要性质：,下面用两种算法按上述递推公式进行计算,算法A,按照递推公式从n=1到n=20，产生如下数据,由递推公式,每计算一次舍入误差增长5倍，误差的积累导致最终的数值解于真实解相悖,于是改进算法如下,算法B,按照递推公式从n=20到n=1，由于该算法每向后推进一步其舍入误差便减少5倍，因此符合原积分模型性态，产生如下数据,直接法：上例采用的是由原模型精确解的递推关系来实现计算机求解的，这种数值求解方法称为直接法,离散变量法：大多数情况下，只能获得原模型解的近似递推关系，即将连续系统离散化，这种数值求解方法称为离散变量法,离散变量法实例：考察结构力学，热传导问题中经常出现的数学定解问题两点边值问题,的数值解法，其中p(x),q(x)及f(x)是a,b上的给定函数，为已知常数，且问题在a,b上恒有唯一解，步骤如下,(1)将区间a,b离散化，即将a,bN等分，所得节点为,其中,称为步长；,称为节点上的值；,称为节点上的函数值，简记为。,(2)将原定解问题进行离散化，由于,略去两式中的余项，并取，即得,一阶中心差商,二阶中心差商,注：均为二阶精度,将上二式代入原问题当中去，得差分格式,其中,。上式是含,N-1个未知数的线性方程组。,向量范数,矩阵范数,算子范数,1.2预备知识,另一种定义,是定义在Rn上的实函数，如果它满足,lp范数,常用的三种范数,向量的1-范数,向量的2-范数,向量的-范数,即,和,等价。,此定理说明向量范数间具有等价性，因此以后只需就一种范数讨论。,证明,（为定义在上的实函数，如果它满足）,谱半径：,为矩阵B的谱半径。,特别地，如果A为实对称矩阵，则,例,解,定理1.5,必存在,中的某范数，使得,定理1.6(矩阵范数的等价性),定义1.5,1.3误差,1.误差的来源与分类,来源,模型误差(描述误差):建立数学模型时是实际问题的抽象和简化，所引起的误差；,分类,舍入误差:计算机表示的数的位数有限，通常用四舍五入的办法取近似值，由此引起的误差.,截断误差(方法误差):求解数学模型时，用简单代替复杂,或者用有限过程代替无限过程所引起的误差,观测误差(测量误差):测量工具的限制或在数据的获取时随机因素所引起的物理量的误差；,假设某一数据的准确值为x*,其近似值为x，则称,2绝对误差与相对误差,e=x*-x为近似值x的绝对误差，简称误差,表征近似值的精确程度,如果存在一个适当小的正数，使得,则称为绝对误差限简称误差限或精度。,称r为相对误差限。,如果存在一个适当小的正数r，使得,为近似值x的相对误差。,而称,实际问题常用,3有效数字取的有限位数如下(3.1415926),取x1=3，误差限不超过0.5;,取x2=3.14,误差限不超过0.005;,若近似值x的绝对误差限是某一位上的半个单位，则说该近似值准确到这一位；且该位到x的第一位非零数字一共有n位，则称近似值x有n位有效数字.,取x3=3.1416,误差限不超过0.00005;,定义：设近似值,如果,则称近似值x有n位有效数字，其中,其中，,准确到位。,都是x的有效数字，或称x,例1,解,例2,解,定理2设近似值,的其相对误差限为,则它至少有n位有效数字。,定理1设近似值,有n位有效数字，则其相对误差限为,4误差传播,计算机的数值运算主要是加，减，乘，除四则运算，带有误差的数过四则运算后如何变化，可用微分描述。准确值x*与其近似值x其差可认为是较小的增量，即可以把差看作微分,例计算圆面积的误差估计圆面积计算公式:y=r2由全微分近似:y2rr=e(y)2re(r),er(y)2er(r),取r=50cm,e(r)=0.5cm,则有e(y)150cm2,er(y)21%=2%,数值运算的误差估计,1.一元函数y=f(x)误差分析(准确值y*=f(x*)由Taylor公式,同理:,所以,2.多元函数z=f(x1,x2,xn)误差分析,(1),(3),(2),3.算术运算的误差估计,例5.二次方程x216x+1=0,取求使具有4位有效数,解:直接计算x187.937=0.063(x1)=(8)+(7.937)=0.0005计算出的x1具有两位有效数,修改算法,4位有效数,一个算法如果输入数据有误差，而在计算过程中舍入误差不增长，则称此算法是数值稳定的，否则称此算法为不稳定的,借助数值计算中误差估计对误差传播的分析，为是误差不增长，可以得出一些基本原则.,1.4算法的数值稳定性,两个相近的数相减会引起有效数字的严重损失，从而导致相对误差增大。,参考文献,1科学计算引论基于MATLAB的数值分析2MATLAB5.X与科学计算