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.
1) Root-finding
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.
4) Interpolation
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.
Summary
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.
Considering their popularity, readily-available tools that provide solutions to these most common numerical tasks would appeal to a broad range of users. On one hand, some users might need a few routines for one-time or very infrequent use whereas, on the other hand, other users might use a program often, but only one specific routine. In either case, the purchase of a commercial software package is not justified and having free software available is a convenient alternative. In fact, these types of numerical math routines are widely available for free, in a variety of formats, offering a variety of capabilities. Several software packages have been developed for installation on a user's computer, for example, Octave and Scilab, to name two. Others are available as Java applets. And yet more are available as immediate-for-use Javascript web pages; for example, AKiTi.ca offers routines for solving many of these types of problems. The availability of these various numerical routines provides people more options when selecting a tool that best fits their unique needs, especially if these tools include solutions for the most common numerical tasks. The availability of good-quality software tools for working with the most common numerical tasks offers the greatest utility to the greatest number of people.
David Binner has a Bachelor's Degree in Engineering. Since graduating, he has taken up computer programming, with an emphasis on numerical programs, and web page design as hobbies. To contact David, please visit his web site, AKiTi.ca, and go to the "Contact" page.
0 comments:
Post a Comment