Алгоритм расчёта вещественных корней полиномов

[SteveNers]

Теоремой Штурма + бин. поиском вроде побыстрее будет

[Sirion]

Написать собственный велосипед — бесценно.

[mamkaololosha]

А теперь по порядку.
Где применяется? Как? Зачем? В университетах учат учиться? Покажут на заводе когда попадете по распределению? Альё, уже 25 лет никого никуда не распределяют. Я могу реализовать Ваш метод где-то на конкретной задаче? Где? Выложить на гитхаб и написать в резюме, что я его знаю и понимаю? А когда спросят «как вы его примените для оптимизации сети или базы данных» мне ссылку на эту статью кидать?

[diller61]

хм, мне кажется это применяется в широчайшем спектре задач

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

сплайны, кривые Безье(где применяются надеюсь писать не надо?) — все это тоже полиномы

[mamkaololosha]

> в широчайшем спектре задач
Вы философ-фундаменталист? У вас спектр задач на столько широк, что вы не можете решить ни одну из них? Можно применить этот метод в ракетостроении чтобы ракеты не падали? Как? Вот конкретная задача. Её могут попросить закодировать в гугл-доке на собеседовании в NASA.
Кривые Безье? Геимдев, 2 курс унивеситета, 10 класс физмата. Ничего оригинального, вот серьезно.

[diller61]

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

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

[diller61]

>Кривые Безье? Геимдев, 2 курс унивеситета, 10 класс физмата.

еще автомобилестроение

кстати чтоб ракеты не падали первоначально необходимо определить причину падения

[diller61]

может причина в том что кто-то из разработчиков забыл как рассчитывать вещественные корни полиномов)

[diller61]

когда начинаешь программировать что-то отличное от «оптимизации сети или базы данных» внезапно, иногда приходится вспоминать многое из того чему учили в «универе» и в «10 классе физмата». Физика, геометрия, матан, сопромат, техмех, теория вероятности, социология…
может потребоваться вспомнить все и раскопать новое, что не входило в учебную программу

[veontomo]

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

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

Пример: полином p1 = x — 2 с одним корнем равным 2, строим полином2 p2 = x + 2, который имеет один корень -2. Произведение полиномов p1*p2 = x^2 — 4 имеет корни +2 и -2. Который из них равен квадрату корней исходых полиномов?

[tsul]

Опущена операция замены переменной: x^2 -> z. Т.е. квадрированным называется полином*полином2 при условии замены. Имеет ту же степень, что и исходный полином.

Нашёл здесь: stu.sernam.ru/book_dig_m.php?id=69

[artemoz]

Если я правильно понял, квадрированный полином предполагается решать относительно x^2. То бишь несколько раз квадрируем, потом берем корень соответствующей степени из второго коэффициента.

[ezz666]

Нужно ещё сделать замену x^2 на x. Очевидно, что получившийся полином уже будет иметь корни равные квадратам корней исходных полиномов.
Но есть другая проблема: если у полинома есть комплексные корни этот метод уже не сработае, замену сделать не удастся.

[veontomo]

Предлагаемый метод претендует на нахождение только вещественных корней, а при при квадрировании комплексные корни появиться не могут.

[Timka21213]

http://www.sciencedirect.com/science/article/pii/S0747717197901905 < — как вариант

[BalinTomsk]

А можно вставить какой-нибудь реальный пример? Типа такого?

int main(int argc, char** argv)
{

    double kf = 5;
    double rootsArray[] = {1,3,6,9};
    int rootsCount = 2;
    polynomRealRoots(15, &kf, rootsArray, rootsCount);

    return 0;
}

Заодно и красивый график для привлечения внимания?

[Sutar]

p2 = -p1 = -(x-2) = -x+2. Вы минус забыли.

[pchelintsev_an]

Есть неплохая книга по этой теме Г.П. Кутищева «Решение алгебраических уравнений произвольной степени: Теория, методы, алгоритмы» (URSS, 2010). Аналитически для уравнения третьей степени — мой топик.

[vadimr]

Не вполне понятна практическая применимость описанного. Давно известны простые численные методы нахождения вещественных корней произвольных дифференцируемых функций. В частности, можно взять в библиотеке старинную книжку «Библиотека алгоритмов. Алгоритмы 1б-50б» и посмотреть там алгоритм 25б. Помнится, я в детстве ещё искал с его помощью корни уравнений вида sin(x)=ln(x) и т.п.

[chersanya]

Далеко — не обязательно в абсолютных значениях. 0.001 отличается от 1 так же, как 1 от 1000.

[rafuck]

А можно, наверное, глупый вопрос. Зачем на практике находить корни полиномов высокой степени?

[Calvrack]

ну масса есть задач. Из бытовой практики — 5ти точечный метод калибровки стерео-пары. Или — есть образмеренный чертеж в Solidworks с наложенными ограничениями, и надо его отобразить — степень там может быть более-менее большой. Вот любой кому нужна такая функциональность для его собственных нужд вынужден искать корни полиномов (или систем полиномов).

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

[rafuck]

Спасибо. Про такой вариант решения задачи на СЗ знал, но не пришло в голову почему-то…
P.S. Немного не в тему, навеяло полиномами. Вспомнил замечательную фразу, не помню, чью: «Полиномы Чебышева всюду плотны в вычислительной математике».

[sci_nov]

По-моему, в основополагающей идее метода есть исключения…