Clase Aplicaciones Numéricas en Investigación de Operaciones 09

Aplicaciones Numéricas en Investigación de Operaciones9

Prof. Gonzalo Müller

[email protected]

Postgrado de Investigación de Operaciones

Facultad de Ingeniería

Universidad Central de Venezuela

Aplicaciones Numéricas en Investigación de Operaciones – Prof. Gonzalo Müller – Clase 9 – GM – 2

Clase Anterior

� Números Aleatorios

� Generador lineal congruente

� Generador simple multiplicativo congruente

� Generador Estándar Mínimo

� Algoritmo de Bays y Durham

� rand, randi

� Método de transformación.� y = F-1(u)

� F(y) – u = 0 → y

� tabla


Clase Anterior

� Método de rechazo

� Monte Carlo

� Simulación

� Muestreo

� Integración por Monte Carlo


Recordando

� Métodos de interpolación polinomial:

� 1 paso: Estimación directa.

� Método de Langrage.

� Método de Neville.

� 2 pasos: Calculo de coeficientes y estimación.

� Método de Newton.

� Splines.

� Mínimos cuadrados.

� Evitar la extrapolación.


Operaciones Númericas Discretas

� En función de obtener un valor representativo en el mundo real es necesario obtener un valor numérico de las expresiones analíticas que se desarrollen.

� Una operación continua debe ser representada por una serie de operaciones discretas.

Los números pseudoaleatorios son una secuencia “no predecible”

pero reproducible, lo cual es de gran utilidad para experimentos


Diferenciación Numérica

� Se debe poseer:

� mecanismo para evaluar la función

� conjunto de puntos discretos que la defina.

� Se aproxima la función por:

� una serie de Taylor.

� una interpolación polinomial y luego se deriva.

� Errores de redondeo debido al computador

� Errores de truncamiento debidos a la interpolación.



Aproximación por series de Taylor

Partiendo de las series de Taylor, se tiene:

...(x)f!3

h(x)f

!2

