2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

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

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



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 полином n-ой степени, численный поиск корней
Сообщение26.10.2011, 00:28 


25/10/11
23
Уважаемые знатоки. У меня есть задача, решить которую самостоятельно, не хватает опыта. Поэтому искрене прошу советов

Итак. У меня есть некоторая компьютерная программа, в которой производятся некоторые статистические вычисления. На одном из шагов мне нужно найти все корни полинома n-степени (причем может быть даже что-то вроде такого k*x^50+x^49+...=0).
Собственно, нужно выбрать наиболее отпимальный (в реализации\быстродейтсвии) способ нахождения корней.

1. Какой способ можете посоветовать?
2. Может быть кто-нибудь владеет \ знает где скачать программный код (на c++ или delphi) для решения поставленной задачи?

 Профиль  
                  
 
 Re: полином n-ой степени
Сообщение26.10.2011, 01:40 
Заблокирован
Аватара пользователя


11/09/11

650
Чем Вам такое не нравится?
http://www.wolframalpha.com/input/?i=2x ... 9%2Bx%2B10

 Профиль  
                  
 
 Re: полином n-ой степени
Сообщение26.10.2011, 07:07 
Заслуженный участник


09/09/10
3729
Лично я бы посоветовал последовательно использовать модифицированный метод Ньютона (который не давится кратными корнями).

 Профиль  
                  
 
 Re: полином n-ой степени
Сообщение26.10.2011, 07:51 
Заслуженный участник


27/06/08
4058
Волгоград
Klad33 в сообщении #496055 писал(а):
Чем Вам такое не нравится?
http://www.wolframalpha.com/input/?i=2x ... 9%2Bx%2B10

Мне не нравится тем, что корней маловато. Их, все же 50. И кратных нет:
Код:
> f:=2*x^50-5*x^49+3*x^48+x+10:df:=diff(f,x);

                           49        48        47
                df := 100 x   - 245 x   + 144 x   + 1

> gcd(f,df);
> evalf(solve(2*x^50-5*x^49+3*x^48+x+10),20);

  1.1070783976502150137, 1.4999999594194430383,

        1.0887526302702221950 + 0.12832512894031300781 I,

        1.0477544511244468966 + 0.26112099742817438460 I,

        0.99286177117267352192 + 0.38964662292861444653 I,

        0.92491753395247690926 + 0.50999630544203193082 I,

        0.84440846523346705649 + 0.62038090459553681292 I,

        0.75218958623981078991 + 0.71938932194096141145 I,

        0.64944355849241159127 + 0.80574170757065662541 I,

        0.53761167686690813376 + 0.87829403300288033756 I,

        0.41833722779476571614 + 0.93607274113308065674 I,

        0.29341812777692649500 + 0.97830543984969870585 I,

        0.16476477545918509721 + 1.0044436424052003874 I,
       
        0.034360770458306630867 + 1.0141781219314906225 I,

        -0.095774606469229708680 + 1.0074478071694568603 I,

        -0.22362252981448731435 + 0.98444293380485576513 I,

        -0.34719935415217188307 + 0.94560298425854776394 I,

        -0.46458968217603803295 + 0.89160986053610185589 I,

        -0.57397742798925992156 + 0.82337671514230618447 I,

        -0.67367449928204851731 + 0.74203288444702871222 I,

        -0.76214674521744164696 + 0.64890540378621331089 I,

        -0.83803687662356082262 + 0.54549761604446718058 I,

        -0.90018414845240605465 + 0.43346540192908269239 I,

        -0.94764068764374588853 + 0.31459155165145178832 I,

        -0.97968443752576770068 + 0.19075876113745373988 I,

        -0.99582875803027256802 + 0.063921675067892839985 I,

        -0.99582875803027256802 - 0.063921675067892839985 I,

        -0.97968443752576770068 - 0.19075876113745373988 I,

        -0.94764068764374588853 - 0.31459155165145178832 I,

        -0.90018414845240605465 - 0.43346540192908269239 I,

        -0.83803687662356082262 - 0.54549761604446718058 I,

        -0.76214674521744164696 - 0.64890540378621331089 I,

        -0.67367449928204851731 - 0.74203288444702871222 I,

        -0.57397742798925992156 - 0.82337671514230618447 I,

        -0.46458968217603803295 - 0.89160986053610185589 I,

        -0.34719935415217188307 - 0.94560298425854776394 I,

        -0.22362252981448731435 - 0.98444293380485576513 I,

        -0.095774606469229708680 - 1.0074478071694568603 I,

        0.034360770458306630867 - 1.0141781219314906225 I,

        0.16476477545918509721 - 1.0044436424052003874 I,

        0.29341812777692649500 - 0.97830543984969870585 I,

        0.41833722779476571614 - 0.93607274113308065674 I,

        0.53761167686690813376 - 0.87829403300288033756 I,

        0.64944355849241159127 - 0.80574170757065662541 I,

        0.75218958623981078991 - 0.71938932194096141145 I,

        0.84440846523346705649 - 0.62038090459553681292 I,

        0.92491753395247690926 - 0.50999630544203193082 I,

        0.99286177117267352192 - 0.38964662292861444653 I,

        1.0477544511244468966 - 0.26112099742817438460 I,

        1.0887526302702221950 - 0.12832512894031300781 I


 Профиль  
                  
 
 Re: полином n-ой степени
