What & How & Why

Approximations / 近似计算


所有 math 条目下的内容均以极不严谨的个人理解方式书写,请见谅!
因个人水平极其有限,我撰写的 wiki 内容不免出现大量纰漏。如果您发现错误,请留言提出,谢谢!


在处理实际问题的过程中,函数的表达式可能会非常复杂。而近似计算则是利用另外一个相对简单的多项式函数去逼近目标函数的某一部分,从而得到指定定义域内(或者某个点的)函数近似值。对于处理一些不可解的函数关系来说,通过利用多项式的特性来进行近似的手段,是非常有效的。近似计算的精度与多项式的阶数有关,比如本章要讨论的线性近似,二次近似,以及以后的泰勒公式。

线性近似与测量误差

线性近似(Linear Approximation)的原理是利用原函数某点的切线作为该函数的表达式。在一个变化足够小的范围内,切线代表的函数结果是可以用于表示原函数在该点的值的。线性近似主要讨论的有两种情况:

  • When Linear Approximations near $x=0$.
  • General representation When Linear Approximations near $x_0$,where $x_0$ is very close to $x$.

对于第一种情况来说,线性近似的表达式可以记做:

$$f(x) \approx f(0) + f'(0)x$$

而对于一般情况来说,已知函数过点 $x_0, f(x_0)$,那么该函数上处于点 $x$ 处的值 $f(x)$ 的线性近似的表达式可以记做:

$$f(x) \approx f(x_0) + f'(x_0)(x-x_0)$$

具体推导过程请查看第三章微分1.1节

Combining approximations

本处主要讨论的是 $x=0$ 处的近似复合规则。


我们需要对某些复合的函数进行近似计算。复合的情况主要分以下三种:

  1. 数字列表项目目标函数是两个函数的和
  2. 目标函数是两个函数的乘积
  3. 目标函数的自变量是其中一个函数

加法和乘法都非常简单,即目标函数的近似结果等于两个函数的近似结果的,比如:


\begin{align} h(x) = f(x) + g(x) \approx &(f(0)+f'(0)x) + (g(0) +g'(0)x)\\\\ h(x) = f(x)\cdot g(x) \approx &(f(0)+f'(0)x) \cdot (g(0) +g'(0)x) \end{align}
一个函数作为自变量的复合形式为 $f(g(x))$。按照前提,我们希望计算 $f(u)$ 在 $0$ 处的近似结果,因此必须满足 $u=0$,也就是 $g(0)=0$。

这种情况下需要考虑将 $u$ 在 $0$ 处的值。如果不为 $0$,可以考虑通过变形的手段来得出,比如:

\begin{align} (1+x^2)^{-1} &= {(1+u)}^{-1}\\\\ &\approx 1-u \\\\ &= 1-x^2\\\\ \end{align} 此处令 $u = x^2$

Error approximation

因为我们采用了近似计算,所以误差一定会伴随而来。有时候我们需要用误差来评估一些计算,因此误差计算也是非常重要的。

误差一般是属于因变量的变化,而该变化量可以通过自变量的变化来求得。通常来讲,如果有 $y =f(x)$,那么我们就可以通过以下关系来求出 $\Delta y$:

$$y + \Delta y = f(x + \Delta x)$$

这样因变量的变化值往往可以用自变量的变化值来表示。并且,在有多个自变量的函数中,我们可以通过近似计算的复合来评估多变量公式带来的误差。

Quadratic approximation

通过线性逼近,我们可以很容易获取一些信息:

  • 目标函数过某个点
  • 目标函数在某个点的切线

通过以上两个信息,我们可以借由切线的方程在一定程度内对目标函数做出近似计算。但这样的计算是不精确的。根据以上两个信息,我们并不能判断目标函数在该点附近的凹凸性Concavity)。这对于近似的结果来说有很明显的影响:目标函数可能在切线的上方或者下方。而我们知道,凹凸性是可以通过二阶导数来判断的;因此,如果知道了目标函数在某一点的二阶导数值,我们也就可以利用这个信息使近似计算的误差变得更小。这样的近似方法,我们称为二次近似Quadratic Approximation)。

