Полиномиальное обратное

Question

У меня есть многочлен пятого порядка:

y = топор ⁵ + bx ⁴ + cx ³ + dx ² + ex + f

Коэффициенты af известны, и мне нужно вычислить x для данного y.Я мог бы, вероятно, использовать алгоритм Ньютона-Рафсона или аналогичный, но я бы предпочел не итеративное решение, если это возможно.

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

Answer 1

Найти корни многочленов сложно и сложно. Получение стабильного надежного алгоритма доставит вам головную боль. Удаление ньютона + root кажется отличной идеей, но заставить работать правильно - очень больно.

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

Современный алгоритм черного ящика: Дженкинс-Трауб . Однако это сложно реализовать, поэтому вам придется где-то найти (или заплатить) реализацию.

Тем не менее, если у вас есть доступ к линейному пакету alebra, простой, надежный, стабильный и эффективный способ - это вычисление собственных значений сопутствующей матрицы . Вот что например. GSL делает.

Answer 2

J Трана вроде как уже ответил на этот вопрос, но ответ в том, что вы вообще не можете найти алгоритм для этого (это математический результат, который сделал Галуа знаменитым).

Кроме того, если это что-то кроме проблемы с домашней работой, вы, вероятно, не хотите, чтобы алгоритм решал эту проблему в радикалах, так как это будет вести себя численно плохо.

Answer 3

Ньютон-Рафсон даст вам только одно решение. Их может быть до 5 для квинтики.

Если вы хотите все решения вам нужно либо соединить Newton-Raphson с root-Removal, либо использовать что-то более надежное.

Один из распространенных методов - использование полиномов Штурма