Введение

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

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

Применение

Обобщенные последовательности Штурма позволяют подсчитать количество корней многочлена, при которых другой многочлен положителен (или отрицателен), не вычисляя эти корни явно. Если известен изолирующий интервал для корня первого многочлена, это также позволяет определить знак второго многочлена в этом корне первого многочлена, не вычисляя более точное приближение корня. Пусть P(x) и Q(x) – два многочлена с вещественными коэффициентами, такие, что P и Q не имеют общих корней, а P не имеет кратных корней. Иными словами, P и Q являются взаимно простыми многочленами. Это ограничение не существенно ограничивает общность дальнейшего изложения, поскольку вычисление НОД позволяет свести общий случай к этому, а вычислительная сложность построения последовательности Штурма сопоставима со сложностью вычисления НОД. Пусть W(a) обозначает число изменений знака в точке a обобщенной последовательности Штурма, начинающейся с P и Q. Если a < b – два вещественных числа, то W(a) – W(b) равно количеству корней P в интервале (a, b), при которых Q(a) > 0, минус количеству корней в том же интервале, при которых Q(a) < 0. В сочетании с общим количеством корней P в этом интервале, определяемым теоремой Штурма, это позволяет вычислить количество корней P, при которых Q(a) > 0, и количество корней P, при которых Q(a) < 0.