2
$\begingroup$

While I was studying numerical methods and optimizations recently, I observed that whenever we find a root to an equation or a system of linear equations, we always find approximate roots. However, we already have algorithms for finding exact roots.

For example, the Gauss-Seidel or Gauss-Jacobi methods of iterative solution tend to find the "most correct" approximate root to the system of linear equations, although we can find exact roots to a system of linear equations through algorithms such as Gauss elimination or Gauss-Jordan method.

What is the reason to use approximation methods when we can find exact roots?

$\endgroup$
  • 2
    $\begingroup$ Because there are some equations for which these methods don't work, and we can't find exact roots. $\endgroup$ – John Doe Apr 11 at 14:53
  • 2
    $\begingroup$ Exact solutions can only be found for an extremely small set of equations. $\endgroup$ – MPW Apr 11 at 14:53
  • $\begingroup$ 2 things I can think of as possible answers. For one, maybe the approximation methods are much faster for large problems. Or maybe there are certain optimization problems that have no algorithmic solution, or one that takes way too long to run $\endgroup$ – NazimJ Apr 11 at 14:54
  • 1
    $\begingroup$ You mention root(s) of an equation once and root(s) of a linear system for the rest of your question; the various named methods you use are for linear systems. Are you interested in finding roots of a polynomial, solutions to linear systems, or both? $\endgroup$ – Eric Towers Apr 11 at 14:56
  • 1
    $\begingroup$ Do we? Can you find the exact roots of any quintic polynomial? $\endgroup$ – Rodrigo de Azevedo Apr 11 at 20:11
1
$\begingroup$

There are at least two important reasons.

First, iterative methods can be significantly faster, and as there are a lot of problems with big systems (hundreds of thousands or more variables), speed can be important. Also, precise methods usually can't take advantage of sparsity, which is common case too.

Second, we usually use finite-precision floating point numbers, so we have to deal with rounding errors, which tend to accumulate in precise methods more. For example, in Gauss elimination, if you get a row slightly wrong, it will affect all subsequent rows. As in iterative methods the "main part" doesn't change, they are (usually) less susceptible to it.

$\endgroup$
  • 1
    $\begingroup$ Please explain "which tend to accumulate in precise methods more". $\endgroup$ – Rodrigo de Azevedo Apr 11 at 20:08
0
$\begingroup$

If I understand your question correctly, the approximation help in terms of calculating the computational complexity. In particular, you effectively reduce the number of operations Flops calculations when you use such approximations.

I hope this help.

Best.

$\endgroup$
0
$\begingroup$

For polynomials: almost no polynomial's roots can be expressed exactly. All linear, quadratic, cubic and quartic polynomials can be factored exactly. The generic case for quintics is similar to that for $x^5 + x + 5$, whose five roots are not expressible using any finite expression of sums, differences, products, quotients, or rational powers of rational numbers. (They can be expressed using Jacobi elliptic functions, which can only be evaluated exactly for very special arguments.) For more on this see solvability by radicals in Galois theory. Generically, for degree above four, nearly all polynomials are not solvable by radicals. As a consequence, the only way forward is to find approximate roots.

Now to linear systems of equations.

There are two resources that any algorithm requires: time and space. For matrix algorithms, it is typical to express the complexities as functions of the size of the matrix. For $n \times n$ matrices, the size is $n$. Also, real implementations of algorithms can increase or decrease the resource usage by nearly constant multiplicative factors. (Implementing on this hardware may be twice as fast as that hardware. Using this representation of the numbers may use ten times as much space as using that representation.) Consequently, constant multipliers are typically ignored when calculating and reporting time complexity -- the "$2$" in "$2 n^2$" is meaningless when we can get a factor of $2$ just by moving to a different computing device. We indicate that we are ignoring constant multipliers by using big O notation. Also, efficiency is largely irrelevant for small problem sizes, we typically think of $n$ as being large. Consequently, although a detailed accounting of resource usage may show, for instance, usage of $\frac{2}{3}n^3 + \frac{3}{2}n^2 - \frac{7}{6}n$ units of a resource, this is reported as $O(n^3)$ because, for large $n$, the lower order terms are irrelevant and as already noted, the leading coefficient is irrelevant.

