Effective condition number for finite difference method (Q2433793)

Solving linear algebraic equations \(Ax = b\) the user is interested in error bounds which are characterized by the condition number \(\kappa\). Especially in the case, where \(A \in {\mathbb R}^{n \times n}\) is symmetric positive definite and \(x,b \in {\mathbb R}^n\) are the unknown and the known vectors, respectively, the well-known traditional condition number in the 2-norm is defined by \(\kappa={\lambda_1}/{\lambda_n}\), \(\lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_n > 0\), \(\lambda_i \in \sigma{\{A\}}\), \(i = 1,\dots,n\), \(\sigma\) spectrum of \(A\). Because such a \(\kappa\) is the worst case of all rounding errors and perturbations of \(b\) the authors treat so-called effective condition numbers already considered by \textit{T. F. Chan} and \textit{D. E. Foulser} [SIAM J. Sci. Statist. Comput. 9, 963--969 (1988; Zbl 0664.65041)] which may be much smaller and more realistic for the given problems. The new simplified effective condition numbers can be calculated using only the eigenvector \(u_n\) corresponding to the minimal eigenvalue \(\lambda_n\) of \(A\). \(u_n\) can be easily computed by the inverse power method. The results are also extended to overdetermined systems. The main part of the paper is the application of the effective condition numbers to linear algebraic equations derived by a finite difference method choosing the Shortley-Weller difference approximation for the Poisson's equation not supposing quasiuniform grids. For homogeneous boundary conditions the effective condition number is proven to be \(O(1)\) under a non-orthogonality assumption by contrast to the traditional condition number \(\kappa = O(h_{\min}^{-2})\), where \(h_{\min}\) is the minimal meshspacing of the grid. For non-homogeneous Neumann and Dirichlet boundary conditions effective condition numbers \(O(h^{-1/2})\) and \(O(h^{-1/2}h_{\min}^{-1})\), respectively, are derived, where \(h\) is the maximal meshsize of the difference grid. The results are validated by comprehensive numerical experiments choosing the Poisson's equation \(-\Delta u = f\) in \(S = \{(x,y) \enspace | \enspace 0 \leq x \leq 1, \enspace 0 \leq y \leq 1\}\) for homogeneous and non-homogeneous Dirichlet and Neumann boundary conditions with given analytical solutions.