Полиномиальный обратный

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

y = ax5 + bx4 + cx3 + dx2 + ex + f

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

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


algorithm math inverse solver
person Anlo    schedule 05.04.2011    source источник
comment
Что вы подразумеваете под неитеративным?   -  person kennytm    schedule 05.04.2011
comment
А какой у тебя вопрос? Также это лучше подходит для mathoverflow.net или math.stackexchange. .com   -  person Darin Dimitrov    schedule 05.04.2011
comment
Это не проблема с точными решениями для каждого af, а важная математическая задача: en.wikipedia.org/ wiki/Quintic_function Есть ли у вас ограничения на af? В противном случае вы, вероятно, не сможете добиться большего успеха, чем итеративное.   -  person J Trana    schedule 05.04.2011
comment
В любом случае итеративное решение может оказаться более быстрым и точным. Ньютон-Рафсон сходится чрезвычайно быстро, и многие из специальных квинтик, имеющих аналитические решения, в любом случае также имеют чрезвычайно большое количество вычислений, каждое из которых способно вносить свои собственные ошибки округления.   -  person marshall.ward    schedule 05.04.2011
comment
Также, если вам нужны все решения, вы можете найти одно с помощью N-R, разделить ax^5 + bx^4 + cx^3 + dx^2 + ex + f - y на x-solution, а затем решить полученную квартику, используя формулу. В принципе работает, но я не знаю, насколько он численно стабилен, особенно учитывая, что solution является приблизительным.   -  person Steve Jessop    schedule 05.04.2011
comment
@Steve: здесь действительно важна стабильность. Есть два метода, с помощью которых вы можете сдувать, и один из них должен сдуваться либо по наименьшему корню, либо по наибольшему (и выбрать соответствующий метод). На самом деле алгоритм Дженкинса-Трауба довольно элегантно решает эту проблему.   -  person Alexandre C.    schedule 05.04.2011
comment
@Anlo - Не могу не думать, что, если вы начинаете с выборочных данных и знаете, что есть только один корень, полином может быть не тем местом для начала. Нельзя ли просто работать напрямую с данными? Я предполагаю, что данные, по крайней мере, немного зашумлены, иначе это было бы тривиально.   -  person Keith    schedule 06.04.2011

Ответы (3)


arrow_upward
8
arrow_downward

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

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

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

Тем не менее, если у вас есть доступ к пакету linear alebra, простым, надежным, стабильным и эффективным способом является вычисление собственных значений компаньона матрица. Это то, что напр. ГСЛ делает.

person Alexandre C.    schedule 05.04.2011
comment
К вашему сведению, существует реализация C++ с открытым исходным кодом (лицензия BSD) алгоритма Дженкинса-Трауба под названием RPOLY++. - person kip622; 20.09.2015

arrow_upward
2
arrow_downward

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

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

person Rupert Swarbrick    schedule 05.04.2011
comment
Печально, что Галуа изобрел абстрактную алгебру быстрее, чем большинство математиков могут ее изучить. - person Steve Jessop; 05.04.2011
comment
Ваша первая фраза непонятна. Существуют решения в замкнутой форме для квинтики, но они включают гипергеометрические функции. - person Alexandre C.; 05.04.2011
comment
Хорошо, если Анло посмотрит на это: вы не можете записать решение общей кубики, используя радикалы. Александру: Я почти уверен, что, учитывая вопрос выше, Анло не думал о гипергеометрических функциях. - person Rupert Swarbrick; 05.04.2011
comment
если бы гипергеометрические функции было просто вычислить, это дало бы прямой ответ. К сожалению, это не так. - person Alexandre C.; 05.04.2011
comment
да. На самом деле вы можете сказать это на языке en.wikipedia.org/wiki/Elementary_functions: гипергеометрическая функции могут быть выражены только в виде бесконечных рядов. В любом случае, я думаю, что мы пишем, что согласны друг с другом, так что мы, вероятно, можем прекратить печатать сейчас :-) - person Rupert Swarbrick; 06.04.2011

arrow_upward
1
arrow_downward

Newton-Raphson даст вам только одно решение. Их может быть до 5 на квинтику.

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

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

person Michael Anderson    schedule 05.04.2011
comment
Это неправильно; N-R может дать вам все пять корней. Вам просто нужно изменить начальную точку и границы. - person duffymo; 05.04.2011
comment
@duffymo: за исключением того, что бассейны конвергенции очень нерегулярны, поэтому вы не можете выбрать, какой корень вы в конечном итоге найдете. Использование теоремы Штурма для обнаружения корней и их последующей обработки с помощью NR может быть хорошей идеей, но возможные множественные корни (т.е. два корня в пределах sqrt(epsilon)) вызывают большую озабоченность. - person Alexandre C.; 05.04.2011
comment
Один запуск N-R даст вам только одно решение. Угадать, с чего начать следующую пробежку, чтобы получить другую, довольно сложно. Однако методы, упомянутые Александром С, вероятно, в любом случае более эффективны и надежны. - person Michael Anderson; 05.04.2011