\section{Motivation}
\begin{frame}{Motivation}
	\begin{itemize}
		\item $A\in \K^{n\times n}$ self-adjoint, $\K\in \{\R, \C\}$.
		\item Assume that $n$ is very large.
		\item Can we get a handle on $m<n$ Eigenvalues of $A$ without having to calculate all of them?
	\end{itemize}
	\begin{center}
	\textbf{Reduce the dimension of the problem}
	\end{center}
\end{frame}




\section{The Rayleigh-Ritz procedure}
\subsection{Theoretical background}

% \begin{frame}
%   \begin{thm}\label{0.1}
%     Let $A\in \K^{n \times n}$ be a self-adjoint matrix with
%     eigenvalues $\lambda_1 \leq \ldots \leq \lambda_n$ and denote by
%     $X_i$ the set of all $i$-dimensional subspaces of $\K^n$ for
%     $i=1, \ldots, n$. Then, we have:
%		$$\lambda_i = \min_{X^i\subseteq \K^n} \max_{x\in X^i\atop x\neq 0} \frac{\langle x,Ax\rangle }{\langle x,x\rangle},$$
%		where $\langle \cdot, \cdot \rangle$ denotes the
%  Euclidian inner producut and the superscript the dimension of a
%  subspace.
%\end{thm}
%We hope to get a good approximation of $\lambda_i$, if we replace
% $\K^n$ by a subspace $U\subseteq \K^n$.
% \end{frame}
\begin{frame}{Characterization of eigenvectors as invariant subspaces}

  \begin{df}
    A subspace $U\subseteq \mathbb{K}^n$ is called ``invariant'' under
    the operation of $A$, if
    \[
      Au \in U, \quad \forall u \in U .
    \]
  \end{df}
  \pause
  \begin{thm}\label{1.2}
    A subspace $U\subseteq \mathbb{K}^n$ is invariant under the
    operation of $A$ if, and only if, it has a basis of eigenvectors
    of $A$.
  \end{thm}
  \pause
  \begin{center}
    Finding eigenvalues of a symmetric matrix $\Leftrightarrow$
    finding invariant subspaces \note{Elaborate on how the invariant
      subspaces actually determine the eigenpairs}
  \end{center}

\end{frame}
\begin{frame}
  Let $q_1, \ldots, q_k$ form an orthonormal basis of
  $U=\text{span}(q_1, \ldots, q_k)$.
  \begin{align*}
    U \text{ invariant } &\Leftrightarrow Aq_j = \sum_{i=1}^k q_i c_{ij} , \, \forall j=1, \ldots, k \\
                         &\Leftrightarrow R(C):=AQ-QC = 0, \, C\in \K^{\color{red}{k\times k}}, \, Q=(q_1, \ldots, q_k)
  \end{align*}
  \begin{itemize}
  \item Unique solution $C=Q^* AQ$.
  \item Obtain an approximation of the eigenvalues of $A$ from $C$!
  \end{itemize}
\end{frame}
\begin{frame}
  \begin{block}{Eigenvalues}
    If $\lambda$ is an eigenvalue of $C=Q^*AQ$ with eigenvector $y$, we have
    \[
      AQy = QCy = Q\lambda y = \lambda Qy \,.
    \]
    So $Qy$ determines an eigenvector of $A$ with the same eigenvalue.
  \end{block}
  Justify: If $U$ is not invariant, we still get a good approximation
  with the eigenvalues of $C$.
\end{frame}
\begin{frame}{Remark:}
\begin{thm}\label{0.1}
	Let $A\in \K^{n \times n}$ be a self-adjoint matrix with eigenvalues $\lambda_1 \leq \ldots \leq \lambda_n$. Then, we have:
	$$\lambda_i = \min_{X^i\subseteq \K^n} \max_{x\in X^i\atop x\neq 0} \frac{\langle x,Ax\rangle }{\langle x,x\rangle},$$
	where $\langle \cdot, \cdot \rangle$ denotes the Euclidian inner producut and the superscript the dimension of a subspace.
\end{thm}


\end{frame}
\begin{frame}
  \begin{thm}\label{1.5}
	Let $Q$ be an orthonormal basis of a subspace $U\subseteq
	\K^n$. We then have:
	\[
	\min_{X^j\subseteq U} \max_{x\in X^j\atop x\neq 0} \frac{\langle
		x,Ax\rangle }{\langle x,x\rangle} = \lambda_j[Q^*AQ] \,,
	\]
	where the latter denotes the $j$-th eigenvalue of $Q^*AQ$.
\end{thm}
  \begin{thm}\label{1.4}
    Let $R(B) = AQ-QB$ be the residual matrix, $\lVert \cdot \rVert$
    the spectral norm. For a given $n$-by-$m$ $Q$ and $C=Q^*AQ$, we
    have:
    \[
      R(C) \leq R(B), \quad \forall B \in \K^{m \times m}\,.
    \]
  \end{thm}
\end{frame}

\subsection{The algorithm}
\algrenewcommand\algorithmicrequire{\textbf{Input:}}
\algrenewcommand\algorithmicensure{\textbf{Output:}}
\begin{frame}
  \begin{algorithmic}[1]
    \Require $n \times m$ full rank matrix $F$; columns form basis of $U$
    \item[]
    \State Orthonormalize columns of $F$ to compute $Q$
    \State $C = Q^\ast A Q$ \Comment{Matrix Rayleigh quotient of $Q$}
    \State Compute the eigenpairs of $C$: $(g_i, \theta_i)$ \Comment{$\theta$: Ritz values}
    \State Compute $y_i = Q g_i$ \Comment{Ritz vectors}
    \State  $r_i = Ay_i - y_i \theta_i = AQg_i - y_i \theta_i$ and
    $\lVert r_i\rVert$ \Comment{Compute error bounds}
    \item[]
    \Ensure
    \begin{itemize}
    \item[]
    \item Best set of approx. eigenpairs of $A$, which can be obtained
      from $U$
    \item Ritz intervals
      $[\theta_i - \norm{r_i}, \theta_i + \norm{r_i}]$, each of which
      contain an eigenvalue of $A$
    \end{itemize}
	\note{Ideally, they are disjoint}
  \end{algorithmic}
\end{frame}