КОРНЕЙ АЛГЕБРАИЧЕСКИХ МНОГОЧЛЕНОВ СПОСОБЫ ВЫЧИСЛЕНИЯ.
Нахождение всех корней алгебр, многочлена является одной из наиболее часто встречающихся вспомогательных задач, возникающих неоднократно при решении таких важных задач, как устойчивость движения, и др. Рассмотрим детально лишь два наиболее эффективных способа нахождения корней на цифровых и гибридных вычисл. машинах.
Для больших ЦВМ необходимы такие методы нахождения корней многочлена, которые, с одной стороны, были бы универсальными, т. е. пригодными для любых коэфф. (комплексных или действительных), не зависели от входных данных (начального приближения и т. п.), требовали при своей реализации только наличия коэфф. многочлена (минимум информации); с другой стороны, являлись бы быстросходящимися. Построить такие методы возможно путем создания «гибридов» между методами спуска и методом Ньютона; это связано с отсутствием у поверхности
где
многочлен
экстремумов локальных, отличных от корней.
Пусть
и для некоторого х
Тогда, используя разложение в ряд Тейлора, получим:
Перемножив эти равенства, получим
где
. При достаточно малом
знак левой части равенства (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.
Г. И. Грездов, В. В. Иванов, М. Д. Маергойз.