Geum.ru

В. Г. Иваненко Московский инженерно-физический институт (государственный университет)

Вид материалаДокументы
Подобный материал:

УДК 004.056:378(06) Проблемы информационной безопасности в системе высшей школы

В.Г. Иваненко

Московский инженерно-физический институт (государственный университет)


Способ определения корней полинома n-й степени как функции его свободного члена


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


Определение корней полинома n-й степени как вычислительная задача весьма часто встает при решении самых разных практических проблем, в том числе и в криптографии. Известно, что для полиномов выше третьей степени нет готовых формул вычисления их корней и решение находят различными итерационными методами. Точность вычисления корней оказывается весьма чувствительной к значениям коэффициентов полинома, а в случае, когда искомые корни близки друг к другу, отмеченная чувствительность становится слишком большой, что является одной из основных проблем при решении рассматриваемой задачи.

Предлагаемый ниже способ нахождения корней полинома произвольной степени основывается на так называемом методе корневого годографа [1], хорошо известном и широко применяемом в технической кибернетике. С помощью этого метода корни полинома

An(x)=xn+a1xn-1+a2xn-2+…+an-1x+an=0 (1)

находятся графоаналитически как траектории корней характеристического уравнения

P(x)+ kQ(x)=0, (2)

где k – изменяющийся от нуля до бесконечности параметр, а P(x) и Q(x) – полиномы, корни которых должны быть известны. В итоге искомая задача сводится к разложению исходного полинома (1) на полиномы P и Q, вычислению их корней и последовательности графических построений на комплексной плоскости корней с элементарными арифметическими вычислениями, которые можно осуществить вручную или на простейшем калькуляторе.

Нахождение корней полиномов P(x) и Q(x) (2) предлагается осуществлять так же, как и для Аn(x). В итоге процедура решения решаемой задачи выглядит следующим образом.
  1. Из коэффициентов исходного полинома (1) сформируем полином второй степени

A2(x)=x2+a1x+a2 , (3)

корни которого находятся элементарно.
  1. Из коэффициентов выражения (1) сформируем полином третьей степени

A3(x)=x3+a1x2+a2x+a3=x(x2+a1x+a2)+a3 , (4)

откуда, согласно (2), можно записать, что

P3(x)=x(x2+a1x+a2), Q3(x)=1, k3=a3.

Корни P3(x) нам известны – это два корня (3) плюс один нулевой. Далее методом корневого годографа [1] определяем на комплексной плоскости x траектории всех трех корней полинома (4) как функции параметра k3 и выбираем три конкретных корня, соответствующих значению k3=a3 .
  1. Из коэффициентов уравнения (1) сформируем полином четвертой степени

A4(x)=x4+a1x3+a2x2+a3x+a4=x(x3+a1x2+a2x+a3)+a4 , (5)

где, очевидно,

P4(x)=x(x3+a1x2+a2x+a3), Q4(x) =1, k4=a4 .

Корни P4(x) нам известны – один нулевой и еще три корня из предыдущего п.2. Затем вновь методом корневого годографа находим корни полинома (5) как функции параметра k4 и выбираем те из них, для которых k4=a4. Далее продолжаем подобную процедуру с увеличением каждый раз степени полинома Ai(x) на единицу, пока не дойдем до степени n.

Общее число шагов, равное (n-2), можно сократить примерно вдвое, если на каждом шаге степень полинома Ai(x) увеличивать не на 1, а на 2, что для отмеченного выше п.2 будет выглядеть следующим образом:

A4(x)=x4+a1x3+a2x2+a3x+a4=x2(x2+a1x+a2)+a3(x+a4/a3),

при этом

P4(x)=x2(x2+a1x+a2), Q=x+a4/a3, k4=a3 .

Точность предлагаемого метода составляет единицы процента, а общее время решения при некотором навыке для степени полинома 5 – 8 не превышает десятков минут.


Список литературы


1. Удерман Э. Г. Метод корневого годографа а теории автоматических систем. – М., Наука, 1972.


ISBN 5-7262-0636-3. XIII Всероссийская научная конференция