On Solving the Ill-Conditioned System Ax = b: General-Purpose Conditioners Obtained From the Boundary-Collocation Solution of the Laplace Equation, Using Trefftz Expansions With Multiple Length Scales

摘要

Here we develop a general purpose pre/post conditioner T, to solve an ill-posed system of linear equations, Ax = b. The conditioner T is obtained in the course of the solution of the Laplace equation, through a boundary-collocation Trefftz method, leading to: Ty = x, where y is the vector of coefficients in the Trefftz expansion, and x is the boundary data at the discrete points on a unit circle. We show that the quality of the conditioner T is greatly enhanced by using multiple characteristic lengths (Multiple Length Scales) in the Trefftz expansion. We further show that T can be multiplicatively decomposed into a dilation T_D and a rotation T_R. For an odd-ordered A, we develop four conditioners based on the solution of the Laplace equation for Dirichlet boundary conditions, while for an even-ordered A we develop four conditioners employing the Neumann boundary conditions. All these conditioners are well-behaved and easily invertible. Several examples involving ill-conditioned A, such as the Hilbert matrices, those arising from the Method of Fundamental Solutions, those arising from very-high order polynomial interpolations, and those resulting from the solution of the first-kind Fredholm integral equations, are presented. The results demonstrate that the presently proposed conditioners result in very high computational efficiency and accuracy, when Ax = b is highly ill-conditioned, and b is noisy.