12
$\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 equation, 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.

$\endgroup$
22
$\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.

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