\documentclass[a4paper]{article}

\def\npart{IB}

\def\ntitle{Numerical Analysis}
\def\nlecturer{<NAME>}

\def\nterm{Lent}
\def\nyear{2018}

\input{header}

\usepackage[boxed]{algorithm2e}

\newcommand*{\inner}{\innerproduct}

% TODO
% add blank matrices

\begin{document}

\input{titlepage}

\tableofcontents

\setcounter{section}{-1}

\section{Introduction}

Numerical analysis is the study of \emph{algorithms} for continuous mathematics. Examples of problems in continuous mathematics are:
\begin{itemize}
\item solve \(f(x) = 0\) where \(f: \R^n \to \R\),
\item solve \(\frac{dx}{dt} = f(x)\) where \(f: \R^n \to \R^n\)
\item optimisation: find \(\min f(x)\) where \(x \in \R^n, f: \R^n \to \R\).
\end{itemize}

A note on complexity: we measure the complexity of an algorithm by the number of \emph{elementary operations} (\(+, \times, -, /\)) it needs.

Big \(O\) notation: for example \(O(n), O(n^2)\), where \(n\) is input size. We also have complexity \(O(f(n))\) if the number of operations is at most \(cf(n)\) where \(c > 0\).

\section{Polynomial Interpolations}

Denote a degree \(n\) polynomial by
\[
  p(x) = p_0 + p_1x + \dots + p_nx^n
\]
and let \(P_n[x]\) be the vector space of polynomials of degree at most \(n\). The interpolation problem is, given \(x_0, x_1, \dots, x_n \in \R\) and \(f_0, f_1, \dots, f_n \in \R\), find \(p \in P_n[x]\) such that \(p(x_i) = f_i\) for \(i = 0, \dots, n\).

\subsection{Lagrange formula}\index{Lagrange formula}

Claim that
\[
  p(x) = \sum_{k = 0}^{n} f_k \underbrace{\prod_{\ell \neq k}^{ } \frac{x - x_\ell}{x_k - x_\ell}}_{L_k(x)}
\]
solves the problem.

Note that \(L_k(x_j) = \begin{cases} 1 & j = k \\ 0 &j \neq k \end{cases}\) and the result easily follows.

Now we prove the uniqueness of the solution. Assume \(q \in P_n[x]\) is another polynomial that interpolates the data. Then \(p - q\) has \(n + 1\) zeros. But a non-zero polynomial in \(P_n[x]\) has at most \(n\) zeros. Thus \(p - q\) must be zero.

This is an easy solution but what is its complexity? For each \(k\), the complexity of evaluating \(L_k(x)\) is \(O(n)\) so the total complexity of evaluating \(p(x)\) is \(O(n^2)\).

\subsubsection{Error of polynomial interpolation}

Let \(C^s[a, b]\) be the space of functions \([a, b] \to \R\) that are \(s\) times continuously differentiable.

\begin{theorem}
  Let \(f \in C^{n + 1}[a, b]\) and let \(p \in P_n[x]\) interpolate \(f\) at distinct \(x_0, \dots x_n\) , i.e.\ \(p(x_i) = f(x_i)\) for \(i = 0, \dots, n\). Then for all \(x \in [a, b]\), there exists \(\xi \in [a, b]\) such that
  \[
    f(x) - p(x) = \frac{1}{(n + 1)!} f^{(n + 1)}(\xi) \prod_{i = 0}^n (x - x_i).
  \]
\end{theorem}

The last term \(\prod_{i = 0}^n (x - x_i)\) is called the \emph{nodal polynomial}.

\begin{proof}
  If \(x = x_i\) for some \(i\) then the result is trivially true. Assume \(x\) is distinct from \(x_i\)'s for all \(i\). Define
  \[
    \varphi(t) = f(t) - \left(p(t) + (f(x) - p(x)) \prod_{i = 0}^n \frac{t - x_i}{x - x_i} \right).
  \]
  Note that the second term is by construction the interpolating polynomial of \(f\) at \(x_0, \dots, x_n\) and \(x\). Thus
  \[
    \varphi(x_0) = \varphi(x_1) = \dots = \varphi(x_n) = \varphi(x) = 0
  \]
  so \(\varphi\) has \(n + 2\) zeros. Recall from IA Analysis I Rolle's Theorem: if \(g \in C^1[a, b]\) such that \(g(a) = g(b)\) then there exists \(\alpha \in (a, b)\) such that \(g'(\alpha) = 0\). Apply it to \(\varphi\), we deduce that \(\varphi'\) has \(n + 1\) zeros. Inductively we find that \(\varphi^{(n + 1)}\) has \(1\) zero, i.e.\ there exists \(\xi \in [a, b]\) such that \(\varphi^{(n + 1)}(\xi) = 0\). Thus
  \[
    0 = \varphi^{(n + 1)}(\xi) = f^{(n + 1)}(\xi) - \left( \underbrace{p^{(n + 1)}(\xi)}_{= 0} + (f(x) - p(x)) \frac{(n + 1)!}{\prod_{i = 0}^n(x - x_i)} \right).
  \]
  Rearrange,
  \[
    f(x) - p(x) = \frac{1}{(n + 1)!}f^{(n + 1)}(\xi) \prod_{i = 0}^n(x - x_i).
  \]
\end{proof}

\begin{eg}
  \([a, b] = [-5, 5]\), \(x_j = -5 + 10 \frac{j}{n}\) for \(j = 0, \dots, n\). Plot \(\prod_{i = 0}^n(x - x_i)\), we note that it vanishes at \(x_i\)'s but blows up near the endpoints.
\end{eg}

This is called \emph{Runge's phenomenon}. If one attempts to interpolate \(f(x) = \frac{1}{1 + x^2}\) using equispaced points on \([-5, 5]\) and plots the error \(f(x) - p(x)|\).

Thus equispaced points may not be the most suitable to minimise the error. The remedy is to look for points \(x_0, \dots, x_n\) such that \(|\prod_{i = 0}^n(x - x_i)|\) is small. This leads us to \emph{Chebyshev points}. For example in the previous case we should choose
\[
  x_j = 5 \cos \frac{(n - j)\pi}{n}.
\]
This choice of points is the one that minimises
\[
  \max_{x \in [a, b]} \left| \prod_{i =0}^n(x - x_i) \right|.
\]

\subsection{Divided difference and Newton's interpolation formula}

\begin{definition}[Divided difference]\index{divided difference}
  Given pairwise distinct points \(x_0, \dots, x_n\), let \(p \in P_n[x]\) interpolate \(f \in C[a, b]\) at these points. The coefficient of \(x^n\) in \(p\) is called the \emph{divided difference} of \(f\) at \((x_0, \dots, x_n)\) and is denoted \(f[x_0, \dots, x_n]\).
\end{definition}

We know from the last lecture that the interpolent is
\[
  p(x) = \sum_{k = 0}^n f(x_k) \prod_{\ell \neq k} \frac{x - x_\ell}{x_k - x_\ell}.
\]
Thus we get
\[
  f[x_0, \dots, x_n] = \sum_{k = 0}^n f(x_k) \prod_{\ell \neq k} \frac{1}{x_k - x_\ell}.
\]

The next example illustrates the reason behind the name ``divided difference''.

\begin{eg}\leavevmode
  \begin{itemize}
  \item \(f[x_0] = f(x_0)\).
  \item \(f[x_0, x_1] = f(x_0)\frac{1}{x_0 - x_1} + f(x_1)\frac{1}{x_1 - x_0} = \frac{f(x_1) - f(x_0)}{x_1 - x_0}\).
  \end{itemize}
\end{eg}

This observation is generalised by

\begin{theorem}
  \[
    f[x_0, x_1, \dots, x_{n + 1}] = \frac{f[x_1, \dots, x_{n + 1}] - f[x_0, \dots, x_n]}{x_{n + 1} - x_0}.
  \]
\end{theorem}

\begin{proof}
  Let \(p \in P_n[x]\) interpolate \(f\) at \(x_0, \dots, x_n\) and \(q \in P_n[x]\) interpolate \(f\) at \(x_1, \dots, x_{n + 1}\) and let
  \[
    r(x) = \frac{x - x_{n + 1}}{x_0 - x_{n + 1}}p(x) + \frac{x - x_0}{x_{n + 1} - x_0}q(x) \in P_{n + 1}[x].
  \]
  Observe that \(r\) interpolates \(f\) at \(x_0, \dots, x_{n + 1}\). So the divided difference, i.e.\ coefficient of \(x^{n + 1}\) in \(r(x)\) is
  \[
    \frac{1}{x_0 - x_{n + 1}}f[x_0, \dots, x_n] + \frac{1}{x_{n + 1} - x_0}f[x_1, \dots, x_{n + 1}].
  \]
\end{proof}

\begin{theorem}
  Assume \(x_0, \dots, x_n\) are pairwise distinct in \([a, b]\) and \(f \in C^n[a, b]\), then there exists \(\xi \in [a, b]\) such that
  \[
    f[x_0, \dots, x_n] = \frac{1}{n!}f^{(n)}(\xi).
  \]
\end{theorem}

\begin{proof}
  Let \(p \in P_n[x]\) interpolate \(f\) at \(x_0, \dots, x_n\). Then function \(f - p\) has \(n + 1\) zeros in \([a, b]\). Applying Rolle's Theorem \(n\) times, we get that \((f - p)^{(n)}\) has at least one zero in \([a, b]\). Let \(\xi \in [a, b]\) be such that \(f^{(n)}(\xi) - p^{(n)}(\xi) = 0\). As \(p\) has degree \(n\), \(p^{(n)}(x) = n! \cdot \text{ leading coefficient}\). The result thus follows.
\end{proof}

\begin{theorem}[Newton's interpolation formula]\index{Newton's formula}
  Let \(x_0, \dots, x_n\) be pairwise distinct and let
  \[
    p(x) = f[x_0] + f[x_0, x_1](x - x_0) + \dots + f[x_0, \dots, x_n]\prod_{i = 0}^{n - 1}(x - x_i).
  \]
  Then \(p(x_i) = f(x_i)\) for \(i = 0, \dots, n\).
\end{theorem}

\begin{proof}
  Induction on \(n\). If \(n = 0\) then \(p(x) = f[x_0]\) which trivially satisfies \(p(x_0) = f[x_0] = f(x_0)\).

  Suppose it holds for \(n - 1\). Let \(p_n \in P_{n - 1}[x]\) interpolate \(f\) at \(x_0, \dots, x_{n - 1}\) and \(p \in P_n[x]\) interpolate \(f\) at \(x_0, \dots, x_{n - 1}, x_n\). \(p - p_n\) is a polynomial of degree \(n\) that vanishes at \(x_0, \dots, x_{n - 1}\), implying that
  \[
    p - p_n = \alpha \prod_{i = 0}^{n - 1}(x - x_i).
  \]
  But \(\alpha\) is the coefficient of \(x^n\) in \(p\) and so we must have \(\alpha = f[x_0, \dots, x_n]\). Thus we deduce that
  \[
    p = p_n + f[x_0, \dots, x_n] \prod_{i = 0}^{n - 1}(x - x_i).
  \]
  By using induction hypothesis, the result follows.
\end{proof}

\subsubsection{Evaluating Newton's interpolating formula}

Recall that the divided difference is defined recursively by
\[
  f[x_0, x_1, \dots, x_{n + 1}] = \frac{f[x_1, \dots, x_{n + 1}] - f[x_0, \dots, x_n]}{x_{n + 1} - x_0}.
\]
We can draw a table to evaluate them:
\[
  \begin{tikzcd}[column sep=tiny, row sep=tiny]
    f[x_0] \ar[dr] \\
    & f[x_0, x_1] \ar[dr] \\
    f[x_1] \ar[ur] & & \cdots \ar[dr] \\
    \vdots & & & f[x_0, \dots, x_n] \\
    f[x_{n - 1}] \ar[dr] & & \cdots \ar[ur] \\
    & f[x_{n - 1}, x_n] \ar[ur] \\
    f[x_n] \ar[ur]
  \end{tikzcd}
\]

The output of this procedure is \(f[x_j, x_{j + 1}, \dots, x_\ell]\) for all \(0 \leq j \leq \ell \leq n\). To evaluate a new divided difference requires 3 operations (2 substractions and 1 division) so the complexity is
\[
  3(n - 1) + 3(n - 2) + \dots + 3 \approx 3 \cdot \frac{n^2}{2} \sim O(n^2).
\]

Having obtained the divided differences, we can use Horner's scheme to evaluate Newton's formula in \(O(n)\). Note that the term \((x - x_0)\), for example, appears in every term except the first one in Newton's interpolating formula so we may group them together
\begin{align*}
  p(x) &= f[x_0] + (x - x_0) (f[x_0, x_1] + (x - x_1)(f[x_0, x_1, x_2] + \cdots \\
       &+ (x - x_{n - 1})f[x_0, x_1, \dots, x_n])).
\end{align*}
This way the evaluation requires \(O(n)\) operations.

\section{Orthogonal Polynomials}

\subsection{Definitions}

\begin{definition}[Inner product]\index{inner product}
  An \emph{inner product} is a function \(\inner{\cdot, \cdot}: V \times V \to \R\) where \(V\) is a real vector space which is
  \begin{enumerate}
  \item symmetric: for all \(x, y \in V\), \(\inner{x, y} = \inner{y, x}\),
  \item positive-definite: for all \(x \in V\), \(\inner{x, x} \geq 0\) with equality if and only if \(x = 0\),
  \item linear: for all \(x, y, z \in V\), \(a, b \in \R\), \(\inner{ax + by, z} = a\inner{x, z} + b\inner{y, z}\).
  \end{enumerate}
\end{definition}

\begin{definition}[Orthogonality]
  Given an inner product, \(x, y \in V\) are \emph{orthogonal} if \(\inner{x, y} = 0\).
\end{definition}

In this section, let \(V = C[a, b]\) and let \(w \in V\) be a positive function and define an inner product
\[
  \inner{f, g} = \int_a^b w(x)f(x)g(x) dx.
\]
It is easy to verify the axioms of inner product.

\begin{definition}[Orthogonal polynomial]\index{orthogonal polynomial}
  Given an inner product in \(V = P[x]\), the \emph{orthogonal polynomials} are a sequence of polynomials \(p_0, p_1, \dots\) such that
  \begin{enumerate}
  \item \(\deg p_n = n\) for all \(n \geq 0\) and
  \item \(\inner{p_n, p_m} = 0\) for all \(n \neq m\).
  \end{enumerate}
\end{definition}

\begin{remark}
  For any \(n \geq 0\), \(\{p_0, \dots, p_n\}\) is an orthogonal basis of \(P_n[x]\).
\end{remark}

The next theorem shows that this object with the desired property does exist:

\begin{theorem}
  For every \(n \geq 0\) there exists a unique monic orthogonal polynomial \(p_n\) of degree \(n\).
\end{theorem}

\begin{proof}
  Let \(p_0(x) = 1\) and proceed by induction on \(n\). Suppose \(p_0, \dots, p_n\) satisfy the induction hypothesis. To define \(p_{n + 1}\) let \(q(x) = x^{n + 1} \in P_{n + 1}[x]\) and conduct Gram-Schmidt on \(q(x)\):
  \[
    p_{n + 1}(x) = q(x) - \sum_{k = 0}^n \frac{\inner{q, p_k}}{\inner{p_k, p_k}}p_k(x).
  \]
  Clearly \(p_{n + 1} \in P_{n + 1}[x]\) and is monic. The orthogonality is a consequence of Gram-Schmidt.

  To prove uniqueness, suppose there exists \(\tilde p_{n + 1} \in P_{n + 1}[x]\) also monic orthogonal. Then \(p = p_{n + 1} - \tilde p_{n + 1} \in P_n[x]\) and thus we have
  \[
    0 = \inner{p_{n + 1}, p} - \inner{\tilde p_{n + 1}, p} = \inner{p, p}
  \]
  so \(p = 0\).
\end{proof}

\begin{eg}[Legendre polynomials]\index{orthogonal polynomial!Legendre}
  Define an inner product
  \[
    \inner{f, g} = \int_{-1}^1 f(x)g(x) dx
  \]
  for \(f, g \in P[x]\). The orthogonal polynomials arising from the scalar product is called \emph{Legendre polynomials}. The first few terms in the sequence are
  \begin{align*}
    p_0(x) &= 1 \\
    p_1(x) &= x \\
    p_2(x) &= x^2 - \frac{1}{3} \\
    p_3(x) &= x^3 - \frac{3}{5}x \\
    f_4(x) &= x^4 - \frac{30}{35}x^2 + \frac{3}{35}
  \end{align*}
\end{eg}

Some well-known examples of orthogonal polynomials:
\begin{table}[h!]
  \centering
  \begin{tabular}{|c||c|c|c|}
    \hline
    Name & Notation & \([a, b]\) & \(w(x)\) \\ \hline
    Legendre & \(P_n\) & \([-1, 1]\) & \(1\) \\ \hline
    Chebyshev & \(T_n\) & \([-1, 1]\) & \((1 - x^2)^{-1/2}\) \\ \hline
    Laguerre & \(L_n\) & \([0, \infty)\) & \(e^{-x}\) \\ \hline
    Hermite & \(H_n\) & \((-\infty, \infty)\) & \(e^{-x^2}\) \\ \hline
  \end{tabular}
  \caption{Common orthogonal polynomials}
\end{table}

\subsection{Three-term recurrence relation}

Gram-Schmidt gives us a way to construct orthogonal polynomials, but it suffers from loss of accuracy due to imprecisions in the calculation of scalar products. A considerably better procedure follows from our next theorem, which relies on the mild assumption that the inner product satisfies
\[
  \inner{xp, q} = \inner{p, xq}
\]
for all \(p, q \in P[x]\).

\begin{theorem}
  Assume the scalar product on \(P[x]\) satisfies \(\inner{xp, q} = \inner{p, xq}\) for all \(p, q \in P[x]\). The orthogonal polynomials are given by
  \begin{align*}
    p_{-1}(x) &= 0 \\
    p_{0}(x) &= 1 \\
    p_{n + 1}(x) &= (x - \alpha_n)p_n(x) - \beta_np_{n - 1}(x),\, n \geq 0
  \end{align*}
  where
  \begin{align*}
    \alpha_n &= \frac{\inner{p_n, xp_n}}{\inner{p_n, p_n}} \\
    \beta_n &= \frac{\inner{p_n, p_n}}{\inner{p_{n - 1}, p_{n - 1}}}
  \end{align*}
\end{theorem}

\begin{proof}
  Let \(n \geq 0\) and \(\psi(x) = p_{n + 1}(x) - (x - \alpha_n)p_n(x) + \beta_np_{n - 1}(x)\). Since \(p_n\) and \(p_{n + 1}\) are monic, it follows that \(\psi \in P_n[x]\). Moreover, because of orthogonality of \(p_{n - 1}, p_n, p_{n + 1}\),
  \[
    \inner{\psi, p_\ell} = 0
  \]
  for \(\ell = 0, \dots, n - 2\) by linearity. Because of monicity, \(q = xp_{n - 1} - p_n \in P_{n - 1}[x]\). Thus from the definition of \(\alpha_n\) and \(\beta_n\),
  \begin{align*}
    \inner{\psi, p_{n - 1}} &= -\inner{p_n, xp_{n - 1}} + \beta_n\inner{p_{n - 1}, p_{n - 1}} = -\inner{p_n, p_n} + \beta_n\inner{p_{n - 1}, p_{n - 1}} = 0 \\
    \inner{\psi, p_n} &= -\inner{xp_n, p_n} + \alpha_n\inner{p_n, p_n} = 0
  \end{align*}
  Every \(p \in P_n[x]\) that obeys \(\inner{p, p_\ell} = 0\) for all \(0 \leq \ell \leq n\) must necessarily be the zero polynomials. Thus \(\psi = 0\) and the result follows.
\end{proof}

\begin{eg}[Chebyshev polynomials]\index{orthogonal polynomial!Chebyshev}
  Define an inner product on \(C[-1, 1]\)
  \[
    \inner{f, g} = \int_{-1}^1 \frac{f(x)g(x)}{\sqrt{1 - x^2}} dx
  \]
  and define
  \begin{align*}
    T_n &\in P_n[x] \\
    T_n(\cos\theta) &= \cos(n\theta)
  \end{align*}
  The first three terms are thus
  \begin{align*}
    T_0(x) &= 1 \\
    T_1(x) &= x \\
    T_2(x) &= 2x^2 - 1
  \end{align*}
  The inner product can be easily found by a change of vairable:
  \begin{align*}
    \inner{T_n, T_m}
    &= \int_{-1}^1 \frac{T_n(x)T_m(x)}{\sqrt{1 - x^2}} dx \\
    &= \int_0^\pi \cos n\theta \cos m\theta d\theta \\
    &= \frac{1}{2} \int_0^\pi (\cos (n + m)\theta + \cos (n - m)\theta) d\theta \\
    &= 0
  \end{align*}
  whenever \(n \neq m\).

  The recurrence relation for Chebyshev polynomials is particularly simple:
  \[
    T_{n + 1}(x) = 2xT_n(x) - T_{n - 1}(x)
  \]
  which can be verified at once from the identity
  \[
    \cos(n + 1)\theta + \cos(n - 1)\theta = 2\cos \theta \cos (n\theta).
  \]
  Note that \(T_n\)'s are not monic. To obtain monic polynomials take \(T_n/2^{n - 1}\) for \(n \geq 1\).
\end{eg}


\subsection{Least-squares polynomial fitting}

\begin{question}
Fix a scalar product on \(C[a, b]\) of the form
\[
  \inner{f, g} = \int_a^b w(x)f(x)g(x) dx
\]
where \(w: [a, b] \to \R\) is positive. Given \(f \in C[a, b]\), find \(p \in P_n[x]\) such that
  \[
    \norm{f - p}^2 = \inner{f - p, f - p}
  \]
  is minimised.
\end{question}

Let \(\hat p_n\) be the polynomial of degree \(n\) minimising \(\norm{f - p}^2\).

\begin{theorem}
  Let \(p_0, p_1, p_2\) be orthogonal polynomials with respect to \(\inner{\cdot, \cdot}\). Then
  \[
    \hat p_n = \sum_{k = 0}^n \frac{\inner{f, p_k}}{\inner{p_k, p_k}} p_k.
  \]
\end{theorem}

\begin{proof}
  We know that any \(p \in P_n[x]\) can be written as
  \[
    p = \sum_{i = 0}^n c_kp_k
  \]
  where \(c_0, \dots, c_n \in \R\). Then
  \begin{align*}
    \inner{f - p, f - p} &= \inner*{f - \sum_{k = 0}^n c_kp_k, f - \sum_{k = 0}^n c_kp_k} \\
                         &= \inner{f, f} - 2\inner*{f, \sum_{k = 0}^n c_kp_k} + \inner*{\sum_{k = 0}^n c_kp_k, \sum_{k = 0}^n c_kp_k} \\
                         &= \inner{f, f} - 2\inner*{f, \sum_{k = 0}^n c_kp_k} + \sum_{k = 0}^n \sum_{k' = 0}^n c_kc_{k'}\underbrace{\inner{p_k, p_k}}_{= 0 \text{ if } k \neq k'} \\
                         &= \inner{f, f} - 2\inner*{f, \sum_{k = 0}^n c_kp_k} + \sum_{k = 0}^n c_k^2 \inner{p_k, p_k}
  \end{align*}
  As usual, to minimise the quantity we take derivative with respect to \(c_i\)'s:
  \[
    \frac{\p}{\p c_k} \inner{f - p, f - p} = -2 \inner{f, p_k}  + 2c_k \inner{p_k, p_k}.
  \]
  Set the derivative to \(0\), we get
  \[
    c_k = \frac{\inner{f, p_k}}{\inner{p_k, p_k}}.
  \]
\end{proof}

In this case, the minimal error is
\[
  \norm{f - \hat p_n}^2 = \inner{f - \hat p_n, f - \hat p_n} = \inner{f, f} - \sum_{k = 0}^n \frac{\inner{f, p_k}^2}{\inner{p_k, p_k}} = \inner{f, f} - \inner{\hat p_n, \hat p_n}.
\]
The can be interpreted as the generalised Pythagoras Theorem for inner product spaces.

It is obvious that \(\norm{f - \hat p_n}^2\) is a non-increasing function of \(n\), but
\begin{question}
  Does \(\norm{f - \hat p_n}^2 \to 0\) as \(n \to \infty\)?
\end{question}

The answer is yes and can be proved using Weierstrass theorem, which we state without giving a proof:

\begin{theorem}[Weierstrass]
  Let \(f \in C[a, b]\) where \([a, b]\) is bounded. For all \(\varepsilon > 0\), there exists a polynomial \(p\) of high enough degree such that
  \[
    |f(x) - p(x)| < \varepsilon
  \]
  for all \(x \in [a, b]\).
\end{theorem}

Using Weierstrass theorem, we can prove the claim above. For any \(p\) we have
\[
  \norm{f - p}^2 = \int_a^b w(x)(f(x) - p(x))^2 dx \leq \left(\max_{x \in [a, b]} |f(x) - p(x)| \right)^2 \int_a^b w(x) d(x).
\]
Give any \(\delta > 0\), by Weierstrass theorem applied with \(\varphi = \sqrt{\delta/\int_a^b w(x) dx}\), there is a polynomial \(p\) of degree \(N\) such that
\[
  |f(x) - p(x)| < \varepsilon
\]
for all \(x \in [a, b]\). Then for any \(N \geq n\),
\[
  \norm{f - \hat p_N}^2 \leq \norm{f - p}^2 \leq \varepsilon^2 \int_a^b w(x) dx = \delta
\]
as required.

\begin{theorem}[Parseval identity]\index{Parseval identity}
  \[
    \sum_{k = 0}^\infty \frac{\inner{f, p_k}^2}{\inner{p_k, p_k}} = \inner{f, f}.
  \]
\end{theorem}

\begin{proof}
  Reformulation of the above claim.
\end{proof}

\subsection{Least-squares fitting to discrete data}

Given the value of a function at pairwise distinct points \(x_1, \dots, x_m\), the goal of this section is to find \(p \in P_n[x]\) that minimises
\[
  \sum_{k = 1}^m (f(x_k) - p(x_k))^2.
\]
This can be thought as a generalisation of the interpolation problem, where \(m = n + 1\) and the minimised error is always \(0\). In the generalised setting, \(n \leq m - 1\) (and usually much smaller).

This question can be reformulated as in terms of orthogonal polynomial, where the inner product is defined to be
\[
  \inner{g, h} = \sum_{k = 1}^m g(x_k)h(x_k)
\]
since then
\[
  \inner{f - p, f - p} = \sum_{k = 0}^n (f(x_k) - p(x_k))^2.
\]

We can proceed as follow, given \(n \leq m - 1\):
\begin{enumerate}
\item use three-term recurrence for the inner product to compute orthogonal polynomials \(p_0, \dots, p_n\).
\item Form
  \[
    \hat p_n = \sum_{k = 0}^n \frac{\inner{f, p_k}}{\inner{p_k, p_k}}p_k.
  \]
\end{enumerate}
The reason we require \(n \leq m - 1\) is for positive definiteness.

\subsection{Gaussian quadrature}

\begin{question}
  Let \(w: [a, b] \to \R\) be positive. We want to approximate the integral \(\int_a^b w(x)f(x) dx\) where \(f \in C[a, b]\).
\end{question}
A \emph{quadrature formula}\index{quadrature} is an approximation of the above expression
\begin{equation}
  \label{eqn:quadrature}
  \int_a^b w(x)f(x) dx \approx \sum_{k = 1}^\nu b_kf(c_k)
  \tag{\(\ast\)}
\end{equation}
where \(b_k\) are \emph{weights} and \(c_k\) are \emph{nodes}.

We require the quadrature formula to be exact for \(f \in P_n[x]\).

Claim that if the quadrature formula \eqref{eqn:quadrature} is exact for any \(f \in P_n[x]\) then necessarily \(n \leq 2\nu - 1\).

\begin{proof}
  We will construct a polynomial of degree \(2\nu\) such that LHS and RHS are different. Let
  \[
    f(x) = \prod_{k = 1}^\nu (x - c_k)^2
  \]
  which has degree \(2\nu\). RHS is equal to \(0\) while LHS is \(\int_a^b w(x)f(x)dx > 0\).
\end{proof}

Can we find a quadrature formula that is exact for all polynomials of degree \(\leq 2\nu - 1\)? Yes, and this is \emph{Gaussian quadrature}\index{quadrature!Gaussian}.

Let
\[
  \inner{f, g} = \int_a^b w(x)f(x)g(x) dx
\]
and let \(p_0, p_1, p_2\) be orthogonal polynomials associated to this inner product.

\begin{theorem}
  For any \(n \geq 0\), \(p_n\) has \(n\) real distinct roots in \([a, b]\).
\end{theorem}

\begin{proof}
  Let \(\xi_1, \dots, \xi_m \in (a, b)\) be the points where \(p_n\) changes sign and let
  \[
    q(x) = \prod_{i = 1}^m (x - \xi_i).
  \]
  Note that \(p_n(x)q(x)\) has constant sign in \([a, b]\), i.e.\ in this step we make every root have even multiplicity. Since \(p_nq\) has constant sign on \([a, b]\),
  \[
    |\inner{p_n, q}| = \left| \int_a^b w(x)p_n(x)q(x) dx \right| = \int_a^b w(x) |p_n(x)q(x)| dx > 0
  \]
  This implies that \(\deg q \geq n\) so \(m \geq n\). But \(m \leq n\) because \(p_n\) has degree \(n\). Thus \(p_n\) has \(n\) distinct real roots in \((a, b)\).
\end{proof}

Given nodes \(c_1, \dots, c_\nu\), define the \emph{interpolatory weights}\index{interpolatory weights}
\begin{equation}
  \label{eqn:weight}
  b_k = \int_a^b w(x) \prod_{j = 1, j \neq k}^\nu \frac{x - c_j}{c_k - c_j} dx
  \tag{\(\ast\ast\)}
\end{equation}
for \(k = 1, \dots, \nu\).

\begin{theorem}\leavevmode
  \begin{enumerate}
  \item The quadrature formula with weights given by \eqref{eqn:weight} is exact for polynomials of degree up to \(\nu - 1\).
  \item If furthermore the \(c_k\)'s are the roots of \(p_\nu\), then the quadrature formula is exact for polynomials up to degree \(2\nu - 1\).
  \end{enumerate}
\end{theorem}

\begin{proof}\leavevmode
  \begin{enumerate}
  \item Let \(f \in P_{\nu - 1}[x]\). Write \(f\) in terms of its interpolating formula at the \(c_k\)'s,
    \[
      f(x) = \sum_{k = 1}^\nu f(c_k) \prod_{j \neq k} \frac{x - c_j}{c_k - c_j}.
    \]
    Then
    \begin{align*}
      \int_a^b w(x)f(x) dx &= \int_a^b w(x) \sum_{k = 1}^\nu f(c_k) \prod_{j \neq k} \frac{x - c_j}{c_k - c_j} dx \\
                           &= \sum_{k = 1}^\nu f(c_k) \int_a^b w(x) \prod_{j \neq k} \frac{x - c_j}{c_k - c_j} dx
    \end{align*}
  \item Assume now that \(c_1, \dots, c_\nu\) are the roots of \(p_\nu\). Let \(f \in P_{2\nu - 1}[x]\). We can write
    \[
      f = p_\nu q + r
    \]
    with \(\deg r \leq \nu - 1, \deg q \leq \nu - 1\). Then
    \begin{align*}
      \int_a^b w(x)f(x) dx &= \int_a^b w(x)p_\nu(x) q(x) dx + \int_a^b w(x)r(x) dx \\
                           &= \inner{p_\nu, q} + \sum_{k = 1}^\nu b_k r(c_k) \\
                           &= 0 + \sum_{k = 1}^\nu b_kf(c_k)
    \end{align*}
  \end{enumerate}
\end{proof}

\subsection{Peano Kernel Theorem}

How does the error behave when we use the quadrature formula to approximate a function that is not a polynomial, or a polynomial of higher degree?

The error from a quadrature formula is
\[
  L(f) = \int_a^b w(x)f(x) dx - \sum_{k = 1}^\nu b_kf(c_k)
\]
Assume \(L(f) = 0\) for all \(f \in P_n[x]\). The goal is to bound error \(|L(f)|\) for \(f \in C^{n + 1}[a, b]\). Recall from IA Analysis I the Taylor expansion formula with integral remainder
\[
  f(x) = \sum_{i = 0}^n f^{(i)}(a) \frac{(x - a)^i}{i!} + \frac{1}{n!} \int_a^x (x - \theta)^n f^{(n + 1)}(\theta) d\theta.
\]
Call the first part \(g(x)\). Since \(g \in P_n[x]\), \(L(g) = 0\). Thus by linearity of \(L\) we get
\[
  L(f) = L\left( x \mapsto \frac{1}{n!} \int_a^x (x - \theta)^n f^{(n + 1)}(\theta) d\theta \right).
\]
Let
\[
  (x - \theta)_+^n =
  \begin{cases}
    (x - \theta)^n & \text{if } \theta \leq x \\
    0 & \text{otherwise}
  \end{cases}
\]
Then
\begin{align*}
  \int_a^x (x - \theta)^n f^{(n + 1)}(\theta) d\theta & = \int_a^b 𝟙_{\theta \leq x} (x - \theta)^n f^{(n + 1)}(\theta) d\theta \\
                                                      &= \int_a^b (x - \theta)_+^n f^{(n + 1)}(\theta) d\theta
\end{align*}
Assuming we can exchange \(L\) and the integral, we get
\[
  L(f) = \frac{1}{n!} \int_a^b K(\theta)f^{(n + 1)}(\theta) dx
\]
where
\[
  K(\theta) = L(x \mapsto (x - \theta)_+^n)
\]
is the \emph{Peano kernel}\index{Peano kernel}.

\begin{eg}[Simpson's rule]
  \[
    \int_{-1}^1 f(x)dx \approx \frac{1}{3} [f(-1) + 4f(0) + f(1)].
  \]
  Then
  \[
    L(f) = \int_{-1}^1 f(x)dx - \frac{1}{3}[f(-1) + 4f(0) + f(1)].
  \]
  We can check that \(L(f) = 0\) for all \(f \in P_2[x]\). The Peano kernel for \(L\) is
  \[
    K(\theta) = L(x \mapsto (x - \theta)_+^2) =
    \begin{cases}
      -\frac{1}{3}\theta(1 + \theta)^2 & \text{if } -1 \leq \theta \leq 0 \\
      -\frac{1}{3}\theta(1 - \theta)^2 & \text{if } 0 \leq \theta \leq 0 \\
      0 & \text{otherwise}
    \end{cases}
  \]
  Assume \(0 \leq \theta \leq 1\) for example,
  \begin{align*}
    K(\theta)
    &= L(x \mapsto (x - \theta)_+^2) \\
    &= \int_{-1}^1 (x - \theta)_+^2 dx - \frac{1}{3} \left[(-1 - \theta)_+^2 + 4(0 - \theta)_+^2 + (1 - \theta)_+^2 \right] \\
    &= \int_\theta^1 (x - \theta)^2 dx - \frac{1}{3}[0 + 0 + (1 - \theta)^2] \\
    &= \frac{(x - \theta)^3}{3}\Big|_0^1 - \frac{1}{3}(1 - \theta)^2 \\
    &= -\frac{1}{3}\theta(1 - \theta)^2
  \end{align*}
  For any \(f \in C^3[-1, 1]\),
  \begin{align*}
    |L(f)| &= \frac{1}{2}\left| \int_{-1}^1 K(\theta)f^{(3)}(\theta)d\theta \right| \\
           &\leq \frac{1}{2} \max_{\theta \in [-1, 1]} |f^{(3)}(\theta)| \int_{-1}^1|K(\theta)| d\theta \\
           &\leq \frac{1}{36} \norm{f^{(3)}(\theta)}_\infty
  \end{align*}

  In particular, applying the result to \(P_2[x]\) tells us that the quadrature is exact for polynomials of degree \(2\) or smaller.
\end{eg}

In fact Peano Kernel Theorem applies to other kind of numerical algorithms as well.

\begin{eg}[Numerical differentiation]
  \[
    f'(0) \approx -\frac{3}{2}f(0) + 2f(1) - \frac{1}{2}f(2).
  \]
  We can check that the formula is exact for \(f(x) = 1, x, x^2\) so by linearity this extends to all elements of \(P_2[x]\). The error is
  \[
    L(f) = f'(0) - [-\frac{3}{2}f(0) + 2f(1) - \frac{1}{2}f(2)]
  \]
  so
  \[
    K(\theta) = L(x \mapsto (x - \theta)_+^2) =
    \begin{cases}
      2\theta - \frac{3}{2}\theta^2 & \text{if } 0 \leq \theta \leq 1 \\
      \frac{1}{2}(2 - \theta)^2 & \text{if } 1 \leq \theta \leq 2 \\
      0 & \text{otherwise}
    \end{cases}
  \]
  For any \(f \in C^3[0, 2]\),
  \begin{align*}
    |L(f)|
    &= \frac{1}{2} \left| \int_0^2 K(\theta)f^{(3)}(0)d\theta d\theta \right| \\
    &\leq \frac{1}{2} \int_0^2 |K(\theta)||f^{(3)}(\theta)|fd\theta \\
    &\leq \frac{1}{2} \norm{f^{(3)}}_\infty \int_0^2 |K(\theta)| d\theta \\
    &\leq \frac{1}{3} \norm{f^{(3)}}_\infty
  \end{align*}
\end{eg}

\section{Ordinary Differential Equations}

Given an ordinary differential equation of the form
\[
  \frac{dy}{dt} = y' = f(t, y),\, y(0) = y_0,\, t \geq 0
\]
where \(f: \R \times \R^N \to \R^N, y \in \R^N\), we want to solve it by compute \(y(t_n)\) where \(t_n = nh\). \(h\) can be thought as the time step.

\subsection{One-step methods}

A \emph{one-step method} is defined as a map
\[
  y_{n + 1} = \varphi_h(t_n, y_n)
\]
where \(y_n\) is our approximation for \(y(nh)\). The map only depends on one previous value, ergo the name.

The \emph{Euler method}\index{Euler method} is a one-step method defined by

\[
  y_{n + 1} = y_n + hf(t_n, y_n), n \geq 0.
\]
The ``deviation'' is
\begin{align*}
  y((n + 1)h)
  &= y(nh + h) \\
  &\approx y(nh) + hy'(nh) \\
  &= y_n + hf(t_n, y_n)
\end{align*}

\begin{definition}[Convergence of algorithm]
  We say that a method \emph{converges} if given \(t^* > 0\),
  \[
    \lim_{h \to 0} \max_{0 \leq n \leq \floor{\frac{t^*}{h}}} \norm{y_n(h) - y(nh)} = 0.
  \]
\end{definition}

\begin{theorem}
  Assume \(f\) is Lipschitz in the second argument. Then Euler's method is convergent.
\end{theorem}

\begin{proof}
  Let \(e_n(h) = y_n(h) - y(nh)\). Then
  \begin{align*}
    e_{n + 1}(h)
    &= y_{n + 1}(h) - y((n + 1)h) \\
    &= [y_n(h) + h f(nh, y_n(h))] - [y(nh) + hy'(nh) + \eta(h)] \\
    \intertext{where we Taylor expand the second term and \(\eta(h) \sim O(h^2)\)}
    &= y_n(h) - y(nh) + h[f(nh, y_n(h)) - y'(nh)] - \eta(h) \\
    &= e_n(h) + h[f(nh, y_n(h)) - f(nh, y(nh))] - \eta(h)
  \end{align*}
  Assume the Lipschitz constant is \(\lambda\), we thus get
  \begin{align*}
    \norm{e_{n + 1}(h)}
    &\leq \norm{e_n(h)} + h\lambda \norm{y_n(h) - y(nh)} + \norm{\eta(h)} \\
    &= \norm{e_n(h)}(1 + h\lambda) + Ch^2
  \end{align*}
  Continue recursively,
  \begin{align*}
    \norm{e_n(h)}
    &\leq \norm{e_{n - 1}(h)}(1 + h\lambda) + Ch^2 \\
    &\leq \norm{e_{n - 2}(h)}(1 + h\lambda)^2 + Ch^2(1 + h\lambda) + Ch^2 \\
    &\leq \cdots \\
    &\leq \underbrace{\norm{e_0(h)}}_0 (1 + h\lambda)^n + Ch^2 \sum_{j = 0}^{n - 1} (1 + h\lambda)^j \\
    &= Ch^2 \frac{(1 + h\lambda)^n - 1}{h\lambda} \\
    &= \frac{Ch}{\lambda} [(1 + h\lambda)^n - 1] \\
    \intertext{As \(e^x \geq 1 + x\),}
    &\leq \frac{Ch}{\lambda} (e^{h\lambda n} - 1) \\
    \intertext{Since \(n \leq \frac{t^*}{h}\),}
    &\leq \frac{Ch}{\lambda}(e^{\lambda t^*} - 1) \\
    &\to 0
  \end{align*}
  as \(h \to 0\).
\end{proof}

\subsection{Multistep methods}

An \emph{\(s\)-step method} is defined by a recursion rule
\begin{equation}
  \label{eqn:multi-step}
  \sum_{\ell = 0}^s \rho_\ell y_{n + \ell} = h \sum_{\ell = 0}^s \sigma_\ell f(t_{n + \ell}, y_{n + \ell})
\end{equation}
where \(\rho_s = 1\).

The method is called \emph{explicit} if \(\sigma_s = 0\). Otherwise it is called \emph{implicit}.

For example for Euler's method,
\[
  y_{n + 1} - y_n = hf(t_n, y_n)
\]
\(s = 1, \rho_1 = 1, \rho_0 = -1, \sigma_1 = 0, \sigma_s = 1\).
This is an explicit method.

By constrast, the implicit Euler method is
\[
  y_{n + 1} - y_n = hf(t_{n + 1}, y_{n + 1}).
\]

An example of a \(2\)-step method is \emph{\(2\)-step Adams-Bashforth} defined by
\[
  y_{n + 2} - y_{n + 1} = h \left( \frac{3}{2}f(t_{n + 1}, y_{n + 1}) - \frac{1}{2}f(t_n, y_n) \right)
\]

\begin{definition}[Order]\index{order}
  The \emph{order} of a multistep method is the biggest integer \(p \geq 0\) such that
  \[
    \sum_{\ell = 0}^s \rho_\ell y(t_{n + \ell}) - h \sum_{\ell = 0}^s \sigma_\ell y'(t_{n + \ell}) = O(h^{p + 1})
  \]
  for all sufficiently smooth functions \(y\).
\end{definition}

If we think \(y'(t_{n + \ell}) = f(t_{n + \ell}, y(t_{n + \ell}))\), this is the error of starting at the previous iteration, i.e.\ the ``local error''.

Now we calculate the order of Euler method.
\begin{align*}
  y(t_{n + 1}) - y(t_n) - hy'(t_n)
  &= y(t_n + h) - y(t_n) - hy'(t_n) \\
  &= y(t_n) + hy'(t_n) + O(h^2) - y(t_n) -hy'(t_n) \\
  &= O(h^2)
\end{align*}
so it has order \(1\).

Another example: the \emph{theta-method} is given by
\[
  y_{n + 1} = y_n + h[\theta f(t_n, y_n) + (1 - \theta) f(t_{n + 1}, y_{n + 1})]
\]
which can thought as a parameterised Euler method, with the parameter \(\theta\) controlling the ``explicitness''. For \(\theta = \frac{1}{2}\), it is given a special name: trapezoidal rule.

The order of the theta-method is

\begin{align*}
  &\phantom{={} } y(t_{n + 1}) - y(t_n) - h[\theta y'(t_n) + (1 - \theta) y'(t_{n + 1})] \\
  &= y(t_n) + hy'(t_n) + \frac{h^2}{2} y''(t_n) + \frac{h^3}{3!}y'''(t_n) + O(h^4) \\
  &\quad - y(t_n) - h[\theta y'(t_n) + (1 - \theta)(y'(t_n) + hy''(t_n) + \frac{h^2}{2} y'''(t_n) + O(h^3))] \\
  &= h^2 \left( \frac{y''(t_n)}{2} - (1 - \theta)y''(t_n) \right) + O(h^3) \\
  &= y''(t_n)(\theta - \frac{1}{2})h^2 + O(h^3)
\end{align*}
Thus if \(\theta = \frac{1}{2}\) then it has order \(2\), otherwise order \(1\)\footnote{Strictly speaking we conclude that the order when \(\theta = \frac{1}{2}\) is at least \(2\). To show the order is \(2\) we need to in addition show that the coefficient of \(h^3\) does not vanish.}.

\begin{theorem}
  Let \(\rho(w) = \sum_{\ell = 0}^s \rho_\ell w^\ell\) and \(\sigma(w) = \sum_{\ell = 0}^s \sigma_\ell w^\ell\). Then the order of the multistep method is the largest integer \(p \geq 0\) such that
  \[
    \rho(e^z) - z \sigma(e^z) = O(z^{p + 1})
  \]
  as \(z \to 0\).
\end{theorem}

\begin{proof}
  This is just a tedious exercise using Taylor expansion. For analytic \(y\), we have
  \begin{align*}
    &\phantom{={} } \sum_{\ell = 0}^s \rho_\ell y(t_{n + \ell}) - h \sum_{\ell = 0}^s \sigma_\ell y'(t_{n + \ell}) \\
    &= \sum_{\ell = 0}^s \rho_\ell \sum_{k = 0}^\infty \frac{(\ell h)^k}{k!} y^{(k)}(t_n) - h \sum_{\ell = 0}^s \sigma_\ell \sum_{k = 0}^\infty \frac{(\ell h)^k}{k!} y^{(k + 1)}(t_n) \\
    &= \sum_{\ell = 0}^s \rho_\ell y(t_n) + \sum_{k = 1}^\infty \frac{h^k}{k!} \left[\sum_{\ell = 0}^s \rho_\ell \ell^k y^{(k)}(t_n) - \sum_{\ell = 0}^s \sigma_\ell \ell^{k - 1} ky^{(k)}(t_n) \right] \\
    &= \sum_{\ell = 0}^s \rho_\ell y(t_n) + \sum_{k = 1}^\infty \frac{h^k}{k!} \left[ \sum_{\ell = 0}^s \rho_\ell \ell^k - \sum_{\ell = 0}^s \sigma_\ell \ell^{k - 1} k \right] y^{(k)}(t_n)
  \end{align*}
  This shows that the method has order \(p\) if and only if
  \begin{align*}
    \sum_{\ell = 0}^s \rho_\ell &= 0 \\
    \sum_{\ell = 0}^s \rho^\ell \ell^k - \sum_{\ell = 0}^s \sigma_\ell \ell^{k - 1}k &= 0
  \end{align*}
  for all \(1 \leq k \leq p\).

  Now repeat the same for the exponentials,
  \begin{align*}
    &\phantom{={} } \rho(e^z) - z\sigma(e^z) \\
    &= \sum_{\ell = 0}^s \rho_\ell e^{\ell z} - z \sum_{\ell = 0}^s \sigma_\ell e^{\ell z} \\
    &= \sum_{\ell = 0}^s \rho_\ell \sum_{k = 0}^\infty \frac{(\ell z)^k}{k!} - z\sum_{\ell = 0}^s \sigma_\ell \sum_{k = 0}^\infty \frac{(\ell z)^k}{k!} \\
    &= \sum_{\ell = 0}^s \rho_\ell + \sum_{k = 1}^\infty \frac{z^k}{k!} \left[ \sum_{\ell = 0}^s \rho_\ell \ell^k - \sum_{\ell = 0}^s \sigma_\ell \ell^{k - 1}k \right]
  \end{align*}
  which is of \(O(z^{p + 1})\) if and only if
  \begin{align*}
    \sum_{\ell = 0}^s \rho_\ell &= 0 \\
    \sum_{\ell = 0}^s \rho_\ell \ell^k - \sum_{\ell = 0}^s \sigma_\ell \ell^{k - 1}k &= 0
  \end{align*}
  for all \(1 \leq k \leq p\), which is exactly the same condition as before. The result thus follows.
\end{proof}

\begin{eg}[Adams-Bashforth]
  Recall
  \[
    y_{n + 2} - y_{n + 1} = h \left( \frac{3}{2}f(t_{n + 1}, y_{n + 1}) - \frac{1}{2}f(t_n, y_n) \right).
  \]
  We have
  \begin{align*}
    \rho(w) &= w^2 - w \\
    \sigma(w) &= \frac{3}{2}w - \frac{1}{2}
  \end{align*}
  Thus the exponential formula says
  \begin{align*}
    \rho(e^z) -z\sigma(e^z)
    &= e^{2z} - e^z - z (\frac{3}{2}e^z - \frac{1}{2}) \\
    &= 1 + 2z + \frac{(2z)^2}{2} + \frac{(2z)^3}{3!} \\
    &\quad - (1 + z + \frac{z^2}{2} + \frac{z^3}{3!}) \\
    &\quad -z(\frac{3}{2} + \frac{3z}{2} + \frac{3z^2}{4} - \frac{1}{2}) + O(z^4) \\
    &= z^3(\frac{8}{6} - \frac{1}{6} - \frac{3}{4}) + O(z^4)
  \end{align*}
  so it has order \(2\).
\end{eg}

\subsubsection{Convergence of multistep methods}

\begin{definition}[Root condition]\index{root condition}
  We say that a polynomial \(\rho(w) = \sum_{\ell = 0}^s \rho_\ell w^\ell\) satisfies the \emph{root condition} if all the roots of \(\rho\) lie inside the unit disc \(\{z \in \C: |z| \leq 1\}\) and any root with modulus \(1\) is simple.
\end{definition}

\begin{theorem}[Dahlquist equivalence theorem]\index{Dahquist equivalence theorem}
  The general \(s\)-step method given by \eqref{eqn:multi-step} is convergent if and only if it has order \(p \geq 1\) and \(\rho(w) = \sum_{\ell = 0}^s \rho_\ell w^\ell\) satisfies the root condition.
\end{theorem}

\begin{eg}[Adams-Bashforth]
  \[
    y_{n + 2} - y_{n + 1} = h \left( \frac{3}{2} f(t_{n + 1}, t_{n + 2}) - \frac{1}{2}f(t_n, y_n) \right).
  \]
  We have checked last time that the order is 2. \(\rho(w) = w^2 - w\) with roots \(0\) and \(1\) so the method satisfies the root condition and converges.
\end{eg}

\begin{eg}
  Consider
  \[
    y_{n + 2} - 2y_{n + 1} + y_n = 0.
  \]
  To find the order,
  \begin{align*}
    y(t_{n + 2}) - 2y(t_{n + 1}) + y(t_n)
    &= y(t_n + 2h) - 2y(t_n + h) + y(t_n) \\
    &= \dots \\
    &= O(h^2)
  \end{align*}
  and further computation shows \(p = 1\). \(\rho(w) = w^2 - 2w + 1\) so \(1\) is a root of multiplicity 2 so root condition is not satisfied.
\end{eg}

To construct a convergent \(s\)-step method, follow the two steps:
\begin{enumerate}
\item Choose a polynomial \(\rho\) of degree \(s\) that satisfies the root condition and \(\rho(1) = 0\).
\item To get an implicit method, take \(\sigma(w)\) to be the \(s\)-degree truncation of Taylor expansion of \(\frac{\rho(w)}{\log w}\) around \(w = 1\) (which exists since \(\rho(1) = 0\)). For an explicit method, take \(\sigma\) to be the \((s - 1)\)-degree Taylor truncation of \(\frac{\rho(w)}{\log w}\).
\end{enumerate}

We verify that the order \(\geq s\): for an implicit method, by construction
\[
  \sigma(w) = \frac{\rho(w)}{\log w} + O(|w - 1|^{s + 1})
\]
as \(w \to 1\). Substitute \(w = e^z\) and since \(e^z - 1 = z + O(z^2)\)
\[
  \sigma(e^z) = \frac{\rho(e^z)}{z} + O(z^{s + 1})
\]
as \(z \to 0\). So the order \(\geq s + 1\). In the case of an explicit method order \(\geq s\).

\begin{eg}
  \(s = 2, \rho(w) = w^2 - w\) satisfies the root equation.
  \begin{align*}
    \frac{\rho(w)}{\log w}
    &= \frac{w(w - 1)}{\log w} \\
    &= \frac{(v + 1)v}{\log (1 + v)} \\
    &= \frac{(v + 1)v}{ v - \frac{v^2}{2} + \frac{v^3}{3} + O(v^4)} \\
    &= \dots \\
    &= 1 + \frac{3}{2}v + \frac{5}{12}v^2 + O(v^3)
  \end{align*}
  Thus
  \[
    \sigma(w) = 1 + \frac{3}{2}(w - 1) + \frac{5}{12}(w - 1)^2
  \]
  for an implicit method (which is called Adams-Moulton method) and
  \[
    \sigma(w) = 1 + \frac{3}{2}(w - 1) = -\frac{1}{2} + \frac{3}{2}w
    \]
    which gives Adams-Bashforth method.
\end{eg}

\subsection{Backward differentiation formula}

\begin{definition}[Backward differentiation formula]\index{backward differentiation formula}
  A \emph{backward differentiation formula} (BDF) is an \(s\)-step methods with
  \begin{equation}
    \label{eqn:BDF}
    \sigma(w) = \sigma_sw^s.
  \end{equation}
\end{definition}

\begin{theorem}
  For \eqref{eqn:BDF} to have order \(s\), we must have
  \[
    \rho(w) = \sigma_s \sum_{\ell = 1}^s \frac{1}{\ell} w^{s - \ell}(w - 1)^\ell
  \]
  with \(\sigma_s = \left( \sum_{\ell = 1}^s \frac{1}{\ell} \right)^{-1}\).
\end{theorem}

\begin{proof}
  We want \(\rho\) to satisfy
  \[
    \rho(w) - \sigma_sw^s\log w = O(|w - 1|^{s + 1})
  \]
  as \(w \to 1\). We have
  \[
    \log w
    = -\log \frac{1}{w}
    = -\log \left( 1 - \frac{w - 1}{w} \right)
    = \sum_{\ell = 1}^\infty \frac{1}{\ell} \left( \frac{w - 1}{w} \right)^\ell.
  \]
  But our choice of \(\rho\) is precisely the first \(s\)-terms in this expansion. The value of \(\sigma_s\) is chosen such that \(\rho_s = 1\).
\end{proof}

\begin{eg}
  Let \(s = 2, \sigma_s = (1 + \frac{1}{2})^{-1} = \frac{2}{3}\), then
  \[
    \sigma(w) = \frac{2}{3}(w(w - 1) + \frac{1}{2}(w - 1)^2) = w^2 - \frac{4}{3}w + \frac{1}{3}
  \]
  which gives \(2\)-step BDF
  \[
    y_{n + 2} - \frac{4}{3}y_{n + 1} + \frac{1}{3}y_n = \frac{2}{3}h f(t_{n + 2}, y_{n + 2}).
  \]
\end{eg}

\subsection{Runge-Kutta methods}

Suppose we want to solve the ODE
\[
  y' = f(t, y),\, y(0) = y_0.
\]
The solution of this ODE satisfies
\begin{align*}
  y(t_{n + 1})
  &= y(t_n) + \int_{t_n}^{t_{n + 1}} y'(\tau) d\tau \\
  &= y(t_n) + \int_{t_n}^{t_{n + 1}} f(\tau, y(\tau)) d\tau \\
  &= y(t_n) + h \int_0^1 f(t_n + \alpha h, y(t_n + \alpha h)) d\alpha \\
\intertext{at this point we can apply quadrature formulæ}
  &\approx y(t_n) + h \sum_{j = 1}^\nu b_j \underbrace{f(t_n + c_j h, y(t_n + c_j h))}_{\approx k_j}
\end{align*}
and Runge-Kutta will give estimates to the \(k_j\)'s.

The \emph{explicit Runge-Kutta method}\index{Runge-Kutta method} is
\[
  y_{n + 1} = y_n + h \sum_{j = 1}^\nu b_j k_j
\]
with
\begin{align*}
  k_1 &= f(t_n, y_n) \\
  k_2 &= f(t_n + c_2h, y_n + c_2hk_1) \\
      &\vdots \\
  k_\nu &= f(t_n + c_\nu h, y_n + h \sum_{j = 1}^{\nu - 1} a_{j, \nu} k_j)
\end{align*}
where \(\sum_{j = 1}^{\nu - 1} a_{j, \nu} = c_\nu\).

\begin{eg}
  \(\nu = 2\). We have
  \[
    y_{n + 1} = y_n + h(b_1k_1 + b_2k_2)
  \]
  where
  \begin{align*}
    k_1 &= f(t_n, y_n) \\
    k_2 &= f(t_n + c_2h, y_n + c_2hk_1)
  \end{align*}
  The order of the Runge-Kutta method is defined to be the largest integer \(p \geq 0\) such that
  \[
    y(t_{n + 1}) - y(t_n) - h(b_1k_1 + b_2k_2) = O(h^{p + 1})
  \]
  where \(y\) is the solution of the ODE. For the above case we have
  \begin{align*}
    k_1 &= f(t_n, y(t_n)) = y'(t_n) \\
    k_2 &= f(t_n + c_2h, y(t_n + c_2h)) \\
        &= f(t_n + c_2h, y(t_n) + c_2hy'(t_n) + O(h^2)) \\
        &= f(t_n, y(t_n)) + \frac{\p f}{\p t} c_2h + \frac{\p f}{\p y} (c_2hy'(t_n) + O(h^2)) + O(h^2) \\
        &= f(t_n, y(t_n)) + hc_2 \underbrace{\left( \frac{\p f}{\p t} + \frac{\p f}{\p y} y'(t_n) \right)}_{y''(t_n)} + O(h^2)
  \end{align*}
  Thus after some calculation we find that
  \begin{align*}
    &\phantom{={}}y(t_{n + 1}) - y(t_n) - h(b_1k_1 + b_2k_2) \\
    &= hy'(t_n)(1 - b_1 - b_2) + h^2y''(t_n)(\frac{1}{2} - b_2c_2) + O(h^3)
  \end{align*}
  Thus if
  \begin{align*}
    1 - b_1 - b_2 &= 0 \\
    \frac{1}{2} - b_2c_2 &= 0
  \end{align*}
  the method has order \(\geq 2\).
\end{eg}

Now let's prove that the order cannot be \(\geq 3\), by exhibiting a ODE whose analytic solution is known. Consider
\begin{align*}
  y' &= y \\
  y(0) &= 1
\end{align*}
The solution of this ODE is \(y(t) = e^t\). Thus
\begin{align*}
  k_1 &= f(t_n, y(t_n)) = y(t_n) = e^{t_n} \\
  k_2 &= f(t_n + c_2h, y(t_n) + c_2hk_1) = y(t_n) + c_2hk_1 = e^{t_n}(1 + c_2h)
\end{align*}
so
\begin{align*}
  &\phantom{={}}y(t_{n + 1}) - y(t_n) - h(b_1k_1 + b_2k_2) \\
  &= e^{t_n + h} - e^{t_n} - he^{t_n}(b_1 + b_2(1 + c_2h)) \\
  &= e^{t_n}(e^h - 1 -h(b_1 + b_2(1 + c_2h))) \\
  &= e^{t_n}(h + \frac{h^2}{2} + \frac{h^3}{6} + O(h^3) - h(b_1 + b_2) - h^2b_2c_2) \\
  &= e^{t_n}(h(1 - b_1 - b_2) + h^2(\frac{1}{2} - b_2c_2) + \frac{h^3}{6} + O(h^3))
\end{align*}
which has a non-vanishing \(h^3\) term.

In general, a Runge-Kutta method has the form
\[
  y_{n + 1} = y_n + h \sum_{\ell = 1}^\nu b_\ell k_\ell
\]
where
\[
  k_\ell = f(t_n + c_\ell h, y_n + h \sum_{j = 1}^\nu a_{\ell, j} k_j)
\]
and \(\sum_{j = 1}^\nu a_{\ell, j} = c_\ell\).

For explicit Runge-Kutta method, \(a_{\ell, j} = 0\) for \(j \geq \ell\), i.e.\ the matrix \(a_{\ell, j}\) is lower triangular.

\subsection{Stiffness}

Consider the ODE
\[
  y' = \lambda y, \, y(0) = 1.
\]
The solution is \(y(t) = e^{\lambda t}\) and if \(\lambda < 0\), \(\lim_{t \to \infty} y(t) = 0\). If we solve our ODE using a numerical method, we want \(\lim_{n \to \infty} y_n = 0\).

For example, explicit Euler gives
\[
  y_n = (1  + h\lambda)^n
\]
which goes to zero as \(n \to \infty\) if and only if \(|1 + h\lambda| < 1\), i.e.\ \(h < \frac{2}{|\lambda|}\).

On the other hand, implicit Euler gives
\[
  y_{n + 1} = (1 - h\lambda)^{-n}
\]
which goes to \(0\) as \(n \to \infty\) for any \(h > 0\).

\begin{definition}[Linear stability domain]\index{linear stability domain}
  Consider a numerical method for the ODE
  \[
    y' = \lambda y, \, y(0) = 1
  \]
  that produces sequence \((y_n)_{n \geq 0}\). The \emph{linear stability domain} of the method is
  \[
    \mathcal D = \{h\lambda \in \C: \lim_{n \to \infty} y_n = 0\}.
  \]
\end{definition}

\begin{definition}[\(A\)-stable]\index{\(A\)-stable}
  We say the method is \emph{\(A\)-stable} if \(\C^- \subseteq \mathcal D\) where \(\C^- = \{z \in \C: \Re z < 0\}\).
\end{definition}

\begin{eg}
  For explicit Euler method,
  \[
    \mathcal D = \{h\lambda \in \C: |1 + h\lambda| < 1\}
    = \{z \in \C: |1 + z| < 1\}.
  \]
  which is not \(A\)-stable.
  
  For implicit Euler method,
  \[
    \mathcal D
    = \{z \in \C: |(1 - z)^{-1}| < 1\}
    = \{z \in \C: |1 - z| > 1\}
  \]
  which is \(A\)-stable.
\end{eg}

\begin{eg}[Trapezoidal rule]
  \[
    y_{n + 1} = y_n + \frac{h}{2}(f(t_n, y_n), f(t_{n + 1}, y_{n + 1}))
  \]
  Assume \(f(t, y) = \lambda y\) so
  \begin{align*}
    y_{n + 1}(1 - \frac{1}{2}h\lambda) &= (1 + \frac{1}{2}h\lambda)y_n \\
    y_n &= \left( \frac{1 + \frac{1}{2}h\lambda}{1 - \frac{1}{2}h\lambda} \right)^n y_0
  \end{align*}
  so the linear stability domain is
  \[
    \mathcal D = \{z \in \C: \Re z < 0\}.
  \]
  Thus trapezoidal rule is \(A\)-stable.
\end{eg}

\begin{theorem}[Second Dahlquist barrier]\index{second Dahlquist barrier}
  Any \(A\)-stable multistep method has order \(\leq 2\).
\end{theorem}

This is a bad news for multistep methods. One way to get around this is to relax \(A\)-stability condition. Recall that the backward differentiation formula (BDF) is an \(s\)-step method with \(\sigma(w) = \sigma_sw^s\). It is almost \(A\)-stable (see pictures in lecture).

\subsubsection{Stiffness and Runge-Kutta}

Consider the \(2\)-stage implicit Runge-Kutta method
\[
  y_{n + 1} = y_n + \frac{1}{4}h(k_1 + 3k_2)
\]
where
\begin{align*}
  k_1 &= f(t_n, y_n + \frac{1}{4}h (k_1 - k_2)) \\
  k_2 &= f(t_n, + \frac{2}{3}h, y_n + \frac{1}{12}h (3k_1 + 5k_2))
\end{align*}

Let's compute its linear stability domain. Assume \(f(t, y) = \lambda y\) so
\begin{align*}
  k_1 &= \lambda y_n + \frac{1}{12}\lambda h (k_1 - K_2) \\
  k_2 &= \lambda y_n + \frac{1}{12}\lambda h(3k_1 + 5k_2)
\end{align*}
Solve to get
\[
  \begin{pmatrix}
    k_1 \\
    k_2
  \end{pmatrix}
  = \frac{\lambda y_n}{1 - \frac{2}{3}h \lambda + \frac{1}{6}(h\lambda)^2}
  \begin{pmatrix}
    1 - \frac{2}{3}h\lambda \\
    1
  \end{pmatrix}
\]
The solution to the original problem is
\[
  y_{n + 1} = \frac{1 + \frac{1}{3}h\lambda}{1 - \frac{2}{3}h\lambda + \frac{1}{6}(h\lambda)^2}y_n
\]
so the linear stability domain is the region where the modulus of the factor is small than \(1\), i.e.
\[
  \mathcal D = \{z \in \C: |r(z)| < 1\}
\]
where \(r(z) = \frac{1 + \frac{1}{3}z}{1 - \frac{2}{3}z + \frac{1}{6}z^2}\). To show it is \(A\)-stable, we use maximum modulus principle from IB Complex Analysis. First notice that \(r(z)\) is a rational function with poles \(2 \pm \sqrt 2 i\). As \(r(z)\) is analytic in the negative real half plane, \(\max|r(z)|\) is attained at the boundary of the domain, i.e.\ \(i\R\). For all \(t \in \R\),
\[
  |r(it)| = \frac{|1 + \frac{1}{3}it|}{|1 - \frac{2}{3}it - \frac{1}{6}t^2|}
\]
so \(|r(it)|^2 \leq 1\) if and only if
\[
  1 + \frac{1}{9}t^2 \leq (1 - \frac{1}{6}t^2)^2 + (\frac{2}{3}t)^2,
\]
if and only if
\[
  \frac{1}{36}t^4 \geq 0.
\]
Thus the method is \(A\)-stable.

Let's show that our implicit Runge-Kutta method has order \(\geq 3\). We will restrict our attention to only scalar autonomous equations \(y' = f(t)\). Let \(y\) be the solution to our ODE. Write \(y\) for \(y_n\). Then
\begin{align*}
  k_1 &= f(y + \frac{1}{4}h(k_1 - k_2)) \\
      &= f(y) + \frac{1}{4}h(k_1 - k_2) f' + \frac{1}{32}h^2(k_1 - k_2)^2 f'' + O(h^3) \\
  k_2 &= f(y + \frac{1}{12}h(3k_1 + 5k_2) \\
      &= f(y) + \frac{1}{12}h(3k_1 + 5k_2)f' + \frac{1}{288}h^2(3k_1 + 5k_2)^2 f'' + O(h^3)
\end{align*}
It is difficult and tedious to solve this directly, but we could use a trick to extract the coefficients iteratively. To first order
\begin{align*}
  k_1 &= f(y) + O(h) \\
  k_2 &= f(y) + O(h)
\end{align*}
Plug in to get
\begin{align*}
  k_1 &= f(y) + O(h^2) \\
  k_2 &= f(y) + \frac{8}{12}h f'f(y) + O(h^2)
\end{align*}
Plug in again,
\begin{align*}
  k_1 &= f(y) - \frac{1}{6}h^2 (f')^2f(y) + O(h^3) \\
  k_2 &= f(y) + \frac{2}{3}h f' f(y) + h^2(\frac{5}{18} (f')^2 f(y) + \frac{2}{9} f'' f(y)^2) + O(h^3)
\end{align*}
Use these values to compute local error,
\begin{align*}
  \cdots
\end{align*}

\blindtext

\subsection{Implementation of ODE methods}

\subsubsection{Error control}

\paragraph{Milne device}

Given the trapezoidal rule
\[
  y_{n + 1} = y_n + \frac{1}{2}h(f(t_n, y_n) + f(t_{n + 1}, y_{n + 1}),
\]
we want to get an estimate of \(y_{n + 1} - y(t_{n + 1})\),
\begin{align*}
  y(t_{n + 1}) - y_{n + 1}
  &= -\frac{1}{12}h^3y'''(t_n) + O(h^4)
\end{align*}
where \(-\frac{1}{12}\) is called the \emph{error constant} of the trapezoidal rule.

We secretly run another method in the background:
Adams-Bashforth
\[
  y_{n + 1} = y_n + \dots
\]
has order \(2\). By expansion,
\[
  y(t_{n + 1}) - y_{n + 1} = \frac{5}{12}h^3y'''(t_n) + O(h^4)
\]
so the error constant is \(\frac{5}{12}\).

Then
\[
  y_{n + 1}^{\text{AB}} - y_{n + 1}^{\text{TR}} = (-\frac{1}{12} - \frac{5}{12})h^3y'''(t_n) + O(h^4)
\]
so
\[
  h^3y'''(t_n) \approx -2(t_{n + 1}^{\text{AB}} - y_{n + 1}^{\text{TR}}.
\]
Plugging into the eqution for trapezoidal rule,
\[
  y_{n + 1}^{\text{TR}} - y(t_{n + 1}) \approx \frac{1}{6} (y_{n + 1}^{\text{TR}} - y_{n + 1}^{\text{AB}}.
\]

More generally, we work with a pair of multistep methods of the same order
\begin{table}[ht]
  \centering
  \begin{tabular}{cc}
    predictor & explicit \\
    corrector & implicity
  \end{tabular}
\end{table}

There are two goals for having a predictor:
\begin{enumerate}
\item get initial guess when solving algebraic equation for the (implicit) corrector method.
\item error control: provide an estimate of the error incurred by the corrector.
\end{enumerate}

Let \(tol > 0\) be the error tolerance probided by user. Let \(\norm{\text{error}}\) be the estimate of the local error as computed in the previous.
\begin{enumerate}
\item \blindtext
\end{enumerate}

\subsubsection{Embedded Runge-Kutta}

The two-step Runge-Kutta method is
\begin{align*}
  k_1 &= f(t_n, y_n) \\
  k_2 &= f(t_n + \frac{1}{2}h, y_n + \frac{1}{2}hk_1) \\
  y_{n + 1}^1 &= y_n + hk_2
\end{align*}
which has order \(2\). We can further define
\begin{align*}
  k_3 &= f(t_n + h, y_n - h + 2hk_1) \\
  y_{n + 1}^2 &= y_n + \frac{1}{6}h(k_1 + hk_2 + k_3)
\end{align*}
which has order \(3\). Then we can use the second method as the ``true'' value of the function to estimate the error the first method, i.e.
\[
  y_{n + 1}^1 - y(t_{n + 1}) \approx y_{n + 1}^1 - y_{n + 2}^2.
\]

Zadunaisky device: the idea is to define another ODE
\begin{equation}
  \label{eqn:Zadunaisky2}
  z' = g(t, z)
  \tag{\(\ast\)}
\end{equation}
``close'' to our ODE
\begin{equation}
  \label{eqn:Zadunaisky1}
  y' = f(t, y)
  \tag{\(\ast\ast\)}
\end{equation}
and such that we know the exact solution to \eqref{eqn:Zadunaisky2}. Our estimate of the error will be
\[
  y_{n + 1} - y(t_{n + 1}) \approx z_{n + 1} - z(t_{n + 1})
\]
where the first term on RHS is what we get by running the numerical method for \eqref{eqn:Zadunaisky2} and the second term is its analytic solution, which is known.

Let \(y_n, y_{n - 1}, \dots, y_{n - p}\) be past solution values define by running the numerical method for \eqref{eqn:Zadunaisky1}. Let \(d\) be a degree \(p\) polynomial that interpolates these the values \(d(t_{n - k}) = y_{n - k}\) for \(0 \leq k \leq p\). Our approximate ODE is
\[
  z' = f(t, z) + (d' - f(t, d))
\]
where the second term on RHS is small since \(d \approx y\) and \(y' = f(t, y)\). The solution of this ODE is just \(z = d\).

That's all we are going to talk about error control.

\subsection{Solving nonlinear algebraic equations using Newton-Raphson}

There is one problem we still haven't discussed: solving nonlinear algebraic equations.

An implicit \(s\)-step method has the form
\[
  y_{n + s} = h \sigma_s f(t_{n + s}, y_{n + s}) + v
\]
where \(v\) only depends on previous values \(y_n, \dots, y_{n + s - 1}\). One way is to use \emph{functional iteration} or \emph{fixed point iteration}:
\begin{enumerate}
\item given initial guess \(y_{n + s}^0\) for \(y_{n + s}\) (for example from predictor method)
\item iteration
  \[
    y_{n + s}^{j + 1} = h \sigma_s f(t_{n + s}, y_{n + s}^j) + v.
  \]
\item (Hope it converges to the actual value.)
\end{enumerate}

\section{Numerical Linear Algebra}

\subsection{LU factorisation}

\begin{definition}[LU factorisation]\index{LU factorisation}
  Let \(A\) be a real \(n \times n\) matrix. An \emph{LU factorisation} of \(A\) is a factorisation \(A = LU\) where \(L\) is unit lower triangluar, i.e.\ \(L_{ij} = 0\) for \(j > i\), \(L_{ii} = 1\) for \(1 \leq i \leq n\) and \(U\) is upper triangular, i.e.\ \(U_{ij} = 0\) if \(j < i\).
\end{definition}

\begin{application}\leavevmode
  \begin{enumerate}
  \item Determinant: given \(A = LU\), the determinant can be computed by
    \[
      \det A = (\det L)(\det U) = \prod_{i = 1}^n L_{ii} \prod_{i = 1}^n U_{ii} = \prod_{i = 1}^n U_{ii}
    \]
    which is much faster than using starting ab initio from the definition
    \[
      \det A = \sum_{\sigma \in S_n} \sgn(\sigma) \prod_{i = 1}^n A_{i, \sigma(i)}
    \]
    which has \(n!\) terms in the sum and can be prohibitively expensive computationally.
  \item Testing non-singularity: \(A\) is singular if and only if \(\det A = 0\), if and only if there exists \(i \in \{1, \dots, n\}\) such that \(U_{ii} = 0\).
  \item Solving linear equations: suppose \(Ax = b\) with \(x\) unknown. Then it suffices to solve
    \begin{align*}
      Ux &= y \\
      Ly &= b
    \end{align*}
    which are triangular systems and can be solved using (forward/backward) substitution (the cost of which is \(O(n^2)\)).
  \end{enumerate}
\end{application}

Let \(\ell_1, \dots, \ell_n\) be columns of \(L\) and \(u_1^T, \dots, u_n^T\) be rows of \(U\) so
\[
  A = LU = (\ell_1 \ \cdots \  \ell_n)
  \begin{pmatrix}
    u_1^T \\
    \vdots \\
    u_n^T
  \end{pmatrix}
  = \sum_{i = 1}^n \ell_i u_i^T
\]
Note that \(\ell_k\) has \(1\) at \(k\)th component and \(0\) at \(i\)th component for \(i < k\). Similarly \(u_k\) has \(0\) at \(i\)th component for \(i < k\). Thus the first \(k - 1\) rows and columns of \(\ell_k u_k^T\) are \(0\). Thus the only contribution to the first row and column of \(A\) comes from \(\ell_1u_1^T\), implying that
\begin{align*}
  u_1^T &= \text{1st row of } A \\
  \ell_1 &= \frac{1}{A_{11}} \cdot \text{1st column of } A
\end{align*}
Subsequently, let \(A_1 = A - \ell_1u_1^T\). The only contribution to the second row and column of \(A_1\) comes from \(\ell_2u_2^T\) so
\begin{align*}
  u_2^T &= \text{2nd row of } A_1 \\
  \ell_2 &= \frac{1}{(A_1)_{22}} \cdot \text{2nd column of } A_2
\end{align*}

The general algorithm is

\begin{algorithm}
  \(A_0 = A\)\;
  \For{\(k = 1\) \KwTo \(n\)}{
    \(u_k^T =\) \(k\)th row of \(A_{k -1 }\)\;
    \(\ell_k = \frac{1}{(A_{k - 1})_{kk}} \cdot\) \(k\)th column of \(A_{k - 1}\)\;
    \(A_k = A_{k - 1} - \ell_ku_k^T\)\;
  }
  \caption{LU factorisation}
\end{algorithm}

\paragraph{Complexity analysis}
The dominant cost is the last line in the for loop, where the number of multiplications needed to form \(\ell_ku_k^T\) is \((n - k + 1)^2\) so the total cost is
\[
  \sum_{k = 1}^n (n - k + 1)^2 = \sum_{j = 1}^n j^2 = O(n^3).
\]

A quick remark for implementation: we don't have to store \(A_k\)'s so it is possible to have even smaller spatial complexity.

The algorithm can be seen as a variant of Guassian elimination: the matrix \(A_k\) constructed in the algorithm is of the form
\[
  \begin{pmatrix}
    0 & 0 \\
    0 & *
  \end{pmatrix}
\]
and the lower right block is exactly the same as the one obtained after \(k\) steps of Gaussian elimination.

\subsection{Pivoting}

In the factorisation algorithm above, what happens if \((A_{k - 1})_{kk} = 0\)? Indeed, not all matrices are LU factorisable. We have to \emph{pivot}\index{pivot}.

\begin{algorithm}
  \(A_0 = A\)\;
  \For{\(k = 1\) \KwTo \(n\)}{
     let \(p \geq k\) be such that \((A_{k - 1})_{pk} \neq 0\)\;
     let \(P_k\) be the permutation matrix that swaps positions \(k\) and \(p\)\;
     \(l_k = \frac{1}{(P_kA_{k - 1})_{kk}} \cdot\) \(k\)th column of \(P_kA_{k - 1}\)\;
     \(u_k^T = \) \(k\)th row of \(P_kA_{k - 1}\)\;
    \(A_k = P_kA_{k - 1} - l_ku_k^T\)\;
  }
  \caption{LU factorisation with pivoting}
\end{algorithm}

If we unfold the algorithm, we get
\begin{align*}
  A_1 &= P_1A - \ell_1u_1^T \\
  A_2 &= P_2A_1 - \ell_2u_2^T = P_2P_1A - P_2\ell_1u_1^T - \ell_2u_2^T \\
  \vdots \\
  A_n &= P_{n - 1} \cdots P_1A - P_{n - 1} \cdots P_2 \ell_1 u_1^T - \cdots - \ell_nu_n^T
\end{align*}
by noting that \(P_n = I\). Since \(A_n = 0\), we get
\[
  PA = \tilde L U
\]
where
\begin{align*}
  P &= P_{n - 1} \cdots P_1 \\
  \tilde L &= (\tilde \ell_1 \  \cdots \  \tilde \ell_n)
\end{align*}
and
\[
  \tilde \ell_k = P_{n - 1} \cdots P_{k + 1} \ell_k.
\]
Note that \(\tilde \ell_k\) has \(1\) at \(k\)th component and \(0\) for \(1, \dots, k - 1\) since the permutations only act on the components \(k + 1, \dots, n\). Thus \(L\) is a unit lower triangular matrix.

\begin{note}
  The algorithm can still fail if \((A_{k - 1})_{pk} = 0\) for all \(p \geq k\). But we can make a choice so that \(\ell_k\) have \(1 \) in \(k\)th component and \(0\) elsewhere, and \(u_k^T\) to be \(k\)th row of \(A_{k - 1}\) so \(A_{k - 1} - \ell_ku_k^T\) has its \(k\)th row and column \(0\) (the factorisation in this case is not unique and we made a choice in \(\ell_k\)).
\end{note}

Pivoting is not only needed to prevent the algorithm from failing but also to prevent round-off errors from accummulating. Thus it is always used for numerical stability of the algorithm. A common choice of pivot is to take \(p\) such that \(|(A_{k - 1})_{pk}|\) is maximum for all \(p \geq k\). With such a choice of pivot, all entries of \(L\) have abolute value \(\leq 1\).

\subsection{Symmetric matrices}

A symmetric matrix \(A\) is such that \(A_{ij} = A_{ji}\) for all \(i, j\). We aim to factorise it in a way to exhibit this symmetry. 

\begin{definition}[LDL\textsuperscript{T} factorisation]\index{LDL\textsuperscript{T} factorisation}
  An \emph{LDL\textsuperscript{T} factorisation} of a symmetric matrix \(A\) is
  \[
    A = LDL^T
  \]
  where \(L\) is unit lower triangular and \(D\) is diagonal.
\end{definition}

Note that this is a special case of LU factorisation where \(U = DL^T\).

We can construct an LDL\textsuperscript{T} factorisation using an algorithm very similar to the LU factorisation (without pivoting), with the final result being
\[
  A = D_{11}\ell_1\ell_1^T + \cdots + D_{nn}\ell_n\ell_n^T = LDL^T
\]
where
\[
  L = \ell_1\ell_1^T + \dots + \ell_n\ell_n^T.
\]

\begin{algorithm}
  \(A_0 = A\)\;
  \For{\(k = 1\) \KwTo \(n\)}{
    \(\ell_k = \frac{1}{(A_{k - 1})_{kk}} \cdot\) \(k\)th column of \(A_{k - 1}\)\;
    \(D_{kk} = (A_{k - 1})_{kk}\)\;
    \(A_k = A_{k - 1} - D_{kk}\ell_k\ell_k^T\)\;
  }
  \caption{LDL\textsuperscript{T} factoriation}
\end{algorithm}

We will run into similar problems if all elements in a row below certain element is zero. We can still use pivoting, but note that to preserve the symmetry we must act it on both the rows and columns. Instead, in this section we will discuss cases where our naïve algorithm always works.

Recall that a symmetric positive definite matrix \(A\) is such that
\[
  x^TAx > 0
\]
for all \(x \in \R^n \setminus \{0\}\).

\begin{theorem}
  A symmetric matrix \(A\) is positive definite if and only if it has an LDL\textsuperscript{T} factorisation where \(D_{kk} > 0\) for all \(1 \leq k \leq n\).
\end{theorem}

\begin{proof}
  This is exactly the same as the proof in IB Linear Algebra, but numerical analysis flavoured.
  \begin{itemize}
  \item \(\impliedby\): Assume \(A = LDL^T\) of the form given. For any \(x \in \R^n \setminus \{0\}\),
    \[
      x^TAx = x^TLDL^Tx = y^TDy = \sum_{k = 1}^n D_{kk}u_k^2 > 0
    \]
    where \(y = L^Tx \neq 0\) since \(x \neq 0\) and \(L\) is non-singular.
  \item \(\implies\): We will show that at each step of the algorithm, \((A_{k - 1})_{kk} > 0\). Proceed by induction. If \(k = 1\),
    \[
      (A_0)_{11} = A_{11} = e_1^TAe_1 > 0.
    \]
    By definition
    \[
      A_{k - 1} = A - D_{11}\ell_1\ell_1^T - \dots - D_{k - 1}\ell_{k - 1}\ell_{k - 1}^T.
    \]
    Define \(x \in \R^n\) as the solution of the linear system
    \[
      \begin{pmatrix}
        & & \ell_1^T \\
        & & \cdots \\
        & & \ell_{k - 1}^T \\
        0 & \cdots & 0 & 1 \\
        & & & & 1 \\
        & & & & & \ddots \\
        & & & & & & 1
      \end{pmatrix}
      x =
      \begin{pmatrix}
        0 \\
        \vdots \\
        0 \\
        1 \\
        0 \\
        \vdots \\
        0
      \end{pmatrix}
    \]
    which has a unique solution as the matrix is non-singular. Then by construction
    \begin{align*}
      (A_{k - 1})_{kk}
      &= x^TA_{k - 1}x \\
      &= x^T(A - \sum_{j = 1}^{k - 1}D_{jj}\ell_j\ell_j^T)x \\
      &= x^tAx - \underbrace{\sum_{j = 1}^{k - 1} D_{jj} (\ell_j^Tx)^2}_{= 0} \\
      &= x^TAx \\
      & > 0
    \end{align*}
  \end{itemize}
\end{proof}

For a positive definite matrix \(A = LDL^T\) with \(D_{kk} > 0\), let
\[
  D^{1/2} = \operatorname{diag}(D_{11}^{1/2}, \dots, D_{nn}^{1/2}).
\]
Then
\[
  A = LD^{1/2}D^{1/2}L^T = \tilde L \tilde L^T
\]
where \(\tilde L = LD^{1/2}\) is lower triangular. This the \emph{Cholesky factorisation}\index{Cholesky factorisation}.

\subsection{Sparse matrices}

Informally, a \emph{sparse matrix}\index{sparse matrix} is one with ``many'' zeros.

\begin{eg}
  A matrix \(A\) is \emph{banded}\index{banded matrix} if \(A_{ij} = 0\) whenever \(|i - j| > r\) for some fixed \(r\). For examlple, if \(r = 1\) then \(A\) is diagonal. If \(r = 2\) then \(A\) is tridiagonal.
\end{eg}

We want the LU factorisation of a sparse matrix to inherit this property.

\begin{theorem}
  Let \(A = LU\) be an LU factorisation of \(A\) (without pivoting). Then
  \begin{enumerate}
  \item all leading zeros in the rows of \(A\) to the left of the diagonal are inherited by \(L\),
  \item all leading zeros in the columns of \(A\) above the diagonal are inherited by \(U\).
  \end{enumerate}
\end{theorem}

\begin{proof}
  We assume that the LU factorisation algorithm terminates without failing, which implies that \((A_{k - 1})_{kk} = U_{kk} \neq 0\).

  Assume \(A_{i, 1} = A_{i, 2} = \dots = A_{i, j} = 0\) where \(j < i\). We want to show
  \[
    L_{i, 1} = L_{i, 2} = \dots = L_{i, j} = 0.
  \]
  But
  \[
    0 = A_{i, 1} = L_{i, 1}\underbrace{U_{11}}_{\neq 0} + \underbrace{L_{1, 2}U_{2, 1} + \dots}_{= 0}
  \]
  so \(L_{i, 1} = 0\). Similarly
  \[
    0 = A_{i, 2} = \underbrace{L_{i, 1}}_{= 0}U_{1, 2} + L_{1, 2}\underbrace{U_{2, 2}}_{\neq 0} + \underbrace{L_{1, 3}U_{3, 2} + \dots}_{= 0}
  \]
  so \(L_{i, 2} = 0\) and so on. The statement about columns are exactly the same.
\end{proof}

\begin{application}
  If \(A\) is banded with bandwidth \(r\), then an LU factorisation of \(A\) inherits this banded structure.
\end{application}

For banded matrices with bandwidth \(r\), an LU facorisation can be computed in \(O(r^2n)\) time, and a linear system can be solved (given an LU factorisation) in \(O(rn)\) time. To see this,

\begin{algorithm}
  \(A_0 = A\)\;
  \For{\(k = 1\) \KwTo \(n\)}{
    \(\ell_k = \frac{1}{(A_{k - 1})_{kk}} \cdot\) \(k\)th column of \(A_{k - 1}\)\;
    \(U_k^T = \) \(k\)th row of \(A_{k - 1}\)\;
    \(A_k = A_{k - 1} - \ell_ku_k^T = A_{k - 1} - \sum_{i = k}^{k + r - 1}\ell_{ik}u_{ki}\)\;
  }
  \caption{LU factorisation for \(r\)-banded matrix}
\end{algorithm}
so we only need \(r^2\) multiplications to form \(\ell_ku_k^T\).

Recall that to solve a linear system \(Ax = b\) given LU factorisation \(A = LU\), we instead solve
\begin{align*}
  Ux &= y \\
  Ly &= b
\end{align*}
using substitutions, which in general takes \(O(n^2)\) opeartions. If \(A\) is \(r\)-banded, in each step at most \(r\) opeartions is needed so the complexity is \(O(rn)\).

For a general sparse matrice \(A\), however, an LU factorisation can have significantly more nonzero elements than \(A\). Ideally we want an LU factorisation that minimises \emph{fill-ins}\index{fill-in}, which is a zero entry of \(A\) that is nonzero in \(L\) or \(U\). One way to minimise fill-ins is via pivoting.

\subsection{QR factorisation}

Recall from IB Linear Algebra: we endow \(\R^n\) with the Euclidean inner product
\[
  \inner{x, y} = \sum_{i = 1}^n x_iy_i = x^Ty.
\]
Two vectors are called \emph{orthogonal} if \(x^Ty = 0\). An \emph{orthonormal} system \((q_1, \dots, q_m)\) in \(\R^n\) is a system such that
\[
  q_i^Tq_j =
  \begin{cases}
    1 & \text{if } i = j \\
    0 & \text{if } i \neq j
  \end{cases}
\]
A matrix \(Q \in \matrixring_{n, n}(\R)\) is \emph{orthogonal} if its columns form an orthonormal basis of \(\R^n\). Equivalently, a matrix \(Q\) is orthogonal if any one of the following holds:
\begin{itemize}
\item \(Q^TQ = I\),
\item \(Q^{-1} = Q^T\),
\item \(QQ^T = I\).
\end{itemize}

\begin{remark}
  If \(Q \in \matrixring_{n, n}(\R)\) is orthogonal then \(\det Q = \pm 1\).
\end{remark}

\begin{definition}[QR factorisation]\index{QR factorisation}
  Let \(A \in \matrixring_{m, n}(\R)\). A QR \emph{factorisation} of \(A\) is a factorisation \(A = QR\) where
  \begin{itemize}
  \item \(Q \in \matrixring_{m, m}(\R)\) is orthogonal,
  \item \(R \in \matrixring_{m, n}(\R)\) is upper triangular.
  \end{itemize}

  In the case where \(m \geq n\), a \emph{reduced QR factorisation} is \(A = QR\) where
  \begin{itemize}
  \item \(Q \in \matrixring_{m, n}(\R)\) has orthogonal columns,
  \item \(R \in \matrixring_{n, n}(\R)\) is upper triangular.
  \end{itemize}
\end{definition}

% add blank matrices

\paragraph{Application fo QR factorisation to linear system solving}

Suppose \(A\) is \(n \times n\). \(Ax = b\) is equivalent to
\begin{align*}
  Rx &= y \\
  Qy &= b
\end{align*}
but \(Q\) is orthogonal so \(Q^{-1} = Q^T\) so
\begin{align*}
  Rx &= y \\
  y &= Q^Tb
\end{align*}
which takes \(O(n^2)\) operations.

\paragraph{Gram-Schmidt algorithm}
\index{Gram-Schmidt}

Assume \(m \geq n\), and we want to construct a reduced QR factorisation. Let \(a_1, \dots, a_n \in \R^n\) be the columns of \(A\). We want to find \(q_1, \dots, q_n \in \R^m\) such that
\begin{enumerate}
\item \(q_k\) is a linear combination of \(a_1, \dots, a_k\),
\item \((q_1, \dots, q_n)\) is an orthonormal system.
\end{enumerate}

\begin{enumerate}
\item \(q_1 = \frac{a_1}{\norm{a_1}}, R_{11} = \norm{a_1}\).
\item \(d_2 = a_2 - (a_2^Tq_1)q_1\), \(q_2 = \frac{d_2}{\norm{d_2}}\). \(R_{12} = a_2^Tq_1, R_{22} = \norm{d_2}\).
\end{enumerate}

\begin{algorithm}
  \(q_1 = \frac{a_1}{\norm{a_1}}\)\;
  \(R_{11} = \norm{a_1}\)\;
  \For{\(j = 2\) \KwTo \(n\)}{
    \(d_j = a_j - \sum_{i = 1}^{j - 1} (a_j^Tq_i)q_i\)\;
    \(q_j = \frac{d_j}{\norm{d_j}}\)\;
    \For{\(i \leq j - 1\)}{
      \(R_{ij} = a_j^Tq_i\)\;
    }
    \(R_{jj} = \norm{d_j}\)\;
  }
  \caption{Gram-Schmidt}
\end{algorithm}

\paragraph{Cost of algorithm}

Assume the columns of \(A\) to be linearly independent, at each iteration \(j\) we have to compute \(\sim j\) inner products between vectors in \(\R^m\), so \(O(mj)\) operations at each iteration. Thus the total cost is \(O(m(1 + \dots + n)) = O(mn^2)\).

However, note that this version of Gram-Schmidt is not numerically stable.

Gram-Schmidt is ``triangular orthogonalisation'' process, i.e.\ use triangular operations to put a matrix into orthogonal form. The next two algorithms are instances of ``orthogonal triangularisation'', i.e.\ use orthognal transformations to turn a matrix into a triangular one.

\subsubsection{Givens algorithm}

We seek orthogonal transformations \(\Omega_1, \dots, \Omega_k\) such that \(R = \Omega_k \cdots \Omega_1 A\) is upper triangular. Then \(A = QR\) where \(Q = (\Omega_k \cdots \Omega_1)^T\) is orthogonal.

\paragraph{Givens rotations}

Recall that clockwise rotation through \(\theta\) in \(\R^2\) is given by
\[
  \begin{pmatrix}
    \cos \theta & \sin \theta \\
    -\sin \theta & \cos \theta
  \end{pmatrix}
\]

\begin{definition}[Givens rotation matrix]\index{Givens rotation matrix}
  A \emph{Givens rotation martrix} \(\Omega \in \R^{m \times m}\) is specified by \(1 \leq p < q \leq m\) and \(\theta \in [-\pi, \pi)\) and defined by
  \begin{align*}
    \Omega_{p, p} &= \cos \theta \\
    \Omega_{p, q} &= \sin \theta \\
    \Omega_{q, p} &= -\sin \theta \\
    \Omega_{q, q} &= \cos \theta \\
    \Omega_{i, j} &=
                    \begin{cases}
                      1 & \text{if } i = j \\
                      0 & \text{otherwise}
                    \end{cases}
  \end{align*}
  Denote it as \(\Omega^{[p, q]}\).
\end{definition}

\begin{eg}
  Let \(m = 4\).
  \begin{align*}
    \Omega^{[1, 2]} &=
    \begin{pmatrix}
      \cos \theta & \sin \theta \\
      -\sin \theta & \cos \theta \\
      & & 1 \\
      & & & 1
    \end{pmatrix}
    \\
    \Omega^{[2, 4]} &=
    \begin{pmatrix}
      1 \\
      & \cos \theta & & \sin \theta \\
      & & 1 & \\
      & - \sin \theta & & \sin \theta
    \end{pmatrix}
  \end{align*}
\end{eg}

\blindtext

\begin{theorem}
  Let \(A \in \R^{m \times n}\). Let \(1 \leq p < q \leq m\) and \(j \in \{1, \dots, n\}\). There is a Givens rotation matrix \(\Omega^{[p, q]}\) such that
  \[
    (\Omega^{[p, q]}A)_{q, j} = 0.
  \]
  Furthermore, the rows of \(\Omega^{[p, q]}A\), except for the \(p\)th and \(q\)th row, are identical to those of \(A\). The \(p\)th and \(q\)th rows of \(\Omega^{[p, q]}A\) are linear combinations of the \(p\)th and \(q\)th row of \(A\).
\end{theorem}

\begin{proof}
  \((A_{p, j}, A_{q, j}) \in \R^2\) is a vector and we can find a clockwise rotation through \(\theta\) sending to the direction along postiive \(x\)-axis. \(\theta\) satisfies
  \begin{align*}
    \cos \theta &= \frac{A_{p,j}}{\sqrt{A_{p, j}^2 + A_{q, j}^2}} \\
    \sin \theta &= \frac{A_{q,j}}{\sqrt{A_{p, j}^2 + A_{q, j}^2}}
  \end{align*}
  Then
  \[
    \begin{pmatrix}
      \cos \theta & \sin \theta \\
      -\sin \theta & \cos \theta
    \end{pmatrix}
    \begin{pmatrix}
      A_{p, j} \\
      A_{q, j}
    \end{pmatrix}
    =
    \begin{pmatrix}
      \ast \\
      0
    \end{pmatrix}
  \]
\end{proof}

The \emph{Givens algorithm}\index{Givens algorithm} is given by

\begin{algorithm}
  \For{\(j = 1\) \KwTo \(n\)}{
    \For{\(i = j + 1\) \KwTo \(m\)}{
      Find a Givens rotation such that \((\Omega^{[j, i]}A)_{i, j} = 0\)\;
      \(A := \Omega^{[j, i]}A\)\;
    }
  }
  \caption{Givens algorithm}
\end{algorithm}

At the end of the algorithm, \(A\) is upper triangular. Note that this does not explicitly compute \(Q\). To do so we 

\begin{algorithm}
  \(Q := I\)\;
  \For{\(j = 1\) \KwTo \(n\)}{
    \For{\(i = j + 1\) \KwTo \(m\)}{
      Find a Givens rotation such that \((\Omega^{[j, i]}A)_{i, j} = 0\)\;
      \(A := \Omega^{[j, i]}A\)\;
      \(Q := \Omega^{[j, i]}Q\)\;
    }
  }
  \(Q := Q^T\)\;
  \caption{Givens algorithm, with \(Q\) stored}
\end{algorithm}

But in practice this is rarely necessary. For example in solving linear equations, it suffices to act on the RHS by the \(\Omega\)'s, which can be done so by adding a few lines to the original code.

\subsubsection{Householder algorithm}

The reflection in \(\R^n\) sending a vector \(u\) to \(-u\) is given by
\[
  H = I - 2 \frac{uu^T}{\norm u^2}.
\]
This is called the \emph{Householder reflection matrix}\index{Householder reflection matrix}. We can check that \(H^TH = I\).

Given a matrix \(A\) which we which to use triangularise using relfection matrix, suppose \(v_1\) is the first column, then we want \(Hv_1\) to be a multiple of \(e_1\). In general we are free to choose the sign. If we want it to be in \(+e_1\) direction, choose \(u_1 = a_1 - \norm{a_1}e_1\). Otherwise, choose \(u_1 = a_1 - (-\norm{a_1}e_1)\).

Use notation
\[
  A_{k:m, j} =
  \begin{pmatrix}
    A_{k, j} \\
    \vdots \\
    A_{m, j}
  \end{pmatrix}
  \in \R^{m - k + 1}
\]
Suppose \(A \in \R^{m \times n}, m \geq n\),

\begin{algorithm}
  \For{\(k = 1\) \KwTo \(n\)}{
    \(\tilde a_k = A_{k:m, k} = (A_{k, k}, \dots, A_{m, k})^T\)\;
    \(\tilde u_k = \tilde a_k + \sgn(A_{k, k}) \norm{\tilde a_k} \tilde e_1\)\;
    \For{\(j = k\) \KwTo \(n\)}{
      \(A_{k:m, j} = A_{k:m, j} - 2 \frac{\tilde u^T A_{k:m, j}}{\norm{\tilde u}^2} \tilde u\)\;
    }
  }
  \caption{Householder algorithm}
\end{algorithm}

This algorithm transforms \(A\) into upper triangular form by a series of orthogonal transformations. Like for the Givens algorithm, the matrix \(Q\) is not explicitly. If necessary, we can initialise an identity matrix, left multiply by the matrix operation corresponding to the operation in each inner loop, and finally take the transpose to get \(Q\).

\paragraph{Cost of Householder algorithm}

For each \(k = 1\) to \(n\), and \(j\) from \(k + 1\) to \(n\), we have to compute the inner product \(\tilde u^T A_{k:m, j}\), which has \(m - k + 1 = O(n)\) multiplications. Thus the total cose is \(O(mn^2)\), same as Givens.

\subsection{Least-square problem}

Suppose \(A \in \R^{m \times n}, b \in \R^m\) where \(m \geq n\). We want to find \(x\) such that \(Ax \approx b\). A popular choice is the \emph{least-squares}\index{least-squares approximation} approximation, aiming to minimise \(\norm{Ax - b}^2\).

\begin{theorem}
  \(x\) is a solution to the least-squares problem if and only if
  \[
    A^T(Ax - b) = 0.
  \]
\end{theorem}

The equation is called \emph{normal equation}.

\begin{proof}
  Let
  \[
    f(x) = \norm{Ax - b}^2 = (Ax - b)^T(Ax - b) = x^TA^TAx - 2b^TAx + b^Tb.
  \]
  Then
  \[
    \gradient f(x) = 2A^TAx - 2A^Tb.
  \]
  Thus at optimality we have \(\gradient f(x) = 0\), so \(A^TAx = A^Tb\).

  Since \(f\) is (by assumption) convex, it is also a sufficient condition for optimality.
\end{proof}

Note that \(A^T(Ax - b) = 0\) if and only if \(Ax - b\) is orthogonal to all the columns of \(A\). Suppose
\[
  A = (a_1 \ | \ \cdots \ | \ a_n),
\]
then this is equivalent to \(a_i^T(Ax - b) = 0\) for all \(i\). Geometrically, \(Ax\) is the projection of \(b\) onto the subspace spanned by \(a_1, \dots, a_n\).

Assume \(A = QR\) is a reduce QR factorisation. By definition \(Q\) has orthonormal columns and these columns span the same subspace as the columns of \(A\). Thus
\begin{align*}
  & A^T(Ax - b) = 0 \\
  \iff & Q^T(Ax - b) = 0 \\
  \iff & Q^TAx = Q^Tb \\
  \iff & Rx = Q^Tb
\end{align*}
Check these conditions carefully using column space. The end result is a triangular system that can be solved using back substitution in \(O(n^2)\) operations.

\printindex

\iffalse
http://damtp.cam.ac.uk/user/hf323/L18-IB-NA/
\fi

\end{document}
