Re: [微積] sigma i^2 公式推導
補述一下, 用這個方法與遞迴求出所有 Σi^k 公式的差別在於,
該方法寫起來是 O(n^3), 這個可以寫到 O(n^2).
雖然用拉格朗日插值也是 O(n^2).
※ 引述《driftseed (阿輝)》之銘言:
: 求
: n
: Σ i^2
: i=1
: 印象中是不是可以用微積分的方式
: 推導出來sigma i、i^2、i^3... 這些公式
n
以Σk^3為例
k=1
x
設 f(x) 是多項式且滿足 ∫f(t)dt = x^3
x-1
微分得 f(x) - f(x-1) = 3x^2
...
f''(x) - f''(x-1) = 6
所以 f''(x) = 6x + c
因此 f'(x) = 3x^2 + cx + d
由 f'(x) - f'(x-1) = 6x 算出 c = 3
得到 f(x) = x^3 + 3/2 x^2 + dx + e
同樣 f(x) - f(x-1) = 3x^2 可以算出 d = 3/2 - 1 = 1/2
x
最後 ∫f(t)dt = 1/4[x^4-(x-1)^4] + 1/2[x^3-(x-1)^3] + 1/4[x^2-(x-1)^2] + ex
x-1
= x^3
比對得 e = 1/4 - 1/2 + 1/4 = 0
n n
因此 Σk^3 = ∫f(t)dt = 1/4 n^4 + 1/2 n^3 + 1/4 n^2
k=1 0
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.115.144.193
※ 編輯: dqIpb 來自: 59.115.144.193 (08/22 20:30)
推
08/23 00:00, , 1F
08/23 00:00, 1F
→
08/23 00:13, , 2F
08/23 00:13, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容:
完整討論串 (本文為第 3 之 4 篇):