Numerical Methods Using MATLAB - Part 5

Graeffe's Root Squaring Method:
           This is a direct method and it is used to find the roots of a polynomial equation with real coefficients. Let us consider an equation of the form:

                         ax3 + bx^2 + cx + d = 0

To find the solution of the above equation, we fill up the following table:

		m		2^m		n1		n2		n3		n4
Given Equation		0		1		a		b		c		d
						a^2		b^2		c^2		d^2
						0		-2*a*c		-2*b*d		0
First Squaring		1		2		a^2		b^2 - 2*a*c		c^2 - 2*b*d		d^2

              Thus, the table goes on. The number of squaring done depends on the required accuracy of the solution. The roots are calculated by using the final values of n1, n2, n3 and n4 as follows:

                   a1^(2^m)=n2/n1

               a2^(2^m)=n3/n2

               a3^(2^m)=n4/n3

          From the above equations, the roots a1, a2, a3 can be calculated.The MATLAB code for solving a polynomial by the above method is given below:

Source Code: 

    % a function that uses Graeffe's method 

    % to calculate roots of Algebraic equation 

    function GraeffeFunc(co,gcount)

             % variable b contains the size of co

             % co  coeff/: vector

             [a b]=size(co);

  

             % initialize count to zero

             count = 0;

            % loop where elements of co vector are squared

            % step by step for further processing

            while count<gcount

                    for i=1:b

                         % for other coeff.

                         if i~=1 && i~=b

                              co1(i)=(co(i)^2)-(2*co(i-1)*co(i+1));

                              % for 1st and last coeff.

                        else

                              co1(i)=co(i)^2;

                        end

                    end

                    count=count+1;

                    co=co1;

           end

           % end of while

           % Finding the solution by operating on co1 vector values

           for i=2:b

               sol(i-1)=(co1(i)/co1(i-1))^(1/(2^gcount));

           end

          % displaying calculated values

          disp(co1);

          disp(sol);

    end

    % end of program

Coming up next:

       * Solution of Simultaneous Linear Algebraic Equations

Read More

Numerical Methods Using MATLAB - Method of False Position

In this post, we solve Algebraic Equations using Regular Falsi Method, also known as Method of False Position. 


Regula Falsi Method:
         Consider the equation f(x)=0. Let a and b be two points such that f(a)<0 and f(b)>0. The function f(x) cuts x-axis at some point between (a,f(a)) and (b,f(b)).  The equation of chord joining the two points is given by,


(y-f(a))/(x-a))=(f(a)-f(b))/(a-b)


         The point where the chord cuts the x-axis gives an approximate value root of f(x)=0. Hence, we substitute y=0 in the above equation to get an expression for x, as follows:

x1=(af(b)-bf(a))/(f(b)-f(a))

          This value of x1 gives an approximate value of root of the equation f(x)=0. Substitute x1 in f(x) and find f(x1).

IF f(x1) > 0
x1=b
ELSE
x1=a


Now,
         x2=(af(x1)-x1f(a))/(f(x1)=f(a))
        Thus, we get a sequence of roots x1,x2,..... The sequence converge to required root with required accuracy.

Source Code :
% Function that calculates approximate solution using Regula Falsi (or) False Position Method
function    RegFalsiFunc(co,deg,rang)
     % x=a --> f(x)<0
     % x=b --> f(x)>0
     a = rang(1);
     b = rang(2);

     % initialize previous var to 0
     prev=0;

     % infinite loop
     while ( 1 )
            % find fa,fb,fx1 substituting a,b in f(x)
            fa = SubFunc(deg,co,a);
            fb = SubFunc(deg,co,b);
  
             % find x1 from fa,fb,a,b
             x1 = ((a*fb)-(b*fa))/(fb-fa);


            % find fx1 substituting x1 in f(x)
            fx1 = SubFunc(deg,co,x1);
   
            % if fx1 is negative replace a with x1
            if (fa*fx1)>0      a=x1;
            % else replace b with x1
            else    b=x1;
            end    
            % end of if....else
   
            % end the loop when required accuracy is achieved
            if abs(abs(x1)-abs(prev)) < 0.000001
                        break;
            end
            % end of if
            prev = x1;
      end
      % end of while
      disp(x1);
 end
% end of function

Read More

Numerical Methods using MATLAB - Iterative Method

In this post, we solve Algebraic Equations by Iterative Method,  which is also famously known as Successive Approximation Technique.

What is an Iterative Method?


Iterative Method:


Consider the equation f(x)=0. We need to find the roots (approximate) of the equation.

Let x=g(x)-------------------------(1)

