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

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

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

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

История

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

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

Обоснование

Рассмотрим многочлен <math>n</math>-й степени <math>p(x)</math>, корни которого (пока неизвестные) обозначим <math>x_1;\ x_2\cdots\ x_n</math>:

<math>p(x) = (x-x_1)(x-x_2)\cdots(x-x_n)</math>

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

<math>q(x)=(x-x_1^2)(x-x_2^2)\cdots(x-x_n^2).</math>

Его коэффициенты можно вычислить следующим образом. Поскольку <math>x^2-x_k^2=(x-x_k)(x+x_k),</math> получаем:

<math>q(x^2) = (x^2-x_1^2)(x^2-x_2^2)\cdots(x^2-x_n^2)=(-1)^n\,p(x)p(-x).</math>

Если обозначить коэффициенты <math>p(x),q(x)</math> через <math>a_k,b_k</math> соответственно:

<math>p(x)=x^n+a_1x^{n-1}+\cdots+a_{n-1}x+a_n,</math>

<math>q(x)=x^n+b_1x^{n-1}+\cdots+b_{n-1}x+b_n,</math>

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

<math>b_k=(-1)^k\,a_k^2+2\sum_{j=1}^{k}(-1)^j\,a_{k-j}a_{k+j},</math>

где принято, что <math>a_j=0</math> при <math>j<0</math> или <math>j>n, a_0=b_0=1.</math>

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

В результате в формулах Виета для последнего многочлена <math>q(y)</math>:

<math>a_1=-(y_1+y_2+\cdots+y_n);\ a_2 = y_1 y_2 + y_1 y_3+\cdots+y_{n-1} y_n;\ \dots a_n=(-1)^n y_1 y_2 \cdots y_n.</math>

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

<math> y_1\approx -a^k_{\;1},\; y_2\approx -a^k_{\;2}/a^k_{\;1}, \;\dots\; y_n\approx -a^k_{\;n}/a^k_{\;n-1}.</math>

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

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

Применение

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

При наличии у <math>p(x)</math> комплексных корней метод также применим, но включает некоторые усложнения, подробно описанные в приведенной ниже литературе.

См. также

• Численное решение уравнений

Литература

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

Ссылки

