Метод Хорнера - Horner's method

В математике и информатике , метод Хорнера (или схема Горнера ) представляет собой алгоритм для вычисления полиномов . Хотя этот метод назван в честь Уильяма Джорджа Хорнера , он намного старше, так как сам Хорнер приписал его Жозефу-Луи Лагранжу , и его можно проследить многие сотни лет назад до китайских и персидских математиков. После появления компьютеров этот алгоритм стал основополагающим для эффективных вычислений с полиномами.

Алгоритм основан на правиле Хорнера:

${\ displaystyle {\ begin {align} a_ {0} & + a_ {1} x + a_ {2} x ^ {2} + a_ {3} x ^ {3} + \ cdots + a_ {n} x ^ {n} \\ & = a_ {0} + x {\ bigg (} a_ {1} + x {\ Big (} a_ {2} + x {\ big (} a_ {3} + \ cdots + x ( a_ {n-1} + x \, a_ {n}) \ cdots {\ big)} {\ Big)} {\ bigg)}. \ end {align}}}$

Это позволяет вычислять полином степени n только умножениями и сложениями. Это оптимально, поскольку есть многочлены степени n, которые нельзя вычислить с помощью меньшего количества арифметических операций. ${\ displaystyle n}$${\ displaystyle n}$

В качестве альтернативы, метод Хорнера также относится к методу аппроксимации корней многочленов, описанному Хорнером в 1819 году. Это вариант метода Ньютона – Рафсона, более эффективный для ручных вычислений с применением правила Хорнера. Он широко использовался, пока компьютеры не стали широко использоваться примерно в 1970 году.

Полиномиальное вычисление и деление в столбик

Учитывая многочлен

${\ displaystyle p (x) = \ sum _ {i = 0} ^ {n} a_ {i} x ^ {i} = a_ {0} + a_ {1} x + a_ {2} x ^ {2} + a_ {3} x ^ {3} + \ cdots + a_ {n} x ^ {n},}$

где постоянные коэффициенты, проблема заключается в оценке полинома при определенном значении в${\ displaystyle a_ {0}, \ ldots, a_ {n}}$${\ displaystyle x_ {0}}$${\ displaystyle x.}$

Для этого новая последовательность констант определяется рекурсивно следующим образом:

${\ displaystyle {\ begin {align} b_ {n} &: = a_ {n} \\ b_ {n-1} &: = a_ {n-1} + b_ {n} x_ {0} \\ (1 ) \ quad \ quad \ quad & ~~~ \ vdots \\ b_ {1} &: = a_ {1} + b_ {2} x_ {0} \\ b_ {0} &: = a_ {0} + b_ {1} x_ {0}. \ End {выровнено}}}$

Тогда это значение . ${\ displaystyle b_ {0}}$${\ displaystyle p (x_ {0})}$

Чтобы понять, почему это работает, многочлен можно записать в виде

${\ Displaystyle p (x) = a_ {0} + x {\ bigg (} a_ {1} + x {\ Big (} a_ {2} + x {\ big (} a_ {3} + \ cdots + x) (a_ {n-1} + x \, a_ {n}) \ cdots {\ big)} {\ Big)} {\ bigg)} \.}$

Таким образом, итеративно подставляя в выражение, ${\ displaystyle b_ {i}}$

${\ displaystyle {\ begin {align} p (x_ {0}) & = a_ {0} + x_ {0} {\ Big (} a_ {1} + x_ {0} {\ big (} a_ {2}) + \ cdots + x_ {0} (a_ {n-1} + b_ {n} x_ {0}) \ cdots {\ big)} {\ Big)} \\ & = a_ {0} + x_ {0} {\ Big (} a_ {1} + x_ {0} {\ big (} a_ {2} + \ cdots + x_ {0} b_ {n-1} {\ big)} {\ Big)} \\ & ~~ \ vdots \\ & = a_ {0} + x_ {0} b_ {1} \\ & = b_ {0}. \ end {align}}}$

Теперь можно доказать, что;

${\ displaystyle (2) \ quad \ quad \ quad p (x) = (b_ {1} + b_ {2} x + b_ {3} x ^ {2} + b_ {4} x ^ {3} + \ cdots + b_ {n-1} x ^ {n-2} + b_ {n} x ^ {n-1}) (x-x_ {0}) + b_ {0}}$

