PROJECT

(b) Discuss relative merits and demerits of the two methods especially with respect to computational complexity, truncation errors and round off errors, involved in computations using these methods. - (3 Marks)

Before discussing the merits and demerits of gaussian elimination and gauss-seidal iterative method with respect to computational complexity , truncation errors and round-off errors let make it clear – what does the above specified errors mean ?

Computational complexity :-

The increasing speed of computers and advances in numerical methods have made it possible to solve most small problems rapidly by means of readily available software, and the attention of many numerical analysts has turned to the solution of problems so large that they require inordinate amounts of computer time. The use of the most efficient method has much greater importance in large problems than it does in small ones. In the latter the flexibility of human use of the program may be of much greater importance. One measure of the efficiency of a numerical method is the number of arithmetic operations needed to solve a problem. (Others include the amount of memory used and the order in which it is used, but these issues are more properly subjects of computer science.) Computational complexity is the study of the inherent computational cost (measured by number of operations) of solving a problem. The result of a complexity analysis is an estimate of how rapidly the solution time increases as the problem size increases. It can be used to analyse problems and assist in the design of algorithms for their solution.

Computing time of an algorithm is o(g(N)) where its execution takes no more time than a constant time g(N) and N is a parameter which characterises the inputs and /or outputs .

Merits and Demerits with respect to computational complexity : -
Direct methods such as Gaussian Elimination are extremely costly in terms of computation time, being of O(N 3) (cubic) in complexity, making them unfeasible for large-scale problems. For problems on this scale we must turn our attention to iterative methods. Iterative methods solve equation by recursively updating estimates until the equation is satisfied to within some value. Iterative methods such as Gauss-Seidal are of order O(N 2)(quadratic) in computational complexity and are therefore much quicker than direct methods.

Thus Gauss-Seidal method is superior than Gaussian Elimination method as N increases the time for the second method will get far worse than the time for the first .

Truncation and Round-Off errors :-

Most problems involve infinite sets of values, each of which can potentially require an infinite number of digits for exact representation. Digital computation, human, mechanical, or electronic, is, by its very nature, finite: it involves a finite set of numerical values, each of which is represented in a finite set of digits. These two approximations of infinite quantities by finite ones lead to the two types of error in numerical computation, truncation and round-off error .

Round off :

The precision of a value is indicated by the number of digits used in its representation. It is typically between seven and 15 decimal digits, depending on the type of computer and calculation. Finite precision means that most values cannot be represented exactly, but that there is some round-off error in the computed approximation. For example, if 4/3 is represented by five significant decimal digits as 1.3333 (the most accurate possible using five digits), there is a round-off error of 0.0000333 . . . (1.3333333… minus 1.3333 )

Truncation errors :-

A function, f(x), is a prescription of a value corresponding to each value of its argument, x. ). A function of a single variable x can be represented graphically by placing a point at [x, f(x)] for each value of x. If this is done for a few values of x, say five values, the set of points , x1, y1, x2, y2, . . . , y5, where yi = f(xi) in graph will obtained. These five co-ordinates (xi , yi), however, do not prescribe the value of the function for other than the five given values of x. Hence, the graph needs infinitely much information if it is to describe the function completely. This circumstance introduces a fundamental concept, that of a finite approximation to an infinite-dimensional object, which is illustrated by the approximation of a smooth graph of a function by a series of straight lines (a piecewise-linear approximation). If consecutive points are joined by a sequence of straight lines, a piecewise-linear approximation is obtained. . More closely spaced points can be used in a piecewise-linear approximation to get a more accurate approximation, but the additional points mean that more information is used to approximate the function. The error caused by replacing an infinite-dimensional object by a finite-dimensional approximation is called truncation error.

Merits and Demerits with respect to Truncation and round-off errors:-

1. As the amount of information is increased to decrease truncation error, the size of each round-off error, which is determined by the number of digits used in the calculation, remains constant. Hence, no amount of additional information can reduce the error below some minimum unless the precision of the calculation is increased.

2. The number of arithmetic operations in the calculation increases as the amount of information increases, so that the total error due to round-off increases because it is the combined effect of an increasing number of round-off errors. In these calculations, the error in the answer, which is the sum of the effects of truncation errors and round-off errors, initially decreases as the amount of information used increases and the truncation error decreases, but then increases as the round-off errors become dominant.

3. Round-off errors, which are proportional to the size of the value containing the error when a fixed number of significant digits is used, can be as large as 5 in the first neglected place or one-half in the last retained place. When a value is added to a much smaller value, the round-off can be large relative to the smaller value. For example, if 23,456 is added to 10.518 in five digits, the result is 23,467, with a round-off error of -0.482. If 23,456 is subtracted from the answer, the result is 11. Thus, in five-digit arithmetic, (23,456 + 10.518) - 23,456 = 11.0, which has an error in the third place. After the addition, the error was less than one-half in the last place, but the subtraction removed the three leading digits, 234, moving this error to the third place. This phenomenon is called cancellation. It does not cause errors but makes the size of errors already introduced larger relative to the computed result. Thus, although round-off errors are small, their effect in the final answer can be large, so that one of the tasks of the numerical analyst is to devise or modify computational schemes to minimize the effect of these errors

4. A system of N equations in N unknowns is usually written as

Ai1X1 + Ai2X2 + ……. + AinXn = bi , I=1,2,3,….,n

where the Aij are the coefficients, the bi are the right-hand side values, and the xj are the unknowns to be computed.

In the Gauss elimination-back substitution procedure it was noted that it could always be completed unless one of the Aii divisors was zero. If one of those divisors is very small, intermediate results may be very large, and the final answer may be obtained as the difference of two large numbers. This means that cancellation may occur so that there may be a large effect due to round-off.