我在做家庭作业时遇到了麻烦。
我需要描述一个有效的算法来解决 polynomial interpolation问题:
令
P[i,j]为点 (xi, yi),...,(xj,yj) 的多项式插值。找到 0 次或 1 次的 3 个简单多项式 q(x)、r(x)、s(x)，使得:P[i,j+1]={q(x)P[i,j](x)-r(x)P[i+1,j+1](x)}/s (x)给定点 (x1,y1),....(xn,yn)，根据您在第 1 节中找到的用于计算系数 a0,.. 的递推关系，描述一种有效的动态规划算法.an-1 的多项式插值。
嗯，我知道如何使用 Newton polynomial 解决多项式插值问题这看起来与上面的递归关系非常相似，但我看不出它如何帮助我找到 0 或 1 度的 q(x)、r(x)、s(x)，并假设我有正确的 q(x ), r(x), s(x) - 我如何使用动态规划解决这个问题？
任何帮助将不胜感激。
最佳答案
q(x) = (x at {j+1}) - x
r(x) = (x at i) - x
s(x) = (x at {j+1}) - (x at i)
x at i 或 x at j 表示它们在输入点的有序列表中的位置。
一些解释:
首先我们需要了解P[i,j](x)的含义。
将所有初始 (x,y) 对放在 n x n 矩阵的主对角线上。
现在您可以将 P[0,0](x) 提取为矩阵中位于 (0,0) 的点的 y 值。
P[0,1] 是矩阵中 (0,0) 和 (1,1) 点的线性插值。这将是一个直线函数。
((x at 0 - x)(y at 1) - (x at 1 - x)(y at 0))
---------------------------------------------
(x at 1 - x at 0)
P[0,2] 是之前两个线性插值的线性插值，这意味着您的 y 现在将是您在前一步。
这也是构建完整多项式的动态算法。
我强烈建议您看看 this很好的讲座，而且很全lecture notes .
关于algorithm - 使用动态规划进行插值，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30879212/