Soluciones de Sistemas de Ecuaciones Lineales

REALIZADO POR: JOSE ALEJANDRO BARAZARTE

C.I 20.766.230ING. COMPUTACION

REPUBLICA BOLIVARIANA DE VENEZUELA

UNIVERSIDAD FERMIN TOROSEDE CABUDARE

Método de Eliminación GaussianaEn forma general este método propone la eliminación progresiva de

variables en el sistema de ecuaciones, hasta tener sólo una ecuación con una incógnita. Una vez resuelta esta, se procede por sustitución regresiva

hasta obtener los valores de todas las variables. Sea por ejemplo el siguiente sistema de ecuaciones: 

Lo que buscamos son 3 números,  que satisfagan a las tres ecuaciones. El método de solución será simplificar las ecuaciones, de tal modo que las soluciones se puedan identificar con facilidad. Se comienza dividiendo la

primera ecuación entre 2, obteniendo:

Se simplificará el sistema si multiplicamos por -4 ambos lados de la primera ecuación y sumando esta a la segunda. Entonces:

Sumándolas resulta

La nueva ecuación se puede sustituir por cualquiera de las dos. Ahora:

Luego, la primera se multiplica por -3 y se le suma a la tercera, obteniendo:

Acto seguido, la segunda ecuación se divide entre -3. Ahora se multiplica por 5 y se le suma a la tercera:

En este momento ya tenemos el valor de x3, ahora simplemente se procede a hacer la sustitución hacia atrás, y automáticamente se van obteniendo los

valores de las otras incógnitas. Se obtendrá:

Se ha visto que al multiplicar o dividir los lados de una ecuación por un número diferente de cero se obtiene una ecuación nueva y válida.

Por otra parte, si se suma un múltiplo de una ecuación a otra ecuación del mismo sistema, el resultado es otra ecuación válida. Por último, si se

intercambian dos ecuaciones de un sistema, lo que se obtiene es un sistema equivalente.

Método de Eliminación Gauss- Jordan

El método de Gauss transforma la matriz de coeficientes en una matriz triangular superior. El método de Gauss- Jordán continúa el proceso de

transformación hasta obtener una matriz diagonal unitaria (aij=0 para cualquier ).

Veamos el método de Gauss- Jordán siguiendo con este ejemploaplicando el método de Gauss llegamos a la siguiente ecuación: 

Ahora seguiremos un procedimiento similar al empleado en el método de Gauss. Tomaremos como pivote el elemento a44=-3; multiplicamos la cuarta ecuación por  -3/4 y la restamos a la primera: 

Realizamos la misma operación con la segunda y tercera fila, obteniendo: 

Ahora tomamos como pivote el elemento a33=2, multiplicamos la tercera ecuación por 2/2 = 1  y la restamos a la primera: 

Repetimos la operación con la segunda fila: 

Finalmente, tomamos como pivote a22=-4, multiplicamos la segunda ecuación por -2/-4  y la sumamos a la primera: 

Empleando la ecuación obtenemos las soluciones: 

Descomposición LUEl método de descomposición LU para la solución de sistemas de

ecuaciones lineales debe su nombre a que se basa en la descomposición de la matriz original de coeficientes (A) en el producto de dos matrices (L

y U).Esto es:

Donde:L - Matriz triangular inferior

U - Matriz triangular superior con todos los elementos de la diagonal principal iguales a 1.

De lo anterior, para matrices de 3x3 se escribe:

    

=

Si efectuamos la multiplicación de L y U, igualando los elementos de ese producto con los de la matriz A correspondientes, se obtiene

De aquí que los elementos de L y U son, en este caso:

Si el sistema de ecuaciones original se escribe como:A x = b

lo cual resulta lo mismo escribir:L U X = b

Definiendo a:U X = Y

podemos escribir:L Y = b

Resolviendo para Y, encontramos:

El algoritmo de solución, una vez conocidas L, U y b, consiste en encontrar primeramente los valores de "Y" por sustitución progresiva

sobre "L Y = b". En segundo lugar se resuelve "U x = y " por sustitución regresiva para encontrar los valores de "x", obteniendo:

