COS2633 EXAM MEMO MERGED.

COS2633 EXAM MEMO
MERGED.

, university
of south africa




COS2633 NUMERICAL METHODS 1 October/November 2014



SOLUTIONS

QUESTION 1


(1.1)
√3
(a) Write the Newton formula (recurrence relation) to approximate 5. (3)
√3 3 3
5 is a solution to the equation x = 5, or equivalently, x − 5 = 0. So if we apply the Newton’s
method to the function f defined by f (x) = x 3 − 5, provided x 0 is given, we obtain the relation
3
(x n ) − 5
(1) x n+1 = xn − 2
.
3 (xn )

(b) Perform three iterations of the Newton algorithm as given in (1.1(a)), starting
0 = 2.at x (3)
Applying the formula in equation (1), we have:
Iteration 1: 3
(x 0) − 5 23 − 5
x 1 = x0 − 2 = 2 − 3(2)2 = 1.75
3 (x0)
Iteration 2:
3
(x 1) − 5 (1.75)3 − 5
x 2 = x1 − 2 = 1.75 − 2
= 1.7109
3 (x1) 3(1.75)
Iteration 3:
(x 2)3 − 5 (1.7109)3
−5
x 3 = x2 − 2 = 1.7109 − 2
= 1.7100
3 (x2) 3(1.7109)


x2 y2
(1.2) The ellipse defined by + = 1 and the parabola defined by y =2 x− 2x − 4 intersect at four
16 9
distinct points.

(a) Write the Newton formula (recurrence relation) in the form of a system of equations, to(6)
approxi-
mate any of the intersection points.
We define
x2 y2
F (x, y) = 216 + 9 − 1
x − 2x − y − 4
The Jacobian is
x 2y
J F (x, y) = 8 9
2x − 2 −1
and its inverse is
1 −1 − 2y
(J F (x, y))−1 = − 4 x
9 .
x
8 + 9 y(x − 1) −2x + 2 8
The Newton’s formula is given by
x n+1 x −1
= n − (J F (x n , yn )) F (x n , yn )
yn+1 yn


[TURN OVER]

, 2 COS2633
OCTOBER/NOVEMBER 2014


and if we let D n = det JF (x n , yn ) = − x8n − 4
(x n − 1), we obtain
y
9 n
" #
x 2n y n2
x n+1 xn 1 −1 − 2y9n + − 1
= − 16 9
yn+1 yn Dn −2x n + 2 x8n x 2n − 2x n − y n − 4
 
x 2n y2
xn 1  −1 16 + 9n − 1 − 2y9n x 2n − 2x n − y n − 4
= − 2 2

yn D n (−2x n + 2) x n + y n − 1 + x n x 2n − 2x n − y n − 4
16 9 8

and therefore the required recurrence relation is
h 2
i
y2
x n+1 = x n − D1n −1 x16 n
+ 9n − 1 − 2y9n x 2n − 2x n − y n − 4
h i
x 2n y2
yn+1 = y n − D1n (−2x n + 2) 16 + 9n − 1 + x8n x 2n − 2x n − y n − 4

