1
MA6000 “seen” in-class test preparation questions
Assignment guidelines:
Assignment brief:
The second MA6000 in-class test will be on Monday 7th March from approx. 15:00-16:30.
The test will be closed-book (although calculators will be permitted) and is based on the ten
questions below. To prepare you should practice solutions to all of these questions so that
on the day you will be able to quickly reproduce them, showing that you understand the
questions and the techniques used to solve them, which hopefully means you will be able
to tackle unfamiliar problems in the future. Please note that the test may include some of
these questions truncated or broken into parts.
Module Learning Outcomes Assessed:
This assessment (test 2) is designed to assess your ability in the following three module
learning outcomes:
? use finite difference methods for solving PDEs and understand limitations of
numerical methods.
? find analytically the extrema of functions of two or more variables, with and without
constraints,
? apply appropriate numerical methods to solve unconstrained and constrained
optimisation problems,
Submission deadline:
In-class test on Monday 7th March.
Feedback Date:
You will receive initial feedback electronically in the form of solutions to the questions soon
after the test (by 21th March 2016) and written feedback on your test papers by 28st March
2016. Please see Drs Lau and Chen if you would like to ask any questions about the
feedback.
This is preparatory work for your second coursework. Your coursework mark will be
based entirely on the in-class timed submission. Please do not hand in any of your
preparatory work.
You can also seek support from MathsAid and Drs Lau and Chen on these questions,
however the MathsAid team will have been asked to help you solve problems rather than
give you solutions, so you’re still expected to engage with the mathematics, but please do
ask questions if you are stuck on a problem.
Marking scheme and feedback:
You are expected to be able to carry out all necessary working to justify your results
and discuss them. Marks shown are approximate only – for guidance – 50 marks
corresponds roughly with work that should be possible to be completed within 60
minutes.
More details of how the marks are broken-down will be on the test paper feedback sheet.
2
1. Consider the following elliptic partial differential equation:
U U 1000(x y), (x, y) D.
xx ? yy
? ? ?
The region D, the values of
U(x, y)
around the boundary and the mesh imposed on the
region are specified in the figure below. You may assume that the grid spacing in both
directions is 0.1 and that the region is positioned so that the bottom edge lies on x-axis and
the left-hand tip touches the y-axis (thus, for example, mesh point 1 has coordinates (0.2,
0.1).
Use the central difference method to approximate the above partial differential equation
and show that the resulting set of linear equations can be written in the form:
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
5
6
3
16
3
0 0 0 1 4
1 0 1 4 1
0 0 4 1 0
1 4 0 0 0
4 1 0 1 0
5
4
3
2
1
v
v
v
v
v
,
(15 marks)
where
vk
, k ?1,…,5
are the approximations to the function values at the mesh points
indicated on the figure. Use Gaussian elimination with back-substitution to solve the
linear equations and work to four decimal places accuracy.
(10 marks)
Continued…
3
2. Use the Forward Difference method to approximate the solution to the following
parabolic partial differential equation at t=0.1, using
?x ?1
and
?t ? 0.1:
0, 0 4, 0
4
2
2
2
? ? ? ?
?
?
?
?
?
x t
x
U
t
U
?
U(0,t) ?U(4,t) ? 0, t ? 0,
), 0 4.
4
)(sin
4
U(x,0) ? (1? 2cos x x ? x ?
? ?
Work to 4 decimal places accuracy.
(15 marks)
If the analytical solution to the above problem is:
,
4
sin
2
( , ) sin 4 x e x
t U x t e
t
? ? ?
?
?
?
compare it to your numerical solution at the grid points, calculate the errors and
comment.
(10 marks)
Continued…
4
3. By using the central differences, show that an explicit numerical scheme for solving
the following hyperbolic equation
??
2??
????
2 – ??
??
2??
????
2 = 0, ?? = 0, 0 = ?? = 1 (D is a constant) (3.1)
subject to:
??(0,??) = ??(1,??) = 0, ?? = 0,
??(??, 0) = ??(??), 0 = ?? = 1 ,
????
????
(??, 0) = ??(??), 0 = ?? = 1 (3.2)
is:
????,??+1 = ????
2 ????-1,?? + 2(1 – ????
2
)????,?? + ????
2 ????+1,?? – ????,??-1 (3.3)
where
????,?? = ??(????
,????)
?? =
??
h
, and h and k are step sizes in the x and t directions respectively.
(6 marks)
The explicit formula (3.3) requires starting values over two time levels. The first set of
starting values ????,0 = ??(????). We also need ????,1 , which we obtain from ????
????
(??, 0) = ??(??)
by approximating the derivatives using differences.
By approximating ????
????
(??, 0) = ??(??) using central differences, show that
????,1 =
1
2
(????
2 ????-1,0 + 2(1 – ????
2
)????,0 + ????
2 ????+1,0) + ?? ??(????) (3.4)
(5 marks)
Apply the explicit scheme (3.3), solve the hyperbolic equation (3.1) with D = 1,
h=k=0.2, and ??(??) = sin(????) , ??(??) = 0, for 0 = ?? = 1 ?????? 0 = ?? = 0.8 .
Work to 3 decimal places accuracy.
(14 marks)
Continued…
5
4. Investigate the stationary points of the function
f (x, y) x y 6x 12y
3 3
? ? ? ?
and determine their nature.
(6 marks)
5. The Golden Section Search is to be applied to a unimodal function to find the minimum
in the interval [0,2]. If we require the error in the calculated optimum to be not greater
than 0.005 how many iteration steps ?? do we need to perform? (Here you may assume
???? = ?? = 0.382 is the value of the ratio for symmetric interval sub-division.)
(4 marks)
6. The Fibonacci Search is to be applied to a unimodal function to find the minimum in
the interval [4,6]. If we require the error in the calculated optimum to be not greater
than 0.01 how many terms of the Fibonacci sequence do we need to use?
(4 marks)
7. Use Hooke and Jeeves’ method to minimize
2 2
f (x, y) ? x ? y ? 2x ? 2xy ? y .
Take
T
b (0,0)
1 ?
as the initial point and
h ?1
as the initial step length. Work to four
decimal place accuracy and stop when the step length
h ? 0.25.
(5 marks)
Continued…
6
8. Use Nelder and Mead’s method on function
( , ) 2 36 4 2 2 4
f x y ? x ? x y ? y ? . Start from the
simplex defined by (1,2), (2,2) and (1,3) and terminate the procedure either after seven
iterations or when you need to reduce the size of the simplex by halving the distances from
l
x . Do NOT perform more than 7 iterations.
(20 marks)
You may assume the following for Nelder and Mead’s method:
If
h
x ,
l
x
and
s
x
denote the vertices with the highest, the lowest and the second highest
function value respectively, then the centroid
c
x
is given by:
( )
2
1
c l s
x ? x ? x
Reflection:
c h
x ? 2x ? x 0
Expansion:
c
x ? x ? x 00 2 0
Contraction: If
( ) ( )
0 h
f x ? f x
then
( )
2
1
00 0 c
x ? x ? x
If
( ) ( )
0 h
f x ? f x
then
( )
2
1
00 h c
x ? x ? x
(If a new point gives a function value equal to a current value then the new point is
treated as having a higher function value.)
9. State, in vector form, first three terms of the Taylor series for a function of three variables
f (x) ? f (x, y,z)
about the point
( , , )
0 0 0 0
x ? x y z
(2 marks)
Hence, state the necessary conditions for
0
x
to be an optimum of
f (x)
and the second
order sufficient condition for
0
x
to be a local maximum of
f (x) .
(3 marks)
Continued…
7
10. For the function
1 2
2
2
2
f (x) ? x1 ? 2x ? 4x ? 4x
by using the method of steepest descent
applied with initial guess
T
x (0,0)
(0)
?
,generate the sequence
(1)
x
and
(2)
x
(5 marks)
Hence deduce the minimum of
f (x)
(5 marks)
The method of Steepest Descent is used to find a local minimum of a well behaved
function of several variables
f (x)
. Show that the method moves in orthogonal steps,
i.e. if
( )
1 k k k
k
k k k
x ? x ? g ? x ? ?f x ? ? ?
then the vector
k k
x ? x ?1
is orthogonal to the
vector
k?2 ? k?1
x x
. Here
( )
k
k
g ? ?f x
is the gradient vector of
f (x)
and
?k
minimises
( )
k
f xk ? ?g .
(10 marks)
The method is now applied to the function
2 2
f (x) ? x ? y ? 2x ? 2xy ? y
with
T
x (0,0) 0 ?
as the starting point and
h ? 0.75
as the initial step-length. The minimum
of
( )
k
f xk ? ?g
is calculated using Powell’s quadratic interpolation method. Powell’s
quadratic interpolation method states that given three points
( , )
l l ? f , ( , )
n n ? f ,
( , )
u u ? f
, the turning point
( , ) m m ? f
of the quadratic through these points, can be
calculated from
( ) ( ) ( )
( )( )( )
2
1
2 l n u n u l u l n
l u l u u n n l
m
f f f
f f
? ?? ? ? ?? ? ? ??
? ? ?? ? ??
?
? ? ?
? ?
and that
( , ) m m ? f
is a minimum if
0
( )( )( )
( ) ( ) ( )
?
? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ?
n u u l l n
l n u n u l u l n
f f f
.
Illustrate how Powell’s quadratic interpolation method is applied by performing two
iterations. Work to four decimal places accuracy.
(15 marks)
END OF COURSEWORK