Инструменты пользователя

Инструменты сайта


Боковая панель

Регистрация

Учебные курсы

Учебные проекты

Материалы к экзаменам

Полезная информация

Обратная связь

others:sxema_gornera

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

Разделить с остатком многочлен f(x) на ненулевой многочлен g(x) - это значит представить f(x) в виде f(x) = g(x)s(x) + r(x), где s(x) и r(x) - многочлены и либо r(x)=0, либо ст. r(x) < ст. g(x).
S(x) назовем неполным частным, а r(x) - остатком при делении f(x) на g(x).
Неполное частное при делении можно найти с помощью простого правила, называемого схемой Горнера, которое, кстати, позволяет найти и остаток.

Пусть f(x) = anxn + an-1xn-1 + … + a1x + a0, an≠0 - многочлен n-й степени. При делении его на (x - c) мы получим неполное частное s(x) и остаток r, т.е. f(x) = (x - c)s(x) + r.
Так как ст. f(x) = n, а ст. (x - c) = 1, то ст. s(x) = n - 1, т.е. s(x) = bn-1xn-1 + bn-2xn-2 + … + b1x + b0, bn-1 ≠ 0.
Таким обрзом, имеем равенство:

anxn + an-1xn-1 + … + a1x + a0 = (x - c)(bn-1xn-1 + bn-2xn-2 + … + b1x + b0) + r.

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

a = bn-1, an-1 = bn-2 - cbn-1, an-2 = bn-3 - cbn-2,
a2 = b1 - cb2, a1 = b0 - cb1, a0 = r - cb0
.

Напомним, что требуется найти неполное частное, т.е. его коэффициенты, и остаток.
Выразим их из полученных равенств:
bn-1 = an,
bn-2 = cbn-1 + an-1, bn-3 = cbn-2 + an-2,
b1 = cb2 + a2, b0 = cb1 + a1, r = cb0 + a0
.
Мы нашли формулы, по которым можно вычислять коэффициенты неполного частного s(x) и остаток r.

Литература
Ананий В. Левитин. Алгоритмы: введение в разработку и анализ — М.: «Вильямс», 2006.
Волков Е. А. Численные методы. — Учеб. пособие для вузов. — 2-е изд., испр. — М.: Наука, 1987.

others/sxema_gornera.txt · Последние изменения: 2014/11/27 09:07 (внешнее изменение)