Numerical Methods

King Saud University

Aims

Chapter 2
Lecture #4

In this lecture, we will . . .

I Introduce the Secant Method

I Introduce the Multiplicity of a Root
I Introduce the Convergence of Iterative Methods
I Introduce the Systems of Nonlinear Equations
Secant Method
Since we known the main obstacle to using the Newton’s method is that it may be
difficult or impossible to differentiate the function f (x). The calculation of f 0 (xn )
may be avoided by approximating the slope of the tangent at x = xn by that of
the chord joining the two points (xn−1 , f (xn−1 )) and (xn , f (xn )), see Figure 1.

y
y=f(x)

x2 x
3
0
x1 x
α

Figure 1: Graphical Solution of Secant Method.

The slope of the chord (or secant) is

f (xn ) − f (xn−1 )
f 0 (xn ) ≈ . (1)
xn − xn−1
The iterative formula of the secant method is given by

(xn − xn−1 )f (xn ) xn−1 f (xn ) − xn f (xn−1 )

xn+1 = xn − = , n ≥ 1. (2)
f (xn ) − f (xn−1 ) f (xn ) − f (xn−1 )
Example 0.1
Use the secant method to find the approximate root of the following equation
within the accuracy 10−2 take x0 = 1.5 and x1 = 2.0 as starting values

x3 = 2x + 1.

Solution. Since f (x) = x3 − 2x − 1 and

x0 = 1.5, f (x0 ) = −0.625,

x1 = 2.0, f (x1 ) = 3.0,

therefore, we see that f (x0 ) 6= f (x1 ). Hence, one can use the iterative formula (2),
to get new approximation:

x0 f (x1 ) − x1 f (x0 ) (1.5)(3.0) − (2.0)(−0.625)

x2 = = = 1.586207,
f (x1 ) − f (x0 ) 3.0 − (−0.625)

and f (x2 ) = −0.18434. Similar way, we can find the other possible approximation
of the root. A summary of the calculations is given in Table 1. •

Table 1: Solution of x3 = 2x + 1 by secant method

n xn−1 xn xn+1 f (xn+1 )

01 1.500000 2.000000 1.586207 -0.1814342
02 2.000000 1.586207 1.609805 -0.0478446
03 1.586207 1.609805 1.618257 0.0013040
Example 0.1
Use the secant method to find the approximate root of the following equation
within the accuracy 10−2 take x0 = 1.5 and x1 = 2.0 as starting values

x3 = 2x + 1.

Solution. Since f (x) = x3 − 2x − 1 and

x0 = 1.5, f (x0 ) = −0.625,

x1 = 2.0, f (x1 ) = 3.0,

therefore, we see that f (x0 ) 6= f (x1 ). Hence, one can use the iterative formula (2),
to get new approximation:

x0 f (x1 ) − x1 f (x0 ) (1.5)(3.0) − (2.0)(−0.625)

x2 = = = 1.586207,
f (x1 ) − f (x0 ) 3.0 − (−0.625)

and f (x2 ) = −0.18434. Similar way, we can find the other possible approximation
of the root. A summary of the calculations is given in Table 1. •

Table 1: Solution of x3 = 2x + 1 by secant method

n xn−1 xn xn+1 f (xn+1 )

01 1.500000 2.000000 1.586207 -0.1814342
02 2.000000 1.586207 1.609805 -0.0478446
03 1.586207 1.609805 1.618257 0.0013040
Example 0.2
Show that the iterative procedure for evaluating the reciprocal of a number N by
using the secant method is:

xn+1 = xn + (1 − N xn )xn−1 , n ≥ 1. (3)

Solution. Let N be a positive number and x = 1/N . If f (x) = 0, then

x = α = 1/N is the exact zero of the function

f (x) = 1/x − N.

Since the secant formula is

(xn − xn−1 )f (xn )
xn+1 = xn − , n ≥ 1.
f (xn ) − f (xn−1 )

Hence, assuming the initial estimates to the root, say, x = x0 , x = x1 and by using
the secant iterative formula, we have

(x1 − x0 )(1/x1 − N ) (x1 − x0 )(1/x1 − N )

x2 = x1 − = x1 − .
(1/x1 − N ) − (1/x0 − N ) −(x1 − x0 )/x1 x0

It gives

x2 = x1 + (1/x1 − N )x1 x0 = x1 + x0 − N x1 x0 = x1 + (1 − N x1 )x0 .

Example 0.2
Show that the iterative procedure for evaluating the reciprocal of a number N by
using the secant method is:

xn+1 = xn + (1 − N xn )xn−1 , n ≥ 1. (3)

Solution. Let N be a positive number and x = 1/N . If f (x) = 0, then

x = α = 1/N is the exact zero of the function

f (x) = 1/x − N.