La determinación de los elementos de las matrices L y U se realizan eficientemente aplicando una forma modificada del método de eliminación

de Gauss.Se observa que el método de descomposición LU opera sólo sobre la matriz de coeficientes, sin modificar el vector de excitación (en este caso b), por lo

que resulta superior al método de eliminación gaussiana.Ejemplo: 

Resolver el siguiente sistema de ecuaciones, factorizando la matriz en LU:

=

Las matrices de factores L y U de A son:

L = U =

El primer paso es resolver la ecuación L Y = b por sustitución progresiva para obtener los elementos del vector auxiliar Y:

=

Donde:

El segundo paso es resolver la ecuación U X = Y para encontrar los elementos de X, por sustitución regresiva:

=

De donde se obtiene:  

 

Factorización de CholeskyUna matriz A simétrica y positiva definida puede ser factorizada de manera eficiente por medio de una matriz triangular inferior y una matriz triangular

superior. Para una matriz no singular la descomposición LU nos lleva a considerar una descomposición de tal tipo A = LU; dadas las condiciones

de A, simétrica definida positiva, no es necesario hacer pivoteo, por lo que ésta factorización se hace eficientemente y en un número de operaciones la

mitad de LU tomando la forma   , donde L (la cual podemos "verla" como la raíz cuadrada de A) es una matriz triangular inferior donde los

elementos de la diagonal son positivos.Para resolver un sistema lineal Ax = b con A simétrica definida positiva y

dada su factorización de Cholesky  , primero debemos resolver Ly = by entonces resolver    para lograr x.

Una variante de la factorización de Cholesky es de la forma    , donde R es una matriz triangular superior, en algunas aplicaciones se desea ver la

matriz en esa forma y no de otra.

Para encontrar la factorización    , bastaría ver la forma de L y observar las ecuaciones que el producto derecho nos conduce al igualar

elementos:

Así obtendríamos que:

Y de manera general, para

Ahora bien, ya que A es simétrica y definida positiva, podemos asegurar que los elementos sobre la diagonal de L son positivos y los restantes elementos

reales desde luego.Una de las aplicaciones de la factorización de Cholesky es resolver las

ecuaciones normales de un problema de cuadrados mínimos, esas ecuaciones son: 

en la que     es simétrica y definida positiva.

Sea A ∈ Rm×n con m ≥ n. La factorización QR de A es A = QR = [Q1 Q2] R1 0 = Q1R1 donde Q ∈ Rm×m es una matriz ortogonal y R1 ∈ R n×n es una matriz triangular superior. Se dice que la matriz R es trapezoidal superior. Esta factorización es útil para resolver sistemas de ecuaciones lineales,

problemas de mínimos cuadrados y problemas de eigenvalores. Las maneras más comunes de calcular la factorización QR son aplicando • las transformaciones de Householder, • las rotaciones de Givens, • el proceso de

ortogonalización de Gram-Schmidt.

Factorización de QR

Transformaciones de HouseHolderSea v ∈ R n, v 6= 0. La matriz de Householder se define como

P = I − 2. vv^T ------ vTv

La matriz es simétrica y ortogonal y, por tanto, P^2 = I. La figura muestra porque se le llama reflexión. El objetivo de esta matriz es usarla para

producir ceros en la matriz que queremos factorizar. Para hacerlo, debemos considerar el problema: Dados los vectores X y Y, ¿cómo calculamos P tal que

Px = y

• Puesto que P realiza una reflexión, se debe cumplir que kyk2 = kxk2 para poder calcular P.

• Hay que notar que P es invariante a la escala de v. • x − y tiene la dirección del vector que queremos. Así, podemos definir v = x − y.

• Puesto que P realiza una reflexión, se debe cumplir que kyk2 = kxk2 para poder calcular P.

• Hay que notar que P es invariante a la escala de v.

• x − y tiene la dirección del vector que queremos. Así, podemos definir v = x − y. Para que P produzca el mayor número de ceros, debemos tener que y = σe1, donde e1 es el vector canónico que tiene un 1 como primer elemento

y el resto son ceros, y σ = ±kxk. Entonces v = x − y = x − σe1.