Это выражение представляет собой практическое применение Хорнера, поскольку оно предлагает очень быстрый способ определения результата;

${\ Displaystyle р (х) / (х-х_ {0})}$

где b ₀ (который равен p (x ₀ )) является остатком от деления, как показано в приведенных ниже примерах. если x ₀ является корнем p (x), то b ₀ = 0 (то есть остаток равен 0), что означает, что вы можете разложить p (x) на (xx ₀ ).
Что касается поиска последовательных значений b, вы начинаете с определения b _n , которое просто равно a _n . Затем вы переходите к другим буквам «Б», используя формулу;

${\ displaystyle b_ {n-1} = a_ {n-1} + b_ {n} x_ {0}}$

пока не дойдете до точки b ₀ .

Примеры

Оценка для${\ displaystyle f (x) = 2x ^ {3} -6x ^ {2} + 2x-1}$${\ displaystyle x = 3.}$

Мы используем синтетическое деление следующим образом:

 x0│   x3    x2    x1    x0
 3 │   2    −6     2    −1
   │         6     0     6
   └────────────────────────
       2     0     2     5

Записи в третьей строке представляют собой сумму записей в первых двух. Каждая запись во второй строке является произведением значения x (3 в этом примере) на запись в третьей строке, находящуюся непосредственно слева. Записи в первой строке - это коэффициенты многочлена, который нужно оценить. Тогда остаток от деления на равен 5. ${\ displaystyle f (x)}$${\ displaystyle x-3}$

Но по теореме о полиномиальном остатке мы знаем, что остаток равен . Таким образом${\ displaystyle f (3)}$${\ Displaystyle f (3) = 5}$

В этом примере, если мы это видим , записи в третьей строке. Итак, синтетическое деление основано на методе Хорнера. ${\ displaystyle a_ {3} = 2, a_ {2} = - 6, a_ {1} = 2, a_ {0} = - 1}$${\ displaystyle b_ {3} = 2, b_ {2} = 0, b_ {1} = 2, b_ {0} = 5}$

Как следствие теоремы о полиномиальном остатке, элементы в третьей строке являются коэффициентами многочлена второй степени, частного от деления на . Остаток равен 5. Это делает метод Хорнера полезным для полиномиального деления в столбик . ${\ displaystyle f (x)}$${\ displaystyle x-3}$

Разделить на : ${\ displaystyle x ^ {3} -6x ^ {2} + 11x-6}$${\ displaystyle x-2}$

 2 │   1    −6    11    −6
   │         2    −8     6
   └────────────────────────
       1    −4     3     0

Частное равно . ${\ displaystyle x ^ {2} -4x + 3}$

Пусть и . Разделите по методу Хорнера. ${\ displaystyle f_ {1} (x) = 4x ^ {4} -6x ^ {3} + 3x-5}$${\ displaystyle f_ {2} (x) = 2x-1}$${\ displaystyle f_ {1} (х)}$${\ Displaystyle f_ {2} \, (х)}$

  0.5 │ 4  -6   0   3  -5
      │     2  -2  -1   1
└───────────────────────
        2  -2  -1   1  -2

Третья строка представляет собой сумму первых двух строк, деленную на 2. Каждая запись во второй строке является произведением 1 с записью третьей строки слева. Ответ

${\ displaystyle {\ frac {f_ {1} (x)} {f_ {2} (x)}} = 2x ^ {3} -2x ^ {2} -x + 1 - {\ frac {4} {2x -1}}.}$

Эффективность

Вычисление с использованием мономиальной формы многочлена степени n требует не более n сложений и ( n ²  +  n ) / 2 умножений, если степени вычисляются путем повторного умножения и каждый моном оценивается индивидуально. (Это можно уменьшить до n сложений и 2 n  - 1 умножений, итеративно оценивая степени x .) Если числовые данные представлены в виде цифр (или битов), то наивный алгоритм также влечет за собой сохранение примерно 2 n- кратного числа бит x (вычисленный многочлен имеет приблизительную величину x ⁿ , и нужно также сохранить сам x ⁿ ). В отличие от этого, метод Хорнера требует только n сложений и n умножений, а его требования к памяти всего в n раз больше числа битов x . В качестве альтернативы метод Хорнера может быть вычислен с n объединенными операциями умножения и сложения . Метод Хорнера также может быть расширен для вычисления первых k производных многочлена с помощью kn сложений и умножений.

