泰勒公式

概念

泰勒公式是将一个在 $x = x_0$ 处有 $n$ 阶导数的函数 $f(x)$ 利用关于 $(x - x_0)$ 的 $n$ 次多项式来逼近函数的方法。

泰勒公式形式

$$ f(x) = \sum_{i = 0} ^ n \frac{f ^ {(i)}(x_0)}{i!} (x - x_0) ^ i + R_n(x) $$

其中等号后的多项式称为函数 $f(x)$ 在 $x_0$ 处的泰勒展开式，剩余的 $R_n(x)$ 是泰勒公式的余项，也就是 $(x - x_0) ^ n$ 的高阶无穷小。

原理

对于 $f(x)$ 的 $i$ 阶导数，相应地求出泰勒展开式的 $i$ 阶导数，要求两者在 $x_0$ 处的值相同。注意到求 $i$ 阶导数后，导数的常数项对应原函数的 $i$ 次项，因此系数乘上了 $i!$，那么展开式中的 $\frac{f ^ {(i)}(x_0)}{i!}$ 的意义就显而易见了。

故我们可以得到结论：对于展开式中的 $i$ 次项，其控制的是 $\frac{\mathrm{d} ^ i f}{\mathrm{d} x ^ i}(x_0)$。

牛顿迭代法

思想

以下只介绍牛顿迭代法在多项式下的运用。

现在有如下问题：已知一个函数 $G(x)$，求一个模 $x ^ n$ 意义下的多项式 $F(x)$ 满足：

$$ G(F(x)) \equiv 0 \pmod{x ^ n} $$

考虑倍增，假设我们已经求出：

$$ G(F_0(x)) \equiv 0 \pmod{x ^ {\left\lceil\frac{n}{2}\right\rceil}} $$

为了扩展到 $\bmod x ^ n$ 意义下，可以 $G(F(x))$ 在 $F_0(x)$ 下进行泰勒展开：

$$ \begin{align*} G(F(x)) & = \sum_{i = 0} ^ {n - 1} \frac{G^{(i)}(F_0(x))}{i!}(F(x) - F_0(x)) ^ i \end{align*} $$

由于 $F(x)$ 和 $F_0(x)$ 的最后 $\left\lceil\frac{n}{2}\right\rceil$ 项相同，所以 $(F(x) - F_0(x)) ^ 2$ 的最后 $2 \cdot \left\lceil\frac{n}{2}\right\rceil$ 项的系数均为 $0$，所以可以得到：

$$ G(F(x)) \equiv G(F_0(x)) + G'(F_0(x))\cdot (F(x) - F_0(x)) \pmod{x ^ n} $$

由于 $G(F(x)) \equiv 0 \pmod{x ^ n}$，得到：

$$ F(x) \equiv F_0(x) - \frac{G(F_0(x))}{G'(F_0(x))} \pmod{x ^ n} $$

这个式子和一般的牛顿迭代 $x = x_0 - \frac{f(x_0)}{f'(x_0)}$ 很相似，但注意这是在多项式意义下的扩展！

运用

其实多项式开方、多项式指数函数等都是牛顿迭代法的运用。