| Students attending college or university in a | | | | points. For situations like this, a systematic |
| discipline heavy in the physical sciences, for | | | | method is required to produce an approximating |
| example, science or engineering, frequently make | | | | function that describes the relationship defined by |
| use of several specific numerical routines. Five of | | | | the data. The approximating function can then be |
| the most popular numerical routines are examined | | | | used to interpolate data between the known data |
| below. These types of routines probably cover | | | | points (or to extrapolate outside the range of the |
| 90% of the routines a student will use during a | | | | known points). Linear least-squares data fitting is |
| typical undergraduate degree. In addition to their | | | | one tool available for such situations. |
| popularity among science and engineering | | | | Applications for this class of numerical task arise in |
| programs, these numerical routines are also | | | | almost any field: economics, physics, politics, |
| encountered in many other curriculum. For | | | | engineering, chemistry, environmental studies, and |
| example, students in first year university who | | | | many more. For example, say a researcher has |
| take an Algebra course to satisfy a breadth | | | | collected population data for a country over the |
| requirement might need a Simultaneous Equations | | | | past fifty years and would like to define an |
| Solver occasionally - while they are taking the | | | | equation that effectively describes the population |
| course. Another student might need to apply a | | | | growth so that future growth can be |
| Linear Least Squares fit - once, for a specific | | | | extrapolated. Instead of simply looking at the |
| assignment - when taking an Accounting class. If | | | | data, and creating a "guesstimate" for an |
| the students then continue on in their planned | | | | equation--a technique that would vary from one |
| majors, say, Political Science or English, they do | | | | researcher to the next--a systematic and |
| not use such tools again. | | | | effective way of examining the data is offered |
| The five routines examined below are presented | | | | by Linear Least- Squares Data Fitting; it offers a |
| in response to the following hypothetical question: | | | | systematic approach for determining trends. |
| Which five numerical routines fill most - if not all - | | | | 4) Interpolation |
| of the needs of undergraduate university | | | | Interpolation is often used when drawing smooth |
| students? The answer given below presents the | | | | curves through data, usually data that does not |
| most common types of numerical tasks and | | | | include errors, and provides a systematic |
| some of their applications. In addition, several | | | | technique for computing data values between the |
| good-quality free tools are named that offer | | | | known data points (or outside the range of the |
| solutions to these types of problems; they | | | | known data points). For example, a researcher |
| provide most of the functionality required by | | | | might have (x, y) data points for the following |
| undergraduate students, allowing them to avoid - | | | | x-values: 1, 2, 3, 4, 5. However, the researcher |
| or at least delay - the expense of purchasing | | | | might need a y-value that corresponds to an |
| commercial software. | | | | x-value of 2.5 or 6.4. The researcher would have |
| 1) Root-finding | | | | to interpolate for the y-value at x = 2.5 (which is |
| Root-finding covers the class of problem in which | | | | within the range of known data values) and |
| the zero(s) of an equation cannot be found | | | | extrapolate for the y-value at x = 6.4 (which is |
| explicitly. | | | | outside the range of known data values). |
| Consider the Quadratic Equation:a x^2 + b x + c | | | | Furthermore, the acquisition of the data may |
| = 0a, b, and c are constants, and values of x that | | | | require sophisticated equipment that is hard to |
| satisfy the equation, called the roots or zeros, | | | | access, or the data may be very expensive to |
| must be found. | | | | compute. In these sorts of situations, a |
| The Quadratic Equation is one example of the | | | | systematic method of computing these |
| class of the problem of finding the roots of | | | | interpolating data points is required. |
| polynomial equations which is, in turn, part of the | | | | Several algorithms exist for this purpose; one |
| larger class of problem of root-finding. In fact, | | | | such algorithm is a Cubic Spline Interpolation. A |
| because the Quadratic Equation is so well-known | | | | Cubic Spline Interpolation creates a smooth curve |
| (students are often introduced to the Quadratic | | | | through known data values by using piecewise |
| Equation and its solution in Grade 10), root-finding | | | | third-degree polynomials that pass through all the |
| is probably the best-known class of numerical | | | | data values. However, it should be noted that |
| routine. | | | | different versions of this algorithm exist, for |
| The van der Waals Equation is another example | | | | example, a natural cubic spline interpolation has the |
| of a polynomial equation for which roots are often | | | | second derivatives of the spline polynomial set to |
| sought:pV^3 - n(RT + bp)V^2 + n^2 aV - n^3 | | | | zero at the endpoints of the interpolation interval. |
| ab = 0 | | | | This means that a graph of the spline outside the |
| In this case, values of V that satisfy the equation | | | | known data range is a straight line. Another |
| are sought, and the polynomial is a cubic (the | | | | version of the algorithm forces a "not-a-knot" |
| highest power of V is 3). van der Waals Equation | | | | condition: the second and second-last points are |
| is often encountered in chemistry, | | | | treated as interpolation points rather than knots |
| thermodynamics, and gasdynamics applications. | | | | (i.e. - the interpolating cubics on the first and |
| Kepler's Equation of Elliptical Motion is another | | | | second sub-intervals are identical, and so are the |
| equation to which root-finding techniques are | | | | ones for the last and second last sub-intervals). |
| applied: | | | | Applications for spline interpolation include |
| E - e sin(E) = M | | | | population data gathered over many years, |
| In this example, the equation is not a polynomial, | | | | cyclical sales information, and the contour of the |
| but it involves a transcendental function. e and M | | | | shape of an automobile body. |
| are known quantities, but there is no way to | | | | 5) Eigenvalues and Eigenvectorslambda is an |
| isolate E on one side of the equation and solve | | | | eigenvalue (a scalar) of the Matrix [A] if there is a |
| for it explicitly. Consequently, numerical techniques | | | | non-zero vector (v) such that the following |
| have to be employed. Rearranging the equation as | | | | relationship is satisfied: |
| follows turns the problem into one of finding the | | | | [A](v) = lambda (v) |
| roots of the equation: | | | | Every vector (v) satisfying this equation is called |
| E - e sin(E) - M = 0 | | | | an eigenvector of [A] belonging to the eigenvalue |
| These examples are just three equations whose | | | | lambda. |
| solution requires root-finding; many more | | | | Eigenproblems arise in almost all fields of science: |
| equations arise whose solutions can be found only | | | | structural analysis, computing the modes of |
| by employing root-finding techniques. Fortunately, | | | | vibration of a beam, aeroelasticity and flutter, |
| the problem of root-finding is a well-developed | | | | system stability (structure, aircraft, satellites, etc.), |
| field of mathematics and computer science. | | | | heat transfer, biological systems, population |
| Almost all root-finding algorithms take an iterative | | | | growth, sociology, economics, and statistics. |
| approach to computing a solution to a desired | | | | Eigenvalues and eigenvectors are also often used |
| degree of accuracy: first, an initial guess is made | | | | in conjunction with the solution of differential |
| and checked, then a closer solution is estimated | | | | equations. Furthermore, the algorithm behind the |
| and checked, and this process is repeated until | | | | Google search engine is also said to treat indexing |
| the user-specified level of accuracy is obtained. | | | | as an eigenproblem. |
| For example, a user might require four decimal | | | | Summary |
| places of accuracy in the solution, so the | | | | Root-finding, solving Simultaneous Equations, Linear |
| computer program would stop iterating for a | | | | Least-Squares Data-fitting, Interpolation, and the |
| solution once an approximation has been found to | | | | computation of Eigenvalues and Eigenvectors are |
| four decimal places. | | | | the most common types of problems faced by |
| 2) Simultaneous Equations | | | | students in college and university. Not only are |
| This class of numerical task deals with solving N | | | | these types of numerical tasks faced by science |
| Equations in N Unknowns. For example, a situation | | | | and engineering students, they also show up |
| may arise in which it can be mathematically | | | | throughout a variety of other programs. In |
| described as a linear (the highest power of x | | | | addition, two more factors attest to the |
| present is 1) system of Three Equations in Three | | | | prevalence of these numerical problems: (i) |
| Unknowns:a11 x1 + a12 x2 + a13 x3 = b1a21 x1 | | | | routines for handling these types of tasks are |
| + a22 x2 + a23 x3 = b2a31 x1 + a32 x2 + a33 | | | | almost always covered in texts and courses on |
| x3 = b3 | | | | numerical mathematics, and (ii) algorithms for |
| The aii and bi values are known but the values of | | | | these mathematical tasks are well-developed and |
| xi that satisfy this system of equations must be | | | | source code for computer programs has been |
| computed. This task could be accomplished with a | | | | available for decades. |
| pencil, paper, and hand calculator, but it would be | | | | Considering their popularity, readily-available tools |
| tedious. And as systems get larger, the number | | | | that provide solutions to these most common |
| of computations involved grows fast, introducing | | | | numerical tasks would appeal to a broad range of |
| the risk of typos or other errors. A system of, | | | | users. On one hand, some users might need a |
| say, 10 Equations in 10 Unknowns would keep a | | | | few routines for one-time or very infrequent use |
| person busy for quite a while! | | | | whereas, on the other hand, other users might |
| Fortunately, computer programs have been | | | | use a program often, but only one specific routine. |
| developed that can compute solutions to these | | | | In either case, the purchase of a commercial |
| systems quickly and accurately. They are usually | | | | software package is not justified and having free |
| put in matrix notation: | | | | software available is a convenient alternative. In |
| [A](x) = (b)where [A] is a square matrix and (x) | | | | fact, these types of numerical math routines are |
| and (b) are column vectors. | | | | widely available for free, in a variety of formats, |
| These sorts of systems can arise from almost | | | | offering a variety of capabilities. Several software |
| any field of study. In a course on Linear Algebra | | | | packages have been developed for installation on |
| such systems will be faced all the time. These | | | | a user's computer, for example, Octave and |
| systems also arise in electric circuit analysis (i.e. - | | | | Scilab, to name two. Others are available as Java |
| Mesh Current Analysis), industrial chemistry | | | | applets. And yet more are available as |
| projects, structural analysis, economics studies, | | | | immediate-for-use Javascript web pages; for |
| and more. In addition to solving the system for | | | | example, AKiTi.ca offers routines for solving |
| the x values, quantities of the [A] matrix itself are | | | | many of these types of problems. The availability |
| often computed to reveal informative properties | | | | of these various numerical routines provides |
| (for example, its determinant, eigenvalues, and LU | | | | people more options when selecting a tool that |
| Decomposition). | | | | best fits their unique needs, especially if these |
| 3) Linear Least-Squares Data Fitting | | | | tools include solutions for the most common |
| Linear Least-Squares data fitting is often applied | | | | numerical tasks. The availability of good-quality |
| to describe data which includes errors. For | | | | software tools for working with the most |
| example, a curve might be sought for data, but | | | | common numerical tasks offers the greatest |
| the data may be such that the expected curve | | | | utility to the greatest number of people. |
| does not satisfactorily pass through all the data | | | | |