使用动态规划进行插值

Question

3

我在做一道作业练习时遇到了困难。

我需要描述一个有效的算法来解决多项式插值问题：

让P [i，j] 成为点（xi，yi），...，（xj，yj）的多项式插值。找到三个简单的次数为0或1的多项式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。

我知道如何使用牛顿插值多项式来解决多项式插值问题，它看起来与上述递归关系非常相似，但我不知道它如何帮助我找到0或1次的 q(x), r(x), s(x)，并且假设我有了正确的 q(x), r(x), s(x) - 我如何使用动态规划来解决这个问题？任何帮助都将不胜感激。

- user3114639

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Yaelet · Accepted Answer

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 很好的讲座和完整的讲座笔记。