# Presentation: 017579

- Time-Marching Numerical Methods

## Basics of Time-Marching Methods

- The finite-volume formulation yielded the ordinary differential equation
- This equation is non-linear in that
- 					and
- The variable *t* is *time* and indicates that the solution *   * may be time-varying
- (unsteady).  The time variable gives the equation a mathematically *hyperbolic*
- character.  That is, the solution is dependant on the solutions at previous times.
- We can use this trait to develop *time-marching numerical methods* in which we
- start with an initial solution (guess) and march the equations in time while
- applying boundary conditions.  The time-varying solution will evolve or the
- solution will asymptotically approach the steady-state solution.

## Methods for Steady Problems

- If we assume the solution is steady, and so, time is not a variable, then the
- equation takes the form
- we have at least a few other options for numerical methods:
- Iterative Methods.   These methods assume the equation is mathematically elliptic and start with an initial solution and iterate to converge to a solution.
- Direct Methods.  These methods also assume the equation is elliptic, but solve the system of equations in a single process.
- Space-Marching Methods.  These methods assume that equation can be cast as a mathematically parabolic equation in one of the coordinate directions and marched along that coordinate.  (i.e. Supersonic flows in *x*-direction).

## Time Discretization

- We will first consider time-marching numerical methods.  We first need to
- consider a *finite time step* ***t*
- where *n* is the index for time.  The **  indicates a finite step (not differential).
- A couple of concepts:
- The marching of the equation over a time step can occur over one or more *stages* and one or more *iterations*.
- The marching can be done *explicitly* or *implicitly*.  An *explicit method* uses known information to march the solution.  An *implicit method* uses known and unknown information and requires solving a local system of equations.

## Euler Methods

- To demonstrate these concepts, consider the Euler methods, both explicit and
- implict.  The methods are single-stage and first-order accurate in time.  The
- the left-hand side of the equation is discretized as
- where
- and so,
- But how to discretize     in in time?
- Explicit:                                                        Implicit:

- ( Unstable! )

## Linearization of 

- The Euler Implicit Method introduced an implicit right-hand-side term.  This
- term is approximated using a local linearization of the form
- The flux Jacobian can be defined as
- such that the Euler implicit method can be expressed as
- or
- where **I** is the identity matrix.

## Trapezoidal Time Difference

- Trapezoidal (mid-point) differencing for second-order accuracy in time:
- Make substitution of equation,
- Use linearization to form

## Three-Point Backward Time Difference

- Three-point backward differencing for second-order accuracy in time:
- This results in the form

## MacCormack Method

- An example of a multi-stage, explicit method is the MacCormack Method,
- 	Stage 1:
- 	Stage 2:
- 	and then

## Runge-Kutta Method

- Another example of a multi-stage, explicit method is the Runge-Kutta Method.
- The four stage method has the form:
- 	Stage 1:
- 	Stage 2:
- 	Stage 3:
- 	Stage 4:
- 	and then
- 	Typical coefficients are:    1 = 1/4,  2 = 1/3,  3 = 1/2,  4 =1.

## Time Step Size Control

- The size of the time step *** t* used in the time-marching methods requires
- several considerations:
- Resolution of time variation (time scale of a fluid particle).
- Stability of the numerical method.
- CFL stability condition:
-  ,   Courant-Friedrichs-Lewy (CFL) number (explicit methods generally require  < 1, but implicit methods allow larger numbers).
- x,  Resolution of the finite-volume cell.
-     ,   Eigenvalues (wave speeds).

## Time Steps, Iterations, and Cycles

- The numerical method marches the solution over a *time step* *** t*.  An *iteration*
- is the numerical process of taking a single time step.  A *cycle* is one or more
- iterations.
- Numerical errors exist in most methods that may not result in a second-order
- solution in time over one iteration.  Multiple *sub-iterations* of the numerical
- method may be needed to remove these errors.
- One such method for performing these sub-iterations is the Newton Iterative
- Method.

## Newton Iterative Method

- Consider the “standard” Newton iterative method for finding a root *f(x) = 0*,
- which can be re-written as
- 					or
- where *m* is the iteration index.  Now consider the equations we wish to solve
- and substitute them into the above form

## Newton Iterative Method (continued)

- Substituting these into the Newton iteration equation yields
- Substituting a three-point, backward time difference for the time derivative,
- applying some other small approximations, yields.
- The right-hand-side of this equation is simply the discretized form of the
- equation
- which is the equation we wish to solve.  Iterating the previous equation until the
- right-hand side becomes zero will assure that the equation is solved with the
- errors reduced.

## ADI / Approximate Factoring

- The Jacobian matrix      is three-dimensional.  We must now approximate the
- Jacobian for the finite-volume cell.   We consider a hexahedral cell with
- generalized coordinates (***, ****, ***).  We can write the Jacobian as the sum
- Substituting this into the left-hand side of the Euler Implicit Method results in
- This can be “factored” to allow a series a 3 one-dimensional numerical solutions.
- The factoring neglects third-order terms and higher and results in the form
- This approach can be applied to the other implicit methods discussed.

## ADI / AF (continued)

- The equations can then be solved in a series of one-dimensional solutions of the
- form:
- The inviscid part of the Jacobian matrices can undergo further *diagonalization* to
- form a scalar penta-diagonal system that is numerically easier to invert, and
- which reduces computational effort.  However, this reduces the implicit method
- to first-order accuracy in time.

## Solution Convergence Acceleration

- There exists several methods for accelerating the convergence of the solution
- to a steady-state solution:
- Use a uniform global CFL number which results in varying local time steps.  Thus larger time steps are used in regions of larger cells.
- Use an incrementing CFL number that starts with a small CFL number to get past initial transients then increases the CFL number to converge.
- Limit the allowable change in the solution, Q, over an iteration.
- Locally fix bad solution points by replacing the bad solution point with an average of local points.

## Other Methods Not Discussed

- Several other solution algorithms are available in WIND that have not been
- discussed:
- Jacobi Method
- Gauss-Seidel Method
- MacCormack’s First-order Modified Approximate Factorization (MAFk)
- ARC3D 3-factor Diagonal Scheme

- Next 