本 Wiki 开启了 HTTPS。但由于同 IP 的 Blog 也开启了 HTTPS,因此本站必须要支持 SNI 的浏览器才能浏览。为了兼容一部分浏览器,本站保留了 HTTP 作为兼容。如果您的浏览器支持 SNI,请尽量通过 HTTPS 访问本站,谢谢!
所有 math 条目下的内容均以极不严谨的个人理解方式书写,请见谅!
因个人水平极其有限,我撰写的 wiki 内容不免出现大量纰漏。如果您发现错误,请留言提出,谢谢!
在处理实际问题的过程中,函数的表达式可能会非常复杂。而近似计算则是利用另外一个相对简单的多项式函数去逼近目标函数的某一部分,从而得到指定定义域内(或者某个点的)函数近似值。对于处理一些不可解的函数关系来说,通过利用多项式的特性来进行近似的手段,是非常有效的。近似计算的精度与多项式的阶数有关,比如本章要讨论的线性近似,二次近似,以及以后的泰勒公式。
线性近似(Linear Approximation)的原理是利用原函数某点的切线作为该函数的表达式。在一个变化足够小的范围内,切线代表的函数结果是可以用于表示原函数在该点的值的。线性近似主要讨论的有两种情况:
对于第一种情况来说,线性近似的表达式可以记做:
$$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节。
本处主要讨论的是 $x=0$ 处的近似复合规则。
我们需要对某些复合的函数进行近似计算。复合的情况主要分以下三种:
加法和乘法都非常简单,即目标函数的近似结果等于两个函数的近似结果的和或积,比如:
\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$
因为我们采用了近似计算,所以误差一定会伴随而来。有时候我们需要用误差来评估一些计算,因此误差计算也是非常重要的。
误差一般是属于因变量的变化,而该变化量可以通过自变量的变化来求得。通常来讲,如果有 $y =f(x)$,那么我们就可以通过以下关系来求出 $\Delta y$:
$$y + \Delta y =
f(x + \Delta x)$$
这样因变量的变化值往往可以用自变量的变化值来表示。并且,在有多个自变量的函数中,我们可以通过近似计算的复合来评估多变量公式带来的误差。
通过线性逼近,我们可以很容易获取一些信息:
通过以上两个信息,我们可以借由切线的方程在一定程度内对目标函数做出近似计算。但这样的计算是不精确的。根据以上两个信息,我们并不能判断目标函数在该点附近的凹凸性(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
$$
上面的结果跟我们把直接求出来的导数和二次导数带到二次多项式里的结果是一致的。
我们来看一个函数:
$$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$ 足够小的时候,误差的最低项对误差的结果是作用最大的。
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$.
前面说到的两种近似方法都需要一个很重要的前提:要近似的点与目标函数必须要足够近。如果已知的点并不靠近目标函数,那么我们在使用得到的近似方程求根(root)时,误差有可能会很大。
为了解决这个问题,伊萨克牛顿提出了一种重复利用线性近似的算法来对根猜测,从而最终逼近正确结果。来看看这个方法是如何达到这样的效果的:
图片来源:Wikipedia,作者:Ralf Pfeifer
根的几何意义就是函数与 $x$ 轴的交点,因此我们只需要求出 $y=0$ 的时候 $x$ 的值就好了。但很明显,某些函数长得稀奇古怪,你是根本没法用代数方法来求解的。那怎么办呢?
当然用到线性近似啦。既然没有办法直接求解,那就通过线性近似来先找到一个可解的方程,再求这个一次方程与 $x$ 轴的焦点不就行了吗?
不过这样误差会比较大,因为线性近似得出的方程只能用于已知点附近的区域;而我们并不知道需要求根的函数与 $x$ 轴的交点与我们线性近似使用的点距离有多远。
牛顿们说,这好办!既然一次误差大,那我们就多求几次好了!于是就使用线性近似求到的解(先前得到的线性近似方程与 $x$ 轴的焦点)作为新的猜测点,再来一轮。
反复多来几次,我们发现每次线性近似与 $x$ 轴的焦点都会与真正的解越来越近,直到某一刻两点的误差被忽略。
总结一下牛顿迭代法求根步骤:
假设目标函数的方程为 $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^*$,那么我们有如下的几个式子:
通过前一节 $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$。从上面的推导也能看出来,牛顿迭代法是二阶收敛的。
不收敛的情况大概分四种:
具体的例子可以参考 如何通俗易懂地讲解牛顿迭代法求开方? 一文中 马同学 的回答。
注:以下公式均只适用于 $x=0$ 的条件下。
注:以下公式均只适用于 $x=0$ 的条件下。