Алгебра · объяснение и практика

Как схема Горнера сокращает вычисление значения многочлена

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

Неизвестное x показывает найденное значение — пять.

В теме Многочлены: деление и корни · Учебная карта

Главная мысль

Многочлен 2x³−3x²+5 можно записать как ((2x−3)x+0)x+5. При x = 2 последовательные накопленные значения равны 2,1,2,9. Последнее число и есть значение многочлена. Такая схема использует коэффициенты по порядку степеней и не требует отдельно вычислять каждый куб или квадрат.

Как раскрывается вложенная форма

Сначала вынесем x из всех членов, кроме свободного:2x³−3x²+0x+5 = (2x²−3x+0)x+5. Внутри повторим вынесение:2x²−3x = (2x−3)x. Получилась вложенная форма ((2x−3)x+0)x+5. Обратное раскрытие восстанавливает исходный многочлен, поэтому при точной арифметике значения совпадают для любого x.

Нулевая запись при x нужна не ради изменения выражения. Она сохраняет место отсутствующего коэффициента. В цепочке 2, −3,0,5 третья позиция соответствует первой степени. Если пропустить ноль и выполнять те же действия над 2, −3,5, получится другой многочлен меньшей степени. Перечень коэффициентов должен включать все позиции от старшей степени до постоянной.

Как проследить накопитель на одном аргументе

Для x = 2 начинаем со старшего коэффициента 2. Умножаем на аргумент и прибавляем следующий коэффициент:2·2−3 = 1. Снова умножаем и прибавляем ноль:1·2+0 = 2. Последний шаг 2·2+5 = 9. Прямое вычисление 2·8−3·4+5 также даёт 9. Два разных представления позволяют проверить порядок коэффициентов и знаки.

На каждом шаге накопитель хранит значение уже обработанной старшей части в соответствующей вложенной записи. Следующий коэффициент нельзя прибавить до умножения, если алгоритм предполагает обратный порядок. Например, (2−3)·2 не равно 2·2−3. Явная короткая таблица накопителя помогает увидеть такую перестановку действий.

Пример

Вычислите x³−2x+4 при x = 3 по коэффициентам 1,0, −2,4.

Начинаем с 1. Затем 1·3+0 = 3, далее 3·3−2 = 7, наконец 7·3+4 = 25. Прямой счёт 27−6+4 подтверждает 25. Нулевой коэффициент при x² сохранён.

Что схема даёт и чего не обещает

Для многочлена степени n стандартная цепочка требует n умножений и n прибавлений после выбора первого коэффициента. Это арифметический счёт операций, а не обещание времени исполнения на любом устройстве. Реальные затраты зависят от представления чисел, языка и размера входа. Если значения целые или рациональные и арифметика точна, алгебраическое равенство сохраняется буквально.

При вычислениях с ограниченной точностью разные равные формы могут округляться немного по-разному. Схема Горнера сама не является доказательством отсутствия погрешности. Она также связана с синтетическим делением на x−r: последний накопитель при аргументе r даёт остаток P(r). Но задача вычисления одного значения и задача восстановления всего частного различаются. В ответе назовите, что было получено, и проверьте хотя бы один удобный аргумент независимым раскрытым способом.

От чтения к действию

А теперь — вы

Для P(x) = 2x²+0x+1 при x = 2 накопитель идёт 2 → 4 → … Каково последнее значение?

Частые вопросы

Почему нельзя пропускать нулевой коэффициент?

Алгоритм связывает каждую позицию с очередной степенью. Пропуск сдвинет все последующие коэффициенты и изменит вычисляемый многочлен.

Последний накопитель всегда является корнем уравнения?

Нет. Он является значением P(r) при выбранном аргументе r. Если это значение нулевое, тогда сам аргумент r — корень.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться