WENO methods
| Chi-Wang Shu (2011), Scholarpedia, 6(5):9709. | doi:10.4249/scholarpedia.9709 | revision #91939 [link to/cite this article] |
Prof. Chi-Wang Shu accepted the invitation on 4 July 2009 (self-imposed deadline: 4 January 2010).
WENO methods refers to a class of nonlinear finite volume or finite difference methods which can numerically approximate solutions of hyperbolic conservation laws and other convection dominated problems with high order accuracy in smooth regions and essentially non-oscillatory transition for solution discontinuities.
High order accurate weighted essentially non-oscillatory (WENO) schemes have gained popularity in numerical solutions of hyperbolic partial differential equations (PDEs) and other convection dominated problems. The main advantage of such schemes is their capability to achieve arbitrarily high order formal accuracy in smooth regions while maintaining stable, non-oscillatory and sharp discontinuity transitions. The schemes are thus especially suitable for problems containing both strong discontinuities and complex smooth solution features.
At the heart of the WENO schemes is actually an approximation procedure, not directly related to PDEs, hence the WENO procedure can also be used in many non-PDE applications, including computer vision and image processing.
The first WENO scheme was introduced in 1994 by Liu, Osher and Chan in their pioneering paper, in which a third order accurate finite volume WENO scheme was designed. In 1996, Jiang and Shu provided a general framework to construct arbitrary order accurate finite difference WENO schemes, which are more efficient for multi-dimensional calculations. Most of the applications use the fifth order accurate WENO scheme designed by Jiang and C.-W. Shu 1996.
As mentioned before, at the heart of the WENO schemes is actually an approximation procedure, not directly related to PDEs. We use the following simple problem of interpolation to describe this approximation procedure. Assume that we are given a uniform mesh \(\cdots < x_1 < x_2 < x_3 < \cdots\) and the point values of a function \(u_i = u(x_i)\ .\) We would like to find an approximation of the function \(u(x)\) at a point other than the nodes \(x_i\ ,\) for example at the half nodes \(x_{i+\frac 12}\ .\)
This can be handled by the traditional approach of interpolation. For example, we could find a unique polynomial of degree at most two, denoted by \(p_1(x)\ ,\) which interpolates the function \(u(x)\) at the mesh points in the stencil \(S_1 = \{ x_{i-2}, \, x_{i-1}, \, x_{i} \}\ .\) We could then use \(u^{(1)}_{i+\frac 12} \equiv p_1(x_{i+\frac 12})\) as an approximation to the value \(u(x_{i+\frac 12})\ ,\) which is given explicitly as \[\tag{1} u^{(1)}_{i+\frac 12} = \frac{3}{8} u_{i-2} - \frac{5}{4} u_{i-1} + \frac{15}{8} u_{i} \]
and is third order accurate \[ u^{(1)}_{i+\frac 12} - u(x_{i+\frac 12}) = O(\Delta x^3) \] if the function \(u(x)\) is smooth in the stencil \(S_1\ .\) Similarly, if we choose a different stencil \(S_2 =\{ x_{i-1}, \, x_{i}, \, x_{i+1} \}\ ,\) we would obtain a different interpolation polynomial \(p_2(x)\) satisfying \(p_2(x_j)=u_j\) for \(j=i-1, \, i, \, i+1\ .\) We then obtain a different approximation \(u^{(2)}_{i+\frac 12} \equiv p_2(x_{i+\frac 12})\) to \(u(x_{i+\frac 12})\ ,\) given explicitly as \[\tag{2} u^{(2)}_{i+\frac 12} = -\frac{1}{8} u_{i-1} + \frac{3}{4} u_{i} + \frac{3}{8} u_{i+1} , \]
which is also third order accurate \[ u^{(2)}_{i+\frac 12} - u(x_{i+\frac 12}) = O(\Delta x^3) \] provided that the function \(u(x)\) is smooth in the stencil \(S_2\ .\) Finally, a third stencil \(S_3 =\{ x_{i}, \, x_{i+1}, \, x_{i+2} \}\) would lead to yet another different interpolation polynomial \(p_3(x)\ ,\) satisfying \(p_3(x_j)=u_j\) for \(j=i, \, i+1, \, i+2\) and giving another approximation \(u^{(3)}_{i+\frac 12} \equiv p_3(x_{i+\frac 12})\ ,\) or explicitly as \[\tag{3} u^{(3)}_{i+\frac 12} = \frac{3}{8} u_{i} + \frac{3}{4} u_{i+1} - \frac{1}{8} u_{i+2} , \]
which is of course also third order accurate \[ u^{(3)}_{i+\frac 12} - u(x_{i+\frac 12}) = O(\Delta x^3) \] provided that the function \(u(x)\) is smooth in the stencil \(S_3\ .\)
If the function \(u(x)\) is globally smooth, all three approximations \(u^{(1)}_{i+\frac 12}\ ,\) \(u^{(2)}_{i+\frac 12}\) and \(u^{(3)}_{i+\frac 12}\) obtained above are third order accurate. One could choose one of them based on other considerations, e.g. smallest local errors or stability.
If we use the large stencil \(S= \{x_{i-2}, \, x_{i-1}, \, x_{i}, \, x_{i+1}, \, x_{i+2} \}\ ,\) which is the union of all three third order stencils \(S_1\ ,\) \(S_2\) and \(S_3\ ,\) then we would be able to obtain an interpolation polynomial \(p(x)\) of degree at most four, satisfying \(p(x_j)=u_j\) for \(j=i-2, \, i-1, \, i, \, i+1, \, i+2\ ,\) and giving an approximation \(u_{i+\frac 12} \equiv p(x_{i+\frac 12})\ ,\) or explicitly as \[\tag{4} u_{i+\frac 12} = \frac{3}{128} u_{i-2} - \frac{5}{32} u_{i-1} + \frac{45}{64} u_{i} + \frac{15}{32} u_{i+1} - \frac{5}{128} u_{i+2} , \]
which is fifth order accurate \[ u_{i+\frac 12} - u(x_{i+\frac 12}) = O(\Delta x^5) \] provided that the function \(u(x)\) is smooth in the large stencil \(S\ .\)
An important observation, which is at the heart of the WENO procedure, is that the fifth order approximation \(u_{i+\frac 12}\ ,\) defined in (4) and based on the large stencil \(S\ ,\) can be written as a linear convex combination of the three third order approximations \(u^{(1)}_{i+\frac 12}\ ,\) \(u^{(2)}_{i+\frac 12}\) and \(u^{(3)}_{i+\frac 12}\ ,\) defined by (1), (2), (3) and based on the three small stencils \(S_1\ ,\) \(S_2\) and \(S_3\) respectively: \[\tag{5} u_{i+\frac 12} = \gamma_1 u^{(1)}_{i+\frac 12} + \gamma_2 u^{(2)}_{i+\frac 12} + \gamma_3 u^{(3)}_{i+\frac 12} \]
where the constants \(\gamma_1\ ,\) \(\gamma_2\) and \(\gamma_3\ ,\) satisfying \(\gamma_1 + \gamma_2 + \gamma_3=1\ ,\) are usually referred to as the linear weights in the WENO literature. In this case they are given as \[ \gamma_1= \frac{1}{16}, \qquad \gamma_2= \frac{5}{8}, \qquad \gamma_3= \frac{5}{16} . \]
If the function \(u(x)\) is smooth in the big stencil \(S\ ,\) then all three third order approximations \(u^{(1)}_{i+\frac 12}\ ,\) \(u^{(2)}_{i+\frac 12}\) and \(u^{(3)}_{i+\frac 12}\) can be used, as well as the fifth order approximation \(u_{i+\frac 12}\) given by (4) or by (5). However, if the function \(u(x)\) has a discontinuity point in \([x_{i-2}, x_{i+2}]\ ,\) then not all three approximations are equally good. The classical ENO idea by Harten, Engquist, Osher and Chakravarthy (1987) is to choose one of the three approximations \(u^{(1)}_{i+\frac 12}\ ,\) \(u^{(2)}_{i+\frac 12}\) and \(u^{(3)}_{i+\frac 12}\ ,\) defined by (1), (2), (3) and based on the three stencils \(S_1\ ,\) \(S_2\) and \(S_3\) respectively, using the information of the local smoothness of the given data \(u_j\) for \(i-2 \leq j \leq i+2\ ,\) measured by divided differences. This would guarantee third order accuracy and essentially non-oscillatory performance if \(u(x)\) is smooth in at least one of the three stencils \(S_1\ ,\) \(S_2\) and \(S_3\ .\)
On the other hand, the WENO idea is to choose the final approximation as a convex combination of the three third order approximations \(u^{(1)}_{i+\frac 12}\ ,\) \(u^{(2)}_{i+\frac 12}\) and \(u^{(3)}_{i+\frac 12}\ :\) \[\tag{6} u_{i+\frac 12} = w_1 u^{(1)}_{i+\frac 12} + w_2 u^{(2)}_{i+\frac 12} + w_3 u^{(3)}_{i+\frac 12} \]
where \(w_j \geq 0\ ,\) \(w_1 + w_2 + w_3 =1\ .\) We would hope that the nonlinear weights \(w_j\) satisfy the following requirements
- \(w_j \approx \gamma_j\) if \(u(x)\) is smooth in the big stencil \(S\ .\)
- \(w_j \approx 0\) if \(u(x)\) has a discontinuity in the stencil \(S_j\)
but it is smooth in at least one of the other two stencils.
The choice of the nonlinear weights \(w_j\) relies on the smoothness indicator \(\beta_j\ ,\) which measures the relative smoothness of the function \(u(x)\) in the stencil \(S_j\ .\) The larger this smoothness indicator \(\beta_j\ ,\) the less smooth the function \(u(x)\) is in the stencil \(S_j\ .\) In most of the WENO papers, this smoothness indicator is chosen as in the paper by Jiang and Shu (1996), \[\tag{7} \beta_j = \sum_{l=1}^{k} \Delta x^{2l-1} \int_{x_{i-\frac 12}}^{x_{i+\frac 12}} \left( \frac{d^l}{dx^l} p_j(x) \right)^2 \, dx \]
where \(k\) is the polynomial degree of \(p_j(x)\) (in our example \(k=2\)). This is clearly just a scaled sum of the square \(L^2\) norms of all the derivatives of the relevant interpolation polynomial \(p_j(x)\) in the relevant interval \([x_{i-\frac 12}, x_{i+\frac 12}]\) where the interpolating point is located. In our example, we can easily work out these explicit formulas as \[\tag{8} \begin{array}{l} \beta_1 = \frac{1}{3} \left( 4 u_{i-2}^2-19u_{i-2}u_{i-1}+25u_{i-1}^2+11u_{i-2}u_i -31u_{i-1}u_i+10u_i^2 \right) \\ \beta_2 = \frac{1}{3} \left( 4u_{i-1}^2-13u_{i-1}u_i+13u_i^2+5u_{i-1}u_{i+1} -13u_iu_{i+1}+4u_{i+1}^2 \right) \\ \beta_3 = \frac{1}{3} \left( 10u_i^2-31u_iu_{i+1}+25u_{i+1}^2+11u_iu_{i+2} -19u_{i+1}u_{i+2}+4u_{i+2}^2 \right) \end{array} \]
Equipped with these smoothness indicators, we can now define the nonlinear weights as \[\tag{9} w_j = \frac{\tilde{w}_j}{\tilde{w}_1 + \tilde{w}_2 + \tilde{w}_3}, \qquad \mbox{with} \quad \tilde{w}_j =\frac{\gamma_j}{(\varepsilon + \beta_j)^2} . \]
Here \(\varepsilon\) is a small positive number to avoid the denominator to become zero and is typically chosen as \(\varepsilon = 10^{-6}\) in actual calculations.
The WENO procedure has been generalized and applied to various types of schemes (finite difference, finite volume, compact schemes, residual distribution schemes, limiters for the discontinuous Galerkin schemes, etc.), and have been applied to various fields including computational fluid dynamics, computational astronomy and astrophysics, semiconductor device simulation, traffic flow models, and computational biology. For a recent review of WENO schemes, we refer to the paper by Shu (2009). For more details of the WENO procedure, we refer to the lecture notes by Shu (1998).
References
- A. Harten, B. Engquist, S. Osher and S. Chakravarthy, Uniformly high order essentially non-oscillatory schemes, III, Journal of Computational Physics, 71:231-303, 1987.
- G. Jiang and C.-W. Shu, Efficient implementation of weighted ENO schemes, Journal of Computational Physics, 126:202-228, 1996.
- X.-D. Liu, S. Osher and T. Chan, Weighted essentially non-oscillatory schemes, Journal of Computational Physics, 115:200-212, 1994.
- C.-W. Shu, Essentially non-oscillatory and weighted essentially non-oscillatory schemes for hyperbolic conservation laws, Advanced Numerical Approximation of Nonlinear Hyperbolic Equations, B. Cockburn, C. Johnson, C.-W. Shu and E. Tadmor (Editor: A. Quarteroni), Lecture Notes in Mathematics, volume 1697, Springer, 325-432, 1998.
- C.-W. Shu, High order weighted essentially non-oscillatory schemes for convection dominated problems, SIAM Review, 51:82-126, 2009.
