Fourier Beyond Dispersion: Wavenumber Explicit and Precise Accuracy of FDMs for the Helmholtz Equation

Hui Zhang * · 2024

Read Fourier Beyond Dispersion: Wavenumber Explicit and Precise Accuracy of FDMs for the Helmholtz Equation by Hui Zhang * (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-12993.txt.

Introduction

Hui Zhang offers, in a 2024 preprint, a practical tool for judging how accurate finite difference methods are for the Helmholtz equation. That equation governs wave problems, and its numerical solutions are notoriously hard to certify. The usual check, dispersion analysis, measures how waves drift in the scheme. It does not measure the true error when a source term drives the problem. Zhang's tool is built on Fourier analysis and closes that gap.

For any scheme, the tool makes the order of convergence easy to read off. Better, the order comes out explicitly in terms of the wavenumber, the quantity that makes Helmholtz problems stiff. The same machinery supports rigorous proofs, not just estimates. Zhang presents the tool as a common yardstick for comparing schemes. Designers of wave solvers gain a sharper way to rank methods before trusting them.

Catalog record

CREATORHui Zhang *
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE15 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-12993

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Fourier Beyond Dispersion: Wavenumber Explicit and Precise Accuracy of FDMs for the Helmholtz Equation Hui Zhang * Abstract We propose a practical tool for evaluating and comparing the accuracy of FDMs for the Helmholtz equation. The tool based on Fourier analysis makes it easy to find wavenumber explicit order of convergence, and can be used for rigorous proof. It fills in the gap between the dispersion analysis and the actual error with source term. Keywords Fourier analysis, finite difference, Helmholtz equation, dispersion analysis, pollution effect MSC 2020 65N06, 65N12, 65N15 1 Introduction. Discretization of the Helmholtz equation suffers from the ‘pollution effect’:“the accuracy of the numerical solution deteriorates with increasing non-dimensional wave number k ” [ 3 ] . It is related to that the numerical solution “has a wavelength that is different from the exact one” [ 3 ] called ‘dispersion’. Albeit useful [ 6 , 8 , 2 ] , dispersion analysis [ 3 ] has not a trivial path to the total error estimate [ 1 ] with source term. In particular, the wavenumber explicit estimate is largely missing in the FDM literature [ 5 , 7 ] . Inspired by [ 4 ] , we propose a Fourier analysis approach to precise error estimation. We shall illustrate the approach in 1D. But it is applicable in 2D and 3D. It also provides a framework for rigorous proof of sharp error estimates. Those extensions will appear elsewhere. 2 Analysis in 1D We consider the model problem with homogeneous Dirichlet boundary condition \mathcal{H}u:=u^{\prime\prime}+k^{2}u=f\text{ in }\Omega:=(0,1),\quad u(0)=u(1)=0. (1) We assume f\in H^{p}_{0}(0,1) , p\geq 1 and k\not\in\pi\mathbb{Z} . Then ( 1 ) has a unique solution u\in H^{p+2}(0,1)\cap H^{1}_{0}(0,1) . It holds f(x)=\sum_{n=1}^{\infty}\hat{f}_{n}\sin(n\pi x),\quad\hat{f}_{n}:=2\int_{0}^{1}f(x)\sin(n\pi x)~\mathrm{d}x,\quad u(x)=\sum_{n=1}^{\infty}\hat{u}_{n}\sin(n\pi x),\quad\hat{u}_{n}:=2\int_{0}^{1}u(x)\sin(n\pi x)~\mathrm{d}x. From the equation ( 1 ), we get \hat{u}_{n}=\frac{1}{k^{2}-\xi_{n}^{2}}\hat{f}_{n}=:\hat{\mathcal{H}}_{n}^{-1}\hat{f}_{n} where \xi_{n}=n\pi . We discretize the domain (0,1) into the uniform grids \Omega_{h}:=\{x_{j}=jh,j=1,\ldots,N-1\} with h=\frac{1}{N} and N\geq 4 an integer. Denote a finite difference scheme by \mathcal{H}^{h}u^{h}=\mathcal{R}^{h}f=:f^{h} where u^{h} and \mathcal{R}^{h}f are functions on \Omega_{h} . We have the discrete Fourier transform f^{h}(x)=\sum_{n=1}^{N-1}\hat{f}^{h}_{n}\sin(n\pi x),\quad\hat{f}^{h}_{n}:=\frac{2}{N}\sum_{j=1}^{N-1}f^{h}(x_{j})\sin(n\pi x_{j}),\quad u^{h}(x)=\sum_{n=1}^{N-1}\hat{u}_{n}^{h}\sin(n\pi x),\quad\hat{u}^{h}_{n}:=\frac{2}{N}\sum_{j=1}^{N-1}u^{h}(x_{j})\sin(n\pi x_{j}),\quad (2) where the formulae of f^{h}(x) and u^{h}(x) hold originally for x\in\Omega_{h} but is also used for extended definition of f^{h}(x) and u^{h}(x) at x\in\Omega=(0,1) . From \mathcal{H}^{h}u^{h}=f^{h} , we shall be able to find \hat{u}^{h}_{n}=(\hat{\mathcal{H}}^{h}_{n})^{-1}\hat{f}_{n}^{h} . The error u-u^{h} is then u-u^{h}=\sum_{n=1}^{N-1}(\hat{u}_{n}-\hat{u}_{n}^{h})\sin(n\pi x)+\sum_{n=N}^{\infty}\hat{u}_{n}\sin(n\pi x). For simplicity, we assume the source f is well resolved on \Omega_{h} i.e. f is band limited with \hat{f}_{n}=0 for n\geq N . It follows that f and its first and high order derivatives have the Fourier expansion f(x)=\sum_{n=1}^{N-1}\hat{f}_{n}\sin(n\pi x),\quad f^{(2q)}(x)=\sum_{n=1}^{N-1}(-\xi_{n}^{2})^{q}\hat{f}_{n}\sin(n\pi x),\quad f^{(2q+1)}(x)=\sum_{n=1}^{N-1}(-1)^{q}\xi_{n}^{2q+1}\hat{f}_{n}\cos(n\pi x),\quad\xi_{n}=n\pi. An analysis including under resolved f will appear elsewhere. For band limited f , the error becomes u-u^{h}=\sum_{n=1}^{N-1}(\hat{u}_{n}-\hat{u}_{n}^{h})\sin(n\pi x)=\sum_{n=1}^{N-1}\left(\hat{\mathcal{H}}_{n}^{-1}-(\hat{\mathcal{H}}_{n}^{h})^{-1}\hat{\mathcal{R}}^{h}_{n}\right)\hat{f}_{n}\sin(n\pi x), (3) where the Fourier transform of \mathcal{R}^{h}f is supposed to be \widehat{(\mathcal{R}^{h}f)}_{n}=\hat{\mathcal{R}}^{h}_{n}\hat{f}_{n} . Theorem 1 . ? \langle 1derr \rangle ? Suppose k\not\in\pi\mathbb{Z} , f\in H^{p}_{0}(0,1) and f is band limited with the Fourier coefficients \hat{f}_{n}=0 for n\geq N for an even integer N\geq 4 . Let u be the solution of ( 1 ). Suppose a linear finite difference equation \mathcal{H}^{h}u^{h}=\mathcal{R}^{h}f on \Omega_{h} with u^{h}(0)=u^{h}(1)=0 has a unique solution u^{h} , where \Omega_{h}:=\{x_{j}=jh,j=1,\ldots,N-1\} and h=\frac{1}{N} . Let u^{h} be extended by the discrete Fourier transform to \Omega=(0,1) . Then we have \|u-u^{h}\|_{L^{2}(0,1)}\leq|f|_{H^{p}(0,1)}\max_{n=1,..,N-1}\left|\hat{\mathcal{H}}_{n}^{-1}-(\hat{\mathcal{H}}_{n}^{h})^{-1}\hat{\mathcal{R}}^{h}_{n}\right|/|\xi_{n}|^{p}, |u-u^{h}|_{H^{1}(0,1)}\leq|f|_{H^{p}(0,1)}\max_{n=1,..,N-1}\left|\hat{\mathcal{H}}_{n}^{-1}-(\hat{\mathcal{H}}_{n}^{h})^{-1}\hat{\mathcal{R}}^{h}_{n}\right|/|\xi_{n}|^{p-1}, where |v|_{H^{p}(0,1)}=\|v^{(p)}\|_{L^{2}(0,1)} is the H^{p} -semi-norm, \xi_{n}=n\pi , and both upper bounds are attainable. Proof. The first inequality follows from the Parseval’s identity in view of ( 3 ) 2\|u-u^{h}\|_{L^{2}{(0,1)}}^{2}=\sum_{n=1}^{N-1}\left|\hat{\mathcal{H}}_{n}^{-1}-(\hat{\mathcal{H}}_{n}^{h})^{-1}\hat{\mathcal{R}}^{h}_{n}\right|^{2}|\hat{f}_{n}|^{2}. The other inequalities can be proved in a similar way. ∎ Remark 1 . ? \langle f1d \rangle ? For an m th order scheme, we usually choose p=m-2 in Theorem 1 . Sometimes, it is useful to choose p=m-1 for the H^{1} -semi-norm of the error. We shall see when p\geq 1 the H^{p} -semi-norm of f does contribute extra powers of k to the upper bound, because 1) the upper bound is attained when \hat{f}_{n} is supported on the frequency where the maximum term in the upper bound is attained, and 2) the maximum term is often attained at a frequency near the wavenumber k . More precisely, if the upper bound is attained when f=\sin(\xi x) with \xi of order k then |f|_{H^{p}(0,1)} is of order k^{p} . Thus, we consider as hard as possible a Helmholtz problem for each wavenumber k . 2.1 FDMs in 1D and their symbols The baseline is of course the classical centered scheme \mathcal{H}_{cls}^{h}u^{h}:=({k}^{2}-\frac{2}{h^{2}})u^{h}(x_{j})+\frac{1}{h^{2}}u^{h}(x_{j-1})+\frac{1}{h^{2}}u^{h}(x_{j+1})=f(x_{j}),\quad x_{j}\in\Omega_{h}. Its left hand side symbol is \hat{\mathcal{H}}^{h}_{cls,n}=k^{2}-\frac{4}{h^{2}}\sin^{2}\frac{\xi_{n}h}{2} with \xi_{n}=n\pi , and right hand side symbol is \hat{\mathcal{R}}^{h}_{cls,n}=1 . It is well known that the dispersion error in 1D is avoidable; see [ 1 ] . Arbitrarily high order 3-point schemes without dispersion in 1D was derived [ 7 ] . We shall study those schemes of order 2, 4, and 6. The 2nd order dispersion free scheme reads \mathcal{H}_{df}^{h}u^{h}:={k}^{2}u^{h}(x_{j})+\frac{k^{2}}{\tilde{k}^{2}}\left[-\frac{2}{h^{2}}u^{h}(x_{j})+\frac{1}{h^{2}}u^{h}(x_{j-1})+\frac{1}{h^{2}}u^{h}(x_{j+1})\right]=f(x_{j}),\quad x_{j}\in\Omega_{h}, where \tilde{k}=\frac{2}{h}\sin\frac{kh}{2} . Its left hand side symbol is \hat{\mathcal{H}}^{h}_{df,n}=k^{2}-\frac{k^{2}}{\tilde{k}^{2}}\frac{4}{h^{2}}\sin^{2}\frac{\xi_{n}h}{2} . The fourth order dispersion free scheme uses the same left hand side operator as the second order scheme uses but different right hand side operator: \mathcal{H}_{df}^{h}u^{h}=f(x_{j})+\left(\frac{1}{\tilde{k}^{2}}-\frac{1}{k^{2}}\right)f^{\prime\prime}(x_{j})=:(\mathcal{R}_{df4}^{h}f)(x_{j}),\quad x_{j}\in\Omega_{h}. Its right hand side symbol is \hat{\mathcal{R}}^{h}_{df4,n}=1-\xi_{n}^{2}\left(\frac{1}{\tilde{k}^{2}}-\frac{1}{k^{2}}\right) . For the sixth order dispersion free scheme, the left hand side is the same as before, and the right hand side operator is (\mathcal{R}_{df6}^{h}f)(x_{j})=(\mathcal{R}_{df4}^{h}f)(x_{j})+\left[\frac{1}{k^{4}}+\left(\frac{h^{2}}{12}-\frac{1}{k^{2}}\right)\frac{1}{\tilde{k}^{2}}\right]f^{(4)}(x_{j}). So its symbol is \hat{\mathcal{R}}^{h}_{df6,n}=\hat{\mathcal{R}}^{h}_{df4,n}+\xi_{n}^{4}\left(\frac{h^{2}}{12}-\frac{1}{k^{2}}\right)\frac{1}{\tilde{k}^{2}}. 2.2 Accuracy of FDMs in 1D According to ( 3 ) and Theorem 1 , the error is essentially determined by \psi_{p}(\xi_{n}):=\left|\hat{\mathcal{H}}_{n}^{-1}-(\hat{\mathcal{H}}_{n}^{h})^{-1}\hat{\mathcal{R}}^{h}_{n}\right|/|\xi_{n}|^{p},\quad\xi_{n}=n\pi,\quad n=1,\ldots,N-1. Recall Remark 1 that if \max_{n}\psi_{p}(\xi_{n}) for the L^{2} -norm error, or \max_{n}\psi_{p-1}(\xi_{n}) for the H^{1} -semi-norm error, is attained near k then |f|_{H^{p}(0,1)} will be of order k^{p} . In that case, we shall multiply \psi_{p} or \psi_{p-1} with k^{p} to represent (up to a constant factor) the sharp upper bound of the L^{2} -norm or H^{1} -semi-norm error. This gives rise to Fig. 1 for the FDMs described in Sect. 2.1 , where p=m-2 is used for an m th order (in h ) scheme. In the first (second) column of the figure, we show \psi_{p} ( \psi_{p-1} ) for L^{2} - ( H^{1} -semi-) norm error, from which, we can see clearly how the error is distributed over the Fourier frequencies \xi_{n} . In particular, all \max_{n}\psi_{p} are attained at a \xi_{n} near k . In the third column, we present the scaling results of k^{p}\max\psi . The first row illustrates the convergence of classical scheme in term of h -refinement with fixed k , which confirms the order O(h^{2}) for both L^{2} - (indicated by \max\psi_{0} ) and H^{1} -semi- (indicated by \max\psi_{-1} ) norms of the error. Since the order in h is well-known, we shall not illustrate that for the other schemes. The second row is again for the classical scheme, but k doubles while N=h^{-1} quadruples. It is seen that \psi_{-1} converges slower than \psi_{0} in this setting. In particular, the subfigure in row 2 and column 3 shows that the order of L^{2} -norm error (indicated by \max\psi_{0} ) is k^{2}h^{2} for the Fourier interpolated u^{h} in ( 2 ), while the plots for \max\psi_{-1} needs some explanation. While k doubles and h^{-1} quadruples simultaneously, it follows that kh halves, and

Read the complete text