Sistema de ecuaciones lineales

Hay varios algoritmos para resolver un sistema de ecuaciones lineales.

Descripción de la soluciónEditar

Para describir un conjunto con un número infinito de soluciones, típicamente algunas de las variables se designan como libres (o independientes, o como parámetros), lo que significa que se les permite tomar cualquier valor, mientras que las variables restantes dependen de los valores de las variables libres.

Por ejemplo, considere el siguiente sistema:

x + 3 y – 2 z = 5 3 x + 5 y + 6 z = 7 {\displaystyle {\begin{alignedat}{7}x&&&&3y&&&&2z&&&&&\3x&&;+\N;&&5y&&;+\N;&&6z&&&&&\end{alignedat}}}

El conjunto de soluciones de este sistema puede describirse mediante las siguientes ecuaciones:

x = – 7 z – 1 e y = 3 z + 2 . {\displaystyle x=-7z-1\;\;\;\;{\text{and}}\;\;\;\;y=3z+2{\text{.}}}

Aquí z es la variable libre, mientras que x e y dependen de z. Cualquier punto del conjunto solución puede obtenerse eligiendo primero un valor para z, y luego calculando los valores correspondientes para x e y.

Cada variable libre da al espacio solución un grado de libertad, cuyo número es igual a la dimensión del conjunto solución. Por ejemplo, el conjunto solución de la ecuación anterior es una recta, ya que se puede elegir un punto del conjunto solución especificando el valor del parámetro z. Una solución infinita de orden superior puede describir un plano, o un conjunto de mayor dimensión.

Diferentes elecciones de las variables libres pueden conducir a diferentes descripciones del mismo conjunto solución. Por ejemplo, la solución de las ecuaciones anteriores puede describirse alternativamente como sigue:

