Метод Хорнера

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

В математике и информатике метод Горнера (или схема Горнера ) — это алгоритм для оценки полиномов . Хотя этот метод назван в честь Уильяма Джорджа Хорнера , он гораздо старше, поскольку сам Хорнер приписывал его Жозефу-Луи Лагранжу , и его можно проследить на много сотен лет назад, до китайских и персидских математиков. ^[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 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 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}$

В этом примере, если мы можем видеть, что , записи в третьей строке. Таким образом, синтетическое деление (которое было фактически изобретено и опубликовано Руффини за 10 лет до публикации Хорнера) проще в использовании; можно показать, что оно эквивалентно методу Хорнера. ${\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}\\[1ex]&=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n}\\[1ex]&=\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)\\[1ex]&=\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)\\[1ex]&=\sum _{i=0}^{\lfloor n/2\rfloor }a_{2i}x^{2i}+x\sum _{i=0}^{\lfloor n/2\rfloor }a_{2i+1}x^{2i}\\[1ex]&=p_{0}(x^{2})+xp_{1}(x^{2}).\end{aligned}}}$$

В более общем случае суммирование можно разбить на k частей: где внутренние суммирования могут быть оценены с использованием отдельных параллельных экземпляров метода Горнера. Это требует немного больше операций, чем базовый метод Горнера, но позволяет k -стороннее SIMD- выполнение большинства из них. Современные компиляторы обычно оценивают полиномы таким образом, когда это выгодно, хотя для вычислений с плавающей точкой это требует включения (небезопасной) реассоциативной математики ^{[ требуется цитата ]} . $${\displaystyle 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})}$$

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

Метод Хорнера — это быстрый, эффективный с точки зрения кода метод умножения и деления двоичных чисел на микроконтроллере без аппаратного умножителя . Одно из двоичных чисел, которое нужно умножить, представляется в виде тривиального многочлена, где (используя приведенные выше обозначения) , и . Затем 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=\left(2^{-3}+2^{-5}\right)m=\left(2^{-3})m+(2^{-5}\right)m\\&=2^{-3}\left(m+\left(2^{-2}\right)m\right)=2^{-3}\left(m+2^{-2}(m)\right).\end{aligned}}}$$

Метод

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

1. Регистр, содержащий промежуточный результат, инициализируется значением d .
2. Начните с наименее значимого (крайнего правого) ненулевого бита в m .
   2. Подсчитать (слева) количество позиций битов до следующего самого значимого ненулевого бита. Если более значимых битов нет, то взять значение текущей позиции бита.
   3. Используя это значение, выполните операцию сдвига влево на указанное количество бит в регистре, содержащем промежуточный результат.
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 ⁻¹ ) — это правый арифметический сдвиг , a (0) не приводит к какой-либо операции (поскольку 2 ⁰ = 1 — это мультипликативный тождественный элемент ), а a (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 находится, как показано черным на рисунке справа. Затем делится на , чтобы получить , который нарисован красным на рисунке справа. Метод Ньютона используется для нахождения наибольшего нуля этого многочлена с начальным предположением 7. Наибольший ноль этого многочлена, который соответствует второму по величине нулю исходного многочлена, находится в точке 3 и обведен красным. Теперь многочлен степени 5 делится на , чтобы получить , который показан желтым цветом. Ноль для этого многочлена снова находится в точке 2 с помощью метода Ньютона и обведен желтым цветом. Теперь используется метод Хорнера для получения , который показан зеленым цветом и обнаруживается, что имеет ноль в точке −3. Этот многочлен далее сводится к , который показан синим цветом, и дает ноль −5. Окончательный корень исходного полинома можно найти, либо используя конечный ноль в качестве начального предположения для метода Ньютона, либо сокращая и решая линейное уравнение . Как видно, ожидаемые корни −8, −5, −3, 2, 3 и 7 были найдены. ${\displaystyle p(x)}$ ${\displaystyle (x-7)}$ $${\displaystyle p_{5}(x)=x^{5}+11x^{4}+5x^{3}-179x^{2}-126x+720}$$ ${\displaystyle (x-3)}$ $${\displaystyle p_{4}(x)=x^{4}+14x^{3}+47x^{2}-38x-240}$$ $${\displaystyle p_{3}(x)=x^{3}+16x^{2}+79x+120}$$ $${\displaystyle p_{2}(x)=x^{2}+13x+40}$$ ${\displaystyle p_{2}(x)}$

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

Метод Хорнера можно модифицировать для вычисления разделенной разности. Учитывая полином (как и прежде), действуйте следующим образом ^[10] ${\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},}$$ $${\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] Статья Хорнера в Части II «Философских трудов Лондонского королевского общества» за 1819 год была тепло и горячо встречена рецензентом ^{[ постоянная мертвая ссылка ]} в выпуске «The Monthly Review: or, Literary Journal» за апрель 1820 года; для сравнения, техническая статья Чарльза Бэббиджа в этом обзоре кратко отвергнута. Последовательность обзоров в «The Monthly Review» за сентябрь 1821 года заключает, что Холдред был первым человеком, открывшим прямое и общее практическое решение числовых уравнений. Фуллер ^[13] показал, что метод, изложенный в статье Хорнера в 1819 году, отличается от того, что впоследствии стало известно как «метод Хорнера», и что, следовательно, приоритет этого метода должен принадлежать Холдреду (1820).

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

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