显然的是,二次近似需要满足三个条件。假设目标函数为 $f(x)$,二次近似的得到的函数为 $q(x)$,那么在点$x_0$处显然有:

\begin{align} f(x_0) &=q(x_0)\\\\ f'(x_0) &=q'(x_0)\\\\ f''(x_0) &=q''(x_0) \end{align}

二次逼近是用一个二次多项式函数来近似目标函数的。假设我们用于逼近目标函数的二次多项式函数为 $f(x) = ax^2+bx+c$。当 $x=0$ 的时候,很容易得出:

\begin{align} f(0) &=q(0)=c\\\\ f'(0) &=q'(0)=b\\\\ f''(0) &=q''(0) =2a\\\\ \end{align}

因此,$f(x) = ax^2+bx+c$ 的公式用导数来表示的话,则有如下式子:

$$\displaystyle f(x) \approx f(0) + f'(0)x + \frac{f^{\prime \prime }(0)}{2}x^2$$
将上面得到的公式中的$0$ 应用到通用格式(即用 $(x-a)$ 表示 $x$)中,就可以写成如下形式:

$$\displaystyle f(x) \approx f(a) + f'(a)(x-a) + \frac{f^{\prime \prime }(a)}{2}(x-a)^2$$

积的二次逼近

如果一个函数由两个函数相乘而得,那么这个函数的二次逼近等于组成其函数的二次逼近相乘的结果。该 rule 的证明十分简单:

令$f、g$ 分别为上述的两个组成函数,根据 production rule 有:

\begin{align} (fg)' &= fg' + g'f\\\\ (fg)'' &= f''g + 2f'g' + fg'' \\\\ \end{align}
将$f、g$ 分别代入二次逼近公式,并相乘,可得:
\begin{align} Q(f) \cdot Q(g) &= \left(f(0)g + f'(0)x + \frac{f''(0)}{2}x^2\right) \cdot \left(g(0) + g'(0)x + \frac{g''(0)}{2}x^2\right) \end{align}
因为二次逼近的乘积最终表现形式也是一个一元二次多项式,因此我们可以将相乘以后高于二次的项都丢弃,整理出来的结果为:
$$ Q(f) \cdot Q(g) \approx f(0)g(0) + \left(f'g(0) +fg'(0) \right)x+ \left( \frac{fg''(0)}{2} + \frac{gf''(0)}{2} + f'g'(0) \right) x^2 $$
上面的结果跟我们把直接求出来的导数和二次导数带到二次多项式里的结果是一致的。

Big-O notation

我们来看一个函数:
$$y=(1+x)^5$$
将这个函数展开以后,有:
$$(1+x)^5 = 1+5x+10x^2+10x^3+5x^4+x^5$$
如果求该函数的线性逼近,则可得:
$$(1+x)^5 \approx 1+5x$$
如果求该函数的二次逼近,则有:
$$(1+x)^5 \approx 1+5x+10x^2$$
当 $x \to 0$ 的时候,随着 $x$ 的减小,误差部分的值会越来越小,直到可以忽略。近似计算就是利用这样的原理。而从表现形式上来说,我们就可以将一个多项式写成它自身的近似计算结果加上另外一部分(误差)的形式,即:
$$Function = Approximation + Error$$
那么最后这一部分误差的值,则成为了衡量一个近似计算方法精度的标准了,误差越小,当然精度就越高了。

为了更精确的评估这个精度,我们定义了一个值 $O$ (big-O) 来作为评估的标准。$O$ 的原本含义是数量级(Order of magnitude),在一个 $n$ 阶的多项式中,$O$ 代表了误差的最大值上限;而这个上限可以用一个常数的乘积和该多项式误差的最低项所得到的结果再取绝对值表示。因为在 $x$ 足够小的时候,误差的最低项对误差的结果是作用最大的