Since the secant formula is

(xn − xn−1 )f (xn )
xn+1 = xn − , n ≥ 1.
f (xn ) − f (xn−1 )

Hence, assuming the initial estimates to the root, say, x = x0 , x = x1 and by using
the secant iterative formula, we have

(x1 − x0 )(1/x1 − N ) (x1 − x0 )(1/x1 − N )

x2 = x1 − = x1 − .
(1/x1 − N ) − (1/x0 − N ) −(x1 − x0 )/x1 x0

It gives

x2 = x1 + (1/x1 − N )x1 x0 = x1 + x0 − N x1 x0 = x1 + (1 − N x1 )x0 .

In general, this becomes

xn+1 = xn + (1 − N xn )xn−1 , n = 1, 2, . . . .

For example, suppose we want the reciprocal of number N = 5. Assuming the

initial approximations of say x0 = 0 and x1 = 0.1, then by using the above
iterative formula, we get the first three approximations as follows:

x2 = 0.1, x3 = 0.15, x4 = 0.175,

The estimated value compares rather favorably with exact value of 1/5, (see
Figure 2). •

5 0.5

4
y = 1/x − 5
0.4 y = x
3 0.3
α
2 0.2
y

y
1 0.1
α
0 0

−1 −0.1

−2 −0.2
y = x + (1 − 5x)x

−3 −0.3
0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5
x x

Figure 2: Graphical Solution of 1/x = 5 and x = x + (1 − 5x)x.

Procedure
(Secant Method)

1. Choose the two initial approximation x0 and x1 .

2. Check, if f (x0 ) = f (x1 ), go to step 1 otherwise, continue.
3. Establish Tolerance ( > 0) value for the function.
4. Compute new approximation for the root by using the iterative formula (2).
5. Check tolerance. If |xn − xn−1 | ≤ , for n ≥ 1, then end; otherwise, go back
to step 4, and repeat the process.
Multiplicity of a Root

So far we discussed about the function which has simple root. Now we will discuss
about the function which has multiple roots. A root is called a simple root if it is
distinct, otherwise roots that are of the same order of magnitude are called
multiple.
Definition 1
(Order of a Root)
The equation f (x) = 0 has a root α of order m, if there exists a continuous
function h(x), and f (x) can be expressed as the product

f (x) = (x − α)m h(x), where h(α) 6= 0. (4)

So h(x) can be used to obtain the remaining roots of f (x) = 0. It is called

polynomial deflation. •
 m=1

m=2

m=3

Figure 3: Multiple roots of f (x) = 0.

The behavior of the graph of f (x) near a root of multiplicity m (m = 1, 2, 3) is

shown in Figure 3.
It can be seen that when α is a root of odd multiplicity, the graph of f (x) will
cross the x-axis at (α, 0); and when α has even multiplicity the graph will be
tangent to but will not cross the x-axis at (α, 0). Moreover, the higher the value of
m the flatter the graph will be near the point (α, 0).
Lemma

Assume that function f (x) and its derivatives f 0 (x), f 00 (x), · · · , f (m) (x) are
defined and continuous on an interval about x = α. Then f (x) = 0 has a root α of
order m if and only if

f (α) = f 0 (α) = f 00 (α) = · · · = f (m−1) (α) = 0, f (m) (α) 6= 0. (5)

For example, consider the equation f (x) = x3 − x2 − 21x + 45 = 0, which has

three roots; a simple root at α = −5 and a double root at α = 3. This can be
verified by considering the derivatives of the function as follows

f 0 (x) = 3x2 − 2x − 21, f 00 (x) = 6x − 2.

At the value α = −5, we have f (5) = 0 and f 0 (5) = 64 6= 0, so by (5), we see that
m = 1. Hence α = −5 is a simple root of the equation. For the value α = 3, we
have
f (3) = 0, f 0 (3) = 0, f 00 (3) = 16 =
6 0,
so that m = 2 by (5), hence α = 3 is a double root of the equation. Note that this
function f (x) has the factorization and can be written in the form of (4) as (see
Figure 4),
f (x) = (x − 3)2 (x + 5).

80

60

40

20
α
0

y
−20
α
−40

−60
y = x3 − x2 − 21x + 45
−80

−100
−6 −4 −2 0 2 4
x

Figure 4: Graphical Solution of x3 − x2 − 21x + 45 = 0.

Note that for a simple root α of the nonlinear equation f (x) = 0, means that

f (α) = 0 but f 0 (α) 6= 0.

But for multiple root α of the nonlinear equation, we must have

f (α) = 0 and f 0 (α) = 0.

