数值分析

绪论1数值分析第一章绪论1.1数值分析研究对象与特点数值分析又叫计算数学。实际问题→数学模型→数值计算方法→程序设计→上机计算求结果1.2数值计算的误差1.2.1误差来源于分类有限差分方法（FiniteDifferencMethods,FDM），是通过有限差分来近似导数或者偏导数，从而求得微分方法的近似解。在实际中，许多数学问题都很难得到其解析解，所谓解析解就是可以通过给出解的具体函数形式，从解的表达式中就可以算出任何自变量对应值；而数值解是在特定条件下通过近似计算得出来的一个数值。数值解只能由具体的系数确定：𝑎𝑥2+𝑏𝑥+𝑐=0(𝑎≠0)。假设f(x)在x0处各阶可导，则根据定理，其在x0+h的泰勒展开式为：𝑓(𝑥0+ℎ)=𝑓(𝑥0)+𝑓′(𝑥0)1!ℎ+𝑓(2)(𝑥0)2!ℎ2+⋯+𝑓(𝑛)(𝑥0)𝑛!ℎ𝑛+𝑅𝑛(𝑥)可以推导函数f一階导数的近似值：𝑓(𝑥0+ℎ)=𝑓(𝑥0)+𝑓′(𝑥0)ℎ+𝑅1(𝑥)设定𝑥0=𝑎，可解𝑓′(𝑎)=𝑓(𝑎+ℎ)−𝑓(𝑎)ℎ−𝑅1(𝑥)ℎ，𝑅1(𝑥)是𝑥→𝑎时的高阶无穷小，可以将f的一阶导数近似为𝑓′(𝑎)≈𝑓(𝑎+ℎ)−𝑓(𝑎)ℎ(一阶近似)。这种由于截断所引起的误差就是截断误差(truncationerror)或方法误差或结尾误差。由“四舍五入”引起的误差称为舍入误差(round-offerror）。步长不可能是无穷小，所以这也会引入一个误差。1.2.2误差与有效数字定义1：设x为准确值，x*为x的一个近似值，称e*=x*-x为近似值的绝对误差，简称误差。准确值是不知道的，否则没必要给出近似值，这也就是说，绝对误差是没法算的，所以我们给出绝对误差e*的误差限：|𝑥−𝑥|，即𝑥−𝑥𝑥+；对于10、11和1000、1001，它们的绝对误差都是1，但是它们误差的程度是不同的，所以，我们引入相对误差。绝对误差:△＝│测量值—真值│相对误差:相对误差＝(绝对误差/真值的绝对值）×100%≈绝对误差/测量值的绝对值）×100%，相对误差用表示。同理，相对误差限可表示为=|𝑥|。为什么需要有效数字，因为有效数值和误差有直接的联系：有效数字越多，绝对误差和相对误差就越小，因此近似数就越准确。因为一个近似数和准确数的前几位相同，就看后面位数的值相不相同，相同的越多说明误差越小。定义2：若近似值𝑥的误差限是某一位的半个单位，该位到𝑥的第一位非零数字共有𝑛位，就说𝑥有𝑛位有效数字。它可表示为𝑥=10(𝑎1+𝑎210−1+⋯+𝑎𝑛10−(𝑛−1))(2-1)′𝑎1≠0，为整数，且|𝑥−𝑥|1210−𝑛+1绪论2定理1设近似数𝑥表示为𝑥=10(𝑎1+𝑎210−1+⋯+𝑎𝑛10−(𝑛−1))其中𝑎(=1，2，⋯，)是0到中的一个数字，𝑎1≠0，整数。若𝑥具有𝑛位有效数字，则其相对误差限为12𝑎110−(𝑛−1)；反之，若𝑥的相对误差限12(𝑎1+1)10−(𝑛−1)，则𝑥至少具有𝑛位有效数字。证明：由(2-1)′可得𝑎110|𝑥|(𝑎1+1)10当𝑥有n位有效数字时=|𝑥−𝑥|𝑥010−𝑛+1𝑎110=12𝑎110−𝑛+1反之，由|𝑥−𝑥|=|𝑥|(𝑎1+1)1012(𝑎1+1)10−𝑛+1=010−𝑛+1故𝑥至少有𝑛位有效数字。1.2.3数值运算的误差估计两个近似数𝑥1与𝑥2，其误差限分别为(𝑥1)及(𝑥2)，它们进行加、减、乘、除运算得到的误差限分别为(𝑥1𝑥2)=(𝑥1)+(𝑥2)(𝑥1𝑥2)=|𝑥1|(𝑥2)+|𝑥2|(𝑥1)(𝑥1/𝑥2)≈|𝑥1|(𝑥2)+|𝑥2|(𝑥1)|𝑥2|2(𝑥2≠0)绝对误差和相对误差与微分的关系(𝑥)=𝑥−𝑥=𝑥(𝑥)=𝑥−𝑥𝑥=𝑥𝑥=𝑛𝑥例如，=𝑥𝑛→𝑛=𝑛𝑛𝑥→𝑛=𝑛𝑛𝑥→()=𝑛(𝑥)即((𝑥𝑛))=𝑛(𝑥)，得到𝑥的误差会将𝑥𝑛的误差变成𝑛𝑥。更一般的是，当自变量有误差时计算函数值也产生误差，其误差限可利用函数的泰勒展开式进行估计。设𝑓(𝑥)是一元函数，𝑥的近似值为𝑥，以𝑓(𝑥)近似𝑓(𝑥)，其误差界记作(𝑓(𝑥))，可用泰勒展开𝑓(𝑥)−𝑓(𝑥)=𝑓′(𝑥)(𝑥−𝑥)+𝑓()2(𝑥−𝑥)2，介于，之间，忽略(𝑥)的高阶项，得计算函数的误差限(𝑓(𝑥))≈|𝑓′(𝑥)|(𝑥)当𝑓为多元函数时，如=𝑓(𝑥1，𝑥2⋯𝑥𝑛)，则A的近似值为=𝑓(𝑥1，𝑥2，⋯𝑥𝑛)，于是由泰勒展开得函数值的误差()为()=−=𝑓(𝑥1，𝑥2，⋯𝑥𝑛)−𝑓(𝑥1，𝑥2⋯𝑥𝑛)≈∑(𝑓(𝑥1，𝑥2，⋯𝑥𝑛)𝑥)𝑛1(𝑥−𝑥)=∑(𝑓𝑥)𝑛1于是误差限()≈∑|(𝑓𝑥)|𝑛1(𝑥)绪论3而的相对误差限为=()=()||≈∑|(𝑓𝑥)|𝑛1(𝑥)||以上部分是关于函数的误差、误差限以及相对误差限等。1.3误差定性分析与避免误差危害向后误差分析法(backwarderroranalysis):𝑥=𝑔(𝑎1，𝑎2⋯，𝑎𝑛)𝑥=𝑔(𝑎1+1，𝑎2+2⋯，𝑎𝑛+𝑛)再推出这些的的界(不是唯一的，且无须求出的具体值)，然后再利用摄动理论(perturbationtheory)估计最后舍入误差|x-a|的界。—詹姆斯·威尔金森(JamesHardyWilkinson,1919-1986)的贡献。区间分析法：设x，y的近似数为α，β，由于|𝑥−𝛼|𝛿𝛼，|𝑥−𝛽|𝛿𝛽，则𝑥∈[𝛼−𝛿𝛼，α+δα]=X，∈[𝛽−𝛿𝛽，β+𝛿β]=Y，若计算𝑧=𝑥，由𝑍=𝑋𝑌=[𝑧，𝑧]=[𝑧−𝛿𝑧，𝑧+δz]，则z为所求近似值，而δ𝑧则为误差值。1.3.1病态问题与条件数对一个数值问题本身如果输入数据有微小扰动(即误差)，引起输出数据(即问题解)相对误差很大，就是病态问题。计算函数值𝑓(𝑥)时，若𝑥有扰动∆𝑥=𝑥−𝑥，其相对误差为∆𝑥x，函数数值𝑓(𝑥)的相对误差为|𝑓(𝑥)−)𝑓(𝑥)𝑓(𝑥)||∆𝑥|≈|𝑥𝑓′(𝑥)𝑓(𝑥)|=称为计算函数值问题的条件数。10就认为是病态。1.3.2算法的数值稳定性定义3一个算法如果输入数据有误差，而在计算过程中舍入误差不增长，则称此算法是数值稳定的，否则称此算法为不稳定的。1.3.3避免误差危害的若干原则1.要避免除数(分母)绝对值远远小于被除数(被除数)绝对值的除法2.要避免两相近数相减当x很大时，√𝑥+1−√𝑥=1√x+1+√𝑥当𝑓(𝑥)=𝑓(𝑥)时，可用泰勒展开𝑓(𝑥)−𝑓(𝑥)=𝑓′(𝑥)(𝑥−𝑥)+𝑓(𝑥)2(𝑥−𝑥)2+⋯，取右端的有限项近似左端。如果无法改变算式，则采用增加有效位数进行运算；在计算机上则采用双倍字长运算，但这要增加机器计算时间和多占内存单元。3.要防止大数“吃掉”小数在计算如:=0242105+∑𝛿10001时，要先计算后式先。4.注意简化计算步骤，减少运算次数插值法4秦九韶算法是将一元n次多项式的求值问题转化为n个一次式的求值计算，大大减少了计算中乘法的次数。⋯求多项式的值时，首先计算最内层括号内一次多项式的值，即，,⋯对于一个n次多项式，至多做n次乘法和n次加法，这就是秦九韶算法。若直接计算，逐项相加，一共需要做𝑛+(𝑛−1)+⋯+2+1=𝑛(𝑛+1)2第二章插值法2.1引言得到一组数据，通过这组数据来找到函数关系，得到函数的方法有插值法和拟合法，当函数是多项式时，称为代数插值。波动大的用拟合法，波动小的用插值法。设函数=𝑓(𝑥)在区间[a,b]上有定义，且已知在点𝑎𝑥0𝑥1⋯𝑥𝑛𝑏上的值0，1，⋯𝑛，若存在一简单函数P(x)，使𝑃(𝑥)=(=0，1，⋯，𝑛)成立，就称𝑃(𝑥)为𝑓(𝑥)的插值函数，点𝑥0，𝑥1，⋯，𝑥𝑛称为插值节点，包含插值节点的区间[a,b]称为插值区间，求插值函数𝑃(𝑥)的方法称为插值法。若𝑃(𝑥)是次数不超过n的代数多项式，即𝑃(𝑥)=𝑎0+𝑎1𝑥+⋯𝑎𝑛𝑥𝑛，其中𝑎为实数，就称𝑃(𝑥)为插值多项式，相应的插值法称为多项式插值。若𝑃(𝑥)为分段的多项式，就称为分段插值。若𝑃(𝑥)为三角多项式，就称为三角插值。2.2拉格朗日插值(𝑛次多项式插值，𝑛个多项式的组合)2.2.1线性插值与抛物插值(函数泰勒展开，取𝑛=1或𝑛=2就得到线性插值与抛物插值)点斜式：𝐿1(𝑥)=+𝑦+1−𝑦𝑥+1−𝑥(𝑥−𝑥)，通分后可得两点式：𝐿1(𝑥)=𝑥+1−𝑥𝑥+1−𝑥+𝑥−𝑥𝑥+1−𝑥+1，由此看出，𝐿1(𝑥)是由两个线性函数的线性组合得到，系数分别为和+1，(𝑥)=𝑥−𝑥+1𝑥−𝑥+1，+1(𝑥)=𝑥−𝑥𝑥+1−𝑥，𝐿1(𝑥)=(𝑥)++1+1(𝑥)，我们称函数(𝑥)及+1(𝑥)为线性插值基函数。同理，利用二次插值基函数−1(𝑥),(𝑥),+1(𝑥)，立即得到二次插值多项式𝐿2(𝑥)=−1−1(𝑥)+(𝑥)++1+1(𝑥)它满足条件𝐿2(𝑥𝑗)=𝑗(𝑗=𝑘−1,𝑘,𝑘+1)，所以，得插值法5𝐿2(𝑥)=−1(𝑥−𝑥)(𝑥−𝑥+1)(𝑥−1−𝑥)(𝑥−1−𝑥+1)+(𝑥−𝑥−1)(𝑥−𝑥+1)(𝑥−𝑥−1)(𝑥−𝑥+1)++1(𝑥−𝑥−1)(𝑥−𝑥)(𝑥+1−𝑥−1)(𝑥+1−𝑥)抛物线插值至少要求用三个插值点来计算。2.2.2拉格朗日插值多项式𝐿𝑛(𝑥𝑗)=𝑗(𝑗=0,1,⋯,𝑛)(2-6)定义1：若n次多项式𝑗(𝑥)(𝑗=0,1,⋯,𝑛)在n+1个节点𝑥0𝑥1⋯𝑥𝑛上满足条件𝑗(𝑥)={1,𝑘=𝑗0,𝑘≠𝑗(𝑗,𝑘=0,1,⋯,𝑛)就称这n+1个n次多项式0(𝑥)，1(𝑥)，⋯,𝑛(𝑥)为节点𝑥0，𝑥1⋯，𝑥𝑛上的n次插值基函数。N次插值基函数为(𝑥)=(𝑥−𝑥0)⋯(𝑥−𝑥−1)(𝑥−𝑥+1)⋯(𝑥−𝑥𝑛)(𝑥−𝑥0)⋯(𝑥−𝑥−1)(𝑥−𝑥+1)⋯(𝑥−𝑥𝑛)𝐿𝑛(𝑥)=∑𝑛0(𝑥)为已知(2-8)由(2−6)𝐿𝑛(𝑥𝑗)=∑𝑛0(𝑥𝑗)=𝑗(𝑗=0,1,⋯,𝑛)形如(2-2)的插值多项式𝐿𝑛(𝑥)称为拉格朗日(Lagrange)插值多项式。注：𝑓(𝑥)=0⇒𝑓(𝑥)=(𝑥−𝑥)𝑔(𝑥)𝑓(𝑥)=𝑓′(𝑥)=0⇒𝑓(𝑥)=(𝑥−𝑥)2𝑔(𝑥)0𝑛(𝑥0)=1,0𝑛(𝑥)=0(=1,2,⋯)⇒0𝑛(𝑥)=(𝑥−𝑥0)(𝑥−𝑥1)(𝑥−𝑥2)⋯(𝑥−𝑥𝑛)𝑔(𝑥)0𝑛(𝑥)是𝑛多项式，(𝑥−𝑥0)(𝑥−𝑥1)(𝑥−𝑥2)⋯(𝑥−𝑥𝑛)已经是𝑛多项式，故𝑔(𝑥)只能是常数，令𝑔(𝑥)=𝑎，𝑎可由0𝑛(𝑥0)=1或𝑗𝑛(𝑥𝑗)=1来确定。定理1在次数不超过n的多项式集合𝐻𝑛中，满足条件(2-2)的插值多项式𝐿𝑛(𝑥)∈𝐻𝑛是存在唯一的。2.2.3插值余项与误差估计定理2设𝑓(𝑛)(𝑥)在[a,b]上连续，𝑓(𝑛+1)(𝑥)在(a,b)内存在，节点𝑎𝑥0𝑥1⋯𝑥𝑛𝑏,𝐿𝑛(𝑥)是满足条件(2-2)的插值多项式，则对任何𝑥∈[𝑎,𝑏],插值余项𝑅𝑛(𝑥)=𝑓(𝑥)