Linear Equations, Solving - Gaussian

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.

 

Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

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: February 18, 2016

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.