Эффективное вычисление наименьшей фиксированной точки многочлена

Пусть P(x) обозначает рассматриваемый многочлен. Наименьшая фиксированная точка (LFP) P - это наименьшее значение x, такое что x = P (x). Многочлен имеет действительные коэффициенты. В общем случае нет никакой гарантии, что LFP будет существовать, хотя он гарантированно существует, если степень нечетна и ≥ 3. Я знаю эффективное решение, если степень равна 3. x=P(x), таким образом, 0=P( х)-х. Существует кубическая формула в закрытой форме, решение для x несколько тривиально и может быть жестко запрограммировано. Степени 2 и 1 также просты. У меня возникают проблемы с более сложными случаями, поскольку я не могу придумать хороший алгоритм для произвольной степени.

РЕДАКТИРОВАТЬ:

Я рассматриваю только реальные фиксированные точки и беру наименьшую из них, не обязательно фиксированную точку с наименьшим абсолютным значением.


algorithm numerical-methods
person Gregory Nisbet    schedule 06.09.2011    source источник
comment
Под минимумом вы имеете в виду абсолютное значение?   -  person PengOne    schedule 06.09.2011
comment
я думаю, что это относится к теоретическому стеку информатики   -  person Suraj Chandran    schedule 06.09.2011
comment
Вы ограничены полиномами? Поиск корней произвольных функций нетривиален, но я думаю, что для общих полиномов есть хорошие решения.   -  person phkahler    schedule 06.09.2011
comment
@Suraj Chandran: Это не теоретическая информатика.   -  person jason    schedule 06.09.2011
comment
@PengOne Нет. Я рассматриваю только реальные фиксированные точки и беру наименьшие из них.   -  person Gregory Nisbet    schedule 06.09.2011
comment
@Грегори: Хорошо, тогда -1000 меньше 2, верно? Затем просто используйте правило знаков, как я предлагаю ниже, чтобы изолировать конечное пересечение оси x.   -  person PengOne    schedule 06.09.2011

Ответы (3)


arrow_upward
5
arrow_downward

Поскольку вам нужна наименьшая фиксированная точка, вы не можете уйти, не найдя все действительные корни P (x) - x и выбрав наименьший.

Нахождение всех корней многочлена — сложная задача. Если у вас есть рутина черного ящика, то обязательно используйте ее. В противном случае рассмотрите следующий трюк:

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

В противном случае вы можете реализовать алгоритм Jenkins-Traub, который очень нетривиальный кусок кода.

Я действительно не рекомендую находить ноль (например, методом Ньютона) и выкачивать до тех пор, пока вы достигаете первой степени: она очень нестабильна, если не сделана должным образом, и вы потеряете много точности (и с ней очень сложно работать с несколькими корнями). Правильный способ сделать это на самом деле - это вышеупомянутый алгоритм Дженкинса-Трауба.

person Alexandre C.    schedule 06.09.2011
comment
Я действительно не рекомендую находить ноль (например, с помощью метода Ньютона) и сдувать до тех пор, пока вы не достигнете степени один, это очень нестабильно, если не сделать это должным образом, и вы потеряете большую точность. Я понимаю, что это было бы так, если бы многочлен - это черный ящик, но я не понимаю, почему процедура поиска корня + полиномиальное деление - плохая идея, если вы можете легко изучить определение многочлена (скажем, он хранится в виде списка действительных чисел). Насколько я понимаю, метод Ньютона имеет очень быструю сходимость и т. д. Я не сомневаюсь в том, что вы говорите, но мне трудно понять, почему. - person Gregory Nisbet; 08.09.2011
comment
@Грегори: дефляция нестабильна, и процедура теряет точность. Даже для полиномов средней степени вы потеряете достаточную точность, чтобы найти неправильные/несуществующие корни. Кроме того, поиск нескольких корней с помощью метода Ньютона обречен на неудачу: (x - a)^n приблизительно равно эпсилон^n, когда |x - a| ~ эпсилон, так что вы получите только корень энной степени машинной точности. Дефляция на x - a даст вам неточный список коэффициентов. Полиномиальные корни могут быть очень чувствительны к коэффициентам (даже если они являются их непрерывной функцией). - person Alexandre C.; 08.09.2011
comment
Вы также можете ознакомиться с числовыми рецептами, чтобы получить некоторые рекомендации по этой проблеме (а также о том, как решить проблему дефляции). - person Alexandre C.; 08.09.2011

arrow_upward
6
arrow_downward

Просто решите f(x) = P(x) - x, используя ваш любимый численный метод. Например, вы можете повторить

x_{n + 1} = x_n - P(x_n) / (P'(x_n) - 1).

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

person jason    schedule 06.09.2011
comment
но как это гарантирует нахождение наименьшей фиксированной точки? Недостаточно найти произвольный. - person Gregory Nisbet; 06.09.2011
comment
Вам нужно будет найти все нули и выбрать наименьший. Это нетривиально, так как вам нужно определить, сколько нулей является комплексным. - person Mysticial; 06.09.2011
comment
@Greogry Nisbet: Это не так. Но как только вы найдете его, скажем, p, вы можете запустить какой-нибудь метод поиска корней, который ищет корни в (-p, p). - person jason; 06.09.2011
comment
Наименьшее не означает наименьшее абсолютное значение. - person Gregory Nisbet; 06.09.2011
comment
@Грегори Нисбет: О, так вам нужна наименьшая реальная фиксированная точка? - person jason; 06.09.2011
comment
@ Джейсон: Да. Мне жаль, что это было неясно с самого начала. Кроме того, фиксированная точка с наименьшим абсолютным значением не обязательно будет уникальной. - person Gregory Nisbet; 06.09.2011

arrow_upward
0
arrow_downward

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

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

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

person PengOne    schedule 06.09.2011