Метод Штурма

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Основні визначення[ред.ред. код]

Послідовність неперервних функцій 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