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

теорема Штурма позволяет вычислить количество действительных корней в диапазоне (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) и 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.

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

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

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

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

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

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

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

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

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