EJEMPLOS DE METODOS DIRECTOS E INDIRECTOS

EJERCICIOS DE METODOS NUMERICOS DIRECTOS E INDIRECTOS

1) Resolver la siguiente ecuación con los métodos de Jacobi y Gauss Seidel en Mathcad:

5x + 3y - z = 12
-x + 9y + 5z = 6
2x + 3y - 7z = 4
Solución:
Variable x
Variable y
Variable z

Programa :





















Valores Iniciales:
x:=1 y:=1 z:=1

Siendo los resultados:

Con el método de Gauss Seidel:
















El resultado será:

En el eje x:

En el eje y:

















En el eje z:

















2) Resolver en Mathcad:

A ) Sin modificar las ecuaciones indique si existe solución considerando xo = 0, yo = 0)

B ) Con los mismos valores iniciales y modificando las ecuaciones resolver el problema

Solución:

Usando el programa de Gauss Seidel:

Siendo los Valores iniciales:
x:=0 y:=0

El resultado será:

En “x” y en “y” el sistema no converge:

B ) Modificando las ecuaciones

Usando el programa de Gauss Seidel:

En el eje “x” y “y”

Metodos

Existen dos métodos:

Método Directo:

• Ax =b
• x = A\ b
• Tamaño moderado
• Modifican la estructura
• Error de redondeo

Método Iterativo:

• x = Cx + d
• x(k+1) = Cx(k) + d
• Tamaño grande
• Conservan los ceros
• Error de truncamiento

A continuación veremos los métodos estudiados en clase.

Métodos Iterativos de sistemas Lineales

1. Método de Jacobi:
Forma “algebraica”

Para i = 1, 2, ..., n








El método de Jacobi se denomina también de los desplazamientos simultáneos pues cada ecuación se cambia simultáneamente teniendo en cuenta los índices de las componentes del vector que se ha calculado precedentemente:





Forma “matricial”

En general para un sistema de n x n siendo A la matriz de un sistema de forma:











Vamos a suponer que A fuera reordenada de modo que todos sus elementos de la diagonal sean nulos:















Si consideramos que el lado derecho del sistema como los elementos de un nuevo paso de interacción (k+1) de los elementos del lado derecho como elementos del paso anterior (k), tendremos:













Ejemplo de método Jacobi:

Resolver la siguiente ecuación:
3x + y – z = 11
x + 7y -2z = 10
x + 3y - 9z= 12

Resolviendo:
X k+1 = (11-yk+zk)/3 => F(y,z)
y k+1 = (10-xk+2zk)/7 => G(x,z)
z k+1 = (-12+xk+3yk)/9 => H(x,y)

Asumiendo que los valores iniciales son x0 = 0; y0 = 0; z0 = 0 se reemplaza:
x1 = (11- y0 + z0) /3 = 11/3
y1 = (10- x0 + 2z0) /7 = 10/7
z1 = (x0+ 3y0 - 12)/9 = 4/3



2. Método de Gauss-Seidel
La iteración de Gauss-Seidel es una mejora de del método anterior, para lo cual requiere de un menor número de iteraciones.

Forma “algebraica”








Forma “matricial”












Siendo de la forma:











Una condición suficiente de convergencia:



entonces el proceso iterativo



a partir de x(0) cualquiera, es convergente hacia la solución de x = B x + c, que existe y es única.

Sea cualquiera de las normas, cuando hay convergencia, debe verificarse:





Nota:
Obsérvese que en el método de Gauss-Seidel los valores actualizados de xi sustituyen de inmediato a los valores anteriores, mientras que en el método de Jacobi todas las componentes nuevas del vector se calculan antes de llevar a cabo la sustitución.

Por contra, en el método de Gauss-Seidel los cálculos deben llevarse a cabo por orden, ya que el nuevo valor xi depende de los valores actualizados de x1, x2, ..., xi-1.

Sistemas Lineales en un cuerpo arbitrario

Cuando consideramos ecuaciones lineales cuyas soluciones son números racionales, reales o complejos o más generalmente un cuerpo K , la solución puede encontrarse mediante Regla de Cramer. Para sistemas de muchas ecuaciones la regla de Cramer puede ser computacional mente más costosa y suelen usarse otros métodos más "económicos" en número de operaciones como la eliminación de Gauss-Jordan y la descomposición de Cholesky. Existen también métodos indirectos (basados en iteraciones) como el método de Gauss-Seidel.

Si el cuerpo es infinito (como es el caso de los números reales o complejos), entonces solo puede darse una de las tres siguientes situaciones:

