Finite difference method

Finite difference methods ( FDM for short ), also methods of finite differences,  are a class of  numerical  methods for solving  ordinary  and  partial differential equations .

The basic idea of ​​the procedure is to approximate the local derivatives in the differential equation at a finite number of (= "finite"), equidistant grid points using difference quotients. The approximated solutions of the differential equation at the grid points can then be calculated using the corresponding system of equations.

Processes of this type are widely used in  fluid dynamic  simulations , for example in  meteorology  and  astrophysics . The difference method is used to a certain extent in  structural engineering . As early as 1904, Friedrich Bleich analyzed the continuous beam; In 1909 Lewis Fry Richardson examined elastic disks and in 1919 Henri Marcus examined elastic plates using the difference method.

A special finite difference method for the numerical solution of the heat conduction equation   is the  Crank-Nicolson method .

Lewis Fry Richardson ,  Richard Southwell ,  Richard Courant ,  Kurt Friedrichs ,  Hans Lewy ,  Peter Lax  and  John von Neumann are among the pioneers of the finite difference method for partial differential equations  .

Example for the numerical solution of an ordinary differential equation

The boundary value problem is given

${\displaystyle u''(x)=2}$  For   ${\displaystyle \quad x\in [0;1]\,,}$

${\displaystyle u(0)=u(1)=3\,.}$

The solution function can be calculated exactly here . ${\displaystyle u\colon [0;1]\to \mathbb {R} }$ ${\displaystyle u(x)=3+x(x-1)}$

For the solution with the difference method, the interval is discretized by the grid points for with the mesh size . The second derivative is discretized using the central difference quotients of the second derivative ${\displaystyle [0;1]}$ ${\displaystyle x_{i}=i\cdot h}$ ${\displaystyle i=0,\ldots ,n+1}$ ${\displaystyle h={\tfrac {1}{n+1}}}$

${\displaystyle u''(x)\approx {\frac {u(x-h)-2u(x)+u(x+h)}{h^{2}}}\ .}$

This gives the difference equations at the inner grid points

${\displaystyle {\frac {1}{h^{2}}}(u_{i-1}-2u_{i}+u_{i+1})=2}$  For   ${\displaystyle i=1,\ldots ,n}$

for the numerical approximate values ​​of the solution values . Using the given boundary values and this is a linear system of equations with equations for the unknowns . ${\displaystyle u_{i}}$ ${\displaystyle u(x_{i})}$ ${\displaystyle u_{0}=u(0)=3}$ ${\displaystyle u_{n+1}=u(1)=3}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle u_{1},\ldots ,u_{n}}$

In matrix form , the system to be solved is here:

${\displaystyle {\frac {1}{h^{2}}}{\begin{pmatrix}-2&1&0&\dots &0\\1&-2&1&\ddots &\vdots \\0&1&\ddots &\ddots &0\\\vdots &\ddots &\ddots &\ddots &1\\0&\dots &0&1&-2\end{pmatrix}}{\begin{pmatrix}u_{1}\\u_{2}\\u_{3}\\\vdots \\u_{n}\end{pmatrix}}={\begin{pmatrix}2-{\frac {3}{h^{2}}}\\2\\2\\\vdots \\2-{\frac {3}{h^{2}}}\end{pmatrix}}}$

Since a maximum of three unknowns occur in each line, it is a system with a sparse coefficient matrix , more precisely a system with a tridiagonal Toeplitz matrix .

Example for the numerical solution of a partial differential equation

In the following, the numerical solution of the heat conduction equation is considered in a restricted area : ${\displaystyle \Omega }$

${\displaystyle \partial _{t}u-\Delta u=f~~{\text{in }}(0,T)\times \Omega ,~f\in C^{0}((0,T)\times \Omega ),}$

${\displaystyle u(t,\cdot )=0~{\text{ auf }}\partial \Omega ,}$

${\displaystyle u(0,\cdot )=u_{0}{\text{ in }}\Omega .}$

Numerical solution in 1D

