UNIDAD 3

SISTEMAS DE ECUACIONES LINEALES

ÍNDICE

INTRODUCCIÓN
3.1. MATRICES
3.1.1. OPERACIONES CON MATRICES
3.2. VECTORES
3.3. ELIMINACIÓN DE GAUSS
3.4. ELIMINACIÓN DE GAUSS-JORDAN
3.5. ESTRATEGIAS DE PIVOTEO
3.6. MÉTODO DE CHOLESKY
3.7. MÉTODO DE DESCOMPOSICIÓN LU
3.8. MÉTODO DE GAUSS-SEIDEL
3.9. MÉTODO ITERATIVO
3.9.1. MÉTODO JACOBI

INTRODUCCIÓN

Muchos problemas que aparecen en situaciones reales involucran dos o más ecuaciones en dos o más variables.

En esta sección se introducen los conceptos básicos referentes a los sistemas de ecuaciones lineales. Definiremos cuando una ecuación es una ecuación lineal y cuando se tiene un sistema de ecuaciones lineales. La matriz aumentada del sistema se utilizara para representar convenientemente el total de la información del sistema y se describirá como la manipulación de ella equivale a la manipulación del sistema de ecuaciones. Asimismo, se introducira la idea de la estrategia de eliminación gaussiana para resolver un sistema de ecuaciones basado ciertas operaciones llamadas operaciones elementales.

3.1. MATRICES

La teoría general de matrices encuentra una de sus aplicaciones más inmediatas en la resolución de sistemas de ecuaciones lineales con múltiples incógnitas. Aunque posteriormente fue objeto de un extenso desarrollo teórico, este campo de las matemáticas surgió en realidad como un instrumento de cálculo para facilitar las operaciones algebraicas complejas.

Una matriz real de orden  m x n siendo m y n números naturales es un conjunto de m x n números distribuidos en “m” filas y “n” columnas. Veamos los siguientes ejemplos:

Una matriz cuadrada de dos filas y 2 columnas:

Una matriz de tres filas y dos columnas:

Una matriz de 3 filas y 4 columnas:

Debemos saber que los números que componen una matriz se denominanelementos. Estos se suelen representar por la expresión  aij donde “i” representa la fila y “j” la columna en la que se encuentra. Por ejemplo:

¿Cuándo dos matrices son iguales?

Dos matrices son iguales si tienen el mismo orden y además los elementos colocados en el mismo lugar valen lo mismo.

Son iguales si:

a= 1, b= 3, c=4 y d= -1

3.1.1. OPERACIONES CON MATRICES

Suma de matrices  

 Dadas dos o más matrices del mismo orden, el resultado de la suma es otra matriz del mismo orden cuyos elementos se obtienen como suma de los elementos colocados en el mismo lugar de las matrices sumandos.

Ejemplo:

 

Resta de matrices  

Dadas dos o más matrices del mismo orden, el resultado de la resta es otra matriz del mismo orden cuyos elementos se obtienen como la resta de los elementos colocados en el mismo lugar de las matrices sumandos.

Ejemplo:

Multiplicación por un número

Para multiplicar una matriz cualquiera por un número real, se multiplican todos los elementos de la matriz por dicho número.

Ejemplo:

 Producto de matrices

 El resultado de multiplicar dos matrices es otra matriz en la que el elemento que ocupa el lugar  cij  se obtiene sumando los productos parciales que se obtienen al multiplicar todos los elementos de la fila “i” de la primera matriz por los elementos de la columna “j” de la segunda matriz. Es decir, multiplicamos la primera fila por los elementos de la primera columna y el resultado será nuestro nuevo elemento. Para ello, el número de columnas de la primera matriz debe coincidir con el de filas de la segunda. Si no fuese así no podríamos realizar la operación.

Ejemplo:

Observamos como la matriz resultante tiene el número de filas de la primera y el de columnas de la segunda.

Debemos recordar, que las matrices no tienen la propiedad conmutativa. En el caso de que se pudiera operar A.B y B.A el resultado por lo general puede ser diferente.

3.2. VECTORES

