MATH260001 Numerical Analysis 202021
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
MATH260001
Numerical Analysis
Semester Two 202021
1. In this question, we assume that your calculator can only perform the four elementary
arithmetic operations, + , − , × and ÷ . In particular, your calculator cannot compute
We want to calculate an approximation of cos(π/5), using polynomial interpolation through the three points x1 = π/6, x2 = π/4 and x3 = π/3.
(a) Calculate the three Lagrange polynomials, defined such that Lk (xi ) = δik where δik is the Kronecker delta. Write your results in the form
Lk (x) = ak ( )2 + bk + ck for k ∈ {1, 2, 3},
where ak , bk and ck are integers. [6 marks]
(b) Calculate the polynomial P (x) that interpolates the function f (x) = cos x at x1 , x2 and x3 . Write the result in the form
P (x) = α ( )2 + β + γ, (1)
where the coefficients α , β and γ depend explicitly on ^2 and ^3, which would have to be estimated numerically in the next part of the question. [2 marks]
(c) Write down a Newton’s step to approximate any radical number of the form ^k η ,
where k is an integer and η a positive real number . Use this algorithm to find an
approximation to ^2 accurate to within 10 −4 . Then, calculate an approximation
to ^3, with the same level of accuracy, by means of another root-finding method
of your choice . (In your estimation of the error, recall that ^2 and ^3 are assumed
unknown.) [7 marks]
(d) Find an approximation to cos(π/5) by evaluating P (π/5) using equation (1) and your numerical estimations of ^2 and ^3 from part (1.c). [2 marks]
(e) Bound the error in your approximation of cos(π/5) using the error formula for
Lagrange interpolation and π ≈ 3. 14159 . [3 marks]
2. (a) Give the definition of the double root of a function and sketch the graph of a function with two roots: a simple root, marked , and a double root, marked x∗ .
[3 marks]
(b) Find an unseen example of a function, f , with a double root, x∗ . The function f should not be a polynomial but could be any rational and transcendental function. Perform enough iterations of Newton’s algorithm, written as a fixed-point iteration xn+1 = g(xn ), to infer the order and rate of convergence of the sequence of data produced. Prove this assertion by writing a Taylor series for g about x∗ , in powers
of (xn − x∗ ) . [7 marks]
f (x)
h(x) =
(2)
based on your choice of f in part 2.b. Perform enough iterations of Newton’s algorithm for h(x) to infer the order of convergence of the improved method. Prove that the order and rate of convergence of the improved method are consistent with the values suggested by your numerical data. [10 marks]
3. The coefficients of the polynomial P (x) = a0 +a1 x +a2 x2 +a3 x3 interpolating the four distinct points (xi , fi ), for i ∈ {1, 2, 3, 4}, satisfy the linear system
Vp = f, (3)
where pT = (a0 , a1 , a2 , a3 ), fT = (f1 , f2 , f3 , f4 ) and V is the Vandermonde matrix.
Keep all rational numbers in your calculations as fractions, not as decimal numbers.
(a) Showing all your working throughout, find the LU-factorisation of the matrix
\1(1) 1 4(1) 1
1 1 1 1
(1 α α α )
where α is an arbitrary number. [6 marks]
(b) Write down the Vandermonde matrix, V , for the four points x1 = − 1, x2 = 2 ,
(c) Using the results from part (3.b), solve equation (3) for p, where the components of the right-hand side vector f are the last four digits of your student ID number. Then write the polynomial interpolating the four data points (xi , fi ), for i ∈ {1, 2, 3, 4}. (No marks will be given for using Lagrange interpolation.) [5 marks]
(d) Using the results from part (3.b), calculate the Lagrange polynomials L4 (x) and L3 (x) defined such that Lk (xi ) = δik where δik is the Kronecker delta. (No marks will be given for using the formula for Lagrange polynomials.)
The last two Lagrange polynomials are
L1 (x) = − + − and L2 (x) = − + . (4)
Without computing the inverse of the Vandermonde matrix V , explain how to find V −1 using of the coefficients of the Lagrange polynomials and write down the result. [6 marks]
4. (a) Consider the n-point Newton-Cote quadrature rule
f(x)dx ≈ wi f(xi ).
(5)
Give the general form function, show that
(b) The quadrature rule
of the expected error term. By considering a constant
wi = h.
[3 marks]
h(h) f(x)dx = w1 f(x1 ) + w2 f(x2 ) + E
(6)
can be made exact for all cubic polynomials, by using a suitable choice of weights and points, respectively wi and xi , i ∈ {1, 2}.
• Write down four equations satisfied by w1 , w2 , x1 and x2 .
• Combine two of these equations to show that x2 = −x1 and hence that
• Calculate the weights and then the value of the quadrature points.
• Find the error term and write the quadrature rule (6). What class of quadra- ture rules does it belong to? [9 marks]
(c) Consider the polynomial P (x) = a0 + a1 x + a2 x2 + a3 x3 , where the coefficients ai , i ∈ {0, 1, 2, 3} are the last four digits of your student ID number. Compute the definite integral ∫1 P (x)dx and its approximation using the quadrature rule obtained in part (4.b). Discuss your results. [3 marks]
(d) We want to find a three-point formula,
f(x)dx = w1 f(x1 ) + w2 f(x2 ) + w3 f(x3 ) + E, x1 < x2 < x3 , (7)
−h
h(h) f(x)dx = h(h) f(−x)dx.
(8)
The quadrature rule should also possess such a property of integrals. Using this
argument of symmetry, show that x2 = 0 and find relations between x1 and x3 ; and between w1 and w3 . Then, calculate the weights and points that make this rule exact for polynomials of the highest degree possible. Find the error term and write the quadrature formula (7). [5 marks]
5. The function y(t) satisfies the ordinary differential equation
dy
dt
The variable t takes discrete values, tn with a constant step-size h = tn+1 − tn , for all
(a) Derive an implicit scheme by integrating (9) over the interval [tn , tn+1], using the trapezium quadrature rule. [3 marks]
(b) Consider the case f (y) = −λy where λ > 0 is a constant.
yn+1 = yn .
iii. Solve the difference equation (i.e. write down yn in terms of y0 ) and show that this implicit scheme is unconditionally stable. [8 marks]
(c) Verify that y(t) = t ln t + 2t is a solution of equation (9) for f (t, y) = 1 + y/t , with initial condition y(1) = 2 .
Write down the implicit scheme obtained in part (5.a) in an explicit form (i.e. express yn+1 in terms of yn ). Then, starting at t = 1 with h = 1 and y0 = 2 , approximate y at t = 2 and calculate the error of the approximation. [4 marks]
(d) The global error of this numerical scheme can be analysed for f (y) = −λy .
Show, by expanding the global error as a Taylor series in powers of h, that the
method is of second order. [5 marks]
2022-08-22