|
NONLINEAR EQUATIONS |
MAJORGENERAL |
On non Internet
Explorer browsers, the equations may not show up.
As an alternative or if you
prefer,
you can see the pdf version of the ebook instead
Title |
An interactive e-book for illustrating Newton-Raphson method of solving nonlinear equations |
|
Creator |
Autar K Kaw |
|
Subject and Keywords |
|
|
Description |
An interactive E-book for illustrating Newton Raphson method of finding roots of nonlinear equation. It includes links to Mathcad simulations for the algorithm, convergence and the pitfalls; biography of the developers of the numerical methods, multiple choice quizzes, and a power point presentation. |
|
Publisher |
Holistic Numerical Methods Institute, |
|
Contributors |
Nathan Collier, Jai Paul, Michael Keteltas, Ginger Williams |
|
Format |
Text/HTML |
|
Last Revised |
May 31, 2007 |
|
Identifier |
http://numericalmethods.eng.usf.edu/ebooks/newtonraphson_03nle_ebook.htm |
|
Language |
English |
|
Rights |
|
Test your knowledge of the background Simulation
Derivation of Newton Raphson method from Taylor series |
||||||||||||||||||||||||||||||||||||||||||||||||||||
|
This is an example of how an instructor of a Numerical Methods course can develop an E-book on a single topic by using resources that are only available at the Holistic Numerical Methods Institute (HNMI) Website. Although one of the primary advantages of a web-based resource is that one can use documents outside of its own domain, we are particularly using this example as a way to illustrate the holistic nature of the resources available at HNMI. You are welcome to modify and edit this e-book to suit your purpose. Using the textbook document written in MS Word 2000 as a foundation, it was made interactive within MS Word 2000 by putting bookmarks and hyperlinks to background information, PowerPoint presentations, Mathcad simulations, historical anecdotes, multiple choice tests, problem sets, etc. Then the MS Word 2000 file was saved as a webpage and that is what you are about to read here. Back to TOCIntroductionBefore you get started, see the video or test your knowledge on the background of solving nonlinear equations or go to the table of contents for particular information. Methods such as bisection method and the false position method of finding a root of a nonlinear equation f(x)=0 require bracketing of the root by two guesses. Such methods are called bracketing methods. These methods are always convergent since they are based on reducing the interval between the two guesses. In the Newton-Raphson (Newton’s Biography; Raphson’s Biography) method, the root is not bracketed. Only the initial guess of the root is needed to get the iterative process started to find the root of an equation. Hence, the method falls in the category of open methods. The Newton-Raphson method is based on the principle that if the initial guess of the root of f(x) = 0 is at xi, then if one draws the tangent to the curve at f(xi), the point xi+1 where the tangent crosses the x-axis is an improved estimate of the root (Figure 1).
Using the definition of the slope of a function, at
which gives
Equation (1) is called the Newton-Raphson formula for solving
nonlinear equations of the form Back to TOC
The steps to apply Newton-Raphson method to find the root of an equation f(x) = 0 are 1.
Evaluate 2. Use an initial guess of the root, xi, to estimate the new value of the root xi+1 as
3.
Find the absolute relative approximate error,
4.
Compare the absolute relative approximate error,
Figure 1. Geometrical illustration of the Newton-Raphson method Look at the PowerPoint presentation of Newton-Raphson Method or see the classroom presentation video for the background and algorithm.
Back to TOCExample You are working for ‘DOWN THE TOILET COMPANY’ that makes floats for ABC commodes. The ball has a specific gravity of 0.6 and has a radius of 5.5 cm. You are asked to find the distance to which the ball will get submerged when floating in water (See Figure 2).
Figure 2. Floating ball problem
The equation that gives the depth ‘x’ to which the ball is submerged under water is given by
Use the Newton-Raphson method of finding roots of equations to find a) the depth ‘x’ to which the ball is submerged under water. Conduct three iterations to estimate the root of the above equation. b) find the absolute relative approximate error at the end of each iteration, and c) the number of significant digits at least correct at the end of each iteration. Solution
Let us
assume the initial guess of the root of Iteration #1The estimate of the root is
The
absolute relative approximate error,
= 19.89% The number of significant digits at least correct is 0, as you need a absolute relative approximate error of less than 5% for one significant digit to be correct in your result. Iteration #2The estimate of the root is
The
absolute relative approximate error,
The number of significant digits at least correct is 2. Iteration #3The estimate of the root is
The
absolute relative approximate error,
The number of significant digits at least correct is 4, as only 4 significant digits are carried through in all the calculations. Conduct a simulation (Mathcad Maple Mathematica Matlab) of how different initial guess effect the solution or see the classroom presentation video for the example. Back to TOCDrawbacks of Newton-Raphson Method1. 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), that is, near where f”(x)=0, the roots may start to diverge away or converge slowly from the root. For example, to find the root of
the root is converging slowly (Table 1). Table 1. Divergence/Slow convergence at inflection point
Figure
3: Divergence/Slow Convergence at inflection point for What is an inflection point?For a function f(x) where the concavity changes from up-to-down or
down-to-up are called inflection points of the graph. For
example in the function, Run the simulation of drawback [MAPLE] [MATHCAD] [MATHEMATICA] [MATLAB] Back to TOC
2. Division of zero or near zero: The formula of Newton-Raphson method is
Consequently
if an iteration value,
in which case
For Table 2. Division by
near zero in
|
…..(1)
.
So starting with an initial guess, xi, one can find the next
guess xi+1, by using equation (1). One can repeat
this process until one finds the root within a desirable tolerance.
symbolically
as
.
If 
%
.
,
the concavity changes at x=1 (See Figure 3). In fact, it also
changes sign at x=1 and thus brings up the Inflection Point Theorem for a
function f(x) that states : “If f’(c) exists and f’’(c) changes sign at x
= c , then the point (c, f(c)) is an inflection point of the graph of f.
is such that 
, then one can face
division by zero or a near-zero number. This will give a large
magnitude for the next value, xi+1. An example is
finding the root of the equation
or 
, division by zero
occurs (Figure 4). For an initial guess close to 0.02, of 
, the Newton-Raphson
method does not even converge after nine iterations (See Table 2).|
Iteration Number |
xi |
|
f(xi) |
|
0 1 2 3 4 5 6 7 8 9 |
0.019990 -2.6480 -1.7620 -1.1714 -0.77765 -0.51518 -0.34025 -0.22369 -0.14608 -0.094490 |
100.75 50.282 50.422 50.632 50.946 51.413 52.107 53.127 54.602 |
-1.6000 x 10-6 -18.778 -5.5638 -1.6485 -0.48842 -0.14470 -0.042862 -0.012692 -0.0037553 -0.0011091 |
Figure 4. Pitfall of division by zero or a near zero number.
Run the simulation of drawback [MAPLE] [MATHCAD] [MATHEMATICA] [MATLAB]
Back to TOC
3. 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. For example for solving the equation
Intuitively,
you would choose of an initial guess 
to
converge to the root of 
.
However, it converges to the root of x = 0 as shown in Table 3 and Figure 5.
Table 3. Root
jumping in Newton
|
Iteration Number |
|
f(xi) |
|
|
0 1 2 3 4 5 |
7.539822 4.461 0.5499 -0.06303 6.376x10-4 -1.95861x10-13 |
0.951 -0.969 0.5226 -0.06303 8.375x10-4 -1.95861x10-13 |
68.973 711.44 971.91 7.54x104 4.27x1010 |
Figure
5. Root jumping from intended location of root for 
Run the simulation of drawback [MAPLE] [MATHCAD] [MATHEMATICA] [MATLAB]
Back to TOC
4. Oscillations near local maximum and minimum: Results obtained from Newton-Raphson method may oscillate about the local maximum or minimum without converging on a root but converging on the local maximum or minimum. Eventually, it may lead to division to a number close to zero and may diverge.
For example for
the equation has no real roots and the root estimates oscillate about the local minima of x=0 (See Table 4; Figure 6).
Table 4.
Oscillations near local maxima and minima in Newton
|
Iteration Number |
|
f(xi) |
|
|
0 1 2 3 4 5 6 7 8 9 |
-1.0000 0.5 -1.75 -0.30357 3.1423 1.2529 -0.17166 5.7395 2.6955 0.9770 |
3.00 2.25 5.062 2.092 11.874 3.57 2.029 34.942 9.268 2.954 |
_____ 300.00 128.571 476.47 109.66 150.80 829.88 102.99 112.927 175.96 |
Figure
6: Oscillations around local minima for
Run the simulation of drawback [MAPLE] [MATHCAD] [MATHEMATICA] [MATLAB]
See the classroom presentation video for the all the advantages and drawbacks
Derivation of Newton Raphson method from Taylor
Newton-Raphson method can also be derived from
+ 
As an approximation, taking only the first two terms of the right hand side,
and we are seeking a point where f(x) = 0, that is, if we assume
which gives
This is the same Newton-Raphson method formula series as derived previously using the geometric method
See the classroom presentation video for the derivation.
See the classroom presentation video for an anecdote of why supercomputers do not need a divide unit.
Problem Set
|
1. |
You are working for ‘DOWN THE TOILET COMPANY’ that makes floats for ABC commodes. The ball has a specific gravity of 0.6 and has a radius of 5.5 cm. You are asked to find the distance to which the ball will get submerged when floating in water.
The equation that gives the depth ‘x’ to which the ball is submerged under water is given by
For the physical problem done in class, answer the following questions a) Solving the third order polynomial exactly would require some effort. However using numerical techniques such as Newton-Raphson method, we can solve this or any other nonlinear equation of the form f(x) = 0. Solve the above equation by Newton-Raphson method assuming you want at least 3 significant digits to be correct in your answer. b) How can you use the knowledge of the physics of the problem to develop initial guess for the Newton-Raphson method? |
|
2. |
The velocity of a body is given by v(t)=5 e-t + 6, where v is in meters/sec and t is in seconds. a) Use Newton Raphson's method to find when the velocity will be 7.0 meters/second. Use only two iterations and take t =2 seconds as the initial guess. b) What is the relative true error at the end of the second iteration for part (a)? Answer: a) 1.522, 1.605 (understand the equation is f(t)=5e-t-1=0) b)Exact value is 1.609, εt = 0.2486% |
|
3. |
Use Newton-Raphson method on the equation x2 =N to derive the algorithm for the square root of N. Answer: xi + 1 = 1/2(xi + N/xi), where x0 is an initial approximation of √N |
|
4. |
Find the next iterative value of the root of x2-4=0 by using Newton-Raphson method, if the initial guess is 3. Answer: 2.1667 |
|
5. |
The root of the equation f(x)= 0 is found by using Newton-Raphson method. The initial estimate of the root is assumed to be x0=3. Given f(3)= 5 and the angle the tangent makes to the function f(x) at x=3 is 57o, what is the next estimate of the root, x1? Answer: -0.24703 |
|
6. |
The root of x3=4 is found by using Newton-Raphson method. At what iteration number would you trust at least two significant digits in your estimate? Answer: Third, if you assume x=2 as the initial guess. |
|
7. |
The ideal gas law is given by
where p is the pressure, v is the specific volume, R is the universal gas constant, and T is the absolute temperature. This equation is only accurate for a limited range of pressure and temperature. Vander Waals came up with an equation that was accurate for a broader range of pressure and temperature, and is given by
where ‘a’ and ‘b’ are empirical constants dependent on a particular gas. Given the value of R =0.08, a=3.592, b=0.04267, p=10 and T=300 (assume all units are consistent), if one is going to find the specific volume, v, for the above values a) how would you rewrite the nonlinear equation for v so as to solve by Newton-Raphson method, (you only have to write the equation – do not solve it) b) from the information given above what would be a good initial guess for v? Back to TOC |
