CS205A Lecture 15 Numerical integration and differentiation

课程主页:https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html

这次回顾第十五讲,这一讲介绍了数值积分和微分。

Chapter 12 数值积分和微分

积分

首先讨论一元函数求积分的问题,即

我们的目标是求

这里有两个假设:

  1. $a,b$固定。
  2. 可以计算$f(x)$任意一点的值。

插值求积

因为定积分是由黎曼和定义的,即

其中

所以一种常见的思路是运用下式近似计算$\int_{a}^{b} f(x)$

其中$w_i$为权重。类似插值的思想,我们希望对于多项式基$f_k(x)= x^k,k=0,\ldots n-1 $,有如下事实成立

系数矩阵为范德蒙矩阵,求解该方程即可,来看一个具体例子

例1

考虑$n=3$的情形:

其中

线性方程组为

解得

这个公式被称为辛普森公式。

Newton-Cotes求积

这部分讨论节点$\{x_1,\dots ,x_n\}$的选择问题,最常见的节点选择方式为选择等距节点,Newton-Cotes求积就有该特点,分别有如下两种:

  1. Closed:包括端点$a,b​$

  2. Open:不包括端点$a,b$

对应图片如下:

根据这两种节点选择的方式,产生了许多常用公式。

Open:

取$n=1$,于是产生了中点公式:

Closed:

取$n=2$,那么

于是产生梯形公式:

取$n=3$,那么

此即为例1的情形,所以

这三种方法的图示如下:

复合求积

实际中我们肯定希望使用多个节点求数值积分,那么相邻两个节点之间可以使用之前介绍的方法:

假设

那么复合中点公式为

复合梯形公式为

在$n$为偶数的情形下,复合辛普森公式为

精确度

这一部分讨论三种积分公式的精确度,首先定义

那么$f$在$c$处的泰勒展开为

对上式积分可得

注意中点公式为

因此中点公式的精确度为$O\left(\Delta x^{3}\right)​$。

对(1)式令$x=a,b$可得

两式相加并乘以$\frac {b-a}{2}​$得到

因此梯形公式的精确度同样为$O\left(\Delta x^{3}\right)$。

运用类似的方法可以证明辛普森公式的精确度为$O\left(\Delta x^{5}\right)​$.

注意泰勒展开只有在$\Delta x$充分小的时候成立,所以实际中先要将区间划分为$\frac{b-a}{\Delta x}$个部分,因此实际的误差还要乘以$\frac 1{\Delta x}$,所以误差分别为:

  • 中点公式:$O(\Delta x^2)$
  • 梯形公式:$O(\Delta x^2)​$
  • 辛普森公式:$O(\Delta x^4)$

还有两种求积分的方法为高斯求积以及自适应求积,这部分讲义介绍的比较简单,这里略过。

多变量积分

由于维度灾难问题,如果函数为

那么按照之前介绍的方法,我们取点的数量为$O(n^k)​$,所以之前的方法很难推广到多变量的情形,此时我们一般采用蒙特卡洛方法。

条件数

之前讨论的都是精确度问题,这部分条件该方法的条件数。假设$\hat f$是$f$的扰动,那么

回顾插值求积部分的公式,我们有

如果所有权重都非负,那么条件数为

如果某些权重是负数,那么某些$|w_i|$可能非常大,求积公式就会不太稳定。

微分

这部分讨论如何计算数值微分。

有限差分

回顾泰勒展开:

调整该等式,我们有

由此得到前向差分公式

同理可得后向差分公式

注意这两种方法的精确度都为$O(h)$。

现在考虑如下两个展开:

两式相减得到

该公式被称为中点差分公式,其精确度为$O(h^2)$。

(1),(2)相加得到二阶导数的中点差分公式:

最后介绍一个提升精度的方法,定义

那么$\forall 0 <\alpha <1$,计算$D(h),D(\alpha h)$可得

写成矩阵形式得到

求解可得

因此

这说明我们利用$D(h)$和$D(\alpha h)$得到了对$f’(x)$的计算公式,其精度为$O(h^2)$。

本文标题:CS205A Lecture 15 Numerical integration and differentiation

文章作者:Doraemonzzz

发布时间:2019年04月30日 - 20:16:00

最后更新:2019年05月04日 - 21:04:02

原始链接:http://doraemonzzz.com/2019/04/30/CS205A Lecture 15 Numerical integration and differentiation/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。