Алгоритмы нахождения корня полинома

Исследование интервала

Рассмотрим один из простых алгоритмов, исследующих, существует ли на заданном интервале [e, f] хотя бы один корень. Один корень заведомо существует, если полином на концах исследуемого интервала имеет разные знаки или один из концов интервала уже является корнем полинома. Это условие и будет характерным признаком поиска нужного интервала. Если исходный интервал [e, f] удовлетворяет характерному признаку, то задача решена и такой интервал найден. В противном случае в цикле по вычислим , где - длина исходного интервала (). Затем организуем внутренний цикл, в котором проверим характерный признак на всех интервалах длины h. Если интервал будет найден, то вычисления завершаются, в противном случае переходим к следующему шагу цикла по , производя очередное дробление . Завершение цикла по означает, что если исследуемый интервал [e, f] и содержит корни, то это близкие пары корней, отстоящие друг от друга на расстояние, меньшее - заключительной длины интервала по завершении цикла по .

Приведу несколько практических рекомендаций, полезных при реализации этой схемы. Внутренний цикл следует организовать так, чтобы не повторять вычисление полинома в тех точках, в которых это вычисление проводилось на предыдущих шагах цикла. Это означает, что когда шаг , то во внутреннем цикле достаточно вычислить значение полинома не более чем в точках. Внешний цикл достаточно ограничить числом в интервале от 10 до 20, поскольку уже при величина исходного интервала уменьшится более чем в 1000 раз, что вполне достаточно в большинстве практических ситуаций. Хотя следует помнить, что в ряде ситуаций практики приходится иметь дело с резко осциллирующими функциями, где близкие корни являются правилом, а не исключением.

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