? C_2 H_2 Cl_4 + ? Ca(O H)_2 ==> ? C_2 H Cl_3 + ? Ca Cl_2 + ? H_2 OAn essential statement in our input parser is that it throws out all characters that are not OK, mainly according to:
OK := c in ['A'..'Z','a'..'z','0'..'9','+','=','(',')']; { with Pascal built-in Set Theory }The advantage of this is flexibility of input: most of it is "comment". It leaves us with the following much shorter string, containing only the essentials, to be processed futher:
C2H2Cl4+Ca(OH)2=C2HCl3+CaCl2+H2OThe end result of input processing is an array that stores the following data structure:
onthou = record e : string[2]; { name of chemical element } L : integer; { length of element name (1 or 2) } p : integer; { position in short formula string } r : integer; { numbering of matrix rows } m : integer; { numbering of matrix columns } g : integer; { number of atoms in molecule } end;
Then comes the computational part. The data stored in the above structure is converted into a matrix and a vector, essentially according to the answer given by lynn: $$ \begin{bmatrix} 2 & 2 & -1 & 0 \\ 2 & 0 & -2 & 0 \\ 0 & 2 & 0 & 0 \\ 4 & 0 & -3 & -2 \\ 0 & 1 & 0 & -1 \end{bmatrix} \begin{bmatrix} a \\ b \\ c \\ d \end{bmatrix} = \begin{bmatrix} 2 \\ 0 \\ 1 \\ 0 \\ 0 \end{bmatrix} $$ Only the numbering of the atoms (matrix rows) is different, which should not come as a surprise. The above is an overdetermined system which can be solved as: $$ A^TA x = \begin{bmatrix} 24 & 4 & -18 & -8 \\ 4 & 9 & -2 & -1 \\ -18 & -2 & 14 & 6 \\ -8 & -1 & 6 & 5 \end{bmatrix} \begin{bmatrix} a \\ b \\ c \\ d \end{bmatrix} = \begin{bmatrix} 4 \\ 6 \\ -2 \\ 0 \end{bmatrix} = A^T b $$ This raises the first question: is the system of equations $A^TAx=A^Tb$ indeed equivalent with $Ax=b$?
procedure Oplossen(A : matrix; var b : vector); { Simple Gauss Solver } var N,i,j,k : integer; p,s : double; begin N := Length(b); { Elimination } for k := 0 to N-1 do begin p := A[k,k]; { pivot } for i := k+1 to N-1 do begin if A[i,k] = 0 then Continue; A[i,k] := A[i,k]/p; for j := k+1 to N-1 do A[i,j] := A[i,j] - A[i,k]*A[k,j]; b[i] := b[i] - A[i,k]*b[k]; end; end; { Backsubstitution } for k := N-1 downto 0 do begin s := b[k]; for j := k+1 to N-1 do s := s - A[k,j]*b[j]; b[k] := s/A[k,k]; end; end;After having obtained an upper triangular matrix, the product of all main diagonal elements is the determinant. The solver is part of our open source, so it's easy to expand the output parameter list with a `Det`. Due to the integer nature of $A^TA$, the determinant must be an integer as well. Hence multiply the floating point solution with the determinant. Then, after rounding everything to the nearest integer and using GCD's, we should obtain the coefficients of the chemical equation.
Runtime error 207 at 00405D4EWhat it means by the way is: division by zero. In order to avoid it, we have modified the source code in such a way that divisions are simply not carried out for pivot values zero. The resulting Garbage Out will do no harm, because we have an overall balance check in the end.
type breuk = record { fraction } teller,noemer : integer; { numerator,denominator } end;Apologies for using so many Dutch words in my programming. One reason is that it protects us from conflicts with the (IMHO too many) reserved (and English) words in Pascal. Anyway, define alternatives for common arithmetic and other common operations. Mind the `Simplify` routine which should be present in most of the fraction functions. Without enduring simplification, the size of numerators and denominators can run quickly out of hand, maybe more quickly than expected. So I've used `int64` inside, which is the largest integer type available in Delphi Pascal.
function maak(a,b : integer) : breuk; { make } function vereenvoudig(f : breuk) : breuk; { Simplify } function afdruk(f : breuk) : string; { print } function plus(a,b : breuk) : breuk; { addition } function minus(a,b : breuk) : breuk; { substraction } function maal(a,b : breuk) : breuk; { multiplication } function deel(a,b : breuk) : breuk; { division } function gelijk(a,b : breuk) : boolean; { equality } function groter(a,b : breuk) : boolean; { greater } function dubbel(a : breuk) : double; { Double precision }As a next step, take the above open source simple Gauss solver and replace in there all common arithmetic operators by their rational number equivalents. The "Fractions" module can be designed in such a way that it is insensitive to division by zero. Which does not mean that you will always have a sensible outcome. But that doesn't matter much, because we can always check the balancing afterwards and there are no divisions in the latter procedure.
Back to our problem. With rational number arithmetic, matrix and vector may be displayed as follows, after pivoting: $$ \begin{bmatrix} 24/1 & 4/1 & -18/1 & -8/1 & | & 4/1 \\ & 25/3 & 1/1 & 1/3 & | & 16/3 \\ & & 19/50 & -1/25 & | & 9/25 \\ & & & 44/19 & | & 22/19 \end{bmatrix} $$ Backsubstitution as usual gives the following solution for the coefficients in the chemical equation: $$ \begin{bmatrix} 1/1 & 1/2 & 1/1 & 1/2 & 1/1 \end{bmatrix} $$ At last multiply with the maximum of the denominators (GCD is not necessary !) and we are finished: $$ \mathrm{2\, C_2 H_2 Cl_4 + Ca(OH)_2 \,\rightarrow \, 2\, C_2 H Cl_3 + Ca Cl_2 + 2\, H_2 O} $$
? Fe + ? O_2 ==> ? Fe O + ? Fe_2 O_3The accompanying balancing equations are: $$ \begin{matrix} \, O : \\ Fe : \end{matrix} \begin{bmatrix} 0 & 2 & -1 & -3 \\ 1 & 0 & -1 & -2 \end{bmatrix} \begin{bmatrix} p \\ q \\ r \\ 1 \end{bmatrix} = 0 \quad \Longrightarrow \quad \begin{bmatrix} 0 & 2 & -1 \\ 1 & 0 & -1 \end{bmatrix} \begin{bmatrix} p \\ q \\ r \end{bmatrix} = \begin{bmatrix} 3 \\ 2 \end{bmatrix} $$ Do the least squares: $$\begin{bmatrix} 0 & 1 \\ 2 & 0 \\ -1 & -1 \end{bmatrix} \begin{bmatrix} 0 & 2 & -1 \\ 1 & 0 & -1 \end{bmatrix} \begin{bmatrix} p \\ q \\ r \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 2 & 0 \\ -1 & -1 \end{bmatrix} \begin{bmatrix} 3 \\ 2 \end{bmatrix} $$ $$ \begin{bmatrix} 1 & 0 & -1 \\ 0 & 4 & -2 \\ -1 & -2 & 2 \end{bmatrix} \begin{bmatrix} p \\ q \\ r \end{bmatrix} = \begin{bmatrix} 2 \\ 6 \\ -5 \end{bmatrix} $$ The matrix is pivoted by hand: $$ \begin{bmatrix} 1 & 0 & -1 \\ 0 & 4 & -2 \\ -1 & -2 & 2 \end{bmatrix} \sim \begin{bmatrix} 1 & 0 & -1 \\ 0 & 4 & -2 \\ 0 & -2 & 1 \end{bmatrix} \sim \begin{bmatrix} 1 & 0 & -1 \\ 0 & 4 & -2 \\ 0 & 0 & 0 \end{bmatrix} $$ It's easily concluded that the system of equations is singular. Which means that there are multiple solutions. To mention a few of these: $$ \mathrm{3\, Fe + 2\, O_2 \,\rightarrow \,Fe O + Fe_2 O_3} \\ \mathrm{5\, Fe + 3\, O_2 \,\rightarrow \, 3\,Fe O + Fe_2 O_3} \\ \mathrm{7\, Fe + 5\, O_2 \,\rightarrow \,Fe O + 3\, Fe_2 O_3} $$
? Fe S + ? H_2 S O_4 ==> ? Fe S O_4 + ? H_2 OThe accompanying (augmented) balancing matrix is pivoted by hand, without least squares though: $$ \begin{matrix} \text{Fe :} \\ \text{S :} \\ \text{O :} \\ \text{H :} \end{matrix} \begin{bmatrix} 1 & 0 & -1 & 0 \\ 1 & 1 & -1 & 0 \\ 0 & 4 & -4 & -1 \\ 0 & 2 & 0 & -2 \end{bmatrix} \sim \begin{bmatrix} 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 4 & -4 & -1 \\ 0 & 2 & 0 & -2 \end{bmatrix} \sim \begin{bmatrix} 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & -4 & -1 \\ 0 & 0 & 0 & -2 \end{bmatrix} $$ The determinant is the product of the main diagonal elements of the last matrix, which is $8$. Thus it is easily seen that the balancing matrix is non-singular. This would have resulted in a Least Squares problem with non-zero residual. Therefore it is not allowed to put any of the unknown coefficients equal to a fixed value (i.e. the last one $=1$). There is no other solution than the zero solution: $$ \mathrm{0\, Fe S + 0\, H_2 S O_4 \,\rightarrow 0\,Fe S O_4 + 0\, H_2 O} $$ Herewith all possible cases have been covered.