利用牛顿迭代法开根号

Posted on Edited on Views:

正好课上讲到开根号的迭代公式，写篇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)\)的根足够近。其实根据可视化，这个过程一目了然，但本人能力有限，暂时做不出来，在此贴上一个我觉得不错的链接，感兴趣的可以阅读一下。

https://www.zhihu.com/question/20690553/answer/925196172

粗糙的代码（python）

求\(\sqrt{17}\)的代码，十分粗糙...

1
2
3
4
5
6
x = 1
a = 17
acc = 1e-5
while abs(x*x-17) >= acc:
    x = (x+a/x)/2
print(x)

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