Midpoint method

In numerical analysis, a branch of applied mathematics, the midpoint method is a one-step method for numerically solving the differential equation,

y'(t)=f(t,y(t)),\quad y(t_{0})=y_{0}

.

Illustration of the midpoint method assuming that

y_{n}

equals the exact value

y(t_{n}).

The midpoint method computes

y_{n+1}

so that the red chord is approximately parallel to the tangent line at the midpoint (the green line).

The explicit midpoint method is given by the formula

y_{n+1}=y_{n}+hf\left(t_{n}+{\frac {h}{2}},y_{n}+{\frac {h}{2}}f(t_{n},y_{n})\right),\qquad \qquad (1e)

the implicit midpoint method by

y_{n+1}=y_{n}+hf\left(t_{n}+{\frac {h}{2}},{\frac {1}{2}}(y_{n}+y_{n+1})\right),\qquad \qquad (1i)

for $n=0,1,2,\dots$ Here, $h$ is the step size — a small positive number, $t_{n}=t_{0}+nh,$ and $y_{n}$ is the computed approximate value of $y(t_{n}).$ The explicit midpoint method is sometimes also known as the modified Euler method,[1] the implicit method is the most simple collocation method, and, applied to Hamiltonian dynamics, a symplectic integrator. Note that the modified Euler method can refer to Heun's method,[2] for further clarity see List of Runge–Kutta methods.

The name of the method comes from the fact that in the formula above, the function $f$ giving the slope of the solution is evaluated at $t=t_{n}+h/2={\tfrac {t_{n}+t_{n+1}}{2}},$ the midpoint between $t_{n}$ at which the value of $y(t)$ is known and $t_{n+1}$ at which the value of $y(t)$ needs to be found.

A geometric interpretation may give a better intuitive understanding of the method (see figure at right). In the basic Euler's method, the tangent of the curve at $(t_{n},y_{n})$ is computed using $f(t_{n},y_{n})$ . The next value $y_{n+1}$ is found where the tangent intersects the vertical line $t=t_{n+1}$ . However, if the second derivative is only positive between $t_{n}$ and $t_{n+1}$ , or only negative (as in the diagram), the curve will increasingly veer away from the tangent, leading to larger errors as $h$ increases. The diagram illustrates that the tangent at the midpoint (upper, green line segment) would most likely give a more accurate approximation of the curve in that interval. However, this midpoint tangent could not be accurately calculated because we do not know the curve (that is what is to be calculated). Instead, this tangent is estimated by using the original Euler's method to estimate the value of $y(t)$ at the midpoint, then computing the slope of the tangent with $f()$ . Finally, the improved tangent is used to calculate the value of $y_{n+1}$ from $y_{n}$ . This last step is represented by the red chord in the diagram. Note that the red chord is not exactly parallel to the green segment (the true tangent), due to the error in estimating the value of $y(t)$ at the midpoint.

The local error at each step of the midpoint method is of order $O\left(h^{3}\right)$ , giving a global error of order $O\left(h^{2}\right)$ . Thus, while more computationally intensive than Euler's method, the midpoint method's error generally decreases faster as $h\to 0$ .

The methods are examples of a class of higher-order methods known as Runge–Kutta methods.

Derivation of the midpoint method

Illustration of numerical integration for the equation

y'=y,y(0)=1.

Blue: the Euler method, green: the midpoint method, red: the exact solution,

y=e^{t}.

The step size is

h=1.0.

The same illustration for

h=0.25.

It is seen that the midpoint method converges faster than the Euler method.

The midpoint method is a refinement of the Euler's method

y_{n+1}=y_{n}+hf(t_{n},y_{n}),\,

and is derived in a similar manner. The key to deriving Euler's method is the approximate equality

y(t+h)\approx y(t)+hf(t,y(t))\qquad \qquad (2)

which is obtained from the slope formula

y'(t)\approx {\frac {y(t+h)-y(t)}{h}}\qquad \qquad (3)

and keeping in mind that $y'=f(t,y).$

For the midpoint methods, one replaces (3) with the more accurate

y'\left(t+{\frac {h}{2}}\right)\approx {\frac {y(t+h)-y(t)}{h}}

when instead of (2) we find

y(t+h)\approx y(t)+hf\left(t+{\frac {h}{2}},y\left(t+{\frac {h}{2}}\right)\right).\qquad \qquad (4)

One cannot use this equation to find $y(t+h)$ as one does not know $y$ at $t+h/2$ . The solution is then to use a Taylor series expansion exactly as if using the Euler method to solve for $y(t+h/2)$ :

y\left(t+{\frac {h}{2}}\right)\approx y(t)+{\frac {h}{2}}y'(t)=y(t)+{\frac {h}{2}}f(t,y(t)),

which, when plugged in (4), gives us

y(t+h)\approx y(t)+hf\left(t+{\frac {h}{2}},y(t)+{\frac {h}{2}}f(t,y(t))\right)

and the explicit midpoint method (1e).

The implicit method (1i) is obtained by approximating the value at the half step $t+h/2$ by the midpoint of the line segment from $y(t)$ to $y(t+h)$

y\left(t+{\frac {h}{2}}\right)\approx {\frac {1}{2}}{\bigl (}y(t)+y(t+h){\bigr )}

and thus

{\frac {y(t+h)-y(t)}{h}}\approx y'\left(t+{\frac {h}{2}}\right)\approx k=f\left(t+{\frac {h}{2}},{\frac {1}{2}}{\bigl (}y(t)+y(t+h){\bigr )}\right)

Inserting the approximation $y_{n}+h\,k$ for $y(t_{n}+h)$ results in the implicit Runge-Kutta method

{\begin{aligned}k&=f\left(t_{n}+{\frac {h}{2}},y_{n}+{\frac {h}{2}}k\right)\\y_{n+1}&=y_{n}+h\,k\end{aligned}}

which contains the implicit Euler method with step size $h/2$ as its first part.

Because of the time symmetry of the implicit method, all terms of even degree in $h$ of the local error cancel, so that the local error is automatically of order ${\mathcal {O}}(h^{3})$ . Replacing the implicit with the explicit Euler method in the determination of $k$ results again in the explicit midpoint method.

Notes

Süli & Mayers 2003, p. 328
Burden & Faires 2011, p. 286

References

Griffiths,D. V.; Smith, I. M. (1991). Numerical methods for engineers: a programming approach. Boca Raton: CRC Press. p. 218. ISBN 0-8493-8610-1.
Süli, Endre; Mayers, David (2003), An Introduction to Numerical Analysis, Cambridge University Press, ISBN 0-521-00794-1.
Burden, Richard; Faires, John (2010). Numerical Analysis. Richard Stratton. p. 286. ISBN 0-538-73351-9.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Süli & Mayers 2003, p. 328

[2] Burden & Faires 2011, p. 286

Numerical methods for integration
First-order methods	Euler method Backward Euler Semi-implicit Euler Exponential Euler
Second-order methods	Verlet integration Velocity Verlet Trapezoidal rule Beeman's algorithm Midpoint method Heun's method Newmark-beta method Leapfrog integration
Higher-order methods	Exponential integrator Runge–Kutta methods List of Runge–Kutta methods Linear multistep method General linear methods Backward differentiation formula Yoshida
Theory	Symplectic integrator

Midpoint method

Derivation of the midpoint method

See also

Notes

References