Метод Хорнера оптимален в том смысле, что любой алгоритм для вычисления произвольного многочлена должен использовать по крайней мере столько же операций. Александр Островский доказал в 1954 году, что количество необходимых дополнений минимально. Виктор Пан доказал в 1966 году, что количество умножений минимально. Однако, когда x является матрицей, метод Хорнера не является оптимальным .

Это предполагает, что многочлен оценивается в мономиальной форме, и предварительное кондиционирование представления не допускается, что имеет смысл, если многочлен оценивается только один раз. Однако, если предварительное кондиционирование разрешено и многочлен должен оцениваться много раз, тогда возможны более быстрые алгоритмы . Они включают преобразование представления многочлена. В общем, полином степени n можно вычислить, используя только ⌊ n / 2 ⌋ +2 умножений и n сложений.

Параллельная оценка

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

Если, однако, вычисляется один полином очень высокого порядка, может быть полезно разбить его следующим образом:

${\ displaystyle {\ begin {align} p (x) & = \ sum _ {i = 0} ^ {n} a_ {i} x ^ {i} \\ & = a_ {0} + a_ {1} x + a_ {2} x ^ {2} + a_ {3} x ^ {3} + \ cdots + a_ {n} x ^ {n} \\ & = \ left (a_ {0} + a_ {2} x ^ {2} + a_ {4} x ^ {4} + \ cdots \ right) + \ left (a_ {1} x + a_ {3} x ^ {3} + a_ {5} x ^ {5} + \ cdots \ right) \\ & = \ left (a_ {0} + a_ {2} x ^ {2} + a_ {4} x ^ {4} + \ cdots \ right) + x \ left (a_ {1 } + a_ {3} x ^ {2} + a_ {5} x ^ {4} + \ cdots \ right) \\ & = \ sum _ {i = 0} ^ {\ lfloor n / 2 \ rfloor} a_ {2i} x ^ {2i} + x \ sum _ {i = 0} ^ {\ lfloor n / 2 \ rfloor} a_ {2i + 1} x ^ {2i} \\ & = p_ {0} (x ^ {2}) + xp_ {1} (x ^ {2}). \\\ конец {выровнено}}}$

В более общем виде суммирование можно разбить на k частей:

${\ displaystyle {\ begin {align} p (x) & = \ sum _ {i = 0} ^ {n} a_ {i} x ^ {i} \\ & = \ sum _ {j = 0} ^ { k-1} x ^ {j} \ sum _ {i = 0} ^ {\ lfloor n / k \ rfloor} a_ {ki + j} x ^ {ki} \\ & = \ sum _ {j = 0} ^ {k-1} x ^ {j} p_ {j} (x ^ {k}) \\\ конец {выровнено}}}$

где внутренние суммирования могут быть оценены с использованием отдельных параллельных экземпляров метода Хорнера. Это требует немного большего количества операций, чем базовый метод Хорнера, но позволяет выполнять большинство из них k- way SIMD . Современные компиляторы обычно оценивают полиномы таким образом, когда это выгодно, хотя для вычислений с плавающей запятой это требует включения (небезопасной) реассоциативной математики.

Применение к умножению и делению с плавающей запятой

Метод Хорнера - это быстрый и эффективный с точки зрения кода метод умножения и деления двоичных чисел на микроконтроллере без аппаратного умножителя . Одно из умножаемых двоичных чисел представляется в виде тривиального многочлена, где (с использованием обозначений выше) и . Затем x (или x в некоторой степени) многократно выносится за скобки. В этой двоичной системе счисления (основание 2) , поэтому степени двойки многократно вычитаются. ${\ displaystyle a_ {i} = 1}$${\ displaystyle x = 2}$${\ displaystyle x = 2}$

Пример

Например, чтобы найти произведение двух чисел (0,15625) и m :

${\ displaystyle {\ begin {align} (0,15625) m & = (0,00101_ {b}) m = (2 ^ {- 3} +2 ^ {- 5}) m = (2 ^ {- 3}) m + ( 2 ^ {- 5}) m \\ & = 2 ^ {- 3} (m + (2 ^ {- 2}) m) = 2 ^ {- 3} (m + 2 ^ {- 2} (m)) . \ end {выровнено}}}$

