From: "rwg@sdf.lonestar.org" <rwg@sdf.lonestar.org> To: math-fun <math-fun@mailman.xmission.com> Sent: Saturday, March 28, 2009 1:30:31 AM Subject: Re: [math-fun] Simpsons' rules Gene>If I'm integrating over a circle, so that there is no boundary, then one point is as good as another, Not quite. Suppose we seek the average value (= 1/rt3) of 1/(2+sin(2(t+f) pi)), a smooth, period 1 fn(t) phase-shifted by the fraction f of a period. Then we can write the equal weight average exactly: (sum(1/(sin(%pi*(2*k/n+2*f))+2),k,0,n-1))/n = ((sqrt(3)+2)^n-(2-sqrt(3))^n)/(sqrt(3)*(-2*cos(%pi*(2*f+1/2)*n)+(sqrt(3)+2)^n+(2-sqrt(3))^n)) n - 1 ==== \ 1 > ----------------------- / 2 k ==== sin(pi (--- + 2 f)) + 2 k = 0 n ----------------------------- =: F(f) n n n (sqrt(3) + 2) - (2 - sqrt(3)) = ----------------------------------------------------------------- n n 1 ((sqrt(3) + 2) + (2 - sqrt(3)) - 2 cos(pi (2 f + -) n)) sqrt(3) 2 (Anybody want to hire me to make their CAS do these?) which does depend (slightly) on f. (And, ironically, is free of rt3.) For n = 1..6, 1 4 15 56 ---------------, ---------------, ----------------, ----------------, 2 + sin(2 f pi) 7 + cos(4 f pi) 26 - sin(6 f pi) 97 - cos(8 f pi) 209 780 ------------------, ------------------- 362 + sin(10 f pi) 1351 + cos(12 f pi) showing a dependence on f declining exponentially with n. Simpson's rule in this case is just F(f)/3 + 2 F(f+1/2n)/3, which is only slightly better, but has 2n samples, so is really worse! Gene>and I would expect the best approximation to be to give equal weights to each point. Now if instead, I integrate over an interval, there are some boundary effects, but deep within the interval , why would I want to do otherwise than to weight the points equally? This is a devilish question. But I don't think you can find any way of fading from 1,4,2,4,2,..., to 3,3,3,3,3,... and back to ...,2,4,2,4,1 that will exactly integrate cubics. Simpson's is geared to polynomials vs periodics. --rwg _______________________________________________ Integrating over the unit circle, let f(x) = sum(a[n] exp(i n x), n = -infinity..infinity). The exact integral is (2 pi a[0]). The uniform weight, N-point approximation is F[N] = (2 pi / N) sum( f(x0 + 2 pi k / N), k = 1..N) = (2 pi / N) sum( a[n] exp(i n x0) exp(2 pi i k n / N), k = 1..N, n = -infinity..infinity) Summing over k gives 0 unless n is a multiple of N. So F[N] = (2 pi) sum( a[N m] exp(i N m x0), m = -infinity..infinity) = (2 pi a[0]) + (error). Assuming that the Fourier coefficients fall off rapidly, the error is bounded by | a[N] | + | a[-N] |. If the function has a discontinuity, the a[n] fall off as 1/n, and it would be better to unwrap the circle and use Gaussian quadrature. -- Gene