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）

在我们没有节点的情况下，霍纳的方法是这样的：

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

Code Horner 的多项式求值方法

Code Horner’s Method for Polynomial Evaluation

matlab

polynomial-math