数值计算方法报告课件

现代数值计算报告现代数值计算报告 2012年9月8日主讲内容主讲内容误差及有效数字误差及有效数字几种插值几种插值曲线拟合的最小二乘法曲线拟合的最小二乘法什么是数值计算方法？数值建模 数值计算实际问题 数学问题 近似解 什么是“好的”数值计算方法？误差小 误差分析耗时少 复杂度分析抗干扰 稳定性分析1误差及有效数字1.1误差的来源 （1）模型误差模型误差 指数学模型与实际问题之间出现的误差。（2）观测误差观测误差 由观测产生的误差 （3）截断误差截断误差 当数学模型不能得到精确解时，通常要用数值方法求它的近似解，其近似解与精确解之间的误差称为截断误差。如函数 f f(x x)用Taylor展式的有限项来近似代替。（4）舍入误差舍入误差 由于受计算机字长的限制，计算时只能取有限位数进行运算，由此产生的误差称舍入误差。1.2 1.2 误差的概念误差的概念(绝对)误差 设 x*为精确值（或准确值），x 为 x*的近似值，称 e=x*x 为近似值x的(绝对)误差。(绝对)误差限（）如果精确值 x*与近似值 x 的误差的绝对值不超过某个正数，即|e|=|x*x|。于是，精确值也可表示为 x*=x ，或相对误差 设 x*为精确值，x 为近似值，相对误差为：当绝对误差 e 较小时，相对误差可写为：相对误差限 如果有正数r使得 则称r为 x*的相对误差限。有效数字 设 x*的近似值为 p为整数，若 x 的绝对误差限不超过末位的半个单位，即 则称用 x 近似 x*是具有“n 位有效数字。”表示数x的末位的半个单位2 几种插值插值问题的背景 在生产和实验中，函数 f(x)或者其表达式不便于计算,或者无表达式而只有函数在给定点的函数值(或其导数值)，此时我们希望建立一个简单的而便于计算的近似函数(x)，来逼近函数 f(x)。常用的函数逼近方法有：插值法；最小二乘法（或称均方逼近）；一致逼近等。插值法是函数逼近的重要方法之一，有着广泛的应用。简单地说，插值法就是用给定的(未知)函数 f(x)的若干点上的函数值(或其导数值)来构造f(x)的近似函数(x)，要求(x)与f(x)在给定点的函数值相等。有很多种插值法，其中以拉格朗日(Lagrange)插值和牛顿(Newton)插值为代表的多项式插值最有特点，常用的插值还有Hermite插值，分段插值和样条插值。插值法的定义 设 f(x)为a，b上的函数，在互异点x0,x1,.,xn 处的函数值分别为f(x0),f(x1),f(xn)，构造一个简单函数(x)作为函数f(x)的近似表达式y=f(x)(x),使 (xi)f(xi),i0,1,2,n (1.0)则称(x)为关于节点x0,x1,.,xn的插值函数；称x0,x1,.,xn 为插值节点；称(xi,f(xi),i=1,2,n 为插值点；f(x)称为被插值函数。(1.0)式称为插值条件。这类问题称为插值问题。2.1 Lagrange插值插值 选用代数多项式作为插值函数。Lagrange插值就是选用节点上的函数值作为插值条件。线性插值线性插值 给定两个点(x0，y0)，(x1，y1），x0 x1，确定一个一次多项式插值函数，简称线性插值线性插值。待定系数法待定系数法 设 L1(x)=a0+a1x,代入插值点当x0 x1时，方程组的解存在唯一。即插值条件：L1(xi)=f(xi)=yi,i=0,1解之得，因此，（1.1）式称为一次LagrangeLagrange插值。插值。由求解过程知，用待定系数法，需要求解线性方程组，当已知节点较多时，即方程的未知数多，计算量较大，不便向高阶插值推广。n 次插值多项式的构造次插值多项式的构造 插值基函数法插值基函数法 分别构造x0,x1,xn 上的 n 次插值基函数 l0(x),l1(x),ln(x),满足性质：即 节点基函数x0 x1x2xnl0(x)1000l1(x)0100l2(x)0010ln(x)0001所以我们得到 n 次Lagrange插值多项式：其中：2.2 n 次次Newton插值公式插值公式 给定n+1个插值点(xi,f(xi),i=0,1,2,n,xi互异，类似地，由二阶至 n 阶差商的定义得：(xx0)(xx0)(xx1)(xx0)(xxn1)上述所有n+1个等式相加，得：其中，插值误差为：n次Newton插值公式拉格朗日插值与牛顿插值的比较拉格朗日插值与牛顿插值的比较举例：2008年阳宗海浓度变化的模拟2.3 埃尔米特埃尔米特(Hermite)插值插值 设 f(x)具有一阶连续导数，已知节点上的函数值和导数值，即(xi,f(xi),(xi,f(xi),i=0,1,2,n,若存在 2n+1次多项式 H2n+1(x)满足 则称 H2n+1(x)为 f(x)关于节点xi(i=0,1,2,n)的Hermite插值多项式。2.4三次样条插值函数Runge现象 插值多项式在插值区间上发生剧烈的震荡。它揭示了高次插值多项式存在的缺陷。产生的原因 误差有截断误差和舍入误差两部分组成，而在插值的计算过程中，舍入误差可能会扩散或放大。分段线性插值：已知节点上的函数值，插值函数整体连续。三次Hermite插值：已知节上的函数值和导数值，插值函数具有一阶连续的导数。为了得到光滑度更高的插值函数，引入样条插值函样条插值函数数。“样条”名词来源于工程中船体和汽车等的外形设计：给出外形曲线上的一组离散点(样点)，如(xi,yi)，i=0,1,2,n,将有弹性的细长木条或钢条(样条)在样点上固定，使其在其它地方自由弯曲，这样样条所表示的曲线，称为样条曲线(函数)。在数学上，它表现为近似于一条分段的三次多项式，它要求在节点处具有一阶和二阶连续导数。定义定义 给定a,b上n+1个节点：a=x0 x1 n),x=(x1,x2,xn),b=(b1,b2,bn),考虑Ax=b，即 由代数知识知，若 秩(A,b)=秩(A),则方程组有解；若 秩(A,b)秩(A),则方程组无解,此时称为矛盾方程组矛盾方程组。矛盾方程组的解，即最小二乘解，是指在均方误差极小意义下的解，即 minAx-b22。我们已经知道，用直线 p(x)=a0+a1x 拟合给定数据:(xi,yi),i=1,2,m,把数据代入直线方程得：考察方程组：ATAa=ATy，即于是我们得到法方程：(3.3)上述表明，ATAa=ATy 的解a=(a0,a1)T,正是线性拟合中法方程的解，即为使 最小的解。上述极小问题也可表示为：而 又是方程组 Aa=y 的最小二乘解。定义定义 设 A=(aij)mn,mn,方程 ATAx=ATb 称为矛盾方程组 Ax=b 的法方程。定理定理3.13.1 （1）若若秩(A)=n，则法方程恒有解。（2）x 是 的解，当且仅当x是法方程的解。注：注：定理3.1告诉我们，求解拟合曲线的极小值问题与求解矛盾方程组的法方程等价。因此，求解拟合曲线的极小 问题可以转化为求解法方程：ATAx=ATb。对于离散数据:(xi,yi),i=1,2,m,用n次多项式来拟合曲线。设 求解极小问题 等价于求解矛盾方程组 Aa=y 的极小问题，其中，因此，求 a0,a1,an,就是求解法方程：ATAa=ATy。例3.3 用二次多项式函数拟合如下数据（见例3.2）。解 m=7，经计算有：设 p(x)=a0+a1x+a2x2,形成法方程：约定 直接计算有：于是得到法方程 解得 a0=0.66667,a1=-1.39286,a2=-0.13095,所以 p(x)=0.66667-1.39286x-0.13095x2 非线性问题线性化 一般地，设 p(x)=a0+a1x+a2x2+anxn.作变换 将数据(xi,yi)由变换转化为(z(i),yi),再求解法方程：ATAa=ATy，其中，由法方程求出a0,a1,an,再代回原变量x就求出了非线性曲线。特别地，如果非线性函数为将给定数据(xi,yi)转换为(ui,vi),求出a,b,再代回原变量y,x，可求得原非线性拟合曲线。例例3.6 3.6 用给数据求经验公式：y=a ebx。x 1 2 3 4 5 6 7 8 y 15.3 20.5 27.4 36.6 49.1 65.6 87.8 117.6解解 线性化。对经验公式取自然对数 ln y=ln a+bx （令u=ln y，b0=ln a，则 u=b0+bx）代入数据的矛盾方程组由法方程 ATAB=ATy，B=（b0,b),即 a=e2.4369=11.4375.y=11.4375e0.2912x.谢谢，请批评指正！谢谢，请批评指正！