7.2.2. Теорема Штурма и метод бисекций Штурма отделения вещественных корней

Напомним читателю, что двумя основными темами исследований Фурье в течение всей его жизни были теория теплоты и теория численного решения уравнений. Обе эти темы были развиты Штурмом, который имел личные и научные связи с Фурье. В 1829 г. рукопись Фурье о численном решении уравнений была представлена нескольким специалистам, среди которых был и Штурм, явно указывавший на большое влияние, оказанное на него этой работой.

Заслуга Штурма состоит в том, что он заменил последовательность Фурье последовательностью

которая называется последовательностью Штурма или цепью. (Это — классическая последовательность Штурма; см. определение 7.2.7 для обобщения определения последовательности Штурма.) Эта новая последовательность получается применением алгоритма Евклида к полиномам если взять в качестве к полиномы, противоположные к полиномиальным остаткам, т.е. она определяется следующими соотношениями:

Преимущество последовательности Штурма состоит в том, что мы можем теперь получить тонное число вещественных корней уравнения на данном интервале. Заметим, что если — степень полинома то обычно получается дополнительных функций потому что при вычислении наибольшего общего делителя полиномов степень каждого остатка обычно на единицу меньше степени предыдущего остатка. Кроме того, если нет кратных корней, то константа. [В гл. 5 мы подробно рассмотрим различные способы построения последовательности (S) над целыми

Пример. Последовательность Штурма, соответствующая полиному — это

Мы имеем следующее

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

со следующими свойствами в интервале (т.е. когда возрастает от до ):

i. В достаточно малой окрестности вещественного корня а полинома знаки полиномов различны, если и одинаковы, если .

ii. Два последовательных члена последовательности Штурма не могут одновременно обращаться в нуль.

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

iv. Последняя функция не обращается в нуль, а следовательно, не меняет знак.

После теоремы 7.2.9 мы представим способ построения бесконечного числа наборов функций [отличных от последовательности,

задаваемой соотношениями которые удовлетворяют условиям определения 7.2.7; кроме того, как мы убедимся при доказательстве теоремы 7.2.8, последовательность определяемая соотношениями также удовлетворяет этим условиям.

Хотя теоремы 7.2.8 и 7.2.9 верны для любой они будут сформулированы и доказаны только для «классической» последовательности Штурма

Точное число вещественных корней уравнения в открытом интервале.

Теорема 7.2.8 (Штурм, 1829 г.). Рассмотрим полиномиальное уравнение с целыми коэффициентами, имеющее только простые корни. Тогда число его вещественных корней в интервале рарно разности , где обозначает число перемен знаков в последовательности Штурма для

Локазательство. Локазательство основано на условиях определения 7.2.7, которые характеризуют функции последовательности Штурма определенной соотношениями

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

b. Два соседних элемента последовательности Штурма не могут одновременно обращаться в нуль. Чтобы в этом убедиться, предположим противное, т.е. пусть — оба нули для некоторого значения . Тогда из видно, что для того же самого значения мы также имеем Это, однако, противоречит тому, что — ненулевая константа. [Очевидно, что тот же самый результат имеет место также для

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

откуда следует, что

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

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

[Отметим, что - не обязан быть простым корнем уравнения

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

Пример. Рассмотрим полиномиальное уравнение последовательность Штурма которого равна Тогда, пользуясь теоремой 7.2.8, мы можем с уверенностью утверждать, что есть два вещественных корня в интервале (0,2), поскольку, вычисляя значения последовательности Штурма при мы получаем с двумя переменами знаков, а вычисляя ее при мы получаем без перемен знаков, и

Сам Штурм утверждал, что теорема 7.2.8 была просто побочным продуктом его интенсивных исследований в области линейных разностных уравнений второго порядка. Требование, чтобы уравнение имело только простые корни, не является ограничением общности, поскольку мы можем сначала выполнить разложение на свободные от квадратов множители (см. разд. 3.2.4), а затем воспользоваться теоремой Штурма. Более того, всякий раз, когда последовательность Штурма имеет элементов, где мы можем легко определять число пар комплексных корней уравнения следующим образом.

Теорема 7.2.9 (Sturm 1835). Рассмотрим полиномиальное уравнение степени с целыми коэффициентами без кратных корней. Тогда имеет столько же пар комплексных корней, сколько имеется перемен знаков в последовательности первых членов функций последовательности Штурма

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

Пусть i — число перемен знаков в Эти перемены получены из знаков коэффициентов при самых высоких степенях дополнительных функциях где первые члены полиномов предполагаются положительными.

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

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

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

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

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

или

Если коэффициент при в полиноме ненулевой, то мы можем продолжать этот процесс и получить функцию такую, что

Однако, если то мы заменяем трехчленом и получаем соотношение

Если не содержит кратных корней, то в конце мы получаем функцию которая является числовой константой. Читателю следует проверить, что эта новая последовательность удовлетворяет условиям определения 7.2.7 и, следовательно, является последовательностью Штурма.

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

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

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

Определение 7.2.10. Пусть — полином с целыми коэффициентами от одной переменной, более того, предположим, что имеет , различных корней Если , то определим сепаратор полинома формулой

Если

Как мы увидим в разд. 7.2.4, при нижняя граница сепаратора дается формулой

STURM. Метод бисекций Штурма отделения вещественных корней уравнения (Sturm’s Bisection Method for Isolation of the Real Roots of an Equation)

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

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

1. [Инициализация] Положить если то вернуть замкнутый интервал [0,0] и положить Вычислить последовательность Штурма по формуле соответствующую полиному и положить . (Когда мы отделяем положительные корни, а когда отделяем отрицательные.)

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

3. [Обновление интервала] Положить .

4. [Основной цикл] Пользуясь теоремой 7.2.8, вычислить число положительных корней в интервале . Если имеется только один корень, то — его изолирующий интервал, он подается на выход. Если интервал содержит более одного корня, то он делится на два подынтервала равной длины, которые добавляются к списку если то замкнутый интервал подается на выход.

5. [Конец?] Если , то удалить из этого списка первый интервал и перейти к шагу 3; если , то выход.

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

соответствующие интервалы в отрицательной полуплоскости, а это тривиально.)

Анализ времени работы алгоритма STVRM. Из описания алгоритма становится очевидно, что метод Штурма — это по существу метод бисекций. Наша реализация метода, когда мы вычисляем раздельно границы для положительных и отрицательных корней и изолируем их отдельно, является очень эффективной, потому что мы минимизируем число бисекций, которые должны быть выполнены. Более того, если то нам ничего не нужно делать, чтобы изолировать отрицательные корни, поскольку они симметричны положительным.

На шаге 1 мы вычисляем последовательность Штурма а в гл. 5 мы видели, что это выполняется за время

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

Вычислим теперь время, необходимое для выполнения шага 4. Заметим, что, пользуясь теоремой Штурма, мы фактически не должны вычислять значение каждого элемента последовательности Штурма в данной рациональной точке, поскольку нам нужен только знак значения полинома в этой точке. Отсюда легко следует, что если — ненулевое рациональное число, то знак числа совпадает со знаком (см. также численный пример ниже). Поэтому мы можем определить знак полинома в рациональной точке, пользуясь только целочисленной арифметикой. Из разд. 3.1.2 легко вывести, что время, необходимое для этого вычисления, равно

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

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

что также ограничивает число делений пополам. Поэтому

и, подставляя последнее выражение в видим что в худшем случае каждое полиномиальное значение вычисляется за время

При условии, что мы имеем делений пополам каждого из не более, чем , интервалов, содержащих корни, и что мы имеем не более, чем полиномов в последовательности Штурма, мы видим, что

(См. также историческое замечание 3.)

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

Отделение положительных корней. Пользуясь алгоритмом BPR разд. 7.2.3, получаем 64 как верхнюю границу положительных корней полинома (см. также соответствующий пример в разд. 7.2.3), т.е. они все находятся в интервале (0,4), где Пользуясь теоремой Штурма, находим, что в интервале (0,4) есть два корня; а именно, в мы получаем с двумя переменами знаков, а в мы получаем без перемен знаков. Разделив пополам интервал (0,4), видим, что и что не имеет перемен знаков; поэтому оба корня находятся в (0,2) и интервал (2,4) исключается из рассмотрения. Разделив пополам теперь интервал (0,2), видим, что и что также имеет две перемены знаков. Поэтому оба корня находятся в (1,2) и интервал (0,1) игнорируется. Затем делим пополам интервал (1,2) и видим,

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

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

Из приведенного примера становится очевидным, что мы должны сосредоточиться на том, как (1) вычислять верхнюю границу b значений положительных корней и (2) определять число делений пополам, необходимых, чтобы отделить корни. Как мы видели при обсуждении времени вычислений метода Штурма, второй вопрос связан с тем, насколько близко расположены корни, и имеет чрезвычайно важное значение как для гарантии того, что процесс завершается после конечного числа шагов, так и при вычислении его теоретических временных оценок. Обе темы рассматриваются ниже.

В разд. 7.2.3 мы представляем правило Коши, очень эффективное средство для вычисления верхней границы b значений положительных корней уравнения, а затем, в разд. 7.2.4, мы доказываем соотношение результат, принадлежащий Малеру (Mahler, 1964), который дает нам нижнюю границу сепаратора корней; см. также (Rump, 1979).