Глава 7. Отделение и аппроксимация вещественных корней полиномиальных уравнений

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

1. Мы явно различаем отделение и аппроксимацию корней (разд. 7.1), в то время как в большинстве работ аппроксимация корней эквивалентна решению уравнений.

2. Мы даем точные формулировки теорем Бюдана и Фурье и рассматриваем их взаимозависимость (см. также рис. 7.1.1); следует отметить, что формулировку теоремы Бюдана нелегко найти в литературе, в то время как теорема Фурье часто приписывается Бюдану.

3. Мы представляем теорему Винсента 1836 г. и получающиеся на ее основе два метода цепных дробей для отделения вещественных корней уравнения; первый из этих методов принадлежит Винсенту (Vincent, 1836) и имеет экспоненциальное время вычислений, в то время как второй принадлежит автору (Akritas, 1978) и имеет, если справедлива некоторая гипотеза, полиномиальное время счета (лучший из классических методов). Теорема Винсента была так хорошо забыта, что даже такая фундаментальная работа, как Enzyclopaedie der matkemaiischen Wissenschaften, игнорирует ее.

Исследуем прежде всего детально метод бисекций Штурма 1829 г. и метод цепных дробей 1978 г., являющийся самым быстрым из существующих методов. Это — два классических метода, описанные в литературе, для отделения вещественных корней полиномиального уравнения с целыми коэффициентами (см. историческое замечание 1 и рис. 7.1.1). Затем исследуем два соответствующих метода аппроксимации этих (изолированных) корней с любой желаемой степенью точности, а именно, метод бисекций и метод, использующий цепные дроби.

Рис. 7.1.1. Краткий обзор исторического развития двух классических методов отделения вещественных корней полиномиального уравнения с целыми коэффициентами. Метод цепных дробей Винсента 1836 г. не показан, поскольку он экспоненциален (см. также историческое замечание 7).

7.1. Введение и обоснования

Самые ранние из известных аналогов алгебраических уравнений содержатся в папирусе Ринда и, очевидно, компилированы из более ранних работ египтянином Амесом приблизительно в 1650 или 1700 г. до нашей эры. Мы находим, например, следующую задачу: «Количество и его седьмая часть, сложенные вместе, дают 19. Чему равно количество?». Очевидно, задача состоит в том, чтобы решить уравнение , как мы сказали бы сегодня. Из-за недостатка удобных алгебраических обозначений египтяне пользовались громоздким методом, известным впоследствии как метод «ложного положения». Хотя иногда утверждают, что греки умели решать уравнения второй степени, в общем ни египтяне, ни греки не сделали сколько-нибудь заметного продвижения с современной точки зрения. Арабы достигли большего, но только во времена Ренессанса, когда итальянские математики пятнадцатого и шестнадцатого столетий (Тарталья, Кардано и Феррари) преуспели в решении через радикалы общих уравнений третьей и четвертой степени, были выполнены работы,

представляющие длительный интерес. [Интересующийся историей читатель может проследить по другим источникам за борьбой за приоритет между Тартальей и Кардано (см., например, книгу (Burnside, Panton, I960, p. 271-274). Другие источники - (Dickson, 1922; Todhunter, 1882; Turnbull, 1957; Weisner, 1938).)]

В семнадцатом и восемнадцатом столетиях предпринимались многочисленные попытки решить общее уравнение пятой степени; было также достигнуто более глубокое понимание природы корней алгебраического уравнения (особенно после работы Декарта), но, несмотря на все это, никому не удалось решить в радикалах уравнение пятой степени. Естественно, что математики задались вопросом, возможно ли вообще такое решение. Ответ дал Руффини (Ruffini, 1804), первым показавший невозможность алгебраического решения уравнения пятой степени. Позднее Абель (Abel, 1826) доказал, что невозможно в общем случае решать алгебраические уравнения степени выше четвертой.

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

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

Как только прояснились цели, последовали и успехи. В начале девятнадцатого столетия Бюдан и Фурье представили две различные (но эквивалентные) теоремы, позволяющие определять максимум возможного числа вещественных корней уравнения с вещественными коэффициентами на данным интервале. Теорема Бюдана появилась в 1807 г. в работе «Nouvelle methode pour la resolution des equations numeriques», а теорема Фурье была впервые опубликована в 1820 г. в «Le bulletin des sciences par la societe

philomatique de Paris». В силу значимости этих двух теорем возникли большие разногласия относительно приоритетных прав. В своей книге Biographies of distinguished scientific men, с. 383, Араго (Arago, 1859) сообщает, что Фурье «счел необходимым получить подтверждение бывших студентов Политехнической школы или профессоров университета», чтобы доказать, что он преподавал свою теорему в 1796, 1797 и 1803 гг.

Как мы увидим в разд. 7.2, основываясь на предложении Фурье, Штурм представил в 1829 г. улучшенную теорему, применение которой дает точное число вещественных корней полиномиального уравнения из без кратных нулей на вещественном интервале; таким образом, он решил проблему отделения вещественных корней (Bocher, 1911-1912). С 1830 г. метод Штурма становится единственным широко известным и используемым, и, следовательно, теорема Бюдана предается забвению. По нашим сведениям, теорему Бюдана можно найти только в статье Винсента и в работах автора, в то время как предложение Фурье появляется почти во всех текстах по теории уравнений. Теорема Бюдана заслуживает специального внимания, поскольку, как мы увидим в разд. 7.3, она составляет основу теоремы Винсента 1836 г. которая, в свою очередь, составляет основу метода цепных дробей 1978 г. (Akritas, 1980а, ) отделения вещественных корней уравнения, метода, превосходящего метод Штурма по эффективности. [См. также рис. 7.1.1 и (Akritas, 1982).]