霍纳方法的算法，基点在朱莉娅

Question

我正试图在Julia中为Horner的方法编写一个算法，该方法使用基点(b1、b2等(来评估多项式：y=p(x(=c1+c2(x-b1(+c3(x-b1((x-b2(+c4(x-b1((x-b2((x-b3(，其中系数由"；c"；并且基点由"0"表示；b"；。我需要评估的多项式是：p(x(=10-(21/2((x+2(+(45/6((x+2((x(-(7/3((x+20((x((x-1(。

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

function hornerpolybase(x,c,b)

# assign y to the first coefficient
# make y the same type as input x
y = c[1] * one(x) 

n = length(c)

for i = 2:n
y = y + c[i] * (x - b[i-1])   
end

return y
end

我的问题是，在for循环的第二次迭代之后，y=c1+c2(x-b1(+c3(x-b2(，而方程应该是y=c1+c2(x-b1(+c3*(x-b1((x-b2(。问题在第三次迭代中重复出现。我在想；如果；for循环中的条件语句应该可以解决这个问题，但我完全被卡住了。如果有任何帮助，我将不胜感激。

Answer 1

• 尽管y的初始化方式不同，但代码的类型并不完全稳定。例如，尝试@code_warntype hornerpolybase(1, [1,1], [1.0])。你可以通过包括b:的类型来修复它

  # assign y to the first coefficient
  T = promote_type(typeof(x), eltype(c), eltype(b))
  y::T = c[1] # implicit conversion to T
  

  (Julia中的evalpoly实际上也有同样的问题…(

• 您正在反向访问c(如果c[1]应该与c_1对应(。你需要从霍纳方法中的最后一个系数开始。

• 在每次迭代中，应该相乘的是y，而不是系数：

  y::T = c[end]
  n = length(c)
  for i = n-1:-1:1
  y = c[i] + y * (x - b[i])   
  end
  

Answer 2

标准Horner方案采用

C0 + C1 X + C2 X² + C3 X³ = C0 + X (C1 + C2 X + C3 X²)
= C0 + X (C1 + X (C2 + C3 X))

所以你计算的是，按这个顺序

C2 + X C3
C1 + X (C2 + C3 X)
C0 + X (C1 + X (C2 + C3 X))

使用中间变量

Y = C3
Y = C2 + X Y
Y = C1 + X Y
Y = C0 + X Y

在您的情况下，也有偏移：

Y = C3
Y = C2 + (X - X2) Y
Y = C1 + (X - X1) Y
Y = C0 + (X - X0) Y