The following are widely reported, so I don't provide specific citations. We report space complexity assuming floating point representations. (Use of exact representations in the worst case lead to exponential space consumption.)

Gaussian elimination and Gauss-Jordan elimination have time complexity $O(n^3)$ and space complexity $O(n^2)$.

(Gauss-)Jacobi iteration has time complexity $O(n^2)$ and space complexity $O(n^2)$.

Gauss-Seidel has time complexity $O(n^2)$ and space complexity $O(n^2)$.

For these algorithms, space complexity is not a concern. However, time complexity does vary. So, suppose we have a problem instance with $n = 10^6$. (This is not actually so large, but is illustrative.) Then we can expect the ratio of time required for Gauss or Gauss-Jordan to the time required for Gauss-Jacobi or Gauss-Seidel to be $$ \frac{(10^6)^3}{(10^6)^2} = 10^6 \text{.} $$ That is, the approximate algorithms are about a million times faster for this problem.

There are additional considerations. For instance, we are discussing calculations using floating point numbers. Such representations have finite precision, so long calculations risk accumulation of error, sometimes to the point that the "solution" returned by the algorithm is garbage. We capture this by describing for which inputs the algorithm is "stable". If the algorithm is stable for a particular input, accumulated errors do not dominate the output. Gaussian and Gauss-Jordan are stable for diagonally-dominant matrices. If your matrix is not diagonally dominant, then the large multiplications to cancel off-diagonal terms amplify the precision errors in those terms (and the subsequent subtractions can lead to catastrophic cancellation). Gauss-Jacobi requires the spectral radius of the matrix to be less than $1$ to even converge. One way to ensure the spectral radius is less than $1$ is to be diagonally dominant. There are symmetric positive-definite matrices for which Gauss-Jacobi does not even converge, e.g. $(\begin{smallmatrix} 1 & 2 \\ 2 & 1 \end{smallmatrix})$. Gauss-Seidel converges for positive-definite and for diagonally dominant matrices. Notice that none of the methods you listed are stable/converge if your matrix is far from diagonally dominant. (So what do you do if you have such a matrix? Precondition.)

To summarize: We have these many algorithms because (1) the running time can vary substantially, depending on which algorithm you use and (2) different algorithms have different stability requirements.

$\endgroup$
  • $\begingroup$ A very good insightful answer, but yes my question also applies to polynomials and linear equations was the part where i thought of the question, let's talk generally now, what is the use of approximation? and how it helps in computation in general? $\endgroup$ – shoaib qureshi Apr 12 at 3:43
  • $\begingroup$ @shoaibqureshi : Updated with the futility of finding exact roots of generic polynomials. $\endgroup$ – Eric Towers Apr 12 at 12:44
  • $\begingroup$ One iteration of approximate algorithms is much faster than dense LU. However it does not imply that an iterative algorithm with the same norm of residuals as a direct method is faster. $\endgroup$ – Pawel Kowal Apr 12 at 20:17
  • $\begingroup$ @PawelKowal : At the level of granularity of the Question, treating the algorithms by their worst-case behaviour is justified. If one happens to work with a class of matrices that have structure, picking a method that leverages that structure is an excellent idea. $\endgroup$ – Eric Towers Apr 12 at 20:44
0
$\begingroup$

See also the answers to my question: For which applications are iterative methods particularly suitable to solve linear systems of equations?.

Reason for iterative methods are

  • Applications with harsh restrictions on the run time that can tollerate some deviations of the computed to the exact solution. This is the case for animations of bodies in video games where an iterative method can offer a nice tradeoff between runtime and precission.
  • Applications where you very large equation systems, as already noted in other answers.
$\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.