9.4 Gauss quadratures and summation by parts

When computing a discrete expansion in terms of orthogonal polynomials
∑N fN (x) = ˆfjpj(x) (9.61 ) j=0
one question is how to efficiently numerically approximate the coefficients ˆ {fj = ⟨pj,f⟩ω} given in Eq. (9.33View Equation). This involves computing weighted integrals of the form
∫b q(x )ω(x)dx. (9.62 ) a
If approximating the weighted integral (9.62View Equation) by a quadrature rule,
∫b N∑ q (x )ω(x)dx ≈ Aiq (xi), (9.63 ) a i=0
where the points {xi} are given but having the freedom to choose the coefficients {Ai }, by a counting argument one would expect to be able to choose the latter in such a way that Eq. (9.63View Equation) is exact for all polynomials of degree at most N. That is indeed the case, and the answer is obtained by approximating q(x ) by its polynomial interpolant (8.1View Equation) and integrating the latter,
∫ b ∫b ∑N (N) ∑N (N) q(x)ω (x )dx ≈ q(xi)ℓi (x)ω(x )dx = Ai q(xi) (9.64 ) a a i=0 i=0
where the N N {ℓi }i=0 are the Lagrange polynomials (8.3View Equation) and the coefficients
∫b A (N) = ℓ(N )(x)ω (x)dx i = 0, 1,...,N, (9.65 ) i i a
are independent of the integrand q(x). If the weight function is nontrivial, they might not be known in closed form, but since they are independent of the function being integrated they need to be computed only once for each set of nodal points {xi}. Suppose now that, in addition to having the freedom to choose the coefficients {Ai}, we can choose the nodal points {xi}. Then we have (N + 1) points and (N + 1) {Ai }, i.e., (2N + 2) degrees of freedom. Therefore, we expect that we can make the quadrature exact for all polynomials of degree at most (2N + 1). This is indeed true and is referred to as Gauss quadratures. Furthermore, the optimal choice of Ai remains the same as in Eq. (9.65View Equation), and only the nodal points need to be adjusted.

Theorem 20 (Gauss quadratures). Let ω be a weight function on the interval (a, b), as introduced in Eq. (9.17View Equation), and let p N+1 be the associated orthogonal polynomial of degree N + 1. Then, the quadrature rule (9.63View Equation) with the choice (9.65View Equation) for the discrete weights, and as nodal points {xj } the roots of pN+1 is exact for all polynomials of degree at most (2N + 1).

The following remarks are in order:

One can see that the Gauss points actually lie inside the interval (a,b), and do not contain the endpoints a or b. Now suppose that for some reason we want the nodes to include the end points of integration,

x = a, x = b. (9.66 ) 0 N
One reason for including the end points of the interval in the set of nodes is when applying boundary conditions in the collocation approach, as discussed in Section 10. Then we are left with two less degrees of freedom compared to Gauss quadratures and therefore expect to be able to make the quadrature exact for polynomials of order up to (2N + 1) − 2 = (2N − 1). This leads to:

Theorem 21 (Gauss–Lobatto quadratures). If we choose the discrete weights according to Eq. (9.65View Equation) as before but as nodal points, the Gauss–Lobatto ones, i.e., the roots of the polynomial

mN+1 (x ) = pN+1(x ) + αpN (x) + βpN −1(x), (9.67 )
with α and β chosen so that m (a) = 0 = m (b) N+1 N+1, then the quadrature rule (9.63View Equation) is exact for all polynomials of degree at most (2N − 1).

Note that the coefficients α and β in the previous equations are obtained by solving the simple system

mN+1 (a) = 0 = pN+1 (a) + αpN (a) + βpN− 1(a), mN+1 (b) = 0 = pN+1 (b) + αpN (b) + βpN −1(b).

One can similarly enforce that only one of the end points coincides with a quadrature one, leading to Gauss–Radau quadratures. The proofs of Theorems 20 and 21 can be found in most numerical analysis books, in particular [242].

For Chebyshev polynomials there are closed form expressions for the nodes and weights in Eqs. (9.63View Equation) and (9.65View Equation):

Chebyshev–Gauss quadratures.
For j = 0,1,...,N,

( ) -2j +-1- xj = − cos 2N + 2 π , (9.68 ) π A (jN)= ------. (9.69 ) N + 1

Chebyshev–Gauss–Lobatto quadratures.

( πj) xj = − cos --- , for j = 0,1,...,N, (9.70 ) N
(| π-- |{ N for j = 1,2,...,(N − 1) A(jN )= . (9.71 ) ||( -π-- 2N for j = 0 and N

Summation by parts.
For any two polynomials p(x),q(x) of degree N, in the Legendre case SBP follows for Gauss, Gauss–Lobatto or Gauss–Radau quadratures, in analogy with the FD case described in Section 8.3.

Since both products q(x)dp(x)∕dx and p(x)dq (x )∕dx are polynomials of degree (2N − 1 ), their quadratures are exact (in fact, the equality holds for each term separately):

⟨ d ⟩d ⟨ d ⟩d ⟨ d ⟩ ⟨ d ⟩ --p,q + p,---q = --p, q + p,---q , (9.72 ) dx ω dx ω dx ω dx ω
where we have introduced the discrete counterpart of the weighted scalar product (9.17View Equation),
N d ∑ ⟨h,g⟩ω := Aih (xi)g(xi), (9.73 ) i=0
with the nodes {xi } and discrete weights {Ai } those of the corresponding quadrature.

On the other hand, in the Legendre case,

⟨ d ⟩ ⟨ d ⟩ --p,q + p,---q = p(b)q(b) − p(a)q(a), (9.74 ) dx ω=1 dx ω=1
and therefore
⟨ d ⟩d ⟨ d ⟩d --p, q + p,---q = p(b)q(b) − p(a)q(a ). (9.75 ) dx ω=1 dx ω=1
Property (9.75View Equation) will be used in Section 9.7 when discussing stability through the energy method, much as in the FD case.
  Go to previous page Go up Go to next page