\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}