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