======Approximations======
//MITx: 18.01.1x Calculus 1A notes//
----
\\
在处理实际问题的过程中，函数的表达式可能会非常复杂。而近似计算则是利用另外一个相对简单的多项式函数去逼近目标函数的某一部分，从而得到指定定义域内（或者某个点的）函数近似值。对于处理一些不可解的函数关系来说，通过利用多项式的特性来进行近似的手段，是非常有效的。近似计算的精度与多项式的阶数有关，比如本章要讨论的线性近似，二次近似，以及以后的泰勒公式。
====线性近似与测量误差====
===基础函数的线性近似===
线性近似（//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)$$
\\
\\
具体推导过程请查看[[math:calculus:mooc:mit_1801x:a:differentiation#线性近似的公式推导|第三章微分1.1节]]。
常见函数的的线性近似结果（$x$ 在 $0$ 附近的情况）
* $(1+x)^r \approx 1+rx$
* $sin(x) \approx x$
* $cos(x) \approx 1$
* $e^x \approx 1+x$
* $ln(1+x) \approx x$
===复合形式的线性近似===
本小节也讨论的是 $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))$ 的形式出现时，通常我们会令 $u = g(x)$。如果希望使用线性近似，那么 $u$ 需要与 $0$ 非常接近。**如果可以直接由** $x \to 0$ **推导出** $u \to 0$（比如 $u = kx$），那么计算的方式是：
- 使用 $u$ 对 $f(u)$ 进行近似计算
- 再将 $u = g(x)$ 带入到之前的计算结果中
如果不行，则需要考虑 $u$ 在哪种情况下可以推导出 $x \to 0$。这种情况下计算的方式是：
- 找到当 $x \to 0$ 时，$u$ 对应 $x$ 的表达式：比如 $u \to 1$，当 $x \to 0$ 时， $u = 1 + x$
- 使用带 $x$ 的表达式进行近似计算
- 计算完毕之后将 $x$ 对于 $u$ 的表达式带入到计算结果中。最终结果会以 $u$ 为自变量的形式呈现
总的来说，计算复合函数的线性近似只有两种方法：
* 如果想要利用之前已经计算的好的公式，那么需要满足 $g(0) = 0$。在原有自变量不趋近于 ''0'' 的情况下，通常的做法是使用新的自变量替代前的自变量，使新的自变量趋近于 ''0''。 比如 $x \to 1$ 时：
* 使用 $u = x - 1$
* 这样 $u\to 0$
* 此时满足 $g(u) = 0$，就可以使用那些公式了。
* 求得近似表达式之后，再将 $u$ 以 $x$ 的形式带入到表达式中，即可得到最终结果。
* 如果不使用替代法，可以使用线性近似公式的**两点形式**直接进行计算。
在使用换元法进行线性近似的计算时，结果中的高次项需要谨慎处理。通常来说，高次项的处理（舍弃）应该**先于**将替换后的变量带入到替换前的变量。比如：$x \to 1$，使用 $u = x - 1$ 进行替换并计算线性近似。已求得线性近似的结果 $u^2$，那么此时我们应该舍弃的高次项是 $u^2$，也就是整个 $(x-1)^2$，而不是将 $u = (x-1)$ 带入到 $u^2$ 中后再展开，再舍弃其中的 $x^2$项。\\ \\
一个判定高次项的舍弃是否合法的标准是，看该高次项的值。高次项之所以被舍弃，是因为在近似结果中，高次项带来的误差非常小。以之前的例子来说，$u\to 0$，那么舍弃 $u^2$ 是没有什么影响的；但 $x\to 1$，舍弃 $x^2$ 则会对最后的结果造成很大的影响。
==一个例外==
\[
\begin{align*}
(1+x^2)^{-1} &= {(1+u)}^{-1}\\\\
&\approx 1-u \\\\
&= 1-x^2\\\\
\end{align*}
\]
此处令 $u = x^2$ 即可进行线性近似。但最终得到的结果是 $1-x^2$。当然， $x^2$ 在 $x \to 0$ 时 等于 $0$，但作为近似的结果，需要尽可能地保留细节，因此此处的 $x^2$ **不需要做进一步的处理**。
==正式的定义==
>Suppose that $g(x)$ is a function such that $g(0) = 0$. To find an approximation of a function $f(g(x))$ **near** $x=0$ , we can take a linear approximation for $f(u)$ and then substitute g(x) in for $u$ .
>**The resulting approximation is likely nonlinear, but it is still an linear approximation**!.
>Warning: this **only works** if $g(0) = 0$ .
>$$\displaystyle \displaystyle f(u) \approx f(0) + f'(0)u \qquad \Longrightarrow \qquad f\left(g(x)\right) \approx f(g(0)) + f'(g(0))g(x)$$
===Error approximation===
误差一般是属于因变量的变化，而该变化量可以通过自变量的变化来求得。通常来讲，如果有 $y =f(x)$，那么我们就可以通过以下关系来求出 $\Delta y$：
\\
\\
$$y + \Delta y =
f(x + \Delta x)$$
\\
\\
这样因变量的变化值往往可以用自变量的变化值来表示。并且，在有多个自变量的函数中，我们可以通过近似计算的复合来评估多变量公式带来的误差。
在误差的线性近似计算中，由于变化量才是表达式中的自变量，因此需要舍弃的高次项是**变化量的乘积**。比如测量速度时，时间与距离同时存在误差 $\Delta t$ 与 $\Delta x$，那么近似计算后表达式中的 $\Delta x \cdot \Delta t$ 选项是要去掉的。
课程中的例子补充-整个例子讲述的是：
- 首先通过公式预测楼的高度
- 其次推导出各个因子的误差值与楼高度的关系，并带入具体的因子误差值计算理论上的高度误差值
- 最后将真实的高度值与预测值相减，得到真实的误差值，并与理论上计算的误差值（//error magnitude//）进行比较。结果真实的误差值小于理论的误差值，说明该预测结果是在允许的范围之内的。
====二次近似====
==几何观点下的近似函数==
如果线性近似代表的函数 $L(x)$ 同时满足一下两个条件：
* $L(x)$ 过目标函数 $f(x)$ 的某一点
* $L(x)$ 与 $f(x)$ 在该点的导数相同
那么我们称 $L(x)$ 为 $f(x)$ **最佳匹配**（//Best Fit//）。也就是说，线性近似可以被解释为函数在某点的最佳匹配。
==二次近似的几何意义==
通过以上两个信息，我们可以借由切线的方程在一定程度内对目标函数做出近似计算。但这样的计算是不精确的。根据以上两个信息，我们并不能判断目标函数在该点附近的**凹凸性**（//Concavity//)。这对于近似的结果来说有很明显的影响：目标函数可能在切线的上方或者下方。而我们知道，凹凸性是可以通过二阶导数来判断的；因此，如果知道了目标函数在某一点的二阶导数值，我们也就可以利用这个信息使近似计算的误差变得更小。这样的近似方法，我们称为**二次近似**（//Quadratic Approximation//）。
\\
\\
{{ math:calculus:mooc:mit_1801x:a:quadratic-min.png?400 |}}
\\
\\
显然的是，二次近似的最佳匹配满足三个条件。假设目标函数为 $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}
\\
\\
将上面的 $a,b,c$ 系数以 $f(0)$ 的形式带入二次近似函数，则可得到 $f(x)$ 在近 ''0'' 处的近似表达式：
\\
\\
$$\displaystyle f(x) \approx f(0) + f'(0)x + \frac{f^{\prime \prime }(0)}{2}x^2$$
\\
将上面得到的公式中的 ''0'' 替换为点 $a$ 并应用到近似的两点形式中，可得：
\\
\\
$$\displaystyle f(x) \approx \underbrace{ f(a) + f'(a)(x-a)}_\text {Linear Approximation} + \underbrace{\frac{f^{\prime \prime }(a)}{2}(x-a)^2}_\text{Quadratic term}$$
\\
\\
常见函数的二次近似结果（ $x$ 在 $0$ 附近的情况）
* ${e^ x = 1 + x + \frac{x^2}{2} + O\left(x^3\right)}$
* $\displaystyle {\sin (x) = x}$
* $\displaystyle {\cos (x) = 1- \frac{x^2}{2}}$
* $\displaystyle {\ln (1+x) = x- \frac{x^2}{2}}$
* $\displaystyle {(1+x)^ r = 1 + rx + \frac{r(r-1)}{2}x^2}$
===积的二次近似===
**如果一个函数由两个函数相乘而得，那么这个函数的二次近似等于组成其函数的二次近似相乘的结果**。简单的证明如下：
\\
\\
令$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}
\\
因为二次近似的乘积最终表现形式也是一个一元二次多项式，因此我们可以将相乘以后高于二次的项都丢弃，整理出来的结果为：
\\
\\
\begin{align}
Q(f) \cdot Q(g)
& \approx f(0) \cdot 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 \newline
& = f(0) \cdot g(0) + \textcolor{red}{( f(0)\cdot g(0))'} \cdot x + \frac{\textcolor{red} {(f(0) \cdot g(0))''}}{2} \cdot x^2
\end{align}
\\
===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^2$ 项决定了整个误差的大小。比如将 $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$.
具体计算中：
* //Order of magnitude// 实际上就是 $x^n$ 的位数。比如 $x = 0.2$, $x^3 = 0.008 = 8*10^{-3}$ ，则 $x^3$ 的 $O$ 就是 $10^{-3}$
* 求 $k$ 需要先求得**总的误差**是多少，再用误差除以**对应项**（比如线性近似就是 $x^2$）的 $O$ 即可。
推测：近似结果应该在没有当前 term 的情况下保留高项，而在存在当前 term 的情况下去掉高项。
====Newton-Raphson method====
之前提到的两种近似方案都需要近似点与目标点足够接近。但当需要对目标函数的根，也就是目标函数与 $x$ 轴的交点位置进行近似时，由于我们并不确定该点与近似点的距离有多远，使用传统的近似方法可能会带来较大的误差。这种情况下，需要利用到牛顿方法。
\\
\\
{{ math:calculus:mooc:mit_1801x:a:450px-newtoniteration_ani.gif |}}
\\
\\
//图片来源//：[[https://zh.wikipedia.org/wiki/%E7%89%9B%E9%A1%BF%E6%B3%95#/media/File:NewtonIteration_Ani.gif|Wikipedia]]，作者：//Ralf Pfeifer//
\\
\\
从上图可以看出，牛顿法的原理是**反复利用线性近似**去使得近似点逐渐逼近目标函数与 $x$ 轴的焦点。其核心内容主要是在重复做两件事：
* 确定函数上一点，计算过该点的切线方程，以及该切线方程与 $x$ 轴的交点
* 以该交点的 $x$ 坐标为基础，寻找到函数上对应的点，根据该对应的点求出过该点的切线，并继续求该切线与 $x$ 轴的交点
这两步会反复的进行，直到我们发现得到的切线与 $x$ 的交点会处于非常稳定（收敛）的一个值，那么就可以确认得到的近似值非常接近函数的根值了。
==具体步骤==
- 先猜测一个值 $x_0$。
- 通过这个 $x_0$ 得到对应目标函数上的点，并通过该点对目标函数做线性近似。
- 通过得到的线性近似方程求解（与 $x$ 轴的焦点）
- 将求到的解作为新的猜测值，重复以上步骤，直到解收敛。
===通项公式推导过程===
假设目标函数的方程为 $f(x)$，起始的猜测点为 $x_0$，那么该方程在 $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$
通过前一节 $O$ 的相关知识（线性近似），可知误差的 //Order of magnitude// 为 $x$ 的平方：
\\
\\
\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}
\\
\\
根据这个结果可以推导出，$ε_n = O(ε_{n-1}^2) = O(ε_{n-2}^4)...$，也就是说误差在以 $x^2$ 的规模减小，也就是收敛程度为二阶。
==一些不收敛的情况==
不收敛的情况大概分四种：
- 误差越来越大
- 循环震荡的不收敛，即 $f(-x) = -f(x)$，也就是 $x_{n+1} = -x_n$
- 猜测点位于驻点（$f'(x_n)$ 太小，导致得到的解太大。图像上为切线几乎与 $x$ 轴平行）
- 不能完整求出所有的根
==避免不收敛的 tips==
* 挑选方程式，要近似的对象最好为方程的根
* 方程的挑选要避免要避免 $f(x) = f'(x) = 0$ 这类情况。这类情况下，误差收敛的速度会非常慢
* 选择初始猜测点时，该点的导数在函数上的斜率不能太“平”（靠近 $x$ 轴）。太平会使得到 root 太大，导致近似的结果偏移到另外一个 root，或是无法收敛
====典型题目====
===函数为商的形式===
某些函数表现为 $\frac{p(x)}{q(x)}$ 的形式。这种情况下需要有两点要注意：
* 看题目要求的**近似是什么数量级**。这一点非常关键，因为涉及到商时，数量级本身也会进行相除。比如，$p(x)$ 是线性近似，$q(x)$ 也是线性近似，那么相除之后得到的是常数级的近似结果，而不是线性近似。
* 近似的商不等于商的近似
来看一个典型例题：\\ \\
Find the linear approximation of $\displaystyle \frac{\ln (1+x)}{xe^x}$ near $x = 0$ \\ \\
这道题同时具有上述的两个坑。首先我们会想到的是算出 $ln(1+x)$ 和 $e^x$ 的线性近似，然后相除，也就是
\begin{align}
\displaystyle \frac{\ln (1+x)}{xe^x}
&\approx \frac{x}{x\cdot (1+x)} \newline
&= \frac{1}{x+1}
\end{align}
这样做显然是错误的。首先，分子与分母都是线性近似的结果，相处以后得到的近似结果是常数级别的；但本题要求的是线性近似。其次，由于线性近似的乘积等于乘积的线性近似，对于 $e^{-x}$，该近似结果不能直接进行相除，而是要转化为乘积的形式进行再次近似，最终得到的结果才能使用。因此正确的求解有两个要点：
* 对 $ln(1+x)$ 进行二次近似，保证商之后得到的结果时线性级的
* 转化$1/e^x$ 的结果为乘积形式，并再次进行线性近似
\begin{align}
\displaystyle \frac{\ln (1+x)}{xe^x}
&\approx \frac{{\color{red} x+\frac{x^2}{2}} }{x\cdot (1+x)} \newline
&= \frac{1+\frac{x}{2} }{x+1} \newline
&= (1+\frac{x}{2}) \cdot(x+1)^{-1} \newline
&\approx (1+\frac{x}{2}) \cdot{\color{red} (1-x)} \newline
&=1- \frac{3}{2} x
\end{align}
====参考与扩展====
* [[https://www.zhihu.com/question/20690553|如何通俗易懂地讲解牛顿迭代法求开方？]]
