COMPUTER ERRORS IN NUMERICAL METHODS
Krešimir Malarić, Roman Malarić
Faculty of Electrical Engineering and Computing, Unska 3, HR-10000 Zagreb, Croatia,
e-mail ,
ABSTRACT: This work deals with computer errors such as round-off error and truncation error. It points out possible errors and gives a method to avoid them. Errors' occurring when solving linear equations and a possible solution for avoiding them is shown.
Keywords: computer error, numerical methods
1. INTRODUCTION
When dealing with numerical methods, certain imperfections of computers have to be taken into the account. A certain problem that would take several days of counting, or impossible to do it properly, can quite easily and quickly be done with a PC at disposal to almost anyone. However, PCs have limitations, which have to be included into the consideration, and prior knowledge of these so-called computer errors can improve our calculation a great deal.
2. BASIC COMPUTER ERRORS
2.1. Round-off error
First important error is round-off error. Example for this error is following: if we input a number with more than 15 decimal digits into the computer (in Excell), the computer will not recognize it. The number 0,1234567890123456 will be saved and read as 0,123456790123450 (round-off error). Over the years, the computers have improved, for only couple of years ago, 9th digit was not recognized. In the future, computers will be more efficient, and error will be smaller, but it will not disappear.
2.2. Truncation error
The next error is so-called truncation error. This error appears while attempting to approximate a certain mathematical operation led by a computer program. It is presumed here that there is no round-off error. If, for example, we calculate numerical derivation in some point according to the equation
(1)
where h converges to 0.
1
Fig. 1. Derivative of a function
Table 1. Errors in numerical approximation of a derivative
h / exp(1)-D(h)5,000000000000000E-01 / -8,085326552989940E-01
1,250000000000000E-01 / -1,771983352128430E-01 / round-off error
3,125000000000000E-02 / -4,291906044276630E-02 / dominates
7,812500000000000E-03 / -1,064599427702320E-02
1,953125000000000E-03 / -2,656301179353000E-03
4,882812500000000E-04 / -6,637510524103440E-04
1,220703125000000E-04 / -1,659175077963760E-04
3,051757812500000E-05 / -4,147811439336730E-05
7,629394531250000E-06 / -1,036945202370630E-05
1,907348632812500E-06 / -2,592442864379760E-06
4,768371582031250E-07 / -6,485398205136050E-07
1,192092895507810E-07 / -1,633207591389410E-07
2,980232238769530E-08 / -5,156205018508330E-08
7,450580596923830E-09 / -3,666088899123570E-08
1,862645149230960E-09 / -1,558701785420170E-07
4,656612873077390E-10 / 8,254840055954560E-08
1,164153218269350E-10 / -2,778474548659200E-06
2,910383045673370E-11 / -1,040786907990920E-05
7,275957614183430E-12 / -4,092544720490920E-05
1,818989403545860E-12 / 2,010970904509080E-05
4,547473508864640E-13 / -4,681715409549090E-04
1,136868377216160E-13 / -4,681715409549090E-04
2,842170943040400E-14 / -4,681715409549090E-04
7,105427357601000E-15 / -3,171817154095490E-02
1,776356839400250E-15 / -3,171817154095490E-02
4,440892098500630E-16 / -2,817181715409550E-01 / truncation error
1,110223024625160E-16 / 2,718281828459050E+00 / dominates
2,775557561562890E-17 / 2,718281828459050E+00
Fig. 1. represents tangent approximation. If h is “too large”, then D(h) becomes inaccurate because h. is not sufficiently close to the limit. This error appears because we are trying to approximate an unrealisable limiting operation, the derivative with “realisable” arithmetic formula D(h). This error would occur even if f(x) and D (h) could be evaluated exactly. When h becomes very small, round-off error starts to dominate. The round-off and truncation errors in computing f(xo+h)-f(xo) are large relative to the actual value of this difference. Round-off error would not be present if D(h) could somehow be computed perfectly. Table 1. show errors in numerical approximation of a derivative.
Other functions like tan, sqrt, etc. would give similar results. Having in mind all the objections mentioned above, one might think that a computer has limitations, but knowing them in advance, we might still make PC very useful tool. The accuracy of PC increases with new models, but they will always have error, because they use strings of 0’s and 1’s of uniform length. Fig. 2 shows error versus step size in logarithmic scale.
Fig 2. Error versus step size
3. SOLUTION OF LINEAR EQUATIONS
Linear equations have following form:
a11x1 + a12x2 + ... + a1nxn = b1
a21x1 + a22x2 + ... + a2nxn = b2
. . . .
. . . .
. . . .
am1x1 + am2x2 + ... + amnxn = bm. (2)
Coefficients aij and bi are real or complex numbers. The system of equations has m equations with n unknowns x1, x2,..., xn. In many mathematical computations and numerical methods it is necessary to solve this system of equations. In many cases the solution can be found with so-called “naive” procedures, but sometimes, round-off error must be taken into consideration.
3.1. Naive Gaussian elimination
There are several variations of Gaussian elimination. With Gaussian elimination there is no truncation error, as with other methods, only round-off error. General Gaussian elimination method is well known and it will not be discussed here further. Due to the round-off error, naive Gaussian elimination can sometimes be unsatisfactory. That will be shown in the following example. If it is assumed that we did not have round-off errors in previous calculations, and that we came to the last two equations of the system:
0xn-1 + xn = 1
2xn-1 + xn = 3,
where 0 is result from the previous calculation. The solution of the equation is xn = xn-1 = 1. However, the true system of the equation is:
εxn-1 + xn = 1
2xn-1 + xn = 3,
Here ε represents a small value, which is the result of the round-off error. As ε0, the further calculation is as follows:
εxn-1 + xn = 1
(1-2/ε)xn = 3 - 2/ε
which gives, xn = (3-2/ε)/(1-2/ε),
xn-1 = (1-xn)/ε
For the values of ε close to 0, the values of 3-2/ε and 1-2/ε are very close to -2/ε, so the value of xn is very close to 1, which is a true value. However, xn-1 = (1-xn)/ε will give nonsense, because 1-xn will be under influence of the error calculated in xn, and even greater error will be made by ε in denominator, which can have any value whatsoever. It can be seen that the calculation of other unknowns xn-2,..., x1, based on the calculated xn-1 can only result in larger error. This method is unacceptable for the reason of parameter placement. The problem in the previous calculation is not ε being small; the problem is that ε is small compared to the other coefficients in the same column. This can be avoided if we change the leading coefficient, replacing it with the largest in the same column (partial pivoting), or with the largest in all remaining rows and columns (maximal pivoting).
3.2. Pivoting of the first coefficient
Partial pivoting
a11 ... a1n
a22(1) ...a2n(1)
. .
. .
. .
ak-1,k-1(k-2) ...ak-1,n(k-2)
akk(k-1)...akn(k-1)
..
..
. .
ank(k-1)...ann(k-1) (3)
Maximum pivoting
a11 ... a1n
a22(1) ...a2n(1)
. .
. .
. .
ak-1,k-1(k-2) ...ak-1,n(k-2)
akk(k-1)...a kn(k-1)
. .
Search this portion of . .
matrix for pivot . .
ank(k-1)...ann(k-1) (4)
In partial pivoting, the search is done in kth column, and with maximum pivoting, the search is done in the whole remaining matrix. Partial pivoting is simpler, but the larger errors are also possible. Now, if we will look at our problem again.
εxn-1 + xn = 1
2xn-1 + xn = 3,
Number 2 is largest and the new system will be:
2xn-1 + xn = 3
εxn-1 + xn = 1.
Further calculation will give as follows,
2xn-1 + xn = 3
(1-ε/2)xn = 1-3ε/2,
as ε is small, xn 1.0, and
xn-1 = (3-xn)/2 1.0
which gives accurate result.
4. CONCLUSION
Computer has two fundamental capabilities: a) it can store a finite set of numbers and b) it can perform arithmetic operation (addition, subtraction, multiplication and division) and it can find whether x is greater, equal or less than y. Examples of round-off error and truncation error was given, which have to be considered in numerical computations with PC. Gaussian elimination with pivoting was shown, and how it reduces the possibility of error.
5. BIBLIOGRAPHY
[1]Sidney Yakowitz & Ferenc Szidarovszky, An Introduction to Numerical Computations, Macmillan Publishing Company, New York, 1986
[2]Josip Butorac, Krešimir Malarić: Program za računanje nepouzdanosti pri Gaussovoj interpolaciji nelinearnih funkcija više varijabli – praktično mjeriteljsko pomagalo, Zbornik radova “38. međunarodni godišnji skup KoREMA”, Zagreb, 26-28. travnja 1993., str. 264-268
POGREŠKE RAČUNALA KOD NUMERIČKIH METODA
SAŽETAK: Ovaj rad se bavi pogreškama računala kao što su pogreška zokruživanja i skraćivanja. Ukazuje na moguće greške i daje metodu kako ih izbjeći. Pokazane su pogreške koje nastaju kod rješavanja linearnih jednadžbi i metoda kako se mogu izbjeći.
Ključne riječi: pogreška računala, numeričke metode