Methods of time discretisation for linear equation

We want to solve the following Linear Differential Equation

We need to know the values of x0 and v0. And them, we can compute the other points using the initial values

$\begin{bmatrix} t_0 \\ x_0 \\ v_0 \\ a_0 \end{bmatrix} \ \ \ \Rightarrow \ \ \ \begin{bmatrix} t_1 \\ x_1 \\ v_1 \\ a_1 \end{bmatrix} \ \ \ \Rightarrow \ \ \ \cdots \ \ \ \Rightarrow \ \ \ \begin{bmatrix} t_{n-1} \\ x_{n-1} \\ v_{n-1} \\ a_{n-1} \end{bmatrix} \ \ \ \Rightarrow \ \ \ \begin{bmatrix} t_n \\ x_n \\ v_n \\ a_n \end{bmatrix}$

Once we have a linear problem, any method below can be expressed using matrix Me and Fe like

$\begin{bmatrix}x_{i+1} \\ v_{i+1} \\ a_{i+1}\end{bmatrix} = \begin{bmatrix}M_{e}\end{bmatrix} \begin{bmatrix}x_{i} \\ v_{i} \\ a_{i}\end{bmatrix} + \begin{bmatrix}F_{e}\end{bmatrix} \begin{bmatrix}f(t_{i}) \\ f(t_{i+1}) \end{bmatrix}$

As a can be expressed in terms of x and v, we find another matrix M and F and rewrite like

$\begin{bmatrix}x_{i+1} \\ v_{i+1} \end{bmatrix} = \begin{bmatrix}M\end{bmatrix} \begin{bmatrix}x_{i} \\ v_{i}\end{bmatrix} + \begin{bmatrix}F\end{bmatrix} \begin{bmatrix}f(t_{i}) \\ f(t_{i+1}) \end{bmatrix}$

Euler description - Explicit method

We suppose that Δt is very small and so v(t) ≈ vi and a(t) ≈ ai in the interval [t_i, t_{i+1}]. Therefore we have

$\begin{align*} t_{i+1} & = t_{i} + \Delta t \\ x_{i+1} & = x_{i} + v_{i} \cdot \Delta t \\ v_{i+1} & = v_{i} + a_{i} \cdot \Delta t \\ a_{i+1} & = f(t_{i+1}) - cv_{i+1} -kx_{i+1} \end{align*}$

If we write in a matricial way, we get

$\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ k & c & 1 \end{bmatrix} \begin{bmatrix} x_{i+1} \\ v_{i+1} \\ a_{i+1} \end{bmatrix} = \begin{bmatrix} 1 & \Delta t & 0 \\ 0 & 1 & \Delta t \\ 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} x_{i} \\ v_{i} \\ a_{i} \end{bmatrix} + \begin{bmatrix} 0 & 0\\ 0 & 0 \\ 0 & 1\end{bmatrix} \begin{bmatrix} f(t_{i}) \\ f(t_{i+1}) \end{bmatrix}$

Once a can be expressed in terms of x and v

$\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} x_{i+1} \\ v_{i+1} \end{bmatrix} = \begin{bmatrix} 1 & \Delta t \\ -k\Delta t & 1 - c\Delta t \end{bmatrix} \begin{bmatrix} x_{i} \\ v_{i} \end{bmatrix} + \begin{bmatrix} 0 & 0 \\ \Delta t & 0 \end{bmatrix} \begin{bmatrix} f(t_{i}) \\ f(t_{i+1}) \end{bmatrix}$

So, in this method, we have the following matrix Me, Fe, M and F

$\begin{bmatrix} M_{e}\end{endbmatrix} = \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ k & c & 1 \end{bmatrix}^{-1} \cdot \begin{bmatrix} 1 & \Delta t & 0\\ 0 & 1 & \Delta t \\ 0 & 0 & 0 \end{bmatrix} \ \ \ \ \ \ \ \ \ \begin{bmatrix} F_{e}\end{endbmatrix} = \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ k & c & 1 \end{bmatrix}^{-1} \cdot \begin{bmatrix} 0 & 0 \\ 0 & 0 \\ 0 & 1 \end{bmatrix}$

