Самый эффективный способ найти минимальную и максимальную кривую sin / cos в C #

Question

Справочная информация: В моей программе есть функция, которая берет набор точек и находит минимум и максимум на кривой, сгенерированной этими точками. Дело в том, что он невероятно медленный, поскольку использует цикл while для определения минимума / максимума на основе приблизительной ошибки. Не совсем уверен, что это за формальный метод, потому что я сам его не написал, но знаю, что нам нужен новый и более эффективный метод.

Вопрос: Мой вопрос - какой самый лучший и самый эффективный метод / алгоритм для нахождения точек минимума-максимума на кривой с использованием C #, который также очень точен?

О кривой: Рядом со мной моя книга по численному анализу из колледжа, поэтому все, что мне нужно, это название метода и толчок в правильном направлении. Я могу создать столько точек, сколько выберу для аппроксимации кривой, но я хочу, чтобы количество точек было минимальным. Кривая всегда имеет форму одного сегмента кривой Sin / Cos, но не всегда является одной и той же кривой и всегда будет меньше одного периода. Диапазон тета составляет 0 & deg; до 359,999 ... & deg; Он имеет некоторый сдвиг фазы и амплитуды, и Y никогда не будет отрицательным. Эта функция / алгоритм должны работать быстро, так как она будет выполняться каждые несколько сотен миллисекунд при изменении кривой.

Любые предложения приветствуются.

EDIT

Дополнительная информация о кривой: Точки генерируются при движении мыши. Точки - это набор точек, основанный на длине резинового ремня в конструкции привода с натяжным элементом, например, такого, как зубчатый ремень в автомобиле. Положение холостого хода определяет длину ремня, и я получаю кривую [длина ремня (y) против положения холостого хода (x)]. В этом случае натяжной ролик является поворотным и будет иметь постоянное круговое движение. Если конструкция привода изменится, кривая изменится либо из-за изменения точек длины, либо из-за ограничения диапазона движения натяжного ролика. Диапазон движения в холостом ходу потенциально равен 0 °; до 359,999 ... & deg; и является тета, как указано выше. Для прорези с прорезями максимальный диапазон составляет 1/2 периода кривой (более простая проблема).

Полагаю, мне нужен общий решатель для обоих типов бездельников, но реальная проблема связана с поворотным бездельником.

Answer 1

Если у вас есть квадратное уравнение, то максимум или минимум всегда будут в точке, когда дифференциал уравнения равен 0. Если ваше квадратное уравнение имеет формулу ax ^ 2 + bx + c = 0, то эта точка будетбыть, когда x = -b / 2a.

Является ли это максимальным значением opr, можно определить, взглянув на a.Если a> 0, то это минимум, а если a <0, то это максимум (если a = 0, то это не квадратичное значение). </p>

Надеюсь, это поможет.Если у вас нет уравнения кривой в такой форме, можете ли вы сказать, с чем вы должны работать?

Редактировать: вопрос изменился, так что криваяучасток синусоиды и уже не квадратичный.Поэтому этот ответ больше не подходит.

Edit2:

Для синусоидальной кривой общее уравнение будет иметь вид y = sin (mx + t) + c.Вы никогда не сможете точно определить исходное уравнение, потому что для любого решения найдется решение с более высокой частотой, которое также соответствует.В настоящее время я не уверен, сколько точек необходимо, чтобы точно рассчитать, что будет (что даст минимум и максимум кривой).

Answer 2

Я немного запутался.

Если вы сами генерируете баллы, почему бы просто не отслеживать самые большие / наименьшие баллы при генерации?

Если у вас естьФункция, как я уверен, что другие указали, просто получить производную и решить для 0. Это даст вам точку (мин) / мин.

Answer 3

Из комментария вход X и выход Y являются массивами

"@ Майк: я генерирую значения и помещаю их в массив"

Я предлагаю использовать этот подход. Все, что вам нужно из моего кода, это {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 4

После того, как вы набрали несколько точек (> = 4), вы можете использовать форму локального поиска, чтобы сопоставить ваши точки с синусоидой y = A cos(Bx+C)+D, а затем использовать простую формулу, основанную на производной, чтобы найти минимум.Во время поиска вы должны держать B как можно меньше, чтобы избежать избыточных высокочастотных решений.Просто идея, может быть очень неэффективной.

Answer 5

Алгоритм, который вы должны использовать (и параметры, которые вы ему задаете), зависит от того, как выглядит ваш набор данных. Похоже, что вы оцениваете форму волны какого-то физического измерения, которое получается непрерывно.

Если это так, то вам нужно решить, хотите ли вы игнорировать локальные минимумы и максимумы (например, всплески шума в сигнале). Кроме того, вам понадобится какой-то способ обработки границ вашего набора данных. Другими словами, считается ли начало ваших данных максимумами, если это самая высокая точка в текущем наборе данных, но она просто спускается с большого пика в предыдущем?

Стандартные алгоритмы обнаружения пиков обычно имеют какой-либо способ задания порога, а также ширины (для контроля чувствительности к пикам) и размера буфера (для обработки действительно постепенных пиков).

Существует множество алгоритмов, просто выберите один или два и настраивайте параметры, пока они не дадут ожидаемых результатов.

Answer 6

Поскольку кривая всегда квадратична (и, следовательно, всегда выпукла), должно быть доступно много методов (хотя, поскольку я не программирую на c #, я не знаю, доступен ли источник). Сначала приходит на ум метод Ньютона, но есть и другие (например, методы внутренней точки). Математическое обоснование этих алгоритмов (но не их реализации, к сожалению) см. В этом учебнике (pdf). Если вы используете какой-либо из этих методов, они будут работать и для других выпуклых кривых.

Answer 7

Все ли у вас доступно множество очков? И нет ли ограничений на «форму» функции, которую представляют эти точки? Если это так, то вы, вероятно, застряли, итерация по точкам будет вашим лучшим выбором ...
Хотя, если у вас есть какая-то другая работа с этим набором, вы можете отсортировать ее по Y-координатам для использования при дальнейшей обработке.

(Держите оба массива рядом - тот, который вы вводили в качестве входных данных (вероятно, он отсортирован по x-corrd?), И тот, который отсортирован по значению функции (y-координата)) ...

Редактировать: если вы знаете, что кривая всегда будет иметь форму, подобную части кривой Sin / Cos, тогда , если вы знаете наименьший период, который может быть представлен , вы можете выполнить некоторые оптимизации, используя алгоритм бинарного поиска, чтобы «искать» точки перегиба (где наклон (изменение Y влево и вправо) имеют разные знаки. Для каждой точки, исследуемой на влево переместите вправо на куски = половину допустимого периода, пока не найдете точку перегиба или знак изменения наклона ... Затем вернитесь на половину последнего изменения x, пока не найдете точку перегиба. [ Сделайте обратное для точек справа]

Рекурсивная процедура, которая исследует / находит первую и последнюю точку перегиба, сравнивает их, чтобы определить, какая из них максимальна, а затем рекурсивно исследует и находит точку заражения на полпути между ними, пока две задействованные точки не станут меньше наименьшего допустимого период, следующий друг за другом, приведет к некоторому приросту производительности ...

2-е РЕДАКТИРОВАНИЕ : Так как я прочитал за год другой комментарий, этот набор никогда не будет содержать более одной точки перегиба ... Если это так, то просто выполните бинарный поиск, чтобы найти его.

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