LAS MATRICES DONDE M>1 Y N=1 (ES DECIR, ESTÁN FORMADAS POR UNA SOLA COLUMNA) SON LLAMADAS MATRICES COLUMNA O VECTORES. DE IGUAL MANERA, SI M=1 Y N>1,SE TIENE UNA MATRIZ FILA O VECTOR. LOS VECTORES SE DENOTARÁN CON LAS LETRAS MINÚSCULAS EN NEGRITAS: B, X, ETC. EN ESTOS CASOS N OSERÁ NECESARIA LAUTILIZACIÓN DE DOBLE SUBÍNDICE PARA LA IDENTIFICACIÓN DE SUS ELEMENTOS Y UN VECTOR X DE M ELEMENTOS (EN COLUMNA) QUEDA SIMPLEMENTE COMO:

3.3. ELIMINACIÓN DE GAUSS

La diferencia entre los métodos de Gauss y de Gauss-Jordan es que el primero finaliza al obtener un sistema equivalente en forma escalonada, mientras que el segundo finaliza al obtener un sistema equivalente en forma escalonada reducida.

---

Método de resolución

1. Aplicamos el método de eliminación de Gauss-Jordan:
   obtener la forma escalonada reducida de la matriz ampliada del sistema de ecuaciones mediante operaciones elementales fila (o columna).
   Una vez tenemos la matriz en forma escalonada reducida, la obtención de la solución es inmediata.
2. Aplicaremos el Teorema de Rouché-Frobenius para determinar el tipo de sistema:
   Sea A·X = B un sistema de m ecuaciones lineales con n incógnitas (sobre un cuerpo en general), siendo m y n naturales (no nulos):
   
   • A·X = B es compatible si, y sólo si, rango( A ) = rango ( A | B ).
   • A·X = B es compatible determinado si, y sólo si, rango( A ) = n = rango( A | B ).

Nota: las operaciones elementales fila y columna nos permiten obtener sistemas equivalentes al inicial pero con una forma que facilita la obtención de las soluciones (en caso de haberlas). Asimismo, existen herramientas más rápidas para hallar las soluciones de los sistemas compatibles determinados, como la Regla de Cramer.

           

3.4. ELIMINACIÓN DE GAUSS-JORDAN

En matemáticas, la eliminación de Gauss, llamada así debido a Carl Friedrich Gauss y Wilhelm Jordan, es un algoritmo del álgebra lineal para determinar las soluciones de un sistema de ecuaciones lineales, encontrar matrices e inversas. Un sistema de ecuaciones se resuelve por el método de Gauss cuando se obtienen sus soluciones mediante la reducción del sistema dado a otro equivalente en el que cada ecuación tiene una incógnita menos que la anterior. El método de Gauss transforma la matriz de coeficientes en una matriz triangular superior. El método de Gauss-Jordan continúa el proceso de transformación hasta obtener una matriz diagonal.

1. Ir a la columna no cero extrema izquierda
2. Si la primera fila tiene un cero en esta columna, intercambiarlo con otra que no lo tenga.
3. Luego, obtener ceros debajo de este elemento delantero, sumando múltiplos adecuados del renglón superior a los renglones debajo de él.
4. Cubrir el renglón superior y repetir el proceso anterior con la submatriz restante. Repetir con el resto de los renglones (en este punto la matriz se encuentra en forma escalonada).
5. Comenzando con el último renglón no cero, avanzar hacia arriba: para cada renglón obtener 1 delantero e introducir ceros arriba de éste sumando múltiplos correspondientes a los renglones correspondientes.

Una variante interesante de la eliminación de Gauss es la que llamamos eliminación de Gauss-Jordan, (debido al mencionado Gauss y a Wilhelm Jordan), esta consiste en ir obteniendo los 1 delanteros durante los pasos uno al cuatro (llamados paso directo) así para cuando estos finalicen ya se obtendrá la matriz en forma escalonada reducida.

3.5.ESTRATEGIAS DE PIVOTEO

Pivoteo y Complejidad

Cuando  se aplica una operación elemental sobre una determinada fila para lograr un 0 en el coeficiente apq, con p = q + 1, q + 2, . . . ,N utilizo el elemento aqq de la matriz, y dicho elemento recibe el nombre de pivote. Los números mpq = apq/aqq se llaman multiplicadores y son los que se multiplican en la fila pivote para restarla de las correspondientes filas.

