martes, 7 de junio de 2011

Diferenciacion e Integracion Numerica

Diferenciacion Numerica

El cálculo de la derivada de una función puede ser un proceso "difícil" ya sea por lo complicado de la definición analítica de la función o por que esta se conoce únicamente en un número discreto de puntos.
Estudiaremos técnicas para aproximar las derivadas de una función y veremos el análisis de error de dichas formulas

•Para aproximar la derivada numéricamente usaremos cocientes de diferencias. 
•Para derivar las formulas usaremos el Teorema de Taylor

Existen 3 diferentes tipos de aproximación numérica:

•Aproximación a la primera derivada con diferencias hacia atrás
•Aproximación a la primera derivada con diferencias hacia adelante
• Aproximación a la primera derivada con diferencias centrales

Aproximación a la primera derivada con diferencias hacia atrás

La serie de Taylor se puede expandir hacia atrás para calcular un valor anterior sobre el valor actual, dada por: 






Truncando la ecuación después de la primera derivada y ordenando los términos se obtiene:






 Donde los errores es 0 (h) y el diferencial indica la primer diferencia dividida hacia atrás. 

Aproximación a la primera derivada con diferencias hacia adelante


Donde al diferencial se le conoce como la primera diferencia hacia adelante y a h se le llama tamaño del paso, esto es, la longitud del intervalo sobre el cual se hace la aproximación. Se le llama diferencia " hacia adelante " ya que usa los datos(i) e (i+1) para estimar la derivada. Al termino completo (o sea, la diferencial entre h ) se conoce como primera diferencia dividida finita.


Aproximación a la primera derivada con diferencias centrale
 Una tercera forma de aproximar la primer derivada es restar la ecuación de la expansión en serie de Taylor hacia adelante:


Para obtener: 

Que se puede resolver para:

Esta ultima ecuación es una representación de las diferencias centrales de la primera derivada. Nótese que el error de truncamiento es del orden de en contraste con las diferencias divididas hacia adelante y hacia atrás, las cuales fueron de orden h. 

Por lo tanto, el análisis de la serie de Taylor ha llevado a la información practica de que la diferencia central es la representación mas exacta de la derivada. Por ejemplo, si se parte el tamaño del paso a la mitad usando diferencias hacia atrás o hacia adelante, el error se reducirá aproximadamente a la mitad, mientras que para diferencias centrales, el error se reduce a la cuarta parte.

Integracion Numerica

En ingeniería se presenta con frecuencia la necesidad de integrar una función que sería, en general, de una de las tres formas siguientes:

1.Una función simple y continua tal como un polinomio, una función exponencial o una función trigonométrica.
2.Una función complicada y continua que es difícil o imposible de integrar directamente.
3.Una función tabulada en donde los valores dex yf(x) se dan en un conjunto de puntos discretos, como es el caso a menudo, de datos experimentales.

 En el primer caso, la integral simplemente es una función que se puede evaluar fácilmente usando métodos analíticos aprendidos en el cálculo. En los dos últimos casos, sin embargo, se deben emplear métodos aproximados. Las fórmulas de integración de Newton-Cotes son los esquemas más comunes dentro de la integración numérica. Se basan en la estrategia de reemplazar una función complicada o un conjunto de datos tabulares con alguna función aproximada que sea más fácil de integrar. La integral se puede aproximar usando una serie de polinomios aplicados por partes a la función o a los datos sobre intervalos de longitud constante. Se dispone de las formas abierta y cerrada de las fórmulas de Newton-Cotes. 

Las formas cerradas son aquellas en donde los puntos al principio y al final de los límites de integración se conocen. Las fórmulas abiertas tienen los límites de integración extendidos más allá del rango de los datos. Las fórmulas abiertas deNewton-Cotes, en general, no se usan en la integración definida. Sin embargo, se usan extensamente en la solución de ecuaciones diferenciales ordinarias.




Minimos Cuadrados

Mínimos cuadrados es una técnica de análisis numérico encuadrada dentro de la optimización matemática, en la que, dados un conjunto de pares (o ternas, etc), se intenta encontrar la función que mejor se aproxime a los datos (un "mejor ajuste"), de acuerdo con el criterio de mínimo error cuadrático.

En su forma más simple, intenta minimizar la suma de cuadrados de las diferencias ordenadas (llamadas residuos) entre los puntos generados por la función y los correspondientes en los datos. Específicamente, se llama mínimos cuadrados promedio (LMS) cuando el número de datos medidos es 1 y se usa el método de descenso por gradiente para minimizar el residuo cuadrado. Se puede demostrar que LMS minimiza el residuo cuadrado esperado, con el mínimo de operaciones (por iteración), pero requiere un gran número de iteraciones para converger.

Desde un punto de vista estadístico, un requisito implícito para que funcione el método de mínimos cuadrados es que los errores de cada medida estén distribuidos de forma aleatoria. El teorema de Gauss-Márkov prueba que los estimadores mínimos cuadráticos carecen de sesgo y que el muestreo de datos no tiene que ajustarse, por ejemplo, a una distribución normal. También es importante que los datos recogidos estén bien escogidos, para que permitan visibilidad en las variables que han de ser resueltas (para dar más peso a un dato en particular, véase mínimos cuadrados ponderados).






lunes, 6 de junio de 2011

Interpolacion de Newton

Se basa en la obtención de un polinomio a partir de un conjunto de puntos dado, aproximándose lo mas posible a la curva buscada. 

La ecuación general para la obtención de la función por este método es:

Donde las “bi” se obtienen mediante la aplicación de una serie de funciones incluidas en una tabla de diferencias. 

