原创的一种求解三次拟合曲线的极大值算法，希望和大家能交流 传感器 多项式 最大值

duguangqian

下面是我的三次曲线拟合的算法，没有使用开方求极大值，经过我一般的试验后，发现在知道上精确度是很高的，误差范围小于1cm.但由于传感器最大值与最小值比标定做的不好，所以诚心将算法拿出来和大家交流，希望能将曲线拟合算法变得跟使用与丰富，也希望大家能将好的传感器最大值与最小值比标定的算法能和我分享510786964@qq.com
//传感器位置-10 -5 5 10，三次多项式矩阵的逆矩阵。系数Q[4]=X_Array[4]*L_value[4];
float X_Array[4][4]={ {-0.0007,0.0013,-0.0013,0.0007},
                                        {0.0067,-0.0067,-0.0067,0.0067},
                                        {0.0167,-0.1333,0.1333,-0.0167},
                                        {-0.1667,0.6667,0.6667,-0.1667}  };
char X[4] = {-10,-5,5,10}; //传感器实际位置
unsigned char L_value[4]={0};  //存储传感器归一化后的值
float AD[4];            //存储ad转换的值
float XX;           //存储最终得到的偏移距离


//曲线拟合函数，目的是求出小车偏离磁导线的偏移距离
void Curve_fitting()
{
        float Q[4]={0};  //存储三次多项式系数
        float Xi=0;
        float Y=0,Ymax=0;//二次函数值
        unsigned char ss=0;
        char Xmax=0; //存储X[4]中最大的值
        float Ys,Xs=0;//存储二次函数的最大值对应的x值；
        float Xtemp=0;//存储磁导线偏移的实际位置
        unsigned char i,j;

       
               
        Get_Lvalue();   //归一化函数，得到归一后的值  可是本人对传感器最大值与最小值标定这一块做的不理想

    //找出对应最大值的传感器位置
        ss=L_value[0];
        Xmax=X[0];
        for(i=0;i<3;i++)
        {
                if(ss<L_value[i+1])
                {
                        ss=L_value[i+1];
                        Xmax=X[i+1];
                }
        }
       
       
    //计算三次多项式系数
        for(i=0;i<4;i++)
                for(j=0;j<4;j++)
                {
                        Q += X_Array[j]*L_value[j];
                }

    //计算三次多项式求导后，Xmax对应的二次函数的值Ymax,它主要用于后面的比较与搜素极大值使用
        Ymax=3*Q[0]*Xmax*Xmax+2*Q[1]*Xmax+Q[2];
       
        //计算二次函数的中轴线及其对应的函数值，也是用于后面的比较与搜素极大值使用
        Xs=(-Q[1])/(3*Q[0]);       
        Ys=3*Q[0]*Xs*Xs+2*Q[1]*Xs+Q[2];

//**************************************************************************
            if(Q[0]>0&&Ys<0)         //当二次曲线开口向上，必须保证有解，所以Ys<0
                {
                        if(Xmax>=Xs)         //画图后很直观的能明白这样做的目的
                                for(Xi=Xs;;Xi-=0.1)
                                {
                                        Y=3*Q[0]*Xi*Xi+2*Q[1]*Xi+Q[2];
                                        if(Y>=0)
                                        {
                                                Xtemp = Xi;
                                                break;
                                        }
                                }
                        else
                           {
                                if(Ymax>=0)
                                        for(Xi=Xmax;;Xi+=0.1)
                                        {
                                                Y=3*Q[0]*Xi*Xi+2*Q[1]*Xi+Q[2];
                                                if(Y<=0)
                                                {
                                                        Xtemp = Xi-0.1;
                                                        break;
                                                }
                                        }
                                else
                                        for(Xi=Xmax;;Xi-=0.1)
                                        {
                                                Y=3*Q[0]*Xi*Xi+2*Q[1]*Xi+Q[2];
                                                if(Y>=0)
                                                {
                                                        Xtemp = Xi+0.1;
                                                        break;
                                                }
                                        }
                                }
                }
//**************************************************************************
       
//**************************************************************************       
        if(Q[0]<0&&Ys>0)                //当二次曲线开口向下，必须保证有解，所以Ys<0
        {
                if(Xmax<Xs)
                        for(Xi=Xs;;Xi+=0.1)
                        {
                                Y=3*Q[0]*Xi*Xi+2*Q[1]*Xi+Q[2];
                                if(Y<=0)
                                {
                                        Xtemp = Xi-0.1;
                                        break;
                                }
                        }
                else if(Xmax>=Xs)
                   {
                        if(Ymax>=0)
                                for(Xi=Xmax;;Xi+=0.1)
                                {
                                        Y=3*Q[0]*Xi*Xi+2*Q[1]*Xi+Q[2];
                                        if(Y<=0)
                                        {
                                                Xtemp = Xi-0.1;
                                                break;
                                        }
                                }
                        else
                                for(Xi=Xmax;;Xi-=0.1)
                                {
                                        Y=3*Q[0]*Xi*Xi+2*Q[1]*Xi+Q[2];
                                        if(Y>=0)
                                        {
                                                Xtemp = Xi+0.1;
                                                break;
                                        }
                                }
                        }
        }
//**************************************************************************
//若磁导线在最左的电感之左或在最右电感的之右，将偏移值设最大
        if(Q[0]>0&&Ys>0||Q[0]<0&&Ys<0)
                Xtemp = Xmax;          //这样做就是为了测试用，具体针对中情况的算法还没想好


       
     XX =  Xtemp;      //最后得到偏移值
}

