В математике и информатике , метод Хорнера (или схема Горнера ) представляет собой алгоритм для вычисления полиномов . Хотя этот метод назван в честь Уильяма Джорджа Хорнера , он намного старше, так как сам Хорнер приписал его Жозефу-Луи Лагранжу , и его можно проследить много сотен лет назад до китайских и персидских математиков. [1] После появления компьютеров этот алгоритм стал фундаментальным для эффективных вычислений с полиномами.
Алгоритм основан на правиле Хорнера:
Это позволяет вычислить многочлен степени n только с умножения и дополнения. Это оптимально, поскольку существуют многочлены степени n, которые нельзя вычислить с помощью меньшего количества арифметических операций [2]
В качестве альтернативы, метод Хорнера также относится к методу аппроксимации корней многочленов, описанному Хорнером в 1819 году. Это вариант метода Ньютона – Рафсона, более эффективный для ручных вычислений с применением правила Хорнера. Он широко использовался, пока компьютеры не стали широко использоваться примерно в 1970 году.
Полиномиальное вычисление и деление в столбик
Учитывая многочлен
где являются постоянными коэффициентами, задача состоит в том, чтобы оценить многочлен при определенном значении из
Для этого новая последовательность констант определяется рекурсивно следующим образом:
потом ценность .
Чтобы понять, почему это работает, многочлен можно записать в виде
Таким образом, итеративно подставляя в выражение,
Теперь можно доказать, что;
Это выражение представляет собой практическое применение Хорнера, поскольку оно предлагает очень быстрый способ определения результата;
где b 0 (который равен p (x 0 )) является остатком от деления, как показано в приведенных ниже примерах. если x 0 является корнем p (x), то b 0 = 0 (что означает, что остаток равен 0), что означает, что вы можете разложить p (x) на (xx 0 ).
Что касается поиска последовательных значений b, вы начинаете с определения b n , которое просто равно a n . Затем вы переходите к другим буквам «Б», используя формулу;
пока не дойдете до точки b 0 .
Примеры
Оценивать для
Мы используем синтетическое деление следующим образом:
х 0 │ х 3 х 2 х 1 х 0 3 │ 2 −6 2 −1 │ 6 0 6 └───────────────────────── 2 0 2 5
Записи в третьей строке представляют собой сумму записей в первых двух. Каждая запись во второй строке является произведением значения x (3 в этом примере) на запись в третьей строке слева. Записи в первой строке - это коэффициенты многочлена, который нужно оценить. Тогда оставшаяся часть по разделению на 5.
Но по теореме о полиномиальном остатке мы знаем, что остаток равен. Таким образом
В этом примере, если мы видим, что , записи в третьей строке. Итак, синтетическое деление основано на методе Хорнера.
Как следствие теоремы о полиномиальном остатке, элементы в третьей строке являются коэффициентами многочлена второй степени, частного от по разделению на . Остаток равен 5. Это делает метод Хорнера полезным для полиномиального деления в столбик .
Делить от :
2 │ 1 −6 11 −6 │ 2 −8 6 └───────────────────────── 1 −4 3 0
Частное .
Позволять а также . Делить от по методу Хорнера.
0,5 │ 4-6 0 3-5 │ 2 -2 -1 1└──────────────────────── 2 -2 -1 1-2
Третья строка представляет собой сумму первых двух строк, деленную на 2. Каждая запись во второй строке является произведением 1 с записью третьей строки слева. Ответ
Эффективность
Вычисление с использованием мономиальной формы многочлена степени n требует не более n сложений и ( n 2 + n ) / 2 умножений, если степени вычисляются путем повторного умножения и каждый моном оценивается индивидуально. (Это можно уменьшить до n сложений и 2 n - 1 умножений, итеративно оценивая степени x .) Если числовые данные представлены в виде цифр (или битов), то наивный алгоритм также влечет за собой сохранение примерно 2 n- кратного числа бит x (вычисленный многочлен имеет приблизительную величину x n , и нужно также сохранить сам x n ). В отличие от этого, метод Хорнера требует только n сложений и n умножений, а его требования к памяти всего в n раз больше числа битов x . В качестве альтернативы метод Хорнера может быть вычислен с n объединенными операциями умножения и сложения . Метод Хорнера также может быть расширен для вычисления первых k производных многочлена с помощью kn сложений и умножений. [3]
Метод Хорнера оптимален в том смысле, что любой алгоритм для вычисления произвольного многочлена должен использовать по крайней мере столько же операций. Александр Островский доказал в 1954 году, что количество необходимых дополнений минимально. [4] Виктор Пан доказал в 1966 году, что количество умножений минимально. [5] Однако, когда x является матрицей, метод Хорнера не является оптимальным .
Это предполагает, что многочлен оценивается в мономиальной форме, и предварительное кондиционирование представления не допускается, что имеет смысл, если многочлен оценивается только один раз. Однако, если предварительное кондиционирование разрешено и многочлен должен оцениваться много раз, тогда возможны более быстрые алгоритмы . Они включают преобразование представления многочлена. В общем, полином степени n можно вычислить, используя только ⌊ n / 2⌋ + 2 умножения и n сложений. [6]
Параллельная оценка
Недостатком правила Хорнера является то, что все операции последовательно зависимы , поэтому на современных компьютерах невозможно использовать преимущества параллелизма на уровне команд . В большинстве приложений, где важна эффективность оценки полиномов, многие полиномы низкого порядка оцениваются одновременно (для каждого пикселя или многоугольника в компьютерной графике или для каждого квадрата сетки в численном моделировании), поэтому нет необходимости находить параллелизм в пределах одинарная полиномиальная оценка.
Если, однако, вычисляется один полином очень высокого порядка, может быть полезно разбить его следующим образом:
В более общем виде суммирование можно разбить на k частей:
где внутренние суммирования могут быть оценены с использованием отдельных параллельных экземпляров метода Хорнера. Это требует немного большего количества операций, чем базовый метод Хорнера, но позволяет выполнять большинство из них k- way SIMD . Современные компиляторы обычно оценивают полиномы таким образом, когда это выгодно, хотя для вычислений с плавающей запятой это требует включения (небезопасной) реассоциативной математики.
Применение к умножению и делению с плавающей запятой
Метод Хорнера - это быстрый и эффективный с точки зрения кода метод умножения и деления двоичных чисел на микроконтроллере без аппаратного умножителя . Одно из умножаемых двоичных чисел представляется как тривиальный многочлен, где (с использованием обозначений выше), а также . Затем x (или x в некоторой степени) многократно выносится за скобки. В этой двоичной системе счисления (основание 2),, поэтому степени двойки многократно выносятся за скобки.
Пример
Например, чтобы найти произведение двух чисел (0,15625) и m :
Метод
Чтобы найти произведение двух двоичных чисел d и m :
- 1. Регистр, содержащий промежуточный результат, инициализируется как d .
- 2. Начните с наименее значащего (крайнего правого) ненулевого бита в m .
- 2b. Подсчитайте (слева) количество битовых позиций до следующего старшего значащего ненулевого бита. Если нет более значимых битов, то берется значение текущей битовой позиции.
- 2c. Используя это значение, выполните операцию сдвига влево на это количество битов в регистре, содержащем промежуточный результат.
- 3. Если были подсчитаны все ненулевые биты, то регистр промежуточных результатов теперь содержит окончательный результат. В противном случае добавьте d к промежуточному результату и перейдите к шагу 2 со следующим наиболее значимым битом в m .
Вывод
В общем случае для двоичного числа с битовыми значениями () продукт
На этом этапе алгоритма требуется, чтобы члены с нулевыми коэффициентами были отброшены, чтобы учитывались только двоичные коэффициенты, равные единице, поэтому проблема умножения или деления на ноль не является проблемой, несмотря на это значение в факторизованное уравнение:
Все знаменатели равны единице (или член отсутствует), поэтому это сводится к
или эквивалентным образом (в соответствии с "методом", описанным выше)
В двоичной математике (основание 2) умножение на степень 2 - это просто операция сдвига регистра . Таким образом, умножение на 2 вычисляется по основанию 2 арифметическим сдвигом . Фактор (2 -1 ) - это арифметический сдвиг вправо , a (0) не приводит к операции (поскольку 2 0 = 1 является мультипликативным тождественным элементом ), а (2 1 ) приводит к арифметическому сдвигу влево. Теперь произведение умножения можно быстро вычислить, используя только операции арифметического сдвига, сложения и вычитания.
Этот метод особенно быстр на процессорах, поддерживающих сдвиг-сложение-накопление с одной инструкцией. По сравнению с библиотекой C с плавающей запятой, метод Хорнера жертвует некоторой точностью, однако он номинально в 13 раз быстрее (в 16 раз быстрее, когда используется форма « канонической подписанной цифры » (CSD)) и использует только 20% пространства кода. [7]
Другие приложения
Метод Хорнера можно использовать для преобразования между различными позиционными системами счисления - и в этом случае x является основанием системы счисления, а коэффициенты a i - это цифры представления данного числа по основанию x. x - матрица , и в этом случае выигрыш в вычислительной эффективности еще больше. Однако для таких случаев известны более быстрые методы . [8]
Нахождение полиномиального корня
Используя алгоритм деления в длину в сочетании с методом Ньютона , можно аппроксимировать действительные корни многочлена. Алгоритм работает следующим образом. Учитывая многочлен степени с нулями сделать какое-то первоначальное предположение такой, что . Теперь повторите следующие два шага:
- Используя метод Ньютона , найдите наибольший ноль из используя догадку .
- Используя метод Хорнера, разделите чтобы получить . Вернитесь к шагу 1, но используйте полином и первоначальное предположение .
Эти два шага повторяются до тех пор, пока для полинома не будут найдены все действительные нули. Если приближенные нули недостаточно точны, полученные значения можно использовать в качестве начальных предположений для метода Ньютона, но с использованием полного полинома, а не сокращенных полиномов. [9]
Пример
Рассмотрим многочлен
который может быть расширен до
Из вышеизложенного мы знаем, что наибольший корень этого многочлена равен 7, поэтому мы можем сделать начальное предположение о 8. Используя метод Ньютона, первый нуль из 7 находится, как показано черным на рисунке справа. Следующий делится на чтобы получить
который показан красным на рисунке справа. Метод Ньютона используется для нахождения наибольшего нуля этого многочлена с начальным предположением 7. Наибольший ноль этого многочлена, который соответствует второму по величине нулю исходного многочлена, находится в точке 3 и обведен красным. Теперь полином пятой степени делится на чтобы получить
который показан желтым цветом. Нуль для этого многочлена снова находится в 2 с помощью метода Ньютона и обведен желтым кружком. Метод Хорнера теперь используется для получения
который показан зеленым и имеет ноль при −3. Далее этот многочлен сводится к
который показан синим цветом и дает ноль -5. Конечный корень исходного многочлена может быть найден либо с использованием конечного нуля в качестве начального предположения для метода Ньютона, либо путем сокращенияи решение линейного уравнения. Как видно, были найдены ожидаемые корни из −8, −5, −3, 2, 3 и 7.
Разделенная разность полинома
Метод Хорнера можно модифицировать для вычисления разделенной разницы. Учитывая многочлен (как и раньше)
действуйте следующим образом [10]
По завершении у нас есть
Это вычисление разделенной разницы подвержено меньшей ошибке округления, чем оценка а также отдельно, особенно когда . Подстановка в этом методе дает , производная от .
История
Статья Хорнера, озаглавленная «Новый метод решения числовых уравнений всех порядков с помощью непрерывного приближения» [12], была зачитана Лондонским королевским обществом на его собрании 1 июля 1819 года с продолжением в 1823 году [12]. ] Статья Хорнера во второй части « Философских трудов Лондонского королевского общества» за 1819 год была тепло и широко встречена рецензентом [ постоянная мертвая ссылка ] в выпуске «Ежемесячного обзора» или «Литературного журнала» за апрель 1820 года; для сравнения, техническая статья Чарльза Бэббиджа в данном обзоре вкратце отклоняется. Последовательность обзоров в «Ежемесячном обзоре» за сентябрь 1821 г. приводит к выводу, что Холдред был первым человеком, открывшим прямое и общее практическое решение числовых уравнений. Фуллер [13] показал, что метод, описанный в статье Хорнера 1819 г., отличается от того, что впоследствии стало известно как «метод Хорнера», и, следовательно, приоритет этого метода должен быть отдан Холдреду (1820 г.).
В отличие от своих английских современников, Хорнер опирался на континентальную литературу, особенно на работы Арбогаста . Также известно, что Хорнер внимательно прочитал книгу Джона Бонникасла по алгебре, хотя и пренебрегал работой Паоло Руффини .
Хотя Хорнеру приписывают создание доступного и практичного метода, он был известен задолго до Хорнера. В обратном хронологическом порядке метод Хорнера уже был известен:
- Паоло Руффини в 1809 году (см . Правило Руффини ) [14] [15]
- Исаак Ньютон в 1669 году [16] [17]
- китайский математик Чжу Шицзе в 14 веке [15]
- китайский математик Цинь Цзюшао в своем математическом трактате в девяти разделах в 13 веке
- персидский математик Шарафуддин ат-Туси в 12 - м веке (первый использовать этот метод в общем случае кубического уравнения) [18]
- китайский математик Цзя Сянь в XI веке ( династия Сун )
- Девять глав по математическому искусству , китайская работа времен династии Хань (202 г. до н.э. - 220 г. н.э.) под редакцией Лю Хуэя (fl. 3 век). [19]
Цинь Цзюшао в своей книге « Шу Шу Цзю Чжан» (« Математический трактат в девяти разделах» , 1247 г.) представляет портфель методов типа Хорнера для решения полиномиальных уравнений, основанный на более ранних работах математика из династии Сун XI века Цзя Сяня ; например, один метод особенно подходит для биквинтиков, пример которого Цинь приводит в соответствии с тогдашней китайской традицией изучения конкретных случаев. Йошио Миками в книге « Развитие математики в Китае и Японии» (Лейпциг, 1913 г.) писал:
"... кто может отрицать факт использования выдающегося процесса Хорнера в Китае, по крайней мере, почти на шесть долгих веков раньше, чем в Европе ... Мы, конечно, никоим образом не собираемся приписывать изобретение Хорнера китайскому происхождению, но время, достаточное для того, чтобы сделать то, что европейцы могли знать о китайском методе прямо или косвенно, не совсем невозможно ». [20]
Ульрих Либбрехт заключил: « Очевидно, что эта процедура - китайское изобретение ... этот метод не был известен в Индии . Он сказал, что Фибоначчи, вероятно, узнал об этом от арабов, которые, возможно, позаимствовали у китайцев. [21] Извлечение квадратных и кубических корней по аналогичным принципам уже обсуждалось Лю Хуэем в связи с проблемами IV.16 и 22 в Цзю Чжан Суан Шу , в то время как Ван Сяотун в 7 веке полагает, что его читатели могут решать кубики с помощью приближения Метод описан в его книге Jigu Suanjing .
Смотрите также
- Алгоритм Кленшоу для вычисления многочленов в форме Чебышева
- Алгоритм Де Бура для оценки сплайнов в форме B-сплайнов
- Алгоритм де Кастельжау для вычисления многочленов в форме Безье
- Схема Эстрина для облегчения распараллеливания на современных компьютерных архитектурах
- Метод Лилля для графической аппроксимации корней
- Правило Руффини и синтетическое деление для деления полинома на бином вида x - r
Заметки
- ^ 600 лет назад китайским математиком Цинь Цзюшао и 700 лет назад персидским математиком Шарафом ад-Дином аль-Хуси
- ^ Пан 1966 .
- ^ Панкевич 1968 .
- Перейти ↑ Ostrowski 1954 .
- ^ Пан 1966 .
- ^ Кнут 1997 .
- ^ Kripasagar 2008 , стр. 62.
- ^ Higham 2002 , раздел 5.4.
- Перейти ↑ Kress 1991 , p. 112.
- ^ Fateman & Каган 2000
- ^ Либбрехт 2005 , стр. 181-191.
- ^ а б Хорнер 1819 .
- ^ Fuller 1999 , стр. 29-51.
- ^ Cajori 1911 .
- ^ а б О'Коннор, Джон Дж .; Робертсон, Эдмунд Ф. , "Метод Хорнера" , Архив истории математики MacTutor , Университет Сент-Эндрюс
- ^ Анализ Per Quantitatum Series, Fluctiones ac Differentias: Cum Enumeratione Linearum Tertii Ordinis, Londini. Ex Officina Pearsoniana. Anno MDCCXI, стр. 10, 4 абзац.
- ↑ Сборник статей Ньютона, издание 1779 г., в сноске, т. I, стр. 270-271
- Перейти ↑ Berggren 1990 , pp. 304–309.
- Перейти ↑ Temple 1986 , p. 142.
- ^ Миками 1913 , стр. 77
- ^ Либбрехт 2005 , стр. 208.
Рекомендации
- Берггрен, JL (1990). «Инновации и традиции в Муадалате Шараф ад-Дин ат-Туси». Журнал Американского восточного общества . 110 (2): 304–309. DOI : 10.2307 / 604533 . JSTOR 604533 .
- Кахори, Флориан (1911). «Метод приближения Хорнера, предвиденный Руффини» . Бюллетень Американского математического общества . 17 (8): 409–414. DOI : 10.1090 / s0002-9904-1911-02072-9 . Прочтите перед Юго-западной секцией Американского математического общества 26 ноября 1910 г.
- Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн 10.1016 / 0315-0860 (81) 90069-0, Клиффорд (2009). «Введение в алгоритмы» . Historia Mathematica (3-е изд.). MIT Press. 8 (3): 277–318. DOI : 10.1016 / 0315-0860 (81) 90069-0 .
- Fateman, RJ ; Кахан, В. (2000). Улучшение точных интегралов из систем символьной алгебры (PDF) (Отчет). ПАМ. Калифорнийский университет в Беркли: Центр чистой и прикладной математики. Архивировано из оригинального (PDF) 14 августа 2017 года . Проверено 17 мая 2018 .
- Фуллер, А.Т. (1999). «Хорнер против Холдреда: эпизод в истории корневых вычислений» . Historia Mathematica . 26 : 29–51. DOI : 10.1006 / hmat.1998.2214 .
- Хайэм, Николас (2002). Точность и устойчивость численных алгоритмов . СИАМ. ISBN 978-0-89871-521-7.
- Холдред, Т. (1820). Новый метод решения уравнений с легкостью и быстротой; по которому истинное значение неизвестного количества находится без предварительного уменьшения. С дополнением, содержащим два других метода решения уравнений, основанных на том же принципе (PDF) . Ричард Уоттс. Архивировано из оригинального (PDF) 06.01.2014 . Проверено 10 декабря 2012 .
- Метод Холдреда приведен в приложении на следующей странице под номером 45 (это 52-я страница версии в формате pdf).
- Хорнер, Уильям Джордж (июль 1819 г.). «Новый метод решения числовых уравнений всех порядков непрерывным приближением» (PDF) . Философские труды . Лондонское королевское общество. 109 : 308–335. DOI : 10,1098 / rstl.1819.0023 . JSTOR 107508 . S2CID 186210512 . Архивировано из оригинального (PDF) 28 марта 2017 года . Проверено 28 марта 2017 .
- Прямо доступно онлайн по ссылке, но также перепечатано с оценкой в DE Smith: A Source Book in Mathematics , McGraw-Hill, 1929; Отпечаток Dover, 2 тома, 1959.
- Кнут, Дональд (1997). Искусство программирования . Vol. 2: получисловые алгоритмы (3-е изд.). Эддисон-Уэсли. с. 486–488 в разделе 4.6.4. ISBN 978-0-201-89684-8.
|volume=
имеет дополнительный текст ( справка ) - Кресс, Райнер (1991). Численный анализ . Springer.
- Крипасагар, Венкат (март 2008 г.). «Эффективная микроматематика - методы умножения и деления для микроконтроллеров». Журнал Circuit Cellar (212).
- Либбрехт, Ульрих (2005). «Глава 13» . Китайская математика в тринадцатом веке (2-е изд.). Дувр. ISBN 978-0-486-44619-6. Архивировано из оригинала на 2017-06-06 . Проверено 23 августа 2016 .
- Миками, Йошио (1913). «Глава 11. Цинь Цзю-Шао» . Развитие математики в Китае и Японии (1-е изд.). Переиздание Chelsea Publishing Co. С. 74–77.
- Островский, Александр М. (1954). «О двух проблемах абстрактной алгебры, связанных с правилом Хорнера» . Исследования по математике и механике представлены Ричарду фон Мизесу . Академическая пресса. С. 40–48. ISBN 978-1-4832-3272-0.
- Пан, Ю. Я (1966). «О средствах вычисления значений многочленов». Русская математика. Обзоры . 21 : 105–136. DOI : 10,1070 / rm1966v021n01abeh004147 .
- Панкевич, В. (1968). «Алгоритм 337: вычисление многочлена и его производных значений по схеме Горнера». Коммуникации ACM . ACM. 11 (9): 633. DOI : 10,1145 / 364063,364089 . S2CID 52859619 .
- Шпигель, Мюррей Р. (1956). Очерк теории и проблем студенческой алгебры Шаума . Макгроу-Хилл.
- Темпл, Роберт (1986). Гений Китая: 3000 лет науки, открытий и изобретений . Саймон и Шустер. ISBN 978-0-671-62028-8.
- Whittaker, ET ; Робинсон, Г. (1924). Расчет наблюдений . Лондон: Блэки.
- Уайли, Александр (1897). «Заметки по науке китайской арифметики» . Китайские исследования . Шанхай. С. 159–194.
- Перепечатано из выпусков The North China Herald (1852 г.).
Внешние ссылки
- "Схема Хорнера" , Математическая энциклопедия , EMS Press , 2001 [1994]
- Цю Цзинь-Шао, Шу Шу Цзю Чжан (под ред. Цун Шу Цзи Чэн)
- Подробнее о приложении для поиска корней см. [1]