Отсутствие комплексных корней у многочлена

[javaProgrammer]

Знает ли кто-нибудь условие отсутствия комплексных корней у произвольного многочлена через его коэффициенты?

[lofar]

Если исходный полином $f(x)$ имеет вещественные коэффициенты, то можно воспользоваться описанным ниже методом.

Пусть $deg(f) = n$ и $\alpha_1,\ldots,\alpha_n$ --- все корни полинома $f(x)$ (возможно с повторениями). Положим $s_k = \alpha_1^k+\ldots+\alpha_n^k$, $k=0,1,2,\ldots$ Числа $s_k$ выражаются через коэффициенты $f(x)$по формулам Ньютона. Составим квадратичную форму

$$ S = \sum^{n-1}_{i,\,k=0}s_{i+k}x_ix_k. $$

Теорема.(см., например, Гантмахер "Теория матриц") Ранг формы $S$ равен числу всех различных корней полинома $f(x)$ (косплексных). Сигнатура $S$ равна числу всех различных действительных корней $f(x)$.

Таким образом, все корни $f(x)$ действительны если и только если ранг $S$ равен ее сигнатуре. То есть в точности тогда, когда отрицательный индекс инерции $S$ равен $0$.

[javaProgrammer]

с $s_k$ я чего-то недопонял.
$a_i$---корни???

[javaProgrammer]

подскажите, если не сложно, о каких формулах Ньютона идет речь. И ,вообще, почему берется именно такая квадратичная форма?

[cepesh]

Откройте Гантмахера и изучите.

[javaProgrammer]

Вы не могли бы указать главу, а то я кроме общих понятий ничего не нашел.

[незваный гость]

Тут еще примешалась небольшая путаница в обозначениях - корни $\alpha_k$ и коэффициенты $a_k$ очень похожи графически.

[lofar]

$\alpha_1,\ldots,\alpha_n$ --- корни. $s_k$ --- сумма $k$-х степеней корней. Никаких $a_i$ не было.

Пусть

$$\begin{array}{rcl} \sigma_1& = & \alpha_1+\ldots+\alpha_n\\ \sigma_2 & = & \alpha_1\alpha_2 + \alpha_1\alpha_3 +\ldots+\alpha_{n-1}\alpha_n\\ \multicolumn{3}{r}{\dotfill}\\ \sigma_n & = &\alpha_1\alpha_2\ldots\alpha_n\\ \end{array}$$

То есть $\sigma_1,\ldots,\sigma_n$ --- элементарные симметрические полиномы от корней $f(x)$.

Формулы Ньютона связывают $s_k$ и $\sigma_i$, например $s_1=\sigma_1$, $s_2 = \sigma_1^2- 2\sigma_2$. Найти их можно в любом учебнике по алгебре.

План таков:
1) По коэффициентам $f(x)$ находим $\sigma_i$ (формулы Виета).
2) По $\sigma_i$ находим $s_k$ (формулы Ньютона).
3) По $s_k$ строим квадратичную форму $S$.
4) Находим отрицательный индекс инерции $S$.
5) Делаем соответствующие выводы.

[незваный гость]

Один из вариантов решения Вашей задачи - воспользоваться методами отделения корней полинома. Рискуя заработать замечание за повтор, порекомендую здесь:

Цитата:

У Полиа и Сегье (т. 1, отдел 3, глава 1, §2; т. 2, отдел 5 глава 1) Вы найдете некоторые критерии, которые часто применяются. В Березин, Жидков Методы вычислений (том 2, гл. 7) приводятся как методы локализации корней, так и методы численного решения уравнений.

Если я правильно помню, эти методы работают через число перемен знака в цепочке производных. Таким образом, Вам надо подсчититать значения полиномов в двух точках, что, несомненно, гораздо проще построения квадратичных форм.

[lofar]

Для отделения корней полиномов обычно используют методы Декарта, Бюдана-Фурье, Штурма и некоторые их модификации.

Я не привел эти методы в качестве решения ввиду наличия следующих "узких" мест.

1) Первые 2 метода дают лишь оценку числа действительных корней.

2) Метод Штурма считает число корней на некотором отрезке $[a,b]$. Поэтому сначала нужно определить границы расположения корней (для этого методы конечно есть).

3) Метод Штурма находит число вещественных корней на отрезке, но без учета кратностей.


Вместе с тем, я вполне допускаю, что существует, какой-то простой неизвестный мне метод нахождения числа вещественных корней. Буду рад ознакомиться с ним.

[незваный гость]

lofar писал(а):

1) Первые 2 метода дают лишь оценку числа действительных корней.

2) Метод Штурма считает число корней на некотором отрезке $[a,b]$. Поэтому сначала нужно определить границы расположения корней (для этого методы конечно есть).

3) Метод Штурма находит число вещественных корней на отрезке, но без учета кратностей.

Я, в целом, согласен с Вами, однако --

Взяв достаточно большой отрезок $[a, b]$, мы получаем количество вещественных корней на прямой. (Правда, Вы правы - при отсутствии кратных корней.) Но если оно равно степени полинома - то все корни вещественные, что нам и требовалось. Если же нет - есть комплексные, что нам опять-таки и требовалось узнать.

С кратными корнями тяжелее. Их наличие, однако, сравнительно легко проверить посчитав $g = {\rm GCD}(p, p')$. Если он не равен 1, считаем количество корней $p/g$ и $g$ (причем первый уже не имеет кратных корней).

Простите, я не помню первые два названных Вами метода. Что Вы имеете ввиду под словом оценка? (Что количество корней небольше, чем ... ?)

[lofar]

Возможен следующий подход.

1) Заменяем $f$ на $g =f/{\rm GCD}(f,f')$. У $f$ все корни действительные тогда и только тогда, когда таковы все корни $g$. При этом у $g$ нет кратных корней.
2) Определяем отрезок $[a,b]$ на котром заведомо находятся все корни $g$ (для $a$ и $b$ имеются оценки через коэффициенты $g$).
3) Методом Штурма находим число вещественных корней $g$ на $[a,b]$. Если это число совпадает со степенью $g$ значит все корни $f$ вещественные.

Просто, мне показалось, что приведение квадратичной формы к диагональному виду запрограммировать проще (формулы Ньютона считаются простым циклом).


Методы Бюдана-Фурье и Декарта сводятся к подсчету перемен знаков и в результате выдают некоторое целое число $M$. Далее, как правило, доказываются два факта. Во-первых, число $N$ вещественных корней $f$ (считая с кратностями) не превосходит $M$. Во-вторых, разность $M-N$ --- четное число.

[незваный гость]

Спасибо за пояснения. Отдельное спасибо за упрощение моего предложения.

Я полпробую сравнить на досуге, какой из методов проще. Но вот быстро - не обещаю.

[Mandel]

Недавно у меня возник такой же вопрос по отделению корней. А можно ли получить некоторый алгоритм нахождений $S_k$, при которых все корни вещественны и известны $S_k$, например, с четными номерами?

Добавлено спустя 2 часа 5 минут 21 секунду:

Я так понял по Вашему методу надо будет еще:
1. Привести форму к диагональному виду.
2. Найти отрицательный индекс инерции.

А как 2 пункт делать?