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

Дан многочлен степени n: An*X^n + ... + A1*X + A0 = 0
Требуется определить границы его корней. Т.е. найти такие 2 числа K и L, что ВСЕ корни больше K, и все корни меньше L. (для любого i: K < Xi < L)
Желательно, чтобы эти числа как можно лучше ограничивали интервал.

пусть корень равен 2+3i
ну и в каких границах он лежит

Я имел в виду действительные корни.
Упс, забыл в первом посте написать.

2 tserega
ключевые слова: "правило знаков Декарта", "метод Бюдана-Фурье", "метод Штурма".
2 esperanto
2+3i лежит внутри круга |z|< 10, а также внутри прямоугольника |Re(z)|<2.18 |Im(z)|<100.

2turl
что ВСЕ корни больше K, и все корни меньше L

Вот тут моя программка есть, может поможет....
Короче пользоваться так:
Если нужно решить уравнение 4x^4+x^2-3x-2=0, то нужно соответственно ввести в прогу такие данные:

2turl
что ВСЕ корни больше K, и все корни меньше L

2Гость
Что еквивалентно |xi| < max(|K|,|L|), у чем Trurl и писал, еквивалентно, в том числе и в смысле применения дальше методов поиска корней

ньютона рафсона запускать из очень_большого_числа и из очень_маленького_числа!!
только числа должны быть не _очень_ большими, иначе будет floating point overflow
могу ньютоном рафсоном поделиться (писал не я)
2albom
а твоя программа каким методом решает??
зы.хотя если там будет нечто вроде

может поглючить

Сообщение отредактировано: wormball - 13.11.03, 17:52

Ищет интервалы (и полуинтервалы) изоляции через производную рекурсивно...

Сообщение отредактировано: Visitor - 13.11.03, 17:56

Вообще-то я и сам не знаю, как этот метод называется.
Просто нужно было решить пару уравнений, вот и додумался до такого. А так как с этой частью теории я вообще не знаком, то конечно и гарантий на отстутствие глюков дать не могу.

Надо же, Visitor уже разобрался в исходнике!!!

Сообщение отредактировано: albom - 13.11.03, 17:58

У нас был очень злобный препод по чисмету

но как? не смотрит же последовательно все значения аргумента??

Сообщение отредактировано: wormball - 13.11.03, 18:03

Рекурсивно

Корни многочлена лежат между корнями его производной и +/-oo

сумасойти
тогда можно вобще брать производные до тех пор, пока не будет прямая, а её корень найти аналитически

Именно так.
Подводные камни лежат около корней второй производной, где метод ньютона без модификаций может повести себя странно, поетому в средних интервалах изоляции использовать дихотомию -- тем более, что она позволяет вычислить значение корня с максимально возможной (машинной) точнстью.
Парные корни (когда f(xk) = f'(xk) = 0) необходимо обрабатывать отдельно...
В полуинтервале от -oo до самого левого корня второй производной и в полуинтервале от самого правого корня второй производной до +oo (у многочленов) неприятных для метода Ньютона особенностей нет. Сам метод ньютона, в етих полуинтервалах, можно уточнить, удлинняя спуск по производной в К раз и ища подходящую для дихотомии пару (xi, xi+1) (у мя ето было обозвано "вилка Ньютона с дихотомическим переключателем" ).
---
Вот, если вдруг кому проверенный емпирически план работ по курсачу нужен...

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

Ну, я так и делал. Искал производные, пока не получится линейное уравнение. Найти его корень - тривиально. Потом по рекурсии возвращался, методом Ньютона ища корни в интервалах. В качестве значений +/- бесконечность брал что-то типа 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?

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

А, так это же совсем просто.
|Xk| < 1+max(|Ai|/|An|) i<n An – старший коэффициент.

Сообщение отредактировано: Trurl - 16.11.03, 13:21

... И еще вопрос, кроме погрешности, как быстро, в среднем, у вас сходился метод ньютона? Сколько времени занимало вычисление одного корня одного многочлена? Поделитесь статистикой, плиз. Взамен могу свой исходник "причесать" и выложить

Сообщение отредактировано: Visitor - 16.11.03, 19:05

А, так это же совсем просто.
|Xk| < 1+max(|Ai|/|An|) i<n An – старший коэффициент.

Это только для максимального положительного годиться...
Т.е. правая граница, но часто с ОЧЕНЬ большой погрешностью

Это годится даже для комплексных. А о какой погрешности идет речь?

Просто из соображений симметрии, оно не может годиться "только для положительны"

Имеется ввиду не погрешность, а точность приближения вот етого max(xi) и min(xi)... Относительная ошибка в худшем случае может достигать где-то max(k=0..N, С(N, k)), N-степень многочлена, но ето не так уж и важно, т.к., в любом случае коеффициенты многочлена должны помещаться в разрядную сетку, иначе мы даже вычислить значение многочлена не сможем...