数值分析

数值分析(科学与工程计算基础)主讲：雷秀仁[e-mail]华南理工大学理学院数学系教材•应用数值分析郑咸义等编著（华南理工大学出版社）参考书目NumericalAnalysis:MathematicsofScientificComputing(ThirdEdition)DavidKincaid&WardCheney（机械工业出版社)NumericalAnalysis(SeventhEdition)RichardL.Burden&J.DouglasFaires（高等教育出版社）数值分析的研究对象数值分析属于计算数学的范畴，是数学的一个分支，也称为数值计算方法、计算方法、数值方法等。其研究对象是求解各种数学问题的数值方法的设计、分析及其有关的数学理论和具体实现的一门学科。它是科学与工程计算（科学计算）的基础。•许多科学与工程实际问题（如：核武器的研制、导弹的发射、气象预报等）的解决都离不开科学计算。•目前，理论、试验、计算已成为人类进行科学活动的三大方法。数值分析的研究对象科学计算的过程，是从数学模型的提出到上机计算得出结果的完整过程。（下图表明了其中的主要步骤和相互关系）数学化离散化程序化数学模型数值算法编制程序上机运行输出结果实际问题数值分析研究的对象数值分析研究的对象数值分析是数学、计算机科学与其他学科交叉的产物。本门课程将着重介绍进行科学计算所必须掌握的一些最基本、最常用的数值方法（数值算法），并作相关分析。数值分析的任务对典型的数学问题给出数值求解方法(近似方法)，并对算法进行理论分析，使得其能够在计算机有效地得以实现。数值算法的构造算法的理论分析数值分析的任务①针对数值问题研究可在计算机上执行且行之有效的计算公式（数值算法）。例：解线性方程组，已有Cramer法则，但不可行。②数值算法的分析，主要包括误差分析（数值问题的性态，数值方法的截断误差、舍入误差和稳定性、收敛性等）和复杂性分析（计算量、存储量）。课程目的①学习一些常用的数值方法，掌握数值方法的基本理论，为进一步研究和使用更复杂的数值算法奠定基础。②初步掌握一种科学计算软件包（如Matlab）的使用方法。课程主要内容插值方法；曲线拟合与函数逼近；数值逼近数值积分与数值微分；线性代数方程组数值求解的直接法；线性代数方程组数值求解的迭代法；数值代数非线性方程与方程组数值求解；常微分方程数值求解。Matlab简介第一章绪论主要内容：一些常用概念；数值算法的复杂度与稳定性。数值计算中的误差；数值算法设计的若干原则；1.数值分析中常用的一些概念数值问题数值解算法计算量病态问题算法数值稳定性数值问题、数值解、算法由一组已知数据（输入数据），求出一组结果数据（输出数据），使得这两组数据之间满足预先制定的某种关系的问题，称为数值问题。由数值计算公式算出的数值形式的解(通常由计算机计算得到)称为数值解。一般数值解是近似解。由给定的已知量，经过有限次的四则运算及规定的运算顺序，求出所关心的未知量的数值解，这样所构成的整个计算步骤，称为数值算法（简称算法）。计算量一个算法所需要的乘法和除法总次数称为计算量。计算量的单位为flop，表示完成一次浮点数乘或除法所需要的时间。算法的计算量可以衡量算法的优劣，因为它体现着算法的计算效率，通常算法的计算量越小，则算法的计算效率越高，因而该算法也越好。由于计算机做加减法要比乘除法快得多，故算法的计算量可以不考虑加减法的时间。例:设A，Ｂ，Ｃ分别为10×20，20×50，50×10的矩阵，计算D=ABC就有如下不同的算法和计算量算法1：D=(AB)C计算量N1=15000flop;算法2：D=A(BC)计算量N2=12000flop.病态问题因初始数据的微小变化，导致解产生剧烈变化问题称为病态问题。病态问题也称为坏问题，这类问题通常是问题本身固有的。求解病态问题应该特别注意，因为实际问题的数据都是近似的或经计算机计算要对输入数据做舍入处理，这都引起原始数据的扰动，若所求解的正好是个病态问题，则采用通常算法计算就会出现很隐蔽的错误，导致不良的后果。病态问题在函数计算、方程求根及方程组求解中都是存在的，它的计算或求解应用专门的方法或将其转化为非病态问题来求解。例：病态的方程组考察方程组和上述方程组尽管只是右端项有微小扰动，但解大不相同：一个是，一个是。这类方程组称为病态的。121221.00012.0001xxxx121221.00012xxxx121xx122,0xx算法的数值稳定性在计算过程中产生的舍入误差能被控制在一定的范围内，且对最后的结果影响不大的算法称为数值稳定算法。不是数值稳定的算法称为数值不稳定算法。数值不稳定算法会导致计算结果失真，对数值不稳定的算法常采用转化成相应的数值稳定的算法来处理。2.对算法所要考虑的问题209.7×101.计算速度。例如，求解一个20阶线性代数方程组，若用克莱姆法则要进行约次乘法运算，如用每秒1亿次乘法运算的计算机要30万年。而用Gauss消去法只需约3000次乘法运算，用普通微机1秒之内便可算出结果。209.7×1021102.存储量。大型问题有必要考虑。3.收敛性。不收敛的算法无使用价值。4.数值稳定性。在大量计算中，舍入误差的积累能否控制住，这与算法有关。3.数值计算中的误差•来源及种类---模型误差、参数误差、截断误差、舍入误差。1.模型误差（也称描述误差）模型误差是在建立数学模型时，由于忽略了一些次要因素而产生的误差，它是数学建模阶段要考虑的误差，不是计算方法可以解决的。2.参数误差（也称观测误差）测量已知参数时，数据带来的误差，它也不是计算方法能解决的问题。数值计算中的误差3.截断误差（也称方法误差）截断误差是对参与计算的数学公式做简化可行处理后所产生的误差（用有限过程代替无限过程或用容易计算的方法代替不容易计算的方法），即数学模型的数值解与精确解之间的误差，是计算方法关注的内容。（举例：P6sinx=…）4.舍入误差（也称计算误差）舍入误差是由于计算机只能表示有限位数字，因而只能取有限位数进行计算所得的误差，它也是计算方法关注的内容。（举例：）3.141592653数值计算中的误差•误差的基本概念绝对误差---近似数x*关于准确数x的绝对误差：E(x)=x－x*（或E(x*)=x－x*）---近似数x*关于准确数x的绝对误差限：｜E(x)｜=｜x－x*｜---工程上表示准确数x的范围：x*－xx*+或x=x*---函数值的绝对误差：E[f(x)]≈f’(x)E(x)（利用微分中值公式导出）举例：f(x)=x^3数值计算中的误差相对误差---近似数x*关于准确数x的相对误差：()()()()或rrxExExExExxxxxxxx()rExxxx()()()()()()rEfxExEff'fxxfxx---函数值的相对误差限：---近似数x*关于准确数x的相对误差限：数值计算中的误差有效数字---用x*表示x时准确到小数点后第k位：1102kxx1121122120.1010(101010),,,,01102mnnnnmnmxxxxxxxxxxxxnmxx即其中=0~9，且（最左一位非零字）；是正整数，是整数。---近似数x*具有n位有效数字：举例1113.1415926530.314592653103.14160.31416103.140.31410数值计算中的误差•有效数字与相对误差的关系---n位有效数字的近似数x*其相对误差：11(1)11002()nrxxEx（最左一位），且(1)11()11002(1)nrExxx（最左一位），且---相对误差为的近似数x*至少具有n位有效数字。注：在未标明近似数的绝对误差时默认该近似数准确到末位数字，从其最左边的非零数字起直到最右边的一位数字止均为有效数字。4.数值计算中应注意的几个问题•若干原则---１．注意简化计算步骤，减少运算次数；（例：秦九韶算法)２．避免两个相近的数相减，减少有效数字的损失；（例）３．使用数值稳定的算法;（例:习题1.16）４．小心处理病态的数学问题；复习题习题1.1(3)(4)、1.2、1.3、1.4、1.6、1.9(1)、1.15、1.162.1插值问题的提出§第二章函数近似计算的插值法()iiyfxxf1.在工程实际问题中,某些变量之间的函数关系是存在的,但通常不能用式子表示,只能由实验或观测得到在一系列离散点上的函数值.2()fx.有的函数虽然有表达式,但比较复杂,计算函数很不经济且不利于在计算机上进行计算.(,)().iixfyfx希望通过这些数据计算函数在其他指定点处的近似值或获取其他信息,()().Pxfx这两种情况下都希望用简单的函数来逼近原函数插值问题的提出插值：已知[a,b]上的函数y=f(x)在n+1个互异点处的函数值:fnf2f1f0f(x)xnx2x1x0x求简单函数P(x)，使得()0,1,(),*iiPxfin计算f(x)可通过计算P(x)来近似代替。如下图所示。yxx0x1f0f1x2f2xifixi+1fi+1xn-1fn-1xnfnP(x)f(x)一、插值问题的数学提法这就是插值问题,(*)式为插值条件,()()Pxfx称函数为函数的插值函数则称之为插值多项式为多项式函数如果,)(xP称为插值节点点,,,2,1,0,nixi称为插值区间区间],[ba个等分点上若给定如函数5],0[,sinxy其插值函数的图象如图00.511.522.533.500.10.20.30.40.50.60.70.80.91sinx的的的xy00.511.522.533.500.10.20.30.40.50.60.70.80.91sinx的的的xy00.511.522.533.500.10.20.30.40.50.60.70.80.91sinx的的的xy00.511.522.533.500.10.20.30.40.50.60.70.80.91sinx的的的xy()()fxPx对于被插函数和插值函数ix在节点处的函数值必然相等()()Pxfx但在节点外的值可能就会偏离()()Pxfx因此近似代替必然存在着误差（截断误差）整体误差的大小反映了插值函数的好坏.为了使插值函数更方便在计算机上运算,一般插值函数都使用代数多项式或有理函数.本章讨论的就是(代数)多项式插值.1.满足插值条件的多项式P(x)是否存在且唯一？2.若满足插值条件的P(x)存在,又如何构造出P(x);即插值多项式的常用构造方法有哪些？3.用P(x)代替f(x)的误差估计，即截断误差的估计；对于多项式插值，我们主要讨论以下几个问题：4.当插值节点无限加密时，插值函数是否收敛于f(x)。二、插值多项式的存在唯一性()[,]yfxab设函数在区间上的代数插值多项式为nnnxaxaxaaxP2210)(且满足()0,1,2,,,niiPxfin.ia其中是n+1个待定的系数012(),,,,nnPxaaaa即多项式的系数满足线性方程组20102000nnaaxaxaxf20112111nnaaxaxaxf2012nnnnnnaaxaxaxf--------(1)上述方程组的系数行列式为n+1阶Vandermond行列式nnnnnnxxxxxxxxxV212110200111101)(ninijijxxjixx0定理1.由Cramer法则,线性方程组(1)有唯一解nnnxaxaxaaxP2210)(()0,1,2,,niiPxfin--------(3)--------(2)),(jixx