h(x)fh f(x)h)f(x

...(x)f!3

h(x)f

!2

h(x)fh f(x)h)f(x

32

32

+′′′−′′+′−=−

+′′′+′′+′+=+

...(x)f12

h(x)fh f(x)2h)f(xh)f(x

...(x)f!3

h(x)fh2h)f(xh)f(x

42

3

+′′′′+′′+=−++

+′′′+′=−−+



� Se obtiene la diferenciación numérica central:

f´(x) = [f(x + h) – f(x – h)]/[2h] – f´´´(x) h2/6 – ...

f´(x) = [f(x + h) – f(x – h)]/[2h] +O(h2)

O(h2): error de truncamiento



� Se obtiene la diferenciación numérica central:

f´´(x)=[f(x + h)+f(x – h) – 2f(x)]/h2+f´´´´(x) h2/12 + ...

f´´(x) = [f(x + h) + f(x – h) – 2f(x)]/h2 +O(h2)

O(h2): error de truncamiento



� Cuando solo se dispone de un conjunto de puntos (x1, x2, ..., xn) que definen la función no es posible emplear la diferenciación numérica central.

Diferenciación numérica adelantada:

f´(x) = [f(x + h) – f(x)]/h – f´´(x) h/2 – f´´´(x) h2/6 – ...

f´(x) = [f(x + h) – f(x)]/h + O(h)

O(h): error de truncamiento



� Cuando solo se dispone de un conjunto de puntos (x1, x2, ..., xn) que definen la función no es posible emplear la diferenciación numérica central.

Diferenciación numérica atrasada:

f´(x) = [f(x) – f(x – h)]/h + f´´(x) h/2 – f´´´(x) h2/6 – ...

f´(x) = [f(x) – f(x – h)]/h + O(h)

O(h): error de truncamiento



h

error

error por truncamiento

O(h2)

O(h)

Partiendo de la serie de Taylor es posible desarrollar otras

expresiones para las derivadas con diferentes errores



h

errorerror por redondeo

f(x) – f(x – h)

f(x + h)+f(x – h)

� Construir las siguientes funciones en Matlab:

� dertayfx1: que calcule la primera derivada.

� dertayfx2: que calcule la segunda derivada.

� Evaluar f ´(x) y f ´´(x) para f(x) = e–x para x = 0.01, x = 0.1, x = 1, x = 10 y comparar con el valor “exacto”, utilizando diferentes h entre 0.5 y 0.0005, graficar los errores

� f(x)

� x

� h

� f ’(x)


Extrapolación de Richardson

� Permite agregar un factor de ajuste a la diferenciación numérica que mejora el valor del resultado obtenido.

D: valor real

d(h): aproximación obtenida a partir de h

O(h): error de la aproximación obtenida a partir de h

D = d(h) + O(h)


Extrapolación de Richardson

� Si O(h) tiene la forma:

O(hP) = C· hP

� Dado dos evaluaciones de D:

D = d(h1) + C· h1P

D = d(h2) + C· h2P

Se tiene la extrapolación de Richarson:

D = [(h1/h2)P d(h2) – d(h1)]/[(h1/h2)

P – 1]


� dertayrfx1: que calcule la primera derivada.

� dertayrfx2: que calcule la segunda derivada.


� f(x)

� x

� h

� f ’(x)h1=h

h2=h/4



Aproximación por polinomios

Teorema Fundamental del Calculo de la Diferencias Finitas

1. La n-esima diferencia de un polinomio de grado n es una constante.

2. La (n+1)-esima diferencia es 0.



Para obtener la diferencia finita de orden n de una función cualquiera es necesario aproximar la misma a través de un polinomio de grado n con n+1coeficientes independientes.

� Problemas:

� A medida que el grado de la diferencia es mayor la propagación por error de truncamiento dada la aproximación por un polinomio es mayor

� Debe evitar polinomios de grado mayor a 6 debido a las oscilaciones.



Splines Cúbicas.

� Es un buen interpolante global.

f´k, k+1(x) = Ak/6[3·(x – xk+1)2/(xk – xk+1) – (xk – xk+1)] –

Ak+1/6[3· (x – xk)2/(xk – xk+1) – (xk – xk+1)] +

(yk – yk+1)/(xk – xk+1)

f´´k, k+1(x) = Ak(x – xk+1)/(xk – xk+1) –

Ak+1(x – xk)/(xk – xk+1) – (xk – xk+1)



Mínimos cuadrados.

f (x) = A1+A2x +A3x2

f´(x) = A2 +A3x

f´´(x) = A3

n ∑xk ∑xk2 A1 ∑yk

∑xk ∑xk2 ∑xk

3 A2 ∑xk yk∑xk

2 ∑xk3 ∑xk

4 A3 ∑xk2 yk


� calpolmc: que calcule los coeficientes A1, A2 y A3.

� derpolmcfx1: que calcule la primera derivada.

� derpolmcfx2: que calcule la segunda derivada.


� f(x)

� x

� h

� f ’(x)



Aproximación Clásica

df(x)/dx = ∆f(x)/∆x

df(x)/dx = [f(x + ∆x) - f(x)]/ ∆x

∆nf(x) = ∆[∆n-1f(x)]

dnf(x)/dxn = [∆n-1f(x + ∆x) - ∆n-1f(x)] /∆xn

dnf(x)/dxn =(dn-1f(x + ∆x)/dxn-1 - dn-1f(x)/dxn-1)/∆x



f''(x) =(∆f(x +∆x) – ∆f(x))/∆x2

f'''(x) =(∆2 f(x +∆x) – ∆2f(x))/∆x3

xk f(xk) ∆f(xk) ∆2f(x) ∆3f(x) ∆4f(x)

x0 f(x0) f(x1)-f(x0) ∆f(x1)-∆f(x0) ∆2f(x1)-∆2f(x0) ∆3f(x1)-∆

3f(x0)


3f(x1)


3f(x2)

x3 f(x3) f(x4)-f(x3) ∆f(x4)-∆f(x3) ∆2f(x4)-∆2f(x3)

x4 f(x4) f(x5)-f(x4) ∆f(x5)-∆f(x4)

x5 f(x5) f(x6)-f(x5)

x6 f(x6)

∆x = 1



f''(x) =(f'(x +∆x) – f'(x))/∆x

f'''(x) =(f''(x +∆x) – f''(x))/∆x

xk f(xk) f'(xk) f''(x) f'''(x) f''''(x)

x0 f(x0) f(x1)-f(x0) f'(x1)-f'(x0) f''(x1)-f''(x0) f'''(x1)-f'''(x0)



x3 f(x3) f(x4)-f(x3) f'(x4)-f'(x3) f''(x4)-f''(x3)

x4 f(x4) f(x5)-f(x4) f'(x5)-f'(x4)

x5 f(x5) f(x6)-f(x5)

x6 f(x6)

∆x = 1


� derclasicafx1: que calcule la primera derivada.

� derclasicafx2: que calcule la segunda derivada.

� Evaluar f ´(x) y f ´´ (x) para f(x) = e–x para x = 0.01, x = 0.1, x = 1, x = 10 y comparar con el valor “exacto”, utilizando diferentes h entre 0.5 y 0.0005, graficar los errores

� f(x)

� x

� ∆x

� f ’(x)

Se necesitan n+1 puntos para calcular la n-esima derivada



� La diferenciación numérica debe ser usada como la última opción.

Debido a los errores presentes en la evaluación:

Dado la limitación en la representación de los números reales que impone el computador:

∆x, f(x + ∆x) - f(x)

x

f(x)-x) f(xlim

dx

df(x)0x ∆

∆+=

→∆


Diferenciación Numérica en Matlab

� diff: Calcula diferencias, ∆f(x) ó ∆x.

Ejemplo:

x = [0.8 5 2 6.2 7]

dx = diff(x);

diff(x) Calcula las diferencias sucesivas de los puntos de x. (n – 1 diferencias, teniendo x n puntos)

diff(x,n) Calcula la n-esima diferencia de x ≡ ∆nf(x) (x debe tener al menos n+1 puntos)


Integración Numérica

� Es una operación común y estable.

� Básicamente constituye una suma.

� Existen dos tipos de métodos:

� Particionado equidistante del intervalo.

� La evaluación de la función no es cotosa.

� Aproxima f(x) utilizando un polinomio de grado n-1

� El esquema de cuadratura obtiene el valor exacto de la integral si el integrando es un polinomio.

∑∫=

→n

1kkk

b

a

)f(xCf(x)dx



� Particionado variable del intervalo, en función de mejorar la precisión.

� La evaluación de la función no cotosa.

� Permite la evaluación integrales con singularidades.



Regla del Trapezoide

� Suma de trapecios

� Partición equidistante del intervalo.

∑∫−

=

+ +∆

=1n

1kk1k

b

a

)f(x)f(x2

xf(x)dx

x

f(x)

xk xk+1

error

I=Área

� Construir la siguiente función en Matlab:

� inttrapfx: que calcule la integral trapezoidal.

� Evaluar para f(x) = e–x para a = 0.01, b = 10 y comparar con el valor “exacto”, utilizando diferentes n entre 5 y 500, graficar los errores

� f(x)

� n

� a, b

� I(f(x))



Regla de Simpson

� Es superior a Trapezoide.

� Es lo que se conoce como hiper-eficiente.


[ ])f(x)f(x4)f(x3

xf(x)dx 210

x

x

2

0

++∆

=∫

x

f(x)

x0 x2

error

I=Área

x1

parábola



Regla de Simpson

� Es superior a Trapezoide.

� Es lo que se conoce como hiper-eficiente.


∑ ∫∫=

=

+2-n

1,3,...k

x

x

b

a

2k

k

f(x)dxf(x)dx

x

f(x)

x0 x2

error

I=Área

x1

parábola



Regla de Bode

� Es superior a Simpson

� Exacto para polinomios de hasta 5º grado.


[ ])f(x14)f(x64)f(x24)f(x64)14f(x45

xf(x)dx 43210

x

x

4

0

++++∆

=∫



Espaciado arbitrario

Aproximando f(x) con una interpolación polinomialde Lagrange, Wk:

j:0, 1, ..., n-1

k

1-n

0kk

b

a

W)f(xf(x)dx ∑∫=

=

k

1-n

0k

jk

1j1j

Wx1j

ab∑

=

++

=+

−


� intfijofx: que calcule la integral por espaciado arbitrario.

� Evaluar para f(x) = e–x para a = 0.01, b = 10 y comparar con el valor “exacto”, utilizando diferentes k entre 5 y 500, graficar los errores

� f(x)

� x =[a, x2,x3, ..., b]� I(f(x))



Romberg

Es una combinación de la regla trapezoidal y la extrapolación de Richarson

� Se considera uno de los métodos más eficientes.

� Superior a Bode.

El error tiene la forma:

O(h2)= C1 h2 + C2 h

4 + ···

donde dada la partición equidistante de 2k-1 intervalos:

h = (b – a)/2k-1



� Dado dos evaluaciones de I, se tiene la extrapolación de Richarson:

I = [(h1/h2)P i(h2) – i(h1)]/[(h1/h2)

P – 1] h1P

i(h1): Integración numérica trapezoidal con k = k1, h1

= (b – a)/2k1-1

i(h2): Integración numérica trapezoidal con k = k2, h2

=(b – a)/2k2-1




I = [2 (k2-k1)P ik2 – ik1]/[2(k2-k1)P – 1]




k2 – k1= 1

Ik2 = [2P ik2 – ik2-1]/[2P – 1]



� Dado más de dos evaluaciones de I, se tiene la extrapolación de Richarson:

k2 – k1= 1

Ik2 = [22 ik2 – ik2-1]/[22 – 1]

i1i2 I2,2i3 I3,2i4 I4,2i5 I5,2… …




k2 – k1= 1

Ik2,2 = [22 ik2 – ik2-1]/[22 – 1]

i1i2 I2,2i3 I3,2i4 I4,2i5 I5,2… …




k2 – k1= 1

Ik2,P = [2P Ik2,P–2 – Ik2-1,P–2]/[2P – 1]

i1i2 I2,2i3 I3,2 I3,4i4 I4,2 I4,4 I4,6i5 I5,2 I5,4 I5,6 I5,8… … … … …




Ik,p = [2P Ik,P–2 – Ik-1,P–2]/[2P – 1]





Ik,p = [2P Ik,P–2 – Ik-1,P–2]/[2P – 1]


Mejor integral que se puede estimar partiendo de tres evaluaciones




Ik,p = [2P Ik,P–2 – Ik-1,P–2]/[2P – 1]


Se puede repetir el proceso hasta que la diferencia entre estimaciones sucesivas sea menor que un error dado




Ejemplo:

I2,2 = [22 i2 – i1]/[22 – 1]

I3,2 = [22 i3 – i2]/[22 – 1]

I3,4 = [24 I3,2 – I2,2]/[24 – 1]

i1i2 I2,2i3 I3,2 I3,4


� intrombfx: que calcule la integral por romberg.

� Evaluar para f(x) = e–x para a = 0.01, b = 10 y comparar con el valor “exacto”, utilizando diferentes k entre 5 y 500, graficar los errores

� f(x)

� k

� a, b

� I(f(x))



Esquema de Gauss

� Selecciona:

� los pesos Wk.

� los n apropiados puntos.

� Es empleado para la solución de:

w(x) es la función de peso, que puede contener singularidades pero es integrables

∫b

a

w(x)f(x)dx



� Si se aproxima f(x) con una interpolación polinomial:

I = ∑Wkf(xk)

los coeficientes y los puntos pueden ser determinados utilizando:

j:0,1, ..., 2n -1

∑∫=

=n

1k

jkk

b

a

j xWdxw(x)x



� Establecer estos valores es un proceso complejo, por lo que existen w(x) clásicas con xk y Wk predefinidos:

Nombre w(x) a b

Legendre 1 -1 1

Laguerre e-x 0 ∞

Hermite e-x2 -∞ ∞

Chebyshev (1 – x2)-1/2 -1 1


Integración Numérica en Matlab

� trapz: Calcula la integral de una función aplicando la regla trapezoidal con ∆x = 1.

quad(f(xk))

Ejemplo: integral del seno entre 0,5 y 3,1 con un error de 1e-8,

fx = sin(0.5:0.5e-8:3.1);

isen = 0.5e-8*trapz(fx);

∑∫−

=

+ +=1n

1kk1k

b

a

)f(x)f(x2

1f(x)dx


Integración Numérica en Matlab

� quad: Calcula una integral definida.

quad(función, limite inferior, limite

superior, error)

Ejemplo: integral del seno entre 0,5 y 3,1 con un error de 1e-8,

isen = quad(@sin, 0.5, 3.1, 1e-8);


Se define una g(x) > f(x), x є [a, b], cuya área es conocida.

Se comienza un proceso de ensayo, Y y X, donde la probabilidad de obtener puntos que pertenezcan al área bajo la curva es proporcional a la fracción de área ocupada por f(x) de g(x)

Integración por Monte Carlo

f(x)

a b

g(x)


Si g(x) = C

Integración por Monte Carlo

a)C-p(bdxf(x)b

a

=∫

f(x)

a b

g(x)C


� intmcarlofx: que calcule la integral por Monte Carlo.

� Evaluar para f(x) = e–x para a = 0.01, b = 10 y comparar con el valor “exacto”, utilizando diferentes nentre 5 y 5000, graficar los errores

� f(x)

� n

� a, b

� I(f(x))


Resumen

� Diferenciación Numérica

� Aproximación por series de Taylor

� Extrapolación de Richardson

� Aproximación por polinomios: Splines Cúbicas, Mínimos cuadrados

� Aproximación Clásica.

� Diferenciación Numérica en Matlab: diff.


Resumen

� Integración Numérica

� Regla del Trapezoide

� Regla de Simpson

� Regla de Bode

� Espaciado arbitrario

� Romberg

� Esquema de Gauss

� Integración Numérica en Matlab: trapz,quad

� Integración por Monte Carlo

Documents

Clase Aplicaciones Numéricas en Investigación de Operaciones 09