MATH0033 Numerical Methods Exam 2021-2022
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
MATH0033
Answer all questions .
1. (a) Consider the function f : [0, ∞) → R defined by f(x) = sinx − x cos x.
We are interested in finding positive roots of f . Consider the following two fixed point iterations
xk+1 = ϕ 1 (xk ), ϕ1 (x) = tanx
k+1 = ϕ2 (k ), ϕ2 (x) = x − +
where x0 and 0 are initial guesses. For each of the two fixed point iterations above, determine
(i) if the method is consistent for any positive root α > 0 of f; (ii) if the method is locally convergent near a positive root α > 0 of f .
If either of these methods is locally convergent, determine also the corre- sponding order of convergence of that method.
(b) Provide an original example of a real-valued function f of a single real vari- able and a corresponding real root α of f such that Newton’s method has local convergence of order equal to three, and no higher than three. Justify your answer by proving that your example fulfills the required condition. Your answer should consist of an original example of your own creation that is not found already in the course materials or other references . (25 marks)
2. Let A ∈ Rn ×n be the symmetric tridiagonal matrix given by
A = . . . . . . . . .
( )
where a and b are both positive real numbers, and where all other entries of A not shown above are zero.
(a) Show that the eigenvalues λk of A are given by
λk = a + 2bcos ( ) ,
for k = 1, . . . ,n. What is the maximum and minimum eigenvalue of A? Hint: check that the vectors vk given by
vj(k) = sin ( ) j = 1, . . . ,n
are eigenvectors for k = 1, . . . ,n .
(b) Considering still the matrix A given above, show that the Jacobi method for the system Ax = b is convergent if and only if A is positive definite.
(c) For a given initial guess x0 , let xk , k ≥ 1, denote the k-th iterate of Jacobi’s method for the linear system Ax = b. Let ϵ > 0 be a given tolerance. Find
a sufficient condition on k in terms of n, a, b and ϵ to ensure that ∥xk − x∥2 ≤ ϵ .
Use this to describe the behaviour of the convergence of Jacobi’s method as n becomes large.
Hint: your answer should distinguish the cases where a > 2b, a = 2b and a < 2b . (25 marks)
3. Let A ∈ Rn ×n be a symmetric positive definite matrix, let b ∈ Rn . For a given 北0 ∈ Rn , consider the Conjugate Gradient method given by the sequence of
iterations
北k+1 = 北k + αkpk , αk =
(Apk , pk ) , for each k ≥ 0, where rk = b − A北k for all k ≥ 0, with p0 = r0 .
(a) Show that, for any k ≥ 1,
(rk , rj ) = 0 Aj = 0, . . . ,k − 1.
Recall any results from the lectures that you use as part of your answer. (b) Show that the coefficients αk can be equivalently written as
∥rk ∥2(2)
αk =
What can be said about the error 北 − 北k if αk = 0 for some value of k?
(c) Construct an original example of a matrix A and vector b to show why the Conjugate Gradient method cannot generally be applied in the case where A is not symmetric positive definite. Your answer should show clearly the reason why the Conjugate Gradient method is not applicable to your example.
Your answer should consist an original example of your own creation that is not found already in the course materials or other references . (25 marks)
y\ (t) = y2 (t) t > 0,
y(0) = 1
and consider it’s approximation by the Backward Euler method with step length h given by
(1) un+1 = un + hun(2)+1 , u0 = 1.
(a) Show that the equation (1) admits two real solutions for un+1 in terms of un , provided that un satisfies a condition that you should specify as part of your answer. Explain why one of these solutions is not appropriate for approximating the solution y(t) and can thus be discarded.
(b) Considering only the appropriate solution found in part (a), find a recur- rence relation for the quantity zn = 1 − 4hun of the form zn+1 = ϕ(zn ) for some function ϕ that you should determine.
(c) Using your answers in part (a) and (b), prove that for any h > 0, there exists an n ∈ N such that no real solution un+1 exists. What feature of the solution y(t) of the original problem does this numerical scheme reproduce? Hint: you may use without proof the fact that the exact solution of the initial value problem is y(t) = (1 − t)−1 . (25 marks)
2023-04-05