Errors and digits

Numerical analysis deals with developing methods, called numerical methods, to approximate a solution of a given
Mathematical problem (whenever a solution exists). The approximate solution obtained by this method will involve
an error which is precisely the difference between the exact solution and the approximate solution. Thus, we have

Exact Solution = Approximate Solution + Error.

For example, 1000001 is an approximation to 1000000 with an absolute error of 1, a relative error of -10-6 and
percentage error of 10-4%, while 2 is an approximation to 1 with an absolute error of 1, a relative error of -1 and
percentage error of 100%.

Significant figures
The Significant Figures of a number refer to those digits that have meaning in reference to a measured or specified
value. There are three rules that are used to determine how many significant figures are in a number.

Rule #1: Non-Zero digits and Zeros that are in between two non-zero digits are always significant.
Rule #2: Leading zeroes are never significant.
Rule #3: Trailing zeroes are never significant.
 Rounding off
The following are the rules for rounding-off:

CASE A: For example, 6.422 rounded off to 1 decimal point

The last digit kept should be unchanged if the next digit becomes 6.4.
is less than 5.
CASE B: For example, 6.4872 rounded off to 2 decimal points
The last digit kept should be increased by 1 if the next becomes 6.49. Similarly, 6.997 rounded off to 2 decimal
digit is greater than 5. points becomes 7.00.
CASE C: For example, 6.6500 rounded off to 1 decimal point
If the next digit is 5, then the last digit kept should becomes 6.6. Similarly, 7.485 rounded off to 2 decimal
be unchanged if it is even. points becomes 7.48.
CASE D: For example, 6.755000 rounded off to 2 decimal points
If the next digit is 5, then the last digit kept should becomes 6.76. Similarly, 8.995 rounded off to 2 decimal
be increased by 1 if it is odd. points becomes 9.00.

Bisection method
We start with an initial interval a0 ,b0  containing the root by checking the condition that f a0  f b0   0 , that is
f a0  and f b0  have opposite signs. Then the first iteration is obtained as follows:
Example: Using Bisection method find a positive root of
2
 x
   sin x  0
2
Correct to 3 decimal places.

Answer is x  1.934 .

Check this link - [Link]

Regula-falsi method
Example: Using Regula-Falsi method solve 2 x  2.5x  5  0 correct to 6 significant figures.
3

We have f 1 f 2   0 . Therefore the iteration table is as follows:

Answer is x  1.66009. Check this link - [Link]

NOTE: Regula-Falsi method converges faster than Bisection method.

NEWTON-RAPHSON method
Example: Using Newton-Raphson method solve
x3  x  1  0
Correct to 4 decimal places.
1 2
We have f 1 f 2   0 . So let’s begin the iteration with x0   1.5 .
2
Therefore the iteration table is as follows:

Answer is x  1.3247 .
interpolation
nEWTon’S FoRWARD InTERpolATIon
nEWTon’S backWARD interpolation
Example.
Example.

lAGRAnGE’S interpolation
 nEWTon’S DIVIDED-difference
interpolation
To illustrate this method, let us first see the linear and quadratic interpolation. Then we shall move on to the general
form of Newton’s divided difference interpolation method.

Linear Interpolation

Given the points x0 , y0  and x1 , y1  . So, f x0   y0 and f  x1   y1 .

As there are only two points, we can fit a linear interpolation polynomial through the points. So let the linear
polynomial f1 x  be given as follows:

f1 x  b0  b1 ( x  x0 )
Quadratic Interpolation

Given the points x0 , y0  , x1 , y1  and  x2 , y 2  . So, f x0   y0 , f  x1   y1 and f x2   y2 .

As there are three points, we can fit a quadratic interpolation polynomial through the points. So let the quadratic
polynomial f 2 x  be given as follows:

f 2 x  b0  b1 ( x  x0 )  b2 ( x  x0 )(x  x1 )
Trapezoidal rule
SImpSon’S onE-third rule
Gauss-elimination method
Gauss-Jordan matrix inversion
method
That is, given an n n matrix A ,

Then matrix B is the inverse of A .

Thus,

Example. Solve by Gauss-Jordan matrix inversion method:

x y  1
yz  5
2x  2 y  6

Solution We can write the given system as AX  B , where

1  1 0   x  1
A  0 1 1 , X   y  ,  
and B  5 .
 
2 2 0  z   6 

We first find A 1 using Gauss-Jordan matrix inversion method as follows:

Hence,
 1/ 2 0 1/ 4  2 0 1
A   1 / 2 0 1 / 4    2 0 1  .
 
1 1
4
 1 / 2 1  1 / 4  2 4  1

And thus,
 2 0 1   1  4  1 
1 1    1   
X  A B    2 0 1   5    8    2
4 4
 2 4  1  6  12 3

Therefore the solution is x  1 , y  2 and z  3 .

MATRIX (LU) FACTORIZATION method
IMP: A matrix may not always have an LU decomposition. Sometimes it is impossible to write a matrix in the form
“lower triangular” × “upper triangular”. Then when can we do so? The following is the answer:
 1 2 3 
  1 2 
But the matrix 2 4 5 cannot be decomposed in LU form, for the second leading submatrix 
2 4
has
 
1 3 4 

determinant equal to 0.

GAUSS-SEIDEL ITERATIVE method

Unlike the previous three methods, this is an iterative method. It is as follows:
 Hence, the solution is x1  0.186 , x2  0.331, x3  0.423 .
Note: There can be systems where the above may not converge. For example, consider the following system:
So you can see from the table that the approximations become progressively worse instead of better, and you can
conclude that the method diverges. So the question arises when will a system converge, and not diverge?

The following definition followed by a theorem answers this question.

That is, if

Now we have the following theorem:

Observe that the coefficient matrix of the system in Example 1 was diagonally dominant, while that of Example 2
was not. However, we can swap the equations and make the coefficient matrix diagonally dominant, and then
apply the method as follows:
 EUlER’S mETHoD
In this section, we will discuss solving an initial value problem (IVP) for an ordinary differential equation. The
initial value problem for an ODE is given by
y '  f ( x, y )
y ( x0 )  y 0
However in this method we don’t find the particular solution of the ODE, instead we only find the value of y for a
given value of x . The simplest numerical method for a first order ordinary differential equation is obtained by
replacing the first order derivative of the unknown function by its finite difference formula. Since we know the
value of the unknown function y at a point x0 , for obtaining the value of y at the point x1  x0  h , we use the
forward difference formula for the derivative given by

y ' ( x) 
1
y( x  h)  y( x)
h
Thus the given ODE becomes
1
y( x  h)  y( x)  f ( x, y)
h
 y( x  h)  y( x)  hf ( x, y)
This can be used to obtain the value of y ( x1 ) in terms of x0 and y( x0 ) as
y( x1 )  y( x0 )  hf ( x0 , y0 )
 y1  y0  hf ( x0 , y0 )

In general, if we know the value of yi , i  0,1,2,3,..., (n  1) , we can obtain the value of yi 1 by using the forward
difference formula at xi to get
yi1  yi  hf ( xi , yi ) , i  0,1,2,3,..., (n  1)

Hence, steps for Euler’s method are:

1. Find xi ’s using the formula xi  x0  ih , so that xn becomes the given point at which we need to the y value.
That is, we need to find yn .
2. Use the formula yi1  yi  hf ( xi , yi ) successively to find yn .

Geometrical Interpretation:

A geometric insight into Euler’s method is shown in the following figure. The tangent line to the graph of y (x) at
x  xi has slope f ( xi , yi ) . The Euler’s method approximates the value of y( xi  1) , that is yi1 , by the
corresponding value of tangent line at the point x  xi .
Ex. Find y(0.04) correct to 5 decimal places for the IVP: y'  y , y(0)  1 , taking h  0.01 .

Sol. Applying Euler’s method with h  0.01 , we get

Hence, y(0.04) correct to 5 decimal places is 1.04060.

Check this link for more examples -[Link]

RUNGE-KUTTA method
Although Euler’s method is easy to implement, yet it is not so efficient in the sense that to get a better
approximation, one needs a very small step size. One way to get a better accuracy is to include the higher order
terms in the Taylor expansion to get an approximation to y' ( x) . But the higher order terms involve higher
derivatives of y . The Runge-Kutta method attempts to obtain higher order accuracy and at the same time avoid the
need for higher derivatives, by evaluating the function f ( x, y) at selected points on each sub-interval.

R-K Method of Order Two

Let y be a solution of the ODE y'  f ( x, y) , y( x0 )  y0 . The Runge-Kutta method of order 2 is obtained by
truncating the Taylor expansion of y( x  h) after the quadratic term. It is given by
1
yi 1  yi  (k1  k 2 )
2
where,
k1  hf ( xi , yi ) ,
k2  hf ( xi  h, yi  k1 )
 
The truncation error of Runge-Kutta method of order 2 is of order O h 3 , whereas Euler’s method is of order
 
O h 2 . Therefore, for a fixed h  0 we expect to get more accurate result from Runge-Kutta method order 2 when
compared to Euler’s method.

R-K Method of Order Four

It is given by
1
yi 1  yi  (k1  2k 2  2k3  k 4 )
6
where,
k1  hf ( xi , yi ) ,
 h k 
k 2  hf  xi  , yi  1 
 2 2
 h k 
k3  hf  xi  , yi  2 
 2 2
k4  hf ( xi  h, yi  k3 )
The truncation error of Runge-Kutta method of order 4 is of order O h 5 .  

The same problem when solved with 4th order R-K method gives the following values:

Hence best approximation is obtained by 4th order R-K method.

Check this link for more examples - [Link]

MILNE’S pREDIToR-CORRECTOR method

