метод Горнера

Алгоритм полиномиальной оценки

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

Алгоритм основан на правиле Горнера , в котором многочлен записывается во вложенной форме :

${\displaystyle {\begin{aligned}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{aligned}}}$

Это позволяет оценивать полином степени n только с помощью умножения и сложения. Это оптимально, поскольку существуют многочлены степени n , которые невозможно вычислить с помощью меньшего количества арифметических операций. ^[2] ${\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{aligned}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{aligned}}}$

Тогда значение . ${\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{aligned}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{aligned}}}$

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

${\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 p(x)/(x-x_{0})}$

где (который равен ) является остатком от деления, как показано в примерах ниже. Если является корнем , то (это означает, что остаток равен ), что означает, что вы можете факторизовать как . ${\displaystyle b_{0}}$ ${\displaystyle p(x_{0})}$ ${\displaystyle x_{0}}$ ${\displaystyle p(x)}$ ${\displaystyle b_{0}=0}$ ${\displaystyle 0}$ ${\displaystyle p(x)}$ ${\displaystyle x-x_{0}}$

Чтобы найти последовательные значения, вы начинаете с определения , которое просто равно . Затем вы работаете рекурсивно, используя формулу; ${\displaystyle b}$ ${\displaystyle b_{n}}$ ${\displaystyle a_{n}}$

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

пока вы не приедете . ${\displaystyle b_{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

Записи в третьей строке представляют собой сумму записей в первых двух. Каждая запись во второй строке представляет собой произведение значения x (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}(x)}$ ${\displaystyle f_{2}\,(x)}$

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

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

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

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

Оценка с использованием мономиальной формы полинома степени требует не более чем сложений и умножений, если степени вычисляются путем повторного умножения и каждый моном оценивается индивидуально. Затраты можно сократить до сложений и умножений путем оценки мощности путем итерации. ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle (n^{2}+n)/2}$ ${\displaystyle n}$ ${\displaystyle 2n-1}$ ${\displaystyle x}$

Если числовые данные представлены в цифрах (или битах), то наивный алгоритм также влечет за собой сохранение количества битов, примерно умноженного на : оцененный полином имеет приблизительную величину , и необходимо также сохранить себя. Напротив, метод Хорнера требует только сложения и умножения, а его требования к объему памяти лишь умножаются на количество битов . Альтернативно, метод Хорнера может быть вычислен с помощью слитого умножения-сложения . Метод Хорнера также можно расширить для оценки первых производных многочлена с помощью сложений и умножений. ^[3] ${\displaystyle 2n}$ ${\displaystyle x}$ ${\displaystyle x^{n}}$ ${\displaystyle x^{n}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle kn}$

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

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

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

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

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

${\displaystyle {\begin{aligned}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}).\\\end{aligned}}}$

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

${\displaystyle {\begin{aligned}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})\\\end{aligned}}}$

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

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

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

Пример

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

