Miniproject – Numerical Linear Algebra – 3NMNLA(4)
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Miniproject – Numerical Linear Algebra – 3NMNLA(4)
1. Let G e Rn×n satisfy ρ(G) < 1. Define
k-1
Sk = Gj .
j=0
(a) Show that I - G is invertible. (b) Prove that
Sk = (I - G)-1 (I - Gk ).
(c) Let v0 , g e Rn be given and consider the recurrence
vk+1 = Gvk + g. (1)
Define wk = g for all k e N and zk = ┌v(w)k(k)┐ . Using (1) and the definition of wk, show that
zk+1 = Hzk ,
where H e R2n×2n is a 2-by-2 block matrix that you should identify.
(d) Using the above recurrence for zk, show by induction that for all k e N
zk = 
┐ z0 .
Deduce that
lim vk = (I - G)-1 g.
[20]
2. Let M, K e Rn×n and f e Rn. The solution u(t) to the system of initial value problems
du
dt
is approximated at time tk := kh, (k e N) by a sequence Uk generated by approximating the time derivative using a finite difference method:
M 
= F(Uk), U0 = u0 . (2)
The parameter h > 0 is called the time-step and the above recurrence is known as the explicit Euler’s method.
(a) Write recurrence (2) as a two-term recurrence in Uk in the form (1), for a matrix G and vector g which
you should specify in terms of M, K, f and h.
(b) Consider the generalised eigenvalue problem
Kxi = µiMxi , (3)
where M, K are assumed to be large, sparse, symmetric and positive-definite.
i. Show that µi are real and positive for all i.
ii. Show further that ρ(G) < 1 if and only if h < hmax for a value hmax which you should specify in terms of the eigenvalues µi in (3).
(c) Let h < hmax. Using the results from Q1, find the limit lim Uk .
[12]
3. To implement efficiently recurrence (2), we re-write it in the form
MUk+1 = 
(Uk), U0 = u0 , (4)
where 
is a function which you should specify in the comments for your code described below.
Write a Matlab function eulermini to implement explicit Euler’s method in the form (4), using a fixed time- step h = 0.8hmax, where hmax is approximated by using a suitable eigenvalue solver of single iteration type. System (4) should be solved at every time step k using the preconditioned Steepest Descent method (PSD) with Uk -1 as initial guess and a tridiagonal preconditioner P comprising the main, sub- and super-diagonals of M . The input to eulermini should be K, M, u0 , f and the number of time-steps N (in this exact order), while the output should be
● a column vector v containing UN;
● the time-step h employed;
● a column vector k containing the number of PSD iterations required at every time step in order to bring the norm of the current residual divided by the norm of the initial residual below a tolerance τ = 10-6 .
Your file should contain all necessary files included as local functions (subfunctions). In particular, note that you should derive and include the eigenvalue solver used for estimating h. [18]
ko↓es on ↓he mNrk之nk proaecüre
Questions 1,2 You should ensure that you state clearly any results you use; you should also reference these results, by indicating where they can be found (e.g., typed lecture notes, example sheets, Matlab tasks etc).
Question 3 The following issues with the file eulermini.m may attract penalties:
● file does not use the suggested input and output as described in the question;
● file does not run due to incorrect syntax;
● file runs but output is incorrect;
● file does not contain the necessary local files;
● implementation does not follow a least complexity approach/principle (e.g., generating a dense matrix inverse in order to solve a linear system etc.); performing unnecessary operations etc;
● file does not suppress unnecessary output;
● file does not contain comments/descriptions;
● file is partially or entirely identical to other submitted files.
2022-05-05