代码之家 › 专栏 › 技术社区 › Mike Webb

求c中sin/cos曲线的最小值和最大值的最有效方法#

numerical-analysis curve math algorithm c#

Mike Webb · 技术社区 · 15 年前

背景: 我的程序中有一个函数,它取一组点,并在这些点生成的曲线上找到最小值和最大值。问题是它的速度非常慢,因为它使用while循环根据近似误差计算出最小值/最大值。不完全确定这是什么形式的方法,因为我自己没有写它,但我知道我们需要一个新的更有效的方法。

问题: 我的问题是,使用C找出曲线上最小-最大点的最佳和最有效的方法/算法是什么?这也是非常准确的?

关于曲线: 我身边有一本大学的数字分析书,所以我只需要一个方法名和一个方向正确的推动。我可以生成尽可能多的点来近似曲线,但我希望将点的数量保持在一个有效的最小值。曲线的形状总是sin/cos曲线的一段,但并不总是相同的曲线,并且总是小于一个周期。θ的范围是0°到359.999…°它有一定的相位和振幅偏移,y永远不会是负值。这个函数/算法必须运行得很快,因为随着曲线的变化,它将每隔几百毫秒运行一次。

如有任何建议,我们将不胜感激。

编辑

关于曲线的更多信息:点在鼠标移动时生成。这些点是一组基于带惰轮的传动设计中的橡胶带长度的点,例如汽车中的蛇形带。惰轮的位置决定皮带的长度,我得到曲线[皮带长度(Y)与惰轮位置(X)]。在这种情况下,惰轮是一个旋转的惰轮,将具有恒定的圆周运动。如果驱动设计发生变化,曲线将发生变化,可能是因为长度点发生了变化,也可能是因为惰轮的运动范围受到了限制。惰轮的运动范围可能为0°至359.999…°,即上文所述的θ。对于有槽惰轮,最大范围是曲线周期的1/2(更容易出现问题)。

我想我需要的是两种类型的惰轮的通用解算器,但真正的问题是旋转惰轮。

7 回复 | 直到 15 年前

Angelo 15 年前

应该使用的算法(以及给出的参数)取决于数据集的外观。听起来你在评估一个连续获取的物理测量波形。

如果是这样,那么您需要决定是否要忽略局部极小值和极大值(例如信号中噪声的峰值)。此外,您还需要某种方法来处理数据集的边缘。换句话说,如果数据的开头是当前数据集中的最高点,但只是从上一个数据集中的一个大峰值下降,那么它是否算为最大值?

屏蔽峰值检测算法通常会有一些方法来指定阈值、宽度(控制对峰值的敏感度)和缓冲区大小(处理真正逐渐的峰值)。

现在有很多算法,只需选择一两个,然后调整参数,直到得到您期望的结果。

Chris 15 年前

如果你有一个二次方程,那么最大值或最小值总是在方程的微分为0的时候。如果你的二次方程的公式是a x^2+b x+c=0,那么这个点就是x=-b/2a。

它是否是最大opr最小值可以通过查看a来确定。如果a>0,则是最小值;如果a<0,则是最大值(如果a=0,则不是二次方)。

希望有帮助。如果你没有这种形式的曲线方程,你能说出你要从中得到什么吗?

编辑: 问题已经改变了,所以曲线是正弦曲线的一部分,不再是二次曲线。因此,这个答案不再适用。

编辑2:

对于正弦曲线,一般方程为y=a sin(mx+t)+c。您将永远无法精确地确定原始方程,因为对于任何解,都会有一个更高频率的解也匹配。我不确定目前需要多少个点来精确计算A会是什么(这会给出曲线的最小值和最大值)。

Jan Gorzny 15 年前

因为曲线总是二次的(因此总是凸的),所以应该有很多可用的方法(尽管因为我没有用C语言编程,我不知道源是否可用)。牛顿的方法首先想到,但还有其他方法(如内点法)。有关这些算法的数学背景(不幸的是,不是它们的实现),请参见 this 教科书(pdf)。如果你使用这些方法中的任何一种,它们也适用于其他凸曲线。

Charles Bretana 15 年前

你所能得到的都是点集吗?这些点所代表的函数的“形状”是否没有限制?如果是这样的话,那么你可能会陷入困境,迭代这些点将是你最好的选择……
尽管在这个集合上还有其他工作要做,但您可能希望按Y坐标对其进行排序,以便将来处理时使用。

(保持两个数组都在周围-输入的那个数组(可能是由x-corrd排序的?)以及按函数值(y-coord)排序的。

编辑: 如果你知道曲线的形状总是“像”sin/cos曲线的一部分,那么 如果你知道可以表示的最小周期 ,您可以通过使用二进制搜索算法来“查找”拐点(其中坡度(向左和向右的y变化)具有不同的符号)来进行一些优化。对于左侧检查的每个点,按块向右移动=允许周期的一半,直到找到拐点或坡度变化符号…然后向后移动X的最后一个变化的一半,直到找到拐点。[对右边的点做相反的操作]

一个递归例程,检查/查找第一个和最后一个拐点,比较它们以确定哪一个是最大的,然后递归检查和查找中间的输入点,直到涉及的两个点小于彼此允许的最小周期APRT,将产生一些性能增益…

第二编辑 :因为我在你的其他评论中看到,这个集合永远不会包含一个以上的拐点…如果是这样,那么只需进行二进制搜索就可以找到它。

PsuedoCode:

  Check Leftmost point to see slope (Up Down or Zero)
       If Zero, done
  Check RightMost Slope 
       If Zero - Done
  If two Slopes are same sign - Done 
        - pick Bigger of two points ( - or smaller if looking for min)
  Check point in the Middle slope
     If Zero, Done
     If slope has same sign as left pt, Change Left to this Point and repeat
     If slope has same sign as right pt, Change Right to this Point and repeat

Mau 15 年前

在收集了一些点(>=4)之后,可以使用本地搜索的形式将点与正弦曲线匹配。 y = A cos(Bx+C)+D 然后用基于导数的简单公式求最小值。搜索时,应尽可能少保留B,以避免冗余的高频解决方案。只是一个想法,可能效率很低。

Waleed A.K. 15 年前

从注释中,输入x和输出y是数组

“@mike:i生成值并将其放入数组”

我建议使用这种方法。我的代码只需要getmaxindex

    private void Test()
    {
        double[] X = SetLinearRange(0, Math.PI * 2, 1000);
        double[] Y = GetOutput(X);
        int MaxIndex = getMaxIndex(Y);
        double MaxX = X[MaxIndex];
        double MaxY = Y[MaxIndex];
    }
    private double[] SetLinearRange(double Start, double End, int Sample)
    {
        double Step = (End - Start) / Sample;
        double CurrentVaue = Start;
        double[] Array = new double[Sample];
        for (int Index = 0; Index < Sample; Index++)
        {
            Array[Index] = CurrentVaue;
            CurrentVaue += Step;
        }
        return Array;
    }
    private double[] GetOutput(double[] X)
    {
        double[] Array;
        Array = (from double Item in X select myFunction(Item)).ToArray();
        return Array;
    }
    private double myFunction(double x)
    {
        double y;
        //put any function
        y = 3 * Math.Sin(5 * x + 2);
        return y;
    }
    private int getMaxIndex(double[] Y)
    {
        double YM = Y.Max();
        int Index = Y.ToList().IndexOf(YM);
        return Index;
    }

我希望那会很快。

Noon Silk 15 年前

我有点困惑。

如果您自己生成点,为什么不在生成时跟踪最大/最小点?

如果你有一个函数,就像我确信其他人已经指出的那样,求出导数并求出0。这将为您提供最小/最大值。