Dekker的方法和固定的进一步边界

计算科学 非线性方程 根
2021-12-28 10:16:16

Dekker 的方法及其演变中的 Brent 方法的设计目标是结合根的确定性，通过在越来越小的区间内的相反符号的函数值证明，括号方法如二分法和正则 falsi 与割线的快速收敛（和更高程度的（反向）插值）方法。尤其是在没有修改的regula falsi方法中，人们有规律地观察到包围区间的一个边界变得固定，这导致收敛是线性的，有时甚至比二分法更慢。

为什么要试验 Dekker 的方法，而不是 Brent 的方法？我已经实现了基于英语 Wiki 的 Brent 方法，但我无法理解的两个条件：条件 4 和条件 5。δ

如果相当大（例如），则此条件不好，如果很小（），则在我的示例函数中没有区别。δ10−4δ10−14

我尝试实现 Dekker 的方法来探索具有不良行为的函数。我已经根据 Wikipedia 和 [1] 编写了代码。但在这两种情况下都是一样的。

我使用靠近根，离根更远。迭代点的序列接近但范围的左边界点始终为。

f(x)=(x+3)(x−1)2   and range   [−4,4/3].
4/31−4−31−4

#Based on [1]
a1=-4.00000000 b1=1.33333333 c1=-4.00000000
a2= 1.33333333 b2=1.23255814 c2=-4.00000000
a3= 1.23255814 b3=1.14122330 c3=-4.00000000
a4= 1.14122330 b4=1.08966720 c4=-4.00000000
a5= 1.08966720 b5=1.05556489 c5=-4.00000000

对立始终为。ci−4

我在实现中是否有错误，或者此方法在此函数中有这种不良行为？如何修改点？ci

参考

  1. 公共汽车、JCP 和 TJ Dekker。“两种具有保证收敛性的高效算法，可以找到函数的零点。” ACM 数学软件交易 (TOMS) 1.4 (1975): 330-345。
2个回答

如 [1] 中运行的 Dekker 方法的完整日志（但基于容差放宽了函数值相等性）读取

    initial: x[ 0] =  -4.000000000000000,  f(x[ 0]) = -25.000000000000000;  a=x[ 0], b=x[ 0], c=x[ 0]
    initial: x[ 1] =   1.333333333333333,  f(x[ 1]) =   0.481481481481481;  a=x[ 0], b=x[ 0], c=x[ 0]
     secant: x[ 2] =   1.232558139534884,  f(x[ 2]) =   0.228910661954293;  a=x[ 0], b=x[ 1], c=x[ 0]
     secant: x[ 3] =   1.141223295849618,  f(x[ 3]) =   0.082592637299225;  a=x[ 1], b=x[ 2], c=x[ 0]
     secant: x[ 4] =   1.089667203324025,  f(x[ 4]) =   0.032881772315203;  a=x[ 2], b=x[ 3], c=x[ 0]
     secant: x[ 5] =   1.055564885924540,  f(x[ 5]) =   0.012521380362105;  a=x[ 3], b=x[ 4], c=x[ 0]
     secant: x[ 6] =   1.034592397360872,  f(x[ 6]) =   0.004827930257963;  a=x[ 4], b=x[ 5], c=x[ 0]
     secant: x[ 7] =   1.021431369375937,  f(x[ 7]) =   0.001847057878276;  a=x[ 5], b=x[ 6], c=x[ 0]
     secant: x[ 8] =   1.013276313630701,  f(x[ 8]) =   0.000707382104210;  a=x[ 6], b=x[ 7], c=x[ 0]
     secant: x[ 9] =   1.008214575350145,  f(x[ 9]) =   0.000270471306102;  a=x[ 7], b=x[ 8], c=x[ 0]
     secant: x[10] =   1.005081086844448,  f(x[10]) =   0.000103400954756;  a=x[ 8], b=x[ 9], c=x[ 0]
     secant: x[11] =   1.003141749908864,  f(x[11]) =   0.000039513380892;  a=x[ 9], b=x[10], c=x[ 0]
     secant: x[12] =   1.001942302905629,  f(x[12]) =   0.000015097489725;  a=x[10], b=x[11], c=x[ 0]
     secant: x[13] =   1.001200628613113,  f(x[13]) =   0.000005767766984;  a=x[11], b=x[12], c=x[ 0]
     secant: x[14] =   1.000742115041459,  f(x[14]) =   0.000002203347648;  a=x[12], b=x[13], c=x[ 0]
     secant: x[15] =   1.000458684641088,  f(x[15]) =   0.000000841662903;  a=x[13], b=x[14], c=x[ 0]
     secant: x[16] =   1.000283495152734,  f(x[16]) =   0.000000321500791;  a=x[14], b=x[15], c=x[ 0]
   midpoint: x[17] =  -1.499858252423633,  f(x[17]) =   9.374822745209075;  a=x[15], b=x[16], c=x[ 0]
   midpoint: x[18] =  -2.749929126211817,  f(x[18]) =   3.516488737876408;  a=x[16], b=x[17], c=x[ 0]
   midpoint: x[19] =  -3.374964563105908,  f(x[19]) =  -7.176939824849181;  a=x[17], b=x[18], c=x[ 0]
     secant: x[20] =  -2.955469385046399,  f(x[20]) =   0.696714337038388;  a=x[19], b=x[18], c=x[19]
     secant: x[21] =  -3.006254598617412,  f(x[21]) =  -0.100386782589438;  a=x[18], b=x[20], c=x[19]
     secant: x[22] =  -2.999858717256849,  f(x[22]) =   0.002260364206725;  a=x[20], b=x[21], c=x[20]
     secant: x[23] =  -2.999999559177439,  f(x[23]) =   0.000007053159416;  a=x[21], b=x[22], c=x[21]
     secant: x[24] =  -3.000000000031142,  f(x[24]) =  -0.000000000498268;  a=x[22], b=x[23], c=x[21]
exit by interval length
 best value: x[25] =  -3.000000000031142,  f(x[25]) =  -0.000000000498268;  a=x[23], b=x[24], c=x[23]

解释是该方法首先遵循bi,ai=bi−1朝向双根x=1. 由于多重性，收敛是线性的。由于没有基于函数值的退出条件，此时点ai,bi足够接近，使得函数值几乎相等，割根计算失败，Dekker 方法切换到二分法的中点。在第一等分根x=1现在在包围间隔/段之外[bi,ci]. 二等分步骤一直持续到中点值第一次为负值，停止在ci=−4. 此时，割线方法重新启动，现在也减少了长度|bi−ci|包围间隔为零。

我认为，如果在给定的间隔内有多个根，则 Dekker 方法的行为会很差。

请参阅 Cleve's Corner ( http://blogs.mathworks.com/cleve/2015/10/12/zeroin-part-1-dekkers-algorithm/ ) 上的此方法，其中方法对于间隔中的一个根足够好。

其它你可能感兴趣的问题
上一篇tecplot 360 ex 中四面体网格的二维切片 下一篇适当的 Lapack/MKL 例程来有效地计算 C = A* inv(B)