• Puesto que P realiza una reflexión, se debe cumplir que kyk2 = kxk2 para poder calcular P.

• Hay que notar que P es invariante a la escala de v.

• x − y tiene la dirección del vector que queremos. Así, podemos definir v = x − y. Para que P produzca el mayor número de

ceros, debemos tener que y = σe1, donde e1 es el vector canónico que tiene un 1 como primer elemento y el resto son ceros, y σ = ±x. Entonces v = x − y = x − σe1. Sea x = (x1, x2, ..., xn) >. Para evitar errores por sustracción

conviene definir σ = −sign(x1)x.

El proceso se ilustra en la siguiente figura para una matriz 4 × 3.

Sea A1 = A y a1 su primer columna. Calculamos la matriz de Householder P1 tal que P1a1 = σe1, con σ = −sign(a11)a1, y hagamos Pb1 = P1. Así, A2 =

Pb1A1 tiene ceros en la primera columna, excepto en el primer elemento. En el paso k-ésimo tenemos

y Rk−1 es triangular superior. Definimos la matriz de Householder Pk tal que Pkxk = σe1, con σ = −sign(xk1)x1, y definimos

• No es necesario construir las matrices de Householder. Es suficiente con determinar v, puesto que PkCk = (I − βvv>)Ck = Ck − βv(v >Ck), con β =

1/v >v. • Definimos Q = Pb1Pb1 · · · Pbn.

• Es mejor hacer el cálculo de Q multiplicando de derecha a izquierda. • El número de operaciones es 2n 2(m − n/3)

Método de Gauss SeidelPara la aplicación al problema del flujo de potencia, las ecuaciones de

nodo y condiciones de contorno se combinan, para el nodo k:

De donde se puede expresar la tensión Vk como:

La ecuación anterior es el corazón del algoritmo iterativo. La iteración comienza con una estimación de las magnitudes y ángulos de todas las

barras del sistema, y se van recalculando las tensiones utilizando los mejores valores disponibles. Esto es, para calcular la tensión Vk se utilizan los V1...k-1

ya actualizados, y los Vk...n del paso anterior. El método tiene una convergencia extremadamente lenta pero segura (excepto para problemas

mal condicionados, o sin convergencia posible.

El método de Gauss-Seidel es un refinamiento del método de Jacobi que generalmente (pero no siempre) converge más rápido. El último valor de

cada variable es sustituido en cada paso en el proceso iterativo. El método de Gauss-Seidel, es un método iterativo y por lo mismo, resulta ser un método bastante eficiente. A continuación se presenta un sistema de

ecuaciones: 

De la ecuación 1 se despeja X1, de la ecuación 2 se despeja X2, y así hasta n se despeja Xn. Resolviendo lo anterior se obtiene:

Este último conjunto de ecuaciones son las que forman las fórmulas iterativas. Para comenzar el proceso iterativo, le se le asigna el valor de cero

a las variables X2, ,… Xn; esto dara un primer valor para X1. Mas precisamente, tenemos:

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, darán una lista de primeros valores para

las incógnitas, la cual conforma el primer paso en el proceso iterativo. Digamos que se tiene: 

Se repite 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. Por lo tanto ahora se tiene: 

En este momento, se puede calcular los errores aproximados relativos, respecto a cada una de las incógnitas. Así, se tiene la lista de errores como

sigue:El proceso se vuelve a repetir hasta que: 

Donde Es es una cota prefijada.

Método de Jacobi

El Método de Jacobi es uno de los métodos iterativos más conocidos.Supóngase que se tiene un sistema 3 x 3. Si los elementos de la

diagonal no son todos cero, la primera ecuación se puede resolver para x1, la segunda x2, y la tercera para x3 y asi obtener:

En general, para un sistema de ecuaciones lineales de n ecuaciones con n incógnitas, el Método de Jacobi para encontrar un valor k de una

variable x es el siguiente:

El procedimiento consiste en asignar unos valores iniciales a las variables, usualmente se escoge "0" por simplicidad, de manera que para generar la

siguiente iteración se sustituyen los valores obtenidos en la ecuación siguiente, con lo que se obtiene:

En la siguiente sección se ilustra cómo la convergencia de éste método está dada por: