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

Дан многочлен степени 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