Главная > Энциклопедия кибернетики. Т.1
НАПИШУ ВСЁ ЧТО ЗАДАЛИ
СЕКРЕТНЫЙ БОТ В ТЕЛЕГЕ
<< Предыдущий параграф Следующий параграф >>
Пред.
След.
Макеты страниц

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

Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике

ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO

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

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

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

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

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

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

где . При достаточно малом знак левой части равенства (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.

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

1
Оглавление
email@scask.ru