The order of multiplicity of the multiple root can be easily find out by taking the
higher derivatives of the function at α unless the higher derivative becomes nonzero
at α. Then the order of nonzero higher derivative will be the order of multiplicity of
the multiple root. •
Example 0.3
Find the multiplicity of the root α = 1 of the equation x ln x = ln x.
Solution. From the given equation, we have

f (x) = x ln x − ln x and f (1) = 0,

1
f 0 (x) = ln x + 1 − and f 0 (1) = 0,
x
1 1
f 00 (x) = + 2 and f 00 (1) = 2 6= 0.
x x
Thus the multiplicity of the root α = 1 of the given equation is 2. •
The order of multiplicity of the multiple root can be easily find out by taking the
higher derivatives of the function at α unless the higher derivative becomes
nonzero at α. Then the order of nonzero higher derivative will be the order of
multiplicity of the multiple root. •
Example 0.3
Find the multiplicity of the root α = 1 of the equation x ln x = ln x.
Solution. From the given equation, we have

f (x) = x ln x − ln x and f (1) = 0,

1
f 0 (x) = ln x + 1 − and f 0 (1) = 0,
x
1 1
f 00 (x) = + 2 and f 00 (1) = 2 6= 0.
x x
Thus the multiplicity of the root α = 1 of the given equation is 2. •
Convergence of Iterative Methods

Usually we don’t know in advance that an equation has multiple roots,

although we might suspect it from sketching the graph. Many problems
which leads to multiple roots, are in fact ill-posed. The methods we
discussed so far cannot be guaranteed to converge efficiently for all
problems. In particular, when a given function has a multiple root
which we require, the methods we have described will either not
converge at all or converge more slowly. For example, the
Newton’s method converges very fast to simple root but converges
more slowly when used for functions involving multiple roots.
Example 0.4
Consider the following two nonlinear equations

(1) xex = 0 (2) x2 ex = 0.

(a) Find the Newton’s method for the solutions of the given equations.
(b) Explain why one of the sequences converges much faster than the other to the
root α = 0.
Solution. (a) For the first equation, we have

f (x) = xex and f 0 (x) = (1 + x)ex .

Then the Newton’s method for the solution of the first equation is

f (xn ) x2n
xn+1 = g1 (xn ) = xn − = , n ≥ 0,
f 0 (xn ) (1 + xn )

which is the first sequence. Similarly, we can find the Newton’s method for the
solution of the second equation as follows:

x2n exn xn + x2n

xn+1 = g2 (xn ) = xn − 2 x
= , n ≥ 0,
(2xn + xn )e n (2 + xn )

and it is the second sequence.

Example 0.4
Consider the following two nonlinear equations

(1) xex = 0 (2) x2 ex = 0.

(a) Find the Newton’s method for the solutions of the given equations.
(b) Explain why one of the sequences converges much faster than the other to the
root α = 0.
Solution. (a) For the first equation, we have

f (x) = xex and f 0 (x) = (1 + x)ex .

Then the Newton’s method for the solution of the first equation is

f (xn ) x2n
xn+1 = g1 (xn ) = xn − = , n ≥ 0,
f 0 (xn ) (1 + xn )

which is the first sequence. Similarly, we can find the Newton’s method for the
solution of the second equation as follows:

x2n exn xn + x2n

xn+1 = g2 (xn ) = xn − 2 x
= , n ≥ 0,
(2xn + xn )e n (2 + xn )

and it is the second sequence.

(b) From the first sequence, we have

x2 x2 + 2x
g1 (x) = and g10 (x) = .
(1 + x) (1 + x)2

Then
0
|g10 (α)| = |g10 (0)| = = 0,
1
which shows that the first sequence converges to zero. Similarly, from the second
sequence, we have

x + x2 x2 + 4x + 2
g2 (x) = and g20 (x) = .
(2 + x) (2 + x)2

Thus
2 1
|g20 (0)| = = < 1,
4 2
which shows that the second sequence is also converges to zero. Since the value of
|g10 (0)| is smaller than |g20 (0)|, therefore, the first sequence converges faster than
the second one. •
Note that in the above Example 0.4, the root α = 0 is the simple root for the first
equation (see Figure 5) because

f (0) = 0 but f 0 (0) = 1 6= 0,

and for the second equation it is a multiple root because

f (0) = 0 and f 0 (0) = 0.

16 30

14
25
12

10 20

8
y

x 15
y = xe

y
6
2 x
y = xe
4 10

2
α 5
0
α
−2 0
−2 −1.5 −1 −0.5 0 0.5 1 1.5 2 −2 −1.5 −1 −0.5 0 0.5 1 1.5 2
x x

Figure 5: Graphical Solution of xex = 0 and x2 ex = 0.

Therefore, the Newton’s method converges very fast for the first equation and
converges very slow for the second equation. However, in some cases simple
modifications can be made to the methods to maintain the rate of convergence.
Two such modified methods are considered here, called the Newton modified
methods.
First Modified Newton’s Method

