Problem Description
This program solves sets of linear
equations using Gaussian Elimination with Partial Pivoting.
Background & Techniques
I finally ran across an application that requires determining the coefficients for a set of polynomials when we have as many
points as the power of the polynomial. Under these conditions, we
can find the coefficients b y treating them as a set of linear
equations. The heart of the code used here is from an old Borland
package, Numerical Toolbox, first released for Turbo Pascal in 1987.
Thankfully, the non-visual parts of Turbo Pascal are 100% compatible
with Delphi, making conversion of old code pretty simple.
For details of the method used, Gaussian Elimination with Partial
Pivoting, you can refer to the reference book that Borland used while
developing the code: Numerical Analysis, Richard Burden and J. Lewis
Fairies, published by Prindle, Weber & Schmidt, 1985. (Here's an
Amazon link to used versions of a more recent edition: Numerical Analysis, Burder & Fairies
- $140 book for $15-$20; seems like a bargain if you are into that kind of
thing.). Or refer to the many
sites on the Internet discussing the technique. For example this
one .
Suppose we want a 5th degree polynomial that generates the first 6
terms of a series, specifically: given f(x) = ax5 + bx4
+cx3 + dx2 +ex and
function values of:
 |
f(1) = 1 = a + b + c + d + e |
|
f(2) = -1 = 32a + 16b + 8c + 4d + 2 |
|
f(3) = 8 = 243a + 81b + 27c + 9d +3 |
|
f(4) = -56 = 1024a + 256b + 64c + 16d +4 |
|
f(5) = 569 = 3125a + 625b + 125c + 25d +5 |
find the values for a, b, c, d, e which satisfy all of the
equations.
If we pass a 5 x 5 array of coefficients and a 1 x 5 array of
desired function values to procedure Partial_Pivoting in unit UMatrix,
we get back a Solutions vector and an error code.
UMatrix defines types
|
TNVector = array [1..TNArraySize] of
extended; |
|
TNMatrix = array[1..TNArraySize] of
TNVector; |
where TNArraySize is a constant representing the maximum size of
the arrays, currently set to 30..
Calling sequence is: Partial_Pivoting (Dimen, Coefficients, Constants, Solution, Error);
where
|
Dimen is an integer passing the number of equations |
|
Coefficients is the array of coefficients of type TNMatrix |
|
Constants is the vector of function values of type TNVector |
|
Solutions is the unique solution vector of type TNVector |
|
Error is the integer return code:
 |
0 = normal return |
|
1 = Dimen < 2 or greater than max allowed |
|
2 = No unique solution exists |
|
The downloadable demo files below include a demo program, GaussianElem
which allows users to specify an input file of coefficients and constants
and displays the solution, the variable values which satisfy the set
of input values.
Input file format is as follows
| Line Number |
Content |
| 1 |
Integer number of equations, N |
| 2 to N+1 |
N sets of coefficients, one per function, each set
containing N values separated by one or more spaces. |
| N+2 |
The constants vector, N values for the functions, in
the same order as the coefficient sets. |
Zipped files also contain a couple of sample problems including
the one described above (Sample101.txt) and the sample
provided with Borland's original version (Sample6A.txt).
Running/Exploring the Program
Suggestions for Further Explorations
Unit UMatrix contains several other potentially
useful procedures Determinant, Inverse, Gaussian_Elimination,
LU_Decompose, LU_Solve, Gauss_Seidel which could (should?) be
tested and documented.
| Original Date: August 4, 2005 |
Modified: November 07, 2008
|
|
