Description

• Write in a neat and legible handwriting or use LATEX
• Clearly explain the reasoning process
• Write in a complete style (subject, verb, and object)
• Be critical on your results
Questions preceded by a * are optional. Although they can be skipped without any deduction, it is important to know and understand the results they contain.
Ex. 1 — Richardson extrapolation
In this exercise we investigate Richardson extrapolation, a sequence acceleration method which can be used to improve the rate of convergence of a quadrature formula.
Let a0 ∈ R be a value to be computed and A(t), t > 0 be such that
(i) limt→0 A(t) = a0;
(ii) For all n ≤ 0, there exist a1,··· ,an, and cn+1 such that
n
A(t) = a0 + ∑aiti + Rn+1(t), with |Rn+1(t)| ≤ cn+1(t);
i=1
Let (An)n∈N be the sequence defined by
A0(t) = A n(tn) ≥
r A
An(t) =, n 1 and r > 1 a constant.
* 1. Prove by induction that for all n ∈ N, An(t) = a0 + O(tn+1).
2. Fixing t0 > 0 and r0 > 1, we define a sequence ™m≥0 such that tm = r0−mt0.
a) Show that when n is fixed then limm→∞ An(tm) = a0.
( −m(n+1)).
b) Show that An(tm) = a0 + O r0
3. For m and n two integers, we define a matrix M whose entry at column n and row m is Am,n = An(tm). Write the pseudocode of a clear algorithm generating the matrix M and returning a0.
4. Romberg integration
a) Understand box 1 and intuitively explain how Richardson extrapolation accelerates the convergence of the trapezium rule.
b) For a function of your choice compare the trapezium rule to Romberg method.

We consider the quadrature formula
. (2.1)
1. Why does formula 2.1 fall under Peano’s method?
2. Determine Peano kernel for this formula, and show that it keeps a constant sign.
3. Conclude on the existence of ξ ∈ [a,b], such that for any f ∈ C2[a,b], the error is expressed as
E(f ) = f ′′(ξ)(b − a)3.
Ex. 3 — Gauss’ method
Let (qk)k∈N be a sequence of polynomials such that
qk(x) = , with x = cos θ.

1. Let w(x) = √1 − x2 be a function over (−1,1).
a) Show that w is a weight function.
b) Show that the (qk)k∈N define a sequence of orthogonal polynomials for the weight function w.
c) Determine the orthonormal polynomials (pk)k associated to (qk)k.
2. We consider the Gauss’ method of order 2n + 1 defined by
n
f (x)w(x) dx ≈ ∑Akf (xk).
k=0
a) Determine all the xk, 0 ≤ k ≤ n.
b) Show that for all 0 ≤ k ≤ n,
π 2 (k + 1)π
Ak = sin . n + 2 n + 2
c) Assuming f ∈ C2n+2[−1,1], show that there exists ξ ∈ (−1,1), such that the error of the method is given by
f (2n+2)(ξ)
En(f ) = c , where c is a constant to be determined. (2n + 2)!