lOMoAR cPSD| 47389193
, lOMoAR cPSD| 47389193
COS2633 NUMERICAL METHODS 1 May/June 2024
SOLUTIONS
QUESTION 1
(a) Consider the equation f(x) = 0.
(i) Describe the false position (regula falsi) method for solving the equation f(x) = 0. (2)
The Regula Falsi (false position) method is an iterative method to solve equations of the form f(x) = 0. We
start with two initial approximations p0 and p1 and their respective images q0 and q1. Then set p as the
x−value of the intersection of the line joining (p0,q0) and (p1,q1) with the x−axis.
p = p1 − q1(p1 − p0)/(q1 − q0); q = f(p)
(p,q) become the new (p0,q0) if q and q0 have the same sign, or the new (p1,q1) if q and q1 have the same
sign. Then we repeat the process until we find a p such that f(p) = 0 or the distance between p and p1 is less
than a given tolerance.
(ii) Explain briefly the main difference between the false position method and the secant method. (2)
The difference between the false position method and the secant method is that in the false position method,
every successive pair of approximations of the root actually brackets the root, which is not a requirement
for the secant method.
(iii) Give two examples of methods which find an approximate solution to f(x) = 0 by using a linear (2)
approximation of the function f.
We have the false position method, the secant method, the bisection method.
(iv) Give two examples of methods which find an approximate solution to f(x) = 0 by using a non-linear (2)
approximation of the function f.
We have the Mu¨ller’s method, the fixed-point method on g(x) = x − f(x), the fixed-point method on g(x) =
x − f(x)/f′(x), also known as the Newton’s method.
(b) Assume that we need to find the roots of (4)
.
Give two different fixed-point iteration algorithms for finding the root.
We have f(x) = x2 + 1/x − 20, ans thus f′(x) = 2x − 1/x2. Hence we can apply the fixed-point method as follows:
• On g(x) = x − f(x) = x − x2 − 1/x + 20;
. This is also known as the Newton’s
method.
Note: There are many other options.
(c) Use the false position method to approximate the root of f(x) = x2 + 2x − 3. Use x0 = 0 and x1 = 3 as(5) starting
values. Complete two iterations.
• Iteration 1: We have
f(x0) = f(0) = −3 < 0; f(x1) = f(3) = 12 > 0
Hence
, lOMoAR cPSD| 47389193
2 COS2633
MAY/JUNE 2014
• Iteration 2: f(p) has the same sign as f(0), hence x0 = 3/5 and f(x0) = −36/25. Hence
(d) Suppose Newton’s method is to be used to solve the following system of non-linear equations: (8)
x = x2 + y xy +
2y = 1
Write down the system of equations necessary to complete one iteration, using x0 = 1 and y0 = 2 as starting
values. Do not solve the system. We define Then the
and its inverse is
−y 1−2
where D = detJF(x,y) = (1 − 2x)(x + 2) + y = −2x2 − 3x + y + 2.
The Newton’s algorithm (recurrence relation) is given by
which gives
where .
After substitution, we get
Note: There are many options, depending on how you choose F (at least four obvious options), but the reasoning
and procedure is the same.
[25]
[TURN OVER]
Downloaded by Dorothy Reyes (dorothyreyes106@gmail.com)
, QUESTION 2
(a)
(i) Describe the Gauss-Seidel iterative method for approximating the solution to the system of linear (7) equations,
Ax = b, where A is an n × n matrix and b is an n−vector. Then also give the matrix formulation of this method.
The Gauss-Seidel method uses the transformation of the matrix A in the form A = D+L+U where D is the
main diagonal, L is the lower triangular part of A excluding the main diagonal, and U is the upper triangular
part of A, also excluding the main diagonal. From A = D + L + U, we have (provided D + L is invertible)
Ax = b ⇐⇒ (D + L + U)x = b
⇐⇒ (D + L)x = −Ux− +b −
⇐⇒ x = −(D + L) 1Ux + (D + L) 1b
This leads to the recurrence relation
(D + L)x[n+1] = −Ux[n] + b ⇐⇒ x[n+1] = −(D + L)−1Ux[n] + (D + L)−1b
Note: If A = D − L − U, the recurrence relation becomes
(D − L)x[n+1] = Ux[n] + b ⇐⇒ x[n+1] = (D − L)−1Ux[n] + (D − L)−1b
And if x = (x1,x2,...,xn), this can also be written as
(1)
At each step, the components already computed are involved in the computation of the following
(remaining) components.
(ii) Use the Gauss-Seidel iterative method to find the solution to the linear system (6)
.
Start with the initial value (2,2), and do two iterations. Is the solution you found after two iterations the
exact solution to the system? Justify your answer!
Using the procedure described in (1) above, we have
Iteration 1
Iteration 2
Indeed (x2,y2) is not the exact solution and this can be checked by straightforward substitution. The exact
solution is actually (x,y) = (2,1).
(b)
(i) Find the inverse of the matrix(7)
