Effect of Significant Digits in Solution of Simultaneous Linear Equations

Jamie Trahan, Autar Kaw, Kevin Martin
University of South Florida
United States of America
kaw@eng.usf.edu

Introduction

The number of significant digits used in numerical solutions of simultaneous linear equations influences the accuracy of the solution vector, especially if the coefficient matrix is nearly singular. In this worksheet, the reader can choose a system of equations and see the influence of significant digits on each element of the solution vector. To learn more about the effects of significant digits on the accuracy of the solution vector click here. 

The following simulation uses Naïve Gaussian Elimination method to demonstrate the effect that significant digits have on the accuracy of the solution.

Section 1: Input Data

The following are the input parameters to begin the simulation. This is the only section that requires user input. The user can change the values that are highlighted only.

In the simulation, Naïve Gaussian Elimination method is used to solve a set of simultaneous linear equations, [A] [X] = [RHS], where [A]nxn is the square coefficient matrix, [X]nx1 is the solution vector, and [RHS]nx1 is the right hand side array. To demonstrate the effect that significant digits have on the accuracy of solution, Mathematica will return a list of solution vectors that were calculated using the significant digits within the range of your choice. It will then plot each element of the solution vector as a function of the number of significant digits used.

nxn coefficient matrix, [AL]

AL = 
        Table[{{12, 7, 3}, {1, 5, 1}, {13, 12, 
              4.001}}];
AL // MatrixForm

nx1 right hand side array, [RHS]

RHS = Table[{22, 7, 29.001}];
RHS // MatrixForm

lower limit of range of significant digits, lowerlim

lowerlim = 3

upper limit of range of significant digits, upperlim

upperlim = 10

number of equations, n

n = Length[AL]

Section 2: Significant Digit Operators

The following functions modify standard arithmetic operators allowing computation with the appropriate number of significant digits. These redefined operators are then used in the Naive Gaussian Elimination method to generate a solution that was computed with the number of significant digits specified.

sdscale[sd_, x_] := 
      Module[{}, 
If[x == 0, m = sd, 
          m = sd - (Floor[Log[10, Abs[x]]] + 
                  1)] ; 
q = 
          N[x*10^m]; 
q = 
          N[Floor[q]*10^(-m)]]

add[a_, b_] := N[a + b]
sub[a_, b_] := N[a - b]
div[a_, b_] := N[a/b]
mul[a_, b_] := N[a*b]

SdDyadic[op_, sd_, x_, y_] := 
      Module[{}, 
z = 
          op[sdscale[sd, x], sdscale[sd, y]]; 
sdscale[sd, 
          z]]

sdadd[sd_, x_, y_] := 
      SdDyadic[add, sd, x, y]
sdsub[sd_, x_, y_] := 
      SdDyadic[sub, sd, x, y]
sdmul[sd_, x_, y_] := 
      SdDyadic[mul, sd, x, y]
sddiv[sd_, x_, y_] := SdDyadic[div, sd, x, y]

Section 3: Procedure for Naïve Gaussian Elimination method

Parameter Names:
n = number of equations
A = nxn coefficient Matrix
B = nx1 right hand side vector
dig = number of significant digits used in calculations

gaussnaive[n_, A_, B_, dig_] := 
      Module[{AA, BB}, 
AA = 
          Array[0, {n, n}]; 
BB = 
          Array[0, n]; 
For[i = 1, 
          i ≤ n, i++, 
For[j = 1, 
            j ≤ n, j++, 
AA[[i, j]] = 
              A[[i, j]]]; 
BB[[i]] = 
            B[[i]]]; 
X = 
          Array[0, n]; 
i = 0; k = 0; 
        j = 0; 
For[k = 1, 
          k ≤ n - 1, k++, 
For[i = k + 1, 
            i ≤ n, i++, 
multiplier = 
              sddiv[dig, AA[[i, k]], 
                AA[[k, k]]]; 
For[j = k + 1, 
              j ≤ n, j++, 
AA[[i, j]] = 
                sdsub[dig, AA[[i, j]], 
                  sdmul[dig, multiplier, 
                    AA[[k, j]]]]]; 
BB[[i]] = 
              sdsub[dig, BB[[i]], 
                sdmul[dig, multiplier, 
                  BB[[k]]]]]]; 
X[[n]] = 
          sddiv[dig, BB[[n]], AA[[n, n]]]; 
For[
          i = n - 1, i ≥ 1, i--, 
          summ = 0; 
For[j = i + 1, 
            j ≤ n, j++, 
            summ = sdadd[dig, summ, 
                sdmul[dig, AA[[i, j]], 
                  X[[j]]]]
]; 
X[[i]] = 
            sddiv[dig, sdsub[dig, BB[[i]], summ], 
              AA[[i, i]]]]; 
X]

