Analysis,Design And Algorithm

If there are more then one possible way of solving a problem, then one may think of more than one algorithm for the same problem. Hence, it is necessary to know in what domains these algorithms are applicable. Data domain is an important aspect to be known in the field of algorithms. Once we have more than one algorithm for a given problem, how do we choose the best among them? The solution is to devise some data sets and determine a performance profile for each of the algorithms.

A best case data set can be obtained by having all distinct data in the set. But, it is always complex to determine a data set, which exhibits some average behavior. The following sections give a brief idea of the well-known accepted algorithms.

2.1 Numerical Algorithms

Numerical analysis is the theory of constructive methods in mathematical analysis. Constructive method is a procedure used to obtain the solution for a mathematical problem in finite number of steps and to some desired accuracy.

2.1.1 Numerical Iterative Algorithm

An iterative process can be illustrated with the flow chart given in fig 2.1. There are four main blocks in the process viz., initialization, decision, computation, and update. The functions of these four blocks are as follows:

1. Initialization: all parameters are set to their initial values.
2. Decision: decision parameter is used to determine when to exit from the loop.
3. Computation: required computation is performed.
4. Update: decision parameter is updated and is transformed for next iteration.

Many problems in engineering or science need the solution of simultaneous linear algebraic equations. Every iterative algorithm is infinite step algorithm. One of the iterative algorithms to solve system of simultaneous equations is Guass Siedel. This iteration method requires generally a few iteration. Iterative techniques have less round-off error. For large system of equations, the iteration required may be quite large. But, there is a guarantee of getting the convergent result.

For example: consider the following set of equations,

10x₁+2x₂+x₃= 9

2x₁+20x₂-2x₃= -44

-2x₁+3x₂+10x₃= 22.

To solve the above set of equations using Guass Siedel iteration scheme, start with (x₁⁽¹⁾,x₂⁽¹⁾,x₃⁽¹⁾)=(0,0,0) as initial values and compute the values of we write the system of x₁, x₂, x₃ using the equations given below

 

x₁^(k+1)=(b₁-a₁₂x₂^(k+1)-a₁₃x₃^(k))/a11

x₂^(k+1)=(b₂-a₂₁x₁^(k+1)-a₂₃x₃^(k))/a22

x₃^(k+1)=(b₃-a₃₁x₁^(k+1)-a₃₂x₃^(k+1))/a33

for k=1,2,3,�

This process is continued upto some desired accuracy. Numerical iterative methods are also applicable for obtaining the roots of the equation of the form f(x)=0. The various iterative methods used for this purpose are,

1. Bisection method: x_i+2=(x_i+x_i+1)/2
2. Regula- Falsi method: x₂=(x₀f(x₁)+ x₁f(x₀))/ (f(x₁)-f(x₀))
3. Newton Raphson method: x₂= x₁-f(x₁)/f¹(x₁)