Firstly, assume an approximate root x0. The more accurate x0 is, the less the number of iterations for finding the exact root. We substitute x0 in (1) and get a new root x1. This process goes on and on, until we get a solution that matches the expected accuracy. We get a sequence of approximate roots. The convergence of the sequence  depends on the value of x0 chosen initially. There are some conditions for the convergence of the method, which are not discussed here.

Where do we get the Source Code?

    Right here!!!!!!!!!!!!!!

Source Code:

function iterateFunc(co,prev)

   %Now 'co' is the vector under scrutiny
   %'co' represents the coefficient vector

   [a,b]=size(co);
   % 'b' gives us the exact size of vector


   % we iterate backward here
   for i=b-1:-1:1

        %we find the position corresponding to minimum degree
        if co(i)~=0
            min=i;
            break;
       end  
  end

 % Beginning of truncation


  % We truncate the constant and the terms with zero coeff:/
  % near the constant

  tco=co(1:min);

  % Minimum degree to be taken as common is given by '(b-min)'
  % b1 gives the size of truncated vector 'tco'
  [a1,b1]=size(tco);

  % infinite while loop
  while 1
 
      % Function return the value of polynomial after sub. of  an user defined constant 'prev'
      ans1=SubFunc(b1-1,tco,prev);

      % Here find the entire right hand side
     % and rise it to the power (reciprocal of min degree)
      curr=((-co(b))/ans1)^(1/(b-min));

      % when required accuracy of solution is met 
      % loop breaks
      if abs(abs(prev)-abs(curr)) < 0.0000001
          break;
     end
 
      % transfer from current to prev
      prev=curr;

  end

  disp(curr);

end

Read More

Numerical Methods using MATLAB - Bisection Method

Why do we need numerical methods?

          In Engineering, there are several different processes involved in a system under study. These processes are represented mathematically by their mathematical models. The models can be algebraic, trignometric, ordinary or partial differential equations. So, in order to study the static and dynamic behaviour of the system, we need to analyse the math models of the particular system. The analysis of these models is known as Numerical Analysis.

Basic Tools for Numerical Analysis:

1. System of Linear Algebraic Equations
2. Eigen value problems
3. Roots of Nonlinear Equations
4. Polynomial Approximation and Interpolation
5. Numerical differentiation and Interpolation

Above are few numerical techniques involved to solve several engineering problems. They are all based on certain assumptions and approximations.

Why do Engineers need to practise programming?

         Engineers are expected to solve problems in real time using the numerical techniques listed above. They just need to assemble existing pieces of code to form a solution to a practical problem. These existing pieces of code is usually a function that does a particular task.

What is MATLAB?

MATLAB  is a high-level language for scientific computing and data visualization built around an interactive programming environment. It is becoming the premiere platform for scientific computing at educational institutions and research establishments.










Why use MATLAB?

        MATLAB is an interactive system whereprograms can be tested and debugged quickly. There is no need for compiling, linking and execution each and every time of testing. Hence, programs can be developed in a shorter time in MATLAB. It contains a large number of basic functions and some numerical libraries like LINPACK etc,. There is no need of declaring variables as int or float since all the numerical entities are treated as arrays.

Where do we start?

        As Step1, we now learn to solve Algebraic Equations numerically. There are quite a few methods for solving them. Most are based on formula and approximation. We here use BISECTION Method to solve Algebraic Equations.

BISECTION METHOD:

Let us consider a polynomial f(x) of degree 'n', then,
f(x)=0 is an algebraic equation, whose solution is assumed to lie between the range (a,b) and is continuous within that range.

 If f(a) and f(b) are of opposite signs, then a real root should exist between points a and b. Let f(a)>0 and f(b)<0.

As a first approximation, we assume the root of the equation to x0=(a+b)/2. If f(x0)<0, the root lies between a and x0 and so we consider new limits as a and x0 and the process goes on.

If f(x0)>0, the root lies between x0 and b and hence we consider limits as x0 and b and the process goes on.

This way, we form a sequence of approximate roots x0, x1,...

Depending of precision required, the number of iterations can be set.

How to write a program for it?

Simple Algorithm: (Solving Algebraic Equation BISECTION method)

I INPUTS:
degree
coefficients
precision

II SETUP:
Range

III LOOP:

WHILE actualAccuracy > precision
Var1  ->  mean(range)
Var2 = FUNCTION value(degree,coefficients,Var1)

IF Var2>0
Range(2) = Var1;

ELSE
Range(1) = Var1;

IV END OF LOOP:

Where do I find the source code?

   SOURCE CODE:

           * BISECTION METHOD
           * SUBSTITUTION METHOD

Coming up next:

      Method of False Position

Read More