Если вы используете производную в знаменателе, вы получаете метод Ньютона. Вы можете получить значение производной с помощью связанной схемы Хорнера или вы можете сформировать полином производной и просто оценить его. Вам нужно будет задокументировать, как вы оцениваете значение полинома.
Комбинация с использованием производной соотв. Шаг Ньютона и текущие приближения корня - это метод Аберта-Эрлиха.
Связанное обсуждение касается того факта, что произведение в знаменателе можно интерпретировать как производную от вспомогательного многочлена. Обсуждаемая формула
(d/dx)((x-p)(x-q)(x-r)(x-s)) = (x-q)(x-r)(x-s)+(x-p)(x-r)(x-s)+(x-p)(x-q)(x-s)+(x-p)(x-q)(x-r)
остается верным в более высоких степенях. Обратите внимание, что при вычислении приблизительного корня, т. е. одного из p,q,r,s, остается только один член произведения.
Это можно использовать для быстрой оценки в высоких степенях, когда алгоритмы быстрой интерполяции/многоточечной оценки, основанные на быстром полиномиальном умножении, быстрее, чем наивные реализации со сложностью, квадратичной по степени.
Для средних степеней быстрее оценивать произведения как заданные (n*(n-2) множителей). Сборка линейных множителей в приближенный полином, а затем вычисление производного полинома в приближениях требует больших усилий (примерно на n²/2 множителей больше).
Чтобы вычислить полином g(z) «наивным» способом, вам нужно несколько раз умножить полином на линейный множитель.
[ a[m], ..., a[0] ] * [ 1, -zz ]
= [ a[m], a[m-1] - zz*a[m],..., a[0] - zz*a[1], -zz*a[0] ]
Это можно сделать на месте, начав сверху, т. е. с наивысшей степени.
a[m+1] = a[m]
for k=m downto 1
a[k] = a[k-1]-zz*a[k]
end for
a[0] = -zz*a[0]
person
Lutz Lehmann
schedule
24.08.2015
