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

В этом разделе мы сформулируем и докажем правило Коши вычисления верхней границы значений положительных корней полиномиального уравнения с целыми коэффициентами. Затем следует обсуждение того, как это правило лучше всего реализовать. Вычисляемая граница является рациональным числом, знаменатель которого — степень 2 (см. историческое замечание

Теорема 7.2.11 (правило Коши). Пусть — нормированное полиномиальное уравнение степени целыми коэффициентами, где по крайней мере для одного , и пусть — число его отрицательных коэффициентов. Тогда

является верхней границей значений положительных корней уравнения

Локазательство. Из определения b мы заключаем, что

для каждого к, такого, что для этих к последнее неравенство можно переписать в виде

Суммируя по всем соответствующим k, получаем или

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

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

а затем мы полагаем где — максимум из всех k. [Заметим, что мы рассматриваем общий случай, когда — не обязательно нормированный полином и см. (Akritas, 1981b).] Вычисление каждого к осуществляется следующим образом. Пусть

— частное для некоторого , и предположим, что

Тогда, очевидно,

Если положить , то это неравенство примет вид

Извлечение корня степени из последнего выражения дает

Если очевидно,

Более того,

поскольку и Объединяя получаем . Фактически мы можем получить меньшее значение для к, если . В этом случае и

так что

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

1. Вычисление наибольшего целого для любого целого

2. Вычисление для неотрицательного целого числа

3. Вычисление для любых целых i и к, положительных или отрицательных, где по определению

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

BPR. Верхняя граница значений положительных корней полиномиального уравнения (Upper Bound on Values of Positive Roots of a Polynomial Equation)

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

Выход: Рациональное число 6, знаменатель которого — степень 2 (b — наименьшая степень 2, такая, что b для 1 к Если нет отрицательных коэффициентов, то

1. [Инициализация] Если положить положить А равным числу отрицательных коэффициентов полинома Если или то перейти к шагу 3; иначе

2. [Обработка отрицательных членов] Для каждого члена выполнять следующее: к если то выполнять если то выполнять если то к если или то

3. [Выход] Вернуть рациональное число b

Анализ времени работы алгоритма BPR. Принимал во внимание упражнение по программированию к этому разделу, мы видим следующее:

Шаг 1 выполняется за время

Одно выполнение шага 2, на котором вычисляется к, такое, что выполняется за время Поскольку шаг 2 выполняется самое большее раз, мы легко заключаем (суммируя по что его время работы есть выполняется за время Поскольку — целое число с одинарной точностью, мы видим, что время выполнения шага 2 доминирует над временем выполнения всего алгоритма, и, следовательно,

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

Для положительных корней мы используем полином как он есть. Применяя алгоритм BPR, мы получаем на первом шаге Второй шаг выполняется только один раз, и мы имеем а поскольку мы модифицируем к в заключение мы полагаем и из третьего шага получаем

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

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