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
\begin{align}
&a_{1 1}x_1 &= b_1 \\
&a_{2 1}x_1 + a_{2 2}x_2 &= b_2 \\
&a_{3 1}x_1 + a_{3 2}x_2 + a_{3 3}x_3 &= b_3 \\
&… & \\
&a_{n 1}x_1 + a_{n 2}x_2 + a_{n 3}x_3 +…+ a_{n n}x_n &= b_n
\end{align}
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:
\begin{align}
x_1 &= \frac{b_1}{a_{1 1}} \\
x_2 &= \frac{b_2 – a_{2 1}x_1}{a_{2 2}} \\
x_3 &= \frac{b_3 – a_{3 1}x_1 – a_{3 2}x_2}{a_{3 3}} \\
… \\
x_n &= \frac{b_n – a_{n 1}x_1 – a_{n 2}x_2 – … – a_{n,n-1}x_{n-1}}{a_{n n}}
\end{align}
Definir la función
|
1 |
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,
|
1 2 3 4 5 6 |
λ> 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
\begin{align}
2x &= 3 \\
3x + y &= 6.5 \\
4x + 2y + 5z &= 10
\end{align}
es \(x=1.5\), \(y=2\) y \(z=0\).
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
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 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
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 |