эффективно определить, есть ли у многочлена корень в интервале [0, T]

Question

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

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

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

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

Answer 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 ≤ i ≤ k, fi (x) имеет степень ниже, чем у fi − 1 (x).Знаки остатков отрицаются со знаками в алгоритме Евклида.

Обратите внимание, что последний неисчезающий остаток fk (или fk − 1, когда fk = 0) является наибольшим общим делителем 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.

Answer 2

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

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

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

Answer 3

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

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

Answer 4

Используйте Правило Декарта знаков , чтобы получить некоторую информацию. Просто посчитайте количество изменений знака в коэффициентах. Это дает вам верхнюю границу количества положительных реальных корней. Рассмотрим полином 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.

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

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

Answer 5

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

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