Статья: Вычисление многочленов от Ньютона до наших дней

Ну, начнём! Когда мы доберёмся до конца этой истории, будем знать больше, чем теперь.

Г. X. Андерсен

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

Многочлены, действительно, предельно просты: алгебраическая запись

f (x) = xn + a1xn–1 + a2xn–2 + ... + an–1x + an (1)

является одновременно и формулой для вычисления значений многочлена 1. Хотя выражения типа cos x, 5√ x , 10x, log 2 x намного лаконичнее, с вычислительной точки зрения они бессодержательны: для вычисления, скажем чисел cos 17°, 5√ 2 , 100,13 или log 2 7 нужны специальные приближённые формулы (или таблицы, составленные с помощью тех же формул). Как правило, в таких формулах появляются многочлены: например,

cos x  1 –

Возможно вы искали - Реферат: Знакочередующиеся и знакопеременные ряды

x2

2!

+

x4

4!

x6

Похожий материал - Лабораторная работа: Методы интегрирования

6!

+

x8

8!

(ошибка в интервале 0≤x≤π/4 меньше одной десятимиллионной!).

А ведь тригонометрические, степенные и т.п. (элементарные) функции — это самые простые из функций анализа, изучаемых и используемых математиками, физиками, инженерами. Известный математик-вычислитель Р. В. Хемминг в своей книге «Численные методы» (М., «Наука», 1972) пишет: «Поскольку с многочленами легко обращаться, большая часть классического численного анализа основывается на приближении многочленами».

Очень интересно - Реферат: Что такое орбита

Так как вычислять многочлены приходится часто, то важно научиться делать это как можно проще. Мы расскажем об эволюции методов вычисления значений многочленов с момента зарождения (XVII век). Впрочем, слово «эволюция» здесь не вполне уместно: история этих методов — скорее очень длинный роман с интересной, но краткой завязкой, однообразным действием и неожиданной развязкой.

§2. Схема Горнера

По правде говоря, здесь возникает сомнение, или вернее вопрос, которого миновать нельзя, не поставив его и на него не ответив.

А. Данте. Пир (1303 г.)

Общепринятый сейчас способ вычисления многочленов восходит к Ньютону и называется схемой Горнера. Эта универсальная (то есть применимая к любому многочлену) схема предельно проста и изящна. Она получается из формулы (1) вынесением за скобки x всюду, где это возможно:

f (x) = (...(((x + a1)·x + a2)·x + a3)...)·x + an. (2)

Порядок действии при вычислении f (x) определяется скобками в (2): сначала сложение внутри самой внутренней пары скобок (его результат обозначим через p1), затем умножение и сложение внутри следующей пары скобок (результат p2) и т.д.:

Вам будет интересно - Реферат: Возникновение измерений в древности

p1 = x + a1;

p2 = p1x + a2;

Похожий материал - Реферат: Движение в центральном симметричном поле

p3 = p2x + a3;

· · · · · · · · · · · · · · · · · ·

К-во Просмотров: 108
Бесплатно скачать Статья: Вычисление многочленов от Ньютона до наших дней