Solve ill-conditioned linear systems

Consider the following linear system of equations :

When solving this system using MATLAB, I found that the condition number of matrix is extremely large, indicating that the system is ill-conditioned. Some characteristics of the system are as follows:

• Condition number of A: 2.715e+06
• Determinant of A: 0.5196

I have attempted several methods, including least squares, normalization, and regularization, but none have produced satisfactory results in terms of accuracy. The matrix A and b is currently stored as double type, and I have also tried using 'vpa' to control the number of significant digits, but it was in vain. Are there any effective methods to solve this system, or is it possible to identify and eliminate highly correlated row vectors to ensure the accuracy of the remaining solutions?

Matlab data ‘.mat’:

https://1drv.ms/u/s!AlQCuPoSp7emgaNizYy43ea4fhgecg?e=vd3ubh

%% Load data
load("cal_linear_equations.mat");
%% Evaluate and calculate
DET_A=det(A_coeff);
Cond_A=cond(A_coeff);
Sol_real=A_coeff\b_coeff;
Error=A_coeff*Sol_real-b_coeff;
max(abs(Error));

Answer 1

[John D'Errico]

The determinant of a matrix is completely, totally irrelevant. Yes, I know you were taught that if it is zero, then the matrix is singular. I'm sorry, but that is numercial bullcrap. What that unknown teacher taught you in some forgotten high school class about matrices that were all nice integers is useless.

A = randn(20,20);
det(A)

ans = 7.2474e+07

A random matrix is hugely unlikely to be singular. The determinant seems to agree it is not, at least IF we believe in what it says. But what is det(10*A)? How about det(A/10)? Can just multiplying a matrix by 10 make a difference? Of course not.

det(A*10)

ans = 7.2474e+27

det(A/10)

ans = 7.2474e-13

Strange. That would lead me to conclude that just multiplying or dividing by 10 makes a difference. Is one of them singular, and the other very much not singular? Again, BULL. The determinant is a liar.

Anyway, in double precision, a condition number of 1e6 is not that terrible. Not great. But I've seen worse.

Sadly, a condition number of that size will cause a loss in your result, since it amplifies any noise in the system by a factor of 1e6. But if you are that close to the edge, you have many issues.

Can using vpa help? NO!!!!!!!!!!! Your matrix already has a condition number of 1e6. It will still have a 1e6 condition number even if you use symbolic tools. And any noise in your data already has that noise in it. There is no magic mathematical potion to get you out of this.

[Shengfan Bi]

Thank you for your detailed explanation. It has been very helpful to me. 😊

Answer 2

[Matt J]

Ill-conditioning is a property of the problem, not the method of solution. You cannot overcome it with any particular choice of algorithm. You need to add more equations to your linear system to make it less ill-conditioned.

[Shengfan Bi]

Thanks for your reply. I am trying to change the number of the equations.

Answer 3

[Catalytic]

If b has no noise in it, you could try normalizing the rows of A

a=vecnorm(A,2,2);

A=A./a;b=b./a;

x=A\b;

[Shengfan Bi]

Thank you very much for your response. I tried normalization, and the condition number decreased a bit. However, the system is still fundamentally too ill-conditioned, and mathematical methods cannot effectively solve this issue.