Метод Хорнерса - Horners method
Эта статья может требовать уборка встретиться с Википедией стандарты качества. Конкретная проблема: Видеть Обсуждение: метод Хорнера # Эта статья о двух разных алгоритмахНоябрь 2018) (Узнайте, как и когда удалить этот шаблон сообщения) ( |
В математика и Информатика, Метод Хорнера (или же Схема Хорнера) - алгоритм для полиномиальная оценка. Хотя назван в честь Уильям Джордж Хорнер, этот метод намного старше, так как его приписывают Жозеф-Луи Лагранж сам Хорнер, и его можно проследить много сотен лет назад до китайских и персидских математиков.[1] После появления компьютеров этот алгоритм стал основополагающим для эффективных вычислений с полиномами.
Алгоритм основан на Правило Хорнера:
Это позволяет оценить многочлен степени п только с умножения и дополнения. Это оптимально, поскольку существуют многочлены степени п которые нельзя оценить с помощью меньшего количества арифметических операций [2]
В качестве альтернативы, Метод Хорнера также относится к методу аппроксимации корней многочленов, описанному Хорнером в 1819 году. Это вариант метода Метод Ньютона – Рафсона стал более эффективным для ручного расчета за счет применения правила Хорнера. Он широко использовался, пока компьютеры не стали широко использоваться примерно в 1970 году.
Полиномиальное вычисление и деление в столбик
Учитывая многочлен
куда являются постоянными коэффициентами, задача состоит в том, чтобы оценить многочлен при конкретном значении из
Для этого определяется новая последовательность констант рекурсивно следующее:
потом это ценность .
Чтобы понять, почему это работает, многочлен можно записать в виде
Таким образом, итеративно подставляя в выражение,
Теперь можно доказать, что;
Это выражение представляет собой практическое применение Хорнера, поскольку оно предлагает очень быстрый способ определения результата;
с б0 (что равно p (x0)) является остатком от деления, как показано в примерах ниже. если х0 является корнем p (x), то b0 = 0 (означает, что остаток равен 0), что означает, что вы можете разложить p (x) на (x-x0).
Что касается поиска последовательных значений b, вы начинаете с определения bп, что просто равно aп. Затем вы переходите к другим буквам «Б», используя формулу;
пока вы не дойдете до б0.
Примеры
Оценивать за
Мы используем синтетическое подразделение следующее:
Икс0│ Икс3 Икс2 Икс1 Икс0 3 │ 2 −6 2 −1 │ 6 0 6 └──────────────────────── 2 0 2 5
Записи в третьей строке представляют собой сумму записей в первых двух. Каждая запись во второй строке является продуктом Икс-value (в этом примере 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 с записью третьей строки слева. Ответ
Эффективность
Оценка с использованием мономиальной формы степени -п полином требует не более п дополнения и (п2 + п) / 2 умножения, если мощности вычисляются путем повторного умножения и каждый одночлен оценивается индивидуально. (Это можно свести к п дополнения и 2п - 1 умножение путем оценки степеней Икс итеративно.) Если числовые данные представлены в виде цифр (или битов), тогда наивный алгоритм также предполагает сохранение примерно 2п умноженное на количество битов Икс (оцененный многочлен имеет приблизительную величину Иксп, и нужно также хранить Иксп сам). Напротив, метод Хорнера требует только п дополнения и п умножения, и его требования к хранению только п умноженное на количество битов Икс. В качестве альтернативы метод Хорнера можно вычислить с помощью п плавленый умножить - складывает. Метод Хорнера также можно расширить для оценки первого k производные полинома с кн сложения и умножения.[3]
Метод Хорнера оптимален в том смысле, что любой алгоритм для вычисления произвольного многочлена должен использовать по крайней мере столько же операций. Александр Островский в 1954 г. доказал, что количество требуемых дополнений минимально.[4] Виктор Пан в 1966 году доказал, что число умножений минимально.[5] Однако когда Икс - матрица, метод Горнера не оптимален.[нужна цитата ]
Это предполагает, что полином вычисляется в мономиальной форме и нет предварительная подготовка представления разрешено, что имеет смысл, если многочлен вычисляется только один раз. Однако, если предварительное кондиционирование разрешено и полином необходимо вычислять много раз, тогда возможны более быстрые алгоритмы. Они включают преобразование представления полинома. В общем, степень-п многочлен можно вычислить, используя только ⌊п/ 2⌋ + 2 умножения и п дополнения.[6]
Параллельная оценка
Недостатком правила Хорнера является то, что все операции последовательно зависимый, поэтому невозможно воспользоваться параллелизм на уровне инструкций на современных компьютерах. В большинстве приложений, где важна эффективность оценки полиномов, многие полиномы низкого порядка оцениваются одновременно (для каждого пикселя или многоугольника в компьютерной графике или для каждого квадрата сетки в численном моделировании), поэтому нет необходимости находить параллелизм в пределах одинарная полиномиальная оценка.
Если, однако, оценивается один полином очень высокого порядка, может быть полезно разбить его следующим образом:
В более общем смысле суммирование можно разбить на k части:
где внутренние суммирования могут быть оценены с использованием отдельных параллельных экземпляров метода Хорнера. Это требует немного большего количества операций, чем основной метод Хорнера, но позволяет k-путь SIMD исполнение большинства из них. Современные компиляторы обычно оценивают полиномы таким образом, когда это выгодно, хотя для плавающая точка для расчетов требуется разрешающая (небезопасная) реассоциативная математика.
Применение к умножению и делению с плавающей запятой
Метод Хорнера - это быстрый и эффективный с точки зрения кода метод умножения и деления двоичных чисел на микроконтроллер без аппаратный умножитель. Одно из двоичных чисел для умножения представляется как тривиальный многочлен, где (с использованием обозначений выше) , и . Потом, Икс (или же Икс до некоторой степени) неоднократно выносится за скобки. В этом двоичная система счисления (база 2), , поэтому степени двойки многократно выносятся за скобки.
Пример
Например, чтобы найти произведение двух чисел (0,15625) и м:
Метод
Чтобы найти произведение двух двоичных чисел d и м:
- 1. Регистр, содержащий промежуточный результат, инициализируется как d.
- 2. Начните с наименее значащего (крайнего правого) ненулевого бита в м.
- 2b. Подсчитайте (слева) количество битовых позиций до следующего старшего значащего ненулевого бита. Если нет более значимых битов, то берется значение текущей битовой позиции.
- 2c. Используя это значение, выполните операцию сдвига влево на это количество бит в регистре, содержащем промежуточный результат.
- 3. Если были подсчитаны все ненулевые биты, то регистр промежуточных результатов теперь содержит окончательный результат. В противном случае добавьте d к промежуточному результату и продолжите шаг 2 со следующим наиболее значимым битом в м.
Вывод
В общем, для двоичного числа с битовыми значениями () продукт
На этом этапе в алгоритме требуется, чтобы члены с нулевыми коэффициентами были отброшены, чтобы учитывались только двоичные коэффициенты, равные единице, таким образом, проблема умножения или деление на ноль не является проблемой, несмотря на это значение в факторизованном уравнении:
Все знаменатели равны единице (или член отсутствует), поэтому это сводится к
или эквивалентным образом (в соответствии с "методом", описанным выше)
В двоичной математике (основание 2) умножение на степень 2 - это просто сдвиг регистра операция. Таким образом, умножение на 2 вычисляется в базе 2 на арифметический сдвиг. Фактор (2−1) это право арифметический сдвиг, a (0) не приводит к операции (так как 20 = 1 - мультипликативный элемент идентичности ) и a (21) приводит к арифметическому сдвигу влево. Произведение умножения теперь можно быстро вычислить, используя только операции арифметического сдвига, сложения и вычитания.
Этот метод особенно быстр на процессорах, поддерживающих сдвиг-сложение-накопление одной инструкции. По сравнению с библиотекой C с плавающей запятой, метод Хорнера жертвует некоторой точностью, однако он номинально в 13 раз быстрее (в 16 раз быстрее, если "каноническая цифра со знаком (CSD)) и использует только 20% кодового пространства.[7]
Другие приложения
Метод Хорнера можно использовать для преобразования между разными позиционными системы счисления - в таком случае Икс является основанием системы счисления, а ая коэффициенты - это цифры основания-Икс представление данного числа - а также может использоваться, если Икс это матрица, и в этом случае выигрыш в вычислительной эффективности еще больше. Фактически, когда Икс является матрицей, возможно дальнейшее ускорение, использующее структуру матричное умножение, и только вместо п необходимо умножение (за счет увеличения объема памяти) с использованием метода Патерсона и Стокмейера 1973 года.[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 г. (но нужна точная ссылка)
- то Китайский математик Чжу Шицзе в 14 веке[15]
- то Китайский математик Цинь Цзюшао в его Математический трактат в девяти разделах в 13 веке
- то Персидский математик Шараф ад-Дин аль-Хуси в 12 веке (первый, кто использовал этот метод в общем случае кубического уравнения)[16]
- китайский математик Цзя Сянь в 11 веке (Династия Сун )
- Девять глав математического искусства, китайское произведение Династия Хан (202 г. до н.э. - 220 г. н.э.) под редакцией Лю Хуэй (эт. 3 век).[17]
Цинь Цзюшао, в его Шу Шу Цзю Чжан (Математический трактат в девяти разделах; 1247), представляет собой портфель методов типа Хорнера для решения полиномиальных уравнений, основанный на более ранних работах математика из династии Сун 11 века. Цзя Сянь; например, один метод особенно подходит для биквинтиков, пример которого Цинь приводит в соответствии с тогдашней китайской традицией изучения конкретных случаев. Ёсио Миками в Развитие математики в Китае и Японии (Лейпциг, 1913 г.) писал:
«... кто может отрицать тот факт, что выдающийся процесс Хорнера использовался в Китае, по крайней мере, почти на шесть долгих веков раньше, чем в Европе ... Мы, конечно, никоим образом не собираемся приписывать изобретение Хорнера китайскому происхождению, но время, достаточное для того, чтобы не исключить возможность того, что европейцы могли знать о китайском методе прямо или косвенно ».[18]
Ульрих Либбрехт заключил: Очевидно, что эта процедура - китайское изобретение ... метод не был известен в Индии.. Он сказал, что Фибоначчи, вероятно, узнал об этом от арабов, которые, возможно, позаимствовали у китайцев.[19] Извлечение квадратного и кубического корня по аналогичным направлениям уже обсуждалось Лю Хуэй в связи с задачами IV.16 и 22 в Цзю Чжан Суан Шу, пока Ван Сяотун в 7 веке предполагает, что его читатели могут решать кубики с помощью метода приближений, описанного в его книге Джигу Суаньцзин.
Смотрите также
- Алгоритм Кленшоу оценивать многочлены от Чебышевская форма
- Алгоритм де Бура оценить шлицы в B-шлиц форма
- Алгоритм де Кастельжау оценивать многочлены от Форма Безье
- Схема Эстрина для облегчения распараллеливания на современных компьютерных архитектурах
- Метод Лилля аппроксимировать корни графически
- Правило Руффини и синтетическое подразделение разделить многочлен на двучлен вида x - r
Примечания
- ^ 600 лет назад китайский математик Цинь Цзюшао и 700 лет назад персидским математиком Шараф ад-Дин аль-Хуси
- ^ Пан 1966.
- ^ Панкевич 1968.
- ^ Островский 1954.
- ^ Пан 1966.
- ^ Кнут 1997.
- ^ Крипасагар 2008, п. 62.
- ^ Хайэм 2002, Раздел 5.4.
- ^ Кресс 1991, п. 112.
- ^ Фейтман и Кахан 2000
- ^ Либбрехт 2005 С. 181–191.
- ^ а б Хорнер 1819.
- ^ Фуллер 1999 С. 29–51.
- ^ Кахори 1911.
- ^ а б О'Коннор, Джон Дж.; Робертсон, Эдмунд Ф., «Метод Хорнера», Архив истории математики MacTutor, Сент-Эндрюсский университет.
- ^ Берггрен 1990 С. 304–309.
- ^ Храм 1986, п. 142.
- ^ Миками 1913, п. 77
- ^ Либбрехт 2005, п. 208.
Рекомендации
- Берггрен, Дж. Л. (1990). «Инновации и традиции в Муадалате Шараф ад-Дин ат-Туси». Журнал Американского восточного общества. 110 (2): 304–309. Дои:10.2307/604533. JSTOR 604533.
- Кахори, Флориан (1911). «Аппроксимационный метод Хорнера, предвиденный Руффини». Бюллетень Американского математического общества. 17 (8): 409–414. Дои:10.1090 / с0002-9904-1911-02072-9. Прочтите перед Юго-западной секцией Американского математического общества 26 ноября 1910 г.
- Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн 10.1016 / 0315-0860 (81) 90069-0, Клиффорд (2009). «Введение в алгоритмы». Historia Mathematica (3-е изд.). MIT Press. 8 (3): 277–318. Дои:10.1016/0315-0860(81)90069-0.
- Фейтман, Р. Дж.; Кахан, В. (2000). Улучшение точных интегралов из систем символической алгебры (PDF) (Отчет). ПАМ. Калифорнийский университет в Беркли: Центр чистой и прикладной математики. Архивировано из оригинал (PDF) на 2017-08-14. Получено 2018-05-17.
- Фуллер, А. Т. (1999). «Хорнер против Холдреда: эпизод в истории корневых вычислений». Historia Mathematica. 26: 29–51. Дои:10.1006 / hmat.1998.2214.
- Хайэм, Николас (2002). Точность и стабильность численных алгоритмов.. СИАМ. ISBN 978-0-89871-521-7.
- Холдред, Т. (1820). Новый метод решения уравнений с легкостью и быстротой; по которому истинное значение неизвестного количества находится без предварительного уменьшения. С дополнением, содержащим два других метода решения уравнений, основанных на том же принципе (PDF). Ричард Уоттс. Архивировано из оригинал (PDF) на 2014-01-06. Получено 2012-12-10.
- Метод Холдреда приведен в приложении на следующей странице под номером 45 (это 52-я страница версии pdf).
- Хорнер, Уильям Джордж (Июль 1819 г.). «Новый метод решения числовых уравнений всех порядков непрерывным приближением» (PDF). Философские труды. Лондонское королевское общество. 109: 308–335. Дои:10.1098 / рстл.1819.0023. JSTOR 107508. Архивировано из оригинал (PDF) на 2017-03-28. Получено 2017-03-28.
- Прямо доступно онлайн по ссылке, но также перепечатано с оценкой в D.E. Смит: Справочник по математике, McGraw-Hill, 1929; Отпечаток Dover, 2 тома, 1959.
- Кнут, Дональд (1997). Искусство программирования. Vol. 2: получисловые алгоритмы (3-е изд.). Эддисон-Уэсли. с. 486–488 в разделе 4.6.4. ISBN 978-0-201-89684-8.
- Кресс, Райнер (1991). Числовой анализ. Springer.
- Крипасагар, Венкат (март 2008 г.). «Эффективная микроматематика - методы умножения и деления для микроконтроллеров». Журнал Circuit Cellar (212).
- Либбрехт, Ульрих (2005). «Глава 13». Китайская математика в XIII веке (2-е изд.). Дувр. ISBN 978-0-486-44619-6.
- Миками, Йошио (1913). «Глава 11. Цинь Цзю-Шао». Развитие математики в Китае и Японии (1-е изд.). Переиздание Chelsea Publishing Co. С. 74–77.
- Островский, Александр М. (1954). «О двух проблемах абстрактной алгебры, связанных с правилом Хорнера». Исследования по математике и механике, представленные Ричарду фон Мизесу. Академическая пресса. С. 40–48. ISBN 978-1-4832-3272-0.
- Пан, Ю. Я (1966). «О средствах вычисления значений многочленов». Русская математика. Обзоры. 21: 105–136. Дои:10.1070 / rm1966v021n01abeh004147.
- Панкевич, В. (1968). «Алгоритм 337: вычисление полинома и его производных значений по схеме Горнера». Коммуникации ACM. ACM. 11 (9): 633. Дои:10.1145/364063.364089.
- Шпигель, Мюррей Р. (1956). Очерк теории и проблем студенческой алгебры Шаума. Макгроу-Хилл.
- Темпл, Роберт (1986). Гений Китая: 3000 лет науки, открытий и изобретений. Саймон и Шустер. ISBN 978-0-671-62028-8.
- Уиттакер, E.T.; Робинсон, Г. (1924). Расчет наблюдений. Лондон: Блэки.
- Уайли, Александр (1897). «Заметки по науке китайской арифметики». Китайские исследования. Шанхай. С. 159–194.
- Перепечатано из выпусков Вестник Северного Китая (1852).
внешняя ссылка
- «Схема Хорнера», Энциклопедия математики, EMS Press, 2001 [1994]
- Цю Цзинь-Шао, Шу Шу Цзю Чжан (Под ред. Цун Шу Цзи Чэна)
- Подробнее о приложении для поиска корней см. [1]