通过二进制搜索和递归查找函数的根 [英] Finding roots of a function with binary search and recursion

问题描述

有人可以请解释一下，为什么我们需要max和min之间的差小于误差(三次方程的根)?它背后的逻辑是什么?为什么我们需要返回min?

Could someone explain, please, why we need a difference between max and min to be less than error (of the root of the cubic equation)? What is the logic behind it? And why we need to return min?

代码如下:

#include <stdio.h>
#include <stdlib.h>

double func(double x)
{
    return x * x * x  + 2 * x * x - 2;
}

double zeroFinder(double min, double max, double error)
{

    if ((max - min) < error)
    {
        return min;
    }
    double x = (max + min) / 2;

    if (func(x) < 0)
    {
        min = x;
    }
    else
    {
        max = x;
    }

    return zeroFinder(min, max, error);
}

int main(void)
{
     zeroFinder(0.0, 1.0, 0.01);
     zeroFinder(0.0, 1.0, 0.001);  
     zeroFinder(0.0, 1.0, 0.000001);    
     zeroFinder(0.0, 1.0, 0.0000000001);

     return 0;
} 

推荐答案

该算法正在实现称为对分法.想法是从一个间隔开始(在您的情况下以max和min分隔)，在中点求值，然后适当缩短间隔.

The algorithm is implementing something known as the Bisection Method. The idea is to start with an interval (delimited by max and min in your case), evaluate the value at the midpoint and then shorten the interval appropriately.

这就像在实线上进行二进制搜索一样.但是，由于我们试图查找实数值，因此该函数可能不会在有限的迭代次数中终止于该实数值(例如，当答案为sqrt(2)时).另外，由于该方法计算浮点变量，因此通常不会获得确切的值.但是，迭代算法应以一组有限的迭代终止.因此，当间隔变得足够小时(例如，当abs(max - min) < <some error value>时，我们可以让函数终止.这意味着获得的答案在正确答案的some error value之内.

This is exactly like binary search on a real line. However, since we are trying to find a real value, the function may not terminate on the real value in a finite number of iterations (e.g., when the answer is say sqrt(2)). Also, since the method calculates floating point variables, often you will not get the exact value. The iterative algorithm should however terminate in a finite set of iterations. Hence when the interval becomes small enough (i.e., when abs(max - min) < <some error value>, we can let the function terminate. What it means is that the answer obtained is within some error value of the correct answer.

正如@Elyasin在评论中提到的那样，代码可以返回max，min或介于两者之间的任何值作为答案.关于开盘和闭盘的时间间隔可能需要考虑一些因素，因此返回(max + min) / 2.0也是一个不错的选择.

As @Elyasin mentions in the comments, the code could return max, min or any value in between to be the answer. There may be some considerations about open and closed intervals, so returning (max + min) / 2.0 is also a safe bet.

这篇关于通过二进制搜索和递归查找函数的根的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！