牛顿拉夫森方法的意外之喜

luyuanhong

牛顿拉夫森方法的意外之喜

原创 围城里的猫 MathSpark 2024 年 06 月 21 日 07:31 陕西

数学并不是总是在人们的意料之中，就像生活并不总是尽如人意那样。你们中的一些人或许有听过牛顿-拉夫森法——这是一种可以用来求多项式或者其他函数根(零点)的方法,可当把这种方法用到复变函数时，惊喜和意外也发生了，这时会产生有趣的分形图案。不过这种分形并不是牛顿发现的，而是因牛顿-拉夫森方法来命名的而已。

在这期推送中，我们将快速介绍所需的背景知识，包括牛顿-拉夫森方法、复数根和复数函数的微分以及分形的概念，最后再看一些牛顿分形的例子。

牛顿拉夫森法

牛顿-拉夫森法提供了一种非常有效的方法来寻找多项式的近似根。如下图所示，我们清楚地看到 0，1，2 分别是多项式的三个根。

但现在我们假装自己不知道，使用该方法来对根的位置进行计算，在下面左侧的图中，我们选择了 x = 2.4 的初始猜测，并在图中标记了 x 为 2.4 的点。然后我们在该点处画一条曲线的切线，并找出该切线与 x 轴的交点。从下图（左侧）我们可以看到切线在约 2.1 处与 x 轴相交：



现在用新的估计值 2.1 替换我们原来的估计值 2.4 ，然后重复该过程。如右上图所示。这一次，新的切线在更靠近根的点处与 x 轴相交。重复几次通常会得到非常接近多项式真实的根的结果，这里我们给出图像，画出切线，只是为了直观，如果我们要用公式来表达这个过程，记 x(n) 是我们当前对于根的猜测，则可以通过以下公式计算下一个猜测 x(n+1) ：



这里 f(x) 是我们要求根的函数，f'(x) 是该函数的一阶导数，公式的具体推导大家可以参考相关资料，不过要注意的是，因为一开始我们的函数三个地方与 x 轴相交。根据我们的初始猜测，公式可能会收敛到不同的解。例如，如果一开始我们从 x = 0.4 作为我们的初始值，该方法在 0 处收敛到根。

意外行为

牛顿-拉夫森方法通常会收敛到最近的根，但情况并不总是如此。我们可以看下面这个例子：



我们从 0.48 的初始估计值开始。但曲线在 x = 0.48 切线斜率非常小，因此切线与 x 轴的交点距离初始位置相当远，此时大概为 2.5 ,如果我们继续这个过程，它实际上会收敛到 x = 2 处的根。下面的图显示了从不同的起始位置，我们会收敛到哪个根。



如果用红点作为起始位置，则会收敛到 0 这个根，蓝色则会收敛到 1 这个根，而标有绿色三角形的，则会收敛到 2 。这表明该方法通常会收敛到最近的根。但有几个区域不会发生这种情况。比如 x = 0.5 附近的绿色三角形小区域将收敛到 2 ， x = 1.5 附近的红点小区域将收敛到 0 。

多项式的复根

我们很快就会看到，将牛顿拉夫森方法应用于涉及复数的多项式会产生与上述类似的效果。某些起点不会收敛到最近的根。但模式要更有趣得多。但首先，我们需要了解多项式的复根。这里我们举一个非常简单的例子：



如果 x 是实数，则该方程只有一个解，即 x = 1 ，但 x 是复数呢？



这个方程仍然有一个实数解 z = 1 。但它也有两个复数解：



和：



如果我们在复平面上绘制这些点，我们会看到下面的情况：



复函数的牛顿-拉夫森法

当我们应用牛顿-拉夫森法寻找复多项式（例如 z 立方减 1）的根时，就会出现所谓的牛顿分形。但是我们如何将这种方法应用于复数多项式呢？由牛顿-拉夫森法的公式，我们需要计算复多项式的微分，这其实是复分析的内容，本身也是一门很优美的学科，我们不会在这里详细展开，这里对于 z 的立方，它的微分法则与实数的完全一致：



我们可以将原始的牛顿-拉夫逊公式应用于 z 的立方，如下所示：



z 立方的牛顿分形

如果我们取复平面上的任意点 z 作为我们的初始猜测点，然后应用牛顿-拉夫森公式，找出它收敛于哪个根。在下面的图中，已针对复平面中的不同点做了计算，分别标有红色、绿色或蓝色，以指示其汇聚的位置：



将其与上图 z^3 - 1 = 0 三个立方根进行比较，它们也按照相同的方案着色。即蓝色的点作为初始猜测则会收敛到 1（蓝色）这个根，其他颜色也类似，显然，大多数点的颜色与最近的根相同，这意味着大多数点都集中在其最近的根上。但也很明显，有些点会集中在不同的根上。

还要注意，在 z 为零的原点处有一个孤立的黑点。在零点处，一阶导数为零，因此无法计算序列的下一次迭代。该点不会收敛到任何根。仔细想想，这是有道理的，零点与所有三个根的距离相等，那么它怎么可能收敛到任何一个根上呢？下一步是计算更多点的收敛根。结果如下



这是 z 立方的牛顿分形，在这幅图中，我们添加了一个额外的细节。我们不仅检查点会收敛到哪个根，还检查它收敛需要多长时间：



具体来说，我们检查公式需要多少次迭代才能达到根的 0.01 误差以内。对于快速收敛的点，颜色会变浅，对于需要较长时间收敛的点，颜色会变深。这告诉我们，位于形状中间的点收敛速度更快，但靠近两种不同颜色边界的点收敛速度较慢。如果我们忽略它收敛到哪个根，只关心收敛的时间，则分形的三个主要部分会相同。



更进一步我们也可以考虑 z^4 ，这同样也会生成美丽的图形。好了今天这期我们就到这里。





围城里的猫