Tip:
Highlight text to annotate it
X
Hi and welcome to this last lecture of module four. In module four, we were so far, we are
discussing about getting solutions to non-linear equations. The non-linear equations in general
of the type f x equal to 0 and we looked at several methods to get the solutions for a
single variable case. And in the previous lecture we extended to multivariable case,
where we had several functions of several different variables and trying to find out
all the values of those x 1 to x n that satisfy the equation f 1 equal to 0, f 2 equal to
0 up to f n equal to 0.
Specifically, we looked at the fixed point iteration method and the Newton Raphson's
method and in the last I guess 20 minutes or so, we just covered some of the extensions
to the Newton Raphson's method that are useful in making the method either more accurate
or more applicable in some sense. So, that is what we have been talking about so far,
f of x equal to 0, there is another type of problems of the same slot f of x equal to
0 where f of x is a polynomial function. Root finding for polynomial functions: What
I have done over here? I have listed just three particular examples of polynomial, polynomials.
The first one is x cube minus 7 x plus 6. You can write this as x cube minus 6 x minus
x plus 1 and then you can do a very straight forward algebraic manipulation on that and
you will essentially get this particular polynomial factored as x minus 1, x minus 2 and x plus
3. Product of these three terms if you call this as f, f 1 of x equal to 0 then the x
values that satisfy f 1 of x are going to be x equal to 1, x equal to 2 and x equal
to minus 3. This particular guy is going to become 0.
When either this term or this term or this term become 0 , the difference is now given
any arbitrary polynomial .What we want to do is to find out all the roots of that particular
polynomial. What I have also listed over here are two other polynomials and again of the
third order. So, What are the roots of the three polynomials?
The roots for the first polynomial are x equal to 1, x equal to 2 and x equal to minus 3
as we had listed earlier the roots of the second polynomial are x equal to 1, the second
root is again x equal to 1 and the third root is x equal to minus 3. So, x equal to1, 1,
minus 3 and for the third polynomial, if you look at its x square plus 1 equal to 0. So,
x square equal to minus 1 or x equal to plus or minus i. So, the three roots are x equal
to i, i is the complex constant, x equal to minus i and the third is x equal to 3. So,
the point of view let us think these three polynomials was this any polynomial of nth
order, for any nth order polynomial. An nth order polynomial will have exactly n roots
. For example, all of these third order polynomials
have three roots, some of the roots may be repeated, it is not necessary that all the
n roots have to be unique roots. In the first example we got three unique roots one, two
and minus three. However, in the second example we got repeated roots. So, one and one are
actually repeated roots then may be repeated roots may or may not be, and the final point
is that the roots could be complex numbers as well in this particular case we get a purely
imaginary number in some other cases we might actually get complex numbers also. so, the
third point is complex roots are possible.
So, what we have is when we have an nth order polynomial we are interested in finding all
the n roots of that polynomial. If even, if those roots end up being complex numbers or
even if those roots are repeated roots. So, we will start Newton Raphson's for polinomial
root finding. So, in Newton Raphson's for polynomial root finding. So, what we will
do is we will start off with certain initial guess x one and
use the Newton Raphson's method to get the actual root. Let us call it x bar one, x bar
one just to represent that it is one of the roots of that particular polynomial. So, let
say we look at again this the first polynomial x minus 1 multiplied by x minus 2 multiplied
by x plus 3 and essentially if we start off with that particular polynomial perhaps for
that polynomial the curve is going to look. So, we have intersection at minus 3 plus 1
and plus 2 for negative values of x for very large negative values of x the function f
is going to be very negative highly negative. So, perhaps I think if I have to guess this
curve is may be the curve is going to look at somewhat like this. I am just drawing a
cartoon and do not mean the curve to be exactly in this form. So, the three roots are minus
3 plus 1 and plus 2, these three roots and what we are interested in doing is we are
interested in finding out all these three roots of this particular equation. So, let
us say we start with our x one at this particular value let us, because we do not know assuming
we do not know anything about at this particular equation. Let us start with x equal to 0 as
the initial guess we start with x equal to 0. We using Newton Raphson's method we will
first get our x, x one bar equal to 1. So, we started off with with a polynomial of the
form x cube minus 7 x plus 6 from x cube minus 7 x plus 6. We found one of the polynomials
was x bar equal to 1 of the roots were x bar equal to 1. So, what does that mean that just
means that x minus 1 is a factor. So, x minus 1 is a factor of x cube minus
7 x plus 6. So, what we can then do is divide essentially x cube minus 7 x plus 6 by x minus
1 and if we do that x cube minus 7 x divided by x minus 1. Basically, what we should be
getting is x minus 2 multiplied by x plus 3. So, this should essentially lead us to
x square plus x minus 6. So, we started with a polynomial of third order we use the Newton
Raphson's method to find out one of the roots of that polynomial once we found out that
root we divided the original polynomial with x minus the root that we have found and we
got a polynomial of one order lower. So, we started with let us call all over polynomials
lets represent them as p subscript n which represents n represents the order of the polynomial
p represents that it is a polynomial when the first root is found, when the root x 1
bar is found the polynomial what is known as deflating the polynomial the polynomial
can be deflated to p n minus 1. So, I will write that over here p n is going to be equal
to p n minus 1, multiplied by x minus x 1 bar the curve x square minus x plus 6 perhaps
would look, let us so, this was our P 1 this became our P 2.
Now, in the polynomial this was our P 3 from P 3 we went to P 2 after deflating out the
polynomial x bar after deflating out the factor x minus 1. Now, this particular curve now
intersects the x axis at two points minus 3 and plus 2, what we can essentially do is
we can start again with our Newton Raphson's method with our x 1 bar equal to the pervious
solution. So, we can start off our x 1 bar at this particular value then use Newton Raphson's
method perhaps will go this way, this way, this way and so on. And we will end up at
the solution two. So, what has happened is we first from p n minus 1 we obtained x 1
bar deflated that particular expression to p from p n we deflated that expression to
p n minus 1, from p n minus 1 we got our second solution x 2 bar and deflated it to p n minus
2 and we repeat this until we reach P 1.
Each time we get a solution, we deflate the overall polynomial by deflating I mean nothing
but, removing that particular factor from that the original polynomial that we started
off. So, I will just write down the algorithmic steps that we are going to flow in this particular
case is we start with p n, second part is choose initial guess x one and subscript one
to represent that we are trying to find the first root of that particular polynomial use
Newton Raphson's to get the first root or in general x 1 bar. So, we will use the Newton Raphson's
to get the first root x one bar deflate polynomial to get p n minus 1 and then essentially repeat
this step this steps from two onwards repeat the steps until we get all the solutions.
And when we are actually going to repeat the steps at that time we will choose the initial
guess x 2 1 we will get Newton Raphson's, we get the second root x, x 2 bar deflate
the polynomial to get p n minus 2 and keep repeating over and over again.
So, I will use instead of 1 and 2 and 3 I will just use i over here to indicate the
i th root and we will repeat this until we get the polynomial P one, the question happens
is what if we have we do not have real roots but, we have complex conjugate roots. but,
going back to what we discussed in the previous lecture improvements to Newton Raphson's method
in case of multiple roots we had said that improvement to the Newton Raphson's method
would be x i plus 1 is going to be equal to x i minus m times f of x i divided by f dash
of x i. So, this was what we said was Ralston's improvement to if there are m repeated roots.
Now, in the polynomial of p n whenever we have a polynomial of p n there are n repeated
roots which of course, means we will replace this m by n when we deflate that polynomial
to p n minus 1 instead of this expression we will use n minus 1 multiplied by f divided
by f dash, when the polynomial becomes p n minus 2, we will use this as n minus 2 f divided
by f dash where of course, f is going to be replace by p n p n minus 1 p minus 2 and so
on. And f dash is going to be nothing but, the first derivative of the specific polynomials.
So, this is the procedure we can actually follow in step number three. So, the Ralston's
modification is something that we can use in step three in order to get fasted convergence
of the Newton Raphson's method for multiple roots this is because, we know a priory that
a polynomial of the form p n has n roots and we are interested in finding out the n roots
of that particular polynomial and every time we deflate the polynomial the number of roots
decreases by one.
So, that is basically the background of using a Newton Raphson's method directly to two
polynomials. Now, the question is this the best that we can do especially when we have
quadratic when we have complex roots and in case of complex roots there is indeed a better
method to use and we will go back to what the expressions that we had and we will just
look at this particular expression where we would get complex roots.
To what we got was there was one real root x equal to 3 and there were two complex roots
x equal to i and x equal to minus i, the complex root will for all the real coefficients. We
know that they always come in complex conjugate pairs. And so, if we have one complex root
one complex root is say a plus i b then are sure to have another complex root a minus i b we are definitely
going to have if a plus i b is a complex root a minus i b is also going to be a root of
that particular equation and then if you multiply the two roots x minus 8 minus i b multiplied
by x minus a plus i b when we when we multiply these guys essentially, we will get this essentially
in the form let say x square plus p x plus q.
Where p and q are real numbers, what we are going to do in our new method is basically
deflate the polynomial by from p n to p n minus 2 form p n minus 2 to p n minus 4 and
so on, until either you are left with P 1 or you are left with P 2 you are you will
be left with P 1 if the order of the polynomy or polynomial is an odd order will be left
with P 2, if the polynomial order is an even order. So, Let us let us go forward and look
at what we can do and this is going to form the basis of the Bairstow's method.
Bairstow's method: for root finding
and the Bairstow's method for root finding is the first part is going to be as follows.
Let say any polynomial p n, let us represent that as a 0 plus a 1 x plus a 2 x squared
plus a 3 x cube plus so on, up to a n x to the power n. Let q equal to, x square plus
p x plus Q b one particular second order polynomial, what we are interested in finding out is whether
this particular guy Q whether or not it is a factor of p n. So, any polynomial p n can
be written as a product p n minus two multiplied by Q, f Q is a factor then this is what we
will be able to write for example, in this particular case x square plus 1 was a factor
of this particular polynomial. So, we could write p 3 equal to q multiplied by p 1. If
we do not have x square plus 1 but, we have certain other polynomial we will not be able
to write it in this particular form but, there will be a remainder.
This is exactly how we write any number, you know a divided by b if that is equal to some
coefficient P and some remainder R we will write a equal top multiplied b plus R and
that is essentially what we are writing, only difference is this is for a polynomial function.
So, now p n minus 2 we will be able to write that as b 0 plus b 1 x plus b 2 x square and
so on, up to b n minus 2 x to the power n minus 2. So, and we let us write R as nothing
but, C 0 plus C 1 x. So, p n minus 2 multiplied by Q, is going to be nothing but, b 0 plus
b 1 x plus b 2 x squared plus so on, up to b n minus n minus 2 x to the power n minus
2 multiplied by x square plus p x plus q. Which we would be able to write this as x
square b 0 plus b 1 x cube plus b 2 x to the power 4 and so on, up to say b n minus 3 x
to the power n minus 1 plus b n minus 2 x to the power n. So, this is when we multiply
x square with this plus multiplying p p x with this bit particular term we will get
b 0 p x plus b 1 p x square plus b 2 p x cube plus b 3 p x to the power 4 and so on, up
to b n minus 2 x to the power n minus 1 this is b n minus 2 multiplied by x to the power
n minus 2 multiplied by p multiplied by x will give us b n minus 2 multiplied by p multiplied
by x to the power n minus 1. I am sorry, I miss the p over here and then
we multiply q with all of this and so, we will have b 0 q plus b 1 q, b 1 q x plus b
2 q x square plus b 3 q x cube plus so on, up and there will not be an x minus x n minus
1 term over here we will end up with p b n minus 2 multiplied by x to the power n minus
2 term. So, when we add all these guys up we can collect the terms in x to the power
n collect the terms in x to the power n minus 1 and so on, and so forth and equate them
to the original polynomial that we had. So, this is our p n minus 2 p n minus 2 multiplied
by q what will do will actually this part from now, and R we will write this as equal
to C 0 plus C 1 x and when we add all these terms up, when we add all these terms we should
essentially get this. Now what we will do is we will start at the other end at the nth
power of this particular term and start moving towards the lower power.
So, b n minus 2 x 2 the power n and then we have a n x to the power n these have to be
equal for this to be for these two things to be equal. Essentially, every coefficient
of x to the power 1, x to the power 2, x to the power 3 and so on, up to x to the power
n should be equal to the original coefficients which gives us essentially b n minus 2 is
going to be equal to a n.
Then the second expression for this is for x, x to the power n term, x to the power n
minus 1 term, is b n minus 3 multiplied by p times b n minus 2, plus p b n minus 2 equal
to a n minus 1, which will give us b n minus 3 equal to a n minus 1 minus p times b n minus
2 for any i th term, if we look at this particular thing for any x to the power i th term, what
we will get for x to the power i we will get b yes, i minus 2 plus p times b, i minus 1
plus q times b i this is going to be equal to a i.
And at this point of time we know b, b i we will know b i minus 1 we will not know b i
minus 2. So, we will be able to write b i minus 2 is equal to a i minus p b i minus
1 or rather we will write this as minus q b i minus p b I minus 1. So, for n we will
have b n for n we will have b, b n minus 2 equal to a n for n minus 1 we will have be
n minus 3 equal to a n minus 1 a n minus a n sorry, for b n minus 2 we will have n minus
3 will have a n minus 1 minus q times b n minus n. So, n minus 1 but, b n minus 1 does
not exist. So, this particular guy will vanish away and we will just have p times b n minus
2. So, writing those out altogether what we will essentially get is b n minus 2 equal
to a n, b n minus 1 equal to a n minus 1 minus p b n minus 2 and b, b i is just going to
be equal. So, b i minus 2 is just going to be equal to a i minus q, b i minus p, b i
minus 1 we will repeat this essentially until we reach b 1 when we actually, reach b 1 at,
at that time. So, until we actually reach the x to the power
2 power when we reach x to the power 2 we will essentially get our b 0 . Once, we get
the b 0 our objective is to find C 1 and C's C 1 and C 0 and C 1 we can get with respect
to from basically the first powers and C 0, we will get with respect to the 0 th power.
So, C 1 plus b 0 p plus b 1 q equal to a 1. So, we will get C 1 plus so, we have C 1 plus
b 0 p plus q b 1 q equal to a 0. So, we take all these terms on to the left hand side and we will get basically
C 1 as a 0 minus b 0 p minus b 1 q that is going to be our C 1 and our C 0 is going to
be so, C 0 plus b 0 q equal to a 0. So, a 0 minus b 0 q is going to be our C 0 this
I am sorry, should be a 1. And this i essentially, i goes from basically
from we are going from x, x to the power n minus 2 from n minus. So, b i minus 2 is essentially
going from n minus 2 to 0 or in other words i goes essentially from n to 2, and this is
this is essentially what we will get. So, the idea behind this is that you start off
essentially with assuming start with assuming p and q.
Once you Assume the value of p and q: we basically deflate the polynomial to get
p n minus 1 and q sorry, p n minus 1 and R, check if R equal to 0 or in other words C
0 equal to 0 and C 1 equal to 0, if not we run Newton Raphson's to get C 0 as a function
of p q equal to 0 and C 1 as a function of p q equal to 0 and the value of p and q that
will give C 0 equal to 0 and C 1 equal to 0 is the root for that particular equation.
So, this is the procedure that we will essentially follow in order to get in order to get the
roots of the particular polynomial and we will follow this particular procedure repeatedly
until, we get the entire polynomial deflated from p n to p n minus 2 p n minus 2 to p n
minus 4 and so on up to 0.
So, what we will do next is just basically take one particular example and just go through
that example to see how this deflation is going to going to work. Now, that we have
looked at various solution techniques, what I will just do is just go ahead and summarize
the overall contents of module four and the summary, what we did essentially in the non-linear
equations solving is we started off with the bracketing methods looked at bisection and
Regula Falsi method and then looked at open methods Secant fixed point iteration and Newton
Raphson's method. And then looked at extension of fixed point
and Newton Raphson's iterations to multi-variable systems and modifications essentially, to
Newton Raphson's method to improve the Newton Raphson's method.
So, that is essentially what we have covered and then we covered the root finding the methods
and in root finding essentially what we started off with saying is, there is a possibility
of using the Newton Raphson's method, in order to find the roots of an equation and every
time we find a roots. We go ahead and deflate the overall polynomial and we keep repeating
that over and over again. So, that is what the overall outline, coming back to the summary
first will summarize the overall non-linear equations, solving methods, all the equations
solving methods that we looked at essentially were iterative methods.
So, this is the overall algorithm that we had seen pictorially for this particular example.
We start with an initial guess that is shown by this red dot over here and then we use
chosen strategy to move this red dot to the next point in at this next at this next point
we verify if the stopping criterion is satisfied in this particular case the stopping criterion
is not satisfied. So, we go back use this chosen strategy to move in the direction of
the solution and we do that repeatedly until this stopping criterion get satisfied, when
it does we have the solution that is available.
We have looked at 5 different methods, for us given x i and x i minus 1, how to go on
to find x i plus 1 and I have summarize this in the table. So, the 5 methods that we looked
at bisection Regula Falsi, Regula Falsi is also known as method of false position fixed
point iteration which is also known a successive iteration or successive substitution method
then the Secant method and then finally, the Newton Raphson's method.
The bisection methods starts with two initial guesses Regula Falsi also starts with two
initial guess, these two methods are bracketing methods because they are bracketing method
the two initial guesses have to lie on either side of the solution. When it comes to a fixed
point iteration, when it comes to a Secant when it comes to fixed point iteration and
when it comes to Newton Raphson's method, we only need one initial guess whereas, in
Secants method we need two initial guesses strictly speaking in Secants method we do
not need the two initial guesses to fall on either side of the of the solution. We can
start with two arbitrary chosen initial guesses also.
And x i plus 1, this is how we move from the current initial current guess to the new guess
x i plus 1 in bisection is nothing but, midpoint of the two solutions x l and x r in case of
Regula Falsi and in case of Secant method we join on the line connecting the point x,
f at x l and x, f at x r and find where that is straight line intersects the x axis. As
a result of this both these two expressions, both these two methods have the same expression
the only difference in Regula Falsiis. We retain the solution such that one solution
is to the left hand side of the true solution and the other solution is to the right hand
side of the true solution. Where as in Secant method we only keep x,
the solution the i th solution and the i minus 1 solution only the latest two solutions the
fixed point iteration, we use x i plus 1 equal to g of x i and in Newton Raphson's method
x i plus 1 is x i minus f divided by f dash computed at x i. We also looked at the order
of convergence I am sorry, we also looked at the order of convergence bisection method
was first order convergence fixed point iteration also was first order convergence first order
method. And Newton Raphson's method we saw was the
second order has a second order or quadratic rate of convergence. We did not derive the
rate of convergence for Regula Falsi or for Secant method Regula Falsi and Secant method
have a super linear rate of convergence. That means in the expression e i plus 1 equal to
e i to the power eta, eta is a value that lies between 1 and 2. Typically it lies very
close to a golden, the golden section rules golden section in general you can expect in
the Regula Falsi method to the order of convergence to be anywhere between say 1.4, 1.4 to about
1.6 that is what the Regular Falsi and sub and sub being for Secant it is equal to the
golden section.
Then stability given the two initial guesses are feasible initial guesses the bracketing
methods are guaranteed to be stable whereas, the open methods as we have seen there is
no guarantees on stability of the open methods fixed point iteration method, we looked at
numerical example where the fixed point iteration does not converge. We although we did not
look at numerical examples for Secant and Newton's that do not converge. We really motivated
these two examples using some kind of a graphical method to say under what conditions these
methods are not going to converge. Now, the issues the important issues with
respect to all of these methods is that bisection and Regula Falsi are essentially single variable
methods and we have to insure that f of x changes the sign at x bar. So, for example,
an equation of the sort f of x equal to x square you cannot use bisection method because
we will not be able to find x l and x r which satisfy f of x l multiplied by f of x r equal
to less than 0 , that is because f if f of x is equal to x square the f of x is always
going to be positive no matter what value of f of x we use.
The fixed point iteration the applicability is limited, because of stability issues. We
saw that this conditions for stability of fixed point iteration where fairly stringent
conditions for stability. The Secant method and Newton Raphson's method are both very
versatile and very fast methods. Specifically, the Newton Raphson's method it is a very versatile
method and the reason for popularity of Newton Raphson's method is one because it is x is
a extendable to multivariable systems. Second, because when f dash of x is not available
we can actually use a numerical derivative and when we use a numerical derivative the
Newton Raphson's method kind of resembles a modified Secant method in some ways and
the overall requirement is that the Newton Raphson's method should not have f dash of
x equal to 0. If f dash of x equal to 0 then the Newton Raphson's method cannot continue.
So, requirement for Newton Raphson's method to continue is that f prime should be not
equal to 0. And likewise we should start with an initial
guess which is not far away from the two solution x bar and it is applicable to multivariable
system, and that is the reason why Newton Raphson's is what we considered for multivariable
system as well as we considered the fixed point iteration for multivariable system.
So, the extension to multivariable system for fixed point iteration we saw was straight
forward at kind of follows the same idea that we use in the Jacobi iteration. So, when we
have the equations x bar e f of x bar equal to 0, all we need to do is essentially x of
i plus 1 should be equal to there is a typographical error over here. This should actually be g
and not f. So, x we are to keep up with really the previous notations. So, x of i plus 1
should be equal to g bar of x i and this is what we need to do iterate on over and over
again in order to get until we converge, when we are going to use fixed point iteration.
Where we saw that the sufficient condition for convergence is that the absolute values
of the sum of the absolute values of partial derivatives of the function with respect to
x 1, x 2 and so on, up to x n should be less than an equal to 1. This is the condition
for convergence and I had stated without actually proving or without actually looking at the
examples that this often ends up being a fairly stringent condition for fixed point iteration
which limits actually the applicability of the fixed point iteration method.
And then we looked at the multivariable Newton Raphson's method and the multivariable Newton
Raphson's method is x i plus 1 as x i minus j inverse f where j is nothing but, Jacobean
and this is how the Jacobean is written d f 1 by d x 1 d f 1 by d x 2 and so on, up
to d f 1 by d x n and on the column we have d f 1 by d x 1 d f 2 by d x 1 and so on, up
to d f n by d x n. So, we essentially get this square matrix
these values have to be computed at the guess x bar at i and we substitute that over here,
we substitute a multiply that with the function value computed at x of i. And this is the
iterative equation that we will get the Newton Raphson's multivariable method is also has
a quadratic rate of convergence and then what we looked ahead is certain improvements that
where that have been developed to improve the speed of convergence or to improve the
stability of the Newton Raphson's method.
The Ralston's modification and this is something that we considered in this lecture also the
Ralston's modification if there are m roots is that instead of having x i plus 1 equal
to x i minus f divided by f dash instead of that we multiply this with a factor m. Another
improved Newton Raphson's method based on the Ralston's modification we said was if
we write h of x equal to f divided by f prime the roots of f of x are going to be the same
as the roots of h of x. So, all the roots of f of x will also appear as roots of h of
x and based on that we you we obtained a modified Newton Raphson's formula. In fact if we rigorously
derive this particular formula. We will notice that this is a third order accurate formula.
So, we can actually improve the accuracy of the Newton Raphson's method from a second
order accurate to a third accurate method, the pit fall or on the flip side for this
particular method is not only do we need to calculate f prime, we also need to calculate
f double prime in order for this particular Newton Raphson's. The third order Newton Raphson's
method or the improved Newton Raphson's method to work.
Then the other modifications so, this these modifications where for multiple roots and
especially to speed up the Newton Raphson's method for multiple roots more importantly
are the modifications that ensure stability of the Newton Raphson's method and one of
the biggest problem or two major problems that we had seen with Newton Raphson's method
is one is when f f prime of x becomes equal to 0 and the other case is when cyclically
we keep repeating the same roots. So, that means the root x i sends us to x i plus 1
and then x i plus 1 sends us to back to x i. So, x i plus 2 equal to x i x i equal to
x i minus 2, x i minus 2 equal to x i minus 4 so on, and so forth.
So, we will not get convergence we will keep circling around the actual x bar that is also
a fairly common problem in Newton Raphson's method. So, the straight forward way of modifying
the Newton Raphson's method is what is known as the line search algorithm a line search
is very much like the Jacobi over relaxation order Jacobi under relaxation that we had
looked at. The only difference is instead of using a Jacobi type of iteration we use
that under relaxation factor in the Newton's iteration. So, instead of having x i equal
x i plus 1 equal to x i minus j inverse f, we have x i minus omega j inverse f where
omega is a value between 0 and 1 and that is an under relaxation parameter.
So, what we are saying is we are going to take really smaller steps then what Newton
Raphson asks us to take just to be a bit more conservative in tracking the solution. This
will reduce the speed of approach to the solution this is definitely going to reduce the speed
of approach. Because of the under relaxation but, it will improve the stability of the
solution. And there are various ways to get a good under relaxation parameter these ways
we are not covered in this particular lecture and there would be suggested for the readings,
if you are interested in knowing how to get this under relaxation factor.
And then finally, we also looked at Levenberg-Marquardt modification to the Newton Raphson's method.
Technically speaking the l m method actually really comes in the optimization and finding
out essentially a least minimization.If you do not understand the terms do not worry about
it. The motivation behind this is that the root roots of the function f of x and nothing
but, the minima of f f f squared of x. We saw that essentially two lectures earlier
what that means pictorially and when we use this Levenberg-Marquardt modification instead
of having j inverse f instead of that we will have j transpose j plus beta i where beta
is a very small factor inverse j transpose f. This is how to get the beta and all that
are fairly advanced techniques which you need to do for the reading on in order to figure
those things out.
And in today's lecture what we looked at is the Bairstow's method for root finding. We
actually, did not go into the meet of the Bairstow's method because that would essentially
involve a fair amount of basically, if it will involve fair amount of algebraic manipulations
which I think you can, we will now be very well equip to go and read up any of the text
books to understand that. So, that is why is essentially for the lack
of time we did not did not go into that but, the idea is that any nth order polynomial
can be written as a product of n minus 2 order polynomial and quadratic polynomial plus a
remainder R, when the remainder R equals 0 at that time q is a factor of p. For example,
in the example examples that we had looked at for example, in this particular case x
square minus 1 is going to be a factor of this particular expression. So, if we choose
the value of p equal to 0 and q equal to minus 1 and go through the procedure that we looked
at in today's class. We will get C 1 equal to 0 and C 0 equal to
0, we are guaranteed to get that that will tell us that x square minus 1 is a essentially
a factor of this and then because x square minus 1 is a factor of this, we will get x
equal to 1 and x equal to minus 1 as this two solution and the deflated polynomial p
n minus 2 is going to be nothing but, x minus 2.
So, that will lead us essentially to the solution to the three solutions x equal to 1 x equal
to minus 1 and x equal to 2 that was essentially about the Bairstow's method, what I urge to
do is, just go and read up about the Bairstow's method in the second text book that we have
over here Chapra and Canale numerical methods. So, this is where essentially we end our module
four which was on algebraic equations solving in module five, we will talk about interpolation
and curve fitting or what is known more technically known as regression, that is what we will
cover in our the next module in this course. Thank you.