正好课上讲到开根号的迭代公式，写篇blog推导一下。

需要解决的问题

怎么求对某一个数开根号的数值解？比如$\sqrt{17}$，它的近似值是多少呢？这个问题抽象一下，其实就是求以下非线性方程的数值解。

\[\begin{align*} x^2 = a \end{align*}\]

写作以下形式更方便之后的推导：

\[\begin{align*} f(x) = x^2 - a = 0 \end{align*}\]

在介绍牛顿迭代法之前，先来复习一下泰勒展开的内容。

泰勒展开

对于函数$f(x)$，在$(x_0, f(x_0))$这个点进行泰勒展开，可以作如下近似：

\[f(x) = f(x_0) + f^\prime(x_0)(x-x_0) + \frac{1}{2}f^{\prime\prime}(x_0)(x-x_0)^2 + \cdots + \frac{f^{(n)}}{n!}(x-x_0)^n\]

中国农业大学的陈研教授开的数值计算方法的课程中，对泰勒展开的理解我个人感觉非常巧妙，以后再写。

牛顿迭代法

牛顿迭代法其实非常简单，我们只取一阶近似：

\[\begin{align*} f(x)\approx f(x_0) + f^\prime(x_0)(x-x_0) \end{align*}\]

我们在一开始也提到，非线性方程可以写作$f(x) = 0$。那么就有如下公式：

\[\begin{align*} f(x_0) + f^\prime(x_0)(x-x_0) = 0 \end{align*}\]

要时刻想清楚我们想求的东西是什么。这个问题我们要求的东西是解，是$x$。所以利用初中知识做一些数学上的变换：

\[\begin{align*} f^\prime(x_0)(x-x_0) &= -f(x_0)\\ x - x_0 &= -\frac{f(x_0)}{f^\prime(x_0)}\\ x &= x_0 - \frac{f(x_0)}{f^\prime(x_0)} \end{align*}\]

（看到分母我们就应该想到它是不能等于0的，所以接下来的推导也都基于$f^\prime(x_0) \neq 0$这个假设）

然而，我们只是随便取的一个点，想要一步就求出解那也有点过于异想天开了。我们接下来还需要做一件事情，就是迭代。

\[\begin{align*} x_1 &= x_0 - \frac{f(x_0)}{f^\prime(x_0)}\\ x_2 &= x_1 - \frac{f(x_1)}{f^\prime(x_1)}\\ \vdots \\ x_k &= x_{k-1} - \frac{f(x_{k-1})}{f^\prime(x_{k-1})} \end{align*}\]

OK，回到我们要解决的问题上来。

\[\begin{align*} f(x) &= x^2 - a\\ f^{\prime}(x) &= 2x \end{align*}\]

那么，迭代的公式就可以写作（这里的等号是赋值的意思，利用程序化的语言来写了）：

\[\begin{align*} x &= x - \frac{x^2-a}{2x}\\ &= \frac{2x^2-x^2+a}{2x} \\ &= \frac{x^2+a}{2x}\\ &= \frac{x + \frac{a}{x}}{2} \end{align*}\]

几何意义

来，看一下这个东西到底是什么。

\[f(x_0) + f^\prime(x_0)(x-x_0) = 0\]

是不是和$f(x)$在$x_0$处的切线方程非常类似？没错。那么我们这里求出来的$x$是什么呢？其实是这条切线与$x$轴的交点。我们在做的事情，其实就是一直找这个交点，直到它和函数$f(x)$的根足够近。其实根据可视化，这个过程一目了然，但本人能力有限，暂时做不出来，在此贴上一个我觉得不错的链接：这篇知乎上的可视化讲解，感兴趣的可以阅读一下。

粗糙的代码（python）

求$\sqrt{17}$的代码，十分粗糙…

有意思的是，我们知道开平方是有两个根的，我们只要把初始值取为负数，得到的就会是负根。