(b) Perform two iterations of the Newton algorithm as given in (1.2(a)), starting 0, y0)with
= (4,
(x1). (4)
The results are as follows:
Iteration 1: We have D0 = − x80 − 49 y0 (x 0 − 1) = − 48 − 49 × 1 (4 − 1) = −11
6
. Then
h i
x2 y2
x 1 = x 0 − D10 −1 160 + 90 − 1 − 2y90 x 20 − 2x 0 − y 0 − 4
h i
6 42 2
= 4 + 11 −1 16 + 19 − 1 − 29 42 − 8 − 1 − 4
118
= = 3.5758
33
h i
x 20 y 02
y1 = y 0 − D10 (−2x 0 + 2) 16
+ 9
− 1 + x80 x 20 − 2x 0 − y 0 − 4
h i
6 42 2
= 1 + 11 (−2 × 4 + 2) 16 + 19 − 1 + 48 42 − 8 − 1 − 4
16
= 11 = 1.4545
118
Iteration 2: We have D1 = − x81 − 4
y (x 1
9 1
− 1) = − 33
− 4
9
× 16
11
118
33
− 1 = − 471
223
. Then
8
h i
1 x 21 y 12 2y1
x2 =x 1 − D1 −1 16 + 9 −1 − 9
x 21 − 2x 1 − y 1 − 4
" ! #
118 2 16 2 32
118 118 2
= 33
+ 223
471
−1 33
+ 11
−1 − 11
33
−2× 118
33
− 16
11
−4
16 9 9
717
= 203 = 3.5320
h i
x 21 y 12
y2 =y 1 − 1
D1 (−2x 1 + 2) 16
+ 9
− 1 + x81 x 21 − 2x 1 − y 1 − 4
" 2 2
! #
118 16 118
16 223 118 33 11 33 118 2 118 16
= 11
+ 471
−2 × 33
+2 + −1 + 33
−2× 33
− 11
−4
16 9 8
1133
= 804
= 1.4092
(c) What is the error of this process, given the fact that the exact solution is (3 .5316, 1.4088)?
(1)
The error of the process is
p −4
2 + (1.4088 − 1.4092)
e = (3.5316 − 3.5320) 2 = 5.6569 × 10


[17]


QUESTION 2

h i
..
(2.1) By means of
Gaussian Elimination on a larger augmented matrix
A . I where I is the identity (7)
matrix of appropriate size, and by using exact calculation, find the inverse of the matrix
 
1 2 3
A =  2 3 4 .
3 4 1


[TURN OVER]

, 3 COS2633
OCTOBER/NOVEMBER 2014


We have the augmented matrix:
 
..
1 2 3 . 1 0 0
 . 
 2 3 4 .. 0 1 0 Row2 ← Row2 − 2Row1
 Row3 ← Row3 − 3Row1
.
3 4 1 .. 0 0 1
 
..
1 2 3 . 1 0 0
 .. 
 0 −1 −2 . −2 1 0
 Row3 ← Row3 − 2Row2
..
0 −2 −8 . −3 0 1
 
..
1 2 3 . 1 0 0
 .. 
 0 −1 −2 . −2 1 0
 1
Row3 ← −4 Row3
..
0 0 −4 . 1 −2 1
 
..
1 2 3 . 1 0 0 
 ..  1
 0 −1
 −2 . −2 1 0  Row2 ← −1 (Row2 + 2Row3)
..
0 0 1 . −1/4 1/2 −1/4
 
..
1 2 3 . 1 0 0  Row1 ← 1
1
(Row1 − 2Row2 − 3Row3)
 . 
 0 1 0 .. 5/2 −2 1/2 

.
0 0 1 .. −1/4 1/2 −1/4
 
.
 1 0 0 .. −13/4 5/2 −1/4 
 . 

 0 1 0 .. 5/2 −2 1/2 
.
0 0 1 .. −1/4 1/2 −1/4
Therefore the inverse of A is  
−13/4 5/2 −1/4
A −1 =  5/2 −2 1/2 
−1/4 1/2 −1/4


(2.2) The SOR algorithm, with relaxation parameter ω for solving a linear system Ax = b is defined by the
formula  
i−1
X Xn
ω
x [k]
i
[k−1]
= (1 − ω)xi +  bi − aij x [k]
j − aij x [k−1]
j
 .
aii
j=1 j=i+1


(a) Perform two iterations of the SOR algorithm to solve the system (4)

1 2 x 8
=
3 1 y 9

with ω = 0.5 starting with0(x
, y0) = (1, 1).
The results are as follows:
Iteration 1: ω
x1 = (1 − ω)x +
[b1 − a 12y0]
0
a11
0.5
= (1 − 0.5)1 + [8 − 2 × 1]
7
1
= 2



[TURN OVER]