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

Question

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

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

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

Answer 1

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

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

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

Answer 2

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

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

• Форма М * сопутствующая матрица из P (x) - x
• Найти все собственные значения M

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

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

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

Answer 3

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

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

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