Дюраны-Кернер с производной в знаменателе

Question

Термином коррекции для Дюрана-Кернер метода корневого находка

$w_k = -\frac{f(z_k)}{\prod_{j\not=k}(z_k - z_j)}$ 

Википедии Talk page упоминает, что также можно использовать производным, в знаменателе вместо указанного выше продукта.

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

Я правильно предполагаю, что производная выглядит, по-видимому, как $ g '(x) $, где $ g (x) = \ prod (z_k - z_j) $?

PS: Я попытался реализовать выражение Бо Якоби со страницы «Обсуждение», но я не могу заставить его работать: я попытался суммировать все продукты всех приближений, кроме одного, и поместить результат в знаменатель, но это не так, t, похоже, работает таким образом ...

Answer 1

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

Комбинация, использующая производную соотв. Шаг Ньютона и текущие корневые аппроксимации - это метод Аберта-Эрлиха.

---

Связанное обсуждение о том, что продукт в знаменателе может быть интерпретирован как производные от вспомогательного полинома. Обсуждалась формула

(д/дх) ((хр) (XQ) (хт) (XS)) = (XQ) (хт) (XS) + (хр) (хт) (XS) + (xp) (xq) (xs) + (xp) (xq) (xr)

остается верным в высшей степени. Следует отметить, что при оценке с приблизительным корнем, то есть одним из p,q,r,s, остается только один термин продукта.

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

---

Для умеренных степеней быстрее оценивать продукты как заданные (n * (n-2) mults). Сборка линейных факторов в приближенном полиноме, а затем оценка производного многочлена в приближениях требует более высокого усилия (около 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]