Вычисление корней полиномов

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

Численные методы решения этой задачи строятся по одному и тому же шаблону: выбирается первое (при отсутствии априорных данных –произвольное) значение корня и вычисляется значение функции при этом значении; теперь стоит задача скорректировать текущее значение x_k так, чтобы соответствующее значение полинома оказалось ближе к нулю.

x_k+1=x_k+d.

Приходится определять направление и величину шага коррекции d.

Для нашего случая, когда левая часть нелинейного уравнения – полином P(z), то есть легко дифференцируемая функция, наиболее подходящим будет видимо классический метод Ньютона или его модификации. Алгоритм Ньютона получается из простых геометрических соотношений – шаг коррекции можно определить как катет прямоугольного треугольника, другим катетом которого является значение полинома в текущей точке, а тангенс противолежащего ему угла есть производная полинома в той же текущей точке:

d=–P(z_k)/P⁽¹⁾(z_k),

z_k+1=z_k–P(z_k)/P⁽¹⁾(z_k), где k – номер итерации.

Можно вычислить производную только в точке первого приближения и использовать ее значение на всех последующих шагах, пожертвовав некоторым снижением скорости сходимости:

z_k+1=z_k–P(z_k)/P⁽¹⁾(z₀).

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

,

где j – порядок очередной производной с достаточно удаленным от нуля значением, t – коэффициент шага коррекции, выбираемый так, чтобы P(z_k+1) было меньше P(z_k).

Перед началом поиска корней можно избавиться от кратных делением исходного полинома на его НОД с первой производной, но потом придется определять кратность корней, пока их количество не станет равным порядку полинома.

Методы определения корней для полиномов степеней ниже пятой, известные из курса элементарной алгебры, рассмотрены кратко при описании программной реализации.