比如前面的例子,如果是线性逼近在 $x=0.1$ 时的 $O$ ,那么就有:
$$O = 10x^2+10x^3+5x^4+x^5$$
将 $x=0.1$ 带入计算,发现这个值是小于 $12x^2$。

显然,当 $x$ 足够小时,高于近似计算最高项的项都可以忽略不计;也就是说,对于不同的多项式,我们都可以找到对应的常数 $k$,使得多项式小于等于其误差的最低项与 $k$ 相乘的绝对值。因此,$O$ 的自变量,代表了这个近似计算精确度的数量级;比如上述的线性近似的精度数量级就是$x^2$ 级别的,记做 $f(x) = O(x^2)$。正式的定义如下:

A function $f(x)$ is on the order $x^n$ near $x=0$, which is denoted using big “O“ notation as $f(x) = O(x^n)$ near $x=0$, if $\left|f(x)\right| \leq k x^ n$.

Newton-Raphson method

前面说到的两种近似方法都需要一个很重要的前提:要近似的点与目标函数必须要足够近。如果已知的点并不靠近目标函数,那么我们在使用得到的近似方程求根(root)时,误差有可能会很大。

为了解决这个问题,伊萨克牛顿提出了一种重复利用线性近似的算法来对根猜测,从而最终逼近正确结果。来看看这个方法是如何达到这样的效果的:




图片来源Wikipedia,作者:Ralf Pfeifer


根的几何意义就是函数与 $x$ 轴的交点,因此我们只需要求出 $y=0$ 的时候 $x$ 的值就好了。但很明显,某些函数长得稀奇古怪,你是根本没法用代数方法来求解的。那怎么办呢?

当然用到线性近似啦。既然没有办法直接求解,那就通过线性近似来先找到一个可解的方程,再求这个一次方程与 $x$ 轴的焦点不就行了吗?

不过这样误差会比较大,因为线性近似得出的方程只能用于已知点附近的区域;而我们并不知道需要求根的函数与 $x$ 轴的交点与我们线性近似使用的点距离有多远。

牛顿们说,这好办!既然一次误差大,那我们就多求几次好了!于是就使用线性近似求到的解(先前得到的线性近似方程与 $x$ 轴的焦点)作为新的猜测点,再来一轮。

反复多来几次,我们发现每次线性近似与 $x$ 轴的焦点都会与真正的解越来越近,直到某一刻两点的误差被忽略。

总结一下牛顿迭代法求根步骤:

  1. 因为我们不知道根哪里,所以先猜测一个值 $x_0$。
  2. 然后通过这个 $x_0$ 得到对应目标函数上的点,并通过该点对目标函数做线性近似。
  3. 通过得到的线性近似方程求解(与 $x$ 轴的焦点)
  4. 将求到的解作为新的猜测值,重复以上步骤,直到解收敛。

通项公式推导过程

假设目标函数的方程为 $f(x)$,起始的猜测点为 $x_0$,那么该方程的线性近似则为:
$$f(x) = f(x_0) + f'(x_0)(x-x_0) $$
因为我们需要求线性近似方程的解,因此令 $f(x) = 0$,则有:
$$f(x_0) + f'(x_0)(x-x_0) = 0$$
通过该等式求 $x$,即可得到牛顿迭代法的公式:

