Ряд Штурма

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Определение[править | править исходный текст]

Рассмотрим многочлен 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)

См. также[править | править исходный текст]

Литература[править | править исходный текст]