Algoritmo de bajada para resolver un sistema triangular inferior
Un sistema de ecuaciones lineales Ax=b es triangular inferior si todos los elementos de la matriz A que están por encima de la diagonal principal son nulos; es decir, es de la forma a11x1=b1a21x1+a22x2=b2a31x1+a32x2+a33x3=b3...an1x1+an2x2+an3x3+...+annxn=bn
El sistema es compatible si, y sólo si, el producto de los elementos de la diagonal principal es distinto de cero. En este caso, la solución se puede calcular mediante el algoritmo de bajada: x1=b1a11x2=b2−a21x1a22x3=b3−a31x1−a32x2a33...xn=bn−an1x1−an2x2−...−an,n−1xn−1ann
Definir la función
bajada :: Matrix Double -> Matrix Double -> Matrix Double
tal que bajada a b
es la solución, mediante el algoritmo de bajada, del sistema compatible triangular superior ax = b
. Por ejemplo,
λ> let a = fromLists [[2,0,0],[3,1,0],[4,2,5.0]] λ> let b = fromLists [[3],[6.5],[10]] λ> bajada a b ( 1.5 ) ( 2.0 ) ( 0.0 )
Es decir, la solución del sistema 2x=33x+y=6.54x+2y+5z=10 es x=1.5, y=2 y z=0.
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
Soluciones en Haskell
module Algoritmo_de_bajada where import Data.Matrix (Matrix, (!), fromLists, nrows, toLists) import Test.Hspec (Spec, hspec, it, shouldBe) bajada :: Matrix Double -> Matrix Double -> Matrix Double bajada a b = fromLists [[x i] | i <- [1..m]] where m = nrows a x k = (b!(k,1) - sum [a!(k,j) * x j | j <- [1..k-1]]) / a!(k,k) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "ej1" $ toLists (bajada a b) `shouldBe` [[1.5],[2.0],[0.0]] where a = fromLists [[2,0,0],[3,1,0],[4,2,5.0]] b = fromLists [[3],[6.5],[10]] -- La verificación es -- λ> verifica -- -- Finished in 0.0007 seconds -- 1 example, 0 failures
Soluciones en Python
def bajada(a: list[list[float]], b: list[list[float]]) -> list[list[float]]: n = len(a) def x(k: int) -> float: return (b[k][0] - sum((a[k][j] * x(j) for j in range(0, k)))) / a[k][k] return [[x(i)] for i in range(0, n)] # Verificación # ============ def test_bajada() -> None: assert bajada([[2,0,0],[3,1,0],[4,2,5.0]], [[3],[6.5],[10]]) == \ [[1.5], [2.0], [0.0]] print("Verificado") # La verificación es # >>> test_bajada() # Verificado