• Паоло Руффини в 1809 году (см. правило Руффини ) ^{[14] [15]}
• Исаак Ньютон в 1669 году ^{[16] [17]}
• китайский математик Чжу Шицзе в 14 веке ^[15]
• китайский математик Цинь Цзюшао в своем «Математическом трактате в девяти разделах» в XIII веке
• персидский математик Шараф ад-Дин ат -Туси в XII веке (первый, кто использовал этот метод в общем случае кубического уравнения) ^[18]
• китайский математик Цзя Сянь в 11 веке ( династия Сун )
• Девять глав о математическом искусстве , китайский труд династии Хань (202 г. до н. э. – 220 г. н. э.), отредактированный Лю Хуэем (ок. 3 в. н. э.) ^[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. Horner 1819.
13. Фуллер 1999, стр. 29–51.
14. 1911.
15. O'Connor, John J.; Robertson, Edmund F. , "Метод Хорнера", Архив истории математики MacTutor , Университет Сент-Эндрюс
16. Анализ по количественной серии, Fluctiones ac Differentias: Cum Enumeratione Linearum Tertii Ordinis, Londini. Экс Officina Pearsoniana. Анно MDCCXI, с. 10, 4-й абзац.
17. Собрание сочинений Ньютона, издание 1779 г., в сноске, т. I, стр. 270-271
18. Берггрен 1990, стр. 304–309.
19. Темпл 1986, стр. 142.
20. Миками 1913, стр. 77
21. Либбрехт 2005, стр. 208.

Ссылки

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

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

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

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

• Кнут, Дональд (1997). Искусство программирования . Том 2: Получисленные алгоритмы (3-е изд.). Addison-Wesley. С. 486–488 в разделе 4.6.4. ISBN 978-0-201-89684-8.
• Кресс, Райнер (1991). Численный анализ . Springer.
• Крипасагар, Венкат (март 2008 г.). «Эффективная микроматематика – методы умножения и деления для микроконтроллеров». Журнал Circuit Cellar (212).
• Либбрехт, Ульрих (2005). "Глава 13". Китайская математика в тринадцатом веке (2-е изд.). Дувр. ISBN 978-0-486-44619-6. Архивировано из оригинала 2017-06-06 . Получено 2016-08-23 .
• Миками, Ёсио (1913). «Глава 11. Цинь Цзю-Шао». Развитие математики в Китае и Японии (1-е изд.). Переиздание Chelsea Publishing Co., стр. 74–77.
• Островский, Александр М. (1954). «О двух проблемах абстрактной алгебры, связанных с правилом Горнера». Исследования по математике и механике, представленные Рихарду фон Мизесу . Academic Press. стр. 40–48. ISBN 978-1-4832-3272-0. Архивировано из оригинала 2019-04-15 . Получено 2016-08-23 .
• Пан, Й. Я. (1966). «О способах вычисления значений многочленов». Математические обзоры . 21 : 105–136. doi :10.1070/rm1966v021n01abeh004147. S2CID  250869179.
• Pankiewicz, W. (1968). "Алгоритм 337: вычисление полинома и его производных значений по схеме Горнера". Сообщения ACM . 11 (9). ACM: 633. doi : 10.1145/364063.364089 . S2CID  52859619.
• Шпигель, Мюррей Р. (1956). Очерк теории и проблем университетской алгебры Шаума . McGraw-Hill. ISBN 9780070602267.
• Темпл, Роберт (1986). Гений Китая: 3000 лет науки, открытий и изобретений . Саймон и Шустер. ISBN 978-0-671-62028-8.
• Уиттекер, ET ; Робинсон, G. (1924). Исчисление наблюдений. Лондон: Blackie.
• Уайли, Александр (1897). «Заметки о науке китайской арифметики». Китайские исследования . Шанхай. С. 159–194.{{cite book}}: CS1 maint: location missing publisher (link)

  Перепечатано из выпусков The North China Herald (1852).

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

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