Overview of Godunov's Method

I am studying Godunov's method and I am unclear on a few details, it seems there are not many resources available regarding this method (at least to my knowledge).

Suppose we have: $$v_t + [f(v)]_x = 0$$ which we are solving on some grid. We denote the solution on this grid as $u_j^n$, which represents the solution at $j\Delta x$ and at time $n\Delta t$.

Before even getting into Godunov's method, I am confused on implementing the grid suggested by most texts, which claim it is more natural to instead consider $$U_j^n = \frac{1}{\Delta x}\int_{x_{j-1/2}}^{x_{j+1/2}} u_j^n$$ but how is this implemented in practice? If are grid is $x_j$ for $j = 0, 1, 2, \ldots, n$, how do we deal with these half points exactly?

Now, for Godunov's method, it is my understanding that we suppose we have a solution at time $n$ which we call $\tilde{u}^n(x, t_n)$. This solution is piecewise constant at time $n$ as it simply the value of our numerical solution over each particular cell $[x_{j-1/2}, x_{j+1/2})$. To obtain the solution at time $n+1$ we use $\tilde{u}(x, t_n)$ as initial data and solve the resulting sequence of Riemann problems.

Assuming the above is correct, I have two questions that follow. First, how do we solve these Riemann problems exactly? The texts I have seen claim that this is trivial since the resulting fluxes contain integrals of constants. Second, at each cell edge we have two solutions, one to the right and one to the left. Which do we use when solving these Riemann problems?

I cannot wrap my head around a "general" way to do this, so to speak. It seems like any code using the Godunov method will be heavily dependent on the flux function $f$.

Solution 1:

For a general finite volume scheme, the definition for the cell averages should be $$ U_j^n = \frac{1}{\Delta x} \int_{x_{j-1/2}}^{x_{j+1/2}} v(x,t_n)\, dx $$ where $v(x,t)$ solves the PDE and the cell boundaries are located at $x_{j\pm 1/2} = (j\pm \frac12)\, \Delta x$. This way, if we define the average flux at the cell boundary $x_{j+1/2}$ as follows $$ F_{j + 1/2} = \frac{1}{\Delta t} \int_{t_n}^{t_{n+1}} f\big(v(x_{j+ 1/2},t)\big)\, dt \, , $$ then the conservation law implies $$ U_{j}^{n+1} = U_j^n - \frac{\Delta t}{\Delta x} \left(F_{j + 1/2} - F_{j - 1/2}\right) . $$ The Godunov method amounts to a specific approximation of $F_{j \pm 1/2}$, but other choices are possible (see for instance the Lax-Friedrichs method).

Your description of Godunov's method sounds correct to me. In some texts, we call this formulation the reconstruct-evolve-average (REA) scheme (1). Thus we define the piecewise constant reconstruction $\tilde u^n$ of $v(\cdot ,t_n)$ such that $\tilde u^n(x,t_n)$ equals $U_j^n$ over each cell $[x_{j-1/2}, x_{j+1/2})$. To evolve the solution from $t_n$ to $t_{n+1}$ in an exact fashion, we need to solve the Riemann problems at the cell interfaces $x=x_{j + 1/2}$ with data $U_{j}^n$ on the left and $U_{j+1}^n$ on the right. By invariance under spatial translation, we can rewrite this Riemann problem about $x=0$. If $f$ does not have any inflection point (e.g. $f$ is a convex function), then the Riemann solution is either a shock wave or a rarefaction wave. In both cases, the value along the cell interface is constant over times $t > t_n$, and we have $$ \tilde u^n(x_{j+1/2}, t_{n+1}) = \begin{cases} U_j^n , & \text{if}\quad f'(U_j^n), f'(U_{j+1}^n) \geq 0, \\ &\text{or if}\quad f'(U_j^n) \geq 0 \geq f'(U_{j+1}^n), \quad s>0 , \\ U_{j+1}^n , & \text{if}\quad f'(U_j^n), f'(U_{j+1}^n) \leq 0, \\ &\text{or if}\quad f'(U_j^n) \geq 0 \geq f'(U_{j+1}^n), \quad s<0 , \\ (f')^{-1}(0), & \text{if}\quad f'(U_j^n) < 0 < f'(U_{j+1}^n) , \end{cases} $$ where $s \, (U_{j+1}^n - U_j^n) = f(U_{j+1}^n) - f(U_{j}^n)$ defines the shock wave speed $s$ according to the Rankine-Hugoniot condition. Therefore, the computation of the numerical flux $F_{j+1/2}$ amounts to averaging a constant function over one time step. In other words, we have $$F_{j+1/2} = f\big(\tilde u^n(x_{j+1/2},t_{n+1})\big) \, .$$

(1) R. J. LeVeque, Numerical Methods for Conservation Laws, Birkhäuser Verlag, 1992. doi:10.1007/978-3-0348-8629-1