Content deleted Content added
Fgnievinski (talk | contribs) avoid duplicating List of numerical analysis topics |
Fgnievinski (talk | contribs) |
||
Line 10:
Numerical analysis continues this long tradition: rather than giving exact symbolic answers translated into digits and applicable only to real-world measurements, approximate solutions within specified error bounds are used.
==Applications==
The overall goal of the field of numerical analysis is the design and analysis of techniques to give approximate but accurate solutions to hard problems, the variety of which is suggested by the following:
Line 25:
* Insurance companies use numerical programs for [[Actuary|actuarial]] analysis.
▲===History===
The field of numerical analysis predates the invention of modern computers by many centuries. [[Linear interpolation]] was already in use more than 2000 years ago. Many great mathematicians of the past were preoccupied by numerical analysis,<ref name="20c"/> as is obvious from the names of important algorithms like [[Newton's method]], [[Lagrange polynomial|Lagrange interpolation polynomial]], [[Gaussian elimination]], or [[Euler's method]]. The origins of modern numerical analysis are often linked to a 1947 paper by [[John von Neumann]] and [[Herman Goldstine]],<ref name="watson" /><ref>
{{cite book |editor1-link=Adhemar Bultheel |editor1-first=Adhemar |editor1-last=Bultheel |editor2-first=Ronald |editor2-last=Cools |title=The Birth of Numerical Analysis |volume=10 |publisher= World Scientific |date=2010 |isbn=978-981-283-625-0 |url={{GBurl|pKZpDQAAQBAJ|pg=PR17}} }}
Line 40 ⟶ 38:
The [[Leslie Fox Prize for Numerical Analysis]] was initiated in 1985 by the [[Institute of Mathematics and its Applications]].
==Key concepts==
===Direct and iterative methods===
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]]).▼
Consider the problem of solving▼
In contrast to direct methods, [[iterative method]]s are not expected to terminate in a finite number of steps. 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.▼
:3''x''<sup>3</sup> + 4 = 28
Line 78 ⟶ 84:
From this table it can be concluded that the solution is between 1.875 and 2.0625. The algorithm might return any number in that range with an error less than 0.2.
===Conditioning===
Ill-conditioned problem: Take the function {{math|size=100%|1=''f''(''x'') = 1/(''x'' − 1)}}. Note that ''f''(1.1) = 10 and ''f''(1.001) = 1000: a change in ''x'' of less than 0.1 turns into a change in ''f''(''x'') of nearly 1000. Evaluating ''f''(''x'') near ''x'' = 1 is an ill-conditioned problem.
Well-conditioned problem: By contrast, evaluating the same function {{math|size=100%|1=''f''(''x'') = 1/(''x'' − 1)}} near ''x'' = 10 is a well-conditioned problem. For instance, ''f''(10) = 1/9 ≈ 0.111 and ''f''(11) = 0.1: a modest change in ''x'' leads to a modest change in ''f''(''x'').
▲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. 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.
===Discretization===
| |||