Алгоритм применения схемы Горненра

Схема Горнера

Схема Горнера (или правило Горнера, метод Горнера) — алгоритм вычисления значения многочлена, записанного в виде суммы мономов, при заданном значении переменной. Метод Горнера позволяет найти корни многочлена, а также вычислить производные полинома в заданной точке. Схема Горнера также является простым алгоритмом для деления многочлена на бином вида x − c. Метод назван в честь Уильям Джорджа Горнера (англ.).

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

Описание алгоритма Задан многочлен P(x): Пусть требуется вычислить значение данного многочлена при фиксированном значении x = x0. Представим многочлен P(x) в следующем виде:

Определим следующую последовательность: … … Искомое значение P(x0) = b0. Покажем, что это так. В полученную форму записи P(x) подставим x = x0 и будем вычислять значение выражения, начиная со внутренних скобок. Для этого будем заменять подвыражения через bi:

Использование схемы Горнера для деления многочлена на бином При делении многочлена на x − c получается многочлен с остатком bn. При этом коэффициенты результирующего многочлена удовлетворяют рекуррентным соотношениям: b0 = a0, bk = ak + cbk − 1. Таким же образом можно определить кратность корня (использовать схему Горнера для нового полинома). Так же схему можно использовать для нахождения коэффициентов при разложении полинома по степеням x - c: