终止条件

从数学上来说,平滑函数的局部极小值的充分条件是很简单的: 是一个局部极小值,如果 并且 Hessian 是正定的.(Hessian 半正定是一个必要条件.)对于一个根来说,条件更简单. 然而,当函数 在一台计算机上计算时,它的值至多只在一定精度上已知,并且实际操作上只可能有有限次数的函数计算,这时我们必须使用误差估计来决定何时搜索已经足够接近一个极小值或是一个根,同时把解的计算只近似到有限容差范围内. 在大多数情况下,这些估计已足够好,但在某些情况下,通常因为该函数在细小尺度内没有被分辨的行为,它们可以是错误的.

容差影响在搜索结束前搜索可以接近一个根或局部极小值的程度. 假设函数本身有一些误差(这在使用数值值进行计算时是典型的),通常不可能比所用的数字精确度的一半更好地定位一个极小值. 这是因为局部极小值的二次性质. 在接近抛物线的底部位置,当您从极小值移动,高度变化得相当缓慢. 因此,如果在函数中有任何误差噪音,它通常会在大致相当于噪音平方根的宽度范围内掩盖抛物线的实际增长. 这可以通过一个例子很好地说明.    

这里加载一个包含一些功用函数的程序包.
In[1]:=
Click for copyable input
下面的命令在不断递减的范围内,画出显示函数 极小值的一系列图形. 使用机器精度计算的曲线用黑色显示;实际曲线(用100位数的精度算得)用蓝色显示.
In[2]:=
Click for copyable input
Out[2]=

从这一系列的图示,很显然看出对于 量级(大约是机器精度的一半或者更小)的改变,函数中的误差掩盖了极小值附近的曲线的实际形状. 如果只在这样的精度上对函数进行采样,是无法确定对于相近的容差,一个给定的点是否给出该函数的最小局部值.

如果采用符号化表示的方法计算导数值,是更加可靠的,但在一般情况下,仅仅依靠导数值是不够的;搜索需要找到函数的一个局部极小值,而在该位置导数必须小到可以在一般情况下满足容差. 另外,请注意,如果您的函数的符号化表示的导数不能被计算,而是使用有限差分或者是一个无导数方法,解的准确度可能会进一步降低.    

根的求解可能会遭受在函数中同样的不准确度. 虽然通常情况下问题不会那么严重,一些误差估计是基于一个优值函数的,而优值函数确实有一个二次型的形状.

由于这种限制的原因,Find 函数的默认容差都将被设置为最后工作精度的一半大小. 根据函数具有多大误差,这可能可以实现也可能无法实现,但是在多数情况下,这是一个合理的目标. 您可以使用 AccuracyGoalPrecisionGoal 选项调整容差. 当 AccuracyGoal->agPrecisionGoal->pg,这就定义了容差 .

给定后,FindMinimum 尝试找到一个满足 . 当然,由于极小值的确切位置 是未知的,因而许要对 进行估计. 对此一般的做法是根据过去的步骤和导数值. 为了在极小值可以符合导数条件,我们对它强加额外的要求 . 对于 FindRoot,相应的条件只是在根的位置,残差要小:.

这里找到了 ,它满足至少12位的准确度,或在容差 之内. 的精度目标意味着 ,因此它没有对公式产生任何影响. (注:您不能同样地把精度目标设为 ,因为它总是用于残差的大小.)
In[3]:=
Click for copyable input
Out[3]=
下面表明,结果满足所要求误差容差.
In[4]:=
Click for copyable input
Out[4]=
这里尝试在8位数的准确度内找到函数 的极小值. FindMinimum 给出一个警告信息,这是由于从图中我们可以看到的函数的误差.    
In[5]:=
Click for copyable input
Out[5]=
这里显示了,虽然在极小值处找到的值基本上是在机器精度(machine epsilon)内,位置却发现只达到了 左右的量级.
In[6]:=
Click for copyable input
Out[6]=

在多维空间里,情况就更为复杂,因为在一些方向可能有比其他方向更多的误差,比如像在 FreudensteinRoth 问题 中,当极小值在沿着相对狭窄的谷处找到时. 对于这样的搜索,搜索参数经常被缩放,这进而又影响了误差估计. 尽管如此,典型的情况仍然是,极小值的二次形状影响实际可以实现的容差.

