3.2　非线性模型求根算法

上一节介绍了用于金融时间序列的非线性模型。从连续时间给定的模型数据来看，其目的是寻找可能推断出有价值信息的极值。利用包括求根算法在内的数值方法，可以求连续函数f的根，例如f(x) = 0，该函数的根可能是函数的最大值或最小值。一般来说，一个方程可能存在很多根或无解。

对非线性模型使用求根法的一个例子是前面讨论的布莱克–斯克尔斯隐含波动率模型。期权交易员可能有兴趣利用该模型计算出隐含价格并将其与市场价格进行对比。在第4章，我们将结合求根法与数值期权定价过程，建立基于特定期权市场价格的隐含波动率模型。

求根法是一个迭代过程，需要一个起始点或估计的根。估计的根可能会收敛得到一个函数解，也可能收敛到非所求根，或者可能根本找不到一个解。因此，找到一个理想的近似根至关重要。

并非每个非线性函数都可以用求根法求解，图3-2展示了一个求根法无法求解的例子：，如图3-2所示，对于–20到20范围内的y值，在x = 0和x = 2处是不连续的。

如何定义理想的近似并没有固定的规则，建议在求根迭代前，用括号表示求解区域，以免在错误的方向反复求解。

3.2.1　增量法

增量法（incremental search）是求解非线性函数的简略方法。对于任意起点a，可以针对每个增量dx得到f(a)的值。假定对于增量dx，f(a + dx)、f(a + 2dx)、f(a + 3dx)…的符号相同。函数值符号改变时得到解，迭代结束；如果超过边界点b没有得到合适解，迭代也结束。

图3-3形象地展示了迭代求根法。

用Python代码实现上例如下：

每次迭代以a+dx即c替代a。若根存在，则根存在于a到c的闭区间。本例将a和c的算术平均值作为近似根，变量n记录迭代次数。

我们再利用Python求解存在一个解析解的方程y = x3 – 2x2 – 5，其中x的取值范围为（–5，5）。设增量dx = 0.001，较小的dx值可以产生更好的精度，迭代次数也更多：

增量求根法是求根算法的一个简单演示，设定好增量dx，经过一段时间的迭代就可以得到相应精度的解。精度越高，求解所需收敛时间越长。实际操作中，增量法是所有求根算法中最不实用的。接下来我们将学习其他效率更高、精度更好的求根方法。

3.2.2　二分法

二分法（bisection method）是最简单的一维求根算法，目的在于求出连续函数f(x)=0的x值。

假设已知一个区间的两点a和b，其中a < b且f(a) < 0，f(b) > 0，令，利用二分法求f(c)的值。

图3-4展示了非线性函数中具体点的位置：

因为图3-4中，f(a)为负值，f(b)为正值，所以二分法假设根x位于a和b之间且f(x) = 0。

若f(c) = 0或在预设的误差容忍范围内接近零点，可视为根已求出。若f(c) < 0，则根位于区间（c, b）内；反之，则根位于区间（a, c）内。

在下一次计算中，c相应地替换为a或b，这样新区间范围就会逐渐变小。二分法将逐步缩小区间重复计算c值，直至求出根。

二分法最大的优势为在给定的迭代次数和允许误差内，一定可以收敛得到根的近似解。某些连续函数求导尤为复杂，而二分法不要求对未知函数求导，处理非平滑函数时非常有效。

与其他求根方法相比，二分法主要的缺陷为迭代时间更长。由于二分法的求根范围在a与b之间，因此需要准确估测根的位置，否则可能会得到错误的解甚至无解。采用更大范围的区间，所需迭代时间更长。

二分法可以稳定收敛且初始无须估计近似根，通常将其结合其他方法使用，例如牛顿迭代法，更快速地获得精确结果。

进行二分法计算的Python代码如下：

再次，将匿名lambda函数绑定到y变量，参数为x。使用二分法求解前例方程y = x3 – 2x2 – 5，其中x取值范围为（–5，5），增量dx为0.00001，迭代次数上限为100次。

可以看出，由二分法得到的结果比增量法更精确，且迭代次数更少。

3.2.3　牛顿迭代法

牛顿迭代法，又称为牛顿–拉夫逊（Newton-Raphson）法，它利用函数求导求解方程，求导之后转化为线性问题，函数f的一阶导数f'表示该函数的切线。设x1为x的下一阶近似值，则x1表达式为：

上式表示切线与x轴相交于点x1，即y = 0，也表示f在点x1的一阶泰勒展开式，其中x1 = x + Δx。由此我们可以得到：

f(x1 + Δx) = 0

按照上述方式迭代，计算过程将在达到迭代次数上限时终止，或在x1与x的绝对差处于可接受的精度水平时终止。

牛顿迭代法需要输入初始估计值以计算f(x)和f'(x)，其收敛速度是二阶的，可快速准确地得到结果。其缺陷在于不能保证整体收敛性。当函数有不止一个根或计算到达局部极值时，该算法无法进行下一步计算。牛顿迭代法需要对目标函数求导，因此必须确保函数可导，而某些函数的导数几乎不可求。

图3-5形象地展示了牛顿迭代法的原理。x0是初始x值，f(x0)的导数与x轴相交于x1。通过反复迭代，计算x1，x2，x3，……

Python实现牛顿迭代法的代码如下：

与3.2.2节中使用二分法运算的结果对比，牛顿迭代法的结果如下：

注意“0”的使用，在Python2中第三行代码要使用5.0而不是5，这样可以让Python将该变量识别为浮点变量而不是整数变量，从而使我们的结果具有更好的精确度。

相比于二分法，牛顿迭代法可通过更少的迭代得到更加精确的答案。

3.2.4　割线法

割线法利用割线求根。割线是与曲线相交两点的直线，并与x轴相交。该法可视为一种拟牛顿迭代法。通过连续绘制割线，可以求近似根。

割线法的原理如图3-6所示。首先需要两个点a与b的横坐标，计算f(a)和f(b)。割线y是f(b)和f(a)两点的连线，与x轴交于点c，满足

因此，c的表达式为：

下一次迭代中，a与b分别取b和c的值，依此类推，连续绘制割线。当迭代次数到达上限或b和c差值达到可接受水平时，迭代终止，如图3-6所示。

割线法收敛速度可视为超线性收敛，快于二分法但慢于牛顿迭代法。由于牛顿法每次迭代的浮点运算量是割线法的2倍，因此可以认为无须求导的割线法在绝对时间上更有优势。

割线法要求输入初始预估值，否则无法保证精确收敛。

割线法的Python代码如下：

同样，使用前述的非线性函数检验结果：

上面几种求根方法都给出了非常精确的近似解，相比二分法，割线法迭代次数更少，但多于牛顿迭代法的迭代次数。

3.2.5　求根法的结合使用

综合前述求根法，可以通过以下步骤进行根的求解：

1）利用速度较快的割线法将问题收敛至预设的误差容忍值，或到达最大迭代次数。

2）一旦达到预设误差容忍值，就切换至二分法求解。

Brent法（或Wijngaarden-Dekker-Brent法）结合了二分法、割线法和逆二次插值法（inverse quadratic interpolation）。该算法优先考虑使用割线法或逆二次插值法，在必要时使用二分法。Brent法可调用SciPy的scipy.optimize.brentq函数实现。