计算拉格朗日多项式的有效方法

计算科学 r
2021-12-03 21:21:17

对于两个给定的向量,不一定是相同的长度,x=(x1,,xN)s=(s1,,sM)我想在 R 中尽可能有效地计算以下术语。对于j=1,,N

Hj:=i=1Mli(xj)
在哪里
li(xj)=l=1,ljMxjslsisl

下面是一些非常低效的测试代码。但是,我看不出如何使用矢量化样式或其他聪明的技巧来加快速度。

x <- rnorm(1000)
s <- rnorm(10,2,0.2)

l <- rep(0,length(s))
output <- rep(0,length(x))
for(j in 1:length(x)){
  xj <- x[j]
  for(i in 1:length(s)){
    s.i.dropped <- s[-i]
    l[i] <- prod((xj-s.i.dropped)/(s[i]-s.i.dropped))
  } 
  output[j] <- sum(l)
}
2个回答

既然专家已经为您做了,为什么还要自己做呢?有关R 中的具体实现,请参见polynompolynomF 。

如果您想了解更多关于计算拉格朗日多项式的有效数值过程,我推荐以下参考资料。

J.P。Berrut 和 LN Trefethen,“重心拉格朗日插值”,SIAM Rev.,第一卷。46,没有。3,第 501-517 页,2004 年。

“重心”拉格朗日公式的要点是预先计算重心权重(在O(n2) 操作) 以便随后可以在O(n)操作。您在上面实现的“天真”方法需要O(n2)正如您所指出的,每个插值的操作都比较慢。这个公式在插值点附近也是数值稳定的,这是一个很大的好处。

我不熟悉R,所以我不知道它是否已经实现了这个例程。但是,自己实施可能并不难。