$\begin{bmatrix} M\end{endbmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}^{-1} \cdot \begin{bmatrix} 1 & \Delta t \\ -k \Delta t & 1- c\Delta t \end{bmatrix} \ \ \ \ \ \ \ \ \ \begin{bmatrix} F\end{endbmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}^{-1} \cdot \begin{bmatrix} 0 & 0 \\ \Delta t & 0 \end{bmatrix}$

Euler description - Implicit method

The same way as for the explicit method, instead of using the value of the actual moment, we use the values which we don't know yet:

$\small \begin{align*} t_{i+1} & = t_{i} + \Delta t \\ x_{i+1} & = x_{i} + v_{i+1} \cdot \Delta t \\ v_{i+1} & = v_{i} + a_{i+1} \cdot \Delta t \\ a_{i+1} & = f(t_{i+1}) - cv_{i+1} -kx_{i+1} \end{align*}$

$\begin{bmatrix} 1 & -\Delta t & 0 \\ 0 & 1 & -\Delta t \\ k & c & 1 \end{bmatrix} \begin{bmatrix} x_{i+1} \\ v_{i+1} \\ a_{i+1} \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} x_{i} \\ v_{i} \\ a_{i} \end{bmatrix} + \begin{bmatrix} 0 & 0\\ 0 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} f(t_{i}) \\ f(t_{i+1}) \end{bmatrix}$

$\begin{bmatrix} 1 & -\Delta t \\ k\cdot \Delta t & 1 + c \cdot \Delta t \end{bmatrix} \begin{bmatrix} x_{i+1} \\ v_{i+1} \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} x_{i} \\ v_{i} \end{bmatrix} + \begin{bmatrix} 0 & 0 \\ 0 & \Delta t \end{bmatrix} \begin{bmatrix} f(t_{i}) \\ f(t_{i+1}) \end{bmatrix}$

So, in this method, we have the following matrix Me, Fe, M and F

$\small \begin{bmatrix} M_{e} \end{bmatrix} = \begin{bmatrix} 1 & -\Delta t & 0 \\ 0 & 1 & -\Delta t \\ k & c & 1 \end{bmatrix} ^{-1}\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{bmatrix} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \begin{bmatrix} F_{e} \end{bmatrix} = \begin{bmatrix} 1 & -\Delta t & 0 \\ 0 & 1 & -\Delta t \\ k & c & 1 \end{bmatrix} ^{-1}\begin{bmatrix} 0 & 0\\ 0 & 0 \\ 0 & 1 \end{bmatrix}$

$\small \begin{bmatrix} M \end{bmatrix} = \begin{bmatrix} 1 & -\Delta t \\ k \Delta t & 1 + c \Delta t \end{bmatrix}^{-1} \cdot \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \begin{bmatrix}F\end{bmatrix} = \begin{bmatrix} 1 & -\Delta t \\ k \Delta t & 1 + c \Delta t \end{bmatrix}^{-1} \begin{bmatrix} 0 & 0 \\ 0 & \Delta t \end{bmatrix}$

Generalized divided difference

Now we use two new parameters called α and β to make a linear interpolation and define the average of v and a on the interval like

$\small \begin{align*} v_{i+\alpha} & = (1-\alpha) \cdot v_{i} + \alpha \cdot v_{i+1} \\ a_{i+\beta} & = (1-\beta) \cdot a_{i} + \beta \cdot a_{i+1} \end{align*}$

And we add the contribution of a on the x equation to get

$\small \begin{align*} x_{i+1} & = x_{i} + v_{i+\alpha} \cdot \Delta t + \dfrac{1}{2}a_{i+\beta} \Delta t^2 \\ v_{i+1} & = v_{i} + a_{i+\beta} \cdot \Delta t \\ f(t_{i}) & = a_{i} + c \cdot v_{i} + k \cdot x_{i} \\ f(t_{i+1}) & = a_{i+1} + c \cdot v_{i+1} + k \cdot x_{i+1} \end{align*}$

In a matricial form

