КОРНЕЙ АЛГЕБРАИЧЕСКИХ МНОГОЧЛЕНОВ СПОСОБЫ ВЫЧИСЛЕНИЯ.

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

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

Пусть и для некоторого х

Тогда, используя разложение в ряд Тейлора, получим:

Перемножив эти равенства, получим

где . При достаточно малом знак левой части равенства (1) определяется знаком Он отрицательный при т. е. для каждой фиксированной точки z есть I секторов убывания и I секторов возрастания ф-ции где I — порядок первой отличной от нуля производной ф-ции в точке z. Наискорейшее убывание (наискорейший спуск) будет при

Следовательно,

где . Из (1) ясно, что при t достаточно малом и h, выбранном согласно равенству (2), будет выполняться неравенство

Заменив z на на и h на получим

где порядок первой отличной от нуля производной ф-ции в точке

При имеем (метод Воеводина)

Т. о., взяв в ур-нии (3) одно из значений корня степени из комплексного числа, получим единую итеративную схему как для стационарной, так и для нестационарной точек.

Т. к. в ур-нии заранее неизвестно, то используют следующий итеративный процесс:

если Ясно, что найдется такой номер 7, для которого будет справедливо неравенство В этом случае полагаем Итеративный процесс (3) и (5) сходится с любого начального приближения к одному из корней алгебр, многочлена. В связи с тем, что вблизи искомого корня находится окрестность этого корня, в которой сходится метод Ньютона. Поэтому процесс (3) и (5) после конечного числа итераций К перейдет в метод Ньютона

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

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

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

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

где погрешности коэфф. Если все не превосходят то

Абс. погрешность метода может быть (для некратных корней) оценена по ф-ле

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

при представлении чисел в форме с фиксированной запятой и

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

Наиболее распространенным К. а. м. с. в. на гибридных вычислительных машинах является метод сведения к задаче отыскания минимумов ф-ции где положительно определенная, непрерывная вместе со своими производными ф-ция вида действительные ф-ции, — достаточно малая постоянная величина. Ф-ция имеет в каждой точке столько секторов убывания и возрастания, каков наименьший порядок производной многочлена отличной от нуля. не имеет локальных минимумов, отличных от глобального. Для отыскания корней на гибридных вычисл. машинах применяются методы быстрого спуска, в частности, методы покоординатного спуска из различных точек пространства искомых переменных, что обусловлено быстрым отысканием корней из различных точек (время поиска равно 0,5 сек) и хорошей наглядностью поиска корней. На внешних устр-вах гибридных вычисл. машин удобно наблюдать траектории поиска корней из различных точек пространства искомых переменных, сечения ф-ции Ф плоскостями и т. д. Для вычисления любого многочлена здесь можно ограничиться такими операциями, как линейная комбинация и перемножение ф-ций, а также суперпозиция ф-ций. Для конструирования ф-лы многочлена с помощью таких операций вводятся дополнительные ур-ния, напр., для многочлена 4-й степени с помощью дополнительных ур-ний находятся элементы комплексного числа после чего

Лит.: Загускин В. Л. Справочник по численным методам решения алгебраических и трансцендентных уравнений. М., 1960 [библиогр. с. 210—213]; Воеводин В. В. Применение метода спуска для определения всех корней алгебраического многочлена. «Журнал вычислительной математики и математической физики», 1961, т. 1, № 2; Кац И. С., Маергойз М. Д. Решение нелинейных алгебраических и трансцендентных уравнений в комплексной области. «Журнал вычислительной математики и математической физики», 1967, т. 7, 1963.

Г. И. Грездов, В. В. Иванов, М. Д. Маергойз.