如需转载请联系听云College团队成员小尹 邮箱：yinhy#tingyun.com

摘要

本文讨论多项式拟合的实时计算，这里实时计算表示为，每一次的传入一个数据以及上一次计算的结果，并返回更改拟合曲线的各个参数，并给出两种算法尝试，在计算量的基础上优化算法，主要以启发为主，欢迎讨论，分享优秀的计算方法。希望对前端图形计算工程师和数据分析师能有一定的帮助。

假设读者已经熟知期望，协方差的定义，以及矩阵的简单计算，并了解以下性质。

从实时线性拟合说起

设点希望能拟合出一条直线使点到线的距离和最小，假设直线方程为,那么就可以根据公式

分别计算出就可以计算出k，计算出联立方程

可分别计算出k和b，所以问题被转化为了实时计算,期中

其中 

因为

所以

令可得

对于只需要改变上面函数中的项即可

对于也只需要修改对应的参数即可

扩展到实时多项式拟合

幂次为2时开始，此时假设直线方程为,原理同上有

联立方程

此时2个方程3个未知数无法求解参数，引入并联立

转化为增广矩阵求解问题

推广到幂次为q时可以获得矩阵

另外矩阵中，在计算矩阵中每个元素时，只需要计算相同部分即可。

计算量分析

算法一

每个协方差都用如下公式进行计算

我们一共所需要计算的期望有

共项，可利用公式进行计算。

若用键值对来表示每一步加法和乘法的数量，则

同时内存中需要存储各个期望的值而不用存储协方差的值

算法二

每个协方差采用增量方程进行计算

我们所需要计算的中间变量有共项，其中，所需要计算的期望有

共项

阵计算中，协方差行，所有项均有项，可以舍弃不影响结果

计算量

n=0时，实际上是在求.

延伸出的其他应用

1)不同数据集合并

更一般的，我们在计算量个集合合并后的方差时，记两个样本集合，集合大小分别是n和m，现已知两个集合的协方差。

其中

又因为

所以

综上

对于多个集合的合并，参考上面推导过程，简写为

对于不同集合协方差，可以在不同主机上进行计算并按此公式进行合并，其中k表示k个集合，表示每个集合的大小。

2)改变输入数据的符号和n的大小，可以将算法改为递减的模式

观察公式

可以反向推导出

也就是更新了的定义，，在此基础上我们可以结合前面的公式进行滑动窗口式的计算。

想阅读更多技术文章，请访问听云技术博客，访问听云官方网站感受更多应用性能优化魔力。