为什么要在递归中出现分段错误来寻找函数的根？

Question

初学者C语言。

我练习用牛顿法求函数f(x)的根。

​

​

这是我的代码：

float bisection_root(float a, float b, float delta) {

    // TODO > pass functions ?
    // TODO check f(a) * f(b) < 0 o non finisce mai...
    // 

    float func(float x);

    printf("test %f \n",  func(a) * func(b) );


    // mean:
    float mean = (a + b) / 2.0;

    if ( fabs(func(mean)) < delta) {
        printf("Called function is: %s. Found delta. Result: %f\n",__func__, mean);
        return mean;
    } 
    else 
    // check if a, mean have same signs:
    if ((func(a) * func(mean)) < 0) {
        printf("Called function is: %s. Taking first half. Result: %f %f\n",__func__, delta, func(a) * func(mean));
        return bisection_root(a, mean, delta);
    }

    else {
        printf("Called function is: %s. Taking second half. Result: %f %f\n",__func__, delta, func(mean) * func(b));
        return bisection_root(mean, b, delta);
    }
    

}

float func(float x) {
    return 2*pow(x,3) - 4*x + 1;
}

在main中调用，如下所示：

int main(int argc, char *argv[]) {
    
    bisection_root(0, 1, 0.00000000002);
    return 0;
}

结果是递归不会停止，并且我有一个segmentation fault: 11。

你能帮助理解为什么递归失败，以及“程序写出内存”在哪里？

负零在C中是什么意思？

这是我的输出：

Called function is: bisection_root. Taking first half. Result: 0.000000 -0.750000
test -0.750000 
Called function is: bisection_root. Taking second half. Result: 0.000000 -0.023438
test -0.023438 
Called function is: bisection_root. Taking first half. Result: 0.000000 -0.012329
...

Called function is: bisection_root. Taking first half. Result: 0.000000 -0.000000 0.258652
test -0.000000 
Called function is: bisection_root. Taking first half. Result: 0.000000 -0.000000 0.258652
test -0.000000 
Called function is: bisection_root. Taking first half. Result: 0.000000 -0.000000 0.258652
Segmentation fault: 11

Answer 1

更新

递归失败的原因

对于此任务，delta as 0.00000000002的错误限制太小。

在这种情况下，当mean不为真时，float mean = (a + b) / 2.0;会不断生成fabs(func(mean)) < delta。

考虑一下当a=0.258652002f和b=0.258652031f，b是继a之后的下一个可能的float。a, b横跨0.25865202250415276的数学根...它们的func()值分别为+7.5155981e-08和-3.20905009e-08，幅度均超过2e-09。在这个误差范围内没有解决方案。

从pow()到powf()的更改(在下面前面的答案中)只是稍微改变了func()，有时足以返回足够小的结果。

使用二分法，当mean等于a或b时，递归可以简单地停止。并不是真的需要delta。

//if (fabs(func(mean)) < delta) {
if (mean == a || mean == b) {

在C中负零是什么意思？

OP的输出类似于"-0.000000"。当该值在-0.0000005和0之间并使用"%f"打印时，就会发生这种情况。(C支持2个零、+0.0和-0.0，因此当值为-0.0时也会出现"-0.000000"。当计算从负值舍入到0.0时，可以看到这一点。)

对于debug，当值较小时，最好使用"%g"而不是"%f"来查看更多信息。

其他想法

如果坚持float数学，最好使用float mean = (a+b) / 2.0f;作为float mean = a/2 + b/2，以避免溢出。

考虑(2*x*x - 4)*x + 1而不是2*pow(x,3) - 4*x + 1。在数学上更稳定。

有关这些想法的两个很好的链接，请参阅@Bob__。

较早的答案

对于float问题，使用float数学比使用double数学似乎更明智。

pow() --> powf()
2.0 --> 2.0f
fabs() --> fabsf()
0.00000000002 --> 0.00000000002f

奇怪的是，使用

pow() --> powf()

通向完成。

Called function is: bisection_root. Found delta. Result: 0.258652`

Answer 2

递归函数在有界数组上工作。

1. 首先要看的是“基本步骤是正确的，并且是递归在它应该停止的时候停止”，或者，为了设置基本情况，在使用递归时最常见的错误是，设置一个变量的基本情况，并使用另一个引用变量遍历数组。从而使基本情况变得不可达。

在您的代码中检查这两个问题。