• el sistema no tiene solución (en dicho caso decimos que el sistema está sobredeterminado o que es incompatible) .
• el sistema tiene una única solución (el sistema es compatible determinado)
• el sistema tiene un número infinito de soluciones (el sistema es compatible indeterminado).

Un sistema de la forma Ax = 0 se le llama sistema homogéneo. El conjunto de todas las soluciones de este tipo de sistema se le llama núcleo de la matriz y se escribe como Nuc A.
Se han diseñado algoritmos alternativos mucho más eficientes a la eliminación de Gauss-Jordan para una gran cantidad de casos específicos. La mayoría de estos algoritmos mejorados tienen una complejidad computacional de O(n²). Algunos de los métodos más usados son:

• Para los problemas de la forma Ax = b, donde A es una matriz de Toeplitz simétrica, se puede utilizar la recursión de Levinson o alguno de los métodos derivados de éste. Un método derivado de la recursión de Levinson es la recursión de Schur, que es ampliamente usado en el campo del procesamiento digital de señales.
• Para los problemas de la forma Ax = b, donde A es una matriz singular o casi singular, la matriz A se descompone en el producto de tres matrices en un proceso llamado descomposición de valores singulares.

Solución de sistemas lineales en un anillo

Los métodos para resolver el sistema (1) sobre un anillo son muy diferentes a los considerados anteriormente. De hecho la mayoría de métodos usados en cuerpos, como la regla de Cramer, son inaplicables en anillos debido a que no existen inversos multiplicativos.

La existencia de solución del sistema (1) sobre los enteros requiere varias condiciones:

1. Para cada i

es divisor de bi .

2. Si la condición anterior se cumple para un determinado i existe un conunto de enteros formado por el conjunto de enteros que satisface la i-ésima ecuación, y existirá solución si la intersección

.

viernes, 22 de febrero de 2008

Sistema Lineal de Ecuaciones

1. Introducción

En matemática y álgebra lineal, un sistema lineal de ecuaciones es un conjunto de ecuaciones lineales sobre un cuerpo o un anillo conmutativo. Un ejemplo de sistema lineal de ecuaciones sería el siguiente:







La cuestión consiste en encontrar los valores desconocidos de las variables x1, x2 y x3 que satisfacen las tres ecuaciones.El problema de los sistemas lineales de ecuaciones es uno de los más antiguos de la matemática y tiene una infinidad de aplicaciones, como en procesamiento digital de señales, estimación, predicción y más generalmente en programación lineal así como en la aproximación de problemas no lineales de análisis numérico.


2. Descripción

En general, un sistema con m ecuaciones lineales n incógnitas puede ser escrito como:

a11x1 + a12x2 + … + a1nxn = b1
a21x1 + a22x2 + … + a2nxn = b2
:
:
am1x1 + am2x2 + … + amnxn = bm,

donde x1, ... ,xn son las incógnitas y los números aij son los coeficientes del sistema. Es posible reescribir el sistema separando con coeficientes con notación matricial:









Si representamos cada matriz con una única letra obtenemos:

Ax = b,

Donde A es una matriz m por n, x es un vector columna de longitud n y b es otro vector columna de longitud m. El sistema de eliminación de Gauss-Jordan se aplica a este tipo de sistemas, sea cual sea el cuerpo del que provengan los coeficientes.

Sistemas lineales reales

Representación gráfica














La intersección de dos planos no paralelos es una recta
Un sistema con incógnitas se puede representar en el n-espacio correspondiente.
En los sistemas con 2 incógnitas, el universo de nuestro sistema será el plano bidimensional, mientras que cada una de las ecuaciones será representada por una recta, si es lineal, o por una curva, si no lo es. La solución será el punto (o línea) donde intersecten todas las rectas y curvas que representan a las ecuaciones. Si no existe ningún punto en el que intersecten al mismo tiempo todas las líneas, el sistema es incompatible, o lo que es lo mismo, no tiene solución.
En el caso de un sistema con 3 incógnitas, el universo será el espacio tridimensional, siendo cada ecuación un plano dentro del mismo. Si todos los planos intersectan en un único punto, las coordenadas de éste serán la solución al sistema. Si, por el contrario, la intersección de todos ellos es una recta o incluso un plano, el sistema tendrá infinitas soluciones, que serán las coordenadas de los puntos que forman dicha línea o superficie.
Para sistemas de 4 ó más incógnitas, la representación gráfica no es intuitiva para el ser humano, por lo que dichos problemas no suelen enfocarse desde esta óptica.
Un sistema de ecuaciones, por las soluciones que se pueden presentar, se puede diferenciar los siguientes casos: compatible si tiene solución e incompatible si no la tiene, de ser compatible puede tener un número finito de soluciones, compatible - determinado, o infinitas soluciones, compatible - indeterminado. Quedando así la clasificación:







