Past exam of the options I course of the University of Oxford / 2013 / P (Numerical Analysis)

The Lagrange interpolation polynomial isThe distinct nodes make all denominators nonzero. Each Lagrange basis polynomial has degree $n$ and satisfies ${\ell }_j(x_i)={\delta }_{ij}$, so the sum has degree at most $n$ and interpolates every specified value.

If $p$ and $q$ both interpolate the data and have degree at most $n$, the polynomial $r=p-q$ has the $n+1$ distinct roots $x_0,\dots ,x_n$. A nonzero polynomial of degree at most $n$ has at most $n$ roots: repeated use of the factor theorem would otherwise make a product of $n+1$ linear factors divide it. Hence $r=0$, proving the interpolating polynomial is unique.

Integrate the Lagrange interpolation polynomial and exchange the integral with the finite sum:Therefore the interpolatory quadrature weights areThe resulting quadrature rule is exact for every polynomial of degree at most $n$, since its interpolant is itself. For a general continuous $f$, replacing $f$ by its interpolant supplies the approximation.

The first pivot is two. Gaussian elimination without partial pivoting uses $R_2\leftarrow R_2-2R_1$ and $R_3\leftarrow R_3-4R_1$, givingThe second pivot is one; $R_3\leftarrow R_3-3R_2$ gives the upper triangular matrixBoth pivots used for division are nonzero, so no row exchange is needed.

The elimination multipliers are $m_{21}=2$, $m_{31}=4$, and $m_{32}=3$. The unit lower triangular matrix in the LU factorization is thereforeDirect multiplication checksThe positive signs in $L$ undo the row subtractions used during Gaussian elimination.

Take the invertible matrix $A=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$, whose determinant is $-1$. Suppose it had an LU factorization with any lower triangular $L$ and upper triangular $U$:The $(1,2)$ entry gives ${\ell }_{11}{u}_{12}=1$, so ${\ell }_{11}\ne 0$. The $(1,1)$ entry gives ${\ell }_{11}{u}_{11}=0$, so $u_{11}=0$. But then the $(2,1)$ entry would be ${\ell }_{21}{u}_{11}=0$, contradicting $a_{21}=1$. Thus this nonsingular matrix has no unpermuted LU factorization, even without imposing a unit diagonal on $L$. A row permutation resolves the zero pivot, explaining the role of partial pivoting.