在 C# 中查找 sin/cos 曲线的最小值和最大值的最有效方法

Question

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

问题：我的问题是使用 C# 查找曲线上的最小最大点的最佳和最有效的方法/算法是什么，这也非常准确？

关于曲线：我附近有大学的《数值分析》书，所以我需要的只是方法名称和正确方向的推动。我可以生成尽可能多的点来近似曲线，但我希望将点的数量保持在有效的最小值。该曲线始终是 Sin/Cos 曲线的一段形状，但并不总是相同的曲线，并且总是小于一个周期。 Theta 的范围是 0° 到 359.999...° 它有一些相位和幅度偏移，并且 Y 永远不会为负。该函数/算法必须快速运行，因为随着曲线变化，它将每几百毫秒运行一次。

任何建议表示赞赏。

编辑

有关曲线的更多信息：这些点是在鼠标移动时生成的。这些点是基于带惰轮的驱动设计中橡胶带长度的一组点，例如汽车中的蛇形带。惰轮的位置决定了皮带的长度，我得到了曲线[皮带长度（y）与惰轮位置（x）]。在这种情况下，惰轮是枢转惰轮，并且会进行恒定的圆周运动。如果驱动设计发生变化，曲线也会发生变化，要么是因为长度点发生变化，要么是因为惰轮的运动范围受到限制。惰轮的运动范围可能是 0° 到 359.999...°，并且是如上所述的 theta。对于开槽惰轮，最大范围是曲线周期的 1/2（更简单的问题）。

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

Answer 1

如果您有一个二次方程，则最大值或最小值将始终位于方程的微分为 0 的点。如果您的二次方程的公式为 ax^2 + bx + c = 0，则该点将是当 x =-b/2a。

是否是最大opr最小值可以通过查看a来确定。如果a> 0 那么它是最小值并且如果 a < 0 则其最大值（如果 a = 0 则其不是二次方）。

我希望这有帮助。如果你没有得到这种形式的曲线方程，你能说一下你需要做什么吗？

编辑：问题已更改，因此曲线是正弦曲线的一部分，而不再是二次曲线。因此，这个答案不再合适。

编辑2：

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

Answer 2

您应该使用的算法（以及您提供的参数）取决于您的数据集的外观。听起来您正在评估连续获取的某些物理测量的波形。

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

固定峰值检测算法通常有某种方式来指定阈值、宽度（以控制对尖峰的敏感度）和缓冲区大小（以处理真正渐进的峰值）。

那里有很多算法，只需选择一两个并调整参数，直到给出您期望的结果。

Answer 3

由于曲线始终是二次的（因此始终是凸的），因此应该有很多可用的方法（尽管由于我不在 c# 中编程，所以我不知道源是否可用）。首先想到的是牛顿法，但还有其他方法（例如内点法）。有关这些算法的数学背景（不幸的是，不是它们的实现），请参阅此教科书（pdf）。如果您确实使用这些方法中的任何一种，它们也适用于其他凸曲线。

Answer 4

你有可用的所有点吗？并且这些点所代表的函数的“形状”没有限制吗？如果是这样，那么您可能会陷入困境，迭代这些点将是您最好的选择......
尽管如果您对此集还有任何其他工作要做，您可能希望按 Y 坐标对其进行排序，以供将来处理使用。

（保留两个数组 - 作为输入输入的数组（可能按 x-corrd 排序？）和按函数值（y-coord）排序的数组）...

编辑：如果您知道曲线的形状始终“像”Sin/Cos 曲线的一部分，那么如果您知道可能表示的最小周期，则可以进行一些优化通过使用二分搜索算法“查找”拐点（其中斜率（Y 向左和向右的变化）具有不同的符号。对于左侧检查的每个点，向右移动 chunks = half允许的周期，直到找到拐点，或者斜率改变符号...然后向后移动 x 最后一次变化的一半，直到找到拐点 [对右侧的点执行相反的操作]

A。递归例程，检查/找到第一个和最后一个拐点，比较它们以确定哪个是最大的，然后递归地检查并找到它们之间的拐点，直到涉及的两个点小于距一个点的最小允许周期另一种，会产生一些性能提升...

第二次编辑：因为我在其他评论中读到该集合永远不会包含多个拐点...如果是这样，那么只需进行二分搜索即可找到它。

伪代码：

  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

Answer 5

收集了几个点 (>=4) 后，您可以使用本地搜索的形式将您的点与正弦曲线 y = A cos(Bx+C)+D 匹配，然后使用简单的根据导数公式求最小值。搜索时，B尽量少，避免出现多余的高频解。只是一个想法，可能效率很低。

Answer 6

从注释中，输入 X 和输出 Y 是数组

“@Mike：我生成值并将它们放入数组中”

我建议使用这种方法。
您从我的代码中需要的只是 {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;
    }

我希望这会很快。

Answer 7

我有点困惑。

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

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