$\small \begin{bmatrix} 1 & -\alpha \Delta t & -\frac{1}{2}\beta \Delta t^2 \\ 0 & 1 & -\beta \Delta t \\ k & c & 1 \end{bmatrix} \begin{bmatrix} x_{i+1} \\ v_{i+1} \\ a_{i+1} \end{bmatrix} = \begin{bmatrix} 1 & (1-\alpha) \Delta t & \frac{1}{2}(1-\beta)\Delta t^2 \\ 0 & 1 & (1-\beta)\Delta t \\ 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} x_{i} \\ v_{i} \\ a_{i} \end{bmatrix} + \begin{bmatrix} 0 & 0 \\ 0 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} f(t_{i}) \\ f(t_{i+1})\end{bmatrix}$

Writting only in terms of x and v

$\begin{bmatrix} M_1 \end{bmatrix} \begin{bmatrix} x_{i+1} \\ v_{i+1} \end{bmatrix} = \begin{bmatrix} M_{0} \end{bmatrix} \begin{bmatrix} x_{i} \\ v_{i} \end{bmatrix} + \begin{bmatrix} M_f \end{bmatrix} \begin{bmatrix} f(t_{i}) \\ f(t_{i+1}) \end{bmatrix}$

$\begin{bmatrix} M_0 \end{bmatrix} = \begin{bmatrix} 1 - \frac{1}{2}(1-\beta)k \Delta t ^2 & (1-\alpha) \Delta t - \frac{1}{2}(1-\beta)c\Delta t^2 \\ -(1-\beta) k \Delta t & 1 - (1-\beta) c \Delta t \end{bmatrix}$

$\begin{bmatrix} M_1 \end{bmatrix} = \begin{bmatrix} 1 + \frac{1}{2} \beta k \Delta t ^2 & - \alpha \Delta t + \frac{1}{2}\beta c\Delta t^2 \\ \beta k \Delta t & 1 + \beta c \Delta t \end{bmatrix}$

$\begin{bmatrix} M_f \end{bmatrix} = -\begin{bmatrix} \frac{1}{2}(1-\beta) \Delta t^2 & \frac{1}{2}\beta \Delta t^2 \\ (1-\beta) \Delta t & \beta \Delta t \end{bmatrix}$

So, in this method, we have the following matrix Me, Fe, M and F

$\begin{bmatrix} M_{e} \end{bmatrix} = \begin{bmatrix} 1 & -\alpha \Delta t & -\frac{1}{2}\beta \Delta t^2 \\ 0 & 1 & -\beta \Delta t \\ k & c & 1 \end{bmatrix}^{-1}\begin{bmatrix} 1 & (1-\alpha) \Delta t & \frac{1}{2}(1-\beta)\Delta t^2 \\ 0 & 1 & (1-\beta)\Delta t \\ 0 & 0 & 0 \end{bmatrix}$

$\begin{bmatrix} F_{e} \end{bmatrix} = \begin{bmatrix} 1 & -\alpha \Delta t & -\frac{1}{2}\beta \Delta t^2 \\ 0 & 1 & -\beta \Delta t \\ k & c & 1 \end{bmatrix}^{-1} \begin{bmatrix} 0 & 0 \\ 0 & 0 \\ 0 & 1 \end{bmatrix}$

$\begin{bmatrix} M \end{bmatrix} = \begin{bmatrix} M_1 \end{bmatrix}^{-1} \begin{bmatrix} M_0 \end{bmatrix} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \begin{bmatrix} F \end{bmatrix} = \begin{bmatrix} M_1 \end{bmatrix}^{-1} \begin{bmatrix} M_f \end{bmatrix}$

It's nice to see that the previous cases are just this method with specific values of α and β.

So, we classify the methods with differents values of α and β.

TODO

Put Newmark's method
Put the classification of implicit/explicit methods
Put the convergence analysis and the timestep Δt stable
Show that if Δt is constant
- We need to compute the matrix M and F once
- Finding the values of x and v is just a matrix multiplication

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Methods of time discretisation for linear equation

Euler description - Explicit method

Euler description - Implicit method

Generalized divided difference

TODO

Clone this wiki locally