Университет города Переславля

      "Алгоритмы непрерывной математики"
     осенний семестр 1998-99 учебного года
                С.В.Дужин

                Лекция 4
             Изоляция корней

Алгоритм Бухбергера позволяет свести решение любой системы
полиномиальных уравнений к решению одного уравнения с одним
неизвестным.

Для нахождения решений одного уравнения с одним неизвестным существуют
методы двух сортов: методы 

Определение.
Последовательность Штурма многочлена f -- это последовательность многочленов
f_i, которая строится так:
   f_0 = f,
   f_1 = f' (производная f по x),
   f_2 = - ост(f_0,f_1),
   f_3 = - ост(f_1,f_2),
   ...
Последним в этой последовательности считается последний ненулевой многочлен,
который получается по указанному правилу.

Определение.
Вариация в точке a -- это число перемен знака в последовательности Штурма в
этой точке, т.е. в числовой последовательности f_0(a), f_1(a), ...
(при этом нули, если они встречаются, не берутся во внимание).
Вариация в точке a обозначается V(a).

Теорема Штурма.
Если числа a и b не являются корнями многочлена f, то число вещественных
корней многочлена f на отрезке [a,b] равно V(a)-V(b).

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

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

Теорема Коши.
Если x_0 -- корень многочлена f(x) = a_0x_n + a_1x^{n-1} + ... + a_n,
то
  |x_0| < 1 + max (|a_1|/|a_0|,...,|a_n|/|a_0|).

Алгоритм Штурма изоляции корней.

Составляем последовательность Штурма.
Пусть M = 1 + max (|a_1|/|a_0|,...,|a_n|/|a_0|).
Начальный интервал (-M,M).
Считаем вариации в концах этого отрезка.
Если разность вариаций равна 0, то у многочлена нет действительных корней.
Если разность вариаций равна 1, то у многочлена один действительный корень,
и данный отрезок его содержит.
Если разность вариаций больше 1, то разобьем интервал пополам и найдем
разность вариаций на каждой из двух частей деления. Деление пополам будем
продолжать до тех пор, пока не получим интервалы, на которых разность
вариаций будет равна 1.