15

If I were to solve a relatively small problem, that is, a problem that can be handled by a direct method like LU, then does the condition number of the linear operator affect the accuracy of the solution?

One of the research problems I am working on focuses on the development of optimization techniques to solve linear systems of equations and the "issues" I am running into are that the condition numbers of the matrices can be very high.

This would be an important factor to consider if I were to use an iterative method and preconditioner, but right now I am solving small problems (less than 1M degrees of freedom), so a direct solver is appropriate for now.

Anton Menshov
  • 8,672
  • 7
  • 38
  • 94
Justin
  • 791
  • 3
  • 11

1 Answers1

29

Yes, the condition number always matters in floating-point arithmetic, whether you choose to solve your system with an iterative or direct method. The relative accuracy of an approximate solution to $Ax = b$ obtained from LU factorization with pivoting is $O(\kappa(A) \cdot \varepsilon)$, where $\varepsilon$ is the smallest floating point number such that $1 + \varepsilon > 1$ on your machine. If you're using 64-bit floats, $\varepsilon \approx 10^{-16}$, so if your matrix has a condition number of $10^{12}$ then you can only guarantee that your solution has 4 digits of accuracy.

For iterative solvers, the matrix condition number enters the show even in infinite-precision arithmetic because it often dictates the theoretical convergence rate of the algorithm. With direct solvers, this only becomes a consideration once you take into account the fact that your computer operates in finite precision.

Daniel Shapero
  • 10,263
  • 1
  • 28
  • 59
  • +1 and thanks for this valuable contribution. If I want eigenvalues of a matrix with condition number $\kappa=10^n$ and I'm using floating-point arithmetic with precision $\epsilon \approx 10^{-m}$, is it the case that we can only guarantee the eigenvalues are accurate to $(m-n)$ digits? Are there any references that discuss this? – Nike Dattani Apr 13 '21 at 21:33
  • 3
    @user1271772 It would be better to ask a new question rather than commenting under a 6 year old post. – Federico Poloni Apr 14 '21 at 07:13