$$ \displaystyle x_1 = x_0 - \frac{f(x_0)}{f'(x_0)} $$

考虑到我们需要反复应用该等式来逼近正确的解,因此可以将该方程写成:

$$ \displaystyle x_{n+1} = x_ n - \frac{f(x_ n)}{f'(x_ n)} $$

牛顿迭代法的收敛性质

我们可能会有疑问,牛顿迭代法在什么情况下是适用;也就是说,在什么条件下才会让解收敛?当然,如果想知道一个算法是否是收敛的,我们可以从误差着手。当误差越来越逼近 $0$ 的时候,我们就可以认为算法是收敛的。

假设我们从第一步开始。为了看误差到底是怎么样变化的,我们需要两个误差值,即第一次计算的误差 $ \epsilon_0$ 和 第二次计算的误差 $\epsilon_1$。令方程真正的解为 $x^*$,那么我们有如下的几个式子:

  • $ε_0 = x^* - x_0$
  • $ε_1 = x^* - x_1$
  • $f(x^*) = 0$ (x^* 是方程真正的解)

通过前一节 $O$ 的相关知识,我们可以写出如下的式子:

\begin{align} f(x^*) &= f(x_0) + f'(x_0)(x^* - x_0) + O((x^*-x_0)^2)\\\\ &=f(x_0) + f'(x_0)ε_0 + O(ε_0^2) \end{align}
因为 $f(x^*) = 0$,因此有:
\begin{align} f(x_0) + f'(x_0)ε_0 + O(ε_0^2) = 0\\\\ f(x_0) = -f'(x_0)ε_0 + O(ε_0^2) \tag{3.1} \end{align}

注意这里 $ O(ε_0^2)$ 本身应该为负,但 $O$ 代表了数量级,因此正负并不重要。通常情况下均用加上 $O$ 表示。

再通过牛顿迭代法,我们可以得到$x_1$ 的值如下:
$$ x_1 = x_0 - \frac{f(x_0}{f'(x_0)} $$
那么$ε_1$ 的值就可以写成如下形式:

\begin{align} ε_1 &= x^* - x_1\\\\ &= x^* - \left(x_0 - \frac{f(x_0}{f'(x_0)} \right)\\\\ &= x^* - x_0 + \frac{f(x_0}{f'(x_0)} \tag{3.2} \end{align}

将先前得到的公式 3.1 带入 3.2,则有:

\begin{align} ε_1 &= x^* - x_0 + \frac{f(x_0}{f'(x_0)}\\\\ &=ε_0 + \frac{-f'(x_0)ε_0 + O(ε_0^2)}{f'(x_0)}\\\\ &=ε_0 - ε_0 + \frac{O(ε_0^2)}{f'(x_0)}\\\\ &=O(ε_0^2) \end{align}

很显然,这样依次迭代下去,误差会越来越小,最终会无限逼近于 $0$。从上面的推导也能看出来,牛顿迭代法是二阶收敛的。

一些不收敛的情况

不收敛的情况大概分四种:

  1. 误差太大(大于1)
  2. 循环震荡的不收敛
  3. 猜测点位于驻点($f'(x_n)$ 太小,导致得到的解太大。图像上为切线几乎与 $x$ 轴平行)
  4. 不能完整求出所有的根


具体的例子可以参考 如何通俗易懂地讲解牛顿迭代法求开方? 一文中 马同学 的回答。

Appx A:常用线性近似函数公式

注:以下公式均只适用于 $x=0$ 的条件下。


  • $sin(x) \approx x$
  • $ cos(x) \approx 1$
  • $ e^x \approx 1+x$
  • $ n(1+x) \approx x$
  • $ (1+x)^r \approx 1+rx$

Appx B:常用二次近似函数公式

注:以下公式均只适用于 $x=0$ 的条件下。


  • ${e^ x = 1 + x + \frac{x^2}{2} + O\left(x^3\right)}$
  • $\displaystyle {\sin (x) = x + O\left(x^3\right)}$
  • $\displaystyle {\cos (x) = 1- \frac{x^2}{2} + O\left(x^3\right)}$
  • $\displaystyle {\ln (1+x) = x- \frac{x^2}{2} + O\left(x^3\right)}$
  • $\displaystyle {(1+x)^ r = 1 + rx + \frac{r(r-1)}{2}x^2 + O\left(x^3\right)}$




参考与扩展