多项式求值的Code Horner方法

Question

我正在尝试对Horner的多项式求值方法进行编码，但由于某种原因，它对我不起作用，我不确定我哪里错了。

这些是我的数据：

nodes = [-2, -1, 1]
x = 2
c (coefficients) = [-3, 3, -1]

到目前为止，我的代码是：

function y = horner(x, nodes, c)
n = length(c);
y = c(1);
for i = 2:n
y = y * ((x - nodes(i - 1)) + c(i));
end
end

我应该得到一个多项式，比如(−1)·(x+2)(x+1)+3·(x+2)−3·1，如果x =2，那么我应该得到-3。但出于某种原因，我不知道自己哪里错了。

编辑：

所以我更改了代码。我认为它有效，但我不确定：

function y = horner(x, nodes, c)
n = length(c);
y = c(n);
for k = n-1:-1:1
y = c(k) + y * (x - nodes((n - k) + 1));
end
end

Answer 1

这是有效的：

function y = horner(x, nodes, c)
n = length(c);
y = 0;
for i = 1:n % We iterate over `c`
tmp = c(i);
for j = 1:i-1 % We iterate over the relevant elements of `nodes`
tmp *= x - nodes(j); % We multiply `c(i) * (x - nodes(1)) * (x -nodes(2)) * (x- nodes(3)) * ... * (x - nodes(i -1))
end
y += tmp; % We added each product to y
end
% Here `y` is as following:
% c(1) + c(2) * (x - nodes(1)) + c(3) * (x - nodes(1)) * (x - nodes(2)) + ... + c(n) * (x - nodes(1)) * ... * (x - nodes(n - 1))
end

Answer 2

(很抱歉这不是python，但我不了解python(

在我们没有节点的情况下，horner的方法是这样工作的：

p = c[n]
for i=n-1 .. 1
p = x*p + c[i]

例如，对于二次型(系数为a、b、c(，这就是

p = x*(x*a+b)+c

请注意，如果您的语言支持fma

fma(x,y,x) = x*y+z

那么霍纳的方法可以写成

p = c[n]
for i=n-1 .. 1
p = fma( x, p, c[i])

当你有节点时，改变很简单：

p = c[n]
for i=n-1 .. 1
p = (x-nodes[i])*p + c[i]

或者，使用fma

p = c[n]
for i=n-1 .. 1
p = fma( (x-nodes[i]), p, c[i])

对于上面的二次方，这导致

p = (x-nodes[1]*((x-nodes[2])*a+b)+c