Al estar trabajando con sistemas de cómputos, cuya precisión está fijada de antemano, cada vez que se produce una operación aritmética se comete un error, en este caso de redondeo. Es por eso que la elección del pivote en cada paso la tomo por algún criterio no trivial de tal forma de tratar que dicho sea el menor posible.

Existen varias estrategias una de ellas consiste en la denominada estrategia de pivoteo parcial. La idea de este método consiste en lo siguiente: comparo el tamaño de todos los elementos de la columna de la fila q-´e sima (a partir del coeficiente que se encuentra en la diagonal) hasta la última fila, y me quedo con aquel elemento que tenga mayor valor absoluto. Una vez encontrada la fila que cumpla lo anterior, la llamo fila i-´e sima, aplico la operación de intercambio de filas entre la q-´e sima y la i-´e sima, de forma tal de lograr multiplicadores mpq menores a uno en valor absoluto.

Durante la derivación del algoritmo de la eliminación Gaussiana con sustitución hacia atrás, se encontró que para obtener un cero para el elemento pivote a(k) kk era necesario un intercambio de filas de la forma (Ek) $ (Ep) donde k + 1 · p · n era el entero más pequeño con a(k) pk 6= 0. En la práctica frecuentemente es deseable realizar intercambios de las filas que contienen a los elementos pivote, aun cuando estos no sean cero. Cuando los cálculos se realizan usando aritmética de dígitos finitos, como será el caso de las soluciones generadas con calculadora u ordenador, un elemento pivote que sea pequeño comparado con los elementos de debajo del en la misma columna puede llevar a un error de redondeo sustancial. 

Pivoteo parcial

La onda con el pivoteo es hacer Gauss-Jordan pero eligiendo el mejor valor para hacer cuentas, de manera tal que los errores de las cuentas de la maquinita sean los menores. Así, se implementa un criterio para reordenar filas de manera tal que se queden los valores mayores al momento de dividir. El método consiste en elegir en la iteración i-ésima, el elemento de la columna que sea el de mayor valor absoluto entre todos los que están por encima de la diagonal, el menor valor de p≥i

|api|=maxi≤k≤n|aki|

Pivoteo parcial escalado

Cuando hay algún valor muy zarpado en las ecuaciones en comparación con el resto, el pivoteo solito no alcanza. Ahí hay que usar escalado. El escalado implica usar un factor de escala para cada fila, que se define

 sk=max1≤j≤n|akj|

3.6. MÉTODO DE CHOLESKY

En matemáticas, la factorización o descomposición de Cholesky toma su nombre del matemático André-Louis Cholesky, quien encontró que una matriz simétrica definida positiva puede ser descompuesta como el producto de una matriz triangular inferior y la traspuesta de la matriz triangular inferior. La matriz triangular inferior es el triángulo de Cholesky de la matriz original positiva definida. El resultado de Cholesky ha sido extendido a matrices con entradas complejas. Es una manera de resolver sistemas de ecuaciones matriciales y se deriva de la factorización LU con una pequeña variación.

Cualquier matriz cuadrada A con pivotes no nulos puede ser escrita como el producto de una matriz triangular inferior L y una matriz triangular superior U; esto recibe el nombre de factorización LU. Sin embargo, si A es simétrica y definida positiva, se pueden escoger los factores tales que U es la transpuesta de L, y esto se llama la descomposición o factorización de Cholesky. Tanto la descomposición LU como la descomposición de Cholesky son usadas para resolver sistemas de ecuaciones lineales. Cuando es aplicable, la descomposición de Cholesky es dos veces más eficiente que la descomposición LU.

En general, si A es Hermitiana y definida positiva, entonces A puede ser descompuesta como

donde L es una matriz triangular inferior con entradas diagonales estrictamente positivas y L* representa la conjugada traspuesta de L. Esta es la descomposición de Cholesky.

La descomposición de Cholesky es única: dada una matriz Hermitiana positiva definida A, hay una única matriz triangular inferior L con entradas diagonales estrictamente positivas tales que A = LL*. El recíproco se tiene trivialmente: si A se puede escribir como LL* para alguna matriz invertible L, triangular inferior o no, entonces A es Hermitiana y definida positiva.

