Максимум многочлена
У меня есть многочлен порядка N (где N четное). Этот полином равен минус бесконечность для х минус / плюс бесконечность (таким образом, он имеет максимум). То, что я делаю сейчас, это взятие производной полинома с помощью polyder затем найти корни полинома N-1-го порядка с помощью roots функция в Matlab, которая возвращает N-1 решения. Затем я выбираю настоящий корень, который действительно максимизирует полином. Проблема в том, что я много обновляю свой многочлен, и на каждом шаге по времени я использую описанную выше процедуру, чтобы найти максимизатор. Поэтому функция root занимает слишком много времени на вычисления, что замедляет работу моего приложения. Есть ли способ или в Matlab, или в предложенном алгоритме, который делает эту максимизацию эффективным с точки зрения вычислений способом (т.е. просто находит одно решение вместо N-1 решений)? Благодарю.
Редактировать: я также хотел бы знать, есть ли в Matlab подпрограмма, которая возвращает только реальные корни вместо roots который возвращает все реальные / сложные.
2 ответа
Стив Моррис представляет файл для обмена файлами, который находит все настоящие корни функций за заданный интервал. Это делается путем интерполяции полинома по полиному Чебычева и нахождения его корней.
Вы можете изменить eig оценка сопутствующей матрицы там, чтобы eigs, Это позволяет вам найти только один (или несколько) корней и сэкономить время (есть большая вероятность, что аналитически можно вычислить корни или экстремумы Чебычева, хотя я не смог найти для этого хорошую ссылку (или даже плохую) один в этом отношении...)).
Еще одна попытка ускорить процесс - отметить, что polyder не делает ничего больше, чем
Pprime = (numel(P)-1:-1:1) .* P(1:end-1);
для вашего полинома P, Также, roots ничего не делает, кроме как находит собственные значения матрицы-компаньона, так что вы можете найти эти собственные значения самостоятельно, что предотвращает вызов roots, Это может быть полезным, поскольку вызовы не встроенных функций внутри цикла не позволяют JIT-компилятору Matlab преобразовать цикл в машинный язык. В противном случае это может дать вам большой прирост скорости (не менее чем в 100 раз больше).
Я думаю, что вам, вероятно, не повезло. Если коэффициенты полинома меняются на каждом временном шаге произвольным образом, то в конечном итоге вы сталкиваетесь с отдельной и не связанной с этим задачей оптимизации на каждом этапе. Недостаточно информации, доступной для рассмотрения вычисления только подмножества корней производного полинома - как узнать, какой производный корень обеспечивает максимальную стационарную точку полинома, не сравнивая значение функции на ВСЕХ производных корней? Если ваши полиномиальные коэффициенты возмущались на каждом шаге только (ограниченной) небольшой величиной или предсказуемым образом, то вполне возможно, что вы сможете попробовать что-то итеративное для уточнения решения на каждом шаге (например, что-то грубое, такое как как использование ваших предыдущих корней в качестве отправной точки нового набора итераций Ньютона для идентификации обновленных производных корней), но вопрос не предполагает, что это действительно так, поэтому я просто догадываюсь. Я могу быть совершенно не прав, но вам может не повезти в получении чего-то более быстрого, если вы не можете предоставить больше информации о некоторой связи между полиномами, сгенерированными на каждом шаге.