# Is there a meaningful distinction between “direct” and “iterative” methods for solving equations?

I'll motivate this question with an example.

The Abel-Ruffini theorem states that there is no general "formula" for the roots of polynomials of degree greater than 4. (Specifically it states that there is no solution that can be expressed in terms of radicals.) This lack of a direct formula means that, in order to compute the roots for e.g. a generic quintic, we have must resort to iterative root-finding algorithms.

The distinction occurs in other problems as well, such as in linear algebra. "Direct" techniques use a "formula", whereas "indirect" techniques iterate until convergence. Same thing for the solutions of ordinary linear differential equations—which have direct "formulas" in terms of complex exponentials—and other systems, which don't.

But as much as I like to pretend I understand that, I simply don't understand the distinction between direct and iterative methods. The way I see it, pretty much every numerical method is iterative—even computing square roots requires an iterative method such as Newton's method in order to converge to the answer with the error bounded by a desired tolerance ϵ. I just don't see why it's such a big deal that there is no "formula" for quintics—even if there were, the computer would still have to use an iterative method like Newton's method until it converged anyway. And I'm not even sure how to make a meaningful definition for the word "formula" to distinguish between the two in the first place.
So where exactly is the distinction and why is it such a big deal?

• The distinction is exactly what you say in your question: an iterative method is not a formula expressed in radicals. If I say $x=1+\sqrt 2$ I have expressed $x$ using a formula expressed in radicals. If I say "$x$ is the limit of $x_{n+1}=f(x_n)$ when $x_0\in[-1, 2]$, I haven't. – Jack M Jan 4 '16 at 10:13
• @JackM: That addresses the distinction but not why it's a big deal (or even a useful or interesting one to make at all), at least from a numerical standpoint. – user541686 Dec 3 '16 at 11:48

With iterative methods, you always update your old guess and get (hopefully) a bit closer to the true solution. This means that you can decide how much work you want to invest depending on how accurate you need your solution. For instance, CG is known to converge to the exact solution in $n$ steps for a matrix of size $n$, and was historically first seen as a direct method because of this. However, after a while people figured out that it works really well if you just stop the iteration much earlier - often you will get a very good approximation after much fewer than $n$ steps. In fact, we can analyze how fast CG converges. The end result is that CG is used as an iterative method for large linear systems today.