{"id":5301,"date":"2016-02-12T17:26:38","date_gmt":"2016-02-12T16:26:38","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5301"},"modified":"2016-02-13T11:27:34","modified_gmt":"2016-02-13T10:27:34","slug":"i1m2015-metodo-de-gauss-para-triangularizar-matrices","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2015-metodo-de-gauss-para-triangularizar-matrices\/","title":{"rendered":"I1M2015: M\u00e9todo de Gauss para triangularizar matrices"},"content":{"rendered":"<p>En la segunda parte de la clase hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-15\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentado las soluciones de los ejercicios de la relaci\u00f3n 18 cuyo objetivo es la triangularizaci\u00f3n de matrices por el m\u00e9todo de Gauss.<\/p>\n<p>Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- Introducci\u00f3n                                                       --\n-- ---------------------------------------------------------------------\n\n-- El objetivo de esta relaci\u00f3n es definir el m\u00e9todo de Gauss para\n-- triangularizar matrices.\n\n-- Adem\u00e1s, en algunos ejemplos de usan matrices con n\u00fameros racionales.\n-- En Haskell, el n\u00famero racional x\/y se representa por x%y. El TAD de\n-- los n\u00fameros racionales est\u00e1 definido en el m\u00f3dulo Data.Ratio.\n \n-- ---------------------------------------------------------------------\n-- Importaci\u00f3n de librer\u00edas                                           --\n-- ---------------------------------------------------------------------\n\nimport Data.Array\nimport Data.Ratio\n\n-- ---------------------------------------------------------------------\n-- Tipos de los vectores y de las matrices                            --\n-- ---------------------------------------------------------------------\n\n-- Los vectores son tablas cuyos \u00edndices son n\u00fameros naturales.\ntype Vector a = Array Int a\n \n-- Las matrices son tablas cuyos \u00edndices son pares de n\u00fameros\n-- naturales. \ntype Matriz a = Array (Int,Int) a\n\n-- ---------------------------------------------------------------------\n-- Funciones auxiliares                                               --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Definir la funci\u00f3n\n--    listaMatriz :: Num a => [[a]] -> Matriz a\n-- tal que (listaMatriz xss) es la matriz cuyas filas son los elementos\n-- de xss. Por ejemplo,\n--    ghci> listaMatriz [[1,3,5],[2,4,7]]\n--    array ((1,1),(2,3)) [((1,1),1),((1,2),3),((1,3),5),\n--                         ((2,1),2),((2,2),4),((2,3),7)]\n-- --------------------------------------------------------------------\n\nlistaMatriz :: Num a => [[a]] -> Matriz a\nlistaMatriz xss = listArray ((1,1),(m,n)) (concat xss)\n    where m = length xss\n          n = length (head xss)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir la funci\u00f3n\n--    separa :: Int -> [a] -> [[a]]\n-- tal que (separa n xs) es la lista obtenida separando los elementos de\n-- xs en grupos de n elementos (salvo el \u00faltimo que puede tener menos de\n-- n elementos). Por ejemplo, \n--    separa 3 [1..11]  ==  [[1,2,3],[4,5,6],[7,8,9],[10,11]]\n-- ---------------------------------------------------------------------\n\nsepara :: Int -> [a] -> [[a]]\nsepara _ [] = []\nsepara n xs = take n xs : separa n (drop n xs)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Definir la funci\u00f3n\n--    matrizLista :: Num a => Matriz a -> [[a]]\n-- tal que (matrizLista x) es la lista de las filas de la matriz x. Por\n-- ejemplo, \n--    ghci> let m = listaMatriz [[5,1,0],[3,2,6]]\n--    ghci> m\n--    array ((1,1),(2,3)) [((1,1),5),((1,2),1),((1,3),0),\n--                         ((2,1),3),((2,2),2),((2,3),6)]\n--    ghci> matrizLista m\n--    [[5,1,0],[3,2,6]]\n-- ---------------------------------------------------------------------\n\nmatrizLista :: Num a => Matriz a -> [[a]]\nmatrizLista p = separa (numColumnas p) (elems p)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Definir la funci\u00f3n\n--    numFilas :: Num a => Matriz a -> Int\n-- tal que (numFilas m) es el n\u00famero de filas de la matriz m. Por\n-- ejemplo,\n--    numFilas (listaMatriz [[1,3,5],[2,4,7]])  ==  2\n-- ---------------------------------------------------------------------\n\nnumFilas :: Num a => Matriz a -> Int\nnumFilas = fst . snd . bounds\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. Definir la funci\u00f3n\n--    numColumnas :: Num a => Matriz a -> Int\n-- tal que (numColumnas m) es el n\u00famero de columnas de la matriz\n-- m. Por ejemplo,\n--    numColumnas (listaMatriz [[1,3,5],[2,4,7]])  ==  3\n-- ---------------------------------------------------------------------\n\nnumColumnas:: Num a => Matriz a -> Int\nnumColumnas = snd . snd . bounds\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6. Definir la funci\u00f3n\n--    dimension :: Num a => Matriz a -> (Int,Int)\n-- tal que (dimension m) es la dimensi\u00f3n de la matriz m. Por ejemplo, \n--    dimension (listaMatriz [[1,3,5],[2,4,7]])  ==  (2,3)\n-- ---------------------------------------------------------------------\n\ndimension :: Num a => Matriz a -> (Int,Int)\ndimension p = (numFilas p, numColumnas p)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7. Definir la funci\u00f3n\n--    diagonalPral :: Num a => Matriz a -> Vector a\n-- tal que (diagonalPral p) es la diagonal principal de la matriz p. Por\n-- ejemplo, \n--    ghci> let p = listaMatriz [[5,1,0],[3,2,6]]\n--    ghci> diagonalPral p\n--    array (1,2) [(1,5),(2,2)]\n--    ghci> elems (diagonalPral p)\n--    [5,2]\n-- ---------------------------------------------------------------------\n\ndiagonalPral :: Num a => Matriz a -> Vector a\ndiagonalPral p = array (1,n) [(i,p!(i,i)) | i <- [1..n]]\n    where n = min (numFilas p) (numColumnas p)\n\n-- ---------------------------------------------------------------------\n-- Transformaciones elementales                                       --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8. Definir la funci\u00f3n\n--    intercambiaFilas :: Num a => Int -> Int -> Matriz a -> Matriz a\n-- tal que (intercambiaFilas k l p) es la matriz obtenida intercambiando\n-- las filas k y l de la matriz p. Por ejemplo, \n--    ghci> let p = listaMatriz [[5,1,0],[3,2,6],[4,6,9]]\n--    ghci> intercambiaFilas 1 3 p\n--    array ((1,1),(3,3)) [((1,1),4),((1,2),6),((1,3),9),\n--                         ((2,1),3),((2,2),2),((2,3),6),\n--                         ((3,1),5),((3,2),1),((3,3),0)]\n--    ghci> matrizLista (intercambiaFilas 1 3 p)\n--    [[4,6,9],[3,2,6],[5,1,0]]\n-- ---------------------------------------------------------------------\n\nintercambiaFilas :: Num a => Int -> Int -> Matriz a -> Matriz a\nintercambiaFilas k l p = \n    array ((1,1), (m,n))\n          [((i,j), p! f i j) | i <- [1..m], j <- [1..n]]\n    where (m,n) = dimension p\n          f i j | i == k    = (l,j)\n                | i == l    = (k,j)\n                | otherwise = (i,j)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9. Definir la funci\u00f3n\n--    intercambiaColumnas :: Num a => Int -> Int -> Matriz a -> Matriz a\n-- tal que (intercambiaColumnas k l p) es la matriz obtenida\n-- intercambiando las columnas k y l de la matriz p. Por ejemplo, \n--    ghci> let p = listaMatriz [[5,1,0],[3,2,6],[4,6,9]]\n--    ghci> matrizLista (intercambiaColumnas 1 3 p)\n--    [[0,1,5],[6,2,3],[9,6,4]]\n-- ---------------------------------------------------------------------\n\nintercambiaColumnas :: Num a => Int -> Int -> Matriz a -> Matriz a\nintercambiaColumnas k l p = \n    array ((1,1), (m,n))\n          [((i,j), p ! f i j) | i <- [1..m], j <- [1..n]]\n    where (m,n) = dimension p\n          f i j | j == k    = (i,l)\n                | j == l    = (i,k)\n                | otherwise = (i,j)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10. Definir la funci\u00f3n\n--    multFilaPor :: Num a => Int -> a -> Matriz a -> Matriz a\n-- tal que (multFilaPor k x p) es a matriz obtenida multiplicando la\n-- fila k de la matriz p por el n\u00famero x. Por ejemplo,\n--    ghci> let p = listaMatriz [[5,1,0],[3,2,6],[4,6,9]]\n--    ghci> matrizLista (multFilaPor 2 3 p)\n--    [[5,1,0],[9,6,18],[4,6,9]]\n-- ---------------------------------------------------------------------\n\nmultFilaPor :: Num a => Int -> a -> Matriz a -> Matriz a\nmultFilaPor k x p = \n    array ((1,1), (m,n))\n          [((i,j), f i j)  | i <- [1..m], j <- [1..n]]\n    where (m,n) = dimension p\n          f i j | i == k    = x*(p!(i,j))\n                | otherwise = p!(i,j)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 11. Definir la funci\u00f3n\n--    sumaFilaFila :: Num a => Int -> Int -> Matriz a -> Matriz a\n-- tal que (sumaFilaFila k l p) es la matriz obtenida sumando la fila l\n-- a la fila k d la matriz p. Por ejemplo,\n--    ghci> let p = listaMatriz [[5,1,0],[3,2,6],[4,6,9]]\n--    ghci> matrizLista (sumaFilaFila 2 3 p)\n--    [[5,1,0],[7,8,15],[4,6,9]]\n-- ---------------------------------------------------------------------\n\nsumaFilaFila :: Num a => Int -> Int -> Matriz a -> Matriz a\nsumaFilaFila k l p = \n    array ((1,1), (m,n))\n          [((i,j), f i j) | i <- [1..m], j <- [1..n]]\n    where (m,n) = dimension p\n          f i j | i == k    = p!(i,j) + p!(l,j)\n                | otherwise = p!(i,j)        \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 12. Definir la funci\u00f3n\n--    sumaFilaPor :: Num a => Int -> Int -> a -> Matriz a -> Matriz a\n-- tal que (sumaFilaPor k l x p) es la matriz obtenida sumando a la fila\n-- k de la matriz p la fila l multiplicada por x. Por ejemplo,\n--    ghci> let p = listaMatriz [[5,1,0],[3,2,6],[4,6,9]]\n--    ghci> matrizLista (sumaFilaPor 2 3 10 p)\n--    [[5,1,0],[43,62,96],[4,6,9]]\n-- ---------------------------------------------------------------------\n\nsumaFilaPor :: Num a => Int -> Int -> a -> Matriz a -> Matriz a\nsumaFilaPor k l x p = \n    array ((1,1), (m,n))\n          [((i,j), f i j) | i <- [1..m], j <- [1..n]]\n    where (m,n) = dimension p\n          f i j | i == k    = p!(i,j) + x*p!(l,j)\n                | otherwise = p!(i,j)\n\n-- ---------------------------------------------------------------------\n-- Triangularizaci\u00f3n de matrices                                      --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 13. Definir la funci\u00f3n\n--    buscaIndiceDesde :: (Num a, Eq a) => \n--                        Matriz a -> Int -> Int -> Maybe Int\n-- tal que (buscaIndiceDesde p j i) es el menor \u00edndice k, mayor o igual\n-- que i, tal que el elemento de la matriz p en la posici\u00f3n (k,j) es no\n-- nulo. Por ejemplo,\n--    ghci> let p = listaMatriz [[5,1,0],[3,2,6],[4,6,9]]\n--    ghci> buscaIndiceDesde p 3 2\n--    Just 2\n--    ghci> let q = listaMatriz [[5,1,1],[3,2,0],[4,6,0]]\n--    ghci> buscaIndiceDesde q 3 2\n--    Nothing\n-- ---------------------------------------------------------------------\n\nbuscaIndiceDesde :: (Num a, Eq a) => Matriz a -> Int -> Int -> Maybe Int\nbuscaIndiceDesde p j i \n    | null xs   = Nothing\n    | otherwise = Just (head xs)\n    where xs = [k | ((k,j'),y) <- assocs p, j == j', y \/= 0, k>=i] \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 14. Definir la funci\u00f3n\n--    buscaPivoteDesde :: (Num a, Eq a) => \n--                        Matriz a -> Int -> Int -> Maybe a\n-- tal que (buscaPivoteDesde p j i) es el elemento de la matriz p en la\n-- posici\u00f3n (k,j) donde k es (buscaIndiceDesde p j i). Por ejemplo,\n--    ghci> let p = listaMatriz [[5,1,0],[3,2,6],[4,6,9]]\n--    ghci> buscaPivoteDesde p 3 2\n--    Just 6\n--    ghci> let q = listaMatriz [[5,1,1],[3,2,0],[4,6,0]]\n--    ghci> buscaPivoteDesde q 3 2\n--    Nothing\n-- ---------------------------------------------------------------------\n\nbuscaPivoteDesde :: (Num a, Eq a) => Matriz a -> Int -> Int -> Maybe a\nbuscaPivoteDesde p j i \n    | null xs   = Nothing\n    | otherwise = Just (head xs)\n    where xs = [y | ((k,j'),y) <- assocs p, j == j', y \/= 0, k>=i] \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 15. Definir la funci\u00f3n\n--    anuladaColumnaDesde :: (Num a, Eq a) => \n--                           Int -> Int -> Matriz a -> Bool\n-- tal que (anuladaColumnaDesde j i p) se verifica si todos los\n-- elementos de la columna j de la matriz p desde i+1 en adelante son\n-- nulos. Por ejemplo,\n--    ghci> let q = listaMatriz [[5,1,1],[3,2,0],[4,6,0]]\n--    ghci> anuladaColumnaDesde q 3 2\n--    True\n--    ghci> let p = listaMatriz [[5,1,0],[3,2,6],[4,6,9]]\n--    ghci> anuladaColumnaDesde p 3 2\n--    False\n-- ---------------------------------------------------------------------\n\nanuladaColumnaDesde :: (Num a, Eq a) => Matriz a -> Int -> Int -> Bool\nanuladaColumnaDesde p j i = \n    buscaIndiceDesde p j (i+1) == Nothing\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 16. Definir la funci\u00f3n\n--    anulaEltoColumnaDesde :: (Fractional a, Eq a) => \n--                             Matriz a -> Int -> Int -> Matriz a\n-- tal que (anulaEltoColumnaDesde p j i) es la matriz obtenida a partir\n-- de p anulando el primer elemento de la columna j por debajo de la\n-- fila i usando el elemento de la posici\u00f3n (i,j). Por ejemplo,\n--    ghci> let p = listaMatriz [[2,3,1],[5,0,5],[8,6,9]] :: Matriz Double\n--    ghci> matrizLista (anulaEltoColumnaDesde p 2 1)\n--    [[2.0,3.0,1.0],[5.0,0.0,5.0],[4.0,0.0,7.0]]\n-- ---------------------------------------------------------------------\n\nanulaEltoColumnaDesde :: (Fractional a, Eq a) => \n                         Matriz a -> Int -> Int -> Matriz a\nanulaEltoColumnaDesde p j i = \n    sumaFilaPor l i (-(p!(l,j)\/a)) p\n    where Just l = buscaIndiceDesde p j (i+1)\n          a      = p!(i,j)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 17. Definir la funci\u00f3n\n--    anulaColumnaDesde :: (Fractional a, Eq a) => \n--                         Matriz a -> Int -> Int -> Matriz a\n-- tal que (anulaColumnaDesde p j i) es la matriz obtenida anulando\n-- todos los elementos de la columna j de la matriz p por debajo del la\n-- posici\u00f3n (i,j) (se supone que el elemnto p_(i,j) es no nulo). Por\n-- ejemplo, \n--    ghci> let p = listaMatriz [[2,2,1],[5,4,5],[10,8,9]] :: Matriz Double\n--    ghci> matrizLista (anulaColumnaDesde p 2 1)\n--    [[2.0,2.0,1.0],[1.0,0.0,3.0],[2.0,0.0,5.0]]\n--    ghci> let p = listaMatriz [[4,5],[2,7%2],[6,10]] \n--    ghci> matrizLista (anulaColumnaDesde p 1 1)\n--    [[4 % 1,5 % 1],[0 % 1,1 % 1],[0 % 1,5 % 2]]\n-- ---------------------------------------------------------------------\n\nanulaColumnaDesde :: (Fractional a, Eq a) => \n                     Matriz a -> Int -> Int -> Matriz a\nanulaColumnaDesde p j i\n    | anuladaColumnaDesde p j i = p\n    | otherwise = anulaColumnaDesde (anulaEltoColumnaDesde p j i) j i \n\n-- ---------------------------------------------------------------------\n-- Algoritmo de Gauss para triangularizar matrices                    --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 18. Definir la funci\u00f3n\n--    elementosNoNulosColDesde :: (Num a, Eq a) => \n--                                Matriz a -> Int -> Int -> [a]\n-- tal que (elementosNoNulosColDesde p j i) es la lista de los elementos\n-- no nulos de la columna j a partir de la fila i. Por ejemplo,\n--    ghci> let p = listaMatriz [[3,2],[5,1],[0,4]]\n--    ghci> elementosNoNulosColDesde p 1 2\n--    [5]\n-- ---------------------------------------------------------------------\n\nelementosNoNulosColDesde :: (Num a, Eq a) => Matriz a -> Int -> Int -> [a]\nelementosNoNulosColDesde p j i = \n    [x | ((k,j'),x) <- assocs p, x \/= 0, j' == j, k >= i]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 19. Definir la funci\u00f3n\n--    existeColNoNulaDesde :: (Num a, Eq a) => \n--                            Matriz a -> Int -> Int -> Bool\n-- tal que (existeColNoNulaDesde p j i) se verifica si la matriz p tiene\n-- una columna a partir de la j tal que tiene alg\u00fan elemento no nulo por\n-- debajo de la fila i; es decir, si la submatriz de p obtenida\n-- eliminando las i-1 primeras filas y las j-1 primeras columnas es no\n-- nula. Por ejemplo, \n--    ghci> let p = listaMatriz [[3,2,5],[5,0,0],[6,0,0]]\n--    ghci> existeColNoNulaDesde p 2 2\n--    False\n--    ghci> let q = listaMatriz [[3,2,5],[5,7,0],[6,0,0]]\n--    ghci> existeColNoNulaDesde q 2 2\n-- ---------------------------------------------------------------------\n  \nexisteColNoNulaDesde :: (Num a, Eq a) => Matriz a -> Int -> Int -> Bool\nexisteColNoNulaDesde p j i = \n    or [not (null (elementosNoNulosColDesde p l i)) | l <- [j..n]]\n    where n = numColumnas p\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 20. Definir la funci\u00f3n\n--    menorIndiceColNoNulaDesde :: (Num a, Eq a) => \n--                                 Matriz a -> Int -> Int -> Maybe Int\n-- tal que (menorIndiceColNoNulaDesde p j i) es el \u00edndice de la primera\n-- columna, a partir de la j, en el que la matriz p tiene un elemento no\n-- nulo a partir de la fila i. Por ejemplo,\n--    ghci> let p = listaMatriz [[3,2,5],[5,7,0],[6,0,0]]\n--    ghci> menorIndiceColNoNulaDesde p 2 2\n--    Just 2\n--    ghci> let q = listaMatriz [[3,2,5],[5,0,0],[6,0,2]]\n--    ghci> menorIndiceColNoNulaDesde q 2 2\n--    Just 3\n--    ghci> let r = listaMatriz [[3,2,5],[5,0,0],[6,0,0]]\n--    ghci> menorIndiceColNoNulaDesde r 2 2\n--    Nothing\n-- ---------------------------------------------------------------------\n\nmenorIndiceColNoNulaDesde :: (Num a, Eq a) => \n                             Matriz a -> Int -> Int -> Maybe Int\nmenorIndiceColNoNulaDesde p j i \n    | null js   = Nothing\n    | otherwise = Just (head js)\n    where n  = numColumnas p\n          js = [j' | j' <- [j..n], \n                     not (null (elementosNoNulosColDesde p j' i))]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 21. Definir la funci\u00f3n\n--    gaussAux :: (Fractional a, Eq a) => \n--                Matriz a -> Int -> Int -> Matriz a\n-- tal que (gaussAux p) es la matriz que en el que las i-1 primeras\n-- filas y las j-1 primeras columnas son las de p y las restantes est\u00e1n \n-- triangularizadas por el m\u00e9todo de Gauss; es decir,\n--    1. Si la dimensi\u00f3n de p es (i,j), entonces p.\n--    2. Si la submatriz de p sin las i-1 primeras filas y las j-1\n--       primeras columnas es nulas, entonces p.\n--    3. En caso contrario, (gaussAux p' (i+1) (j+1)) siendo\n--    3.1. j' la primera columna a partir de la j donde p tiene\n--         alg\u00fan elemento no nulo a partir de la fila i,\n--    3.2. p1 la matriz obtenida intercambiando las columnas j y j'\n--         de p,\n--    3.3. i' la primera fila a partir de la i donde la columna j de\n--         p1 tiene un elemento no nulo,\n--    3.4. p2 la matriz obtenida intercambiando las filas i e i' de\n--         la matriz p1 y\n--    3.5. p' la matriz obtenida anulando todos los elementos de la\n--         columna j de p2 por debajo de la fila i.\n-- Por ejemplo,\n--    ghci> let p = listaMatriz [[1.0,2,3],[1,2,4],[3,2,5]]\n--    ghci> matrizLista (gaussAux p 2 2)\n--    [[1.0,2.0,3.0],[1.0,2.0,4.0],[2.0,0.0,1.0]]\n-- ---------------------------------------------------------------------\n\ngaussAux :: (Fractional a, Eq a) => Matriz a -> Int -> Int -> Matriz a\ngaussAux p i j \n    | dimension p == (i,j)             = p                        -- 1\n    | not (existeColNoNulaDesde p j i) = p                        -- 2  \n    | otherwise                        = gaussAux p' (i+1) (j+1)  -- 3\n    where Just j' = menorIndiceColNoNulaDesde p j i               -- 3.1 \n          p1      = intercambiaColumnas j j' p                    -- 3.2\n          Just i' = buscaIndiceDesde p1 j i                       -- 3.3\n          p2      = intercambiaFilas i i' p1                      -- 3.4\n          p'      = anulaColumnaDesde p2 j i                      -- 3.5\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 22. Definir la funci\u00f3n\n--    gauss :: (Fractional a, Eq a) => Matriz a -> Matriz a\n-- tal que (gauss p) es la triangularizaci\u00f3n de la matriz p por el m\u00e9todo\n-- de Gauss. Por ejemplo, \n--    ghci> let p = listaMatriz [[1.0,2,3],[1,2,4],[1,2,5]]\n--    ghci> gauss p\n--    array ((1,1),(3,3)) [((1,1),1.0),((1,2),3.0),((1,3),2.0),\n--                         ((2,1),0.0),((2,2),1.0),((2,3),0.0),\n--                         ((3,1),0.0),((3,2),0.0),((3,3),0.0)]\n--    ghci> matrizLista (gauss p)\n--    [[1.0,3.0,2.0],[0.0,1.0,0.0],[0.0,0.0,0.0]]\n--    ghci> let p = listaMatriz [[3.0,2,3],[1,2,4],[1,2,5]]\n--    ghci> matrizLista (gauss p)\n--    [[3.0,2.0,3.0],[0.0,1.3333333333333335,3.0],[0.0,0.0,1.0]]\n--    ghci> let p = listaMatriz [[3%1,2,3],[1,2,4],[1,2,5]]\n--    ghci> matrizLista (gauss p)\n--    [[3 % 1,2 % 1,3 % 1],[0 % 1,4 % 3,3 % 1],[0 % 1,0 % 1,1 % 1]]\n--    ghci> let p = listaMatriz [[1.0,0,3],[1,0,4],[3,0,5]]\n--    ghci> matrizLista (gauss p)\n--    [[1.0,3.0,0.0],[0.0,1.0,0.0],[0.0,0.0,0.0]]\n-- ---------------------------------------------------------------------\n\ngauss :: (Fractional a, Eq a) => Matriz a -> Matriz a\ngauss p = gaussAux p 1 1\n\n-- ---------------------------------------------------------------------\n-- Determinante                                                       --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 23. Definir la funci\u00f3n\n--    gaussCAux :: (Fractional a, Eq a) => \n--                 Matriz a -> Int -> Int -> Int -> Matriz a\n-- tal que (gaussCAux p i j c) es el par (n,q) donde q es la matriz que\n-- en el que las i-1 primeras filas y las j-1 primeras columnas son las\n-- de p y las restantes est\u00e1n triangularizadas por el m\u00e9todo de Gauss;\n-- es decir, \n--    1. Si la dimensi\u00f3n de p es (i,j), entonces p.\n--    2. Si la submatriz de p sin las i-1 primeras filas y las j-1\n--       primeras columnas es nulas, entonces p.\n--    3. En caso contrario, (gaussAux p' (i+1) (j+1)) siendo\n--    3.1. j' la primera columna a partir de la j donde p tiene\n--         alg\u00fan elemento no nulo a partir de la fila i,\n--    3.2. p1 la matriz obtenida intercambiando las columnas j y j'\n--         de p,\n--    3.3. i' la primera fila a partir de la i donde la columna j de\n--         p1 tiene un elemento no nulo,\n--    3.4. p2 la matriz obtenida intercambiando las filas i e i' de\n--         la matriz p1 y\n--    3.5. p' la matriz obtenida anulando todos los elementos de la\n--         columna j de p2 por debajo de la fila i.\n-- y n es c m\u00e1s el n\u00famero de intercambios de columnas y filas que se han \n-- producido durante el c\u00e1lculo. Por ejemplo,\n--    ghci> gaussCAux (listaMatriz [[1.0,2,3],[1,2,4],[1,2,5]]) 1 1 0\n--    (1,array ((1,1),(3,3)) [((1,1),1.0),((1,2),3.0),((1,3),2.0),\n--                            ((2,1),0.0),((2,2),1.0),((2,3),0.0),\n--                            ((3,1),0.0),((3,2),0.0),((3,3),0.0)])\n-- ---------------------------------------------------------------------\n\ngaussCAux :: (Fractional a, Eq a) => \n             Matriz a -> Int -> Int -> Int -> (Int,Matriz a)\ngaussCAux p i j c \n    | dimension p == (i,j)             = (c,p)                        -- 1\n    | not (existeColNoNulaDesde p j i) = (c,p)                        -- 2  \n    | otherwise                        = gaussCAux p' (i+1) (j+1) c'  -- 3\n    where Just j' = menorIndiceColNoNulaDesde p j i                   -- 3.1 \n          p1      = intercambiaColumnas j j' p                        -- 3.2\n          Just i' = buscaIndiceDesde p1 j i                           -- 3.3\n          p2      = intercambiaFilas i i' p1                          -- 3.4\n          p'      = anulaColumnaDesde p2 j i                          -- 3.5\n          c'      = c + signum (abs (j-j')) + signum (abs (i-i'))\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 24. Definir la funci\u00f3n\n--    gaussC :: (Fractional a, Eq a) => Matriz a -> Matriz a\n-- tal que (gaussC p) es el par (n,q), donde q es la triangularizaci\u00f3n\n-- de la matriz p por el m\u00e9todo de Gauss y n es el n\u00famero de\n-- intercambios de columnas y filas que se han producido durante el\n-- c\u00e1lculo. Por ejemplo,  \n--    ghci> gaussC (listaMatriz [[1.0,2,3],[1,2,4],[1,2,5]])\n--    (1,array ((1,1),(3,3)) [((1,1),1.0),((1,2),3.0),((1,3),2.0),\n--                            ((2,1),0.0),((2,2),1.0),((2,3),0.0),\n--                            ((3,1),0.0),((3,2),0.0),((3,3),0.0)])\n-- ---------------------------------------------------------------------\n\ngaussC :: (Fractional a, Eq a) => Matriz a -> (Int,Matriz a)\ngaussC p = gaussCAux p 1 1 0\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 25. Definir la funci\u00f3n\n--    determinante :: (Fractional a, Eq a) => Matriz a -> a\n-- tal que (determinante p) es el determinante de la matriz p. Por\n-- ejemplo, \n--    ghci> determinante (listaMatriz [[1.0,2,3],[1,3,4],[1,2,5]])\n--    2.0\n-- ---------------------------------------------------------------------\n\ndeterminante :: (Fractional a, Eq a) => Matriz a -> a\ndeterminante p = (-1)^c * product (elems (diagonalPral p'))\n    where (c,p') = gaussC p\n<\/pre>\n<p>El c\u00f3digo anterior se encuentra tambi\u00e9n en <a href=\"https:\/\/github.com\/jaalonso\/I1M-Ejercicios\/blob\/master\/Ejercicios\/Rel_19_sol.hs\">GitHub<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>En la segunda parte de la clase hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos comentado las soluciones de los ejercicios de la relaci\u00f3n 18 cuyo objetivo es la triangularizaci\u00f3n de matrices por el m\u00e9todo de Gauss. Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[250],"tags":[270,310],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5301"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=5301"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5301\/revisions"}],"predecessor-version":[{"id":5302,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5301\/revisions\/5302"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=5301"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=5301"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=5301"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}