Chapter 1: SOLUTION OF NON LINEAR EQUATIONS
1- INTRODUCTION.
This Chapter deals with the methods to find the roots of non-linear equations.
( )
If f(x) is continuous, we can make use of the Intermediate Value Theorem to
bracket a root; i.e., we can find numbers x1 and x2 such that f(x1) and f(x2) have
different signs. Then the intermediate value theorem tells us that there is at least one
value xr ∈ (a, b) such that f(xr) = 0. The number xr is called a root or zero of f(x).
Solving nonlinear equations is also called root-finding.
2-Estimating the roots (locate the root).
Before using any methods to find the roots , we need to find two initial guesses for
the root. For this purpose two methods are used, the graphical method or the trial
and error method.
a-Graphical Method
A simple method for obtaining an estimate of the root of the equation f(x)=0 is to
make a plot of the function and observe where it crosses the x axis. This point, which
represents the x value for which f(x)=0, provides a rough approximation of the root.
Example 1:
Use the graphical approach to determine the drag coefficient c needed for a
parachutist of mass m=68.1 kg to have a velocity of 40 m/s after free-falling for time
t=10 s. Note: The acceleration due to gravity is 9.8 m/s 2.
We to solve the following equation:
( )
( ) ( )
G: gravity; m: mass of the parachutists; v the velocity; t the time.
( ) ( )
( ) ( )
( ) ( )
1
Various values of c can be substituted into the right-hand side of this equation to
compute
c f(c.)
4 34.11489
8 17.65345
12 6.06695
16 -2.26875
20 -8.40062
These points are plotted in Fig.1. The resulting curve crosses the c axis between 12
and 16. Visual inspection of the plot provides a rough estimate of the root of 14.75.
The validity of the graphical estimate can be checked by substituting it into the
equation of f(c) to yield.
f(14.75) =0.059 which is close to zero
f(c.)
40
30
20
10 f(c.)
0
0 5 10 15 20 25
-10
-20
Figure 1
Graphical techniques are of limited practical value because they
are not precise. However, graphical methods can be utilized to
obtain rough estimates of roots. These estimates can be
employed as starting guesses for numerical methods discussed
in this chapter.
Aside from providing rough estimates of the root, graphical
interpretations are important tools for understanding the
Figure 2 properties of the functions and anticipating the pitfalls of the
numerical methods. For example, Fig. 2 shows a number of
ways in which roots can occur (or be absent) in an interval prescribed by a lower
bound xi and an upper bound xu. Figure 2b depicts the case where a single root is
2
bracketed by negative and positive values of f(x). However, Fig. 2d, where f(xi) and
f(xu) are also on opposite sides of the x axis, shows three roots occurring within the
interval. In general, if f(xi) and f(xu) have opposite signs, there are an odd number of
roots in the interval. As indicated by Fig. 2a and c, if f(xi) and f(xu) have the same
sign, there are either no roots or an even number of roots between the values.
Example 2
Locate roots of the following function:
( ) ( ) ( )
The function f(x) has several roots over the range x=0 to x=5.
Use computer graphics to gain insight into the behaviour of this function.
Solution.
Packages such as Excel and MATLAB software can be used to generate plots. The
following figure is a plot of f(x) from x=0 to x=5. This plot suggests the presence of
several roots, including a possible double root at about x=4.2 where f(x) appears to
be tangent to the x axis. A more detailed picture of the behaviour of f(x) is obtained
by changing the plotting range from x=3 to x=5, as shown in Fig.b. Finally, in Fig.c,
the vertical scale is narrowed further to f(x)=−0.15 to f(x)=0.15 and the horizontal
scale is narrowed to x =4.2 to x=4.3. This plot shows clearly that a double root does
not exist in this region and that in fact there are two distinct roots at about x=4.23
and x=4.26. Computer graphics will have great utility in your studies of numerical
methods. This capability will also find many other applications in your other classes
and professional activities as well.
3
b- Incremental Search of the roots
A plot of the function is usually very in locating the roots; another option is to
incorporate an incremental search. This consists of starting at one end of the region
of interest and then making function evaluations at small increments across the
region. When the function changes sign, it is assumed that a root falls within the
increment. The x values at the beginning and the end of the increment can then
serve as the initial guesses for one of root finding methods that will be described in
this chapter. A potential problem with an incremental search is the choice of the
increment length. If the length is too small, the search can be very time consuming.
On the other hand, if the length is too great, there is a possibility that closely spaced
roots might be missed. The problem is compounded by the possible existence of
multiple roots.
3 Bracketing Methods
We will be considering the methods that exploit the fact that a function typically
changes sign in the vicinity of a root. These techniques are called bracketing
methods because two initial guesses for the root are required. As the name implies,
these guesses must “bracket,” or be on either side of, the root. The particular
methods described herein employ different strategies to systematically reduce the
width of the bracket and, hence, home in on the correct answer.
3.1 The Bisection Method
The bisection method, which is alternatively called binary chopping, interval halving,
or Bolzano’s method, is a method in which the interval is always divided in half. If a
function changes sign over an interval, the function value at the midpoint is
evaluated. The location of the root is then determined as lying at the midpoint of the
subinterval within which the sign change occurs. The process is repeated to obtain
refined estimates. A simple algorithm for the bisection calculation is listed below, and
a graphical depiction of the method is provided in Fig3. The following example goes
through the actual computations involved in the method.
Bisection Algorithm:
Step 1: Choose x1 and x2 guesses for the root such that the function changes
sign over the interval. This can be checked by ensuring that f(x 1)*f(x3)<0.
Step 2: An estimate of the root x3 is determined by
Step 3: Make the following evaluations in which subinterval the root lies:
4
a) If f(x1)*f(x3)<0, the root lies in the upper subinterval. Therefore,
set x2=x3 and return to step 2.
b) If f(x1)*f(x3)>0, the root lies in the upper subinterval. Therefore,
set x1=x3 and return to step 2.
c) If f(x1)*f(x3)=0, the equals x3; terminate the computation.
Example 3.1.1
Use the bisection method to find the roots of the following function:
( )
x y
0 -3
1 -4
2 3
3 24
4 65
5 132
5
Error Max
n x1 x2 x3 f(x1) f(x2) f(x3) ξ
0 1.000 2.000 1.500 -4.000 3.000 -1.875 0.5
1 1.500 2.000 1.750 -1.875 3.000 0.172 0.143 0.25
2 1.500 1.750 1.625 -1.875 0.172 -0.943 0.077 0.125
3 1.625 1.750 1.688 -0.943 0.172 -0.409 0.037 0.0625
4 1.688 1.750 1.719 -0.409 0.172 -0.125 0.018 0.03125
5 1.719 1.750 1.734 -0.125 0.172 0.022 0.009 0.0156
6 1.719 1.734 1.727 -0.125 0.022 -0.052 0.005 0.0078
3.1.2 Termination Criteria and Error estimate.
An objective criterion for deciding when to terminate the method is needed. We
should terminate when the relative error drops below a certain prespecified value.
| |*100
The absolute value is used because we are usually concerned with the magnitude of
ε rather than with its sign. When ε becomes less than a prespecified stopping
criterion ξ, the computation is terminated.
3.1.3 Convergence Criteria
At the iteration 0 ; the maximum error is:
• At the iteration 1: (case where x3=x2 and x1 the same) :
6
At iteration n:
( )
So; the number of iteration needed to have an error ξ will be:
( ) ( )
-1
( )
3.2 The false Position Method
A short coming of the bisection method is that, in dividing the interval from x1 to x2
into equal halves, no account is taken of the magnitudes of f(x1) and f(x2). For
example, if f(x1) is much closer to zero than f(x2), it is likely that the root is closer to
x1 than to xu. An alternative method that exploits this graphical insight is to join f(x1)
and f(x2) by a straight line. The intersection of this line with the x axis represents an
improved estimate of the root. The fact that the replacement of the curve by a
straight line gives a “false position” of the root is the origin of the name, method of
false position, or in Latin, regula falsi. It is also called the linear interpolation
method. Using similar triangles, the intersection of the straight line with the x axis
can be estimated as
( ) ( )
( ) ( ) ( ) ( )
Collect Terms and rearrange:
( ( ( )) ( ) ( )
Which can be solved for:
( )( )
( ) ( )
7
This is the false-position formula. The value of x 3 computed with the above
equation then replaces whichever of the two initial guesses, x 1 or x2, yields a
function value with the same sign as f(x 3). In this way, the values of x 1 and x2
always bracket the true root. The process is repeated until the root is
estimated adequately. The algorithm is identical to the one for bisection with
the exception that the false position formula is used for step 2. In addition, the
same stopping criterion is used to terminate the computation.
Example 3.2.1:
Use the false position method to find the roots of the following function:
( )
As in example 3; we take x1=1 and x2=2
x1 x2 x3 f(x 1 ) f(x 2 ) f(x 3 ) ξ
1 2 1.571 -4.000 3 -1.364
1.571 2 1.705 -1.364 3 -0.248 7.86
1.705 2 1.728 -0.248 3 -0.039 1.30
1.728 2 1.731 -0.039 3 -0.006 0.20
1.731 2 1.732 -0.006 3 -0.001 0.03
1.732 2 1.732 -0.001 3 0.000 0.00
8
4- Open Methods
For the bracketing methods, the root is located within an interval prescribed by a
lower and an upper bound. Repeated application of these methods always results in
closer estimates of the true value of the root. Such methods are said to be
convergent because they move closer to the truth as the computation progresses. In
contrast, the open methods described in the followings are based on formulas that
require only a single starting value of x or two starting values that do not necessarily
bracket the root. As such, they sometimes diverge or move away from the true root
as the computation progresses (Fig. b). However, when the open methods converge
(Fig.c), they usually do so much more quickly than the bracketing methods. We will
begin our discussion of open techniques with a simple version that is useful for
illustrating their general form and also for demonstrating the concept of convergence.
4.1 NEWTON-RAPHSON METHOD
The most widely used of all root-locating formulas is the Newton-Raphson equation .
If the initial guess at the root is xi, a tangent can be extended from the point [xi, f(xi)].
The point where this tangent crosses the x axis usually represents an improved
estimate of the root. The Newton-Raphson method can be derived on the basis of
this geometrical interpretation (an alternative method based on the Taylor series is
described in ). As in the following figure, the first derivative at x is equivalent to the
slope:
9
( )
( )
This can be rearranged to obtain:
( )
( )
which is called the Newton-Raphson formula
Example 4.1.1
−x
Use the Newton-Raphson method to estimate the root of f(x)= e −x, employing
an initial guess of x0 =0.
( )
10
n x f(x) f'(x) x+1 ξ
0 0 1 -2 0.5 100
1 0.5 0.11 -1.607 0.5663 11.709
2 0.5663 0.00 -1.568 0.5671 0.147
3 0.5671 0.00 -1.567 0.5671 0.000
4.1.2 Error Analysis of Newton Raphson Method
The Taylor series expansion can be represented as:
( )
( ) ( ) ( )( ) ( )
Where ξ lies somewhere in the interval from xi to xi+1. An approximate version is
obtainable by truncating the series after the first derivative term:
( ) ( ) ( )( )
At the intersection with the x axis, f(xi+1) would be equal to zero:
( ) ( )( )
Which can be solved for:
( )
( )
So we derived the Newton formula using a Taylor series.
The Taylor series can also be used to estimate the error of the formula.
For the solution xi+1=xr; and f(xr)=0.
We obtain then:
( )
( ) ( )( ) ( )
As
( ) ( )( )
So;
( )
( )( ) ( )
11
The Error is equal to:
Ei;i+1= x3-xi+1
So:
( )
0 ( ) ( )
If we assume convergence, both xi and ϵ should be approximated by the root [Link]
the above equation can be rearranged to yield:
( )
( )
So the error is roughly proportional to the square of the previous error. So we have a
quadratic convergence.
4.2 Pitfalls of the Newton-Raphson Method
Although the Newton-Raphson method is often very efficient, there are situations
where it performs poorly as shown by the following example:
4.2.1 Example
Determine the positive root of f(x) = x10 −1 using the Newton Raphson method and
an initial guess of x=0.5.
Newton Raphson formula will be:
( )
n x x(i+1) n x x(i+1) n x x(i+1) n x x(i+1)
0 0.5 51.65 11 18.009 16.208 21 6.279 5.651 31 2.190 1.971
1 51.650 46.485 12 16.208 14.587 22 5.651 5.086 32 1.971 1.774
2 46.485 41.837 13 14.587 13.129 23 5.086 4.578 33 1.774 1.597
3 41.837 37.653 14 13.129 11.816 24 4.578 4.120 34 1.597 1.439
4 37.653 33.888 15 11.816 10.634 25 4.120 3.708 35 1.439 1.299
5 33.888 30.499 16 10.634 9.571 26 3.708 3.337 36 1.299 1.178
6 30.499 27.449 17 9.571 8.614 27 3.337 3.003 37 1.178 1.083
7 27.449 24.704 18 8.614 7.752 28 3.003 2.703 38 1.083 1.024
8 24.704 22.234 19 7.752 6.977 29 2.703 2.433 39 1.024 1.002
9 22.234 20.010 20 6.977 6.279 30 2.433 2.190
10 20.010 18.009
12
Thus, after the first poor prediction, the technique is converging on the true root of 1,
but at a very slow rate.
Aside from slow convergence due to the nature of the function, other difficulties can
arise, as illustrated in the following figure. For example, a depicts the case where an
inflection point occurs in the vicinity of a root. Notice that iterations beginning at x0
progressively diverge from the root. b illustrates the tendency of the NewtonRaphson
technique to oscillate around a local maximum or minimum. Such oscillations may
persist, or as in Fig. b, a near-zero slope is reached, whereupon the solution is sent
far from the area of interest. Figure c shows how an initial guess that is close to one
root can jump to a location several roots away. This tendency to move away from the
area of interest is because near-zero slopes are encountered. Obviously, a zero
slope is truly a disaster because it causes division by zero in the Newton-Raphson
formula. Graphically , it means that the solution shoots off horizontally and never hits
the x axis.
13
4.3 The Secant Method
A potential problem in implementing the Newton-Raphson method is the evaluation
of the derivative. Although this is not inconvenient for polynomials and many other
functions, there are certain functions whose derivatives may be extremely difficult or
inconvenient to evaluate. For these cases, the derivative can be approximated by a
backward finite divided difference.
( ) ( )
( )
This approximation can be substituted into Newton Raphson formula to yield the
following iterative equation:
( )( )
( ) ( )
This is the formula for the secant method. Notice that the approach requires two
initial estimates of x. However, because f(x) is not required to change signs between
the estimates, it is not classified as a bracketing method.
4.3.1 Example
Use the secant method to estimate the root of :
( )
with initial estimates of x-1=0, x0=1.0
n x -1 x0 f(x -1 ) f(x 0) x1 ξ
0 0 1 1 -0.632 0.613
1 1 0.613 -0.632 -0.071 0.564 8.67
2 0.613 0.564 -0.071 0.005 0.567 0.59
3 0.564 0.567 0.005 0.000 0.567 0.00
14
5- Errors and Computer Arithmetic:
Several sources of error interact to affect the accuracy of our result.
5.1 Round-off Error
All computing devices represent numbers with some imprecision. Digital computers,
which are the normal devices for implementing numerical methods, will nearly
always use floating-point number with a fixed word length. The true values are not
exactly expressed by such representations. We call this error round-off, whether the
decimal fraction is rounded or chopped after the final digit.
5.2 Error in original Data
Real world problems, in which an existing or proposed physical situation is modelled
by a mathematical equation, frequently have coefficients that are imperfectly known.
The model itself may not perfectly reflect the behaviour of the situation either. The
numerical analyst can do nothing to overcome such errors by his choice of method ,
but need to be aware of such uncertainties; in particular, he may need to perform
tests to see how sensitive his results are to change in the input information.
5.3 Blunders
These are typing errors, for example instead of .
You have to test the numerical code with a result that you know.
15