Solving a small non-symmetric, non-diagonally dominant, and non-sparse system

Question

I want to solve a small (20 $\times$ 20 up to 30$\times$30) system which is not symmetric, not diagonally dominant, and not sparse. Each row contains a modified form of the Legendre coefficient of a set of user specified functions. The difference between between each row is that the functions are raised to a different power (row $i$ has $[f]^i$ and row $i+1$ has $[f]^{i+1}$). Currently the system has Cond(A) ~ $10^{19}$ and for a 20$\times$20 system Rank(A) =15.

Answer 1

As I understand your question you are given a set of values $f,y\in\mathbb{R}^n$ and have to solve a system \begin{align*} \begin{pmatrix} f_1&\ldots& f_n\\ \vdots&&\vdots\\ f_1^n&\ldots& f_n^n \end{pmatrix}\cdot x &= y \end{align*} for $x\in\mathbb{R}^n$.

All of the values $f_i$ are nonzero. Otherwise your matrix would be singular and you were out of luck.

After scaling the arguments $z_i := f_i \cdot x_i$ you obtain a Vandermonde-matrix as system matrix: \begin{align*} \begin{pmatrix} 1&\ldots& 1\\ f_1&\ldots& f_n\\ \vdots&&\vdots\\ f_1^{n-1}&\ldots& f_n^{n-1} \end{pmatrix}\cdot z &= y \end{align*} Note that matrices of this kind are known to be very ill conditioned in the general case. There are special algorithms for such systems that exploit divided differences. Maybe you find even more recent variants of that algorithm by an internet search. There is also a matlab code VANDERMONDE under LGPL license that implements this method.

See also the similar question https://math.stackexchange.com/questions/384126/solving-linear-equations-with-vandermonde.

After solving that system you can scale back the solution via $x_i = \frac{z_i}{f_i}$.

Answer 2

Considering that the matrixes are not huge, but ill-conditionated you can try to use a regularization technique:

• truncated SVD (for example see link)
• Tikhonov regularization

Unlike the preconditioning techniques, where you have an equivalent system but with a better spectral properties for the matrix, here you approximate the problem, i.e. the original system.

Answer 3

Another option here would be to use high precision arithmetic to solve your system of equations. Quadruple precision floating point arithmetic should be enough to deal with your condition number of $10^{19}$ and give you an answer good to about 10 digits, assuming that all of the coefficients in your problem are accurate to 30 digits. Beyond that, there are libraries for extended precision floating point arithmetic that could be used to obtain even more digits.