Ряд Штурма

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

Определение

Рассмотрим многочлен $f(x)$ с вещественными коэффициентами. Конечная упорядоченная последовательность отличных от нуля многочленов с вещественными коэффициентами

$f_0(x), f_1(x), ..., f_s(x) \quad$

называется рядом Штурма для многочлена $f(x)$, если выполнены следующие условия:

• $f_s(x) \quad$ не имеет вещественных корней;
• если $f_k(c) = 0 \quad$ и $1\leqslant k\leqslant s - 1$, то $f_{k-1}(c)f_{k+1}(c) < 0 \quad$;
• если $f(c) = 0 \quad$, то произведение $f_0(c)f_1(c) \quad$ меняет знак с минуса на плюс, когда $x$, возрастая, проходит через точку $c$, то есть когда существует такое $\delta > 0$, что $f_0(x)f_1(x) < 0 \quad$ для $x\in (c-\delta, c)$ и $f_0(x)f_1(x) > 0 \quad$ для $x\in (c, c+\delta)$.

Иногда ряд Штурма также определяют как построенный определённым образом ряд Штурма.

Связанные определения

• Значением ряда Штурма в точке $c$ называется количество смен знака в последовательности $f_0(c), f_1(c), ..., f_s(c)$ после исключения нулей.

Теорема Штурма

Пусть $f(x)$ — ненулевой многочлен с вещественными коэффициентами, $f_0(x), f_1(x), ..., f_s(x)$ — некоторый ряд Штурма для него, [a, b] — промежуток вещественной прямой, причём $f(a)f(b)\neq 0$. Тогда число различных корней многочлена $f(x)$ на промежутке $[a,b]$ равно $W(a)-W(b)$, где $W(c)$ — значение ряда Штурма в точке $c$.

Построение

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

• $f_0(x)=f(x)$;
• $f_1(x)=f_0'(x)$;
• Если $f_k(x)$ ($k>0$) имеет корни, то $f_{k+1}(x) = - f_{k-1}(x) \bmod f_k(x)$, где $f(x)\bmod g(x)$ — остаток от деления многочлена $f(x)$ на многочлен $g(x)$ в кольце многочленов $\R [x]$, иначе $s = k$.

Для произвольного многочлена, отличающегося от константы, можно положить

$f_0(x) = \frac{f(x)}{(f(x),f^'(x))}$,

и далее следовать приведенному выше способу. Здесь $(f(x),f'(x))$ — наибольший общий делитель многочленов $f(x)$ и $f^'(x)$. Если многочлен $f(x)$ есть ненулевая константа, то его ряд Штурма состоит из единственного многочлена $f_0(x)=f(x)$.

Применение

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

Пример

Построим указанным выше способом ряд Штурма для многочлена $f(x)=(x-1)(x-3)=x^2-4x+3$

Многочлен $f_i(x)$	Знак многочлена в точке
	$-\infty$	$0$	$1$	$2$	$3$	$4$	$+\infty$
$f_0(x)=x^2-4x+3$	$+ \quad$	$+ \quad$	$0 \quad$	$- \quad$	$0 \quad$	$+ \quad$	$+ \quad$
$f_1(x)=2x-4$	$- \quad$	$- \quad$	$- \quad$	$0 \quad$	$+ \quad$	$+ \quad$	$+ \quad$
$f_2(x)=1$	$+ \quad$	$+ \quad$	$+ \quad$	$+ \quad$	$+ \quad$	$+ \quad$	$+ \quad$
Значение ряда в точке	$2 \quad$	$2 \quad$	$1 \quad$	$1 \quad$	$0 \quad$	$0 \quad$	$0 \quad$

Таким образом, по теореме Штурма число корней многочлена $f(x)$ равно:

• $2-0=2$ на промежутке $(-\infty, +\infty)$
• $2-0=2$ на промежутке $(0, 4)$
• $2-1=1$ на промежутке $(0, 2)$

Литература

• Кострикин А. И. Введение в алгебру, ч. 1 «Основы алгебры», изд. 2 исправленное, — Физматлит, Москва, 2004.
• Шафаревич И. Р. О решении уравнений высших степеней (метод Штурма). — М.: Гостехиздат, 1954.

См. также

• Теорема Декарта