1
Research Seminar for Mathematics
TOPIC :NEWTON RAPHSON METHOD
SUBMITTED TO:
MISS HUSNA MUZAFFAR
SUBMITTED BY:
ATIQA SHAHEEN(BC190200184)
DEPARTMENT OF MATHEMATICS
VIRTUAL UNIVERSITY OF PAKISTAN
3
OUTLINE
Definition
Historical background
Geometrical representation
Complex function
Convergence of Newton method
Drawbacks of Newton Method
Conclusion
References
4
DEFINITION
In numerical analysis, Newton's method, also known as the Newton
Raphson method, named after Isaac Newton and Joseph Raphson,
is a root-finding algorithm which produces successively better approximations
to the roots(or zeroes) of a real-valued function.
New ton Raphson method is numerical methods for solving either algebraic or transcendental equation.
5
The most basic version starts with a single-variable function f defined
for a real variable x, the function's derivative f′, and an initial guess
x0 for a root off. If the function satisfies sufficient assumptions and
the initial guess is close, then
𝑥1 =𝑥0 −¿ ¿
6
The process is repeated as
𝑥𝑛+1 =𝑥 𝑛 −¿ ¿
Until a sufficiently precise value is reached. This algorithm is first
in the class of Householder's methods, succeeded by Halley's
method. The method can also be extended to complex functions
and to systems of equations.
7
Historical Background
The name "Newton's method" is derived from Isaac Newton's
description of a special case of the method in written in 1669,
published in 1711 by William Jones) and in De mitosis fluxional et serierum
Infinitarum (written in 1671, translated and published as Method of
Fluxions in 1736 by John Colson). However, his method differs substantially
from the modern method given above. Newton applied the method only to polynomials,
starting with an initial root estimate and extracting a sequence of error corrections.
8
He used each correction to rewrite the polynomial in terms of the remaining error, and
then solved for a new correction by neglecting higher-degree terms. He did not explicitly
connect the method with derivativesThree
or present a general formula. Newton applied this
Formula
method to both numerical and algebraic problems, producing Taylor series in the latter
case.
Newton may have derived his method from a similar but less precise method by Vista. The
essence of Viet’s method can be found in the work of the Persian mathematician Sharif al-
Din al-Tutsi
9
Geometrical Representation
Here is a picture to demonstrate what Newton's method actually does:
10
Complex Function
Newton's method can be directly applied to find their zeroes.
Each zero has a basin of attraction in the complex plane, the set
of all starting values that cause the method to converge to that
particular zero. These sets can be mapped as in the image shown.
For many complex functions, the boundaries of the basins of
attraction are fractals.
In some cases there are regions in the complex plane which are not
in any of these basins of attraction, meaning the iterates do not converge.
11
Convergence of Newton Method
According to Taylor's theorem, any function f(x) which has a
continuous second derivative can be represented by an expansion
about a point that is close to a root of f(x).
𝑓 (𝛼)= 𝑓 (𝑥 𝑛 )+ 𝑓 ′ (𝑥𝑛 )(𝛼 − 𝑥 𝑛 )+ 𝑅 1
Where the Lagrange form of the Taylor series expansion remainder is
1 ″ 2
𝑅1 = 𝑓 (𝜉 𝑛 ) ( 𝛼 − 𝑥 𝑛 ) ,
2!
12
By solving above we have the result:
¿ 𝜀𝑛+1 ∨¿ ¿ ¿ ¿
This equation shows that the order of convergence is at least quadratic. if the following
conditions are satisfied:
f′(x) ≠ 0; for all x ∈ I, where I is the interval [ −𝛼
|ε0|, + |ε0𝛼
|];
f″(x) is continuous, for all x ∈ I;
M |ε0| < 1
13
where M is given by
1
𝑀= ¿
2
If these conditions hold,
¿ 𝜀𝑛+1 ∨≤ 𝑀 ⋅ 𝜀2𝑛 .
14
Drawbacks of Newton Raphson Method
Divergence at inflection points
If the selection of a guess or an iterated value turns out to be close to the
inflection point of f ( x ), [where f”( x ) = 0 ], the roots start to diverge away
from the root.
𝑓 ( 𝑥𝑖 )
𝑥𝑖 +1 =𝑥 𝑖 −
𝑓 ′ ( 𝑥𝑖 )
Division of zero or near zero:
If an iteration, we come across the division by zero or a near-zero number,
then we get a large magnitude for the next value, xi+1.
15
Root jumping:
In some case where the function f (x) is oscillating and has a number
of roots, one may choose an initial guess close to a root.
However, the guesses may jump and converge to some other root.
Oscillations near local maximum and minimum:
Results obtained from N-R method may oscillate about the local max
or min without converging on a root but converging on the local max
or min. Eventually, it may lead to division to a number close to zero and
may diverge.
16
CONCLUSION
The Newton-Raphson method is a suitable and accurate
method to allocate roots of equations which can round up to
thousands of decimal places. The method usually works most
of the time, however, if the initial guessed value was not close
enough to the root, the method may not converge correctly
towards to the targeted root.
17
REFERENCES
General Texts in Numerical Analysis
Kendall E. Atkinson, An Introduction to Numerical Analysis, (1989) John Wiley & Sons,
Inc, ISBN 0-471-62489-6 Tjalling J. Ypma, Historical development of the Newton–
Raphson method, SIAM Review 37 (4), 531–551, 1995. doi:10.1137/1037125. Bonnans,
J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006).
Numerical optimization: Theoretical and practical aspects. Universitext (Second revised
ed. of translation of 1997 French ed.). Berlin: Springer-Verlag. pp. xiv+490.
doi:10.1007/978-3-540-35447-5. ISBN 3-540-35445-X. MR 2265882.
18
THANK YOU