Полиномы

Массивы и классические алгоритмы математики

Полиномом n-й степени называют функцию:

(6.1)

Если рассматривать график этой функции на плоскости, то и - это декартовы координаты точек графика функции. Значения (k из интервала [0,n]) называются коэффициентами полинома. Все они принадлежат одному типу и при программной работе с полиномами представляются одномерным массивом с n+1 элементами.

Если задан массив коэффициентов полинома , то вычислить значение полинома в точке не представляет особой сложности. Но ни один уважающий себя программист не позволит себе вычислять значение полинома, буквально пользуясь схемой 6.1, требующей n-1 операций возведения в степень, n операций умножения и n операций сложения. Прекрасный пример того, как можно упростить алгоритм, дает схема Горнера, вообще не требующая возведения в степень. В этой схеме полином представляют в виде:

(6.2)

Удобнее представлять схему Горнера в рекуррентной форме:

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

Если - полином n-й степени с коэффициентами , - полином n-й степени с коэффициентами и , то из этого следует равенство соответствующих коэффициентов:

(6.3)

Многие задачи над полиномами связаны с определением их корней. Напомню, является корнем полинома, если . У полинома n-й степени не более чем действительных корней. Если - нечетно, то полином имеет хотя бы один действительный корень. Все корни полинома принадлежат некоторому конечному интервалу [c, d]. Вне этого интервала поведение полинома определяется его старшим членом - . Для полинома четной степени обе ветви уходят в , если и в , если . Для полинома нечетной степени ветви полинома вне интервала [c, d] разнонаправлены. Если , то правая ветвь уходит в , а левая ветвь - в . Если , то левая ветвь уходит в , а правая ветвь - в .

Когда по каким-либо физическим соображениям интервал [c, d] известен хотя бы приблизительно, задача нахождения корней полинома облегчается, в противном случае она может быть довольно трудной, особенно для случая близко расположенных корней.