Course: UMA 011 (Numerical Analysis)
Instructor: Dr. Amit Kumar,
Associate Professor,
School of Mathematics,
TIET, Patiala
Email: amitkumar@thapar.edu
Mob: 9888500451
Order of a root
If a root is repeated times then order of that root will be . A root of
order 1 is called a simple root and a root of order greater than 1 is called a
multiple root.
For example, roots of ( ) ( ) are 2, 2 and 3.
Since, 2 is repeating two times so order of 2 is two. It is a multiple root.
While, 3 is repeating one time so order of 3 is one. It is a simple root.
Method to check the order of a root
Let us consider that ( ) and its derivatives ( ) ( ) ( ),… are
defined and continuous on an interval about . We say that ( )
has a root of order if and only if ( ) ( ) ( ) …,
( ) ( )
( ) , ( ) .
Check that and are roots of the function ( )
or not, If yes then check their order.
Since, ( ) and ( )
so, and 2 are roots of ( )
Now,
( )
( )
( )
( )
Since,
( ) ( ) but ( ) . So, order of 1 is 3.
( ) . So, order of 2 is 1.
If the function ( ) has a root of order at then there exists a
continuous function ( ) so that ( ) can be expressed as ( )
( ) ( ), where ( )
Order of Convergence
Let * + be a convergent sequence and converges to .
Set and
i.e.,
and
If there exists two positive numbers and so that
| | | |
Then sequence is said to converge to with order of convergence . The
number is called the asymptotic error constant.
If the convergence of * + is called linear.
If the convergence of * + is called quadratic.
If is large, the sequence converges rapidly to .
Order of Convergence of Fix point method
Prove that if is a root of the equation ( ) and ( ) is continuously
differentiable for all near to such that ( ) . Then, the iteration
( ) linearly converges to root .
( )
( ) ( and )
( ) ( )
( ) ( )
(Since is a root of the equation ( ) so ( ) )
( ) ( )
( )
( ) ( )
( )
( ( ) )
Prove that if is a root of the equation ( ) and ( ) is
continuously differentiable for all near to such that ( ) ,
( )
Then, the iteration ( ) quadratically converges to root .
( )
( ) ( and )
( ) ( )
( ) ( )
(Since is a root of the equation ( ) so ( ) )
( ) ( )
( )
( ) ( )
( )
( ) ( )
(Since, ( ) ( ) )
( )
Prove that if is a root of the equation ( ) and ( ) is times
continuously differentiable for all near to , for some such that
( ) ( )
( ) ( ) ( ) , ( ) . Then, the iteration
( ) converges to root with order of convergence .
( )
( ) ( and )
( ) ( ) ( ) ( )( )
( ) ( )
( )
( ) ( )
(Since is a root of the equation ( ) so ( ) )
( )
( ) ( ) ( ) ( )
( )
( ) ( )( )
( )
( ) ( ) ( ) ( )
( )
( )
( ) ( )
( ) ( )( )
( ) ( ) ( )( )
(Since, )
( )
Prove that Newton Raphson method converges linearly with the rate of
convergence . / for multiple roots. While, it converges quadratically
for simple roots.
Let be the root of the function ( ) and the order of be .
Since, order of is . So, ( ) may be written as
( ) ( ) ( ) ( )
Substituting
( ) ( ) ( )
and
( ) ( ) ( ) ( ) ( )
in Newton Raphson formula
( )
( )
( ) ( )
( ) ( ) ( ) ( )
( ) ( )
( ) , ( ) ( ) ( )-
( ) ( )
, ( ) ( ) ( )-
Comparing with fix point formula
( ), we have
( ) ( )
( )
, ( ) ( ) ( )-
, ( ) ( ) ( )-,( ) ( ) ( )-
,( ) ( )-, ( ) ( ) ( ) ( )-
( )
, ( ) ( ) ( )-
( )
, ( ) ( ) ( )-,( ) ( ) ( )-
,( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )-
, ( ) ( ) ( )-
, ( )-, ( )-
, ( )-
If then
( ) .
Hence, order of convergence is linear.
However, If then
( ) and it can be verified that ( )
Hence, order of convergence is quadratic.
Modify Newton Raphson method in such a manner that it also converges
converges quadratically for simple as well as multiple roots.
Let be the root of the function ( ) and the order of be . Then,
modified Newton Raphson formula
( )
( )
( )
will converge for simple as well as multiple roots.
Prove that modify Newton Raphson method converges quadratically for
simple as well as multiple roots.
Since, order of is . So, ( ) may be written as
( ) ( ) ( ) ( )
Substituting
( ) ( ) ( )
and
( ) ( ) ( ) ( )( ) in modified Newton Raphson
formula
( )
( )
( )
( ) ( )
( )
( ) ( ) ( ) ( )
( ) ( )
( )
( ) , ( ) ( ) ( )-
( ) ( )
( )
, ( ) ( ) ( )-
Comparing with fix point formula
( ), we have
( ) ( )
( ) ( )
, ( ) ( ) ( )-
, ( ) ( ) ( )-,( ) ( ) ( )-
,( ) ( )-, ( ) ( ) ( ) ( )-
( )
, ( ) ( ) ( )-
( )
( )
, ( ) ( ) ( )-,( ) ( ) ( )-
,( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )-
, ( ) ( ) ( )-
( )
, ( )-, ( )-
( )
, ( )-
It can be verified that ( )
Hence, order of convergence is quadratic.
The above discussed modified Newton Raphson method can be used only if
is known. If is not known then modify Newton Raphson method in
such a manner that it also converges quadratically for simple as well as
multiple roots.
It is proved that if is a simple root of ( ) then Newton Raphson’s
method
( )
( )
converges qudratically for .
So, if the function ( ) is replaced with such a function ( ) for which
the multiple root of ( ) is a simple root of the function ( ) then
Newton Raphson method
( )
( )
will converge qudratically.
Assuming
( )
( )
( )
( ) ( )
( ) ( ) ( ) ( )
( ) ( )
( ) , ( ) ( ) ( )-
( ) ( )
, ( ) ( ) ( )-
and hence,
, ( ) ( ) ( )-,( ) ( ) ( )-
,( ) ( )-, ( ) ( ) ( ) ( )-
( )
, ( ) ( ) ( )-
We have,
( ) ( )
( )
, ( ) ( ) ( )-
and
, ( ) ( ) ( )-,( ) ( ) ( )-
,( ) ( )-, ( ) ( ) ( ) ( )-
( )
, ( ) ( ) ( )-
, ( )-, ( )-
, ( )-
So, is a simple root of
( )
( )
( )
.
Hence,
( )
( )
Where,
( )
( ) will converge qudratically.
( )
It is obvious that 1.5 is root of ( ) and order of 1.5 is 3. Find
the root near to 1.5 up to two decimal places using Newton Raphson
method, Modified Newton Raphson method (Based upon ) by considering
.
Newton Raphson method
( )
( )
( )
( )
( )
Modified Newton Raphson method based upon
( )
( )
( )
is repeating 3 times so
( )
( )
( )
( )
( )
( )
Modified Newton Raphson method not based upon
( )
( )
( )
( ) ( ) ( )
( )
( ) ( )
( )
( )
( )
( )
For more details and questions, please visit
https://sites.google.com/site/mathscomputation