Сообщение26.10.2011, 09:30 
Заслуженный участник


11/05/08
32166
wizardofnothing в сообщении #496052 писал(а):
На одном из шагов мне нужно найти все корни полинома n-степени (причем может быть даже что-то вроде такого k*x^50+x^49+...=0).
Собственно, нужно выбрать наиболее отпимальный (в реализации\быстродейтсвии) способ нахождения корней.

Ничего -- на таких степенях любой алгоритм будет численно крайне неустойчив.

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

 Профиль  
                  
 
 Re: полином n-ой степени
Сообщение26.10.2011, 16:56 
Заслуженный участник
Аватара пользователя


11/03/08
9490
Москва
Присоединяюсь к совету. Если в задаче что-то требует нахождения корней полинома 50-й степени, то что-то в постановке ложно.

(Оффтоп)

Был у меня один знакомый - пол-аспирантуры убил на разработку метода нахождения корней характеристического полинома корреляционной матрицы, с построением как-то справился, методом Фадеева-Леверье, хоть и медленно, а корни оказались крайне неустойчивы, библиотеку повышенной точности сам написал, диссертация горела.
Даже не знаю, сделал ли я доброе дело, рассказав о стандартной программе нахождения С.З. методом Якоби. С одной стороны, диссер он в срок вполне успешно сдал, с другой - обидел я его сильно, жалко смотреть было на последовавшую истерику...

 Профиль  
                  
 
 Re: полином n-ой степени
Сообщение26.10.2011, 23:53 
Заслуженный участник


23/07/08
10626
Crna Gora
Необходимость факторизации полинома высокой степени возникает, например, при использовании метода Прони (цифровая обработка сигналов) -- это метод приближения сигнала суммой экспонент.

В книге С.Л.Марпл, "Цифровой спектральный анализ и его приложения" для этой цели предлагается использовать алгоритм Дженкинса-Трауба, там приводится и программа (правда, на Фортране). Я её когда-то давно переводил на C++. Программа довольно сложная, занимает несколько страниц, но хорошие алгоритмы на дороге не валяются. Находит все корни полинома -- вещественные, комплексные. Коэффициенты полинома тоже в общем случае комплексные.

 Профиль  
                  
 
 Re: полином n-ой степени
Сообщение27.10.2011, 00:34 


26/08/11
2057
Евгений Машеров в сообщении #496188 писал(а):
Присоединяюсь к совету. Если в задаче что-то требует нахождения корней полинома 50-й степени, то что-то в постановке ложно.
Игра: Генерирутся последовательно 100 случайных чисел в интервале $(0;1)$. После каждого наибольшего числа можем или выбрать, или подождать. Цель-выбрать наибольшее число. При каких "критических" значениях будем выбирать.

 Профиль  
                  
 
 Re: полином n-ой степени
Сообщение27.10.2011, 01:14 
Заслуженный участник


27/06/08
4058
Волгоград
Shadow в сообщении #496363 писал(а):
Евгений Машеров в сообщении #496188 писал(а):
Присоединяюсь к совету. Если в задаче что-то требует нахождения корней полинома 50-й степени, то что-то в постановке ложно.
Игра: Генерирутся последовательно 100 случайных чисел в интервале $(0;1)$. После каждого наибольшего числа можем или выбрать, или подождать. Цель-выбрать наибольшее число. При каких "критических" значениях будем выбирать.
Известная стратегия - пропустить примерно $\frac{100}e$ чисел, запомнив наибольшее из них, и выбрать первое большее того, что запомнили.
Только причем здесь исходная задача?

 Профиль  
                  
 
 Re: полином n-ой степени
