The central difference scheme: $$\frac{d^2u}{dx^2}=\frac{u_{n+1}-2u_i + u_{n-1}}{\Delta x^2}$$ yields a tridiagonal coefficient matrix [1 -2 1]; As the number of points gets larger, this matrix becomes ill-conditioned. Yet this is a popular discretization. Why is this scheme so commonly used when it is prone to ill-conditioning, and what is the typical workaround to the illconditoning?


TL;DR: The continuous operator exhibits this behavior, any faithful discretization will just inherit it.

Deeper cut: If you look at the spectrum (eigenpairs) of the continuous operator $\frac{d^2}{dx^2}$, the eigenvectors are trigonometric functions of the form $\cos(kx)$ and $\sin(kx)$, with eigenvalue $k^2$. Low frequency functions (ie constant or very smooth functions) can be well represented on any grid. As you refine and sample with more points, you will more closely approximate the high frequency solutions too. Therefore, basically any convergent discretization of this operator will have a nearly constant $\lambda_{min}$ eigenvalue and a $\lambda_{max}$ eigenvalue that grows quadratically with number of samples (thus, a condition number $\kappa = \lambda_{max}/\lambda_{min}$ that grows quadratically with N). So you can't really escape this fate just by fiddling around with FD schemes versus FE schemes, etc.

This is problematic for (eg) Krylov solvers or other techniques whose convergence hinges upon condition number (and therefore will take more-than-linear time complexity to solve this problem). But you can get around the issue using multiresolution analysis (especially multigrid, which can solve this problem, and many others like it, in $O(N)$ time). The convergence properties of multigrid are all based on this sort of spectral/fourier analysis.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.