#numerical integration

what’s up I spent several hours and fought three different branches of computer science making this dumb gif.

Numerical Integration

In mathematics numerical integration techniques like trapezoidal rule, Simpson’s 1/3rd rule, Simpson’s 3/8th rule and Gauss quadrate formula are available. In trapezoidal rule, the variation of the function between two sampling point is assumed linear. In Simpson’s 1/3rd rule 3 sampling points are used and second degree curve is fitted. In Simpson’s 3/8th rule 4 sampling…

This is a blog post for our 2/17/15 class in which we talked about Numerical Integration. (If you're just one of my regular followers, not my professor, and are seeing this, it's for a Technical Animation class I'm taking.)

We went over many different techniques in class, mostly going over the formulas. For my blog post I decided to organize and re-cap in one place some of the pros, cons, and real-world examples for the different integration techniques we talked about (mostly using the textbook and wikipedia to get a brief overview of each method). In doing so I hoped to gain a better understanding of how the methods differ from one another.

Euler: This is the most simple integration method. It is not time-reversible, as it depends on the value of the previous step to compute the next step. It is not very stable or very accurate, so for this reason it isn't used as much as other methods like Runge-Kutta, which have similar computational cost but more accurate results.

Runge-Kutta: Runge-Kutta methods are symmetrical with respect to each interval. They are a lot more stable and accurate than Euler. in RK4 specifically, though there is a lot of computation on each step, it increases accuracy so that larger time steps can be taken and overall computational cost is less than with naive Euler.

Implicit Euler: This is also known as the backward Euler method. The implicit method finds a position whose derivative can update the current value to the new value at the next time step. While it takes more time to solve this equation than the forward Euler, it is more stable and larger time steps can be taken, so in the long run computational savings occur, just like in Runge-Kutta.

Semi-implicit Euler: Unlike Euler, it is symplectic, meaning it conserves energy of dynamic systems. It is more stable and computationally costs less as well. It is used in many physics engines because it has many desirable qualities.

Leapfrog: One of this method's strengths is that it is time-reversible, meaning you can integrate both forward and backward in time steps. It is also symplectic. For this reason it is often used specifically in orbital dynamics, since other integration schemes like RK4 don't conserve energy. It is also used in gravity simulations, though RK4 is more commonly used here.

This is my personal favorite area which definitely is a vast subject and we'll barely scratch the surface here - NUMERICAL METHODS

Since, today dynamics is mostly studied on the computer, we'll see a couple of numerical integration methods. One of them is Euler's Method.

Let $$ \dot{x}=f(x,t), x(t_0)=x_0\ $$

This is approximated by making use of Taylor series approximation of the dependent variable \(x(t)\) at point \(t_{i+1}\) (Note that \(t_{i+1}-t_i=\Delta t\) ). That is

$$ x(t_{i+1})=x(t_i+\Delta t) = x(t_i) + \Delta t \dot{x}(t_i)+O(\Delta t^2) $$

Neglecting higher order terms,

$$ x_{i+1} = x_i+f(x_i,t_i)\Delta t $$

This is the simplest possible numerical integration scheme.

Location Truncation Error

The error made in a single step, the difference b/w the numerical solution after one step, \(x_1\) and the exact solution at time \(t_1=t_0+\Delta t\) is LTE.

The numerical solution is given by

$$x_1=x_0+f(x_0,t_0)\Delta x $$

For the exact solution, we use the taylor expansion

$$ x(t_0+\Delta t)=x(t_0)+\Delta t\dot{x}(t_0)+ \frac{1}{2}\Delta t^2\ddot{x}(t_0)+O(\Delta t^3) $$

Thus

$$ LTE = x(t_0+\Delta t)-x_1=\frac{1}{2}\Delta t^2\ddot{x}(t_0)+O(\Delta t^3) $$

A slightly different formulation for the local truncation error can be obtained by using the Lagrange form for the remainder term in Taylor's theorem. If \(x\) is a continuous second derivative, then there exists a \(\xi \in [t_0,t_0+\Delta t]\) such that 

$$ LTE = \frac{1}{2} \Delta t^2\ddot{x}(\xi)$$