\documentclass{beamer}
%\documentclass[aspectratio=1610]{beamer}
\mode<presentation>
\usepackage{amsmath}
\usepackage[utf8]{inputenc}
\usepackage{amssymb}
\usecolortheme{default}
\usetheme{Malmoe}
%\usetheme{Frankfurt}
%\usetheme{Berlin}
\usepackage{color}
\definecolor{kek}{rgb}{0.074,0.0988,0.600}

\begin{document}

\title{Cholesky-felbontás }
\author{Sáfár Orsolya}
\date{}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\titlepage
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Elmélet}

\begin{frame}
\frametitle{Cholesky-felbontás}
{\color{kek} Definíció}: Az ${\bf A}\in \mathbb{R}^{n\times n}$ mátrix Cholesky-felbontásának nevezzük az ${\bf A}={\bf U^TU}$ szorzatot, ahol ${\bf U}$ egy olyan felső háromszög-mátrix, amelynek minden diagonálisbeli eleme pozitív.
\medskip

{\color{kek} Tétel}: Egy mátrixnak pontosan akkor létezik Cholesky-felbontása, ha szimmetrikus és pozitív definit. Ha létezik a Cholesky-felbontás, akkor egyértelmű és az alábbi képlettel lehet kiszámítani $\bf{U}$ elemeit: 
\begin{eqnarray}
u_{11}&=&\sqrt{a_{11}}, \textrm{aztán} \quad i=2,\dots, n \textrm{-re:}\\
\nonumber
u_{ij}&=&\left(a_{ij}-\sum\limits_{k=1}^{j-1}u_{ik}u_{jk}\right)/u_{jj}, \quad j=1,\dots,i-1 \\
\nonumber
u_{ii}&=&\sqrt{\strut a_{ii}-\sum\limits_{k=1}^{i-1}u_{ik}^2}
\end{eqnarray}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Bizonyítás}
A létezés igazolásához teljes indukcióval dolgozunk a mátrix mértére.
\begin{itemize} 
\item $i=1$-re ${\bf A}=[a_{11}]$, ahol $a_{11}>0$ ha ${\bf A}$ pozitív definit, és ekkor $[\sqrt{a_{11}}]=[u_{11}]$ tényleg a Cholesky-felbontást adja. 
\item Tegyük fel tehát, hogy $i$-ig igaz az állítás. 
\item Ekkor $i+1$-re:
\end{itemize}
$${\bf A_{i+1}}=\left[
\begin{array}{rr}
{\bf A_i}& {\bf v} \\
{\bf v^T }& \alpha \\
\end{array}
\right]	 $$
alakba írható a mátrix, ahol ${\bf A_i}$ pozitív definit,  ugyanis ${\bf A_{i+1}}$ főminorja. A felírásban kihasználtuk ${\bf A_{i+1}}$ szimmetriáját is, továbbá $\alpha>0$ szintén a pozitív definitségből következik a $(0, \dots, 0, 1)$ vektorral. Másrészt az indukciós feltétel miatt ${\bf A_i}={\bf U_i^T U_i}$, ahol ${\bf U_i}$ felső háromszög mátrix pozitív diagonálissal.
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Bizonyítás - folytatás}
Ezek után keressük ${\bf A_{i+1}}$ felbontását 
$${\bf U_{i+1}}=\left[
\begin{array}{rr}
{\bf U_i} & {\bf u} \\
{\bf 0^T} & \beta \\
\end{array}
\right]	 $$
alakban, ekkor az
$$\left[
\begin{array}{rr}
{\bf U_i^T}& {\bf 0} \\
{\bf u^T} & \beta \\
\end{array}
\right]	
\left[
\begin{array}{rr}
{\bf U_i}& {\bf u} \\
{\bf 0^T} & \beta \\
\end{array}
\right]=\left[
\begin{array}{rr}
{\bf A_i}& {\bf v} \\
{\bf v^T} & \alpha \\
\end{array}
\right] $$
egyenlőségnek kell teljesülnie, azaz ${\bf U_i}^T{\bf u}={\bf v}$ és ${\bf u}^T{\bf u}+\beta^2=\alpha$ adódik.
Innen ${\bf u}$ egyértelmű, mert ${\bf U_i}$ reguláris (hiszen pozitív definit).
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Bizonyítás - folytatás}
Másrészt 
$$0<\det({\bf A_{i+1}})=\det({\bf U_{i+1}})^2=\beta^2\det({\bf U_{i}})^2$$
mutatja, hogy $\beta$ valós, és így $\beta=\sqrt{\strut \alpha-{\bf u^T u}}$. Ekkor a tételben szereplő formula a ${\bf v=U_{i}u}={(a_{1,i}, \dots ,a_{i-1,i} )^T}$ egyenlet megoldásából adódik egyszerű visszahelyettesítéssel.

\bigskip

Továbbá tetszőleges reguláris ${\bf B}\in \mathbb{R}^{n\times n}$-es mátrixra ${\bf B^T B}$ pozitív definit, hiszen ${\bf x^T B^T B x}=||{\bf Bx}||^2_2> 0$ ha ${\bf x}\neq {\bf 0}$, így csakis pozitív definit mátrixnak létezhet Cholesky-felbontása.
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Cholesky-felbontás futásideje}
{\color{kek} Tétel}: A Cholesky-felbontás $\frac{n^2}{3}+{\bf O}(n^2)$ lebegőpontos művelet kiszámításával készíthető el.

\medskip

{\color{kek} Bizonyítás}: Használjuk fel a kiszámításra vonatkozó képleteket!
\begin{eqnarray}
\nonumber
u_{ij}&=&\left(a_{ij}-\sum\limits_{k=1}^{j-1}u_{ik}u_{jk}\right)/u_{jj}, \quad i=2,\dots n, \quad j=1,\dots,i-1 \\
\nonumber
u_{ii}&=&\sqrt{\strut a_{ii}-\sum\limits_{k=1}^{i-1}u_{ik}^2}\quad i=2,\dots n
\end{eqnarray}
$u_{11}$ meghatározása egy művelet, $u_{ij}$-é $1+2(j-1)+1$, végül $u_{ii}$-é $1+1+2(i-1)$. Azaz:
$$1+\sum\limits_{i=2}^n\sum\limits_{j=1}^{i} 2+2j=1+\sum\limits_{i=2}^n(i+2)(i+1)=\frac{n^3}{3}+{\bf O}(n^2)$$
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Tesztek Matlabban}
\begin{frame}
\frametitle{Példa}

{\color{kek} Példa}: Az 
$$\mathrm{\bf A}=\left[
\begin{array}{ccc}
16& -4 & 4 \\
-4 & 10 & -1\\
4 & 1 & 2 \\
\end{array}
\right]	 
$$
mátrix Cholesky-felbontása a \textsf{CholeskyFelbontas(A)} függvénnyel elkészítve:
$$\mathrm{\bf U}=\left[
\begin{array}{rrr}
4& -1 & 1 \\
0 & 3 & 0\\
0 & 0 & 1 \\
\end{array}
\right]	 
$$
és így ${\bf U}^T{\bf U}={\bf A}$.
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
\begin{frame}
\frametitle{A futásidő tesztelése Matlabban}
\begin{center}
\includegraphics[width=5.5cm]{kep1.png}
\end{center}
A futásidőkön látszik, hogy nagy méretű mátrixokra a Cholesky--felbontás elkészítése gyorsabb, mint az LU-felbontásé. Viszont az \textsf{sqrt()} függvény kiszámítása több időt igényel, mint az alapműveletek, ennek hatását látjuk kis méretű mátrixokra.
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}