二分与三分

这是一篇用二分和三分求方程的根的博客

二分法求方程的根

如果有函数发f(x)，它在区间[a, b]上递增或者递减，并且f(a)*f(b)<0。那么我们知道函数必然有一个等于0的解，而且这个解我们可以用二分法来求近似解。

然后通过二分法缩小范围，直到区间长度足够小，这时候就说明找到了一个误差不超过区间长度的近似解。

在二分法当中，我们没进行一次二分迭代，区间的长度就会缩减一半，这是一个指数级的缩减。所以即使一开始的区间很大，经过二分迭代也可以迅速缩减，得到一个非常精准的结果，并且和泰勒级数一样，除了能得到一个足够精确的值之外，还能得到误差的范围。（注：函数可以不是严格单调的，二分法只需要满足f(a)*f(b)<0，函数连续并且只有一个零点）。

@example

1

用二分法求f(x)=x*x*x-7.7*x*x+19.2*x-15.3在区间[1,2]之间的根．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#include <stdio.h>
#include <math.h>

const double eps = 1e-6; //定义我们计算的精度
double a,b,c,d;        //假定我们输入的函数是一元三次方程组，a*x*x*x+b*x*x+c*x+d=0
double f(double x) //定义我们的函数
{
return a*x*x*x+b*x*x+c*x+d;
}

int main()
{
    double m,n;//求根区间[m,n]
    double i,j,sum;
    printf("请输入一元三次方程组的系数：a,b,c,d:");
    scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
    printf("\n请输入求根区间[m,n]:");
    scanf("%lf%lf",&m,&n);
    if(f(m)*f(n)<0)
    {
        while(fabs(m-n)>eps)
        {
          i=(m+n)/2.0;
          sum=f(i);
          printf("[%lf  %lf]\n",m,n);
          if(fabs(sum)<eps)
           {
               break;
            //printf("\n该方程组的近似根为:x2*=%lf\n",i);
            //return 1;
           }
          else if(f(i)*f(m)<0)
          {
              n=i; //修正区间，将[m,n]换成[m,i],这里的i是中点
          }  
          else if(f(i)*f(n)<0)
          {
              m=i;//修正区间，将[m,n]换成[i,n],这里的i是中点
          }
        }
    }
    printf("%lf  %lf",m,n);
    j=(m+n)/2;
    printf("\n该方程组的近似根为:x*=%lf\n",j);
}

三分查找

1.概念

在二分查找的基础上，在右区间（或左区间）再进行一次二分，这样的查找算法称为三分查找，也就是三分法。

三分查找通常用来迅速确定最值。

二分查找所面向的搜索序列的要求是：具有单调性（不一定严格单调）；没有单调性的序列不是使用二分查找。与二分查找不同的是，三分法所面向的搜索序列的要求是：序列为一个凸性函数。通俗来讲，就是该序列必须有一个最大值（或最小值），在最大值（最小值）的左侧序列，必须满足不严格单调递增（递减），右侧序列必须满足不严格单调递减（递增）。如下图，表示一个有最大值的凸性函数：

2.算法思路

（1）与二分法类似，先取整个区间的中间值mid。

1

mid = (left + right) / 2;

（2）再取右侧区间的中间值midmid，从而把区间分为三个小区间。

1

midmid = (mid + right) / 2;

（3）我们mid比midmid更靠近最值，我们就舍弃右区间，否则我们舍弃左区间？。

比较mid与midmid谁最靠近最值，只需要确定mid所在的函数值与midmid所在的函数值的大小。当最值为最大值时，mid与midmid中较大的那个自然更为靠近最值。最值为最小值时同理。

1
2
3
4

if (cal(mid) > cal(midmid))
    right = midmid;
else
    left = mid;

（4）重复（1）（2）（3）直至找到最值。

算法的正确性：

1、mid与midmid在最值的同一侧。由于凸性函数在最大值（最小值）任意一侧都具有单调性，因此，mid与midmid中，更大（小）的那个数自然更为靠近最值。此时，我们远离最值的那个区间不可能包含最值，因此可以舍弃。

2、mid与midmid在最值的两侧。由于最值在中间的一个区间，因此我们舍弃一个区间后，并不会影响到最值。

@example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

const double EPS = 1e-10;
 
double calc(double x)
{
    // f(x) = -(x-3)^2 + 2;
    return -(x-3.0)*(x-3.0) + 2;
}
 
double ternarySearch(double low, double high)
{
    double mid, midmid;
    while (low + EPS < high)
    {
        mid = (low + high) / 2;
        midmid = (mid + high) / 2;
        double mid_value = calc(mid);
        double midmid_value = calc(midmid);
        if (mid_value > midmid_value)
            high = midmid;
        else
            low = mid;
    }
    return low;
}