Ejemplo:

      Suponiendo que tenemos 4 puntos, la tabla de diferencias tiene la siguiente forma:



Con esto, la ecuación quedaría de la siguiente forma:
      Teniendo los siguientes puntos:


     Calculamos su tabla:

     Obteniendo el siguiente polinomio:






Interpolacion de Lagrange

Este método de interpolación consiste en encontrar una función que pase a través de n puntos dados.

Un polinomio en series de potencias es

g(x) = a+ a1x + a2x+ ... + anxn

La formula de interpolación de Lagrange de orden n es











Ejemplo. Del siguiente conjunto ajuste un polinomio con n = 3 puntos para el valor de t = 251
x
y
94
929
205
808
371
860












y(251) = 890.5





Metodo de Lu


DESCOMPOSICIÓN LU





Su nombre se deriva de las palabras inglesas "Lower" y "Upper", que en español se traducen como "Inferior" y "Superior". Estudiando el proceso que se sigue en la descomposición LU es posible comprender el por qué de este nombre, analizando cómo una matriz original se descompone en dos matrices triangulares, una superior y otra inferior.


La descomposición LU involucra solo operaciones sobre los coeficientes de la matriz [A], proporcionando un medio eficiente para calcular la matriz inversa o resolver sistemas de álgebra lineal.


Primeramente se debe obtener la matriz [L] y la matriz [U].


[L] es una matriz diagonal inferior con números 1 sobre la diagonal. [U] es una matriz diagonal superior en la que sobre la diagonal no necesariamente tiene que haber números 1.


El primer paso es descomponer o transformar [A] en [L] y [U], es decir obtener la matriz triangular inferior [L] y la matriz triangular superior [U].

PASOS PARA ENCONTRAR LA MATRIZ TRIANGULAR SUPERIOR (MATRIZ [U])
Hacer cero todos los valores abajo del pivote sin convertir este en 1. 
Para lograr lo anterior se requiere obtener un factor el cual es necesario para convertir a cero los valores abajo del pivote. 
Dicho factor es igual al número que se desea convertir en cero entre el número pivote. 
Este factor multiplicado por -1 se multiplica luego por el pivote y a ese resultado se le suma el valor que se encuentra en la posición a cambiar (el valor en la posición que se convertirá en cero). Esto es: 


- factor * pivote + posición a cambiar

PASOS PARA ENCONTRAR LA MATRIZ TRIANGULAR INFERIOR (MATRIZ [L])

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
Obtener la matriz triangular inferior L y la matriz triangular superior U. 
Resolver Ly = b (para encontrar y). 
El resultado del paso anterior se guarda en una matriz nueva de nombre "y". 
Realizar Ux = y (para encontrar x). 
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. 


EJEMPLO 1 DE DESCOMPOSICIÓN LU


PROBLEMA: Encontrar los valores de x1, x2 y x3 para el siguiente sistema de ecuaciones:




NOTA: Recuérdese que si la matriz es 2x2 se hará 1 iteración; si es 3x3, 2 iteraciones; si es 4x4, 3 iteraciones; y así sucesivamente.


SOLUCIÓN:


4
- 2
- 1
9
[A] =
5
1
- 1
[B] =
7
1
2
- 4
12


ITERACIÓN 1


factor 1 = (a21 / a11) = 5 / 4 = 1.25
factor 2 = (a31 / a11) = 1 / 4 = 0.25


Encontrando [U]


fila 2 = - (factor 1) * (fila 1) + (fila 2)
fila 3 = - (factor 2) * (fila 1) + (fila 3)


a11 = a11
a12 = a12
a13 = a13
a21 = - (1.25) * (4) + (5) = 0
a22 = - (1.25) * (- 2) + (1) = 3.5
a23 = - (1.25) + (- 1) + (- 1) = 0.25
a31 = - (0.25) * (4) + (1) = 0
a32 = - (0.25) * (- 2) + (2) = 2.5
a33 = - (0.25) * (- 1) + (- 1) = - 0.75


4
- 2
- 1
[U] =
0
3.5
0.25
0
2.5
- 0.75


Encontrando [L]



1
0
0
[L] =
1.25
0
0
0.25
0
0



ITERACIÓN 2


factor 3 = (u32 / u22) = 2.5 / 3.5 = 0.7142857143


Encontrando [U]


fila 3 = - (factor 3) * (fila 2) + (fila 3)
a31 = - (2.5 / 3.5) * (0) + (0) = 0
a32 = - (2.5 / 3.5) * (3.5) + (2.5) = 0
a33 = - (2.5 / 3.5) * (0.25) + (- 0.75) = - 0.9285714286



4
- 2
- 1
[U] =
0
3.5
0.25
0
0
- 0.9285714286


Encontrando [L]




1
0
0
[L] =
1.25
1
0
0.25
0.7142857143
1

Ahora ya se tiene la matriz [U] y la matriz [L]. El siguiente paso es resolver: Ly = b para encontrar la matriz y. En pocas palabras es como que se pidiera resolver el siguiente sistema de ecuaciones, encontrando los valores de y1, y2 y y3:




Al resolver el sistema anterior, se obtienen los siguientes valores para y1, y2 y y3:





El último paso es resolver Ux = y para encontrar la matriz x. En otras palabras es como que se pidiera resolver el siguiente sistema de ecuaciones, encontrando los valores de x1, x2 y x3:




La solución del sistema es:




Este es finalmente el valor de x1, x2 y x3; es decir, la respuesta del ejercicio utilizando la descomposición LU.