Section 4: Results

In this section, the procedure for Naive Gauss Elimination is called for different numbers of significant digits within the lowerlim to upperlim significant digit range. Each column corresponds to a solution vector that was calculated with the number of significant digits specified in the column heading. Compare these values to the exact solution found below to discover the effect that round-off error has on the accuracy in a solution of simultaneous linear equations.

X1 = Array[0, upperlim];
Xstore = 
        Array[0, {n, (upperlim + 1) - 
              lowerlim}];
For[p = lowerlim, 
      p ≤ upperlim, p++, 
X1 = 
        gaussnaive[n, AL, RHS, p]; 
subvalue = 
        lowerlim - 1; 
For[i = 1, 
        i ≤ n, i++, 
        Xstore[[i, (p - subvalue)]] = 
          X1[[i]]]]
Xvar = Table[(Subscript["X", J]), {J, 1, n, 1}];
SigDig = 
        Table["Digits="[b], {b, lowerlim, upperlim, 
            1}];
TableForm[Xstore, 
      TableHeadings -> {Xvar, SigDig}]

The exact solution to the system of equations with default number of significant digits in Mathematica is:

Xexact = LinearSolve[AL, RHS];
MatrixForm[Xexact]

The following graphs also demonstrate the effect that the number of significant figures has on  solution. Each element of the solution vector is plotted as a function of the number of significant digits used.

\(For[i = 1, 
      i ≤ 
        n, \(i++\), 
Print["  "]; 
ttl = 
        Print["Value of", " ", "X"\_i, " ", "as a function of the number of significant digits used"]; 
data = 
        Table[{k, Xstore[\([i, k - subvalue]\)]}, {k, lowerlim, 
            upperlim}]; 
ListPlot[
        data, 
PlotJoined -> 
          True, 
PlotRange -> 
          All, 
Frame -> 
          True, 
FrameLabel -> "X"\_i, 
PlotStyle -> {Thickness[0.012], 
            RGBColor[0, 0, 1]}]; 
Print[
        data]; 
Print["  "]; 
      Print["____________________________________"]; 
      Print["  "]]\)

Conclusion

Mathematica helped us to apply our knowledge of Naive Gaussian Elimination to study the effect of significant digits on the solution of a set of simultaneous linear equations.

Question 1: Choose a set of equations for which the coefficient matrix is nonsingular. For example

5x + 6y +  9z =  29
6x + 9y + 2z =  19
11x + 9y + 5z = 30

See how the number of significant digits makes a difference in the solution vector.

Question 2: Choose a set of equations for which the coefficient matrix is nearly singular. For example

5x + 6y +  9z =  29
6x + 9y + 2z =  19
11x +159y +11.001z = 49.002

See if the number of significant digits makes a difference in the solution vector.

Question 3: One of the classical problems to show the effect of significant digits on solutions of simultaneous linear equations is with a Hilbert matrix as the coefficient matrix. A matrix (Subscript[[H], nxn]) is called the (n^th)Hilbert matrix if

(Subscript[h, ij])= (1/(i + j - 1))

For example, a 4 x 4 Hilbert matrix is

(({{1, (1/2), (1/3)}, {(1/2), (1/3), (1/4)}, {(1/3), (1/4), (1/5)}}))

References

[1] Autar Kaw, Holistic Numerical Methods Institute, http://numericalmethods.eng.usf.edu/, See
Introduction to Systems of Equations
Effect of Significant Digits on Solution of Equations
How does Gaussian Elimination work?