Метод

Чтобы найти произведение двух двоичных чисел d и m :

1. Регистр, содержащий промежуточный результат, инициализируется как d .

2. Начните с наименее значащего (крайнего правого) ненулевого бита в m .

2b. Подсчитайте (слева) количество битовых позиций до следующего старшего значащего ненулевого бита. Если нет более значимых битов, то берется значение текущей битовой позиции.

2c. Используя это значение, выполните операцию сдвига влево на это количество битов в регистре, содержащем промежуточный результат.

3. Если были подсчитаны все ненулевые биты, то регистр промежуточных результатов теперь содержит окончательный результат. В противном случае добавьте d к промежуточному результату и перейдите к шагу 2 со следующим наиболее значимым битом в m .

Вывод

В общем, для двоичного числа с битовыми значениями ( ) произведение равно ${\ displaystyle d_ {3} d_ {2} d_ {1} d_ {0}}$

${\ displaystyle (d_ {3} 2 ^ {3} + d_ {2} 2 ^ {2} + d_ {1} 2 ^ {1} + d_ {0} 2 ^ {0}) m = d_ {3} 2 ^ {3} m + d_ {2} 2 ^ {2} m + d_ {1} 2 ^ {1} m + d_ {0} 2 ^ {0} m.}$

На этом этапе алгоритма требуется, чтобы члены с нулевыми коэффициентами были отброшены, чтобы учитывались только двоичные коэффициенты, равные единице, поэтому проблема умножения или деления на ноль не является проблемой, несмотря на это значение в факторизованное уравнение:

${\ displaystyle = d_ {0} \ left (m + 2 {\ frac {d_ {1}} {d_ {0}}} \ left (m + 2 {\ frac {d_ {2}}} {d_ {1}) }} \ left (m + 2 {\ frac {d_ {3}} {d_ {2}}} (m) \ right) \ right) \ right).}$

Все знаменатели равны единице (или член отсутствует), поэтому это сводится к

${\ displaystyle = d_ {0} (m + 2 {d_ {1}} (m + 2 {d_ {2}} (m + 2 {d_ {3}} (m)))),}$

или эквивалентным образом (в соответствии с "методом", описанным выше)

${\ displaystyle = d_ {3} (m + 2 ^ {- 1} {d_ {2}} (m + 2 ^ {- 1} {d_ {1}} (m + {d_ {0}} (m)) )).}$

В двоичной математике (основание 2) умножение на степень 2 - это просто операция сдвига регистра . Таким образом, умножение на 2 вычисляется по основанию 2 арифметическим сдвигом . Фактор (2 ^-1 ) представляет собой арифметический сдвиг вправо , a (0) не приводит к операции (поскольку 2 ⁰ = 1 является мультипликативным тождественным элементом ), а (2 ¹ ) приводит к арифметическому сдвигу влево. Теперь произведение умножения можно быстро вычислить, используя только операции арифметического сдвига, сложения и вычитания.

Этот метод особенно быстр на процессорах, поддерживающих сдвиг-сложение-накопление одной инструкции. По сравнению с библиотекой C с плавающей запятой, метод Хорнера жертвует некоторой точностью, однако он номинально в 13 раз быстрее (в 16 раз быстрее, когда используется форма « канонической подписанной цифры » (CSD)) и использует только 20% пространства кода.

Другие приложения

Метод Хорнера может использоваться для преобразования между различными позиционными системами счисления - и в этом случае x является основанием системы счисления, а коэффициенты a _i - это цифры представления данного числа по основанию x. x - матрица , и в этом случае выигрыш в вычислительной эффективности еще больше. Однако для таких случаев известны более быстрые методы .

Нахождение полиномиального корня

Используя алгоритм деления в длину в сочетании с методом Ньютона , можно аппроксимировать действительные корни многочлена. Алгоритм работает следующим образом. Для данного многочлена степени с нулями сделайте какое-нибудь начальное предположение, такое что . Теперь повторите следующие два шага: ${\ Displaystyle p_ {п} (х)}$${\ displaystyle n}$${\ displaystyle z_ {n} <z_ {n-1} <\ cdots <z_ {1},}$${\ displaystyle x_ {0}}$${\ displaystyle z_ {1} <x_ {0}}$

