Ряд Штурма

Ряд Штурма (система Штурма) для речовинного багаточлена - послідовність многочленів, що дозволяє ефективно визначати кількість коренів многочлена на проміжку і наближено обчислювати їх за допомогою теореми Штурма. Ряд та теорема названі ім'ям французького математика Жака Штурма.


1. Визначення

Розглянемо многочлен 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) .

Іноді ряд Штурма також визначають як побудований певним чином ряд Штурма.


1.1. Пов'язані визначення

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

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

Нехай 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 .


3. Побудова

Ряд Штурма існує для будь-якого ненульового речового многочлена.
Нехай багаточлен 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) .


4. Застосування

Ряд Штурма використовується для визначення кількості речових коренів многочлена на проміжку (див. теорему Штурма). Звідси випливає можливість його використання для наближеного обчислення речових коренів методом двійкового пошуку.

4.1. Приклад

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

Многочлен f_i (x) Знак многочлена в точці
- \ Infty01234+ \ Infty
f_0 (x) = x ^ 2-4x +3+ \ Quad+ \ Quad0 \ quad- \ Quad0 \ quad+ \ Quad+ \ Quad
f_1 (x) = 2x-4- \ Quad- \ Quad- \ Quad0 \ quad+ \ Quad+ \ Quad+ \ Quad
f_2 (x) = 1+ \ Quad+ \ Quad+ \ Quad+ \ Quad+ \ Quad+ \ Quad+ \ Quad
Значення ряду в точці 2 \ quad2 \ quad1 \ quad1 \ quad0 \ quad0 \ quad0 \ quad

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

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

Література