Si se representa gráficamente, la primera ecuación se corresponde con una circunferencia de radio y centrada en el origen de coordenadas, mientras que la segunda ecuación se corresponde con una recta que pasa por el origen y cuya pendiente es -0,5. Ambas intersectan en dos puntos únicos, por lo que el sistema es en el caso concreto de los sistemas lineales, los sistemas compatibles determinados son aquellos en los que todas sus ecuaciones son linealmente independientes. Los mísmos tienen una única solución, la cual se encuentra geométricamente en el punto en donde las rectas se cruzan.

Tipos de sistemas lineales:

1. Compatible indeterminadoUn sistema es compatible indeterminado cuando posee un número infinito de soluciones. Por ejemplo, el siguiente sistema:






Tanto la primera como la segunda ecuación se corresponden con la recta cuya pendiente es -0.5 y que pasa por el punto (0,0) , por lo que ambas intersectan en todos los puntos de dicha recta. El sistema es compatible por haber solución o intersección entre las rectas, pero es indeterminado al ocurrir esto en infinitos puntos.
En este tipo de sistemas, la solución genérica consiste en expresar una o más variables como función matemática del resto.
En los sistemas lineales compatibles indeterminados, al menos una de sus ecuaciones se puede hallar como combinación lineal del resto, es decir, es linealmente dependiente.


2. Incompatible

De un sistema se dice que es incompatible cuando no presenta ninguna solución. Por ejemplo, supongamos el siguiente sistema:






Las ecuaciones se corresponden gráficamente con dos rectas, ambas con la misma pendiente, Al ser paralelas, no se cortan en ningún punto, es decir, no existe ningún valor que satisfaga a la vez ambas ecuaciones.

Métodos de resolución:

1. SustituciónEl método de sustitución consiste en despejar en una de las ecuaciones cualquier incógnita, preferiblemente la que tenga menor coeficiente, para, a continuación, sustituirla en otra ecuación por su valor.
En caso de sistemas con más de dos incógnitas, la seleccionada debe ser sustituida por su valor equivalente en todas las ecuaciones excepto en la que la hemos despejado. En ese instante, tendremos un sistema con una ecuación y una incógnita menos que el inicial, en el que podemos seguir aplicando este método reiteradamente.Por ejemplo, supongamos que queremos resolver por sustitución este sistema:









En la primera ecuación, seleccionamos la incógnita Y por ser la de menor coeficiente y que posiblemente nos facilite más las operaciones, y la despejamos, obteniendo la siguiente ecuación










El siguiente paso será sustituir cada ocurrencia de la incógnita Y en la otra ecuación, para así obtener una ecuación donde la única incógnita sea la X.





Al resolver la ecuación obtenemos el resultado x=5 , y si ahora sustituimos esta incógnita por su valor en alguna de las ecuaciones originales obtendremos y=7 , con lo que el sistema queda ya resuelto.





2. IgualaciónEl método de igualación se puede entender como un caso particular del método de sustitución en el que se despeja la misma incógnita en dos ecuaciones y a continuación se igualan entre sí la parte derecha de ambas ecuaciones.Tomando el mismo sistema utilizado como ejemplo para el método de sustitución, si despejamos la incógnita en ambas ecuaciones nos queda de la siguiente manera:













Como se puede observar, ambas ecuaciones comparten la misma parte izquierda, por lo que podemos afirmar que las partes derechas también son iguales entre sí.













Llegados a este punto, la ecuación resultante es resoluble y podemos obtener el valor de la incógnita x, y a partir de aquí, sustituyendo dicho valor en una de las ecuaciones originales, obtener el valor de la y , que además ya se encuentra despejada.



3. ReducciónEste método suele emplearse mayoritariamente en los sistemas lineales, siendo pocos los casos en que se utiliza para resolver sistemas no lineales. El procedimiento, diseñado para sistemas con dos ecuaciones e incógnitas, consiste en transformar una de las ecuaciones (generalmente, mediante productos), de manera que obtengamos dos ecuaciones en la que una misma incógnita aparezca con el mismo coeficiente y distinto signo. A continuación, se suman ambas ecuaciones produciéndose así la reducción o cancelación de dicha incógnita , obteniendo así una ecuación con una sola incógnita, donde el método de resolución es simple.



Por ejemplo, en el sistema:












no tenemos más que multiplicar la primera ecuación por -2 para poder cancelar la incógnita Y. Al multiplicar, dicha ecuación nos queda así:





Si sumamos esta ecuación a la segunda del sistema original, obtenemos una nueva ecuación donde la incógnita Y ha sido reducida y que, en este caso, nos da directamente el valor de la incógnita X: