15
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
29
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ +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? $\endgroup$
    – Nike Dattani
    Commented Apr 13, 2021 at 21:33
  • 3
    $\begingroup$ @user1271772 It would be better to ask a new question rather than commenting under a 6 year old post. $\endgroup$
    – Federico Poloni
    Commented Apr 14, 2021 at 7:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.