El requisito de que L tenga entradas diagonales estrictamente positivas puede extenderse para el caso de la descomposición en el caso de ser semidefinida positiva. La proposición se lee ahora: una matriz cuadrada A tiene una descomposición de Cholesky si y sólo si A es Hermitiana y semidefinida positiva. Las factorizaciones de Cholesky para matrices semidefinidas positivas no son únicas en general.

En el caso especial que A es una matriz simétrica definida positiva con entradas reales, L se puede asumir también con entradas reales. Una Matriz D diagonal con entradas positivas en la diagonal (valores propios de A), es factorizable como , donde  es matriz cuya diagonal consiste en la raíz cuadrada de cada elemento de D, que tomamos como positivos. Así:

La factorización puede ser calculada directamente a través de las siguientes fórmulas (en este caso realizamos la factorizacón superior ):
 para los elementos de la diagonal principal, y:

 para el resto de los elementos. Donde  son los elementos de la matriz U.

3.7. MÉTODO DE DESCOMPOSICIÓN LU

Para encontrar la matriz triangular inferior se busca hacer ceros los valores de arriba de cada pivote, así como también convertir en 1 cada pivote. Se utiliza el mismo concepto de "factor" explicado anteriormente y se ubican todos los "factores" debajo de la diagonal según corresponda en cada uno.

Esquemáticamente se busca lo siguiente:

  

Originalmente se tenía:

Debido a que [A] = [L][U], al encontrar [L] y [U] a partir de [A] no se altera en nada la ecuación y se tiene lo siguiente:

Por lo tanto, si Ax = b, entonces LUx = b, de manera que Ax = LUx = b.

PASOS PARA RESOLVER UN SISTEMA DE ECUACIONES POR EL MÉTODO DE DESCOMPOSICIÓN LU

