Lecture 07

IIT Kanpur July 201
20 followers
Oct 23, 2023
Previously we have discussed several aspects of numerical method. First we
have talked about what we exactly do when we apply numerical methods for
problem solving and then we have established that the problems we solve
in numerical methods they usually come from physical phenomena. We discussed how
to model a physical phenomena and then how to solve those model equations and
we have seen that usually solution of those model equations involve numerical
methods. Now all these previous lectures together the completes the introductory
phase of our course and now we are really getting into the numerical
methods of different kinds and first we'll start from root finding which
means that we'll study the solution of equation consisting only one unknown and
first we'll look at a method that we call bisection method. So in bisection
method what we do is that for solving fx equals 0 we start by identifying an
interval around the solution. For example this is the initial interval around the
solution and then our goal will be to narrow down this interval iteratively to
get the solution. So let us see how we can solve algebraic equation of one
unknown using bisection method. We take an algebraic equation and by algebraic
again and again using this term what we mean that we are not talking about
differential or integral equations. We'll come to differential equations later on
but right now we are not talking about them. We are only considering now
algebraic equation of one unknown and such equations in general can be written
as fx equals 0 where x is the unknown. Such equations we call linear if they're
of the type of ax plus b. Here a and b are known constants so ax equals b equals
0. If that is the equation then we can solve this equation very easily
analytically. For a not equal to 0 we know that the equation gives us a
solution of x equals minus b by a so it's very easy and there is no question
of using numerical methods for such cases. However if the equation is not of
this type then the equation is called nonlinear. Now nonlinearity comes from
various terms such as in a nonlinear equation you can get sine x cos x log of
x etc etc. You will get x to the power n where n is neither 0 nor 1. That means
in your equation you may get x square x cube root over x etc etc. So when you
get some of this kind of terms in your equation then your equation is
definitely nonlinear in nature. If you plot this fx equals ax plus b you get a
straight line but if you plot any such equation where you have such terms you
don't get a straight line you get some kind of a nonlinear curve. Now we wish to
solve this nonlinear equations. Now how do we solve this nonlinear equations?
Sometimes we have nonlinear equations where we can have the solution
analytically. For example if we have a quadratic equation we know how to solve
a quadratic equation analytically. But most nonlinear equations cannot be
solved analytically. For example if I have an equation x plus tan x equals 2
this cannot be solved analytically. This is a nonlinear equation and we have to
use some numerical method to solve it. Here our focus is a nonlinear equation
of one unknown and such equation is written in general fx equals 0. There are
fundamentally two approaches of solving such equation. In first approach we
start with an interval x1 x2 and the solution we know that falls between x1
and x2. Once this x1 and x2 are identified subsequently what we do is
that we iteratively close this gap. So our goal is to reduce this x1 minus x2
that means bringing x1 and x2 closer and closer iteratively and eventually we'll
come very close to this solution where we will terminate our calculation and
we'll assume that we have reached the solution. This is a kind of technique
that we call bisection. There are other techniques also they follow the same
type of procedure same philosophy of procedure but we'll look at one of them
that is bisection. The other approach is that we can solve linear equations so we
linearize the nonlinear equation and how we do so we'll look into it and this
linearized equation we solve it but linearized equation is not the actual
equation so what happens that is not the correct solution so we iteratively
update this linearized solution. It doesn't seem very easy now but you'll see
this is an easy procedure and we'll see it in subsequent lecture. This kind of
procedure is something that we call a Newton-Raphson type method and we'll
talk about Newton-Raphson in subsequent lecture. Right now let's discuss
bisection method. So let us see how we can solve the equation fx equals 0 using
bisection method. This is a function y equals fx if I plot it it shows it like
this blue curve. It is not necessary to plot it to solve fx equals 0 using
bisection method but this kind of a pictorial description will help us to
understand how does this method work. So what we do is that we first here in this
case we know that fx equals 0 give the exact solution. We don't know the exact
solution but let us say that if we have the exact solution then that will be at
this fx equals 0 so at this particular point where this blue curve cuts the x
axis that would be the point that would be the x location if I take the x
location that would be the root of this equation. Now if I go to a right side
then I see that my fx is greater than 0. If I go toward left side then I see that
my fx is less than 0 and exactly at this point at this root fx is equal to 0. Of
course depending upon the nature of this curve it may so happen that right side
is less than 0 and left side is greater than 0 that may so happen but the main
point here is that the root comes at fx equal to 0 and one side of the root will
be fx greater than 0 which eventually is the right side here and another side
of root is fx less than 0 which incidentally is the left side here. So
now what we do is that we take some trial and from our trial we identify two
points one is x1 and another is x2 such that f of x1 multiplied by f of x2 less
than 0. What does that mean? Well if f of x1 and f of x2 individually both are
less than 0 that means both of them will be on this side then of course their
multiplication cannot be less than 0. Their multiplication will be greater
than 0 if individually both of them are less than 0. On the other hand if f of x1
and f of x2 both are in this side then they are both positive that means their
multiplication will again be greater than 0. So when I say that we have
identified two points x1 and x2 such that f of x1 multiplied by f of x2 less
than 0 what we mean that one of this point is on right side of the solution
and another point is on the left side of the solution. So for instance it could be
like this x1 is here and x2 is about here that means f of x1 is negative f of
x2 is positive that means f of x1 multiplied by f of x2 is less than 0. We
can try different values of x1 and x2 and from that we can get two points such
that this condition of f of x1 f of x2 less than 0 is satisfied. So we
understand that between this x1 and x2 this function will change its sign which
tells us that between these two points x1 and x2 there must be a point where f
of x equals 0 and that tells us that between these two points x1 and x2 we do
have a root. Now the question is how we can close this gap of x1 and x2 and
reach this root. So we employ a very simple method here and the method of
narrowing the interval of x1 x2 is as follows first or we call it iteration 0
in iteration 0 I get the value of x and superscript within bracket 0 means this
is iteration 0 so this is the value of x at iteration 0 is x1 plus x2 divided by 2
so I have taken this x1 this x2 I divide this x1 plus x2 and I divide by 2 so I'll
get it somewhere in between x1 and x2 I don't know exactly where but I have just
assumed it will be here and this will be my x0 that is the 0th iteration of x. Now
this 0th iteration of x will see that it is on the left side or it is on the
right side if it is on the left side then what it will do we'll take that
this well this x1 is not needed anymore we now know that root will be between
this x0 and x2 so what we do this x0 I set it as my new x1 however if that does
not happen if x0 falls on the right side then I know that my root will be
between this x0 and x1 in that case we take this x0 here and we take that as my
new x2 here this arrow right arrow means assigning the value of this x0 in
x1 or here this assigning the value of this x0 in x2 so in iteration 0 either
x1 or x2 one of them will be updated not both one of them will remain just the
same and one of them will be updated they will be updated by x1 plus x2 by 2
now of course we are ready to go to iteration 1 and iteration 1 once again
we'll take this x1 plus x2 by 2 but you can see that now my interval is shorter
than what it was before although they look similar x0 is x1 plus x2 by 2 x1 is
x1 plus x2 by 2 however one of this has changed either x1 or x2 has changed it
has come closer to the root either on left side or on right side therefore this
iteration 1 value of x we hope that it will be closer toward this root and this
is how we keep on coming closer and closer toward the root eventually of
course we have to stop the iteration and we have to assume that we have come
close enough to the root as you can understand that in numerical method we
never reach exact solution we can only come closer and closer to it we have to
set a convergence criteria we also call it stopping criteria where we'll stop
our calculation to do so we'll check this x for every x we'll check this f x
of xk and when this comes to be very small the small real number epsilon that
will set it according to the accuracy that we need when f x of xk absolute
value of this is very small this is close to 0 we'll assume that my xk is
the acceptable solution it will still not be equal to the exact solution but
it will be our acceptable solution and we'll stop our calculation there so let
us see an example so we take a very simple problem this is x square minus 7
x plus 10 equals 0 it's very easy to see that it has an exact solution of x
equals 2 and x equals 5 we can use bisection method and try getting one of
this solution in bisection method we can only get one solution so between the two
intervals we assume that there is one solution if there are multiple solutions
between the two intervals we'll only get one of them so here you see that for x
1 equals 0 fx is 10 and for x 2 equals 3 fx is minus 2 so we are very sure that
between 10 and minus 2 there is a solution fx equals 0 so between 0 and 3
x 1 equals 0 it is 10 and x 2 equals 3 it is minus 2 so between 0 and 3 there
must be a solution fx equals 0 between 0 and 3 so we have a root in this
interval 0 and 3 so let us try to find that root if I keep on calculating it
and create a table I'll get a table like this so this is my iteration counter
first column in iteration 0 I have x 1 equals 0 and x 2 equals 3 so my x is the
average of this 2 that is 1.5 and f of x is 1.75 remember that when f of x is
close to 0 we'll sort of reach the solution so now with this x I update the
x 1 my x 2 remains same so my x new x comes 1.5 plus 3 divided by 2 that is 2.25
and f of x comes minus 0.6 875 you can see that earlier it was 1.75 now it is
0.6 875 so it is coming down then I take this 2.25 it is my new x 2 my x 1 is 1.5
so my x is 1.5 plus 2.25 divided by 2 that is 1.875 f of x is 0.3906 you can
see that we are coming down in this manner if we continue our calculation we
will see that this x 1 and x 2 are coming closer and closer they were
initially 0 and 3 which means that in between them we had this root of 2 now
you can see that it is coming 1.5 to 3 1.5 to 2.25 1.875 to 2.25 etc etc so then
you can see that from 7th iteration it is coming 1.99 to 2.01 in that range and
it is still coming down in 10th iteration it is 1.9980 there will be
difference between 9th and 10th in more significant digits if we take but for
simplicity I have removed those digits in the table so you can see that within
10 iteration it comes down to 1.9980 2.0009 my x is 1.9995
we know exactly the x is 2 it is coming 1.9995 and f of x is 0.0015 it is small
but it is still not very close to 0 so we keep on iterating it and we can see
that my fx is coming down closer and closer to 0 and my x is coming closer
and closer to 2 so we are convinced that we are going in right direction and
more iteration will give us the acceptable value of the root our
iteration will stop when the value of this fx is less than this epsilon which
we can define depending upon the accuracy that we want to have one of the
major advantage of bisection method that it will always converge to the root and
that is a huge advantage in any engineering application so let us take
that we are starting from this interval x1 and x2 and this 0 indicates their
0th value so initial value of x1 and x2 which means that it is their 0th
iteration will now iteratively update this x1 and x2 when we update this x1
and x2 we go to first iteration we know that one of them will remain same and
one of them will be replaced by the average of previous iteration so in
iteration 1 x1 1 may remain same and x2 may be updated using the average of
previous iteration x1 and x2 so it is either this or it could be so that x2
remains same as the previous iteration value and x1 is updated with the average
of x1 and x2 from previous iteration so one of this will happen after the
iteration 1 then we see that the difference between x1 and x2 after
iteration 1 is any way I take it I see from both side this is x1 0 minus x2 0
by 2 or what we can say that iteration 1 the difference between x1 and x2 is
equal to the difference between x1 and x2 at iteration 0 divided by 2 so their
difference is decreasing which means x1 and x2 are coming closer and closer
similarly after iteration 2 what we will have is that x2 that means x1 in
second iteration x2 in second iteration their difference equals x1 in first
iteration x2 in first iteration their difference divided by 2 now we know that
x1 minus x2 in first iteration equals x1 minus x2 in 0th iteration divided by 2
so I can write that this is equal to x1 minus x2 in 0th iteration divided by 2
square taking help from here if we proceed this way we can say that after
kth iteration my x1 minus x2 will be x1 minus x2 at 0th iteration divided by 2
to the power k which means for large value of k the difference between x1
minus x2 will be very very small in other sense that limit k tends to
infinity their difference will be 0 so if I have infinite iteration this x1 and
x2 will fall exactly over one another but we are not going through infinite
iteration but increasing the value of k gives us closer and closer range of x1
x2 so limit k tends to infinity x1 k minus x2 k equals 0 therefore we can say
that bisection method will always converge to correct solution of course
to reach the correct solution it may require large number of iteration here
what you see is a pseudocode for bisection method we have not discussed
pseudocode yet it is coming in next week so don't worry about it if you don't
know what it is but essentially this is a computer program written in our own
language this will not run in a computer this is for our own understanding here
this is the input input is f of x x1 and x2 where f of x1 multiplied by f of x2
is less than 0 and we are also giving an input of this maximum error which is
the epsilon or the stopping criteria the final result will be x naught where f of
x naught is less than this maximum error or epsilon so here you can see that I
get this y1 and y2 form at this x1 and x2 and as long as this is less than 0 I'll
go through this calculation if it is not less than 0 I'll simply print that we
have invalid input and we'll exit the program then we calculate the error
error will be minimum of this y1 or y2 whatever is minimum and this as long as
my error is greater than maximum error then we'll do this calculation what I
have already explained we'll get this value of x naught is x1 plus x2 by 2
we'll check if this x naught is good enough if it is not then we'll replace
this x naught it will be either x1 or x2 and we'll continue this way until the
solution converges now to summarize this lecture we have seen bisection
method the theory the convergence as well as an example it solves one
equation for one unknown it starts from an interval that consists the intended
root and then the goal here is to close the interval iteratively using the
technique that I have discussed and using simply a handheld calculator you
find one root using bisection method for this equation x square minus 7x plus 7
equals 0 you develop the table as I have shown in this lecture hand
calculation is enough you do not have to write a computer program even if you can
write a computer program I'll still urge you to do a manual calculation this is
will help you to understand how the procedure works that's all for this
lecture thank you and I'll see you in next class
