MA20222 Coursework 2020/21
Due Noon Thursday 3rd December 2020.
Include your m-files in the report, and type the report in Word (or similar) or LaTeX1.
Please also upload your m-files.
There will be two submission points on MOODLE, one for m-files and another for the report in
pdf format.
Grade This coursework contributes 25% to the final grade.
60% Content.
40% Presentation. Write up your mathematical arguments and computational results clearly
and concisely. Present your answer to the questions in order, including figures or plots along-
side your discussion 2. Think about what to include to answer the questions effectively and
don’t include anything that is not needed. Any MATLAB code should be well commented.
Each question in the assignment is equally weighted (although not all questions are of the same
length).
Complex numbers In MATLAB, i or j both represent imaginary i =
√−1 , but they can be easily
overwritten by i=1 for example. It is better to use 1j, which cannot be changed.
>> 1j
ans =
0.0000 + 1.0000i
MATLAB can easily evaluate complex-valued functions:
>> sin(1j) % this is sin of imaginary i
ans =
0.0000 + 1.1752i
Notice that even though 1j is used, the results are returned using the i notation.
1Overleaf http:\\www.overleaf.com is recommended as a very convenient way of using LaTeX. See https://www.
overleaf.com/read/jtbjbfbgddtx for a template.
2Note that if a question asks for a plot or any other numerical results, then this needs to be clearly displayed in the
report. It is not enough to ask the examiner to run your code to regenerate the figures.
1
A The Newton fractal
Consider a function f : C → C and the problem of finding roots of f in the complex plane rather
than the real line. We use Newton’s method, the same formula used in class for the real line, in the
complex plane.
A1. Consider a sequence en of positive real numbers converging to zero such en+1 = Kern where r
is the order of convergence (as defined in your notes) and K > 0 is a constant. Show that
log en+1
log en
→ r , as n→∞ .
[5 marks]
A2. Write an m-file to apply Newton’s method to a given function f . Use the following syntax
function [z,allzn]=Newton(f, df, z0, N)
% f is a function and df its derivative
% z0 is the initial data (complex)
% N is the number of iterations
% return values:
% z is the final approximation of Newton’s method
% allzn contains the sequence generated by
% Newton’s method (including the initial condition).
.
.
which should be callable with
z0=0.5; N=5; f=@(z) (z^5-1); df= %fill in
[z,allzn]=Newton(f, df, z0, N)
Let Z1, . . . ,Z5 denote the five roots of f (z) = z5 − 1 . Choose three initial data far from the
roots of f and plot the convergence of Newton’s method using a semi-log plot (see the MATLAB
command semilogy) for the error en := |Zk − zn| against n , where Zk is the relevant root and
zn the sequence generated by Newton’s method.
Compute the quantity log en+1/ log en . According to the convergence theory for Newton’s
method, what do you expect this ratio to be? What is it in your experiments? [5 marks]
A3. Look up the command pcolor (i.e., type help pcolor) and try it out; for example,
>> C=[1 2 0; 3 4 0; 0 0 0];
>> pcolor(C) % plot appears
>> x=[-1,0,1]; y=x;
>> pcolor(x,y,C); % plot appears with axis
>> shading flat % tweaks the way the colours are plotted
2
The last row and column of C are ignored and a checker-board plot of the entries is shown.
Let xi , yi := −R + 2R(i − 1)/(M − 1) for i = 1, . . . ,M and R > 0 . Put M = 100 and R = 1.2
and, for each i , j = 1, . . . ,M , start Newton’s method with initial condition z0 = xi +
√−1 yj and
run 100 iterations. Let Ci j = k if the result of the Newton iteration is closest to Zk (from A2). At
the end of this, you should have an M ×M matrix C with entries 1, . . . , 5 .
Plot C using pcolor and mark the location of the roots Z1, . . . ,Z5 . Label the real and imaginary
axis (be sure to get them the correct way round!). Include the plot in your report.
Look up the convergence theorem for Newton’s method (Theorem 4.3) and relate the “there
exists > 0 ” part to the plot. [5 marks]
A4. In the following, if you like, change the colour scheme to depend on the number of iterations
required to attain a certain tolerance instead of the target root (or a combination of the two) or
change the underlying function f . Many choices generate interesting fractals.
Generate your Newton fractal. Zoom into an interesting part of the plot (to reveal finer structure
than was possible on the original plot). To get sufficient resolution, you should increase the
number of Newton iterations and define a new set of xi and yj .
Zoom into an interesting part of the plot. You should provide three plots using pcolor in total.
Quote a definition of fractal (look it up on the web) and relate it to your plots. [5 marks]
B Derivative-free nonlinear solver
Frequently in applications, it is hard or impossible to provide explicit derivatives f ′(x) to an algorithm
and so-called derivative-free methods are required. We explore a variant of Newton’s method that is
derivative free, based on the approximation
f ′(xn) ≈ f (xn)− f (xn−1)xn − xn−1 ,
if xn−1 6= xn and |xn − xn−1| is small.
B1. Suppose x0, x1 are given, and consider the iteration
xn+1 = xn − xn − xn−1f (xn)− f (xn−1) f (xn), n ≥ 1, (1)
where we assume that f (xn) 6= f (xn−1) .
Code up this method, taking care to note it needs two initial conditions x0, x1 . Apply it to f (z) =
z5 − 1 and compare its rate of convergence to Newton’s method, using the method from A2. [5 marks]
B2. Let x be a root of f , and xn be approximations generated by (1), and define the error en =
x−xn . Derive the following expression for the error en+1 at step n+1 , using the Newton divided
differences:
en+1 = −en−1 en A, for A := f [xn−1, xn, x ]f [xn−1, xn] .
3
Assume that |A| ≤ A¯ for all x , xn, xn−1 ∈ R , where A¯ is some given constant real number.
Define En := |en|/K for a constant K . Show how to choose K so that
En+1 ≤ EnEn−1.
[5 marks]
B3. For simplicity, we suppose this inequality holds exactly and derive the resulting rate of the error
converging to zero. Consider En ∈ (0, 1) such that En+1 = EnEn−1 and En → 0 as n → ∞ .
Show that, for a real-number C independent of n ,
En+1 ≤ CEφn ,
where φ = (1 +
√
5)/2 (the golden ratio).
Compare the rate φ to your computations in B1. [5 marks]
C Systems of equations
We are interested in solving the nonlinear system of equations
f1(x1, . . . , xd) = 0,
...
fd(x1, . . . , xd) = 0,
(2)
for x1, . . . , xd ∈ R , given functions f1, . . . , fd : Rd → R .
C1. Fix x ,y ∈ Rd and let g(λ) := fi(x + λ(y − x )) for λ ∈ R . Write the Taylor’s series for g(λ) in
terms of partial derivatives of f , giving the remainder term at second order (i.e., of O(λ2) ). [5 marks]
C2. Let f (x ) := [f1(x ), . . . , fd(x )]T and suppose that |∂
2fi (x )
∂xj∂xk | ≤ K for all i , j , k = 1, . . . , d and x ∈ Rd .
Show how to define a d × d matrix J(x ) and a vector R such that
f (y ) = f (x ) + J(x )(y − x ) +R ,
and ∥∥R ∥∥2 ≤ L∥∥ x − y ∥∥22
for some constant L that you should define. The constant L may depend on d and K , but not
x or y . [5 marks]
C3. Now derive Newton’s method for solving (2) in the form
x n+1 = x n + δ, J(x n)δ = −f (x n).
Discuss the difficulties in using this equation as a practical iterative method for solving Eq.(2). [5 marks]
Total 50 marks
4

欢迎咨询51作业君