Нахождение корней полиномов

Рассмотренные выше методы решения нелинейных трансцендентных уравнений пригодны и для алгебраических уравнений. Вместе с тем, есть некоторые особенности.

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

С другой стороны,

1) для полиномов всегда наперед известно число корней: полином P_n (x) = a_nxⁿ + a_{n– 1} x^{n– 1} +… + a ₁ x + a ₀, где a ₀, … a_n – действительные числа (a_n ¹0) имеет ровно n корней, действительных или комплексных, при условии, что каждый корень считается столько раз, какова его кратность;

2) комплексные корни образуют комплексно–сопряженные пары, т.е. каждому корню x = c + id соответствует x = c – id;

3) известны оценки границ корней полинома: [1], где

(5.11)

Отметим, что, во-первых, это завышенные оценки, и, во-вторых, в связи с малостью r на практике пользуются оценкой , и, в-третьих, эти оценки справедливы и для комплексных корней.

Пример. P ₃(x) = 0,6 x ³ – 4 x ² + 5 x + 4 =0.

; .

Корни этого полинома x₁» –0,544; x₂» 2,743; x₃» 4,467. Их абсолютные значения лежат в диапазоне [0,4(4); 9,3(3)].

Также известна теорема Лагранжа. Пусть а_n > 0 и 0 £ k £ n– 1 – номер первого отрицательного коэффициента полинома P_n (x), если просматривать их в порядке убывания степени x. Тогда за верхнюю границу положительных корней уравнения P_n (x)=0 может быть взято число , где C наибольшая из абсолютных величин отрицательных коэффициентов полинома P_n (x). Если отрицательных коэффициентов нет, то есть все a_i ³0, то P_n (x) не имеет положительных корней.

Возьмем тот же пример: P ₃(x) = 0,6 x ³ – 4 x ² + 5 x + 4 =0.

k =1; C =4; .

Рассмотрим применение метода Ньютона к решению алгебраического уравнения:

.

На каждом итерационном шаге в точке x_k требуется вычислять значение полинома n -ой степени и полинома n -1 степени

P′ (x) = na_nx^{n– 1} + (n– 1) a_{n –1} x^{n –2} + …+ a ₁.

Для сокращения объема вычислений можно использовать схему Горнера. Имеем рекуррентные формулы b_n = a_n; b_j = a_j + x_k b_{j+ 1}, j = n –1,…,0. В результате получаем P (x_k) =b ₀. Применяем этот же метод к полиному

P′ (x) = d_nx^{n– 1} + d_{n– 1} x^{n– 2} + … + d ₁ ,

получаем рекуррентные формулы

c_n = d_n; c_j = d_j + x_k c_{j+ 1}, j = n– 1, …, 1

и в результате P¢ (x_k) = c ₁. Следовательно, . Отметим, что для уменьшения погрешностей лучше сначала находить наименьшие по модулю корни многочлена и сразу удалять их из уравнения, приводя его к меньшей степени (применяя ту же схему Горнера). Эта процедура помогает и в отыскании кратных корней.

Как быть, если рассматриваемое уравнение имеет комплексные корни? Должно быть ясно, что если все значения функции вещественны и в качестве начального приближения x ₀ также взято вещественное число, то и все последующие значения x_k также будут вещественны.

Однако если взять в качестве x ₀ комплексное число, то последующие x_k также могут оказаться комплексными. Поэтому изложенные методы годятся и для работы с комплексными числами.

Кроме того, многочлен P_n (x), имеющий пару комплексных корней x _1,2 = c ± id, можно записать в следующем виде:

P_n (x) = (x–x ₁)(x–x ₂) P_{n– 2}(x);

или, после подстановки, x ₁ и x ₂

P_n (x) = ((x–с)²+ d ²) P_{n– 2}(x)

и провести анализ, подобный тому, который мы провели выше.