Sistemas Lineales

Sistemas Lineales

Los sistemas de ecuaciones lineales son una de las herramientas matemáticas de modelaje más comunes en las aplicaciones. Una clasificación común de los sistemas lineales es por su tamaño. Los sistemas con O(100) variables se consideran pequeños y usualmente se utilizan los llamados métodos directos para su solución. Los sistemas de O(1000) ó más variables se consideran grandes o de gran escala y los métodos de solución más eficientes por lo general son los llamados métodos iterativos o indirectos. Otra clasificación importante de los sistemas lineales es por la cantidad o densidad de ceros de la matriz de coeficientes. Los sistemas con pocas entradas distintas de cero se llaman escasos. De lo contrario decimos que el sistema es denso. El aprovechar la estructura de ceros de la matriz de coeficientes nos lleva por lo general a algorítmos mucho más eficientes que los convencionales.

La solución directa de sistemas de ecuaciones lineales conlleva esencialmente dos etapas: transformación del sistema original a otro sistema equivalente más "simple" y luego la solución del nuevo sistema equivalente. La transformación del sistema original a uno más simple toma muchas formas la más común de ellas siendo el proceso de Eliminación Gaussiana. En este método, en su forma básica, si ninguno de los pivotes se hace cero, se producen como resultado matrices L y U triangulares inferior unitaria y superior respectivamente tal que A=LU donde A es la matriz de coeficientes del sistema original. El sistema Ax=b se puede resolver ahora en dos etapas adicionales.

Problema Básico y Notación

Un sistema lineal de n ecuaciones en n desconocidas se puede escribir de la forma

(3.1)

donde los son dados y x1,x2,…,xn son desconocidas. Si definimos la matriz A y los vectores b, x por

(3.2)

Entonces podemos escribir el sistema (3.1) en forma matricial como Ax=b. La matriz A se conoce como la matriz de coeficientes del sistema y b como el lado derecho. Si b=0, i.e., bi=0, 1 i n, entonces decimos que el sistema es homogeneo. De lo contrario se dice que es nohomogeneo.

Ejemplo 1: Considere el sistema

Si definimos

Entonces podemos escribir el sistema en forma matricial como Ax=b.

¿Cúando tiene (3.1) solución y que esta sea única?

Teorema (3.1): Sea A una matriz n n y b un vector. Las siguientes aseveraciones para el sistema Ax=b son todas equivalentes:

a. El sistema tiene solución que es única para todo lado derecho b.

b. El sistema tiene por lo menos una solución para todo lado derecho b.

c. El sistema homogeneo asociado tiene x=0 como única solución.

d. det(A) 0

e. A es invertible

Eliminación Gaussiana

Vamos ahora a estudiar el método más básico y a la ves más importante para la solución directa de sistemas lineales. Primero ilustramos el método con un ejemplo y despúes lo generalizamos.

Ejemplo 2: Considere el sistema de ecuaciones siguiente:

Podemos resolver esto mediante eliminación Gaussisana como sigue:

Con este último sistema equivalente podemos obtener la solución sustituyendo para atrás:

a.

b.

c.

Vamos a generalizar este ejemplo a un sistema 33 general. Escribimos el sistema original como

(3.3)

Paso 1: Suponemos que y definimos

se llama el pivote en este paso. El sistema (3.3) reduce ahora a:

(3.4)

donde

Paso 2: Suponemos ahora que y definimos

Ahora (3.4) reduce a:

donde

Paso 3: Hacemos ahora la sustitución para atrás para obtener la solución. Suponemos aqui que :

Pasamos ahora al caso general del sistema:

Primero pasamos por la etapa de eliminación. Esto es, para k=1,2,…,n-1:

Paso k: Suponemos que (pivote). El sistema en este paso se reduce a uno de la forma:

donde

(3.5)

En el último paso llegamos a un sistema triangular superior de la forma:

(3.6)

donde

(3.7)

Paso n: Calculamos finalmente la solución del sistema haciendo sustitución para atrás:

(3.8)

Las fórmulas (3.5), (3.7), (3.8) definen el Método de Eliminación Gaussiana en su forma básica. Las formulas (3.5) definen la parte de eliminación del método mientras que (3.8) nos da la sustitución para atrás.

Antes de entrar en las variantes de el método básico vamos a hacer un estudio de la cantidad de operaciones envueltas en el método. Esto se conoce como un conteo operacional. Examinando las fórmulas para los en (3.5) podemos construir la tabla siguiente:

Paso Sumas Multiplicaciones Divisiones

1 (n-1)2 (n-1)2 n-1

2 (n-2)2 (n-2)2 n-2

n-1 1 1 1

TOTAL n(n-1)(2n-1)/6 n(n-1)(2n-1)/6 n(n-1)/2

donde usamos las fórmulas

Es costumbre contar las operaciones de multiplicación y división juntas. De modo que la tabla de arriba la podemos resumir diciendo que en la parte de eliminación del método de eliminación Gaussiana el total de:

Sumas y Restas =

Multiplicaciones y Divisiones =

Las fórmulas para los en (3.5) se conocen como la modificación del lado derecho. Estas conllevan:

Sumas y Restas = n-1 + (n-2) + … + 1 =

Multiplicaciones y Divisiones = n-1 + (n-2) + … + 1 =

Las fórmulas (3.8) de la sustitución para atrás conllevan los siguientes totales de operaciones:

Sumas y Restas = 1 + 2 + … + (n-1) =

Multiplicaciones y Divisiones = 1 + 2 + … + n =

Combinando todos los totales parciales hasta ahora obtenemos que el proceso completo de eliminación Gaussiana conlleva un total de:

Sumas y Restas =

Multiplicaciones y Divisiones =

Note que para n "grande" ambos resultados son aproximadamente (1/3)n3. Asi que por ejemplo doblar n equivale a aproximadamente ocho veces más tiempo computacional. Observe también que la parte de eliminación es la que contribuye el termino proporcional a n3. La modificación del lado derecho y la sustitución para atrás son ambas proporcionales a n2. Note que estos tres procesos son independientes uno del otro. Por consiguiente si hay la necesidad de resolver varios sistemas todos con la misma matriz de coeficientes, la parte de eliminación debe hacerse una sola ves.

Al derivar las fórmulas (3.5), (3.7), (3.8) asumimos que los pivotes . Si por el contrario algún , entonces

...