${\displaystyle {\begin{aligned}(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{aligned}}}$

Метод

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

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

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

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

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

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% пространства кода. ^[7]

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

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

Поиск корня полинома

Используя алгоритм деления в столбик в сочетании с методом Ньютона , можно аппроксимировать действительные корни многочлена. Алгоритм работает следующим образом. Учитывая полином степени с нулями, сделайте первоначальное предположение такое, что . Теперь повторите следующие два шага: ${\displaystyle p_{n}(x)}$ ${\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_{n}(x)}$ ${\displaystyle x_{0}}$
2. Используя метод Горнера, разделите , чтобы получить . Вернитесь к шагу 1, но используйте полином и начальное предположение . ${\displaystyle (x-z_{1})}$ ${\displaystyle p_{n-1}}$ ${\displaystyle p_{n-1}}$ ${\displaystyle z_{1}}$

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

Пример

Поиск корня полинома с использованием метода Горнера

Рассмотрим полином

${\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 (x-7)}$

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

который на рисунке справа нарисован красным. Метод Ньютона используется для поиска наибольшего нуля этого многочлена с начальной догадкой 7. Самый большой нуль этого многочлена, который соответствует второму по величине нулю исходного многочлена, находится в позиции 3 и обведен красным. Полином 5-й степени теперь делится на, чтобы получить ${\displaystyle (x-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}(x)=x^{2}+13x+40}$

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

Деленная разность многочлена

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

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

По завершении мы имеем

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

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

История

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

Статья Хорнера под названием «Новый метод решения числовых уравнений всех порядков методом непрерывной аппроксимации» ^[12] была зачитана перед Лондонским королевским обществом на его заседании 1 июля 1819 года с продолжением в 1823 году. ^{[12] ]} Статья Хорнера во второй части « Философских трудов Лондонского королевского общества» за 1819 год была тепло и широко встречена рецензентом ^{[ постоянная мертвая ссылка ]} в выпуске The Monthly Review: или Literary Journal за апрель 1820 года; для сравнения, техническая статья Чарльза Бэббиджа в этом обзоре категорически отвергается. В серии обзоров в « Ежемесячном обзоре» за сентябрь 1821 года делается вывод, что Холдред был первым человеком, открывшим прямое и общее практическое решение числовых уравнений. Фуллер ^[13] показал, что метод, описанный в статье Хорнера 1819 года, отличается от того, что впоследствии стало известно как «метод Горнера», и что, следовательно, приоритет этого метода должен принадлежать Холдреду (1820).

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

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

• Паоло Руффини в 1809 году (см. правило Руффини ) ^{[14] [15]}
• Исаак Ньютон в 1669 году ^{[16] [17]}
• китайский математик Чжу Шицзе в XIV веке ^[15]
• китайский математик Цинь Цзюшао в своем «Математическом трактате в девяти разделах» XIII века.
• персидский математик Шараф ад-Дин аль-Туси в XII веке (первый, кто применил этот метод в общем случае кубического уравнения) ^[18]
• китайский математик Цзя Сянь в 11 веке ( династия Сун )
• «Девять глав математического искусства» , китайская работа династии Хань (202 г. до н.э. – 220 г. н.э.) под редакцией Лю Хуэя (ок. III век). ^[19]

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

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

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

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

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

Примечания

1. 600 лет назад, китайский математик Цинь Цзюшао и 700 лет назад, персидский математик Шараф ад-Дин ат-Туси.
2. Пан 1966
3. Панкевич 1968.
4. Островский 1954.
5. Пан 1966.
6. Кнут 1997.
7. Крипасагар 2008, с. 62.
8. Хайэм 2002, раздел 5.4.
9. Кресс 1991, с. 112.
10. Фейтман и Кахан 2000
11. Либбрехт 2005, стр. 181–191.
12. Хорнер 1819.
13. Фуллер 1999, стр. 29–51.
14. Каджори 1911.
15. О'Коннор, Джон Дж.; Робертсон, Эдмунд Ф. , «Метод Хорнера», Архив истории математики MacTutor , Университет Сент-Эндрюс
16. Анализ по количественной серии, Fluctiones ac Differentias: Cum Enumeratione Linearum Tertii Ordinis, Londini. Экс Officina Pearsoniana. Анно MDCCXI, с. 10, 4-й абзац.
17. Сборник статей Ньютона, издание 1779 г., в сноске, т. я, с. 270-271
18. Берггрен 1990, стр. 304–309.
19. Темпл 1986, с. 142.
20. Миками 1913, с. 77
21. Либбрехт 2005, с. 208.

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