rubick

第一，你做的事情根本就不是“拟合”，你可以先看看书，搞清楚什么是拟合。
第二，求跟公式一定比你的算法快，唯一的问题是开方运算。
第三，你做的其实是求函数的零点，你居然一点一点地搜索，精度保证不了不说，还慢，时间复杂读跟精度的指数成正比，为什么不用二分法？黄金分割法？牛顿迭代法？随便一个的时间复杂度都是线性的。
第四，开方（精度0.01%）的线性算法几十年前就已经公布了，五行代码的事情，不会写的话，打表都行。用求跟公式速度就是常数了，程序10行不到的事情。
最后：你把一个常数时间复杂度，10行代码就搞定的事情，用了指数时间复杂度的算法，写成了100+行的代码……
你还是多看看书吧……

左岸天空

赞！

rubick

既然你分享的是“算法”，而代码本身是一种非常糟糕的对“算法”的描述方法，极为不便于读者理解
那么能不能用汉语（而非C语言）简单地描述几句，配以必要的图像。

duguangqian

rubick 发表于 2014-3-1 16:09
既然你分享的是“算法”，而代码本身是一种非常糟糕的对“算法”的描述方法，极为不便于读者理解
那么能不 ...

嗯，那我就简单的描述下，因为它也容易好懂

duguangqian

若拟合后的曲线方程为 Y=a*x^3+b*x^2+c*x+d
则其导数为Y’=3*a*x^2+2*b*x+c 了
情况一：三次多项式系数a小于零，既它的导函数二次函数开口向下，


显然，Ｙｓ只有大于零的时候，三次曲线才有极值，二次函数与ｘ轴的交点Xtempj就对应这三次函数极大值（高数中的极值问题的一些结论），也就是三次拟合曲线算法得出的偏移值。怎么用单片机算出来呢？显然直接利用求根公式会耗费单片机资源，那么就采用一种比较和查询的方法求取近似值了。情况①是Xmax小于Xs,那么直接从Xs开始向右代值比较（就是将Xi递增0.1向右求出Yi的值），一旦Yi的值小于零，立即停止递增，此时Xtemp就近似等于Xi了。
同理，情况②是Xmax大于Xs，那么就从Xmax开始搜寻咯。但若Ymax大于零，就向右搜寻，若Ymax小于零，就像左搜寻。

情况二：对于三次多项式系数a大于零的分析，也是和上面的方法一样了。

当磁导线在最左传感器之左或最右传感器之右的时候，三次多项式是单调的，因而没有极大值，也就是二次函数没有根了。

所以此算法在直到上是很管用的，但一旦偏离远了，就必须过渡到其他算法或者是重新拟合一条曲线了

duguangqian

若拟合后的曲线方程为 Y=a*x^3+b*x^2+c*x+d

则其导数为Y’=3*a*x^2+2*b*x+c了

情况一：三次多项式系数a小于零，既它的导函数二次函数开口向下，

file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/msohtml1/01/clip_image002.jpg

显然，Ｙｓ只有大于零的时候，三次曲线才有极值，二次函数与ｘ轴的交点Xtempj就对应这三次函数极大值（高数中的极值问题的一些结论），也就是三次拟合曲线算法得出的偏移值。怎么用单片机算出来呢？显然直接利用求根公式会耗费单片机资源，那么就采用一种比较和查询的方法求取近似值了。情况①是Xmax小于Xs,那么直接从Xs开始向右代值比较（就是将Xi递增0.1向右求出Yi的值），一旦Yi的值小于零，立即停止递增，此时Xtemp就近似等于Xi了。

同理，情况②是Xmax大于Xs，那么就从Xmax开始搜寻咯。但若Ymax大于零，就向右搜寻，若Ymax小于零，就像左搜寻。

情况二：对于三次多项式系数a大于零的分析，也是和上面的方法一样了。

当磁导线在最左传感器之左或最右传感器之右的时候，三次多项式是单调的，因而没有极大值，也就是二次函数没有根了。

所以此算法在直到上是很管用的，但一旦偏离远了，就必须过渡到其他算法或者是重新拟合一条曲线了

windson

不明觉厉啊

duguangqian

rubick 发表于 2014-3-2 01:43
第一，你做的事情根本就不是“拟合”，你可以先看看书，搞清楚什么是拟合。
第二，求跟公式一定比你的算法 ...

嗯，一定好好看看书，研究研究它

sun听

duguangqian 发表于 2014-3-1 17:15
若拟合后的曲线方程为 Y=a*x^3+b*x^2+c*x+d
则其导数为Y’=3*a*x^2+2*b*x+c 了
情况一：三次多项式系数a小 ...

你是根绝国防科技大学的计数报告来做的？