7.5.2. Аппроксимация вещественного корня с использованием цепных дробей

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

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

аппроксимирует корень уравнения с требуемой точностью.

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

Продолжая исследования в направлении, обозначенном в разд. 7.3, следует заметить, что теорема 7.3.9 мажет также использоваться для аппроксимации вещественных корней полиномиального уравнения с любой требуемой точностью (см. историческое замечание 9).

Ясно, что это легко можно достигнуть расширением (вычислением большего числа неполных частных) цепной дроби (V3), что преобразует исходное полиномиальное уравнение в уравнение с ровно одной переменой знаков в последовательности его коэффициентов (см. историческое замечание 10).

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

Предположим, что предел аппроксимации равен и что в процессе аппроксимации вещественного корня q полиномиального уравнения мы вычислили к неполных частных разложения корня в цепную дробь. Тогда из рассуждений разд. 7.3 становится очевидным, что в находится между последовательными подходящими дробями абсолютное значение разности которых равно Следовательно,

и метод завершает работу, когда

для некоторого к.

Ниже мы описываем два способа вычисления цепной дроби (V3), чтобы аппроксимировать с точностью с вещественный корень уравнения. Эти два метода имеют одну и ту же теоретическую оценку времени вычислений, но различную эмпирическую эффективность.

Первый способ вычисления цепной дроби (V3) состоит в вычислении каждого дополнительного неполного частного с помощью правила Коши, как описано в разд. 7.3.4. Однако, в основном из-за правила Коши, этот подход неэффективен, в чем можно убедиться, взглянув на табл. 7.6.2 в разд. 7.6. Фактически он даже медленнее метода бисекций, метода, хорошо известного своей неэффективностью.

Второй способ вычисления цепной дроби (V3) — воспользоваться преимуществами специальных свойств полиномов, с которыми

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

Теорема 7.5.1. Пусть — полиномиальное уравнение степени с только одной переменой знаков в последовательности своих целых коэффициентов. Тогда

— верхняя граница значения его (единственного) положительного корня.

Доказательство. Для любой степени переменной мы имеем

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

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

для , и это доказывает теорему.

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

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

(см. упражнения по программированию для этого раздела).

APPROX-CF. Аппроксимация вещественного корня уравнения с использованием цепных дробей (Approximate a Real Root of an Equation Using Continued Fractions)

Вход: Предел аппроксимации e, являющийся рациональным числом, и уравнение с полиномом из которого получаем изолирующий интервал для корня; — полиномиальное уравнение степени с одной переменой знаков в последовательности его целых коэффициентов, полученное из исходного уравнения после подстановки Для некоторых определенных значений . Мы хотим аппроксимировать с точностью корень уравнения расположенный в открытом интервале с неупорядоченными концевыми точками Очевидно, что , потому что иначе нам нечего делать.

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

1а. [Инициализация] Положить . [Уточнение цепной дроби] Пользуясь вычислить — целую часть положительного корня уравнения Если то перейти к шагу 5.

2. Модифицировать .

3. [Корень?] Если то положить где получены из вернуть замкнутый интервал

и закончить работу. (Положительный корень, который мы пытались аппроксимировать, - рациональное число.)

4. [Готово?] Если , то вернуть открытый интервал с неупорядоченными концевыми точками где получены из и закончить работу. [Этот интервал аппроксимирует корень полинома с заданной точностью.]

5. Положить и перейти к шагу

Анализ времени работы алгоритма APPROX-CF.

Отметим, что время выполнения всего алгоритма доминируется временами выполнения шагов 1 и 2.

Для первой итерации алгоритма мы имеем следующее:

Шаг 1 выполняется за время (см. упражнения по программированию для этого раздела).

Шаг 2 выполняется за время что является временем выполнения подстановки [и включает в себя подстановку Комбинируя это выражение с тем, что Для всех i [см. (А2)], мы получаем что ограничивается величиной

Сравнивая время вычислений для правила Коши (разд. 7.2.3), мы видим, что доминирует над временем вычислений шагов 1 и 2.

Для последующих итераций алгоритма снова доминирует над временем вычисления шагов 1 и 2, поскольку для любого последующего мы имеем (теорема 7.3.13).

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

i. , где есть i-й элемент последовательности Фибоначчи.

ii, (округленное до ближайшего целого), где

Очевидно, из следует откуда мы получаем

Перемножал получаем

Пример. Аппроксимируем с точностью положительный корень уравнения изолирующий интервал которого есть Нам даны полином и рациональная функция с помощью которой мы получили изолирующий интервал; как так и были вычислены в примере разд. 7.3.4.

Применяя APPROX-CF, получаем следующие результаты:

Шаг 1а. Полагаем

Шаг lb. Применение алгоритма дает и мы переходим к шагу 5.

Шаг 5. Здесь мы вычисляем новые полиномы и переходим к шагу

Шаг lb. Применяя получаем

Шаг 2. На этом шаге мы модифицируем полиномы

Шаг 3. Очевидно, что

Шаг 5. Здесь мы вычисляем новые значения и переходим к шагу

Шаг lb. Применяя получаем

Шаг 2. На этом шаге мы модифицируем

Шаг 3. Очевидно, что

Шаг 5. Здесь мы вычисляем новые значения и переходим к шагу

Шаг Применяя получаем

Шаг 2. На этом шаге мы модифицируем

Шаг 3. Очевидно, что

и мы завершаем вычисления.

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