In the 1D case there is a bounded interval. Since in this case only a spatial derivative is considered, the heat conduction equation can be written as follows: ${\displaystyle \Omega =(a,b)}$

${\displaystyle \partial _{t}u-\partial _{xx}u=f}$

Discretization

In order to be able to use the finite difference method, the interval must first be divided into a finite number of sub-intervals. For this purpose, equidistant sampling points used: ${\displaystyle \Omega }$ ${\displaystyle N+2}$

${\displaystyle x_{0}=a,~x_{N+1}=b,~x_{i}=a+i\cdot {\frac {b-a}{N+1}}}$, for . ${\displaystyle i=0,\ldots ,N+1}$

The grid width of this discretization is therefore . According to the assumption, the function you are looking for disappears at the boundary values , i.e. H. so that these values ​​do not have to be considered further. This allows the function evaluations to be displayed as a vector in the support points : ${\displaystyle h={\frac {b-a}{N+1}}}$ ${\displaystyle u}$ ${\displaystyle u(x_{0})=u(x_{N+1})=0}$ ${\displaystyle u}$ ${\displaystyle \mathbb {R} ^{N}}$

${\displaystyle U_{h}=(u_{1}(t),\dots ,u_{N}(t))^{T}}$

Approximation of the derivative

The second derivative of the location can now be approximated at the support points by second order difference quotients: ${\displaystyle u}$

${\displaystyle \partial _{xx}u(t,x_{i})\approx {\frac {u(t,x_{i+1})-2u(t,x_{i})+u(t,x_{i-1})}{h^{2}}}}$

If the heat conduction equation is rearranged, the following system of ordinary first-order differential equations results: ${\displaystyle \partial _{t}u}$

${\displaystyle {\dot {U}}_{h}(t)=-A_{h}U_{h}+f_{h}}$

where and . ${\displaystyle f_{h}:=(f(t,x_{1}),\dots ,f(t,x_{N}))^{T}}$ ${\displaystyle A_{h}:={\frac {1}{h^{2}}}{\begin{pmatrix}2&-1&0&\dots &0\\-1&2&-1&\dots &0\\0&\ddots &\ddots &\ddots &\vdots \\0&\dots &\dots &-1&2\end{pmatrix}}}$

This system can now by any method for solving ordinary differential equations, such as B. the Runge-Kutta method or the Euler method can be solved. 

Goodness of the approximation

A finite difference method generates a linear system of equations (analogous to the equation in the example chapter )

${\displaystyle A_{h}u_{h}=b_{h},}$

where is the numerical approximation of the solution and should explicitly represent the dependence on the grid. Let be the exact solution and the finite representation using . ${\displaystyle u_{h}}$ ${\displaystyle h}$ ${\displaystyle u(x)}$ ${\displaystyle U\in \mathbb {R} ^{N}}$ ${\displaystyle U_{i}=u(x_{i})}$

An FDM is called consistent of order , if there is one with ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle C_{K}>0}$

${\displaystyle \|A_{h}U-b_{h}\|\leq C_{K}h^{n}.}$

FDM is stable , if one is so for all true ${\displaystyle C_{S}>0}$ ${\displaystyle v\in \mathbb {R} ^{N}}$

${\displaystyle \|A_{h}v\|\geq C_{S}\|v\|.}$

One can show that convergence already follows from consistency and stability, that is

${\displaystyle \|U-u_{h}\|\leq {\frac {C_{K}}{C_{S}}}h^{n}.}$

literature

• Christian Großmann, Hans-Görg Roos: Numerical treatment of partial differential equations. 3. Edition. BG Teubner Verlag, Wiesbaden 2005, ISBN 3-519-22089-X .
• Stig Larsson, Vidar Thomée: Partial differential equations and numerical methods. Springer-Verlag, Berlin 2005, ISBN 3-540-20823-2 .
• Claus-Dieter Munz, Thomas Westermann: Numerical treatment of ordinary and partial differential equations. 3. Edition. Springer-Verlag, ISBN 978-3-642-24334-9

Web links

Commons : Finite Difference Method  - collection of images, videos and audio files