1. Используя метод Ньютона , найти наибольший нуль в использовании догадки .${\ displaystyle z_ {1}}$${\ Displaystyle p_ {п} (х)}$${\ displaystyle x_ {0}}$
2. Используя метод Хорнера, разделите, чтобы получить . Вернитесь к шагу 1, но используйте многочлен и первоначальное предположение .${\ displaystyle (x-z_ {1})}$${\ displaystyle p_ {n-1}}$${\ displaystyle p_ {n-1}}$${\ displaystyle z_ {1}}$

Эти два шага повторяются до тех пор, пока для полинома не будут найдены все действительные нули. Если приближенные нули недостаточно точны, полученные значения можно использовать в качестве начальных предположений для метода Ньютона, но с использованием полного полинома, а не сокращенных полиномов.

Пример

Рассмотрим многочлен

${\ displaystyle p_ {6} (x) = (x + 8) (x + 5) (x + 3) (x-2) (x-3) (x-7)}$

который может быть расширен до

${\ displaystyle p_ {6} (x) = x ^ {6} + 4x ^ {5} -72x ^ {4} -214x ^ {3} + 1127x ^ {2} + 1602x-5040.}$

Из вышеизложенного мы знаем, что наибольший корень этого многочлена равен 7, поэтому мы можем сделать первоначальное предположение о 8. Используя метод Ньютона, первый нуль из 7 находится, как показано черным на рисунке справа. Далее делится на, чтобы получить ${\ displaystyle p (x)}$${\ Displaystyle (х-7)}$

${\ displaystyle p_ {5} (x) = x ^ {5} + 11x ^ {4} + 5x ^ {3} -179x ^ {2} -126x + 720}$

который показан красным на рисунке справа. Метод Ньютона используется для нахождения наибольшего нуля этого многочлена с начальным предположением 7. Наибольший ноль этого многочлена, который соответствует второму по величине нулю исходного многочлена, находится в точке 3 и обведен красным. Теперь полином 5-й степени разделим на, чтобы получить ${\ Displaystyle (х-3)}$

${\ displaystyle p_ {4} (x) = x ^ {4} + 14x ^ {3} + 47x ^ {2} -38x-240}$

который показан желтым цветом. Нуль для этого многочлена снова находится в 2 с помощью метода Ньютона и обведен желтым кружком. Метод Хорнера теперь используется для получения

${\ displaystyle p_ {3} (x) = x ^ {3} + 16x ^ {2} + 79x + 120}$

который показан зеленым и имеет ноль при −3. Далее этот многочлен сводится к

${\ Displaystyle p_ {2} (х) = х ^ {2} + 13x + 40}$

который показан синим цветом и дает ноль -5. Конечный корень исходного многочлена может быть найден либо с помощью конечного нуля в качестве начального предположения для метода Ньютона, либо путем сокращения и решения линейного уравнения. Как видно, были найдены ожидаемые корни из −8, −5, −3, 2, 3 и 7. ${\ Displaystyle p_ {2} (х)}$

Разделенная разность полинома

Метод Хорнера может быть изменен для вычисления разделенной разности с учетом полинома (как и раньше) ${\ Displaystyle (p (y) -p (x)) / (yx).}$

${\ displaystyle p (x) = \ sum _ {i = 0} ^ {n} a_ {i} x ^ {i} = a_ {0} + a_ {1} x + a_ {2} x ^ {2} + a_ {3} x ^ {3} + \ cdots + a_ {n} x ^ {n},}$

действовать следующим образом

${\ displaystyle {\ begin {align} b_ {n} & = a_ {n}, & \ quad d_ {n} & = b_ {n}, \\ b_ {n-1} & = a_ {n-1} + b_ {n} x, & \ quad d_ {n-1} & = b_ {n-1} + d_ {n} y, \\ & {} \ \ \ vdots & \ quad & {} \ \ \ vdots \\ b_ {1} & = a_ {1} + b_ {2} x, & \ quad d_ {1} & = b_ {1} + d_ {2} y, \\ b_ {0} & = a_ {0 } + b_ {1} x. \ end {выровнено}}}$

По завершении у нас есть

${\ displaystyle {\ begin {align} p (x) & = b_ {0}, \\ {\ frac {p (y) -p (x)} {yx}} & = d_ {1}, \\ p (y) & = b_ {0} + (yx) d_ {1}. \ end {align}}}$