1. Obtener la matriz triangular inferior L y la matriz triangular superior U.
2. Resolver Ly = b (para encontrar y).
3. El resultado del paso anterior se guarda en una matriz nueva de nombre "y".
4. Realizar Ux = y (para encontrar x).
5. El resultado del paso anterior se almacena en una matriz nueva llamada "x", la cual brinda los valores correspondientes a las incógnitas de la ecuación.
   
   
   
   3.8. MÉTODO DE GAUSS-SIEDEL
   1. 
      
   2. 
      
   3. 
      
   4. 
      
   5. 
      
      
      
      El método de Gauss-Seidel es un método iterativo y por lo mismo resulta ser bastante eficiente. Se comienza planteando el sistema de ecuaciones con el que se va a trabajar:

      
      

      De la ecuación 1 despejar x1, de la ecuación 2 despejar x2, …, de la ecuación n despejar xn. Esto da el siguiente conjunto de ecuaciones:

      

      Este último conjunto de ecuaciones son las que forman las fórmulas iterativas con las que se va a estar trabajando. Para comenzar el proceso iterativo, se le da el valor de cero a las variables x2,…, xn; esto dará un primer valor para x1. Más precisamente, se tiene que:

      

      Enseguida, se sustituye este valor de x1 en la ecuación 2, y las variables x3,…, xn siguen teniendo el valor de cero. Esto da el siguiente valor para x2:

      

      Estos últimos valores de x1 y x2, se sustituyen en la ecuación 3, mientras que x4,…, xn siguen teniendo el valor de cero; y así sucesivamente hasta llegar a la última ecuación. Todo este paso arrojará una lista de primeros valores para las incógnitas, la cual conforma el primer paso en el proceso iterativo. Para una mejor comprensión esto se simbolizará de esta forma:

      

      Se vuelve a repetir el proceso, pero ahora sustituyendo estos últimos datos en vez de ceros como al inicio. Se obtendrá una segunda lista de valores para cada una de las incógnitas, lo cual se simbolizará así:

      

      En este momento se pueden calcular los errores aproximados relativos, respecto a cada una de las incógnitas. La lista de errores se presenta a continuación:

      

      El proceso se vuelve a repetir hasta que:

      

      donde  se debe prefijar convenientemente.
      

      
      

      
      

      
      

      
      

      3.9. MÉTODO ITERATIVO

      
      Un método iterativo trata de resolver un problema matemático (como una ecuación o un sistema de ecuaciones) mediante aproximaciones sucesivas a la solución, empezando desde una estimación inicial. Esta aproximación contrasta con los métodos directos, que tratan de resolver el problema de una sola vez (como resolver un sistema de ecuaciones Ax=b encontrando la inversa de la matriz A). Los métodos iterativos son útiles para resolver problemas que involucran un número grande de variables (a veces del orden de millones), donde los métodos directos tendrían un coste prohibitivo incluso con la potencia del mejor computador disponible.
      

      En el caso de un sistema lineal de ecuaciones, las dos clases principales de métodos iterativos son los métodos iterativos estacionarios y los más generales métodos del subespacio de Krylov

      Métodos iterativos estacionarios

      Los métodos iterativos estacionarios resuelven un sistema lineal con un operador que se aproxima al original, y basándose en la medida de error (el residuo), desde unaecuación de corrección para la que se repite este proceso. Mientras que estos métodos son sencillos de derivar, implementar y analizar, la convergencia normalmente sólo está garantizada para una clase limitada de matrices.

      Métodos del subespacio de Krylov

      Los métodos del subespacio de Krylov forman una base ortogonal de la secuencia de potencias de la matriz por el residuo inicial (la secuencia de Krylov). Las aproximaciones a la solución se forman minimizando el residuo en el subespacio formado. El método prototípico de esta clase es el método de gradiente conjugado. Otros métodos son elmétodo del residuo mínimo generalizado y el método del gradiente biconjugado.

      Convergencia

      Dado que estos métodos forman una base, el método converge en N iteraciones, donde N es el tamaño del sistema. Sin embargo, en la presencia de errores de redondeo esta afirmación no se sostiene; además, en la práctica N puede ser muy grande, y el proceso iterativo alcanza una precisión suficiente mucho antes. El análisis de estos métodos es difícil, dependiendo de lo complicada que sea la función del espectro del operador.

      Precondicionantes

      El operador aproximativo que aparece en los métodos iterativos estacionarios puede incorporarse también en los métodos del subespacio de Krylov, donde se pasan de ser transformaciones del operador original a un operador mejor condicionado. La construcción de precondicionadores es un área de investigación muy extensa y de gran alcance científico.

      
      

      
      

      3.9.1. MÉTODO JACOBI

      
      En análisis numérico el método de Jacobi es un método iterativo, usado para resolver sistemas de ecuaciones lineales del tipo . El algoritmo toma su nombre del matemático alemán Carl Gustav Jakob Jacobi. El método de Jacobi consiste en usar fórmulas como iteración de punto fijo.
      

      La base del método consiste en construir una sucesión convergente definida iterativamente. El límite de esta sucesión es precisamente la solución del sistema. A efectos prácticos si el algoritmo se detiene después de un número finito de pasos se llega a una aproximación al valor de x de la solución del sistema.

      La sucesión se construye descomponiendo la matriz del sistema  en la forma siguiente:

      

      donde , es una matriz diagonal y , es la suma de una matriz triangular inferior  y una matriz triangular superior , luego . Partiendo de , podemos reescribir dicha ecuación como:

      

      Luego,

      

      Si aii ≠ 0 para cada i. Por la regla iterativa, la definición del Método de Jacobi puede ser expresado de la forma:

      

      donde  es el contador de iteración, Finalmente tenemos:

      

      Cabe destacar que al calcular xi(k+1) se necesitan todos los elementos en x(k), excepto el que tenga el mismo i. Por eso, al contrario que en el método Gauss-Seidel, no se puede sobreescribir xi(k) con xi(k+1), ya que su valor será necesario para el resto de los cálculos. Esta es la diferencia más significativa entre los métodos de Jacobi y Gauss-Seidel. La cantidad mínima de almacenamiento es de dos vectores de dimensión n, y será necesario realizar un copiado explícito.
      
      
      

      BIBLIOGRAFÍA

      
      

      https://www.matesfacil.com/ESO/sistema-ecuaciones/metodo-grafico/metodo-grafico-sistemas-ecuaciones-lineales-resueltos-grafica-recta-interseccion-solucion-interseccion.html
   6. APUNTES EN CLASES