Как полиномы решать?

Vovka · Post by **Vovka** » 18 Feb 2002 15:14

Подскажите программки которые умеют находить _точные_ корни полиномов?

stas_u · Post by **stas_u** » 18 Feb 2002 15:33

<blockquote>quote:<hr>Originally posted by Vovka:
Подскажите программки которые умеют находить _точные_ корни полиномов?<hr></blockquote>

А это разве возможно в общем случае?

AK70 · Post by **AK70** » 18 Feb 2002 15:38

Maple, Matematika, Reduce

Vovka · Post by **Vovka** » 18 Feb 2002 15:40

<blockquote>quote:<hr>Originally posted by stas_u:


А это разве возможно в общем случае?

<hr></blockquote>

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

Vovka · Post by **Vovka** » 18 Feb 2002 15:46

<blockquote>quote:<hr>Originally posted by AK70:
Maple, Matematika, Reduce<hr></blockquote>

А бесплатное чего-нить есть?

AK70 · Post by **AK70** » 18 Feb 2002 15:56

<blockquote>quote:<hr>Originally posted by Vovka:


А бесплатное чего-нить есть?<hr></blockquote>

yes, I don't remember the titles. search in Google something like "symbolic/computer algebra package polynomial"

I've seen programs in different languages. moreover, all algorithms are very well described.

Kisena · Post by **Kisena** » 22 Feb 2002 01:35

<blockquote>quote:<hr>
матрицы собственных значений
<hr></blockquote>
Матрицы собственных значений чего?

flip_flop · Post by **flip_flop** » 22 Feb 2002 04:37

<blockquote>quote:<hr>Originally posted by Kisena:

Матрицы собственных значений чего?<hr></blockquote>
Eigen values of a companion matrix:
let p(x)=c1*x^(n-1)+ ... + cn
A=
-c2/c1 -c3/c1 ... -cn/c1
1 0 ... 0
0 1 ... 0
...
0 ... 1 0

т.е. под главной диагональю единичная диагональ. Тогда
x_roots|p(x)=0: x_roots=eig(A)
Детали типа лидирующих нулей опущены
P.S. Сорри, болею гриппом, отупел - следует читать "на основе собственных значений присоединенной матрицы"

[ 21-02-2002: Message edited by: flip_flop ]

Brat Levon · Post by **Brat Levon** » 22 Feb 2002 09:24

<blockquote>quote:<hr>Originally posted by Vovka:
Подскажите программки которые умеют находить _точные_ корни полиномов?<hr></blockquote>

Просто интересно:
Что значит "точные"? С какой степенью точности? С использованием радикалов?
Какой степени полиномы?

flip_flop · Post by **flip_flop** » 22 Feb 2002 09:53

<blockquote>quote:<hr>Originally posted by Brat Levon:


Просто интересно:
Что значит "точные"? С какой степенью точности? С использованием радикалов?
Какой степени полиномы?<hr></blockquote>АК70 имел в виду символьное решение (в [b:dd57c41e2b] аналитическом [/b:dd57c41e2b] виде, как функцию коеффициентов полинома). Если находить [b:dd57c41e2b] численное [/b:dd57c41e2b] решение с помощью бесплатных программ, то могу рекомендовать ОКТАВу - бесплатный аналог МАТЛАБа. Функция roots находит корни полинома произвольной степени. Вспомним основную теорему алгебры - полином n-й степени имеет ровно n корней (корни могут быть комплексные или кратные). Практически погрешность численного нахождения корней определяется погрешностью округления и обычно корни находятся с использованием численно устойчивой схемы на основе матрицы собственных значений.

Vovka · Post by **Vovka** » 22 Feb 2002 11:27

<blockquote>quote:<hr>Originally posted by Brat Levon:


Просто интересно:
Что значит "точные"? С какой степенью точности? С использованием радикалов?
Какой степени полиномы?

<hr></blockquote>

А что такое радикалы? [img:85064fa070]images/smiles/icon_eek.gif[/img:85064fa070]

Полиномы любой степени.

Кстати, AK70, чего-то я не могу найти алгоритма решения.

Может, нужно поконкретней пояснить, что мне нужно. Есть какой-то полином с коэффициентами a0...an. Все ли корни этого полинома можно "собрать", используя коэффициенты a0...an, четыре арифметические операции, и операцию извлечения корня? (Какой степени, кстати? Только n?)

Если да, то при "хороших" значениях коэффициентов a0...an - например, целых числах, небольших по модулю, получается не так уж много вариантов перебора. Например, если aj==1, то вряд ли корень полинома степени, скажем, 4, будет иметь корень вида (325325325325 + sqrt(7463634))/968745.

Если нет, то что ещё пожет появиться? Какие-нить бесконечные дроби, корни, суммы? Может, их тоже можно включить в общуй перебор и проверить?

Главное - нужно знать, для произвольного n, вид возможных корней полинома степени n.
После этого довольно просто состряпать программку, перебирающую все возможные корни и проверяющие их (разумеется, уменьшая степень полинома при нахождении каждого корня).

Dm.uk · Post by **Dm.uk** » 22 Feb 2002 11:47

2 DFF
нет что б решение на сдвиговых регистрах отобразить [img:fba2c1c0ca]images/smiles/icon_smile.gif[/img:fba2c1c0ca]

flip_flop · Post by **flip_flop** » 22 Feb 2002 16:54

<blockquote>quote:<hr>Originally posted by Dm.ie:
2 DFF
нет что б решение на сдвиговых регистрах отобразить [img:1b79f0d426]images/smiles/icon_smile.gif[/img:1b79f0d426] <hr></blockquote> [img:1b79f0d426]images/smiles/icon_smile.gif[/img:1b79f0d426]