1
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ Currently the system has $\operatorname{cond}(A) \approx 10^19$ and $\operatorname{rank} A = 15$ -- What do you mean exactly here? The situation you have pictured is impossible. If $\operatorname{rank} A<20$ then the system is singular and $\operatorname{cond}(A) =+\infty$ (if it is defined at all). $\endgroup$ – Federico Poloni Nov 13 '16 at 12:40
  • 2
    $\begingroup$ When he says rank(A)=15, he's saying that some numerical library with some numerical tolerance for 0 singular values came to the conclusion that the numerical rank was 15. This is about what you might expect in double precision floating point arithemtic. $\endgroup$ – Brian Borchers Nov 13 '16 at 23:54
  • $\begingroup$ @BrianBorchers Yes. That is what I mean with the statement about Vandermonde-Matrices being very ill conditioned in the general case. $\endgroup$ – Tobias Nov 14 '16 at 9:27
  • $\begingroup$ How did you solve it ? Did you precondition your matrix ? $\endgroup$ – percusse Nov 14 '16 at 10:46
3
$\begingroup$

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}$.

$\endgroup$
1
$\begingroup$

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

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.