Форум на Исходниках.RU

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

Visitor — Wed, 19 Nov 2003 15:23:17 +0000

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

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

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

Trurl — Wed, 19 Nov 2003 14:49:19 +0000

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

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

tserega — Wed, 19 Nov 2003 13:42:41 +0000

tserega:

QUOTE (Trurl @ 16.11.03, 15:19)

QUOTE

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

А, так это же совсем просто.
|Xk| < 1+max(|Ai|/|An|) i

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

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

Visitor — Sun, 16 Nov 2003 19:03:36 +0000

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

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

Trurl — Sun, 16 Nov 2003 13:19:53 +0000

Trurl:

QUOTE

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

А, так это же совсем просто.
|Xk| < 1+max(|Ai|/|An|) i

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

Visitor — Sat, 15 Nov 2003 14:56:28 +0000

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

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

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

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

Visitor — Fri, 14 Nov 2003 15:20:51 +0000

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

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

tserega — Fri, 14 Nov 2003 15:10:51 +0000

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

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

Visitor — Fri, 14 Nov 2003 14:24:16 +0000

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

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

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

wormball — Fri, 14 Nov 2003 14:21:40 +0000

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

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

Visitor — Fri, 14 Nov 2003 10:20:26 +0000

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

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

tserega — Fri, 14 Nov 2003 10:19:50 +0000

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

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

Visitor — Fri, 14 Nov 2003 10:08:12 +0000

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

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

tserega — Fri, 14 Nov 2003 09:55:31 +0000

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

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

albom — Fri, 14 Nov 2003 09:50:51 +0000

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

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

tserega — Fri, 14 Nov 2003 09:44:31 +0000

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

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

albom — Fri, 14 Nov 2003 09:41:18 +0000

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

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

tserega — Fri, 14 Nov 2003 09:31:03 +0000

tserega:

QUOTE (albom @ 14.11.03, 11:26)

Теперь рассмотрим xmin, если f(xmin)>0 и f(xmin-1)

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

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

albom — Fri, 14 Nov 2003 09:26:27 +0000

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

CODE

xx:=xmin;
step:=1;
repeat
xx:=xx-step
step:=step*2;
until f(xx)<0;

То есть получим промежуток [xx; xmin], и корень можно найти, например, методом деления этого промежутка пополам.

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

tserega — Fri, 14 Nov 2003 06:28:44 +0000

tserega:

QUOTE (wormball @ 13.11.03, 20:05)

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

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

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

Visitor — Thu, 13 Nov 2003 19:15:45 +0000

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

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

wormball — Thu, 13 Nov 2003 18:05:29 +0000

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

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

Visitor — Thu, 13 Nov 2003 18:03:44 +0000

Visitor: Рекурсивно

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

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

wormball — Thu, 13 Nov 2003 18:02:28 +0000

wormball:

QUOTE

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

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

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

Visitor — Thu, 13 Nov 2003 18:00:22 +0000

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

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

albom — Thu, 13 Nov 2003 17:56:33 +0000

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

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

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

Visitor — Thu, 13 Nov 2003 17:51:27 +0000

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

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

wormball — Thu, 13 Nov 2003 17:44:32 +0000

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

CODE

   /
   /
   __ /
   / \ /
   / \___/
_______________ /_________________
   /
      /
      /

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

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

Visitor — Thu, 13 Nov 2003 17:42:48 +0000

Visitor:

QUOTE (Guest @ 13.11.03, 22:10)

QUOTE (Trurl @ 13.11.03, 17:03)

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

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

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

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

albom — Thu, 13 Nov 2003 17:42:38 +0000

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

QUOTE

4
4 0 1 -3 -2

Потом из результатов выбирай минимальный и максимальный - получишь свои границы.

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

Guest — Thu, 13 Nov 2003 17:10:03 +0000

Guest:

QUOTE (Trurl @ 13.11.03, 17:03)

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

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

Trurl — Thu, 13 Nov 2003 14:03:58 +0000

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

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

tserega — Thu, 13 Nov 2003 13:20:37 +0000

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

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

esperanto — Thu, 13 Nov 2003 13:17:03 +0000

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

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

tserega — Thu, 13 Nov 2003 12:01:25 +0000

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