Кратко — набор надежных тестов и алгоритмов, которыми пользуются, когда нельзя явных корней:
1) Проверка кратных корней (символьный тест)
- Вычислите $G=\gcd (P,P^{\prime })$. Если $G\ne 1$, то все корни $G$ — кратные корни $P$.
- Для отдельного корня $r$ кратность равна минимальному $m$ such что $P^{(m)}(r)\ne 0$: множество производных. Формула: если $P=(x-r{)}^{m}Q$ и $Q(r)\ne 0$, то $P^{(k)}(r)=0$ для $k<m$ и $P^{(m)}(r)\ne 0$.
- Для получения всех кратностей используйте квадратно-свободное разложение (square‑free factorization) через последовательные gcd: стандартный алгоритм над $\mathbb{Q}[x]$ или полями конечных характеристик.
2) Подсчёт и локализация действительных корней (без явного нахождения)
- Последовательность Штурма: $S_0=P,S_1=P^{\prime }$, далее $S_{k+1}=-\mathrm{rem}(S_{k-1},S_k)$ до нуля. Число разных действительных корней в интервале $(a,b]$ равно $V(a)-V(b)$, где $V(x)$ — число смен знаков в последовательности $S_i(x)$. Этот метод даёт точное число разных корней (учитывает кратности как единичные).
- Budan–Fourier и правило Декарта: правило Декарта даёт верхнюю оценку на число положительных корней (снижается чётным числом): число положительных корней $\le$ число смен знаков в последовательности коэффициентов $P$. Для отрицательных корней примените $P(-x)$. Budan–Fourier даёт оценки числа корней в любом интервале по числу смен знаков в последовательности $P^{(k)}(a)$.
3) Определение знака многочлена на интервалах и поведение в окрестности корня
- Если корень имеет нечётную кратность — знак меняется при прохождении через корень; чётная кратность — знак не меняется. Это следует из разложения $(x-r{)}^m$.
- После изоляции интервала с ровно одним корнем (например, с помощью Штурма и бисекции) знак в левой/правой части находим подстановкой любого тест‑пункта в интервал.
4) Практическая стратегия для «высокой степени»
- Сначала символьный gcd для выявления кратных корней и квадратно‑свободное разложение.
- Затем примените последовательность Штурма, чтобы разделить ось на интервалы, каждый с заданным числом корней (изолировать по одному).
- В каждом интервале: оцените знак в точке, определите изменение знака через правило кратности; при необходимости численно уточните корень (бисекция/метод Ньютона с контролем сходимости).
- Для оценок числа положительных/отрицательных корней используйте Декарта / Budan–Fourier для быстрых границ.
5) Замечания по численной устойчивости и инструментам
- Алгоритмы требуют точной арифметики (рациональные коэффициенты — использовать вычисления над $\mathbb{Q}$ или многоточечную арифметику; для вещественных коэффициентов — интервал‑арифметика).
- Для численного приближения корней можно использовать метод собственного числа компаньонной матрицы, но он даёт приближённо корни (не всегда надёжно для кратных корней). Для верификации кратностей комбинируйте численные приближения с символьным gcd или проверками малых производных.
Резюме: символьный $\gcd (P,P^{\prime })$ и квадратно‑свободное разложение для кратностей; последовательность Штурма (или Budan–Fourier + Декарт) для точного подсчёта и изоляции действительных корней; знак на интервалах определяется взятием тест‑точки и правилом чётности кратности.