tag:blogger.com,1999:blog-5246987755651065286.post98952366187383576..comments2024-02-22T16:15:42.388-08:00Comments on cbloom rants: 06-13-09 - A little mathemagiccbloomhttp://www.blogger.com/profile/10714564834899413045noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-5246987755651065286.post-74746038108935445632009-06-15T10:30:01.163-07:002009-06-15T10:30:01.163-07:00I learned
the differential equation version of Ro...I learned<br /><a href="http://en.wikipedia.org/wiki/Bulirsch%E2%80%93Stoer_algorithm" rel="nofollow"> the differential equation version of Romberg integration</a> in high school, and it totally blew my mind.<br /><br />Those Robin Green slides are way cool. The part on polynomial evaluation was surprising!won3dhttps://www.blogger.com/profile/09787472194187459747noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-10708635717635041612009-06-13T17:49:59.157-07:002009-06-13T17:49:59.157-07:00Whoah yeah Robin's talk is awesome, I've s...Whoah yeah Robin's talk is awesome, I've seen some similar material from him before but never the full talk slides. It's chock full of craziness.cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-44862955711915565572009-06-13T16:03:08.178-07:002009-06-13T16:03:08.178-07:00Numerical integration: One thing that's really...Numerical integration: One thing that's really handy to know is <a href="http://en.wikipedia.org/wiki/Romberg_integration" rel="nofollow">Romberg integration</a>; it's a relatively short but sweet extension of the trapezoid rule integration functional. The basic idea is rather simple: Treat the value of the integral as a function I(h) of your step size h. The first step uses one unsubdivided evaluation of the trapezoid rule for the interval [a,b], so h_0=b-a. The second step subdivides the interval in the middle, the third subdivides the resulting two intervals in the middle, and so on. That gives you a sequence of I(h_0), I(h_0/2), ..., I(h_0/(2^k)); fit a polynomial through this, your integral estimate is the extrapolated value for I(0). Understanding the idea is idea, proving that it works most definitely isn't :). Romberg integration works well for smooth functions or nearly-smooth functions with known discontinuities - and for everything else, you probably want to use Monte Carlo techniques anyway. The code works out beautifully as well: for the trapezoid rule evaluations, you can recycle the sum from the previous k and only add the new points. The polynomial evaluation is best done using Neville's algorithm. Finally, for the trapezoid rule, you can use a polynomial in h^2 instead of h for better convergence speed (explanation why is, again, nontrivial; it relies on properties of the error term expansion that's used in the convergence proof).<br /><br />It's really a rather elegant algorithm - there's a lot of math working in the background, but the actual code ends up very short and clean.<br /><br />As your post is both about numerical integration and orthogonal polynomials, <a href="http://en.wikipedia.org/wiki/Gaussian_quadrature" rel="nofollow">gaussian quadratures</a> deserve at least a honorary mention. The proof of the fundamental theorem mentioned in the article is really worth studying; it's, again, a beautiful piece of math, since everything falls so neatly into place - and the conclusion is anything but obvious.<br /><br />Finally, a really great resource on approximating functions numerically is Robin Greens GDC 2003 talk on the subject: <a href="http://www.research.scea.com/gdc2003/fast-math-functions_p1.pdf" rel="nofollow">part 1</a>, <a href="http://www.research.scea.com/gdc2003/fast-math-functions_p2.pdf" rel="nofollow">part 2</a>. It's terrific, and not nearly as well-known as it should be.ryghttps://www.blogger.com/profile/03031635656201499907noreply@blogger.com