• Берггрен, Дж. Л. (1990). «Инновации и традиции в Муадалате Шарафа ад-Дина ат-Туси». Журнал Американского восточного общества . 110 (2): 304–309. дои : 10.2307/604533. JSTOR  604533.
• Каджори, Флориан (1911). «Метод аппроксимации Горнера, предсказанный Руффини». Бюллетень Американского математического общества . 17 (8): 409–414. дои : 10.1090/s0002-9904-1911-02072-9 .Прочтите перед Юго-западной секцией Американского математического общества 26 ноября 1910 года.
• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн 10.1016/0315-0860(81)90069-0, Клиффорд (2009). «Введение в алгоритмы». Historia Mathematica (3-е изд.). МТИ Пресс. 8 (3): 277–318. дои : 10.1016/0315-0860(81)90069-0 .{{cite journal}}: CS1 maint: numeric names: authors list (link)
• Фейтман, Р.Дж .; Кахан, В. (2000). Улучшение точных интегралов из систем символьной алгебры (PDF) (Отчет). ПАМ. Калифорнийский университет в Беркли: Центр чистой и прикладной математики. Архивировано из оригинала (PDF) 14 августа 2017 г. Проверено 17 мая 2018 г.
• Фуллер, AT (1999). «Хорнер против Холдреда: эпизод в истории корневых вычислений». История математики . 26 : 29–51. дои : 10.1006/hmat.1998.2214 .
• Хайэм, Николас (2002). Точность и устойчивость численных алгоритмов . СИАМ. ISBN 978-0-89871-521-7.
• Холдред, Т. (1820). Новый метод решения уравнений с легкостью и скоростью; с помощью которого находится истинное значение неизвестной величины без предварительного уменьшения. С дополнением, содержащим два других метода решения уравнений, основанных на том же принципе (PDF) . Ричард Уоттс. Архивировано из оригинала (PDF) 6 января 2014 г. Проверено 10 декабря 2012 г.

  Метод Холдреда находится в приложении на следующей странице под номером 45 (52-я страница PDF-версии).

• Хорнер, Уильям Джордж (июль 1819 г.). «Новый метод решения численных уравнений всех порядков методом непрерывной аппроксимации». Философские труды . Королевское общество Лондона. 109 : 308–335. дои : 10.1098/rstl.1819.0023. JSTOR  107508. S2CID  186210512.

  Доступен напрямую в Интернете по ссылке, но также перепечатан с оценкой в ​​DE Smith: A Source Book in Mathematics , McGraw-Hill, 1929; Перепечатка Дувра, 2 тома, 1959 г.

• Кнут, Дональд (1997). Искусство компьютерного программирования . Том. 2: Получисловые алгоритмы (3-е изд.). Аддисон-Уэсли. стр. 486–488 в разделе 4.6.4. ISBN 978-0-201-89684-8.
• Кресс, Райнер (1991). Численный анализ . Спрингер.
• Крипасагар, Венкат (март 2008 г.). «Эффективная микроматематика - методы умножения и деления для микроконтроллеров». Журнал Circuit Cellar (212).
• Либбрехт, Ульрих (2005). «Глава 13». Китайская математика в тринадцатом веке (2-е изд.). Дувр. ISBN 978-0-486-44619-6. Архивировано из оригинала 6 июня 2017 г. Проверено 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. S2CID  250869179.
• Панкевич, В. (1968). «Алгоритм 337: вычисление значений многочлена и его производных по схеме Горнера». Коммуникации АКМ . АКМ. 11 (9): 633. дои : 10.1145/364063.364089 . S2CID  52859619.
• Шпигель, Мюррей Р. (1956). Очерк теории и проблем студенческой алгебры Шаума . МакГроу-Хилл. ISBN 9780070602267.
• Темпл, Роберт (1986). Гений Китая: 3000 лет науки, открытий и изобретений . Саймон и Шустер. ISBN 978-0-671-62028-8.
• Уиттакер, ET ; Робинсон, Г. (1924). Исчисление наблюдений. Лондон: Блэки.
• Уайли, Александр (1897). «Заметки о науке китайской арифметики». Китайские исследования . Шанхай. стр. 159–194.{{cite book}}: CS1 maint: location missing publisher (link)

  Перепечатано из номеров The North China Herald (1852 г.).

Внешние ссылки

• «Схема Хорнера», Математическая энциклопедия , EMS Press , 2001 [1994]
• Цю Цзинь-Шао, Шу Шу Цзю Чжан (изд. Цун Шу Цзи Чэн)
• Дополнительную информацию о приложении для поиска корней см. в [1].