Content deleted Content added
Jasper Deng (talk | contribs) →Applications: why we need numerical analysis and not just a few formulae Tags: Mobile edit Mobile web edit Advanced mobile edit |
Jasper Deng (talk | contribs) →Direct and iterative methods: clarify this is not a rounding error issue Tags: Mobile edit Mobile web edit Advanced mobile edit |
||
Line 44:
Direct methods compute the solution to a problem in a finite number of steps. These methods would give the precise answer if they were performed in [[Arbitrary-precision arithmetic|infinite precision arithmetic]]. Examples include [[Gaussian elimination]], the [[QR decomposition|QR factorization]] method for solving [[system of linear equations|systems of linear equations]], and the [[simplex method]] of [[linear programming]]. In practice, [[floating-point arithmetic|finite precision]] is used and the result is an approximation of the true solution (assuming [[numerically stable|stability]]).
In contrast to direct methods, [[iterative method]]s are not expected to terminate in a finite number of steps, even if infinite precision were possible. Starting from an initial guess, iterative methods form successive approximations that [[Limit of a sequence|converge]] to the exact solution only in the limit. A convergence test, often involving [[Residual (numerical analysis)|the residual]], is specified in order to decide when a sufficiently accurate solution has (hopefully) been found. Even using infinite precision arithmetic these methods would not reach the solution within a finite number of steps (in general). Examples include Newton's method, the [[bisection method]], and [[Jacobi iteration]]. In computational matrix algebra, iterative methods are generally needed for large problems.<ref>{{cite book |first=Y. |last=Saad |title=Iterative methods for sparse linear systems |publisher=SIAM |date=2003 |isbn=978-0-89871-534-7 |url={{GBurl|qtzmkzzqFmcC|pg=PR5}} }}</ref><ref>{{cite book |last1=Hageman |first1=L.A. |last2=Young |first2=D.M. |title=Applied iterative methods |publisher=Courier Corporation |edition=2nd |date=2012 |isbn=978-0-8284-0312-2 |url={{GBurl|se3YdgFgz4YC|pg=PR4}} }}</ref><ref>{{cite book |first=J.F. |last=Traub |title=Iterative methods for the solution of equations |publisher=American Mathematical Society |edition=2nd |date=1982 |isbn=978-0-8284-0312-2 |url={{GBurl|se3YdgFgz4YC|pg=PR4}}}} </ref><ref>{{cite book |first=A. |last=Greenbaum |title=Iterative methods for solving linear systems |publisher=SIAM |date=1997 |isbn=978-0-89871-396-1 |url={{GBurl|QpVpvE4gWZwC|pg=PP6}}}}</ref>
Iterative methods are more common than direct methods in numerical analysis. Some methods are direct in principle but are usually used as though they were not, e.g. [[GMRES]] and the [[conjugate gradient method]]. For these methods the number of steps needed to obtain the exact solution is so large that an approximation is accepted in the same manner as for an iterative method.
| |||