如果我们看到一个序列的前$k$项，不能确定下一项的值，因为有无限多的多项式函数可以模拟这个序列。
比如立方函数产生的序列：
$$u_n=1,8,27,64,125,216\dots$$
如果只给出前两项，最佳匹配（最简单）是线性函数，那么下一项是15。如果给出前三项，那么最佳匹配是二次多项式。
我们定义$OP(k, n)$为序列前$k$项的最优多项式函数的第$n$项。如果$n\leq k$，那么能够精确表示序列的第$n$项。潜在的第一个不匹配项FIT（first incorrect term）是$OP(k, k+1)$，这种情况称为称作bad OP（BOP）。
如果只给出一项，最明智的选择是常数函数。
因此，对于立方函数的序列来说，OP如下所示：
$$\begin{aligned}
OP(1,n)&=1&&1,1,1,1\dots\
OP(2,n)&=7n-6&&1,8,15\dots\
OP(3,n)&=6n^2-11n+6&&1,8,27,58,\dots\
OP(4,n)&=n^3&&1,8,27,64,125\dots
\end{aligned}$$
$k\geq 4$就没有BOP了。
所有的FIT之和是$1+15+58=74$。
对于下面的十阶多项式函数
$$u_n=1-n+n^2-n^3+n^4-n^5+n^6-n^7+n^8-n^9+n^{10}$$
求所有BOP对应的FIT之和。
其实题目挺简单的。需要做的就是找出函数的前11项，然后用小于十阶的函数取拟合，找到第一个FIT求和就可以了。
或许可以编程来完成这个题目，但是还需要解线性方程组求系数。鉴于数值计算的知识都快还给老师了，matlab也都忘到脑后了；同时工作中不涉及这些，不知道有哪些类库可以用，所以使用wolframalpha来解决这个题目。
输入公式$1 − n + n^2 − n^3 + n^4 − n^5 + n^6 − n^7 + n^8 − n^9 + n^10$可以得到前几项的值
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 683 | 44287 | 838861 | 8138021 | 51828151 | 247165843 | 954437177 | 3138105961 | 9090909091 | 23775972551 | 57154490053 | 128011456717 | 269971011311 |
下面以$OP(6,n)$为例。
输入前6项得到一个五阶多项式函数。get 5 degree polynomial for 1, 683, 44287, 838861, 8138021, 51828151
$$-14707439 + 34305227 x - 29116967 x^2 + 11535788 x^3 - 2175668 x^4 + 159060 x^5$$
再找到前几项
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|
| 1 | 683 | 44287 | 838861 | 8138021 | 51828151 | 205015603 |
第一项不同的就是205015603。
按照同样的做法可以完成其他小于十阶的情况，然后就和即可。