C++ 数学与算法系列之牛顿、二分迭代法求解非线性方程

1. 前言

前文介绍了如何使用“高斯消元法”求解线性方程组。

本文秉承有始有终的态度，继续介绍“非线性方程”的求解算法。

本文将介绍 2 个非线性方程算法：

• 牛顿迭代法。
• 二分迭代法。

牛顿迭代法（Newton's method）又称为牛顿-拉夫逊方法（Newton-Raphson method），是拉夫逊和牛顿同时提出来的一种在实数域和复数域上近似求解方程的方法。

为何说是近似求解方程？

因为对于多数方程式，因不存在求根公式，或者说无法或很难找到标准的可以直接套用的模板公式。

因而求精准解非常困难，从而寻找方程的近似根就显得特别重要。

即使如牛顿大神提出的方法，也只是近似求解的算法，甚至需要满足某种收敛条件的方程式才能使用牛顿迭代法求解。

下面将具体介绍这 2 种求解算法。

2. 牛顿迭代算法

下面将通过一系列演示图，直观告诉大家牛顿迭代法的算法思想。算法中，牛顿用到了微积分相关的知识。

所以，在阅读下文时，需要具备微积分的认知。

牛顿迭代算法求解方程式的过程，有点类似福尔摩斯探案。通过蛛丝马迹，先合理的预测，然后根据推理逻辑，让预测离真相近一点、再近一点……一直到找到或接近真相。

实事告诉我们，不是所有的预测都能找到真相。同理，基于预测的牛顿迭代法也不一定总是能找到方程式的解，看完下面的演示流程，你将明白。

假设现有一非线性方程式 f(x)，其在平面坐标轴上的曲线图案如下。所谓求解，指求其与横坐标轴相交时的点的 x值。

现在，看看牛顿是如何使用微积分思想找到这个解的。只能说，牛逼人的思想非我等凡人能比拟。

2.1 基本思想

• 在横坐标上找一 x0 点（也称预测点），并绘制 (x0,f(x0)) 点与曲线相交的切线。切线和横坐轴相交于 x1。

• 再绘制(x1,f(x1))点与曲线的切线，此时，切线与横轴相交于x2，继续绘制出(x2,f(x2))与曲线的交点……如此迭代，直到切线与横坐标轴的交点与曲线和横坐标的交点重合，此交合点便是曲线的解。是不是很简单，为什么是牛顿发现的，而不是我？

• x0的选择并不完全是任意的，也应该有基本的推理依据。预测点是关键，如果与真实值相差太远，则迭代次数会很大。理论上，只要预测点给的好，且此方程式满足牛顿迭代算法的前提条件，无论迭代多少次，解必能找出来，无非就是时间的长短。

2.2 如何求解 x1

现在的问题转向到如何通过已知的x0值计算出x1的值？是否存在一个标准的公式？

现在就是微积分上场的时候，请屏住呼吸！真相将昭然若揭。

• 在x0 和 x1之间选择任一点x，从此点向上绘制垂直线，假设与切线相交的位置的纵坐标值为y 。并绘制如下箭头所指的三角形。

• 三角形为直角三角形，学过三角函数的都知道，会存在如下的关系。

• 现在轮到微积分知识上场，它告诉我们，其中的tan0就是切线与曲线的斜率。根据微积分原理，斜率即是x0在曲线上的导数，可以根据导函数计算出来，即tan0=f'(x0)。太完美了，如此公式可演变如下：

继续化丽的转身后，它便如涅槃重生一样，破茧成如下人见人爱的模样：

• 因切线与横坐标轴相交的位置y=0，从而便可以求得 x1的值：