Метод Штурма

Ме́тод Шту́рма використовується для виокремлення дійсних коренів многочленів, тобто знаходження інтервалів, які містять рівно по одному кореню. Надалі отриману інформацію про розміщення коренів можна використати для їх знаходження чисельними методами.

Метод, ряд і теорема названі на честь французького математика Жака Шарля Франсуа Штурма.

Основні визначення

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

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

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

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

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

Побудова ряду Штурма для многочлена

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

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

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

Джерела

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