Метод Лобачевского — Греффе

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Метод Лобачевского — Греффе — эффективный алгоритм для нахождения корней многочлена. Иногда называется, по именам первооткрывателей, «Метод Лобачевского — Греффе — Данделена» или «Метод Данделена — Лобачевского — Греффе».

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

Недостатками метода являются отсутствие сопутствующего контроля ошибок при ручном счёте и сложность оценки точности результата. Точность метода может оказаться невысокой из-за численной неустойчивости, то есть быстрого накопления погрешности в ходе вычислений[1]. Кроме того, метод медленно сходится, если у многочлена есть корни, равные или очень близкие по модулю (например, +4 и —4)[2].

История[править | править вики-текст]

Рассуждения, близкие к идее данного метода, высказывали ещё в XVII веке Ньютон (в «Универсальной арифметике») и Варинг в «Аналитических этюдах»[3]. Первое краткое изложение идеи опубликовал французский математик Ж. Данделен в 1826 году[4]. Этот мемуар остался незамеченным. Восемь лет спустя аналогичную идею более подробно изложил и развил Н. И. Лобачевский в своём учебнике «Алгебра или вычисление конечных» (1834), но и его работа не привлекла внимания научной общественности[5].

В 1836 году Берлинская академия наук объявила конкурс на разработку удобного метода нахождения комплексных корней многочлена. Среди призёров была статья швейцарского профессора К. Г. Греффе «Die Auflösung der höheren numerischen Gleichungen» (1837). Греффе изложил метод развёрнуто, с многочисленными примерами. В дальнейшем этот алгоритм был несколько усовершенствован И. Ф. Энке (1841) и Э. Карвалло (E. Carvallo, 1890), Впервые имена всех трёх первооткрывателей были указаны в книге Э. Уиттекера и Г. Робинсона «Математическая обработка результатов наблюдений» («The calculus of observations», 1924)[3].

Обоснование[править | править вики-текст]

Рассмотрим многочлен -й степени , корни которого (пока неизвестные) обозначим :

Временно сделаем предположение, что все корни этого многочлена вещественны и различны (нет кратных корней). Обозначим многочлен, корни которого равны квадратам корней :

Его коэффициенты можно вычислить следующим образом. Поскольку получаем:

Если обозначить коэффициенты через соответственно:

то коэффициенты обоих многочленов связаны формулой:

где принято, что при или

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

В результате в формулах Виета для последнего многочлена :

все одночлены, кроме одного, в каждом тождестве исчезающе малы, и система Виета сводится к простым линейным равенствам[6]:

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

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

Применение[править | править вики-текст]

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

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

См. также[править | править вики-текст]

Литература[править | править вики-текст]

  • Березин И. С., Жидков Н. П. Методы вычислений. — М.: Физматлит, 1960. — Т. 2. — С. 103—128. — 620 с.
  • Демидович Б. П., Марон И. А. Основы вычислительной математики. — Изд. 2-е. — М.: Физматлит, 1963. — С. 176—195. — 660 с.
  • Лобачевский Н. И. Алгебра или вычисления конечных, Полн. собр. соч., т. 4, М. - П., 1948.
  • Лобачевского метод // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1982. — Т. 3.

Ссылки[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Математическая энциклопедия, 1982.
  2. Основы вычислительной математики, 1963, с. 177—178..
  3. 1 2 Юшкевич А. П., Башмакова И. Г. «Алгебра или вычисление конечных» Н. И. Лобачевского // Историко-математические исследования. — М.—Л.: ГИТТЛ, 1949. — № 2. — С. 126—127..
  4. Dandelin, G. P. Recherches sur la résolution des équations numériques. Nouveaux mémoires de l'Académie Royale des Sciences et Belles-Lettres de Bruxelles (1826). Volume 3, page 7.
  5. Хрестоматия по истории математики. Арифметика и алгебра. Теория чисел. Геометрия / Под ред. А. П. Юшкевича. — М.: Просвещение, 1976. — С. 85—86. — 318 с.
  6. 1 2 Методы вычислений, 1960, с. 103—105..