Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Maths 770 Advanced Numerical Analysis

Assignment 1

2022

Q1.  [15 marks] Let A be the N × N symmetric positive definite matrix defined by

┌    2   -1      0    . . .      0 ┐

' -1      2   -1    . . .          '

1   '                                           '                                                     1

A =       '(')    0   -1      2    . . .      0  '(') ,        with N = 26  and h =           

'    0   . . .      0   -1      2 |

(a) Write a function function  [A]  =  Laplacian(N)  that builds the matrix A.         

(b)  Compute the eigenvalues of A using the standard QR method (i.e., without shift).

(c)  Check your result by comparing with the eigenvalues obtained with the in-built Matlab command eig and with the exact eigenvalues

Q2.  [10 marks] We aim to find the cubic minimax approximation to function u in [0, 1]: u(x) = -ex + (e - 1)x + 1.

(a) Take xj  = j/4, j = 0, . . . , 4 as n + 2 points to start the Remes algorithm.  Perform

three iterations of the Remes algorithm.

(b) Plot the solution and the error at each iteration to observe how the approximation

corrects itself and improves.

Q3.  [25 marks] Matrix A from Q1 is actually the discretisation with centered finite differences

of the 1D Laplacian operator, i.e., second derivative. Let’s now consider the boundary value problem (BVP)

x,u

whose analytical solution is the function u in Q2. We now wish to solve the above BVP numerically, which leads to solving the linear system Auh  = f, with A as in Q1 and where the elements of the right-hand-side f satisfy: fj  = exp(jh), j = 1, . . . , N .

(a) Write Matlab functions for the three following iterative methods

(i) Richardson method              (ii)  Steepest Descent method     (iii)  Conjugate Gradient method

(b) For N = 2n , n = 3, . . . , 7, solve the linear system Auh  = f using the three methods

above with initial guess u0  = 0, tolerance ε = 10z6  and maximum number of iterations MaxIter = 150, 000.

(c) For each value of N, compute the L2-error luh - u(xj )l2 , where u is the function in Q2 and xj  = jh, j = 1, . . . , N, and plot the error with respect to the matrix size N using Matlab command semilogy.

On a second graph, plot the number of iterations required to convergence with respect to n. What conclusion can you draw from these graphs?