\documentclass{beamer}
\usetheme{Boadilla}
%\setbeamertemplate{background canvas}[vertical shading]
%\usepackage{pgfpages}\pgfpagesuselayout{2 on 1}[letterpaper,border shrink=5mm]
\setbeamertemplate{navigation symbols}{}
\setbeamertemplate{footline}{}

\makeatletter
\newenvironment<>{myproof}[1][\proofname]{%
  \par
  \def\insertproofname{#1\@addpunct{.}}%
  \pushQED{\qed}
  \textbf{\insertproofname} }
{\popQED}
\makeatother

\usepackage[utf8]{inputenc}
\usepackage[english,spanish]{babel}
\decimalpoint
\unaccentedoperators

\usepackage{ifthen}
\usepackage{tikz}
\usetikzlibrary{trees,arrows,fadings,mindmap,shapes}
\definecolor{alertboxcolor}{rgb}{1,1,0}
\definecolor{passivenodecolor}{rgb}{0.85,0.85,0.85}
\definecolor{activenodecolor}{rgb}{0.5,0.9,0.5}
\definecolor{greennodecolor}{rgb}{0.7,1.0,0.7}
\definecolor{commentnodecolor}{rgb}{0.6,0.6,0.6}
\definecolor{domaincolor}{rgb}{0.5,0.9,0.5}
\newcommand{\myalert}[1]{\tikz[baseline=(aaa.base)]\node(aaa)[fill=yellow!30,rounded corners=3mm]{#1};}
\newcommand{\myredalert}[1]{\tikz[baseline=(aaa.base)]\node(aaa)[fill=yellow!30,rounded corners=3mm,text=red]{#1};}
\newcommand{\mathalert}[1]{\myalert{\ensuremath{#1}}}

\usepackage{lmodern}
\usepackage{amsmath,mathtools,amssymb}
\usepackage{extarrows}

\usepackage{colortbl}
\newcommand{\Lcell}{\cellcolor[rgb]{0.7,1.0,0.7}}
\definecolor{RobinHoodcolor}{rgb}{0.1,0.7,0.1}

\newcommand{\transformto}[1]{\xrightarrow{\substack{#1}}}

\theoremstyle{definition}
\newtheorem{mydefinition}{Definición}
\newtheorem{myexample}{Ejemplo}
\newtheorem{myexercise}{Ejercicio}
\newtheorem{myproblem}{Problema}
\theoremstyle{remark}
\newtheorem{myobservation}{Observación}

\newcommand{\RealNumbers}{{\mathbb{R}}}
\newcommand{\transposed}[1]{#1^\top}
\newcommand{\matr}[2]{\left[\begin{array}{#1}#2\end{array}\right]}
\newcommand{\eqdef}{\coloneqq}
\newcommand{\medstrut}{\vphantom{\int_{0_0}^{1^1}}}
\newcommand{\bigstrut}{\vphantom{\displaystyle\int}}
\newcommand{\addeq}{\mathop{+=}}

\title{Factorización LU:\\explicación por medio de matrices elementales}
\author{\texorpdfstring{Egor Maximenko,\\con correcciones de Juan Carlos González Rodríguez}{Egor Maximenko, con correcciones de Juan Carlos González Rodríguez}}
\institute[IPN-ESFM, Mexico]{Instituto Polit\'{e}cnico Nacional, ESFM, M\'{e}xico}
\hypersetup{pdfkeywords={factorización; LU; explicación; matrices elementales}}

\newcommand{\mytableofcontents}[1]{
\begin{frame}{Contenido}
\begin{center}
\begin{tikzpicture}
  [outer sep=3pt,ar/.style={line width=2pt,passivenodecolor,>=stealth'},
  pssv/.style={rectangle,rounded corners,minimum size=1cm,text width=3cm,text centered,fill=passivenodecolor},
  actv/.style={rectangle,rounded corners,minimum size=1cm,text width=3cm,text centered,fill=activenodecolor},
  comment/.style={text=commentnodecolor}]
%
\ifthenelse{#1=1}%
{\node (intro) at (-4,3) [actv] {\footnotesize Objetivos\\y requisitos};}%
{\node (intro) at (-4,3) [pssv] {\footnotesize Objetivos\\y requisitos};}
%
\ifthenelse{#1=2}%
{\node (matrelem) at (1,3) [actv] {\footnotesize Matrices\\elementales};}%
{\node (matrelem) at (1,3) [pssv] {\footnotesize Matrices\\elementales};}
%
\ifthenelse{#1=3}%
{\node (robinhood) at (4,1.5) [actv] {\footnotesize Principio de\\Robin Hood};}%
{\node (robinhood) at (4,1.5) [pssv] {\footnotesize Principio de\\Robin Hood};}
%
\ifthenelse{#1=4}%
{\node (alg) at (0,0) [actv] {\footnotesize Deducción\\del algoritmo};}%
{\node (alg) at (0,0) [pssv] {\footnotesize Deducción\\del algoritmo};}
%
\ifthenelse{#1=5}%
{\node (simpl) at (-4,-1.5) [actv] {\footnotesize Notación comprimida};}%
{\node (simpl) at (-4,-1.5) [pssv] {\footnotesize Notación comprimida};}
%
\ifthenelse{#1=6}%
{\node (action) at (-1, -3) [actv] {\footnotesize Algoritmo en acción};}%
{\node (action) at (-1, -3) [pssv] {\footnotesize Algoritmo en acción};}%
%
\ifthenelse{#1=7}%
{\node (problems) at (4, -3) [actv] {\footnotesize Temas para meditar};}%
{\node (problems) at (4, -3) [pssv] {\footnotesize Temas para meditar};}
\draw[->,ar] (intro.east) -- (matrelem.west);
\draw[->,ar] (matrelem.east) to[out=-10,in=120] (robinhood.north);
\draw[->,ar] (robinhood.south) to[out=-120,in=0] (alg.east);
\draw[->,ar] (alg.west) to[out=180,in=60] (simpl.north);
\draw[->,ar] (simpl.south) to[out=-60,in=170] (action.west);
\draw[->,ar] (action.east) -- (problems.west);
\end{tikzpicture}
\end{center}
\end{frame}
}

\begin{document}

\begin{frame}
\maketitle
\end{frame}

\mytableofcontents{0}

\mytableofcontents{1}


\begin{frame}{Objetivo}

Dada una matriz cuadrada $A$,\\
construir un par de matrices cuadradas $L$ y $U$ tales que:
\begin{enumerate}
\item $A=LU$,
\item $L$ es {\color{blue}unitriangular inferior},
\item $U$ es {\color{blue}triangular superior}.
\end{enumerate}

\bigskip
Ejemplo:
\[
\underbrace{
\matr{rrrr}{
 2 &   5 &  -2 &   0 \\
 2 &   4 &  -5 &   4 \\
 8 &  17 & -13 &  14 \\
-2 &  -5 & -14 &  -9
}}_{A}
=\underbrace{
\matr{rrrr}{
\color{blue} 1 & \color{blue}0 & \color{blue} 0 & \color{blue}0 \\
 1 & \color{blue} 1 & \color{blue} 0 & \color{blue} 0 \\
 4 &  3 & \color{blue} 1 & \color{blue} 0 \\
-1 &  0 & -4 & \color{blue} 1
}}_{L}
\;
\underbrace{
\matr{rrrr}{
 2 &  5 & -2 &  0 \\
\color{blue} 0 & -1 & -3 &  4 \\
\color{blue} 0 & \color{blue} 0 &  4 &  2 \\
\color{blue} 0 & \color{blue} 0 & \color{blue} 0 & -1
}}_{U}.
\]
\end{frame}

\begin{frame}{Objetivo}

Vamos a deducir y practicar un algoritmo para construir $L$ y $U$.\\
Con la matriz $A$ de la página anterior el algoritmo funciona así\\
(ahora no lo explicamos):

\begin{align*}
&
\matr{rrrr}{
 2 &   5 &  -2 &   0 \\
 2 &   4 &  -5 &   4 \\
 8 &  17 & -13 &  14 \\
-2 &  -5 & -14 &  -9
}
\transformto{R_2\addeq-R_1\\R_3\addeq-4R_1\\R_4\addeq R_1}
\matr{rrrr}{
 2 &   5 &  -2 &   0 \\
\Lcell 1 &  -1 &  -3 &   4 \\
\Lcell 4 &  -3 &  -5 &  14 \\
\Lcell-1 &   0 & -16 &  -9
}
\\[1ex]
&\transformto{R_3\addeq-3R_2\\(R_4\addeq 0R_2)}
\matr{rrrr}{
 2 &   5 &  -2 &   0 \\
\Lcell 1 &  -1 &  -3 &   4 \\
\Lcell 4 & \Lcell 3 &  4 &   2 \\
\Lcell-1 & \Lcell 0 & -16 &  -9
}
\transformto{R_4\addeq 4R_3}
\matr{rrrr}{
 2 &   5 &  -2 &   0 \\
\Lcell 1 &  -1 &  -3 &   4 \\
\Lcell 4 & \Lcell 3 &  4 &   2 \\
\Lcell-1 & \Lcell 0 & \Lcell-4 &  -1
}.
\end{align*}
\end{frame}


\begin{frame}{Requisitos para comprender bien esta presentación}

\begin{enumerate}
\item Matrices triangulares y sus propiedades.
\item Matrices unitriangulares.
\item Operaciones elementales por renglones de tipo $R_q\addeq \lambda R_p$.
\item Operaciones elementales por columnas de tipo $C_q\addeq \lambda C_p$.
\item Matrices elementales que corresponden a la operación $R_q\addeq \lambda R_p$.
\item Multiplicación por matrices elementales del lado izquierdo.
\item Multiplicación por matrices elementales del lado derecho.
\item Matrices inversas a las matrices elementales.
\end{enumerate}

\medskip
Los ejemplos de esta sección sólo indican los prerrequisitos necesarios\\
y \textbf{no son suficientes} para entrar al tema.

\end{frame}



\mytableofcontents{2}



\begin{frame}{Operación elemental mul-ad por renglones (filas)}

\begin{myexample}
Al primer renglón de la matriz sumarle el tercero multiplicado por $-2$:
\[
\matr{rrr}{
 7 &  1 & -3 \\
-6 &  7 &  4 \\
 4 &  5 & -7
}
\transformto{ R_1 \addeq -2 R_3}
\matr{rrr}{
-1 & -9 & 11 \\
-6 &  7 &  4 \\
 4 &  5 & -7
}.
\]
El tercer renglón no se modifica.
\end{myexample}

\begin{myexample}
A la tercera fila de la matriz sumarle la segunda multiplicada por $7$:
\[
\matr{rrrr}{
-3 & 2 &  1 &  2 \\
 0 & -6 & -7 & -5 \\
-7 & -2 &  4 &  4 \\
 2 & -5 &  2 &  4
}
\transformto{ R_3 \addeq 7R_2 }
\matr{rrrr}{
-3 & 2 &  1 &  2 \\
 0 & -6 & -7 & -5 \\
-7 & -44 & -45 & -31 \\
 2 & -5 &  2 &  4
}.
\]
\end{myexample}

\end{frame}

\begin{frame}{Operación elemental mul-ad por columnas}

\begin{myexample}
A la tercera columna de la matriz sumarle la primera multiplicada por $4$:
\[
\matr{rrr}{
 1 & -7 & -2 \\
-2 & -2 &  6 \\
-5 & -3 &  5
}
\transformto{C_3 \addeq 4C_1}
\matr{rrr}{
 1 & -7 &  2 \\
-2 & -2 & -2 \\
-5 & -3 & -15
}.
\]
\end{myexample}

\begin{myexample}
A la segunda columna de la matriz sumarle la cuarta multiplicada por $-1$:
\[
\matr{rrrr}{
-3 & -6 & -2 & -4 \\
-4 &  1 & -7 & -3 \\
 4 &  3 &  4 &  0 \\
-3 &  2 & -6 & -7
}
\transformto{C_2 \addeq -C_4}
\matr{rrrr}{
-3 & -2 & -2 & -4 \\
-4 &  4 & -7 & -3 \\
 4 &  3 &  4 &  0 \\
-3 &  9 & -6 & -7
}.
\]

\end{myexample}

\end{frame}


\begin{frame}{Matrices elementales}

Se obtienen de la matriz identidad al aplicar una operación elemental.\\
En este tema trabajamos sólo con operaciones elementales de tipo mul-ad.

\begin{myexample}
\[
\underbrace{
\matr{rrr}{
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
}}_{I_3}
\transformto{R_3 \addeq -7 R_1}
\underbrace{
\matr{rrr}{
1 & 0 & 0 \\
0 & 1 & 0 \\
-7 & 0 & 1
}}_{\text{una matriz elemental}}.
\]
\end{myexample}

\begin{myexample}
\[
\underbrace{
\matr{rrrr}{
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1
}}_{I_4}
\transformto{R_2 \addeq 2R_3}
\underbrace{
\matr{rrrr}{
1 & 0 & 0 & 0 \\
0 & 1 & 2 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1
}}_{\text{una matriz elemental}}.
\]
\end{myexample}

\end{frame}

\begin{frame}{Multiplicación por matrices elementales del lado izquierdo}

\[
\underbrace{
\matr{rrr}{
1 & 0 & 0 \\
-3 & 1 & 0 \\
0 & 0 & 1
}}_{E}
\;
\underbrace{
\matr{rrr}{
 6 & -1 &  2 \\
 7 &  2 &  3 \\
 0 & -3 & -2
}}_{A}
=
\underbrace{
\matr{rrr}{
 6 & -1 &  2 \\
-11 &  5 & -3 \\
 0 & -3 & -2
}}_{B}.
\]
Se ve que la matriz $B$ se obtiene de la matriz $A$
al aplicar la operación elemental $R_2\addeq -3 R_1$:
\[
A \transformto{R_2 \addeq -3 R_1} B.
\]
En otras palabras, multiplicar $A$ por $E$ del lado \textbf{izquierdo} fue lo mismo\\
que hacer con los \textbf{renglones} de $A$ la operación elemental $R_2 \addeq -3 R_1$.

\end{frame}

\begin{frame}{Multiplicación por matrices elementales del lado izquierdo}

\begin{myexercise}

\[
\underbrace{
\matr{rrr}{
\visible<2->{1} & \visible<2->{0} & \visible<2->{2} \\
\visible<2->{0} & \visible<2->{1} & \visible<2->{0} \\
\visible<2->{0} & \visible<2->{0} & \visible<2->{1}
}}_{E}
\;
\underbrace{
\matr{rrr}{
 20 & 30 & -30 \\
 3 &  -1 &  7 \\
 -4 & 2 & -5
}}_{A}
=
\underbrace{
\matr{rrr}{
12 & 34 & -40 \\
 3 & -1 & 7 \\
-4 & 2 & -5
}}_{B}.
\]

\medskip

\begin{overlayarea}{\textwidth}{6ex}
\only<1>{
\begin{center}
Antes de pasar a la siguiente página escriba en papel\\
la operación elemental $A\transformto{?}B$ y la matriz $E$.
\end{center}
}
\only<2>{
\begin{center}
$A\transformto{R_1\addeq 2R_3}B$
\end{center}
}
\end{overlayarea}

\end{myexercise}

\end{frame}


\begin{frame}{Multiplicación por matrices elementales del lado derecho}

\[
\underbrace{
\matr{rrrr}{
 3 & -1 & -4 &  6 \\
 1 &  5 &  2 & -3 \\
 4 &  0 &  1 &  6 \\
-2 & -1 &  6 &  2
}}_{A}\;
\underbrace{
\matr{rrrr}{
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 3 & 0 & 1
}}_{E}
=
\underbrace{
\matr{rrrr}{
 3 & 17 & -4 &  6 \\
 1 & -4 &  2 & -3 \\
 4 & 18 &  1 &  6 \\
-2 &  5 &  6 &  2
}}_{B}.
\]
Se ve que
\[
A \transformto{C_2 \addeq 3 C_4} B.
\]
En este ejemplo, multiplicar $A$ por $E$ del lado \textbf{derecho} fue lo mismo\\
que hacer con las \textbf{columnas} de $A$ la operación elemental $C_2 \addeq 3 C_4$.

\end{frame}

\begin{frame}{Multiplicación por matrices elementales del lado derecho}

\begin{myexercise}

\[
\underbrace{
\matr{rrr}{
 -2 & \phantom{-}5 & 40  \\
 1  & 0 & -10 \\
 1  & 2 & 40
}}_{A}\;
\underbrace{
\matr{rrr}{
\visible<2->{\phantom{-}1} & \visible<2->{\phantom{-}0} & \visible<2->{-4} \\
\visible<2->{0} & \visible<2->{1} & \visible<2->{0} \\
\visible<2->{0} & \visible<2->{0} & \visible<2->{1}
}}_{E}
=
\underbrace{
\matr{rrr}{
-2 & \phantom{-}5 & 48 \\
 1 &  0 & -14 \\
 1 &  2 & 36
}}_{B}.
\]

\medskip

\begin{overlayarea}{\textwidth}{6ex}
\only<1>{
\begin{center}
Antes de pasar a la siguiente página escriba en papel\\
la operación elemental $A\transformto{?}B$ y la matriz $E$.
\end{center}
}
\only<2>{
\begin{center}
$A\transformto{C_3\addeq -4C_1}B$
\end{center}
}
\end{overlayarea}

\end{myexercise}

\end{frame}


\begin{frame}{Matrices inversas de las matrices elementales}

\begin{myexample}
\[
E=
\matr{rrr}{
1 & 0 & 0 \\
0 & 1 & 5 \\
0 & 0 & 1
},\qquad
E^{-1}=
\matr{rrr}{
1 & 0 & 0 \\
0 & 1 & -5 \\
0 & 0 & 1
}.
\]\par\smallskip
En efecto, el producto de estas dos matrices es
\[
\matr{ccc}{
1+0+0 & 0+0+0 & 0+0+0 \\
0+1+0 & 0+1+0 & 0-5+5 \\
0+0+0 & 0+0+0 & 0+0+1
}
=I_3.
\]

\end{myexample}

\begin{myexample}
\[
E=
\matr{rrrr}{
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
-2 & 0 & 1 & 0 \\
0 & 0 & 0 & 1
},\qquad
E^{-1}=
\matr{rrrr}{
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
2 & 0 & 1 & 0 \\
0 & 0 & 0 & 1
}.
\]
\end{myexample}

\end{frame}

\begin{frame}{Matrices inversas de las matrices elementales}

\begin{myexercise}
\[
E=
\matr{rrr}{
1 & -4 & \phantom{-}0 \\
0 & 1 & 0 \\
0 & 0 & 1
},\qquad
E^{-1}=
\visible<2->{
\matr{rrr}{
1 & 4 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
}.}
\]
\end{myexercise}

\begin{overlayarea}{\textwidth}{3ex}
\only<1>{Antes de pasar a la siguiente página escriba en papel la matriz $E^{-1}$.}
\end{overlayarea}

\visible<3->{
\begin{myexercise}
\[
E=
\matr{rrrr}{
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 2 & 1
},\qquad
E^{-1}=
\visible<4->{
\matr{rrrr}{
1 & \phantom{-}0 & \phantom{-}0 & \phantom{-}0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & -2 & 1
}.
}
\]
\end{myexercise}
}

\begin{overlayarea}{\textwidth}{3ex}
\only<3>{Antes de pasar a la siguiente página escriba en papel la matriz $E^{-1}$.}
\end{overlayarea}

\end{frame}

\begin{frame}{Matrices inversas de las matrices elementales}

\begin{myexercise}
\[
E=
\matr{rrrr}{
1 & -3 & \phantom{-}0 & \phantom{-}0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1
},\qquad
E^{-1}=
\visible<2->{
\matr{rrrr}{
1 & \phantom{-}3 & \phantom{-}0 & \phantom{-}0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1
}.
}
\]
\end{myexercise}

\begin{overlayarea}{\textwidth}{3ex}
\only<1>{Antes de pasar a la siguiente página escriba en papel la matriz $E^{-1}$.}
\end{overlayarea}

\visible<3->{
\begin{myexercise}
\[
E=
\matr{rrr}{
1 & \phantom{-}0 & \phantom{-}0 \\
0 & 1 & 5 \\
0 & 0 & 1
},\qquad
E^{-1}=
\visible<4->{
\matr{rrr}{
1 & \phantom{-}0 & \phantom{-}0 \\
0 & 1 & -5 \\
0 & 0 & 1
}.}
\]
\end{myexercise}
}

\begin{overlayarea}{\textwidth}{3ex}
\only<3>{Antes de pasar a la siguiente página escriba en papel la matriz $E^{-1}$.}
\end{overlayarea}

\end{frame}


\mytableofcontents{3}

\begin{frame}{Robin Hood del bosque matricial}

En matemáticas se usa frecuentemente una idea que se puede enunciar así:
\begin{center}
{\color{RobinHoodcolor}Quitarle a los ricos y darle a los pobres.}
\end{center}
En forma aditiva esto significa \textit{restar y sumar}, por ejemplo:
\begin{align*}
a+b = a-c+c+b.
\end{align*}
En forma multiplicativa se trata de \textit{dividir y multiplicar}:
\[
X Y = 3X\,\frac{Y}{3}.
\]
En el mundo de matrices, si $E$ es una matriz invertible, entonces 
\[
AB = A I B = A (E^{-1} E) B = (A E^{-1})\,(EB).
\]
\end{frame}


\mytableofcontents{4}



\begin{frame}{Inicio de la deducción del algoritmo}

Vamos a construir una factorización LU de la matriz
\[
A = 
\matr{rrr}{
-4 &  -3 &  1 \\
 8 &  11 & -1 \\
 4 &  18 &  5
}.
\]
En cada paso escribiremos $A$ como un producto $LU$.\\[1ex]
La matriz $L$ siempre será unitriangular inferior.\\[1ex]
La matriz $U$ originalmente no será triangular superior,\\
pero la vamos a convertir en una matriz triangular superior paso a paso.

\end{frame}

\begin{frame}{Hacia el primer paso del algoritmo}

Empezamos con $L=I_3$, $U=A$:
\[
A =
\underbrace{
\matr{rrr}{
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
}}_{L}\;
\underbrace{
\matr{rrr}{
-4 &  -3 &  1 \\
 8 &  11 & -1 \\
 4 &  18 &  5
}}_{U}.
\]
Nótese que:
\begin{itemize}
\item $A=LU$ (así será en cada paso);
\item $L$ es unitriangular inferior;
\item $U$ todavía no es triangular superior.
\end{itemize}

\end{frame}

\begin{frame}{Hacia el primer paso del algoritmo}
\[
A =
\underbrace{
\matr{rrr}{
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
}}_{L}\;
\underbrace{
\matr{rrr}{
-4 &  -3 &  1 \\
 8 &  11 & -1 \\
 4 &  18 &  5
}}_{U}.
\]
Necesitamos convertir $U$ en una matriz triangular superior.\\
Para empezar, podemos eliminar la entrada $U_{2,1}$\\
aplicando la operación elemental $R_2\addeq 2R_1$.

\medskip
Aplicar a los renglones de $U$ la operación elemental $R_2\addeq 2R_1$\\
es lo mismo que multiplicar $U$ del lado izquierdo por la matriz elemental
\[
E =
\matr{rrr}{
1 & 0 & 0 \\
2 & 1 & 0 \\
0 & 0 & 1
}.
\]
\end{frame}


\begin{frame}{Preparamos el primer paso del algoritmo}

\[
A =
\underbrace{
\matr{rrr}{
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
}}_{L}\;
\underbrace{
\matr{rrr}{
-4 &  -3 &  1 \\
 8 &  11 & -1 \\
 4 &  18 &  5
}}_{U}.
\]
Queremos multiplicar $U$ del lado izquierdo por la matriz elemental
\[
E =
\matr{rrr}{
1 & 0 & 0 \\
2 & 1 & 0 \\
0 & 0 & 1
}.
\]
Sería injusto sólo sustituir $U$ por $EU$, pues $A \ne L E U$.\\
Actuando como {\color{RobinHoodcolor}Robin Hood} (quitarle a los ricos y darle a los pobres)\\
metemos el producto $E^{-1} E$ entre $L$ y $U$:
\[
A = L\,U = L\,I_3\,U = L\,(E^{-1} E)\,U = (L E^{-1})\,(E U).
\]
\end{frame}

\begin{frame}{Primer paso del algoritmo}

Metimos el producto $E^{-1}E$ entre $L$ y $U$:
\[
A=
\underbrace{
\matr{rrr}{
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
}}_{L}\;
\underbrace{
\matr{rrr}{
1 & 0 & 0 \\
-2 & 1 & 0 \\
0 & 0 & 1
}}_{E^{-1}}\ \ \ 
\underbrace{
\matr{rrr}{
1 & 0 & 0 \\
2 & 1 & 0 \\
0 & 0 & 1
}}_{E^{\vphantom{-1}}}\;
\underbrace{
\matr{rrr}{
-4 &  -3 &  1 \\
 8 &  11 & -1 \\
 4 &  18 &  5
}}_{U}.
\]
Hay que hacer la operación $R_2\addeq 2R_1$ con los renglones de $U$\\
y la operación $C_1\addeq -2C_2$ con las columnas de $L$:
\[
A=
\underbrace{
\matr{rrr}{
1 & 0 & 0 \\
-2 & 1 & 0 \\
0 & 0 & 1
}}_{L}\;
\underbrace{
\matr{rrr}{
-4 & -3 &  1 \\
 0 &  5 &   1 \\
 4 & 18 &  5
}}_{U}.
\]
Felicidades: acabamos el primer paso del algoritmo.

\end{frame}

\begin{frame}{Un receso después del primer paso del algoritmo}

Hemos llegado a la siguiente descomposición de $A$:
\[
\underbrace{
\matr{rrr}{
-4 &  -3 &  1 \\
 8 &  11 & -1 \\
 4 &  18 &  5
}}_{A}
=
\underbrace{
\matr{rrr}{
1 & 0 & 0 \\
-2 & 1 & 0 \\
0 & 0 & 1
}}_{L}\;
\underbrace{
\matr{rrr}{
-4 & -3 &  1 \\
 0 &  5 &   1 \\
 4 & 18 &  5
}}_{U}.
\]
Notamos que al final del primer paso:
\begin{itemize}
\item $A=LU$ (y es fácil comprobarlo);
\item $L$ es unitriangular inferior;
\item $U$ todavía no es triangular superior,
pero ya hemos eliminado\\una entrada por debajo de la diagonal principal.
\end{itemize}

\end{frame}

\begin{frame}{Hacia el segundo paso del algoritmo}

\[
A
=
\underbrace{
\matr{rrr}{
1 & 0 & 0 \\
-2 & 1 & 0 \\
0 & 0 & 1
}}_{L}\;
\underbrace{
\matr{rrr}{
-4 & -3 &  1 \\
 0 &  5 &   1 \\
 4 & 18 &  5
}}_{U}.
\]
Para eliminar $U_{3,1}$ aplicaremos la operación elemental $R_3\addeq R_1$.\\
Es lo mismo que multiplicar $U$ del lado izquierdo por la matriz elemental
\[
\matr{rrr}{
1 & 0 & 0 \\
0 & 1 & 0 \\
1 & 0 & 1
}.
\]
Para que todo sea justo, al mismo tiempo hay que multiplicar $L$
del lado derecho por la inversa de esta matriz elemental.

\end{frame}

\begin{frame}{Segundo paso del algoritmo}

Metemos entre $L$ y $U$ el producto de una matriz elemental por su inversa:
\[
A=
\underbrace{
\matr{rrr}{
1 & 0 & 0 \\
-2 & 1 & 0 \\
0 & 0 & 1
}}_{L}\;
\matr{rrr}{
1 & 0 & 0 \\
0 & 1 & 0 \\
-1 & 0 & 1
}\qquad
\matr{rrr}{
1 & 0 & 0 \\
0 & 1 & 0 \\
1 & 0 & 1
}\;
\underbrace{
\matr{rrr}{
-4 & -3 &  1 \\
 0 &  5 &   1 \\
 4 & 18 &  5
}}_{U}.
\]
Hacemos la operación $R_3\addeq R_1$ con los renglones de $U$\\
y la operación $C_1\addeq-C_3$ con las columnas de $L$:
\[
A=
\underbrace{
\matr{rrr}{
1 & 0 & 0 \\
-2 & 1 & 0 \\
-1 & 0 & 1
}}_{L}\;
\underbrace{
\matr{rrr}{
-4 & -3 &  1 \\
 0 &  5 &  1 \\
 0 & 15 &  6
}}_{U}.
\]
Se terminó el segundo paso.
\end{frame}

\begin{frame}{Un descanso después del segundo paso}

Hemos llegado a la siguiente descomposición de $A$:
\[
\underbrace{
\matr{rrr}{
-4 &  -3 &  1 \\
 8 &  11 & -1 \\
 4 &  18 &  5
}}_{A}
=
\underbrace{
\matr{rrr}{
1 & 0 & 0 \\
-2 & 1 & 0 \\
-1 & 0 & 1
}}_{L}\;
\underbrace{
\matr{rrr}{
-4 & -3 &  1 \\
 0 &  5 &  1 \\
 0 & 15 &  6
}}_{U}.
\]
Notamos que:
\begin{itemize}
\item $A=LU$ (y es fácil comprobarlo);
\item $L$ es unitriangular inferior;
\item $U$ todavía no es triangular superior,
pero ya hemos eliminado\\dos entradas por debajo de la diagonal principal.
\end{itemize}

\end{frame}

\begin{frame}{Preparamos el tercer paso del algoritmo}
\[
A
=
\underbrace{
\matr{rrr}{
1 & 0 & 0 \\
-2 & 1 & 0 \\
-1 & 0 & 1
}}_{L}\;
\underbrace{
\matr{rrr}{
-4 & -3 &  1 \\
 0 &  5 &  1 \\
 0 & 15 &  6
}}_{U}.
\]
Para eliminar $U_{3,2}$ aplicaremos la operación elemental $R_3\addeq-3R_2$.\\
Es lo mismo que multiplicar $U$ del lado izquierdo por la matriz elemental
\[
\matr{rrr}{
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & -3 & 1
}.
\]
Para que todo sea justo, al mismo tiempo hay que multiplicar $L$
del lado derecho por la inversa de esta matriz elemental.

\end{frame}

\begin{frame}{Tercer paso del algoritmo}
\[
A
=
\underbrace{
\matr{rrr}{
1 & 0 & 0 \\
-2 & 1 & 0 \\
-1 & 0 & 1
}}_{L}\;
\matr{rrr}{
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 3 & 1
}\quad
\matr{rrr}{
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & -3 & 1
}\;
\underbrace{
\matr{rrr}{
-4 & -3 &  1 \\
 0 &  5 &  1 \\
 0 & 15 &  6
}}_{U}.
\]
Hacemos la operación $R_3\addeq -3R_2$ con los renglones de $U$\\
y la operación $C_2\addeq 3C_3$ con las columnas de $L$:
\[
A=
\underbrace{
\matr{rrr}{
1 & 0 & 0 \\
-2 & 1 & 0 \\
-1 & 3 & 1
}}_{L}\;
\underbrace{
\matr{rrr}{
-4 & -3 &  1 \\
 0 &  5 &  1 \\
 0 &  0 &  3
}}_{U}.
\]
\end{frame}

\begin{frame}{Respuesta}

Hemos obtenido la siguiente factorización de $A$:
\[
\underbrace{
\matr{rrr}{
-4 &  -3 &  1 \\
 8 &  11 & -1 \\
 4 &  18 &  5
}}_{A}
=
\underbrace{
\matr{rrr}{
1 & 0 & 0 \\
-2 & 1 & 0 \\
-1 & 3 & 1
}}_{L}\;
\underbrace{
\matr{rrr}{
-4 & -3 &  1 \\
 0 &  5 &  1 \\
 0 &  0 &  3
}}_{U}.
\]
$L$ es unitriangular inferior, $U$ es triangular superior.\\
Es la factorización LU requierida. Falta hacer la comprobación.

\end{frame}

\begin{frame}{Comprobación}

\begin{align*}
LU &=
\matr{rrr}{
1 & 0 & 0 \\
-2 & 1 & 0 \\
-1 & 3 & 1
}
\matr{rrr}{
-4 & -3 &  1 \\
 0 &  5 &  1 \\
 0 &  0 &  3
}
=
\\[1ex]
&=\matr{ccc}{
-4+0+0 & -3+0+0 & 1+0+0 \\
8+0+0 & 6+5+0 & -2+1+0 \\
4+0+0 & 3+15+0 & -1+3+3
}
\\[1ex]
&=
\matr{rrr}{
-4 & -3 &  1 \\
 8 & 11 & -1 \\
 4 & 18 &  5
}
=A.\quad\checkmark
\end{align*}

\end{frame}


\mytableofcontents{5}



\begin{frame}{Omitir las matrices elementales}

Las matrices elementales nos sirvieron para deducir el algoritmo,\\
pero ahora vamos a quitar estos \emph{andamios}.

\bigskip
Para aplicar al factor $U$ la operación $R_q \addeq \lambda R_p$ escribimos $A$ como
\[
A = LU = L (E^{-1} E) U = (L E^{-1}) (E U),
\]
donde $E$ se obtiene de la matriz identidad al poner $\lambda$ en la entrada $(q,p)$.\\
Su matriz inversa $E^{-1}$ se obtiene de $I$ al poner $-\lambda$ en la entrada $(q,p)$.

\bigskip
Multiplicar $L$ del lado derecho por $E^{-1}$ es lo mismo que\\
hacer la operación $C_p \addeq -\lambda C_q$ con las columnas de $L$.

\end{frame}

\begin{frame}{Aplicar operaciones elementales a $U$ y $L$}

\begin{align*}
A&=
\underbrace{
\matr{rrr}{
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
}}_{L}\;
\underbrace{
\matr{rrr}{
-4 &  -3 &  1 \\
 8 &  11 & -1 \\
 4 &  18 &  5
}}_{U}
\begin{array}{l}
U\colon\ R_2\addeq 2R_1,\ R_3\addeq R_1\\
L\colon\ C_1\addeq-2C_2,\ C_1\addeq-C_3
\end{array}
\\
&=
\underbrace{
\matr{rrr}{
1 & 0 & 0 \\
-2 & 1 & 0 \\
-1 & 0 & 1
}}_{L}\;
\underbrace{
\matr{rrr}{
-4 &  -3 &  1 \\
 0 &  5 & 1 \\
 0 &  15 &  6
}}_{U}
\quad
\begin{array}{l}
U\colon\ R_3\addeq -3R_2\\
L\colon\ C_2\addeq 3C_3
\end{array}
\\
&=
\underbrace{
\matr{rrr}{
1 & 0 & 0 \\
-2 & 1 & 0 \\
-1 & 3 & 1
}}_{L}\;
\underbrace{
\matr{rrr}{
-4 &  -3 &  1 \\
 0 &  5 & 1 \\
 0 &  0 &  3
}}_{U}
\end{align*}%
\visible<2->{%
Nótese que es muy fácil aplicar a la matriz $L$ las operaciones indicadas:\\
hay que copiar el coeficiente correspondiente en la posición adecuada.
}
\end{frame}

\begin{frame}{Transformar $U$ y poner coeficientes en $L$}

\begin{align*}
A&=
\underbrace{
\matr{rrr}{
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
}}_{L}\;
\underbrace{
\matr{rrr}{
-4 &  -3 &  1 \\
 8 &  11 & -1 \\
 4 &  18 &  5
}}_{U}
\begin{array}{l}
U\colon\ R_2\addeq 2R_1,\ R_3\addeq R_1\\
L_{2,1}\leftarrow -2,\ L_{3,1}\leftarrow -1
\end{array}
\\
&=
\underbrace{
\matr{rrr}{
1 & 0 & 0 \\
-2 & 1 & 0 \\
-1 & 0 & 1
}}_{L}\;
\underbrace{
\matr{rrr}{
-4 &  -3 &  1 \\
 0 &  5 & 1 \\
 0 &  15 &  6
}}_{U}
\quad
\begin{array}{l}
U\colon\ R_3\addeq -3R_2\\
L_{3,2}\leftarrow 3
\end{array}
\\
&=
\underbrace{
\matr{rrr}{
1 & 0 & 0 \\
-2 & 1 & 0 \\
-1 & 3 & 1
}}_{L}\;
\underbrace{
\matr{rrr}{
-4 &  -3 &  1 \\
 0 &  5 & 1 \\
 0 &  0 &  3
}}_{U}.
\end{align*}%
\visible<2->{%
En cada paso se elimina una entrada de $U$ y se llena una entrada de $L$.\\
Además las entradas diagonales de $L$ siempre son $1$.\\
Vamos a guardar las entradas no triviales de $L$ en la parte inferior de $U$.
}
\end{frame}

\begin{frame}{Notación comprimida para calcular la factorización LU}

Las entradas que corresponden a $L$ están marcadas con verde:
\begin{align*}
A = \matr{rrr}{
-4 &  -3 &  1 \\
 8 &  11 & -1 \\
 4 &  18 &  5
}
\transformto{ R_2\addeq 2R_1 \\R_3\addeq R_1 } &
\matr{rrr}{
-4 &  -3 &  1 \\
\Lcell -2 & 5 & 1 \\
\Lcell -1 & 15 &  6
}
\\[1ex]
\transformto{ R_3\addeq -3R_2 }&
\matr{rrr}{
-4 &  -3 &  1 \\
\Lcell -2 &  5 & 1 \\
\Lcell -1 & \Lcell 3 &  3
}.
\end{align*}
Respuesta:
\[
\underbrace{
\matr{rrr}{
-4 &  -3 &  1 \\
 8 &  11 & -1 \\
 4 &  18 &  5
}}_{A}
=
\underbrace{
\matr{rrr}{
1 & 0 & 0 \\
-2 & 1 & 0 \\
-1 & 3 & 1
}}_{L}\;
\underbrace{
\matr{rrr}{
-4 & -3 &  1 \\
 0 &  5 &  1 \\
 0 &  0 &  3
}}_{U}.
\]

\end{frame}


\mytableofcontents{6}


\begin{frame}{Factorización LU, ejemplo $4\times 4$}

\begin{align*}
A=
\matr{rrrr}{
 3 &  2 &   4 &  -1 \\
-9 & -7 & -14 &   5 \\
 6 &  4 &  10 &  -3 \\
-3 &  0 &  10 &  -7
}
\transformto{R_2\addeq 3R_1\\R_3\addeq-2R_1\\R_4\addeq R_1}
&
\matr{rrrr}{
3 &  2 &  4 &  -1 \\
\Lcell -3 & -1 & -2 &  2 \\
\Lcell  2 &  0 &  2 & -1 \\
\Lcell -1 &  2 & 14 & -8
}
\\[1ex]
\transformto{(R_3\addeq 0R_2)\\R_4\addeq 2R_2}
\matr{rrrr}{
3 &  2 &  4 &  -1 \\
\Lcell -3 & -1 & -2 &  2 \\
\Lcell  2 & \Lcell 0 &  2 & -1 \\
\Lcell -1 & \Lcell -2 & 10 & -4
}
\transformto{R_4\addeq-5R_3}
&
\matr{rrrr}{
3 &  2 &  4 &  -1 \\
\Lcell -3 & -1 & -2 &  2 \\
\Lcell  2 & \Lcell 0 &  2 & -1 \\
\Lcell -1 & \Lcell -2 & \Lcell 5 & 1
}.
\end{align*}
Respuesta:
\[
\underbrace{
\matr{rrrr}{
 3 &  2 &   4 &  -1 \\
-9 & -7 & -14 &   5 \\
 6 &  4 &  10 &  -3 \\
-3 &  0 &  10 &  -7
}}_{A}
=
\underbrace{
\matr{rrrr}{
 1 &  0 &  0 &  0 \\
-3 &  1 &  0 &  0 \\
 2 &  0 &  1 &  0 \\
-1 & -2 &  5 &  1
}}_{L}\;
\underbrace{
\matr{rrrr}{
 3 &  2 &  4 & -1 \\
 0 & -1 & -2 &  2 \\
 0 &  0 &  2 & -1 \\
 0 &  0 &  0 &  1
}}_{U}.
\]

\end{frame}

\begin{frame}{Comprobación}

\begin{align*}
LU
&=
\matr{rrrr}{
 1 &  0 &  0 &  0 \\
-3 &  1 &  0 &  0 \\
 2 &  0 &  1 &  0 \\
-1 & -2 &  5 &  1
}\;
\matr{rrrr}{
 3 &  2 &  4 & -1 \\
 0 & -1 & -2 &  2 \\
 0 &  0 &  2 & -1 \\
 0 &  0 &  0 &  1
}
\\[1ex]
&=
\matr{c|c|c|c}{
 3 &  2 &  4 & -1 \\\hline
-9 & -6-1 &  -12-2 & 3+2 \\\hline
 6 & 4+0 & 8+0+2 & -2+0-1 \\\hline
 -3 & -2+2 & -4+4+10 & 1-4-5+1
}
\\[1ex]
&=
\matr{rrrr}{
 3 &  2 &   4 &  -1 \\
-9 & -7 & -14 &   5 \\
 6 &  4 &  10 &  -3 \\
-3 &  0 &  10 &  -7
}
=A.\quad\checkmark
\end{align*}

\end{frame}

\begin{frame}{}
\begin{center}
Para aprender a jugar fútbol,\\
no es suficiente sólo ver partidos por la tele.
\end{center}
\par\bigskip
\begin{center}
\"{U}bung macht den Meister.\\
La práctica convierte uno al maestro.
\end{center}
\end{frame}


\begin{frame}{Ejercicios}

Aplicar el algoritmo de factorización LU (en la notación comprimida)\\
a cada una de las siguientes cuatro matrices.
Hacer las comprobaciones.
\begin{align*}
&
\matr{rrr}{
-3 &  2 &   5 \\
 9 & -5 & -11 \\
-6 &  5 &   9
},
&
&
\matr{rrrr}{
 -3 &   1 &   5 &   1 \\
  9 &  -4 &  -9 &   1 \\
 -3 &   2 &   0 &  -1 \\
  6 &  -5 &   9 &  16
},
\\[2ex]
&
\matr{rrr}{
 3 &  1 & -2 \\
 4 &  1 &  1 \\
-6 & -2 & -1
},
&
&
\matr{rrr}{
1/2 & 0 & -1/2 \\
-1/4 & -1 & -1/4 \\
3/4 & -2 & 1/4
}.
\end{align*}
En los últimos dos ejercicios las respuestas son fraccionarias.

\end{frame}


\mytableofcontents{7}


\begin{frame}{Ejemplo de una matriz que no tiene factorización LU}

\begin{myproblem}
Demostrar que la matriz
\[
A = \matr{rr}{ 0 & 5 \\ 2 & -3 }
\]
no tiene ninguna factorización LU.
\end{myproblem}

\bigskip
Sugerencias: suponer que
\[
\underbrace{
\matr{cc}{ 1 & 0 \\ x & 1 }
}_{L}\;
\underbrace{
\matr{cc}{ u & v \\ 0 & w }
}_{U}
= \matr{rr}{ 0 & 5 \\ 2 & -3 },
\]
escribir cuatro ecuaciones ($1\cdot u+0\cdot 0=0$, etc.),\\
analizar el sistema obtenido y mostrar que es inconsistente.

\end{frame}

\begin{frame}{Unicidad de la factorización LU}

\begin{myproblem}
Supongamos que $A$ es una matriz cuadrada invertible y
\[
A = L_1 U_1 = L_2 U_2,
\]
donde $L_1$ y $L_2$ son unitriangulares inferiores,\\
$U_1$ y $U_2$ son triangulares superiores.\\[2ex]
Demostrar que $L_1=L_2$ y $U_1=U_2$.
\end{myproblem}

Sugerencias:
\begin{itemize}
\item \emph{Separar moscas de tacos}: transformar la igualdad $L_1 U_1=L_2 U_2$\\
de tal manera que las $L$s se junten en un lado y las $U$s en el otro.
\item Pensar en el producto y en las inversas de matrices triangulares.\\
\item Pensar en la intersección de la clases de matrices unitriangulares inferiores
con la clase de matrices triangulares superiores.
\end{itemize}
\end{frame}

\begin{frame}{Criterio de existencia de una factorización LU}

\begin{myproblem}
Sea $A$ una matriz cuadrada de orden $n$.\\
Demostrar que las siguientes dos condiciones son equivalentes:
\begin{itemize}
\item[(a)] $A$ posee una factorización LU con entradas diagonales de $U$ no nulas;
\item[(b)] para cada $p\in\{1,\ldots,n\}$,
$\det(A_{\{1,\ldots,p\},\{1,\ldots,p\}})\ne0$.
\end{itemize}
\end{myproblem}

\begin{overlayarea}{\textwidth}{29ex}
\only<1>{
En la condición (b) se trata de los \emph{menores principales líderes} de $A$,\\
llamados también \emph{menores de esquina}. Por ejemplo, si $n=4$, $p=2$,
\[
A=\matr{cccc}{
A_{1,1} & A_{1,2} & A_{1,3} & A_{1,4} \\
A_{2,1} & A_{2,2} & A_{2,3} & A_{2,4} \\
A_{3,1} & A_{3,2} & A_{3,3} & A_{3,4} \\
A_{4,1} & A_{4,2} & A_{4,3} & A_{4,4}
},\quad
\det(A_{\{1,2\},\{1,2\}}) =
\left|
\begin{array}{cc}
A_{1,1} & A_{1,2} \\
A_{2,1} & A_{2,2}
\end{array}
\right|.
\]
}
\only<2>{
Sugerencias:
\begin{itemize}
\item Para la implicación (a)$\Rightarrow$(b), mostrar que
\[
A_{\{1,\ldots,p\},\{1,\ldots,p\}}=
L_{\{1,\ldots,p\},\{1,\ldots,p\}}
U_{\{1,\ldots,p\},\{1,\ldots,p\}}.
\]
\item Para la implicación (b)$\Rightarrow$(a),
mostrar que las operaciones elementales del tipo $R_q\addeq\lambda R_p$ con $q>p$ no cambiar los menores
\[
\det(A_{\{1,\ldots,p\},\{1,\ldots,p\}}),
\]
y en el inicio del paso $p$ la entrada $(p,p)$ de $A$ es distinta de cero.
\end{itemize}
}
\end{overlayarea}

\end{frame}


\end{document}

