7.3.4. Два метода цепных дробей отделения вещественных корней

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

Имеются два метода цепных дробей: Винсента, 1836 г., и автора 1978 г., соответствующие двум различным способам вычисления неполных частных - (см. историческое замечание 7). Как мы увидим ниже, различие между этими двумя методами можно рассматривать как аналог различия между интегралами Римана и Лебега. То есть хорошо известно, что сумма может вычисляться следующими двумя способами:

В основе метода цепных дробей Винсента 1836 г. лежит вычисление какого-то неполного частного - с помощью серии единичных приращений, с каждым из которых мы должны выполнить сдвиг [для некоторого полиномиального уравнения и проверить изменение числа перемен знаков. Этот подход «в лоб» приводит к методу с экспоненциальным поведением, и, следовательно, его практическая ценность невелика. Специального алгоритма для этого метода мы не приводим.

В качестве примера метода Винсента отделим корни полиномиального уравнения

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

быстрой ЭВМ это займет несколько лет. Однако метод Винсента весьма эффективен, когда значения неполных частных маленькие.

Напротив, метод цепных дробей, разработанный автором в 1978 г., заключается в немедленном вычислении какого-либо неполного частного - в качестве нижней границы b значений положительных корней некоторого полинома т.е., пользуясь правилом Коши (разд. 7.2.3), мы немедленно определяем b и полагаем . [Напомним, что вычисление нижней границы (от lower bound — Перев.) значений положительных корней некоторого полиномиального уравнения эквивалентно вычислению верхней границы значений положительных корней уравнения с последующим обращением, т.е. Положив , мы должны только выполнить для соответствующего полинома подстановку , для чего потребуется приблизительно столько же времени, что и для подстановки поэтому, пользуясь этим методом, мы экономим огромное количество машинного времени, и решается за несколько секунд. Подробный алгоритм этого метода представлен ниже.

Отметим, что для всех i мы имеем где а, — наименьший положительный корень некоторого полиномиального уравнения. Следовательно, очевидно, что в общем случае, чтобы вычислить правило Коши применяется несколько раз; например, чтобы вычислить для полинома его нужно применить 18 раз. Однако, поскольку число применений правила Коши очень мало по сравнению со значением - и не мажет быть предопределено, мы мажем безопасно считать, что в нашем обсуждении

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

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

где теперь наименьшее расстояние между любыми двумя корнями равно

Доказательство. Пусть суть корней уравнения внутри интервала (0,1), и предположим, что в то время кал Поскольку лемма доказана.

Лемма 7.3.12. Пусть — полиномиальное уравнение степени d 2 от одной неизвестной с целыми коэффициентами и без кратных корней, имеющее два комплексно-сопряженных корня внутри круга с центром и радиусом 1/2; более того, пусть Тогда инверсия примененная к уравнению отображает «1 и а? в полуплоскость с вещественной частью где теперь расстояние между ними

Локазательство аналогично предыдущему.

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

Рассмотрим бесконечное двоичное дерево, с каждой вершиной которого мы ассоциируем тройку вида где полином получен из исходного полинома подстановкой — число перемен знаков в последовательности коэффициентов полинома [Необходимо ассоциировать с каждым преобразованным полиномом соответствующую функцию так, чтобы в конце мы могли легко получить изолирующие интервалы корней; см. также Если — исходное полиномиальное уравнение с v переменами знаков в последовательности коэффициентов, то корень дерева соответствует тройке

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

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

С учетом этих определений различие между двумя методами цепных дробей для отделения вещественных корней полиномиального уравнения показано на рис. 7.3.1.

Рис. 7.3.1. Геометрическая интерпретация двух различных способов вычисления значения некоторого (длины ветви).

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

где — произвольное неотрицательное целое число, а — положительные целые элементы (где определено условием (VI) в теореме 7.3.9), преобразует уравнение в

новое уравнение, соответствующее терминальному узлу типа или Тогда для всех к, 1 к h, мы имеем

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

Метод непрерывных дробей Винсента 1836 г. экспоненциален как по (а), так и по (b), в то время как метод непрерывных дробей автора 1978 г. теоретически экспоненциален только из-за возрастания размера целых коэффициентов, т.е., пользуясь правилом Коши, автору удалось исключить экспоненциальность, обусловленную фактором (а). Однако по теореме Кузьмина (упоминаемой в разд. 2.2.4) мы не можем теоретически ограничить размер неполных частных а,- и, следовательно, не можем контролировать рост коэффициентов. Тем не менее, благодаря тому, что (для того, чтобы изолировать корни) мы вычисляем очень мало неполных частных снова пользуясь теоремой Кузьмина, мы видим, что вероятность больших неполных частных практически равна нулю, и, следовательно, наша гипотеза хорошо обоснована.

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

ACF1978.

Метод цепных дробей 1978 г. для отделения вещественных корней уравнения (Continued Fractions Method of 1978 for Isolation of the Real Roots of an Equation)

Вход: полиномиальное уравнение с целыми коэффициентами и без кратных корней.

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

1. [Инициализация] Положить если то выдать замкнутый интервал [0,0] и положить и вычислить число v перемен знаков в последовательности коэффициентов полинома — множество определенных выше троек

где Если , то мы отделяем положительные корни, а если то отделяем отрицательные; <i-flag — флаг сдвига-инверсии.]

2. или Если или то из правила знаков Кардано-Декарта (теорема 7.2.6) мы знаем, что нет положительных корней или есть ровно один положительный корень соответственно; в последнем случае — его изолирующий интервал — подается на выход. В любом из этих случаев подстановки не нужны; если то перейти к шагу 10, иначе выход.

2а. В этой точке нам известно, что требует дальнейшего исследования. Положить и перейти к шагу 4.

3. [Проверка завершения] Если то удалить первую тройку и перейти к шагу 4; если то перейти к шагу 1, иначе выход.

4. [Вычисление 6] Пользуясь правилом Коши (разд. 7.2.3) вычислить нижнюю границу 6 значений положительных корней полинома если то перейти к шагу 6.

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

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

7. Если , то выполнять перейти к шагу . В этой точке нам известно, что а это означает наличие корней уравнения в интервале (0,1); положить обеспечивая условие [в случае необходимости умножить на

8. [Изменить вычислить число перемен знаков в последовательности коэффициентов полинома Как на шаге 2, если или то

из правила знаков Кардано-Декарта мы знаем, что или нет положительных корней, или есть один положительный корень; в последнем случае вывести его изолирующий интервал, равный если если открытому интервалу с неупорядоченными концевыми точками в остальных случаях [полученному, конечно, во всех случаях по соответствующей функции Если то добавить тройку к множеству Т.

9. [Возврат к циклу] Если то перейти к шагу 7; иначе выполнять перейти к шагу

10. [Отделить отрицательные корни] Если то выполнять положить так что отрицательные корни становятся положительными; вычислить число v вариаций знаков в последовательности коэффициентов полинома и перейти к шагу иначе выход. (Если мы выходим здесь, то отрицательные корни симметричны положительным и мы уже знаем их изолирующие интервалы. Конечно, в этом случае интервалы, полученные нами для отрицательных корней, находятся в положительной полуплоскости и должны быть отображены на соответствующие интервалы в отрицательной полуплоскости — тривиальное действие.)

Анализ времени работы алгоритма ACF1978. Из разд. 3.1.2 нам известно, что для данного полинома подстановка выполняется за время

Из (V12) нам известно, что для каждого вещественного корня уравнения мы должны выполнить не более таких подстановок, где

Кроме того, из условия гипотезы 7.3.13 нам известно, что для каждого вещественного корня полинома и для каждой подстановки

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

Поскольку полином имеет не более вещественных корней, то

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

Пример. Отделим вещественные корни уравнения где Применяя алгоритм ACF1978, получаем следующие результаты:

Шаг 1. Здесь мы полагаем и вычисляем значение v, равное 2. (Мы сначала отделяем положительные корни.)

Шаг 2а. Поскольку мы полагаем им и переходим к шаху 4.

Шах 4. Чтобы использовать правило Коши, мы сначала полагаем и получаем затем мы применяем В PR к последнему уравнению и получаем Поэтому

Шаг 5. На этом шаге мы модифицируем очевидно, .

Шаг 6. Полагаем , модифицируем и переходим к шагу 8.

Шаг 8. На этом шаге мы полагаем и вычисляем равное 0.

Шаг 9. Поскольку мы переходим к шагу 7.

Шаг и мы вычисляем новые значения ). [Заметим, что мы получили, полагая

Шаг 8. На этом шаге мы устанавливаем и вычисляем значение которое оказывается равным 2. В этом случае мы полагаем

Шаг 9. Поскольку мы устанавливаем и переходим к шагу 3.

Шаг 3. и мы удаляем из него первую тройку и переходим к шагу 4.

Шаг 4. Снова мы сначала полагаем и получаем затем мы применяем BPR к последнему уравнению и получаем Поэтому и мы переходим к шагу 6.

Шаг 6. Полагаем модифицируем и переходим к шагу 8.

Шаг 8. Здесь мы устанавливаем и вычисляем значение которое оказывается равным 1. В этом случае мы выводим первый изолирующий интервал (1, 3/2), полученный из .

Шаг 9. Поскольку мы переходим к шагу 7.

Шаг мы вычисляем новые значения .

Шаг 8. Здесь мы устанавливаем и вычисляем значение которое оказывается равным 1. В этом случае мы выводим второй изолирующий интервал полученный из .

Шаг 9. Поскольку мы устанавливаем и переходим к шагу 3.

Шаг 3. поэтому мы переходим к шагу 10.

Шаг 10. Мы теперь отделяем отрицательные корни. Поскольку мы полагаем , вычисляем значение v, которое оказывается равным 1, и переходим к шагу 2.

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

Полностью процесс проиллюстрирован на рис. 7.3.2.

Рис. 7.3.2. Двоичное дерево, полученное для отделения положительных корней уравнения