To determine a root of known multiplicity m for the equation f (x) = 0, we may

use the first Newton’s modified method (also called the Schroeder’s method) which
is given by the form

f (xn )
xn+1 = xn − m , n = 0, 1, 2, . . . (6)
f 0 (xn )
Example 0.5
1
Show that nonlinear equation = x has a root at x = 1. Use the first
e(1−x)
modified Newton’s method to find its first three approximations using x0 = 0.
Solution. Since f (x) = 1 − xe(1−x) . First we show that α = 1 is the zero of the
given function as
f (α) = f (1) = 1 − 1e0 = 1 − 1 = 0.
To check whether it is simple or multiple zero of f (x), we do the following

f 0 (x) = −e1−x + xe(1−x) and f 0 (α) = f 0 (1) = −1 + 1 = 0,

which means that α = 1 is the multiple zero of the given function. To find its
order of multiplicity, we do

f 00 (x) = 2e(1−x) − xe(1−x) and f 00 (α) = f 00 (1) = 2 − 1 = 1 6= 0,

hence α = 1 is a zero of multiplicity 2 of the given function. Now we have to find

the first three approximations to the multiple zero α = 1 of the given function by
using the first modified Newton’s method which can be written as

f (xn ) 1 − xn e(1−xn )
xn+1 = xn − m = xn − m , n ≥ 0,
f 0 (xn ) (xn − 1)e(1−xn )

where m is the order of multiplicity of the zero of the function.

Example 0.5
1
Show that nonlinear equation = x has a root at x = 1. Use the first
e(1−x)
modified Newton’s method to find its first three approximations using x0 = 0.
Solution. Since f (x) = 1 − xe(1−x) . First we show that α = 1 is the zero of the
given function as
f (α) = f (1) = 1 − 1e0 = 1 − 1 = 0.
To check whether it is simple or multiple zero of f (x), we do the following

f 0 (x) = −e1−x + xe(1−x) and f 0 (α) = f 0 (1) = −1 + 1 = 0,

which means that α = 1 is the multiple zero of the given function. To find its
order of multiplicity, we do

f 00 (x) = 2e(1−x) − xe(1−x) and f 00 (α) = f 00 (1) = 2 − 1 = 1 6= 0,

hence α = 1 is a zero of multiplicity 2 of the given function. Now we have to find

the first three approximations to the multiple zero α = 1 of the given function by
using the first modified Newton’s method which can be written as

f (xn ) 1 − xn e(1−xn )
xn+1 = xn − m = xn − m , n ≥ 0,
f 0 (xn ) (xn − 1)e(1−xn )

where m is the order of multiplicity of the zero of the function.

For n = 0, 1, 2 and m = 2, with initial approximation x0 = 0, we have

x1 = 0.7358, x2 = 0.9782, x3 = 0.9998,

are the required first three approximations to α = 1, (see Figure 6). •

45

40

35

30

y = 1 − xe(1−x)
25
y

20

15

10

5
α
0
−2 −1.5 −1 −0.5 0 0.5 1 1.5 2
x

Figure 6: Graphical Solution of 1 − xe(1−x) = 0.

Second Modified Newton’s Method
An alternative approach to this problem that does not require any knowledge of
the multiplicity of the root is to replace the function f (x) in the equation by q(x),
where
f (x)
q(x) = 0 .
f (x)
This iterative formula of the second modified Newton’s method is given by

f (xn )f 0 (xn )
xn+1 = xn − , n = 0, 1, 2, . . . (7)
[f 0 (xn )]2 − [f (xn )][f 00 (xn )]

Example 0.6
Use the second modified Newton’s method to find the first approximation x1 to
the multiple root of the nonlinear equation 1 − cos(x) = 0, using x0 = 0.1.
Solution. Since f (x) = 1 − cos x, we have f 0 (x) = sin x and f 00 (x) = cos x. Now
using the second modified Newton’s formula (7)

f (xn )f 0 (xn )
xn+1 = xn − , n ≥ 0,
[f 0 (x 2 00
n )] − [f (xn )][f (xn )]

we have
(1 − cos xn )(sin xn )
xn+1 = xn − , n ≥ 0.
[sin xn ]2 − (1 − cos xn )(cos xn )
Second Modified Newton’s Method
An alternative approach to this problem that does not require any knowledge of
the multiplicity of the root is to replace the function f (x) in the equation by q(x),
where
f (x)
q(x) = 0 .
f (x)
This iterative formula of the second modified Newton’s method is given by

f (xn )f 0 (xn )
xn+1 = xn − , n = 0, 1, 2, . . . (7)
[f 0 (x 2 00
n )] − [f (xn )][f (xn )]

Example 0.6
Use the second modified Newton’s method to find the first approximation x1 to
the multiple root of the nonlinear equation 1 − cos(x) = 0, using x0 = 0.1.
Solution. Since f (x) = 1 − cos x, we have f 0 (x) = sin x and f 00 (x) = cos x. Now
using the second modified Newton’s formula (7)

f (xn )f 0 (xn )
xn+1 = xn − , n ≥ 0,
[f 0 (x 2 00
n )] − [f (xn )][f (xn )]

we have
(1 − cos xn )(sin xn )
xn+1 = xn − , n ≥ 0.
[sin xn ]2 − (1 − cos xn )(cos xn )
For n = 0 and the initial approximation x0 = 0.1, we have

(1 − cos x0 )(sin x0 ) (1 − cos 0.1)(sin 0.1)

x1 = x0 − = 0.1− = 0.098,
[sin x0 ]2 − (1 − cos x0 )(cos x0 ) [sin 0.1]2 − (1 − cos 0.1)(cos 0.1)

which is the required first approximation to α = 0, (see Figure 7). •

1.5

1
y = 1 − cosx
y

0.5

α
0
−2 −1.5 −1 −0.5 0 0.5 1 1.5 2
x

Figure 7: Graphical Solution of 1 − cosx = 0.

Example 0.7
x2
Show that the function f (x) = ex − − x − 1 has zero of multiplicity 3 at α = 0
2
and then, find the approximate solution of the zero of the function with the help
of the Newton’s method, first and second modified Newton’s methods, by taking
initial approximation x0 = 1.5 within an accuracy of 10−4 .
Solution. Since α = 0 is a root of f (x), (see Figure 8), so

x2
f (x) = ex − − x − 1, f (0) = 0,
2
f 0 (x) = x
e − x − 1, f 0 (0) = 0,
f 00 (x) = ex − 1, f 00 (0) = 0,
f 000 (x) = ex , f 000 (0) = 1 6= 0,

the function has zero of multiplicity 3. In Table 2 we showed the comparison of

three methods. •
We note that for the multiple root the both modified Newton’s methods converge
very fast as they took 4 iterations to converge while the Newton’s method
converges very slow and took 25 iterations to converge for the same accuracy.
Example 0.7
x2
Show that the function f (x) = ex − − x − 1 has zero of multiplicity 3 at α = 0
2
and then, find the approximate solution of the zero of the function with the help
of the Newton’s method, first and second modified Newton’s methods, by taking
initial approximation x0 = 1.5 within an accuracy of 10−4 .
Solution. Since α = 0 is a root of f (x), (see Figure 8), so

x2
f (x) = ex − − x − 1, f (0) = 0,
2
f 0 (x) = x
e − x − 1, f 0 (0) = 0,
f 00 (x) = ex − 1, f 00 (0) = 0,
f 000 (x) = ex , f 000 (0) = 1 6= 0,

the function has zero of multiplicity 3.

•
Example 0.7
x2
Show that the function f (x) = ex − − x − 1 has zero of multiplicity 3 at α = 0
2
and then, find the approximate solution of the zero of the function with the help
of the Newton’s method, first and second modified Newton’s methods, by taking
initial approximation x0 = 1.5 within an accuracy of 10−4 .
Solution. Since α = 0 is a root of f (x), (see Figure 8), so

x2
f (x) = ex − − x − 1, f (0) = 0,
2
f 0 (x) = x
e − x − 1, f 0 (0) = 0,
f 00 (x) = ex − 1, f 00 (0) = 0,
f 000 (x) = ex , f 000 (0) = 1 6= 0,

the function has zero of multiplicity 3. In Table 2 we showed the comparison of

three methods. •
We note that for the multiple root the both modified Newton’s methods converge
very fast as they took 4 iterations to converge while the Newton’s method
converges very slow and took 25 iterations to converge for the same accuracy.
 Table 2: Comparison results of three methods for the Example 0.7

Newton’s Method 1st. M.N. Method 2nd. M.N. Method

n xn xn xn
00 1.500000 1.500000 1.500000
01 1.067698 0.2030926 -0.297704
02 0.745468 3.482923e-03 -6.757677e-03
03 0.513126 1.010951e-06 -3.798399e-06
.. ........
25 7.331582e-05

2.5

1.5
y = ex − x2/2 − x − 1
1
y

0.5
α
0

−0.5

−1
−2 −1.5 −1 −0.5
x0 0.5 1 1.5 2

Figure 8: Graphical Solution of ex − x2/2 − x − 1 = 0.

Now we define the order of the convergence of functional iteration schemes
discussed in the previous sections. This is a measure of how rapidly a sequence
converges.
Definition 2
(Order of Convergence)
Suppose that the sequence {xn }∞ n=0 converges to α, and let en = α − xn define
the error of the nth iterate. If two positive constants β 6= 0 and R > 0 exist, and

|α − xn+1 | |en+1 |
lim = lim = β, (8)
n→∞ |α − xn |R n→∞ |en |R

then the sequence is said to converge to α with order of convergence R. The number β
is called the asymptotic error constant. The cases R = 1, 2 are given special
consideration.
If R = 1, the convergence of the sequence {xn}∞n=0 is called linear.
If R = 2, the convergence of the sequence {xn}∞n=0 is called quadratic.
If R is large, the sequence {xn } converges rapidly to α; that is, (8) implies that for
large values of n we have the approximation |en+1 | ≈ β|en |R . For example,
suppose that R = 2 and |en | ≈ 10−3 ; then we could expect that
|en+1 | ≈ β × 10−6 . •
Example 0.8
Show that the following sequence
 
1 N
xn+1 = xn 1 + 2 , n ≥ 0,
2 xn
√
will converge quadratically to N .
Solution. Since the sequence is given as
 
1 N
xn+1 = xn 1 + 2 ,
2 xn
√
and α = N , then we have
√ √ √
   
1 N 1 N
xn+1 − N = xn 1 + 2 − N = xn + −2 N
2 xn 2 xn
√ !2
1 √ N 1 √
= xn − √ = (xn − N )2 .
2 xn 2xn

Thus
1 2
en+1 = e or en+1 ∝ e2n ,
2xn n
which shows the quadratic convergence. •
Example 0.8
Show that the following sequence
 
1 N
xn+1 = xn 1 + 2 , n ≥ 0,
2 xn
√
will converge quadratically to N .
Solution. Since the sequence is given as
 
1 N
xn+1 = xn 1 + 2 ,
2 xn
√
and α = N , then we have
√ √ √
   
1 N 1 N
xn+1 − N = xn 1 + 2 − N = xn + −2 N
2 xn 2 xn
√ !2
1 √ N 1 √
= xn − √ = (xn − N )2 .
2 xn 2xn

Thus
1 2
en+1 = e or en+1 ∝ e2n ,
2xn n
which shows the quadratic convergence. •
Systems of Nonlinear Equations

A system of nonlinear algebraic equations may arise when one is dealing with
problems involving optimization and numerical integration (Gauss quadratures).
Generally, the system of equations may not be of the polynomial variety.
Therefore a system of n equations in n unknowns is called nonlinear if one or more
of the equations in the systems is/are nonlinear.
We now consider methods for solving systems of nonlinear algebraic equations in
which each equation is a function of a specified number of variables.
Consider the system of two nonlinear equations with two variables

f1 (x, y) = 0, (9)
and
f2 (x, y) = 0. (10)
The problem can be stated as follows:
Given the continuous functions f1 (x, y) and f2 (x, y), find the values x = α and
y = β such that
f1 (α, β) = 0 and f2 (α, β) = 0. (11)
The function f1 (x, y) and f2 (x, y) may be algebraic equations, transcendental or
any nonlinear relationship between the input x and y and the output f1 (x, y) and
f2 (x, y). The solutions to (9) and (10) are the intersections of the
f1 (x, y) = f2 (x, y) = 0, see Figure 9.

f (x,y) f1(x,y)
2

Figure 9: Nonlinear equation in two variables.

To solve the system of nonlinear equations we have many methods but we will use
the Newton’s method.
Consider the two nonlinear equations specified by the equations (9) and (10).
Suppose that (xn , yn ) is an approximation to a root (α, β), then by using the
Taylor’s theorem for functions of two variables for f1 (x, y) and f2 (x, y) expanding
about (xn , yn ), we have

f1 (x, y) = f1 (xn + (x − xn ), yn + (y − yn ))
∂f1 (xn , yn ) ∂f1 (xn , yn )
= f1 (xn , yn ) + (x − xn ) + (y − yn ) + ···
∂x ∂y

and
f2 (x, y) = f2 (xn + (x − xn ), yn + (y − yn ))
∂f2 (xn , yn ) ∂f2 (xn , yn )
= f2 (xn , yn ) + (x − xn ) + (y − yn ) + ···
∂x ∂y

Since f1 (α, β) = 0 and f2 (α, β) = 0, these equations, with x = α and y = β, give

∂f1 (xn , yn ) ∂f1 (xn , yn )

0 = f1 (xn , yn ) + (α − xn ) + (β − yn ) + ···
∂x ∂y
∂f2 (xn , yn ) ∂f2 (xn , yn )
0 = f2 (xn , yn ) + (α − xn ) + (β − yn ) + ···
∂x ∂y
The Newton’s method has a condition that initial approximation (xn , yn ) should
sufficiently close to exact root (α, β), therefore, the higher order terms may be
neglected to obtain

