编程科学/峰值与谷值

根据 CME，要找到具有自变量x的曲线的极小值或极大值，你需要求导，将导数设为零，然后解出x。在该点，原函数的斜率为零，因此必须是峰值上的最高点或谷值中的最低点。正如 CME 所说，你无法确定零斜率代表峰值还是谷值，但它必须是其中之一。

求解x的过程非常类似于简化表达式的过程；这是一个超出本文范围的复杂任务。因此，我们将无法象征性地找到极小值/极大值。但是，由于艾萨克·牛顿爵士，我们将能够以数值方式执行此任务。

在本章的其余部分，我们将放弃我们的面向对象方法，并采用函数式方法，因为使用对象的目的就是执行符号任务。将我们以前的面向对象方法改编为执行数值任务（例如查找极小值/极大值）被留作练习。

来自过去的爆炸

首先，我们必须学习如何将多项式及其导数表示为数值 Sway 函数。还记得我们在第 3 章和第 4 章中的比率函数吗？我们用它来计算 ${\frac {dy}{dx}}$ 的数值。

   function ratio(x,dx,y)
       {
       var dy = y(x + dx) - y(x);
       dy / dx;
       }

在 Sway 中，我们不仅可以从函数中返回数字、字符串和环境（对象），我们还可以返回函数本身。我们将使用这个事实来构建数值导数函数。

---

此时，你应该阅读 Sway 参考手册中关于 返回局部函数 的内容。

---

因此，与其使用需要我们一遍又一遍地传入相同y函数的比率函数，我们不如定义一个函数来返回一个自定义的比率，该比率只接受x值作为参数。看看代码将有很大帮助。

   function derivative(y,dx)
       {
       function ratio(x)
           {
           var dy = y(x + dx) - y(x);
           dy / dx;
           }
       }

由于derivative函数中的最后一个表达式是ratio的定义，因此它是ratio函数作为derivative的返回值。现在，我们可以将x值传递给原始函数及其导数。

与往常一样，让我们使用这个多项式作为实验对象进行测试。

   $3x^{2}-10x+5$

将这个多项式以数值方式表示为 Sway 函数，我们有

   function y(x)
       {
       3 * (x ^ 2) - (10 * x) + 5;
       }
     
   var y' = derivative(y,0.000001);

我们预计y的符号导数为

   $6x-10$

因此，我们预计y(2)将产生 -3，以及y'(2)将产生 2。

   sway> y(2);
   INTEGER: -3
   sway> y'(2);
   REAL_NUMBER: 2.0000029988

第二个结果中的不精确度再次归因于使用实数而不是整数。^[1]

一个好的固定点

在数值上查找极小值/极大值的下一步是能够找到函数的固定点。如果一个函数有一个固定点（并非所有函数都有），那么存在一个值x，使得

   $f(x)=x$

例如，余弦函数在约 0.7390851332 处有一个固定点。

   sway> cos(0.7390851332);
   REAL_NUMBER: 0.7390851332

我说约是因为 Sway 默认情况下不会显示所有有效数字。

查找固定点在算法上很简单。

   function fixedPoint(f,x)
       {
       if (f(x) == x)
           {
           x;
           }
       else
           {
           fixedPoint(f,x + f(x) / 2);
           }
       }

如果对于给定的x，$f(x)!=x$，我们尝试使用新的x值再次进行。方便的是，x 和 $f(x)$ 的平均值是我们的下一次尝试的数学上合理的数值。

虽然这段代码很好地说明了这种方法，但它也有一些问题。第一个问题是 f(x) 被计算了两次。为了提高效率，我们应该只计算一次。

   function fixedPoint(f,x)
       {
       var next = f(x);
       if (next == x)
           {
           x;
           }
       else
           {
           fixedPoint(f,x + next / 2);
           }
       }

下一个问题是由于 Sway 中实数的精度有限。由于实数无法精确表示，因此通常不建议在实数精度极限的情况下进行相等比较。因此，除非你确切地知道（而在 fixedPoint 的情况下，你不确切地知道），否则你应该检查数字是否在某个很小的范围内。

   var FIXED_POINT_DELTA = 1e-10;

   function fixedPoint(f,x)
       {
       var next = f(x);
       if (abs(x - next) < FIXED_POINT_DELTA)
           {
           x;
           }
       else
           {
           fixedPoint(f,x + next / 2);
           }
       }

使用abs（绝对值）函数是因为x - next可能是一个很大的负值，这也将小于 $1*10^{-10}$。^[2]

在调用fixedPoint时，我们需要一个x的初始值。事实证明，1.0 几乎总是好的猜测，所以让我们硬编码它。这里有一个很巧妙的技巧。

   function fixedPoint(f)
       {
       function helper(f,x)
           {
           var next = f(x);
           if (abs(x - next) < FIXED_POINT_DELTA)
               {
               x;
               }
           else
               {
               helper(f,x + next / 2);
               }
           }
       helper(f,1.0);
       }

这个技巧的本质是将你想为其固定某些参数的函数重命名为一个好的名称，比如helper。^[3] 然后，你使用具有原始名称的函数包装该函数，使helper成为一个局部函数。然后，你在包装函数中做的最后一件事是调用 helper，固定所需参数的值。

我们可以通过注意到fixedPoint' 的形式参数f绑定到与helper' 的形式参数f相同的值来改进最新版本，因此我们可以在定义和调用中删除helper' 的版本。

   function fixedPoint(f)
       {
       function helper(x)
           {
           var next = f(x);
           if (abs(x - next) < FIXED_POINT_DELTA)
               {
               x;
               }
           else
               {
               helper(x + next / 2);
               }
           }
       helper(1.0);
       }

不要忘记更改递归调用。

牛顿的变换

牛顿提出了一种巧妙的方法来找出多项式（以及其他可微函数）在哪里具有零值。他说，某个函数f 的零点也是从f 派生的新函数的固定点。这个新函数，$f_{NT}$，是

   $f_{NT}(x)=x-{\frac {f(x)}{f\,'(x)}}$

因此，要找到某个函数的零点，我们使用牛顿变换生成一个新函数，并将变换后的函数传递给我们的固定点查找器。它返回的值就是我们的零点！

首先，让我们实现牛顿变换。

   function NewtonsTransform(f)
       {
       var f' = derivative(f,0.000001);
       function y(x)
           {
           x - (f(x) / f'(x));
           }
       }

现在让我们测试我们的多项式。

   $y=3x^{2}-10x+5$

我们使用 Sway 函数实现它，与以前一样，并创建导数函数。

   function y(x)
       {
       3 * (x ^ 2) - (10 * x) + 5;
       }
     
   var y' = derivative(y,0.000001);

函数y在哪里产生零点？

   sway> fixedPoint(NewtonsTransform(y));
   REAL_NUMBER: 0.6125741133
   sway> y(0.6125741133);
   REAL_NUMBER: -1.441567e-10

考虑到我们固有的不精确度，0.6125741133 似乎确实接近y 的零点。y' 呢？

   sway> fixedPoint(NewtonsTransform(y));
   REAL_NUMBER: 1.6666661669
   sway> y(1.6666661669);
   REAL_NUMBER: 1.776357e-09

同样，对于政府工作来说足够接近零。

问题

1. 修改符号系统以处理数值导数。为了使数值导数兼容，derivative函数应该返回一个具有toString 和value 方法的对象。