Эффективно определяя, имеет ли полином корень в интервале [0, T]

У меня есть полиномы нетривиальной степени (4+), и вам необходимо надежно и эффективно определить, имеют ли они корень в интервале [0, T]. Точное местоположение или количество корней меня не интересуют, мне просто нужно знать, есть ли хотя бы один.

Сейчас я использую интервальную арифметику как быструю проверку, чтобы проверить, могу ли я доказать, что корни не существуют. Если я не могу, я использую Jenkins-Traub для решения всех полиномиальных корней. Это явно неэффективно, поскольку он проверяет все реальные корни и находит их точные позиции, информацию, которую я не нуждаюсь.

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

Например, одна оптимизация, которую я мог бы сделать, это проверить, имеет ли мой многочлен f (t) один и тот же знак при 0 и T. Если нет, в интервале, очевидно, есть корень. Если это так, я могу решить для корней f '(t) и оценить f на всех корнях f' в интервале [0, T]. f (t) не имеет корня в этом интервале тогда и только тогда, когда все эти оценки имеют тот же знак, что и f (0) и f (T). Это уменьшает степень полинома I, чтобы корень найти на единицу. Не огромная оптимизация, но, возможно, лучше, чем ничего.

Ответ 1

Теорема Штурма позволяет рассчитать число реальных корней в диапазоне (a, b). Учитывая количество корней, вы знаете, есть ли хотя бы один. Из нижней части страницы 4 этой статьи:

Пусть f (x) - вещественный многочлен. Обозначим его через f0 (x) и его производную f '(x) через f1 (x). Действуйте так же, как в алгоритме Евклида, чтобы найти

f0(x) = q1(x) · f1(x) − f2(x),
f1(x) = q2(x) · f2(x) − f3(x),
.
.
.
fk−2(x) = qk−1(x) · fk−1(x) − fk,

где fk - константа, а для 1 ≤ я ≤ k, fi (x) имеет степень ниже, чем для fi-1 (x). Знаки остатков отменяются по сравнению с алгоритмами Евклида.

Заметим, что последний неисчезающий остаток fk (или fk-1 при fk = 0) является наибольшим общим дивизор f (x) и f '(x). Последовательность f0, f1,.,., fk (или fk-1 при fk = 0) называется последовательностью Штурма для многочлена f.

Теорема 1 (теорема Штурма) Число различных вещественных нулей многочлена f (x) с вещественные коэффициенты в (a, b) равны избытку числа изменений знака в последовательности f0 (a),..., fk-1 (a), fk по числу изменений знака в последовательности f0 (b),..., fk-1 (b), fk.

Ответ 2

Конечно, вы можете выполнять двоичный поиск в своей арифметике интервалов. Начните с [0, T] и замените его на ваш многочлен. Если интервал результата не содержит 0, все готово. Если это так, разделите интервал в 2 и повторите каждую половину. Эта схема найдет приблизительное местоположение каждого корня довольно быстро.

Если вы в конечном итоге получаете 4 отдельных интервала с корнем, вы знаете, что все готово. В противном случае, я думаю, вам нужно получить интервалы [x, y], где f '([x, y]) не содержит нуля, что означает, что функция монотонно возрастает или убывает и, следовательно, содержит не более одного нуля. Двойные корни могут представлять проблему, мне придется больше об этом думать.

Изменить: если вы подозреваете множественный корень, найдите корни f ', используя ту же процедуру.

Ответ 3

Используйте правило Декарта знаков, чтобы получить некоторую информацию. Просто подсчитайте количество изменений знака в коэффициентах. Это дает верхнюю оценку числа положительных вещественных корней. Рассмотрим многочлен P.

P = 131,1 - 73,1 * x + 52,425 * x ^ 2 - 62,875 * x ^ 3 - 69,225 * x ^ 4 + 11,225 * x ^ 5 + 9,45 * x ^ 6 + x ^ 7

Фактически, я создал P, чтобы иметь простой список корней. Они...

{-6, -4.75, -2, 1, 2.3, -i, +i}

Можно ли определить, существует ли корень в интервале [0,3]? Обратите внимание, что в конечных точках P не изменяется знак.

P(0) = 131.1
P(3) = 4882.5

Сколько знаковых изменений есть в коэффициентах P? Есть 4 изменения знака, поэтому может быть до 4 положительных корней.

Но теперь подставим x + 3 для x в P. Таким образом,

Q(x) = P(x+3) = ...
  4882.5 + 14494.75*x + 15363.9*x^2 + 8054.675*x^3 + 2319.9*x^4 + 370.325*x^5 + 30.45*x^6 + x^7

Посмотрите, что Q (x) не имеет знаковых изменений в коэффициентах. Все коэффициенты являются положительными. Поэтому корней не может быть больше 3.

Поэтому в интервале [0,3] МОЖЕТ быть либо 2, либо 4 корня.

По крайней мере, это говорит вам, стоит ли вообще смотреть на все. Конечно, если функция имеет противоположные знаки на каждом конце интервала, мы знаем, что в этом интервале имеется нечетное число корней.

Ответ 4

Это не так эффективно, но вполне надежно. Вы можете построить многочлен Companion Matrix (разреженная матрица, собственные значения которой являются корнями полиномов).

Существуют эффективные алгоритмы собственных значений, которые могут находить собственные значения в данном интервале. Одна из них - это обратная итерация (можно найти собственные значения, близкие к некоторому входному значению. Просто укажите среднюю точку интервала как приведенное выше значение).

Ответ 5

Если значение f(0)*f(t)<=0, то вам гарантированно будет root. В противном случае вы можете начать разделение домена на две части (деление пополам) и проверить значения в конце, пока не убедитесь, что в этом сегменте нет корня.

if f(0)*f(t)>0 у вас либо нет, ни два, четыре, ни корни. Ваш предел - это полиномиальный порядок. если f(0)*f(t)<0 у вас могут быть один, три, пять,.. корни.