当您需要在超出默认容差的范围内寻找一个根或极小值时,您可能需要增加最后工作精度. 为此,您可以需要使用WorkingPrecision 选项. 当您使用 WorkingPrecision->prec 时,搜索从初始值的精度开始,并随着搜索的收敛,自适应地增加到 prec. 默认情况下,WorkingPrecision->MachinePrecision,所以机器精度数字被使用,这通常要快得多. 达到更高的精度花费的时间可能会显著增加,但是可能带来更准确的结果,如果您的函数定义适当的话. 对于非常高精度的解,推荐用牛顿方法,因为它的二次收敛速度大大减少了最终需要的步骤数目.

值得注意的是,如果函数用较低精度的数字定义,WorkingPrecision 选项则不会带来任何好处. 一般而言,为了使 WorkingPrecision->prec 是有效的,用来定义函数的数字应该是精确的或者至少达到精度 prec. 在可能的时候,函数中的数字精度用 SetPrecision 被人为地增加到 prec,因此收敛仍然可以达到,但是这并非总是可能的. 在任何情况下,当函数和导数使用数值计算的时候,如果必要的话,结果的精度都提高到 prec,这样使得内部算法可以使用 prec 位数的精度来完成. 即使如此,根或者极小值的实际精度或准确度受函数中的准确度限制. 记住这一点在使用 FindFit 时尤为重要,这种情况下数据通常只在一定精度上已知.

这是使用机器精度的数字定义的函数.
In[7]:=
Click for copyable input
即使有较高的工作精度,极小值也不能被更好地分辨,因为实际函数仍然有如图中显示的同样的误差. 这里对导数做了具体指定,以保持其他信息与前面所示的机器精度下的计算的一致性.
In[8]:=
Click for copyable input
Out[8]=
这是当函数没有机器精度数字时,使用20位数精度的计算.
In[9]:=
Click for copyable input
Out[9]=

如果您指定 WorkingPrecision->prec,但是没有明确指定 AccuracyGoalPrecisionGoal 选项,那么它们的 Automatic 的默认设置自动被视为 AccuracyGoal->prec/2PrecisionGoal->prec/2. 正如前文所述,这将导致一般现实情况下可以预期的最小容差.

以下是使用50位数精度进行的计算,这里没有明确指定 AccuracyGoal 或者 PrecisionGoal 选项的设置.
In[10]:=
Click for copyable input
Out[10]=
这里显示了在极小值处的数值实际上被发现比默认的25位容差更好.
In[11]:=
Click for copyable input
Out[11]=

下表总结了影响精度和容差的选项.

选项名
默认值
WorkingPrecisionMachinePrecision使用的最终工作精度 prec; 精度自适应地从 prec 和初始条件的精度中较小的那个增加到 prec
AccuracyGoalAutomatic设置 ag 通过 决定一个绝对容差; 当 Automatic 时,
PrecisionGoalAutomatic设置 pg 通过 决定一个绝对容差; 当 Automatic 时,

函数中的精度和容差选项.

一个搜索过程有时候会缓慢地收敛. 为了防止缓慢的搜索无限制地持续下去,所有 Find 命令都有一个在终止前所允许的最大迭代(步骤)数目. 这可以通过具有默认值 MaxIterations->100 的选项 MaxIterations 控制. 当在此条件下,搜索终止的时候,命令将会发出 讯息.

这里从 Optimization`UnconstrainedProblems` 程序包取得Brown-Dennis问题.     
In[12]:=
Click for copyable input
Out[12]//Short=
这里试图用默认方法,即Levenberg-Marquardt方法,求解问题,因为这里函数是一个平方和的形式.
In[13]:=
Click for copyable input
Out[13]=

Levenberg-Marquardt方法在这个问题收敛缓慢,因为在极小值附近,残差不为零,需要 Hessian 的二阶部分. 虽然该方法最终仅在400个步骤下收敛,也许更好的选择是使用一个可能更快收敛的方法.

In[44]:=
Click for copyable input
Out[44]=

在更大规模的计算中,当达到迭代极限时,一种可能的解决方案是使用返回的最后搜索点,作为继续搜索的一个初始条件,最好是使用另一种方法来搜索.