Границы корней многочлена

Ну, я так и делал. Искал производные, пока не получится линейное уравнение. Найти его корень - тривиально. Потом по рекурсии возвращался, методом Ньютона ища корни в интервалах. В качестве значений +/- бесконечность брал что-то типа MaxInt. Хотелось бы что-то точнее.
2 albom: так и не понял, как в твоей программе определяется правая и левая границы корней

Значит, там у нас есть функция f(x), дальше находим все x при которых f`(x)=0.
Теперь рассмотрим xmin, если f(xmin)>0 и f(xmin-1)<f(xmin), то на промежутке от -oo до xmin есть ровно один корень.
Зная что он там есть, можно легко его найти. Например, сначала сделав это:

Так откуда взять этот xmin? Просвяти, пожалуйста. Как корни искать - это понятно.

Решаем уравнение f`(x)=0. Получим n корней: x1, x2, x3, x4 ... xn (x1<x2<x3<x4<...<xn).
Вот xmin=x1; ну а xmax=xn.

Сообщение отредактировано: albom - 14.11.03, 09:43

ОК. Пусть f(x) = X^2 - 5*X + 6 (корни 2 и 3)
f'(x) = 2*X - 5
X = 2.5
И какой тут xmin или xmax?

Сообщение отредактировано: tserega - 14.11.03, 09:44

xmin=xmax=2.5
Итого, есть два промежутка [-oo; 2.5] и [2.5; +oo]. И заметь, на каждом из промежутков находится не более одного корня!

Похоже, мы обсуждаем разные темы. Надо найти приближение этих значений плюс/минус бесконечность. That's the problem! Точки экстремума понятно, как искать.

Зачем метод Ньютона запускать из +/- бесконечности?
Я же говорю, на полуинтервалах (-oo, min(Xmin второй производной, Xmin первой производной)] и [max(Xmax второй производной, Xmax первой производной), +oo) многочлен всегда только выпукл или только вогнут. Так и запускаем его из min(Xmin1, Xmin2)-1, затем из max(Xmax1, Xmax2)+1... И получаем перемену знака Y(xi) на (или даже ДО) первой же итерации, если там корень вообще есть...

Сообщение отредактировано: Visitor - 14.11.03, 10:20

2 Visitor: как я понял, Xmin1 - это минимальный корень первой производной, а Xmin2 - второй производной?

Да, правильно понял

с другой стороны если там уравнение 10й степени, наверное не будет большой разницы, решать уравнение 10й степени или 8й.

Сложность хде-то N^2 поисков корней, хде N -- степень уравнения...

А сложность поиска от степени не зависит, зависит от точности епсилон и организации процедуры поиска.

Сообщение отредактировано: Visitor - 14.11.03, 14:26

Могут разве что возникнуть проблемы с переполнением (коэффицент перед степенью увеличивается как n!)

В процессе вычисления производной сразу нормировать коеффициенты Чтобы an при x^n = 1

Сообщение отредактировано: Visitor - 14.11.03, 15:21

Я чего хотел спросить...

У вас до какой степени многочлена корни правильно искались? Без "удвоения" одного корня из-за погрешностей при вычислении, потери точности в корнях, где многочлен касается или почти параллелен Ox и без пропусков парных корней, где f(xi) = f'(xi) = 0?

У меня, помнится, не особо высокие степени в разряд "надежно" обрабатываемых попали...