Программа нахождения корней полиномов

emorozovan

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

sokrat

Ну запости алгоритм для начала

Xephon

тебе ведь, наверное, приближенно надо
попробуй пакет MAPLE

spiritmc

А что по этому поводу говорит http://netlib.org ?
А GNU Scientific Library?
---
...Я работаю антинаучным аферистом...

lesfly

Знаю как эту задачу свести к задаче нахождения собственных значений комплексной матрицы произвольного вида

spiritmc

http://netlib.org
Я там видел кучу различных сборок для нахождения соб. значений матриц разного вида. Там же есть и ссылки на мат. литературу.
---
"Vyroba umelych lidi, slecno, je tovarni tajemstvi."
Karel Capek

lesfly

В общем маза в том, чтобы составить матрицу, для которой этот многочлен является характеристическим, и тогда его корни - это собственные значения матрицы

spiritmc

А ты знаешь, как составлять такой многочлен?
---
...Я работаю антинаучным аферистом...

lesfly

Видел когда-то в одной книжонке, сейчас не помню, кому надо пусть сами придумывают

SO-RO-KA-

нахождение собственных значений матрицы посложней будет вроде
есть простые методы:
метод ньютона (производная считается аналитически)
можно искать минимум абсолютного значения, стандартными методами спуска

lesfly

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

spiritmc

Ошибся, читать --- "матрицу".
---
"...Надо учиться --- не напрягаясь!.." Акад. А.А.Бучаченко.

lesfly

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

spiritmc

Спуском ты найдёшь только один корень.
Если много корней, дорого будет по времени.
Опять же, начальное приближение?
---
...Я работаю антинаучным аферистом...

erema22

>нахождение собственных значений матрицы посложней будет вроде
AFAIK сведение к проблеме собственных чисел - самый нормальный способ поиска _всех_ корней многочлена.
Если речь только о частичной задаче, то возможно, некоторые способы будут лучше.

erema22

QR-алгоритм
(матрицы здесь явно не будут симметричными)

vln2

Есть же бессмертная книжка Богачева, где все как есть написано. Ну и ЧМЫ поднять стоило бы.
Кроме того, есть книга Панкратьева, где объяснено, как искать корни комплексных полиномов.
Да, в конце концов, есть очень быстрый метод нахождения наибольшего (наименьшего) корня. Если есть его комплексная версия, то банальным делением многочлена на полученный корень и последующим повторением алгоритма можно очень быстро найти все корни.

piv2008

Поделитесь, пожалуйста, со мной, неучем, ссылкой на "бессмертную книжку Богачева" и на алгоритм поиска наименьшего корня.

SO-RO-KA-

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

erema22

Я сам уже всё забыл.
Но когда мне вот именно это было надо, я просто пошёл на кафедру и застал там г-на Ищенко.
Он много чего мне сообщил, но основной вывод был именно такой, который я сформулировал выше.
ЗЫ По-моему, на мехмате никогда не было проблемой подойти к кому-то из преподавателей и что-то спросить. Как минимум, книжку посоветуют.
Оставить комментарий
Имя или ник:
Комментарий: