MA2501 Numerical

Methods
Spring 2015
Norwegian University of Science
and Technology Solutions to exercise set 5
Department of Mathematics

1 Assume that the regula falsi method (without modifications) is used for finding the
solution of the equation x3 = 0.
a) Show that during all the iterations one endpoint of the solution interval remains
unchanged, unless the iteration finds the solution after the first step.
b) Denote by ck the result of the method at the k-th step. Show that

|ck+1 |
lim = 1. (1)
k |ck |

Note: It can be proven that the method of false position converges to the root,
so you can assume limk ck = 0.
Remark: A sequence (ck )kN converging to 0 and satisfying (1) is said to converge
sublinearly. Sublinear converge of a sequence means that the number of iterations it
takes to come closer to the limit by even one digit will become arbitrarily large. Thus
numerical methods that have such sequences as output should usually be avoided.

Possible solution:

a) First we note that the equation x3 = 0 has the unique solution x = 0. Thus, unless
one of the iterates becomes 0, we will always have the inequality a < 0 < b. Moreover
we note that the result of the method given the input [a, b] is

ab3 ba3 b2 a2
c= = ab .
b3 a3 b3 a3
Obviously c = 0 if and only if a = b.
Assume now that a 6= b. Then either of the inequalities a2 < b2 or a2 > b2 holds.
Assume first that a2 < b2 . Then, since a < 0 < b and therefore ab < 0, we have

b2 a2
c = ab < 0,
b3 a3
implying that in the next step a is replaced by c. Moreover this implies that also in
the next step the inequality a2 < b2 holds, and thus, again, it is the left endpoint of
the interval that is updated.
An analogous argumentation shows that in the case a2 > b2 it is always the point b
that gets replaced by c.

February 19, 2015 Page 1 of 9

 Solutions to exercise set 5

b) Assume without loss of generality that at the start of the iteration we have a2 < b2
(the case where a2 > b2 can be treated similarly). Then the previous considerations
show that the sequence ck is defined by the iteration c0 = a0 and

b2 c2k
ck+1 = ck b .
b3 c3k

In particular,
ck+1 b2 c2k
=b 3 .
ck b c3k
From the assumption we may assume that ck 0. Thus

|ck+1 | b2 c2k
lim = lim b 3 = 1.
k |ck | k b c3 k

1
2 Apply fixed point iteration to the solution of the equation cos(x) = 2 sin(x) using
the mapping
1
(x) = x + cos(x) sin(x).
2

a) Show that the mapping is a contraction on [0, /2] (note that you also have
to show that (x) [0, /2] for all x [0, /2]).
b) Compute the first five iterates of the fixed point iteration using the starting
value x(0) = 0.
c) Provide an estimate of the accuracy of the outcome of the method after the 5th
iteration. How many iterations will be needed to obtain a result with an error
smaller than 1012 ?

Possible solution:

a) Since x sin(x) for x 0 and cos(x) 0 on [0, /2], it follows that (x) 0 for
x [0, /2]. Moreover sin(x) 0 on [0, /2], implying that (x) x + cos(x) for all
x [0, /2]. Since the maximum of the function x 7 x + cos(x) on [0, /2] is /2,
this shows that, indeed, maps [0, /2] to [0, /2].
Next note that the function is differentiable with
1
0 (x) = 1 sin(x) cos(x).
2
Obviously we have 0 (x) 1 1 1/2 = 1/2 for every x R. In addition, the
function 0 is strictly convex on [0, /2] (since sin and cos are concave on [0, /2], and
therefore the function 0 does not have local maxima in (0, /2). As a consequence,
1
0 (x) max{0 (0), 0 (/2)} = max{1/2, 0} =
2
for all x [0, /2]. Thus we have shown that |0 (x)| 1/2 for all x [0, /2],
showing that is a contraction on [0, /2] with contraction factor 1/2.

February 19, 2015 Page 2 of 9

 Solutions to exercise set 5

b) The first five iterates are

x(0) = 0,
x(1) = 1,
x(2) 1.1196,
x(3) 1.1057,
x(4) 1.1073,
x(5) 1.1071.

c) For estimating the accuracy of the iterates, we use the inequality


 (k)

 C 
 (k)

(k1) 
x x  x x
1C
  

with k = 5 and C = 1/2 (the contraction factor). Thus we obtain

   
x x  x(5) x(4)  2 104 .
 (5)   

In order to estimate the number of iterations that are needed for obtaining an error
smaller than 1012 , we use the inequality
  C k4  (5)  1   1
 x x  x x(4)  = k5 x(5) x(4)  k6 104 .
 (k)   
1C 2 2

Since we want the error to be smaller than 1012 , we obtain from this the condition

2k6 108

or
k 6 + log2 (108 ) 32.6.
Thus we would need 33 iterations.1

3 Define the function G : R R by

(
x + ex if x 0,
G(x) =
1 if x 0.

Show that this function satisfies |G(x) G(y)| < |x y| for all x 6= y R, but has no
fixed point. Why is this example no contradiction to Banachs fixed point theorem?
What happens if you apply fixed point iteration with this function G?
1
All these computations were made with the contraction factor 1/2. It is, however, possible to derive a
much smaller one on a small interval around the solution. Thus, in fact, we are vastly overestimating the
error and the required number of iterations.

February 19, 2015 Page 3 of 9

 Solutions to exercise set 5

Possible solution:

G(x) > x for all x, showing that the function G cannot have a fixed point. Moreover the
function G is differentiable with derivative
(
0 1 ex if x 0,
G (x) =
0 if x 0.

In particular, |G0 (x)| < 1 for all x R. Therefore, for all x < y we have
Z y  Z y
G0 (t) dt G0 (t) dt < |y x| ,

|G(x) G(y)| = 
 
x x

showing that the function G indeed has all the desired properties.

Note that limt G0 (t) = 1. Thus, while |G(x) G(y)| < |x y| for all x and y, there
exists no constant C stricly smaller than 1 such that |G(x) G(y)| < C |x y| for all x and
y. Thus the existence of this function does not contradict Banachs fixed point theorem.

By construction we have G(x) > x for all x, showing that the sequence defined by x(k+1) =
G(x(k) ) is increasing (for any starting point x(0) ). Now assume that this sequence is
bounded. Then it has a limit x R. This limit, however, would satisfy the equation

G(x ) = G( lim x(k) ) = lim G(x(k) ) = lim x(k+1) = x ;

k k k

in other words, x would be a fixed point of G, which is impossible. Hence the sequence is
unbounded and we have
lim x(k) = +
k

regardless of the initial value x(0) .

4 Show that G : R3 R3 , defined by

" r #T
1 1 1 5 3 1 10 3
G(x1 , x2 , x3 ) = cos(x2 x3 ) + , x21 + , ex1 x2 ,
3 6 25 16 100 20 60

has a unique fixed point in D = [x1 , x2 , x3 ]T | 1 xi 1, i = 1, 2, 3 . Use kk .



Approximate the solution to within 105 in kk by applying fixed point iteration.

Possible solution:

D is clearly closed and convex. It is also clear that G is continuous since all the component
functions are continuous from basic continuity laws about products, compositions, and
additions and subtractions.

February 19, 2015 Page 4 of 9

 Solutions to exercise set 5

To show that G is a contraction, we must first show that it maps D into D. Let G =
[g1 , g2 , g3 ], thus
1 1
g1 = cos(x2 x3 ) + ,
3 r 6
1 5 3
g2 = x21 + ,
25 16 100
1 10 3
g3 = ex1 x2 .
20 60

We check that 1 gi (x) 1 for i = 1, 2, 3 and any x D.

For g1 , x2 x3 clearly takes values in [1, 1]. Since cos is even and decreasing on [0, 1] it
follows that
1 1
min g1 = cos(1) + 1,
xD 3 6
1 1 1
max g1 = cos(0) + = 1.
xD 3 6 2

Since g2 is an even function of x1 and increasing on [0, 1] it follows that

r
1 2
5 3 53
min g2 = 0 + = 1,
xD 25 16 100 100
r
1 5 3 21 3
max g2 = x21 + = 1,
xD 25 16 100 100

For g3 , x1 x2 takes values in [1, 1]. Since g3 is an increasing function of x1 x2 it follows

that
1 10 3
min g1 = e(1) 1,
xD 20 60
1 10 3
max g1 = e1 1.
xD 20 60
Thus G maps D into D.

To show that G is a contraction we now compute all the partial derivatives. The non-zero
ones are
g1 x3
= sin(x2 x3 ),
x2 3
g1 x2
= sin(x2 x3 ),
x3 3
g2 1 x
= q 1 ,
x1 25 x2 + 5
1 16
g3 x2 x1 x2
= e ,
x1 20
g3 x1 x1 x2
= e .
x2 20

February 19, 2015 Page 5 of 9

 Solutions to exercise set 5

Again the continuity of all these follow from basic continuity rules for multivariable func-
tions, so G is continuously differentiable.

We must now show that for the Jacobian of G, JG , we have

maxkJG k C < 1
xD

From the definition of this matrix norm we must show that the maximum absolute row
sum satisfies this bound. For the 1st row we have the absolute row sum
3  
X  g1  |x2 | + |x3 |
 xj  =
  |sin(x2 x3 )| .
3
j=1

This clearly has maximum value in D when |x2 | = |x3 | = 1, i.e. the maximum value is
3  
X  g1  2
max  xj  = 3 sin(1).
 
xD
j=1

For the 2nd row we have the absolute row sum

3  
X  g2  1 |x1 |
 xj  = 25 q 2 .
 
5
j=1 x + 1 16

This is 0 for x1 = 0. For any x1 6= 0

1 |x | 1 |x1 | 1
q 1 < p = .
25 x2 + 5 25 x1 2 25
1 16

Therefore
3  
X  g2  1
max  xj  25 .
 
xD
j=1

Finally the 3rd row has absolute row sum

3  
X  g3  |x1 | + |x2 | x x
 xj  = e 1 2.
 
20
j=1

It is apparent by inspection that the maximum value in D happens when x1 x2 = 1, i.e.

the maximum value is
3  
 g3 
= e .
X
max 
xD  xj  10
j=1

Since
2 e 1
sin(1) > > ,
3 10 25
the maximum absolute row sum, and thus
2
maxkJG k = sin(1) 0.561 < 1
xD 3
Thus G is a contraction with contraction factor C = 0.561.

February 19, 2015 Page 6 of 9

 Solutions to exercise set 5

To solve the problem to within 105 in the infinity-norm, we apply the final error bound
from Banachs fixed point theorem and iterate until
1 C 5
kx(k) x(k1) k 10 7.8 106 ,
C
and then return x(k) . Starting at x(0) = 0 we find that this bound is satisfied at k = 4.
Then x(4) [0.50000, 0.00000, 0.52360], which is correct to the digits given. The error
bound is somewhat conservative, and x(3) would have been accurate enough. The true
error for x(4) turns out to be about 1.8 109 .

5 Find an approximation of a solution of the equation x3 2x 5 = 0 by applying

three steps of:
a) the bisection method with starting interval [2, 3],
b) the secant method with starting values x(0) = 3 and x(1) = 3.5,
c) the Newton method with starting value x(0) = 3.

Possible solution:

a) For the bisection method we obtain the intervals given by

a = 2, b = 3,
a = 2, b = 2.5,
a = 2, b = 2.25,
a = 2, b = 2.125.

b) For the secant method we obtain

x(0) = 3,
x(1) = 3.5,
x(2) 2.4622,
x(3) 2.2615,
x(4) 2.1229.

c) Newtons method yields

x(0) = 3,
x(1) = 2.36,
x(2) 2.1271,
x(3) 2.0951.

The actual solution is

x 2.09455.

February 19, 2015 Page 7 of 9

 Solutions to exercise set 5

6 Compute the first three steps of the Newton method for the solution of the system
of equations
5x + 2 sin(x) + cos(y) = 0,
4 cos(x) + 2 sin(y) 5y = 0
with initial value (x(0) , y (0) ) = (0, 0) (you may want to use Matlab for solving the
linear systems).

Possible solution:

For the application of Newtons method we denote

 
5x + 2 sin(x) + cos(y)
F (x, y) := .
4 cos(x) + 2 sin(y) 5y

Then the Jacobian of F is

 
5 + 2 cos(x) sin(y)
JF (x, y) = .
4 sin(x) 2 cos(y) 5

Its inverse can be calculated analytically as

 
1 1 2 cos(y) 5 sin(y)
JF (x, y) =
det JF (x, y) 4 sin(x) 5 + 2 cos(x)

with

det JF (x, y) = 25 10 cos(x) 10 cos(y) + 4 cos(x) cos(y) 4 sin(x) sin(y).

Newtons method now defines iteratively

 (k+1)   (k) 
x x
= JF (x(k) , y (k) )1 F (x(k) , y (k) ).
y (k+1) y (k)

Starting with (x(0) , y (0) ) = (0, 0), we thus obtain the iterates
 (1)   
x 1 1
= ,
y (1) 3 4
 (2)   
x 0.1302
,
y (2) 1.1838
 (3)   
x 0.1330
.
y (3) 1.1597

7 Implement in Matlab Newtons method for the solution of an equation f (x) = 0

with f : R R. Your function should take as an input the function f , its deriva-
tive f 0 , and a starting value x(0) . Test your implementation on the functions in
example 5 of this exercise set.

February 19, 2015 Page 8 of 9

 Solutions to exercise set 5

Matlab-comments

There are basically two methods to pass functions as arguments to another function.
The first possibility is to pass the name of the function as a string (that is, the name
written in single quotes). Then the command feval can be used for evaluating the
function. Alternatively, you can pass a function handle, which is an argument of the
form @f, where f is the function. Then you can evaluate the function either directly
with f(x) or, again, using feval.
Consider for example the function
function y = myfun(f)
y = feval(f,1);
end
If you then call myfun(sin), you obtain as result sin(1). The same result will be
obtained using the function call myfun(@sin).

Possible solution:

You find some example code on the webpage of the course.

February 19, 2015 Page 9 of 9