Метод Штурма

Послідовність неперервних функцій ${\displaystyle f_{0},f_{1},\ldots ,f_{n}}$ називається рядом Штурма на відрізку ${\displaystyle [a,b]}$, якщо виконуються такі умови:

1. ${\displaystyle f_{n}}$ не має коренів на ${\displaystyle [a,b]}$
2. Якщо при деяких ${\displaystyle c\in [a,b],0<i<n}$ виконується рівність ${\displaystyle f_{i}(c)=0}$, то ${\displaystyle f_{i-1}(c)f_{i+1}(c)<0}$
3. Якщо ${\displaystyle f_{0}(c)=0}$ при деякому ${\displaystyle c\in (a,b)}$, то при переході через ${\displaystyle c}$ функція ${\displaystyle f_{0}(x)f_{1}(x)}$ змінює знак з "−" на "+".

Якщо в точці ${\displaystyle \alpha }$ всі ${\displaystyle f_{i}(\alpha ),\,i=0,\ldots ,n}$ не рівні нулю, то можна визначити кількість знакозмін ${\displaystyle \omega (\alpha )}$ як кількість індексів ${\displaystyle 0\leq i<n}$, таких що ${\displaystyle f_{i}(\alpha )f_{i+1}(\alpha )<0}$

Нехай на відрізку ${\displaystyle [a,b]}$ задано ряд Штурма ${\displaystyle \left\{f_{i}\right\}_{i=0}^{n}}$, причому ${\displaystyle f_{i}(a)\neq 0,f_{i}(b)\neq 0}$ при всіх ${\displaystyle i=0,\ldots ,n}$. Тоді на ${\displaystyle [a,b]}$ існує рівно ${\displaystyle \omega (a)-\omega (b)}$ коренів рівняння ${\displaystyle f_{0}(x)=0}$

Нехай многочлен ${\displaystyle P(x)}$ не має кратних коренів. Тоді для нього можна побудувати ряд Штурма за таким алгоритмом:

1. ${\displaystyle f_{0}(x)=P(x)}$
2. ${\displaystyle f_{1}(x)=P'(x)}$
3. ${\displaystyle f_{k-1}=f_{k}(x)g_{k}(x)-f_{k+1}(x),\quad degf_{k+1}<degf_{k}}$, тобто ${\displaystyle f_{k+1}}$ — це взята з протилежним знаком остача від ділення ${\displaystyle f_{k-1}}$ на ${\displaystyle f_{k}}$.

Останній крок повторюється до отримання нульового многочлена. Ряд Штурма утворюють всі ненульові многочлени ${\displaystyle f_{k}}$. Описаний процес дуже нагадує алгоритм Евкліда знаходження найбільшого спільного дільника многочленів, а останній в ряді многочлен з точністю до числового множника збігається з найбільшим спільним дільником ${\displaystyle P(x)}$ та ${\displaystyle P'(x)}$. Оскільки ${\displaystyle P(x)}$ не має кратних коренів, то ${\displaystyle P(x)}$ і ${\displaystyle P'(x)}$ є взаємно-простими, а тому ${\displaystyle f_{n}(x)\equiv const\neq 0}$

• Шафаревич И. Р. О решении уравнений высших степеней (метод Штурма). — М.: Гостехиздат, 1954. (рос.)