連續計算平均數和方差

問題：對數列$x[n]$,計算其平均數$m[n]$,方差$v[n]$，平均數m[n]為x[1]到x[n]之間數的平均值v[n]為x[1]到x[n]之間的方差
$$\begin{gathered} m[n]=\sum _1^n(\frac{x[i]}{n}) \\ v[n]=\sum _i^n(\frac{(x[i]?m[n]{)}^2}{n}) \end{gathered}$$

這個問題用通用的方法計算沒有問題，但是效率會比較低。因為計算后面的平均數和方差時，前面的數重復累加計算了多次。對于平均數m[n]，一個簡單的優化方法就是設置一個累加序列s[n],s[i]為x[0]到x[i]之間數的和。這樣計算平均數m[n]，很容易從s[n]得到，計算方差呢？也可以設置另一個累加序列s2[n]，s2[i]為x[0]到x[i]之間數的平方和。
$$\begin{gathered} s[n]=\sum _1^n(x[i]) \\ m[n]=\frac{s[n]}{n} \\ s2[n]=\sum _1^{n}x[i{]}^2 \\ v[n]=\frac{{\sum }_1^{n}x[i{]}^2+n?m[n{]}^2?2?m[n]?{\sum }_1^{n}x[i]}{n} \\ =\frac{s2[n]+n?m[n{]}^2?2?m[n]?s[n]}{n} \end{gathered}$$
但是這種方法需要另外再多加兩個數組s[n]和s2[n]。下面介紹一種更好的方法，據說來自Donald Knuth 的《計算機程序設計藝術》第二卷，但是我粗略在這本書中找了一下沒有找到。我是在《Learning JavaScript JavaScript Essentials for Modern Application Development》這本書中介紹reduce方法(P140)看到的，覺得這種遞推方法很漂亮。下面進行推導：
$$\begin{gathered} m[n]=\sum _1^n(\frac{x[i]}{n}) \\ =\frac{{\sum }_1^{n?1}x[i]+x[n]}{n} \\ =\frac{{\sum }_1^{n?1}x[i]}{n?1}?\frac{n?1}{n}+\frac{x[n]}{n} \\ =m[n?1]?\frac{n?1}{n}+\frac{x[n]}{n} \\ =\frac{n?m[n?1]?m[n?1]+x[n]}{n} \\ =m[n?1]+\frac{x[n]?m[n?1]}{n} \end{gathered}$$
方差的計算有點區別，先計算其二階矩。
$$\begin{gathered} M2[n]=\sum _1^n(x[i]?m[n]{)}^2 \\ =\sum _1^n(x[i]?m[n?1]?\frac{x[n]?m[n?1]}{n}{)}^2 \\ =\sum _1^n(x[i]?m[n?1]{)}^2+\frac{(x[n]?m[n?1]{)}^2}{n}?2?\frac{x[n]?m[n?1]}{n}?\sum _1^{n}x[i]?m[n?1] \\ =M2[n?1]+(x[n]?m[n?1]{)}^2+\frac{(x[n]?m[n?1]{)}^2}{n}?2?\frac{(x[n]?m[n?1]{)}^2}{n} \\ =M2[n?1]+(x[n]?m[n?1]{)}^2?\frac{(x[n]?m[n?1]{)}^2}{n} \\ =M2[n?1]+(x[n]?m[n?1])?(x[n]?m[n?1]?m[n]+m[n?1]) \\ =M2[n?1]+(x[n]?m[n?1])?(x[n]?m[n]) \end{gathered}$$

m[n]和M2[n]計算都有一個$x[n]?m[n?1]$項，M2[n]還有一項很相似的$x[n]?m[n]$，并且都是累加的形式。雖然計算v[n]還需要先計算M2[n]，似乎還是多了一個臨時數組。

總結

以上是生活随笔為你收集整理的对序列连续计算平均数和方差的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。