Алгоритм решения полинома высокой степени >100?

← →
Maxim Suvorov (2006-10-30 01:46) [0]

Какие существуют алгоритмы поиска решиний полинома высоких степеней (>100) с указаной точностью?
По возможности с исходником, или хотя бы реализуемый алгоритм практически.

← →
Германн © (2006-10-30 02:02) [1]

А в твоём распоряжении есть "суперкомпьютер"?
Без него, сама подобная мысль, имхо, конщунственна.

← →
Maxim Suvorov (2006-10-30 02:09) [2]

не всех решений, а тольчо частичных, причем они лежат в рамках -100 и до 10000

← →
ЮЮ © (2006-10-30 03:30) [3]

Метод половинного деления: если в двух точках знаки разные, значит где-то есть корень.

Значение, естественно, считать не
A[n] * x^n + A[n-1] * x^(n-1) + ... + A[0]
a
((.. (A[n] * x + A[n - 1]) * x ....) * x + A[0]

← →
MBo © (2006-10-30 07:48) [4]

Корни полиномов такой степени обычно не ищут, т.к. точности не хватит.
Для степеней до 10 обычно хватает простых численных методов (Ньютона-Рафсона, Лагерра и т.п.), до примерно 20-30 - нужны тщательно отлаженные профессиональные библиотеки, использующие методы Дженкинса-Трауба или решающие проблему поиска собственных значений

Откуда вообще такая задача возникла?

← →
palva © (2006-10-30 10:27) [5]

Наверно, нужно научиться раскладывать полином на сомножители. Скажем 100 степени на два полинома 50 степени и т. д. до 2-й.

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

Вобщем надо экспериментировать.

← →
palva © (2006-10-30 10:28) [6]

> много, попыток выбиратя начальное значение методом Монте-Карло.
много попыток, выбирая начальное значение методом Монте-Карло.

← →
Вольный Стрелок © (2006-10-30 10:58) [7]

схема Горнера?

← →
Maxim Suvorov (2006-10-30 11:34) [8]

> Откуда вообще такая задача возникла?
Финансовый анализ инвестиционых инструментов и облигаций.
Полином есть уровнение такого вида:
K1/(1+r/m1)^t1*m1+K2/(1+r/m2)^t2*m*+....Kn/(1+r/mn)^tn*mn+C=0
Где t*m>100, вот так вот. Если методои перебора значений?

← →
Maxim Suvorov (2006-10-30 11:35) [9]

Ищем r.

← →
palva © (2006-10-30 11:54) [10]

То есть степень полинома примерно 100 в квадрате?
А что такое частное решение.
А комплексные корни надо искать?

← →
Maxim Suvorov (2006-10-30 12:08) [11]

нет, комлексные не надо.

← →
palva © (2006-10-30 12:33) [12]

> нет, комлексные не надо.
Тогда лучше искать в соответствии с
ЮЮ © (30.10.06 03:30) [3]
без преобразования функции в многочлен. Нетривиально будет понять все ли корни найдены. Сначала можно пройти по области -100 и до 10000 с каким-нибудь небольшим шагом.

← →
Axis_of_Evil © (2006-10-30 12:36) [13]

> palva © (30.10.06 12:33) [12]
> Сначала можно пройти по области -100 и до 10000 с каким-
> нибудь небольшим шагом.

если 2*n корня окажутся в одном интервале разбиения?
ф-ция будет иметь значения одинакового знака на концах.
не так, imho, делать надо.
// не знаю как:>

← →
MBo © (2006-10-30 12:38) [14]

>если 2*n корня окажутся в одном интервале разбиения?
ф-ция будет иметь значения одинакового знака на концах.

Есть метод Штурма для определения количества корней на интервале

← →
palva © (2006-10-30 12:41) [15]

> метод Штурма
Тогда придется преобразовывать к многочлену.

K1/(1+r/m1)^t1*m1+K2/(1+r/m2)^t2*m*+....Kn/(1+r/mn)^tn*mn+C=0

И это полином? :)
k1
-------------------- + ..
( 1 + r/m1) ^(t1*m1)

← →
Maxim Suvorov (2006-10-30 18:18) [17]

> И это полином? :)

Сводиться к полиному.
Есть едеи как решать?

> Maxim Suvorov (30.10.06 18:18) [17]

> > И это полином? :)

k1
-------------------- + ..
( 1 + r/m1) ^(t1*m1)

> Сводиться к полиному.

Ну, дык и покажи оный полином.

--
Regards, LVT.

> Maxim Suvorov (30.10.06 18:18) [17]

> Есть едеи как решать?

Методом Ньютона, вестимо.

--
Regards, LVT.

← →
Maxim Suvorov (2006-10-31 04:00) [20]

Нет, так не покатит, в даннов случае по-моему (поправте если не прав), это апроксимируется до:
k1
-------------------- =exp(-r*t1)*k1,
( 1 + r/m1) ^(t1*m1)

тут как бы задача по-проще (?), но всеравно едей как решать у меня нету, может подскажете штонить? (МазКад даний пример с 100 членов решил где-то за 1 мин (!), приэтом нашел около 60 (!) корней, обычных и комлексных :(.

Я в свое время творил программу, она рисовала годограф функции до 10^3 или 10^4 степени переменной.
Потом по годографу на глазок определялись корни.

← →
Maxim Suvorov (2006-10-31 20:43) [22]

Усе тему можно закрыть я уже сам вывел нужный алгоритм, уже проверил - работает.

Алгоритм решения полинома высокой степени >100? Найти похожие ветки