%\documentclass{beamer} \documentclass[handout]{beamer} %%% produces a handout - ready to print, no frames \setbeamertemplate{navigation symbols}{ \insertslidenavigationsymbol} %keeps or removes navigation symbols \setbeamercolor{navigation symbols dimmed}{fg=blue!75!black} %changes how the bottom \setbeamercolor{navigation symbols}{fg=white!80!white} %navigation symbols look \mode {\usetheme{boxes}} \setbeamertemplate{items}[square] \hypersetup{colorlinks=true,linkcolor=gray} \usepackage{amsbsy,amsfonts} \usepackage{amstext} \usepackage{latexsym,eucal,amsmath,amsthm} \usepackage{amssymb} \usepackage{graphicx} \usepackage{subfigure} \usepackage{hyperref} \newcommand{\blob}{\rule[.2ex]{.9ex}{.9ex} \ } \newcommand{\dd}{\rule[.2ex]{.6ex}{.6ex}} \newcommand{\R}{\mathbb{R}} \newcommand{\norm}[1]{\lVert#1\rVert} % norm \newcommand{\avg}[1]{\left< #1 \right>} % average \newcommand{\sabs}[1]{\left| #1 \right|} % smaller absolute value \newcommand{\abs}[1]{\bigl| #1 \bigr|} % absolute value %\newcommand{\sabs}[1]{\left| #1 \right|} \title{ General Vector Spaces} \author{Silvius Klein} \date{} \vspace{2in} \institute{MA1202 Linear Algebra with Applications} \AtBeginSection[] % "Beamer, do the following at the start of every section" { \begin{frame} \frametitle{Outline} % make a frame titled "Outline" \tableofcontents[currentsection] % show TOC and highlight current section \end{frame} } \begin{document} % this prints title, author etc. info from above %\begin{frame} %\titlepage %\end{frame} \begin{frame} \frametitle{Inner products} \underline{Definition}: An {\em inner product} on a real vector space $V$ is an operation (function) that assigns to each pair of vectors $(\vec{u}, \vec{v})$ in $V$ a \alert{scalar} $\avg{ \vec{u}, \vec{v} }$ satisfying the following axioms: \begin{itemize} \item[1.] $\avg{ \vec{u}, \vec{v} } = \avg{ \vec{v}, \vec{u} } $ \ (Symmetry) \item[2.] $\avg{ \vec{u} + \vec{v}, \vec{w} } = \avg{ \vec{u}, \vec{w} } + \avg{ \vec{v}, \vec{w} }$ \ (Additivity) \item[3.] $\avg{ k \, \vec{u}, \vec{v} } = k \, \avg{ \vec{u}, \vec{v} }$ \ (Homogeneity) \item[4.] $\avg{ \vec{v}, \vec{v} } \, \ge 0$ \ and $\avg{ \vec{v}, \vec{v} } = 0$ iff $\vec{v} = \vec{0}$ \ (Positivity) \end{itemize} \medskip \pause \underline{Theorem} (basic properties): Given vectors $\vec{u}, \vec{v}, \vec{w}$ in an inner product space $V$, and a scalar $k$, the following properties hold: \begin{itemize} \item $\avg{ \vec{\rm{o}}, \vec{v} } = \avg{ \vec{v}, \vec{\rm{o}} } = 0$ \item $\avg{ \vec{u} - \vec{v}, \vec{w} } = \avg{ \vec{u}, \vec{w} } - \avg{ \vec{v}, \vec{w} }$ \item $\avg{ \vec{u}, \vec{v} + \vec{w} } = \avg{ \vec{u}, \vec{v} } + \avg{ \vec{u}, \vec{w} }$ \item $\avg{ \vec{u}, \vec{v} - \vec{w} } = \avg{ \vec{u}, \vec{v} } - \avg{ \vec{u}, \vec{w} }$ \item $\avg{ \vec{u}, k \vec{ v} } = k \, \avg{ \vec{u}, \vec{v} }$ \end{itemize} \end{frame} \begin{frame} \frametitle{Norm and distance in an inner product space} \underline{Definition}: If $V$ is a real inner product space then we define \begin{itemize} \item The norm (or length) of $\vec{v}$: $$\norm{\vec{v}} = \sqrt{ \avg{ \vec{v}, \vec{v} } } $$ \item The distance between $\vec{u}$ and $\vec{v}$: $$ d (\vec{u}, \vec{v}) = \norm{ \vec{u} - \vec{v}} = \sqrt{ \avg{ \vec{u} - \vec{v}, \vec{u} - \vec{v} } } $$ \end{itemize} \medskip \underline{Theorem} (basic properties): Given vectors $\vec{u}, \vec{v}$ in an inner product space $V$, and a scalar $k$, the following properties hold: \begin{itemize} \item $\norm{\vec{v}} \ge 0$ \ and \ $\norm{\vec{v}} = 0$ iff $\vec{v} = \vec{0}$. \item $\norm{ k \vec{v}} = |k| \, \norm{\vec{v}}$ \item $d (\vec{u}, \vec{v}) = d (\vec{v}, \vec{u}) $ \item $d (\vec{u}, \vec{v} ) \ge 0$ \ and \ $d (\vec{u}, \vec{v}) = 0$ iff $\vec{u} = \vec{v}$. \end{itemize} \end{frame} \begin{frame} \frametitle{Angle between vectors} \underline{Theorem} (Cauchy-Schwarz): If $u$ and $v$ are vectors in an inner vector space, then $$\abs{ \avg{u, v} } \le \norm{u} \, \norm{v} $$ \medskip \pause \underline{Definition}: The angle between two vectors $u$ and $v$ in an inner vector space is defined as $$\theta = \cos^{-1} \, \frac{\avg{u,v}}{\norm{u} \, \norm{v}} $$ \medskip \pause \underline{Theorem} (the triangle inequality): If $u, v$ and $w$ are vectors in an inner vector space, then \begin{itemize} \item $\norm{u + v} \le \norm{u} + \norm{v}$ \item $d (u, v) \le d (u, w) + d (w, v)$ \end{itemize} \end{frame} \begin{frame} \frametitle{Orthogonality} \underline{Definition}: Two vectors $u$ and $v$ in an inner vector space are called {\em orthogonal} if $\avg{u, v} = 0$. \smallskip \pause Clearly $u \perp v$ iff the angle between them is $\theta = \frac{\pi}{2}$. \pause \medskip \underline{Theorem} (the Pythagorean theorem): If $u$ and $v$ are \alert{orthogonal} vectors in an inner vector space, then $$\norm{u + v}^2 = \norm{u}^2 + \norm{v}^2$$ \medskip \underline{Definition}: Let $W$ be a subspace of an inner product space $V$. The set of vectors in $V$ which are orthogonal to \alert{every} vector in $W$ is called the {\em orthogonal complement} of $W$ and it is denoted by $W^\perp$. \pause \medskip \underline{Theorem}: The orthogonal complement has the following properties: \begin{itemize} \item $W^\perp$ is a subspace of $V$. \item $W \cap W^\perp = \{ \vec{\rm{o}} \}$. \item If $V$ has finite dimension then $(W^\perp)^\perp = W$. \end{itemize} \end{frame} \begin{frame} \frametitle{Orthogonal sets, orthonormal sets} Let $(V, \avg{ \ })$ be an inner product space and let $S$ be a set of vectors in $V$. \medskip \underline{Definition}: The set $S$ is called {\em orthogonal} if any two vectors in $S$ are orthogonal. The set $S$ is called {\em orthonormal} if it is orthogonal and any vector in $S$ has norm $1$. \medskip \pause \underline{Theorem}: Every orthogonal set of nonzero vectors is linearly independent. \medskip \pause \underline{Definition}: A set of vectors $S$ is called an {\em orthogonal} basis (OGB) for $V$ if $S$ is a basis and an orthogonal set (that is, $S$ is a basis where all vectors are perpendicular). A set of vectors $S$ is called an {\em orthonormal} basis (ONB) for $V$ if $S$ is a basis and an orthonormal set (that is, $S$ is a basis where all vectors are perpendicular and have norm $1$). \end{frame} \begin{frame} \frametitle{Orthogonal sets, orthonormal sets} Let $(V, \avg{ \ })$ be an inner product space. \medskip \underline{Theorem}: If $S = \{ v_1, v_2, \ldots, v_n \}$ is an orthogonal basis in $V$ and $u$ is any vector in $V$, then $$u = \frac{\avg{u, v_1}}{\norm{v_1}^2} \, v_1 + \frac{\avg{u, v_2}}{\norm{v_2}^2} \, v_2 + \ldots + \frac{\avg{u, v_n}}{\norm{v_n}^2} \, v_n$$ If $S = \{ v_1, v_2, \ldots, v_n \}$ is an orthonormal basis in $V$ and $u$ is any vector in $V$, then $$u = \avg{u, v_1} \, v_1 + \avg{u, v_2} \, v_2 + \ldots + \avg{u, v_n} \, v_n$$ \end{frame} \begin{frame} \frametitle{Projection onto a subspace} Let $(V, \avg{ \ })$ be an inner product space. Let $W$ be a finite dimensional subspace. \medskip \underline{Theorem}: If $S = \{ v_1, v_2, \ldots, v_r \}$ is an orthogonal basis in $W$ and $u$ is any vector in $V$, then $${\rm proj}_W \, u = \frac{\avg{u, v_1}}{\norm{v_1}^2} \, v_1 + \frac{\avg{u, v_2}}{\norm{v_2}^2} \, v_2 + \ldots + \frac{\avg{u, v_r}}{\norm{v_r}^2} \, v_r$$ If $S = \{ v_1, v_2, \ldots, v_r \}$ is an orthonormal basis in $W$ and $u$ is any vector in $V$, then $${\rm proj}_W \, u= \avg{u, v_1} \, v_1 + \avg{u, v_2} \, v_2 + \ldots + \avg{u, v_r} \, v_r$$ \end{frame} \begin{frame} \frametitle{Gram-Schmidt process} \underline{Theorem}: Every nonzero finite dimensional inner product space has an orthonormal basis. \bigskip Given a basis $\{ u_1, u_2, \ldots, u_n \}$, to find an orthogonal basis $ \{ v_1, v_2, \ldots, v_n \}$ we use the following procedure: \begin{itemize} \item[Step 1.] $v_1 = u_1$ \item[Step 2.] $v_2 = u_2 - \frac{\avg{u_2, v_1}}{\norm{v_1}^2} \, v_1 $ \item[Step 3.] $v_3 = u_3 - \frac{\avg{u_3, v_1}}{\norm{v_1}^2} \, v_1 - \frac{\avg{u_3, v_2}}{\norm{v_2}^2} \, v_2 $ \item[Step 4.] $v_4 = u_4 - \frac{\avg{u_4, v_1}}{\norm{v_1}^2} \, v_1 - \frac{\avg{u_4, v_2}}{\norm{v_2}^2} \, v_2 - \frac{\avg{u_4, v_3}}{\norm{v_3}^2} \, v_3$ \end{itemize} and so on for $n$ steps, where $n = \dim (V)$. \medskip To obtain an orthonormal basis, we simply normalize the orthogonal basis obtained above. \end{frame} \begin{frame} \frametitle{Formulation of the least squares problem} Given an {\em inconsistent} system $A \, x = b$, find a vector $x$ that comes ''as close as possible" to being a solution. \medskip In other words: find a vector $x$ that {\em minimizes} the distance beyween $b$ and $A \, x$ that is, a vector that minimizes $\norm{ b - A x}$ (with respect to the Euclidian inner product). \medskip We call such a vector $x$ a {\em least squares solution} to the system $A \, x = b$. \medskip We call $b - A x$ the corresponding {\em least squares vector} and $\norm{b - A x}$ the corresponding {\em least squares error}. \medskip \underline{Theorem}: If $x$ is a least squares solution to the inconsistent system $A \, x = b$, and if $W$ is the column space of $A$, then $x$ is a solution to the consistent system $$ A \, x = {\rm proj}_{W} b$$ \medskip \underline{Note:} The above theorem is not always practical, because finding the orthogonal projection ${\rm proj}_{W} b$ may take time (by using Gram-Schmidt). \end{frame} \begin{frame} \frametitle{Solution of the least squares problem} \underline{Theorem:} For every inconsistent system $A \, x = b$, the associated normal system $$A^T A \, x = A^T b$$ is consistent and its solutions are {\em least squares solutions} of $A \, x = b$. \smallskip Moreover, if $W$ is the column space of $A$ and if $x$ is such a least squares solution to $A \, x = b$, then $${\rm proj}_{W} b = A \, x$$ \medskip \underline{Theorem:} For an inconsistent system $A \, x = b$ the following statements are equivalent: \begin{itemize} \item[a)] There is a {\em unique} least squares solution. \item[b)] The columns of $A$ are linearly independent. \item[c)] The matrix $A^T A$ is invertible. \end{itemize} \medskip \underline{Theorem:} If an inconsistent system $A \, x = b$ has a unique least squares solution, then it can be computed as $$x^* = (A^T A)^{-1} A^T b$$ \end{frame} \begin{frame} \frametitle{Function approximation} \underline{Problem}: Given a function $f$ on the interval $[a, b]$, a subspace $W$ of $C [a, b]$, find the {\em best approximation} of $f$ by a function $g$ in $W$. \pause \medskip Best approximation is meant as minimizing the {\em mean square error}, where $$\text{ mean square error } = \int_a^b [ f (x) - g (x) ]^2 \, d x$$ \pause If we consider the (standard) inner product on $C [a, b]$, defined by $$\avg{f_1, f_2} = \int_a^b f_1 (x) \cdot f_2 (x) \, d x$$ and the corresponding norm, then it is easy to see that $$\text{ mean square error } = \avg{f-g, f-g} = \norm{f-g}^2$$ Therefore, the approximation problem can be reformulated as: find a function in $W$ that minimizes $\norm{f-g}^2$. \pause \medskip \underline{Solution:} The best approximation of $f$ by a function in $W$ is $$g = {\rm proj}_W \, f$$ \end{frame} \begin{frame} \frametitle{Fourier series} We want to approximate functions by {\em trigonometric polynomials} of a certain order. In this case, the subspace $W$ is $\textbf{T}_n$, the set of all trigonometric polynomials of order $\le n$. By definition, $$\textbf{T}_n = \text{ span } \{ 1, \cos x, \cos 2 x, \ldots, \cos n x, \sin x, \sin 2 x, \ldots, \sin n x \}$$ \pause The trigonometric functions above that span $\textbf{T}_n$ are {\em orthogonal}, so the set $\{ 1, \cos x, \cos 2 x, \ldots, \cos n x, \sin x, \sin 2 x, \ldots, \sin n x \}$ forms an orthogonal basis in $\textbf{T}_n$. \medskip \pause Therefore, to compute ${\rm proj}_W \, f$, we can use the formula on the slide ``Projection onto a subspace" and we get: \begin{align*} f (x) \approx {\rm proj}_{\textbf{T}_n} \, f = \frac{a_0}{2} & + [a_1 \cos x + a_2 \cos 2 x + \ldots + a_n \cos n x] \\ & + [b_1 \sin x + b_2 \sin 2 x + \ldots + b_n \sin n x] \end{align*} \pause where for $k = 0, 1, \dots, n$, the numbers $a_k$ and $b_k$ are called the {\em Fourier coefficients} of $f$ and they are computed as $$a_k = \frac{1}{\pi} \, \int_0^{2 \pi} f (x) \cos k x \, dx \qquad b_k = \frac{1}{\pi} \, \int_0^{2 \pi} f (x) \sin k x \, dx$$ \end{frame} \end{document}