MATH0033: Numerical Methods Final exam, 2020-2021
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
MATH0033: Numerical Methods
All questions should be attempted. Marks obtained in all solutions will count.
1. Let f (x) = log(x + 2) - x/2.
(a) Show that f has a unique root α in the interval (0, o).
(b) Prove that [2, 4] is a valid starting interval for the bisection method, and determine
the number of iterations required to find α with an absolute error less than or equal to 10-6 .
(c) Write down the Newton iteration explicitly for this problem. Does the iteration converge linearly or quadratically to α? Justify your answer.
(d) Show that φ1 (x) = 2 log(x + 2) and φ2 (x) = eα/2 - 2 both provide consistent fixed point formulations for f (x) = 0.
Prove that one of these formulations converges to α for any initial guess in [2, 4], while the other does not converge to α, regardless of how good the initial guess is, unless one of the iterates equals α itself.
2. (a) Consider the iterative solution of the linear system Ax = b, where A = ╱ 3(ξ) 4(1) 、,
ξ 0 is a real parameter, and x, b e R2 .
Without computing eigenvalues, give a sucient condition on ξ for the Jacobi and Gauss-Seidel methods to be convergent.
(b) Write down the iteration matrices for the Jacobi and the Gauss-Seidel methods
for the matrix in part (a), and determine a necessary and sucient condition on ξ for the Jacobi and Gauss-Seidel methods to be convergent.
(c) In the gradient method for the solution of a general linear system Ax = b, the relative step length αk in the increment xk+1 - xk = αk rk (with rk = b - Axk denoting the residual) is chosen so as to minimise the magnitude of the error vector ek+1 = x - xk+1 with respect to a certain A-weighted norm. Explain why it is not in general possible in a practical implementation to choose αk so as to minimise the magnitude of ek+1 with respect to the Euclidean norm.
3. (a) Show that if X, Y e Rnxn are symmetric then ρ(XY) s ρ(X)ρ(Y).
(b) Let A e Rnxn be an invertible matrix, and let b e Rn . Suppose that A = A1 + A2 for some symmetric positive definite matrices A1 , A2 e Rnxn . Given a1 , a2 > 0,
consider the following iteration, where I e Rnxn denotes the identity matrix:
} k = 0, 1, 2, . . . .
Show that the iteration can be written in the form xk+1 = Bxk + c for some B e Rnxn and c e Rn that you should specify.
(c) Show that if
R := λ(1σ(a)1 ) │ λ(2σ(a)2 ) │ < 1
then the iteration converges to the exact solution of the linear system Ax = b. You may assume without proof that the iteration is consistent, and that if X, Y e Rnxn then ρ(XY) = ρ(YX).
(d) Now suppose that σ(A1 ), σ(A2 ) c [λ- , λ+] for some 0 < λ- s λ+ < o.
Show that if a1 = a2 = a > 0 the quantity R defined in (c) satisfies
R s ╱max { │ , │}、 2 .
By minimising the right-hand side of this inequality as a function of a, show that a can be chosen so as to give
|xk+1 - x|2 s \2 |xk - x|2 , k = 0, 1, 2, . . . ,
assuming the matrix B in (b) is symmetric.
4. Consider the following IVP involving a system of ODEs for two unknowns S and I:
,
ì ì ì ì ì
(
ì ì ì ì ì
(
dS
(t) = -βI(t)S(t),
dt
dI
(t) = βI(t)S(t) - γI(t), dt
S(0) = S0 , I(0) = I0 ,
0 < t < T,
0 < t < T,
where T, β , γ , S0 and I0 are all positive real numbers.
(a) Write the system in the form
, y\ (t) = f(t, y(t)), 0 < t < T,
defining y, y0 and f, and show that if u, v e [0, 1] × [0, 1] then
|f(t, u) - f(t, v)|o s L|u - v|o
for some constant L > 0 that you should specify.
(b) Define the truncation error Tn for the backward Euler scheme applied to this IVP
system with a uniform time step, and show that, under appropriate smoothness assumptions,
|Tn |o s Ch,
where h is the time step length and C > 0 is a constant you should specify. State the smoothness assumptions on S(t) and I(t) under which your analysis is valid.
(c) Show that the backward Euler solution un considered in part (b) satisfies |y(tn ) - un |o s C* h, 0 < h < h* ,
for some C* > 0 and h* > 0 you should specify.
(d) Write down the system (S) of nonlinear equations that must be solved at each time step in the backward Euler method for this IVP system.
Show that if the system (S) has a solution in [0, 1] × [0, 1] and if γ > β then the Newton method for the solution of (S) converges quadratically to that solution, assuming a sufficiently good initial guess (that you need not specify). If you use any results from lectures, quote them carefully.
2023-04-05