∂f1 (xn , yn ) ∂f1 (xn , yn )

0 ≈ f1 (xn , yn ) + (α − xn ) + (β − yn )
∂x ∂y (12)
∂f2 (xn , yn ) ∂f2 (xn , yn )
0 ≈ f2 (xn , yn ) + (α − xn ) + (β − yn )
∂x ∂y

We see that this represents a system of two linear algebraic equations for α and β.
Of course, since the higher order terms are omitted in the derivation of these
equations, their solution (α, β) is no longer an exact root of (11) and (12).
However, it will usually be a better approximation than (xn , yn ), so replacing
(α, β) by (xn+1 , yn+1 ) in (11) and (12), gives the iterative scheme

∂f1 (xn , yn ) ∂f1 (xn , yn )

0 = f1 (xn , yn ) + (xn+1 − xn ) + (yn+1 − yn )
∂x ∂y
∂f2 (xn , yn ) ∂f2 (xn , yn )
0 = f2 (xn , yn ) + (xn+1 − xn ) + (yn+1 − yn )
∂x ∂y
Then writing in the matrix form, we have
 ∂f ∂f1  
1   
 ∂x ∂y  xn+1 − xn f1
=− , (13)
   
 
 ∂f2 ∂f2  yn+1 − yn f2
∂x ∂y

where f1 , f2 and their partial derivatives f1 x , f1 y are evaluated at (xn , yn ). Hence

   
 ∂f
1 ∂f1 −1  
xn+1 xn  ∂x ∂y  f1
 = −
  
 . (14)
yn+1 yn  ∂f2 ∂f2  f2
∂x ∂y
We call the following matrix J a Jacobian matrix
 ∂f ∂f1 
1
 ∂x ∂y 
J = . (15)
 
 ∂f2 ∂f2 
∂x ∂y
Note that (13) can be written in the simplified form as follows
 ∂f ∂f1  
1   
 ∂x ∂y  h f1



  = − ,
 ∂f2 ∂f2  k f2
∂x ∂y
where h and k can be evaluated as
 ∂f2 ∂f1   ∂f2 ∂f1 
− f1 + f2 f1− f2
∂y ∂y ∂x ∂x
h=  and k=  , (16)
∂f1 ∂f2 ∂f1 ∂f2  ∂f1 ∂f2 ∂f1 ∂f2 
− −
∂x ∂y ∂y ∂x ∂x ∂y ∂y ∂x
where all functions are to be evaluated at (x, y). The Newton’s method for a pair
of equations in two unknowns is therefore
     
xn+1 xn h
= + , n = 0, 1, 2, . . . (17)
yn+1 yn k

where (h, k) are given by (16) evaluated at (xn , yn ).

Example 0.9
For the following system of two equations

x3 + 3y 2 = 21
x2 + 2y = −2

Find the Jacobian matrix and its inverse using initial approximation (1, −1), then
find the first approximation by using the Newton’s method.
Solution. Given
f1 (x, y) = x3 + 3y 2 − 21, f1 x = 3x2 , f1 y = 6y,
f2 (x, y) = x2 + 2y + 2, f2 x = 2x, f2 y = 2.

At the given initial approximation x0 = 1 and y0 = −1, we have

∂f1 ∂f1
f1 (1, −1) = −17, = f1 x = 3, = f1 y = −6,
∂x ∂y

∂f1 ∂f2
f2 (1, −1) = 1, = f2 x = 2, = f2 y = 2.
∂x ∂y

The Jacobian matrix J at the given initial approximation can be calculated as

 ∂f ∂f1  
1 
 ∂x ∂y  3 −6  
1 2 6
J = = and J −1 = ,
   
 ∂f2 ∂f2  18 −2 3
2 2
∂x ∂y
Example 0.9
For the following system of two equations

x3 + 3y 2 = 21
x2 + 2y = −2

Find the Jacobian matrix and its inverse using initial approximation (1, −1), then
find the first approximation by using the Newton’s method.
Solution. Given
f1 (x, y) = x3 + 3y 2 − 21, f1 x = 3x2 , f1 y = 6y,
f2 (x, y) = x2 + 2y + 2, f2 x = 2x, f2 y = 2.

At the given initial approximation x0 = 1 and y0 = −1, we have

∂f1 ∂f1
f1 (1, −1) = −17, = f1 x = 3, = f1 y = −6,
∂x ∂y

∂f1 ∂f2
f2 (1, −1) = 1, = f2 x = 2, = f2 y = 2.
∂x ∂y

The Jacobian matrix J at the given initial approximation can be calculated as

 ∂f ∂f1  
1 
 ∂x ∂y  3 −6  
