二分法-牛顿法-求sqrt

title: 二分法牛顿法求sqrt
comments: true
categories:

Algorithm
tags:
Algorithm
C++
date: 2019-03-21 10:47:38

使用二分法

首先确定二分法查找的首尾区间，然后根据abs(mid^2-target)<eps的误差进行区间的移动，寻找满足精度的位置

存在的问题:

第一步寻找合适的搜索区间，我们从函数曲线上可以看出，y=x和y=√x在x=1时交集；
当待开根号数在(0,1)之间时，搜索区间也在(0,1)，当待开根号数tar>1时，区间在[1,x]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3el4PZu0-1576236781089)(http://po7b8zci3.bkt.clouddn.com/15531498785073.jpg)]

实现

float found(float x,float eps,float s,float e){
    float mid = s+(e-s)/2.0;
    float tmp = mid*mid - x;

    if(abs(tmp) <= err){
        return mid;
    }
    if(tmp >0){
        return found(x,eps,s,mid);
    }else{
        return found(x,eps,mid,e);
    }
}

float sqrt(float x,float eps){
    if (x<0) return -1;
    if (x==0) return 0;

    if(0<x && x<1){
        return found(x,eps,0.,1.);
    }else{
        return found(x,eps,1,x);
    }
    
}

二分法的非递归实现

float found(float x,float eps,float s,float e){
    float mid = (e+s)/2.0;
    float tmp =  mid*mid - x;
    
    while(abs(tmp) > eps){
        printf("cnt %d %f %f %f \n ",cnt,s,e,mid);

        if(tmp>0){
            e = mid;
        }else{
            s = mid;
        }
        mid=(s+e)/2;
        tmp = mid*mid - x;
    }
    return mid;
}

使用牛顿迭代法

仔细思考一下就能发现，我们需要解决的问题可以简单化理解。

从函数意义上理解：我们是要求函数f(x) = x²，使f(x) = num的近似解，即x² - num = 0的近似解。
从几何意义上理解：我们是要求抛物线g(x) = x² - num与x轴交点（g(x) = 0）最接近的点。

实现


float NewTown(float x,float eps){
    float x0,x1= x/2.0;

    int cnt=0;

    while(abs(x1-x0) >= eps){
        x0 = x1;
        printf("cnt: %d %f \n ",cnt,x0);
        x1 = x0 - (x0*x0-x)/(2.0*x0);
// x1 = 1.0/2*(x0+x/x0);
        cnt++;
    }
    
    return x1;
}

使用牛顿迭代法求多项式的一个根

定区间，找中点，中值计算两边看。 
同号去，异号算，零点落在异号间。

实现


float NewTown2(){
    float x,x1=1;
    int a=1,b=2,c=3,d=4;

    float f,f1;

    while(abs(x1-x) >0.001){
        x=x1;
        f = ((a*x+b)*x+c)*x + d;
        f1 = (3*a*x+2*b)*x+c;
        x1 = x - f/f1;
    }

    printf("newtown2 %.10f",x1);
    return x1;

}

牛顿迭代法

五次及以上多项式方程没有根式解（就是没有像二次方程那样的万能公式)

牛顿迭代法（Newton’s method），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。
切线是曲线的线性逼近
求高阶方程式的近似解，
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-t6ijUoIP-1576236781090)(http://po7b8zci3.bkt.clouddn.com/15531543539924.jpg)]

比如我们要开平方根，则可以转换为求x^2 - a = 0的实数根，根据x_n+1 = x_n - f(x_n)/f’(x_n) ,不断迭代新的切线，直到找到近似解，f(x)和x轴的交点

不收敛的情况：

驻点

起始点不幸选择了驻点，从几何上看切线根本没有根。

越来越远离的不收敛

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-v0fcY15e-1576236781091)(http://po7b8zci3.bkt.clouddn.com/15531548601931.jpg)]

循环震荡的不收敛

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PskEgjVi-1576236781093)(http://po7b8zci3.bkt.clouddn.com/15531550374784.jpg)]

不能完整求出所有的根

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-D5WtvezB-1576236781096)(http://po7b8zci3.bkt.clouddn.com/15531549206795.jpg)]

总结

应用牛顿-拉弗森方法，要注意以下问题：
函数在整个定义域内最好是二阶可导的
起始点对求根计算影响重大，可以增加一些别的判断手段进行试错

牛顿法求极值梯度下降求极值

其实牛顿迭代法也可以很方便的求极值，只要x=x−f’(x)/f"(x)
这样求的就是，f’(x)与x轴的交点，既导数的零点，也即是f(x)的极值点

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-feBh9guZ-1576236781101)(http://po7b8zci3.bkt.clouddn.com/15531575573419.jpg)]