Processing math: 100%
Ir al contenido principal

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=b2a21x1a22x3=b3a31x1a32x2a33...xn=bnan1x1an2x2...an,n1xn1ann

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