A predictor-corrector method is an algorithm that proceeds in two steps. First, the prediction step calculates a rough
approximation of the desired quantity. Second, the corrector step refines the initial approximation using another
means.

In this method, four prior values of y , viz. y0 , y1 , y 2 and y3 are needed to evaluate the value of y 4 . In fact in this
method, we always find the value of y 4 . A predictor formula is used to predict the value of y 4 , and then a corrector
formula is used successively to improve its value.

NOTE: The four prior values of y are given in the question. In case they are not given, we find them by any of the
methods we have learnt earlier.

The predictor formula is given by

4h
y 4p  y0  (2 y1/  y 2/  2 y3/ )
3
And the corrector formula is given by
h /
y4c  y2  ( y2  4 y3/  y4/ )
3
Observe that the predictor formula is used only once. Further while calculating the first corrected value of y 4 , we
use y 4p . From the second iteration, we keep on putting the latest value of y4c again and again in the right-hand side
until its two consecutive values match up to the desired level.
Example: Find y(0.2) correct to 5 decimal places by Milne’s Predictor-Corrector Method.

dy
 xy  2 y . Given y(0)  1 , y(0.05)  1.106553, y(0.1)  1.227525, y(0.15)  1.365130.
dx

Solution. Here f ( x, y)  xy  2 y , and h  0.05 . Also y0  1 , y1  1.106553, y2  1.227525 , and

y3  1.365130 .

Since two consecutive values of y4c are same, the required solution is y4  y (0.2)  1.52196 .

Check this link for more examples - [Link]

FINITE-DIFFERENCE method
A differential equation with boundary conditions, i.e., an initial condition and a final condition is said to be a
Boundary Value Problem (BVP). In our syllabus we shall solve only second order differential equation. So in our
syllabus, a BVP will look like this:
d2y dy
2
 P( x)  Q( x) y  R( x) , y(a)  A , y(b)  B where P(x) , Q(x) and R(x) are functions of x .
dx dx
We will be given a BVP like above along with either h or n , the number of subintervals of (a, b) . They are related
by the formula b  a  nh , just like the previous methods.

The algorithm for this method is as follows:

STEP 1: Break the interval (a, b) into n subintervals and name the points as follows:
a  x0 , x1  x0  h , x2  x0  2h , x3  x0  3h , … , xn  x0  nh  b .
The corresponding y values are y0 , y1 ,…, yn . (Observe that y0  A and yn  B are given in the question)
d2y dy
STEP 2: Substitute 2 and in the given ODE by the following central finite differences:
dx dx
d 2 yi yi 1  2 yi  yi 1

dx 2 h2
dyi yi 1  yi 1

dx 2h
To obtain
yi 1  2 yi  yi 1 y y
2
 P( xi ) i 1 i 1  Q( xi ) yi  R( xi ) , for i  1,2,..., (n 1)
h 2h
Now on putting i  1,2,..., (n  1) and arranging the equations with respect to yi ’s and also putting the values of xi ’s
and that of y0 and yn obtain a system of (n  1) linear equations in (n  1) variables, namely y1 , y 2 ,…, yn1 .
STEP 3: Solve the above system to find the values of y1 , y 2 ,…, yn1 .

 x
Example: Find y(1.5) , y (2) , y(2.5) from y"1   y  x . Given that y(1)  2 and y(3)  1 .
 5
Solution: We have x0  1 , x1  1.5 , x2  2 , x3  2.5 and x4  3 . Hence h  0.5 . Also y0  2 and y4  1 .
yi 1  2 yi  yi 1
Now substituting yi 
//
in the given ODE we get,
h2
yi 1  2 yi  yi 1  x 
 1  i  yi  xi
h2  5
 h2 
 yi 1   2  h 2  xi  yi  yi 1  h 2 xi , for i  1,2,3 .
 5 
 yi1  2.25  0.05xi yi  yi1  0.25xi , for i  1,2,3 .
Putting i  1,2,3 successively we get,
y2  2.25  0.05x1 y1  y0  0.25x1
y3  2.25  0.05x2 y2  y1  0.25x2
y4  2.25  0.05x3 y3  y2  0.25x3
Next putting all the known variables, viz. x1 , x 2 , x3 , y0 and y 4 , we get
y2  2.175 y1  2  0.375
y3  2.15 y2  y1  0.5
 1  2.125y3  y2  0.625
Solving the above system we get
y1  y(1.5)  0.31472731, y2  y(2)  0.9404681, y3  y(2.5)  1.2072791.

Check the following link for other examples.

NOTE:
1. Use the formulae for y" and y' directly in exam as shown in the video while solving a problem. You don’t have
to derive them.
2. Finally you have to solve a system of linear equations where the variables are y1 , y 2 ,…, yn1 . This you can
solve by any method you want. In this video they have solved by a method not known to you, so you don’t have
to worry about that. Just use any method you want.

The link - [Link]