WikiDer > Метод Хорнерса - Википедия

Эта статья может требовать уборка встретиться с Википедией стандарты качества. Конкретная проблема: Видеть Обсуждение: метод Хорнера # Эта статья о двух разных алгоритмах Пожалуйста помоги улучшить эту статью если вы можете. (Ноябрь 2018) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

$${ 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}}}$$

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

В качестве альтернативы, Метод Хорнера также относится к методу аппроксимации корней многочленов, описанному Хорнером в 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 {align}}}$

потом ${ 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})}$

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

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

пока вы не дойдете до б₀.

Примеры

Оценивать ${ displaystyle f (x) = 2x ^ {3} -6x ^ {2} + 2x-1}$ за ${ displaystyle x = 3.}$

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

 Икс0│   Икс3    Икс2    Икс1    Икс0 3 │   2    −6     2    −1   │         6     0     6   └────────────────────────       2     0     2     5

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

Но по теорема о полиномиальном остатке, мы знаем, что остаток ${ 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}$, записи в третьей строке. Итак, синтетическое деление основано на методе Хорнера.

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

Разделять ${ 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}}.}$

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

Оценка с использованием мономиальной формы степени -п полином требует не более п дополнения и (п² + п) / 2 умножения, если мощности вычисляются путем повторного умножения и каждый одночлен оценивается индивидуально. (Это можно свести к п дополнения и 2п - 1 умножение путем оценки степеней Икс итеративно.) Если числовые данные представлены в виде цифр (или битов), тогда наивный алгоритм также предполагает сохранение примерно 2п умноженное на количество битов Икс (оцененный многочлен имеет приблизительную величину Икс^п, и нужно также хранить Икс^п сам). Напротив, метод Хорнера требует только п дополнения и п умножения, и его требования к хранению только п умноженное на количество битов Икс. В качестве альтернативы метод Хорнера можно вычислить с помощью п плавленый умножить - складывает. Метод Хорнера также можно расширить для оценки первого k производные полинома с кн сложения и умножения.^[3]

Метод Хорнера оптимален в том смысле, что любой алгоритм для вычисления произвольного многочлена должен использовать по крайней мере столько же операций. Александр Островский в 1954 г. доказал, что количество требуемых дополнений минимально.^[4] Виктор Пан в 1966 году доказал, что число умножений минимально.^[5] Однако когда Икс - матрица, метод Горнера не оптимален.^{[нужна цитата]}

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

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

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

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

${ 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-путь SIMD исполнение большинства из них. Современные компиляторы обычно оценивают полиномы таким образом, когда это выгодно, хотя для плавающая точка для расчетов требуется разрешающая (небезопасная) реассоциативная математика.

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

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

Пример

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

${ 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 и м:

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

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

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

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

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

Вывод

В общем, для двоичного числа с битовыми значениями (${ 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 (м + 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⁻¹) это право арифметический сдвиг, a (0) не приводит к операции (так как 2⁰ = 1 - мультипликативный элемент идентичности) и a (2¹) приводит к арифметическому сдвигу влево. Произведение умножения теперь можно быстро вычислить, используя только операции арифметического сдвига, сложения и вычитания.

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

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

Метод Хорнера можно использовать для преобразования между разными позиционными системы счисления - в таком случае Икс является основанием системы счисления, а а_я коэффициенты - это цифры основания-Икс представление данного числа - а также может использоваться, если Икс это матрица, и в этом случае выигрыш в вычислительной эффективности еще больше. Фактически, когда Икс является матрицей, возможно дальнейшее ускорение, использующее структуру матричное умножение, и только ${ displaystyle { sqrt {n}}}$ вместо п необходимо умножение (за счет увеличения объема памяти) с использованием метода Патерсона и Стокмейера 1973 года.^[8]

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

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

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

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

Пример

Нахождение корня полинома с использованием метода Хорнера

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

${ displaystyle p_ {6} (x) = (x-3) (x + 3) (x + 5) (x + 8) (x-2) (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 и обведен красным. Теперь полином пятой степени делится на ${ 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. Конечный корень исходного многочлена может быть найден либо с помощью конечного нуля в качестве начального предположения для метода Ньютона, либо путем сокращения ${ Displaystyle p_ {2} (х)}$ и решение линейного уравнения. Как можно видеть, были найдены ожидаемые корни из −8, −5, −3, 2, 3 и 7.

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

Метод Хорнера можно модифицировать для вычисления разделенной разницы ${ Displaystyle (п (у) -р (х)) / (у-х).}$ Учитывая многочлен (как и раньше)

${ 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},}$

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

${ 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)}$.

История

Цинь Цзюшаоалгоритм решения квадратного полиномиального уравнения${ displaystyle -x ^ {4} + 763200x ^ {2} -40642560000 = 0}$
результат: x = 840^[11]

Работа Хорнера «Новый метод решения числовых уравнений всех порядков непрерывным приближением»,^[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

Примечания

Рекомендации

• Берггрен, Дж. Л. (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]