7.5. Аппроксимация вещественных корней полиномиального уравнения

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

Ниже мы рассматриваем два метода аппроксимации, первый из которых основан на бисекции, а второй использует цепные дроби вместе с теоремой Винсента; см. (Akritas et al., 1983; Cajori, 1910; Ng, 1980; Nordgaard, 1922; Verbaeten, 1975).

7.5.1. Аппроксимация вещественного корня с использованием бисекции

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

Алгоритм бисекции.

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

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

в интервале в то время как если имеет тот же знак, что и то корень находится в интервале Этот процесс повторяется, пока длина текущего интервала не станет меньше или равной

Из разд. 3.1.2 и 7.2.2 мы можем легко увидеть, что метод бисекций аппроксимирует корень с точностью за время

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

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

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

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