Вычисление многочленов — от Ньютона до наших дней
| Категория реферата: Рефераты по математике
| Теги реферата: реферат на тему здоровье, дипломная работа 2011
| Добавил(а) на сайт: Jejler.
Предыдущая страница реферата | 1 2 3 4 5 6 7 8 | Следующая страница реферата
Общепринятый сейчас способ вычисления многочленов восходит к Ньютону и называется схемой Горнера. Эта универсальная (то есть применимая к любому многочлену) схема предельно проста и изящна. Она получается из формулы (1) вынесением за скобки x всюду, где это возможно:
|
f(x) = (...(((x + a1)·x + a2)·x + a3)...)·x + an. |
(2) |
Порядок действии при вычислении f(x) определяется скобками в (2): сначала сложение внутри самой внутренней пары скобок (его результат обозначим через p1), затем умножение и сложение внутри следующей пары скобок (результат p2) и т.д.:
|
(3) |
всего n–1 умножений и n сложений2 .
Схема Горнера настолько совершенна, что вопрос о возможности её улучшения не возникал два с половиной века и был задан «вслух» впервые лишь в 1954году! Постановка этого вопроса (ответ на него предполагался отрицательным) имела важные и неожиданные последствия.
§3. Индивидуальные схемы
— Вы позволите мне записать эту романтическую историю, сэр? — спросил потрясенный мистер Снодграсс.
— Сколько угодно, сэр, сколько угодно, ещё пятьдесят таких, если они вам по вкусу.
Ч. Диккенс
Уже в курсе школьной алгебры мы встречаемся с примерами многочленов, для которых существуют необычайно экономные схемы; единственный их недостаток — они не универсальны.
Сравнивая разные схемы по числу операций, мы будем объединять операции сложения и вычитания в группу «(+,–)-операций», а гораздо более трудоёмкие операции умножения и деления — в группу «(×,:)-операций».3
Примеры.
(а) Многочлен f(x) = x2^k можно вычислить за k умножений (а не за 2k по Горнеру):
|
p1 = x·x = x2, Рекомендуем скачать другие рефераты по теме: тесты для девочек, анализ темы курсовой работы. Категории:Предыдущая страница реферата | 1 2 3 4 5 6 7 8 | Следующая страница реферата Поделитесь этой записью или добавьте в закладки |
|
Главная