• Брудно А. Л. [kvant.mccme.ru/1989/04/metod_lobachevskogo.htm Метод Лобачевского].// Квант. № 4 (1989), С. 51—53.
• Weisstein, Eric W. [mathworld.wolfram.com/GraeffesMethod.html Graeffe's Method] (англ.) на сайте Wolfram MathWorld.
• [math.fullerton.edu/mathews/n2003/GraeffeMethodMod.html Module for Graeffe's Method by John H. Mathews]

Отрывок, характеризующий Метод Лобачевского — Греффе

Князь Андрей посмотрел на него и, не отвечая, продолжал, обращаясь к Алпатычу:
– Так скажи, что до десятого числа жду ответа, а ежели десятого не получу известия, что все уехали, я сам должен буду все бросить и ехать в Лысые Горы.
– Я, князь, только потому говорю, – сказал Берг, узнав князя Андрея, – что я должен исполнять приказания, потому что я всегда точно исполняю… Вы меня, пожалуйста, извините, – в чем то оправдывался Берг.
Что то затрещало в огне. Огонь притих на мгновенье; черные клубы дыма повалили из под крыши. Еще страшно затрещало что то в огне, и завалилось что то огромное.
– Урруру! – вторя завалившемуся потолку амбара, из которого несло запахом лепешек от сгоревшего хлеба, заревела толпа. Пламя вспыхнуло и осветило оживленно радостные и измученные лица людей, стоявших вокруг пожара.
Человек во фризовой шинели, подняв кверху руку, кричал:
– Важно! пошла драть! Ребята, важно!..
– Это сам хозяин, – послышались голоса.
– Так, так, – сказал князь Андрей, обращаясь к Алпатычу, – все передай, как я тебе говорил. – И, ни слова не отвечая Бергу, замолкшему подле него, тронул лошадь и поехал в переулок.


От Смоленска войска продолжали отступать. Неприятель шел вслед за ними. 10 го августа полк, которым командовал князь Андрей, проходил по большой дороге, мимо проспекта, ведущего в Лысые Горы. Жара и засуха стояли более трех недель. Каждый день по небу ходили курчавые облака, изредка заслоняя солнце; но к вечеру опять расчищало, и солнце садилось в буровато красную мглу. Только сильная роса ночью освежала землю. Остававшиеся на корню хлеба сгорали и высыпались. Болота пересохли. Скотина ревела от голода, не находя корма по сожженным солнцем лугам. Только по ночам и в лесах пока еще держалась роса, была прохлада. Но по дороге, по большой дороге, по которой шли войска, даже и ночью, даже и по лесам, не было этой прохлады. Роса не заметна была на песочной пыли дороги, встолченной больше чем на четверть аршина. Как только рассветало, начиналось движение. Обозы, артиллерия беззвучно шли по ступицу, а пехота по щиколку в мягкой, душной, не остывшей за ночь, жаркой пыли. Одна часть этой песочной пыли месилась ногами и колесами, другая поднималась и стояла облаком над войском, влипая в глаза, в волоса, в уши, в ноздри и, главное, в легкие людям и животным, двигавшимся по этой дороге. Чем выше поднималось солнце, тем выше поднималось облако пыли, и сквозь эту тонкую, жаркую пыль на солнце, не закрытое облаками, можно было смотреть простым глазом. Солнце представлялось большим багровым шаром. Ветра не было, и люди задыхались в этой неподвижной атмосфере. Люди шли, обвязавши носы и рты платками. Приходя к деревне, все бросалось к колодцам. Дрались за воду и выпивали ее до грязи.
Князь Андрей командовал полком, и устройство полка, благосостояние его людей, необходимость получения и отдачи приказаний занимали его. Пожар Смоленска и оставление его были эпохой для князя Андрея. Новое чувство озлобления против врага заставляло его забывать свое горе. Он весь был предан делам своего полка, он был заботлив о своих людях и офицерах и ласков с ними. В полку его называли наш князь, им гордились и его любили. Но добр и кроток он был только с своими полковыми, с Тимохиным и т. п., с людьми совершенно новыми и в чужой среде, с людьми, которые не могли знать и понимать его прошедшего; но как только он сталкивался с кем нибудь из своих прежних, из штабных, он тотчас опять ощетинивался; делался злобен, насмешлив и презрителен. Все, что связывало его воспоминание с прошедшим, отталкивало его, и потому он старался в отношениях этого прежнего мира только не быть несправедливым и исполнять свой долг.
Правда, все в темном, мрачном свете представлялось князю Андрею – особенно после того, как оставили Смоленск (который, по его понятиям, можно и должно было защищать) 6 го августа, и после того, как отец, больной, должен был бежать в Москву и бросить на расхищение столь любимые, обстроенные и им населенные Лысые Горы; но, несмотря на то, благодаря полку князь Андрей мог думать о другом, совершенно независимом от общих вопросов предмете – о своем полку. 10 го августа колонна, в которой был его полк, поравнялась с Лысыми Горами. Князь Андрей два дня тому назад получил известие, что его отец, сын и сестра уехали в Москву. Хотя князю Андрею и нечего было делать в Лысых Горах, он, с свойственным ему желанием растравить свое горе, решил, что он должен заехать в Лысые Горы.
Он велел оседлать себе лошадь и с перехода поехал верхом в отцовскую деревню, в которой он родился и провел свое детство. Проезжая мимо пруда, на котором всегда десятки баб, переговариваясь, били вальками и полоскали свое белье, князь Андрей заметил, что на пруде никого не было, и оторванный плотик, до половины залитый водой, боком плавал посредине пруда. Князь Андрей подъехал к сторожке. У каменных ворот въезда никого не было, и дверь была отперта. Дорожки сада уже заросли, и телята и лошади ходили по английскому парку. Князь Андрей подъехал к оранжерее; стекла были разбиты, и деревья в кадках некоторые повалены, некоторые засохли. Он окликнул Тараса садовника. Никто не откликнулся. Обогнув оранжерею на выставку, он увидал, что тесовый резной забор весь изломан и фрукты сливы обдерганы с ветками. Старый мужик (князь Андрей видал его у ворот в детстве) сидел и плел лапоть на зеленой скамеечке.
Он был глух и не слыхал подъезда князя Андрея. Он сидел на лавке, на которой любил сиживать старый князь, и около него было развешено лычко на сучках обломанной и засохшей магнолии.
Князь Андрей подъехал к дому. Несколько лип в старом саду были срублены, одна пегая с жеребенком лошадь ходила перед самым домом между розанами. Дом был заколочен ставнями. Одно окно внизу было открыто. Дворовый мальчик, увидав князя Андрея, вбежал в дом.
Алпатыч, услав семью, один оставался в Лысых Горах; он сидел дома и читал Жития. Узнав о приезде князя Андрея, он, с очками на носу, застегиваясь, вышел из дома, поспешно подошел к князю и, ничего не говоря, заплакал, целуя князя Андрея в коленку.
Потом он отвернулся с сердцем на свою слабость и стал докладывать ему о положении дел. Все ценное и дорогое было отвезено в Богучарово. Хлеб, до ста четвертей, тоже был вывезен; сено и яровой, необыкновенный, как говорил Алпатыч, урожай нынешнего года зеленым взят и скошен – войсками. Мужики разорены, некоторый ушли тоже в Богучарово, малая часть остается.