1 2 6
J = = and J −1 = ,
   
 ∂f2 ∂f2  18 −2 3
2 2
∂x ∂y
is the inverse of the Jacobian matrix. Now to find the first approximation we have
to solve the following equation
        
x1 1 1 2 6 −17 2.5556
= − = ,
y1 −1 18 −2 3 1 −3.0556

the required first approximation. •

Example 0.10
Solve the following system of two equations using the Newton’s method with given
accuracy  = 10−5 .
4x3 + y = 6
x2 y = 1
Assume x0 = 1.0 and y0 = 0.5 as starting values.
Solution. Obviously this system of nonlinear equations has an exact solution of
x = 1.088282 and y = 0.844340, (see Figure 10). Let us look how the Newton’s
method is used to approximate these roots. The first partial derivatives are as
follows:
f1 (x, y) = 4x3 + y − 6, f1 x = 12x2 , f1 y = 1,
f2 (x, y) = x2 y − 1, f2 x = 2xy, f2 y = x2 .
At the given initial approximation x0 = 1.0 and y0 = 0.5, we get

∂f1 ∂f1
f1 (1.0, 0.5) = −1.5, = f1 x = 12, = f1 y = 1.0,
∂x ∂y

∂f1 ∂f2
f2 (1.0, 0.5) = −0.5, = f2 x = 1.0, = f2 y = 1.0.
∂x ∂y
Example 0.10
Solve the following system of two equations using the Newton’s method with given
accuracy  = 10−5 .
4x3 + y = 6
x2 y = 1
Assume x0 = 1.0 and y0 = 0.5 as starting values.
Solution. Obviously this system of nonlinear equations has an exact solution of
x = 1.088282 and y = 0.844340, (see Figure 10). Let us look how the Newton’s
method is used to approximate these roots. The first partial derivatives are as
follows:
f1 (x, y) = 4x3 + y − 6, f1 x = 12x2 , f1 y = 1,
f2 (x, y) = x2 y − 1, f2 x = 2xy, f2 y = x2 .
At the given initial approximation x0 = 1.0 and y0 = 0.5, we get

∂f1 ∂f1
f1 (1.0, 0.5) = −1.5, = f1 x = 12, = f1 y = 1.0,
∂x ∂y

∂f1 ∂f2
f2 (1.0, 0.5) = −0.5, = f2 x = 1.0, = f2 y = 1.0.
∂x ∂y
The Jacobian matrix J and its inverse J −1 at the given initial approximation can
be calculated as follows:
 ∂f ∂f1  
1 
 ∂x ∂y  12.0 1.0  
J =

=
   and J −1 = 1 1.0 −1.0
.
 ∂f2 ∂f2  11.0 −1.0 12.0
1.0 1.0
∂x ∂y

6
Y

x2y = 1

4x3 + y = 6

−6
−6 0 6
X

Figure 10: Graphical solution of the given nonlinear system.

By using the following formula

   
 ∂f
1 ∂f1 −1  
xn+1 xn  ∂x ∂y  f1
 = −
  
 , (18)
yn+1 yn  ∂f2 ∂f2  f2
∂x ∂y
we get the first approximation as follows
        
x1 1.0 1 1.0 −1.0 −1.5 1.090909
= − = .
y1 0.5 11.0 −1.0 12.0 −0.5 0.909091
Similarly, the second iteration gives
      
x2 1.090909 1 1.190082 −1.0 0.102178
= −
y2  0.909091  15.012077 −1.983471 14.280989 0.081893
1.088264
= .
0.844686
The first two and the further steps of the method are listed in Table 3. •

Table 3: Solution of a system of two nonlinear equations

n x-approx. y-approx. 1st. func. 2nd. func.

xn yn f1 (xn , yn ) f2 (xn , yn )
00 1.000000 0.500000 -1.50000 -0.500000
01 1.090909 0.909091 0.102178 0.081893
02 1.088264 0.844686 0.000091 0.000377
03 1.088282 0.844340 0.000001 0.000001
Procedure
Newton’s Method for Two Nonlinear Equations

1. Choose the initial guess for the roots of the system, so that the determinant
of the Jacobian matrix is not zero.
2. Establish Tolerance (> 0).
3. Evaluate the Jacobian at initial approximations and then find inverse of
Jacobian.
4. Compute new approximation to the roots by using iterative formula

x[n+1] = Z[n] + x[n] . (19)

.
5. Check tolerance limit. If k(xn , yn ) − (xn−1 , yn−1 )k ≤ , for n ≥ 0, then end;
otherwise, go back to step 3, and repeat the process.
Summary

In this lecture, we ...

I Introduced the Secant Method
I Introduced the Multiplicity of a Root
I Introduced the Convergence of Iterative Methods
I Introduced the Systems of Nonlinear Equations