Сообщение27.10.2011, 07:16 


26/08/11
2057
Цитата:
Известная стратегия - пропустить примерно $\frac{100}e$ чисел, запомнив наибольшее из них, и выбрать первое большее того, что запомнили.
Только причем здесь исходная задача?
Это когда нет ограничений. А когда числа ограничены в интервале $(0;1)$ задача совершенно другая.
Т.е понимаете, что если с первого раза попадется 0.99999999991, ждать $\frac{100}{e}$ попыток не буду.

 Профиль  
                  
 
 Re: полином n-ой степени
Сообщение27.10.2011, 08:01 
Заслуженный участник


12/09/10
1547
Так ведь она и легче гораздо.
Если появился на $k$-м числе максимум $a$, то вероятность появления еще хотя бы одного максимума $1-a^{100-k}$. Ну и сравниваем с $1/2$. Каким образом полиномы выскакивают?

 Профиль  
                  
 
 Re: полином n-ой степени
Сообщение27.10.2011, 08:05 
Заслуженный участник


27/06/08
4058
Волгоград
Shadow в сообщении #496384 писал(а):
Это когда нет ограничений. А когда числа ограничены в интервале $(0;1)$ задача совершенно другая.
Т.е понимаете, что если с первого раза попадется 0.99999999991, ждать $\frac{100}{e}$ попыток не буду.
Угу. Невнимательно прочел.
Сколько раз зарекался по ночам не отвечать...

 Профиль  
                  
 
 Re: полином n-ой степени
Сообщение27.10.2011, 08:33 


26/08/11
2057
Cash в сообщении #496389 писал(а):
Так ведь она и легче гораздо.
Если появился на $k$-м числе максимум $a$, то вероятность появления еще хотя бы одного максимума $1-a^{100-k}$. Ну и сравниваем с $1/2$. Каким образом полиномы выскакивают?

Результат у Вас получится не плохой, но не оптимальный. А зачем сравнивать с $\frac 1 2$. С другим надо сравнивать.....и все не так просто

 Профиль  
                  
 
 Re: полином n-ой степени
Сообщение27.10.2011, 10:41 
Заслуженный участник


12/09/10
1547
Чувствую себя злостным оффтопщиком...
Можно попросить модераторов выделить задачу в отдельную тему?

Цитата:
Результат у Вас получится не плохой, но не оптимальный

В задаче надо ставить четкие критерии, а не расплывчатые цели.
Я исходил из следующего:если игрок угадал максимум, то он получает рубль, если нет - рубль отдает. Цель - максимизировать прибыль.
У вас есть сомнения, что предложенная мной стратегия не оптимальна?
Любая другая стратегия будет ошибочна.
Допустим появляется на $k$-м шаге максимум $a$ и вы принимаете решение брать или не брать.
Пусть $p=1-a^{100-k}$. Если $p>1/2$ и вы отказываетесь или $p<1/2$ и вы берете, то вы играете в минус, при следовании стратегии - в плюс. Какие еще могут быть вопросы?
А вот величина этой прибыли - это отдельная история...

 Профиль  
                  
 
 Re: полином n-ой степени
Сообщение27.10.2011, 11:33 


26/08/11
2057
Cash в сообщении #496406 писал(а):
Чувствую себя злостным оффтопщиком...
Можно попросить модераторов выделить задачу в отдельную тему?

Цитата:
Результат у Вас получится не плохой, но не оптимальный

В задаче надо ставить четкие критерии, а не расплывчатые цели.
Я исходил из следующего:если игрок угадал максимум, то он получает рубль, если нет - рубль отдает. Цель - максимизировать прибыль.
если игрок угадал максимум, то он получает рубль, если нет - ничего не получает и ничего не отдает. Правильная постановка.
Вый, кстати, получили оптимальную стратегию задачи: "Можете выбрать одно число. И ето ваша прибыль" (Без условие, чтобы было наибольшее). Но задача то другая. Интересный вариант - как изменится стратегия, если угадать максимум получаем не рубль, а стоимость числа

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 24 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group