Класс для приближенного поиска корней полинома n-ной степени от 1 переменной (с++)

[NikSlim]

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

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

Стоит ли мне отдельно писать методы поиска корней для степеней < 5? Там ведь скорее всего будет выигрыш по времени по сравнению с численными способами, имеет ли смысл так делать?

[Abstraction]

Стоит ли мне отдельно писать методы поиска корней для степеней < 5? Там ведь скорее всего будет выигрыш по времени по сравнению с численными способами, имеет ли смысл так делать?

Если не смущают комплексные числа - можете сделать.

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

Здесь (внимание на раздел member functions, пройдите по ссылкам - в описаниях конкретных методов есть и примеры использования).
Также Шилдт или любой другой приличный справочник по C++.

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

Если нужно найти хотя бы один корень, то для нечётной степени - метод дихотомии (возьмите в начале значения в точках z, -z, где z таково, что старший член превосходит по модулю все младшие).
Ну, как легко задаваемый, хоть и нестрогий, вариант: метод случайной точки (берёте упомянутые z и -z, если в них знаки разные - метод дихотомии; если одинаковые - раз за разом берёте случайную точку на интервале от -z до z, пока знак в ней не окажется другим или не будет проведено "достаточно много" испытаний).

[NikSlim]

Сообщение от Abstraction

Если не смущают комплексные числа - можете сделать.

Здесь (внимание на раздел member functions, пройдите по ссылкам - в описаниях конкретных методов есть и примеры использования).
Также Шилдт или любой другой приличный справочник по C++.

Если нужно найти хотя бы один корень, то для нечётной степени - метод дихотомии (возьмите в начале значения в точках z, -z, где z таково, что старший член превосходит по модулю все младшие).
Ну, как легко задаваемый, хоть и нестрогий, вариант: метод случайной точки (берёте упомянутые z и -z, если в них знаки разные - метод дихотомии; если одинаковые - раз за разом берёте случайную точку на интервале от -z до z, пока знак в ней не окажется другим или не будет проведено "достаточно много" испытаний).

Буквально пол часа назад сам нашел эту ссылку) Сначала игнорил, потому что не по-русски, я с инязом не в ладах, потом все-таки проверил. Без иняза понятно)

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

[Abstraction]

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

Сомневаюсь, что бисекция в этом случае поможет (может быть всего один корень чётной кратности). Но... если многочлен имеет вид x^n+a_(n-1)*x^(n-1)+...+a_1*x+a_0, то при z=max(|a_(n-1)|, |a_(n-2)|^(1/2), ..., |a_1|^(1/(n-1), |a_0|^(1/n)), все корни заведомо лежат от -z до z.

[NikSlim]

Сообщение от Abstraction

Сомневаюсь, что бисекция в этом случае поможет (может быть всего один корень чётной кратности). Но... если многочлен имеет вид x^n+a_(n-1)*x^(n-1)+...+a_1*x+a_0, то при z=max(|a_(n-1)|, |a_(n-2)|^(1/2), ..., |a_1|^(1/(n-1), |a_0|^(1/n)), все корни заведомо лежат от -z до z.

а вот это интересно, можно ли поинтересоваться, почему? я не очень с алгеброй

[Abstraction]

Гм... по здравом размышлении, там не максимум, а 2*max.
Соображение очень простое: |x|^n>|a_m|*|x|^m при |x|^(n-m)>|a_m| или |x|>|a_m|^(1/(n-m)). Далее, (2*max)^n = max^n+n*max^n+... >= max^n+max*max^(n-1)+max^2*max^(n-2) >= |a_(n-1)|*max^(n-1)+...+|a_0|. То есть, первый член по модулю заведомо превосходит сумму всех остальных, и при увеличении x ситуация уже не изменится - нулей дальше нет. По сути, это отражение того факта, что полином степени n с некоторого момента оказывается больше любого полинома степени (n-1).

[NikSlim]

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