Это вычисление разделенной разности подвержено меньшей ошибке округления, чем оценка и по отдельности, особенно когда . Подстановка в этом методе дает производную от . ${\ displaystyle p (x)}$${\ displaystyle p (y)}$${\ Displaystyle х \ приблизительно у}$${\ displaystyle y = x}$${\ displaystyle d_ {1} = p '(x)}$${\ displaystyle p (x)}$

История

Статья Хорнера под названием «Новый метод решения числовых уравнений всех порядков путем непрерывного приближения» была зачитана Лондонским королевским обществом на его заседании 1 июля 1819 года с продолжением в 1823 году. Статья Хорнера во второй части. « Философские труды Лондонского королевского общества за 1819 год» был тепло и широко встречен рецензентом в выпуске «Ежемесячного обзора» или «Литературного журнала за апрель 1820 года»; для сравнения, техническая статья Чарльза Бэббиджа в данном обзоре вкратце отклоняется. Последовательность обзоров в «Ежемесячном обзоре» за сентябрь 1821 г. приводит к выводу, что Холдред был первым человеком, открывшим прямое и общее практическое решение числовых уравнений. Фуллер показал, что метод, описанный в статье Хорнера 1819 г., отличается от того, что впоследствии стало известно как «метод Хорнера», и что, следовательно, приоритет этого метода должен быть отдан Холдреду (1820 г.).

В отличие от своих английских современников, Хорнер опирался на континентальную литературу, особенно на работы Арбогаста . Также известно, что Хорнер внимательно прочитал книгу Джона Бонникасла по алгебре, хотя и пренебрегал работой Паоло Руффини .

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

• Паоло Руффини в 1809 году (см . Правило Руффини )
• Исаак Ньютон в 1669 году
• китайский математик Чжу Шицзе в 14 веке
• китайский математик Цинь Цзюшао в своем математическом трактате в девяти разделах в 13 веке
• персидский математик Шарафуддин ат-Туси в 12 - м веке (первый использовать этот метод в общем случае кубического уравнения)
• китайский математик Цзя Сянь в XI веке ( династия Сун )
• Девять глав по математическому искусству , китайская работа времен династии Хань (202 г. до н.э. - 220 г. н.э.) под редакцией Лю Хуэя (fl. 3 век).

Цинь Цзюшао в своей книге « Шу Шу Цзю Чжан» (« Математический трактат в девяти разделах» , 1247 г.) представляет портфель методов типа Хорнера для решения полиномиальных уравнений, основанный на более ранних работах математика из династии Сун XI века Цзя Сяня ; например, один метод особенно подходит для биквинтиков, пример которого Цинь приводит в соответствии с тогдашней китайской традицией изучения конкретных случаев. Йошио Миками в книге « Развитие математики в Китае и Японии» (Лейпциг, 1913 г.) писал:

«... кто может отрицать тот факт, что выдающийся процесс Хорнера использовался в Китае, по крайней мере, почти на шесть долгих веков раньше, чем в Европе ... Мы, конечно, никоим образом не собираемся приписывать изобретение Хорнера китайскому происхождению, но время, достаточное для того, чтобы не исключить возможность того, что европейцы могли знать о китайском методе прямо или косвенно ».

Ульрих Либбрехт заключил: « Очевидно, что эта процедура - китайское изобретение ... этот метод не был известен в Индии . Он сказал, что Фибоначчи, вероятно, узнал об этом от арабов, которые, возможно, позаимствовали у китайцев. Извлечение квадратных и кубических корней по аналогичным принципам уже обсуждалось Лю Хуэем в связи с проблемами IV.16 и 22 в Цзю Чжан Суан Шу , в то время как Ван Сяотун в 7 веке предполагает, что его читатели могут решать кубики с помощью метода аппроксимации, описанного в его книга Jigu Suanjing .

Смотрите также

• Алгоритм Кленшоу для вычисления многочленов в форме Чебышева
• Алгоритм Де Бура для оценки сплайнов в форме B-сплайнов
• Алгоритм де Кастельжау для вычисления многочленов в форме Безье
• Схема Эстрина для облегчения распараллеливания на современных компьютерных архитектурах
• Метод Лилля для графической аппроксимации корней
• Правило Руффини и синтетическое деление полинома на бином вида x - r

Примечания

использованная литература

• Берггрен, 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]