y = – 3 7 x + 11 7 y z = – 1 7 x – 1 7 . {\displaystyle y=-{{frac {3}{7}}x+{{frac {11}{7}};{\text{y}};{{frac {1}{7}} z=-{{frac {1}{7}}x-{frac {1}{7}}{texto{y}}.

Aquí x es la variable libre, e y y z son dependientes.

Eliminación de variablesEditar

El método más sencillo para resolver un sistema de ecuaciones lineales es eliminar repetidamente las variables. Este método se puede describir de la siguiente manera:

1. En la primera ecuación, resuelva una de las variables en términos de las otras.
2. Sustituya esta expresión en las ecuaciones restantes. Esto da lugar a un sistema de ecuaciones con una ecuación menos y una incógnita menos.
3. Repite hasta que el sistema se reduzca a una sola ecuación lineal.
4. Resuelve esta ecuación y vuelve a sustituir hasta encontrar la solución completa.

Por ejemplo, considera el siguiente sistema:

x + 3 y – 2 z = 5 3 x + 5 y + 6 z = 7 2 x + 4 y + 3 z = 8 {\displaystyle {\begin{alignedat}{7}x&&;+\N-;&&3y&&;-\N-;&&2z&&&&&\3x&&;+\N;&&5y&&;+\N-;&&6z&&;=\N-;&&&\2x&&&&4y&&&&3z&&&&&\end{alignedat}}}

Resolviendo la primera ecuación para x, se obtiene x = 5 + 2z – 3y, y al insertar esto en la segunda y tercera ecuación se obtiene

– 4 y + 12 z = – 8 – 2 y + 7 z = – 2 {\displaystyle {\begin{alignedat}{5}-4y&&;+\N;&&12z&&&&&&-2y&&&&7z&&&&&\end{alignedat}}}

Resolviendo la primera de estas ecuaciones para y se obtiene y = 2 + 3z, y enchufando esto en la segunda ecuación se obtiene z = 2. Ahora tenemos:

x = 5 + 2 z – 3 y y = 2 + 3 z z = 2 {\displaystyle {\begin{alignedat}{7}x&&&&&&&&2z&&&&3y&&&&&&&&3z&&&&&\\z&&&&&&&&&&&&&\end{alignedat}}}

Reducción de filasEditar

En la reducción de filas (también conocida como eliminación gaussiana), el sistema lineal se representa como una matriz aumentada:

.

Esta matriz se modifica entonces utilizando operaciones elementales de fila hasta que alcanza la forma escalonada de fila reducida. Hay tres tipos de operaciones elementales de fila:

Tipo 1: Intercambiar las posiciones de dos filas. Tipo 2: Multiplicar una fila por un escalar no nulo. Tipo 3: Añadir a una fila un múltiplo escalar de otra.

Debido a que estas operaciones son reversibles, la matriz aumentada producida siempre representa un sistema lineal que es equivalente al original.

Existen varios algoritmos específicos para reducir una fila de una matriz aumentada, siendo los más sencillos la eliminación de Gauss y la eliminación de Gauss-Jordan. El siguiente cálculo muestra la eliminación de Gauss-Jordan aplicada a la matriz anterior:

∼ ∼ ∼ ∼ ∼ . {\displaystyle {\begin{aligned}{left}&{left}{left}{left}{left}{left}{left}&{left}{left}{left}{left}{left}{left}.

La última matriz está en forma escalonada reducida, y representa el sistema x = -15, y = 8, z = 2. Una comparación con el ejemplo de la sección anterior sobre la eliminación algebraica de variables muestra que estos dos métodos son, de hecho, los mismos; la diferencia radica en cómo se escriben los cálculos.

Regla de CramerEditar

La regla de Cramer es una fórmula explícita para la solución de un sistema de ecuaciones lineales, con cada variable dada por un cociente de dos determinantes. Por ejemplo, la solución del sistema

x + 3 y – 2 z = 5 3 x + 5 y + 6 z = 7 2 x + 4 y + 3 z = 8 {\displaystyle {\begin{alignedat}{7}x&&\;3y&&\;2z&&\;5\\3x&&\;5y&&\;6z&&\;7\\2x&&\;4y&&\;3z&&\;8\end{alignedat}}}

está dada por

x = | 5 3 – 2 7 5 6 8 4 3 | | 1 3 – 2 3 5 6 2 4 3 | , y = | 1 5 – 2 3 7 6 2 8 3 | | 1 3 – 2 3 5 6 2 4 3 | | 1 3 – 2 3 5 7 6 2 4 3 | , z = | 1 3 5 3 5 7 2 4 8 | | 1 3 – 2 3 5 6 2 4 3 | . {\_displaystyle x={\frac}{\i} {\i}nada más}{\i},\left|{\begin{matrix}5&&&&&&3\end{matrix}}\right|\,}{\,\left|{\begin{matrix}1&&&&&&3\end{matrix}}\right|\,}},\;\;\;\;y={\frac {\_es},\left|{\begin{matrix}1&&&&&&3\end{matrix}}\right|\,}{\,\left|{\begin{matrix}1&&&&&&3\end{matrix}}\right|\,}},\;\;\;\;z={{frac}} {{b}}que es lo que se llama..,\left|{\begin{matrix}1&&&&&&8\end{matrix}}\right|\,}{\,\left|{\begin{matrix}1&&&&&&3\end{matrix}}\right|\,}}.}

Para cada variable, el denominador es el determinante de la matriz de coeficientes, mientras que el numerador es el determinante de una matriz en la que se ha sustituido una columna por el vector de términos constantes.

Aunque la regla de Cramer es importante desde el punto de vista teórico, tiene poco valor práctico para matrices grandes, ya que el cálculo de determinantes grandes es algo engorroso. (De hecho, los determinantes grandes se calculan más fácilmente utilizando la reducción de filas.)Además, la regla de Cramer tiene propiedades numéricas muy pobres, lo que la hace inadecuada para resolver incluso sistemas pequeños de forma fiable, a menos que las operaciones se realicen en aritmética racional con precisión ilimitada.

Solución matricialEditar

Si el sistema de ecuaciones se expresa en la forma matricial A x = b {\displaystyle A\mathbf {x} =\mathbf {b} } el conjunto de soluciones también puede expresarse en forma matricial. Si la matriz A es cuadrada (tiene m filas y n=m columnas) y tiene rango completo (todas las m filas son independientes), entonces el sistema tiene una solución única dada por

x = A – 1 b {\displaystyle \mathbf {x} =A^{-1}\mathbf {b} } x = A + b + ( I – A + A ) w {\displaystyle \mathbf {x} =A^{+}\mathbf {b} +(I-A^{+}A)\Nmathbf {w} }

Otros métodosEditar

Si bien los sistemas de tres o cuatro ecuaciones pueden resolverse fácilmente a mano (véase Cracoviano), a menudo se utilizan ordenadores para sistemas más grandes. El algoritmo estándar para resolver un sistema de ecuaciones lineales se basa en la eliminación gaussiana con algunas modificaciones. En primer lugar, es esencial evitar la división por números pequeños, que puede conducir a resultados inexactos. Esto puede hacerse reordenando las ecuaciones si es necesario, un proceso conocido como pivote. En segundo lugar, el algoritmo no hace exactamente la eliminación gaussiana, sino que calcula la descomposición LU de la matriz A. Esto es sobre todo una herramienta de organización, pero es mucho más rápido si uno tiene que resolver varios sistemas con la misma matriz A pero diferentes vectores b.

Si la matriz A tiene alguna estructura especial, esto puede ser explotado para obtener algoritmos más rápidos o más precisos. Por ejemplo, los sistemas con una matriz simétrica definida positiva pueden resolverse dos veces más rápido con la descomposición Cholesky. La recursión de Levinson es un método rápido para las matrices de Toeplitz. También existen métodos especiales para matrices con muchos elementos nulos (las llamadas matrices dispersas), que aparecen a menudo en las aplicaciones.

Un enfoque completamente diferente se adopta a menudo para los sistemas muy grandes, que de otro modo tomarían demasiado tiempo o memoria. La idea es comenzar con una aproximación inicial a la solución (que no tiene por qué ser precisa en absoluto), y cambiar esta aproximación en varios pasos para acercarla a la solución verdadera. Una vez que la aproximación es lo suficientemente precisa, se considera que es la solución del sistema. Esto conduce a la clase de métodos iterativos.

También hay un algoritmo cuántico para sistemas lineales de ecuaciones.