View
7
Download
0
Category
Preview:
Citation preview
Tema 7
Métodos numéricos paraecuaciones funcionales
Randall Romero Aguilar, PhD
Universidad de Costa RicaSP6534 - Economía Computacional
I Semestre 2020Última actualización: 10 de marzo de 2020
Tabla de contenidos
1. Introducción
2. Interpolación polinomial
3. Interpolación con splines
4. Consideraciones adicionales
5. Paquete CompEcon
6. Ecuaciones funcionales
1. Introducción
En muchas aplicaciones de la economía computacional,necesitamos reemplazar una función analíticamente intratablef :ℜn 7→ ℜ con una aproximación numéricamente tratable f .
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 1
É En algunas aplicaciones, f puede ser evaluada en cualquierpunto de su dominio, pero con dificultad, por lo que deseamosreemplazarla con una aproximación f con la que es más fáciltrabajar.É En otras aplicaciones, f está definida implícitamente en una
ecuación funcional, pero la ecuación carece de una soluciónde forma cerrada, por lo que deseamos calcular una soluciónaproximada f .
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 2
É Primero estudiaremos interpolación, una estrategia generalpara formar una aproximación tratable de una función quepueda ser evaluada en cualquier punto de su dominio.É Los métodos para resolver ecuaciones funcionales están
basados en principios de interpolación, que estudiaremosposteriormente.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 3
Interpolación
É Consideremos una función real f definida en un intervalo dela recta real que puede ser evaluada en cualquier punto de sudominio.É En general, aproximaremos f usando una función f que es
una combinación lineal finita de n funciones base conocidasϕ1,ϕ2, . . . ,ϕn de nuestra escogencia:
f (x)≈ f (x)≡n∑
j=1cjϕj(x).
É Fijaremos los n coeficientes de la base c1, c2, . . . , cnrequiriendo que f interpole, es decir, que concuerde con f , enn nodos de interpolación x1,x2, . . . ,xn de nuestra escogencia.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 4
É La base más fácilmente reconocible es la base de monomios
ϕ0(x) = 1ϕ1(x) = xϕ2(x) = x2
...
ϕn(x) = xn,
quw puede utilizarse para construir aproximacionespolinomiales:
f (x)≈ f (x)≡ c0 + c1x + c2x2 + . . .+ cnxn.
É No obstante, como veremos en breve, podemos utilizar otrasfunciones base para aproximar funciones.É Además, hay diferentes maneras de escoger los nodos de
interpolación.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 5
É Sin importar cómo escojamos las n funciones base y nodos,calcular los coeficientes base se reduce a resolver unaecuación lineal:
n∑j=1
cjϕj(xi) = f (xi), i = 1,2, . . . ,n.
É Escribimos la ecuación de interpolación en forma matricialϕ1(x1) ϕ2(x1) . . . ϕn(x1)ϕ1(x2) ϕ2(x2) . . . ϕn(x2)
......
. . ....
ϕ1(xn) ϕ2(xn) . . . ϕn(xn)
matriz de interpolación Φ
c1c2
...cn
c
=
f (x1)f (x2)
...f (xn)
y
es decir, Φc = y donde, para i = 1,2, . . . ,n y j = 1,2, . . . ,n,
Φij = ϕj(xi) y yi = f (xi)
y c es el vector n× 1 de coeficientes base a ser determinado.©Randall Romero Aguilar, PhD SP-6534 / 2020.I 6
É En teoría, un esquema de interpolación está bien definido siescogemos las funciones base y los nodos de interpolación detal manera que la matriz de interpolación Φ sea invertible.É No obstante, en la práctica, la matriz de interpolación debe
cumplir el requisito más estricto de no ser mal condicionada.É De lo contario, no será posible calcular los coeficientes base
con precisión.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 7
Idealmente, un esquema de interpolación debe satisfacer variascondiciones.É Debe ser teoréticamente posible alcanzar una aproximación
arbitrariamente precisa incrementando el número defunciones base y nodos de interpolación.É Debe ser posible resolver la ecuación de interpolación de
manera rápida y precisa.É Debe ser relativamente barato evaluar, diferenciar, integrar y
manipular la aproximación resultante.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 8
É Los esquemas de interpolación solo difieren en cómo seescogen las funciones base ϕj y los nodos de interpolación xi .É Desarrollaremos esquemas de interpolación basados en dos
clases de funciones base:É polinomios ortogonalesÉ splines polinomiales por partes
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 9
2. Interpolación polinomial
Teorema de Weierstrass
É El teorema de Weierstrass afirma que toda función real puedeser aproximada a un grado arbitrario de precisión en unintervalo acotado con un polinomio.É Específicamente, si f es continua en [a,b] y ε > 0, entonces
existe un polinomio p tal que
maxx∈[a,b]
|f (x)− p(x)|< ε.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 10
É El teorema de Weierstrass motiva el uso de polinomios paraaproximar funciones continuas.É No obstante, el teorema no es muy práctico:É no da ninguna guía sobre cómo encontrar el polinomio que
provee un nivel deseado de precisión.É ni siquiera nos dice de qué grado es el polinomio requerido.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 11
Interpolación polinomial ingenua
Una manera de construir una aproximación polinomial f de gradon para una función f en el intervalo acotado [a,b] procede así:
1. Escribimos la aproximación
f (x)≡n∑
j=0cjx j
en términos de la base de monomios 1,x ,x2, . . . ,xn.
2. Fijamos los n+ 1 coeficientes base c0, c1, . . . , cn requiriendoque f coincida con f en los n+ 1 nodos equi-espaciados deinterpolación xi = a + ih, donde h = b−a
n .
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 12
-1.0
1.0x0 x1 x2 x3
-1.0
1.0x4 x5 x6 x7
-1 1-1.0
1.0x8
-1 1
x9
-1 1
x10
-1 1
x11
Monomial Basis Functions on [-1,1]
Figura 7.1: Funciones base monomiales en [−1,1]
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 13
É Este esquema de interpolación polinomial, sufre de dosproblemas serios pero distintos.
1. La matriz de interpolación es una matriz Vandermonde, que esmás mal condicionada conforme aumenta el grado delpolinomio de interpolación.
2. Hay funciones para las que el error de aproximación explotaconforme aumenta el grado del polinomio de interpolación.
É El ejemplo clásico es la función de Runge:
f (x) = 11+ 25x2 , −1≤ x ≤ 1.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 14
1.00 0.75 0.50 0.25 0.00 0.25 0.50 0.75 1.000.0
0.2
0.4
0.6
0.8
1.0y
y = 11 + 25x2
Runge's Function
Figura 7.2: Función de Runge
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 15
Polinomios de Chebyshev
É Los polinomios de Chebyshev son muy útiles para interpolarfunciones.É Formalmente, el polinomio de Chebyshev de grado n está
definido por
Tn(z) = cos(n cos−1 z), para z ∈ [−1, 1]
É A primera vista, aesta expresión para nada parece unpolinomio!É Veremos que sí son polinomios, con la ayuda de la identidad
trigonométrica cos(u + v)+ cos(u − v) = 2cosu cosv
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 16
Usando la definición anterior partimos de:
Tn+1(z)+Tn−1(z) = cos[(n+ 1) cos−1 z] + cos[(n− 1) cos−1 z]= cos[n cos−1 z +cos−1 z] + cos[n cos−1 z − cos−1 z]= 2cos(n cos−1 z) cos(cos−1 z)= 2zTn(z)
Es decir, dados dos polinomios de Chebyshev consecutivos,podemos encontrar el siguiente por medio de
Tn+1(z) = 2zTn(z)−Tn−1(z)
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 17
Es fácil obtener los primeros dos polinomios a partir de ladefinición:
T0(z) = cos(0cos−1 z) = 1T1(z) = cos(1cos−1 z) = z
y los siguientes usando Tn+1(z) = 2zTn(z)−Tn−1(z)
T2(z) = 2z2 − 1T3(z) = 4z3 − 3zT4(z) = 8z4 − 8z2 + 1T5(z) = 16z5 − 20z3 + 5zT6(z) = 32z6 − 48z4 + 18z2 − 1T7(z) = 64z7 − 112z5 + 56z3 − 7z
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 18
-1.0
1.0T0(z) T1(z) T2(z) T3(z)
-1.0
1.0T4(z) T5(z) T6(z) T7(z)
-1 1-1.0
1.0T8(z)
-1 1
T9(z)
-1 1
T10(z)
-1 1
T11(z)
Chebychev Polynomial Basis Functions on [-1,1]
Figura 7.3: Polinomios de Chebyshev en [−1,1]
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 19
Como Tn(z) = cos(n cos−1 z), entonces −1≤ Tn(z)≤ 1.
Valores extremos
n cos−1 z = iπ⇒z = cos
� inπ
�i = 0, . . . ,n
Raíces
n cos−1 z = iπ− π2 ⇒
z∗ = cos
�2i − 12nπ
�i = 1, . . . ,n
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 20
-1 0 1-1
0
1
08
28
48
68
88
18 38 58 78
Extrema and zeros of a Chebyshev polynomial
Figura 7.4: Valores extremos y raíces de T4(z)
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 21
Interpolación con nodos de Chebyshev
É La teoría nos dice que la mejor manera de aproximar unafunción continua con un polinomio en un intervalo acotado[a,b] es interpolarlo en los llamados nodos de Chebyshev:
xi =a + b
2+
b − a2
cos
�2n− 2i + 12n
π
�, i = 1,2, . . . ,n.
É Los n nodos de Chebyshev corresponden a los n ceros delpolinomio de Chebyshev Tn(z), transformados linealmentepara abarcar el intervalo [a,b] en vez del [−1,1].É Los nodos de Chebyshev no están equi-espaciados y no
incluyen los puntos finales del intervalo de aproximación.É Están más cercanos entre sí hacia los límites del intervalo de
aproximación, y más alejados cerca del centro.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 22
n = 3
n = 4
n = 5
n = 6
n = 7
n = 8
-1 0 1
n = 9
Chebyshev nodes
Figura 7.5: Nodos de Chebyshev en [−1,1]
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 23
Si f es continua. . .É Teorema de Rivlin: la interpolación polinomial con nodos de
Chebyshev es cercanamente óptima, es decir, alcanza un errorde aproximación que es muy cercano al error mínimoobtenible con otro polinomio del mismo grado.É Teorema de Jackson: la interpolación polinomial con nodos de
Chebyshev es consistente, es decir, el error de aproximacióndesaparece conforme aumenta el grado del polinomio.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 24
1.00 0.75 0.50 0.25 0.00 0.25 0.50 0.75 1.00x
0.0
0.5
1.0
1.5
2.0Er
ror
Runge's Function 11th-DegreePolynomial Approximation Error.
Chebychev NodesUniform Nodes
Figura 7.6: Error de aproximación polinomial para la función de Runge
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 25
É Cuando la función que se está aproximando es suave, lainterpolación polinomial con nodos de Chebyshevgeneralmente exhibe errores que oscilan muy uniformementea lo largo del intervalo de aproximación.É Esta característica se conoce como la propiedad de
equi-oscilación de Chebyshev.É Consideremos la interpolación de Chebyshev para exp(−x) en
[−1,1].É La interpolación con nodos de Chebyshev evita la
inestabilidad mostrada cerca de los extremos del intervalo porla interpolación polinomial con nodos uniformes porque losnodos de Chebyshev están más concentrados cerca de losextremos del intervalo.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 26
1.00 0.75 0.50 0.25 0.00 0.25 0.50 0.75 1.00x
6
4
2
0
2
4
6Er
ror
1e 10 Chebychev Approximation Error - Function
Figura 7.7: Error de aproximación polinomial Chebyshev para e−x
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 27
É Interpolar en los nodos de Chebyshev tiene muchas ventajas.É No obstante, el uso de nodos de Chebyshev por si solo no
elimina la mala condicionadidad.É La mala condicionadidad surge por la escogencia de las
funciones base, no por la escogencia de los nodos deinterpolación.É Afortunadamente, hay una alternativa a la base de monomios
que es ideal para expresar interpolaciones polinomiales connodos de Chebyshev.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 28
Interpolación con polinomios de Chebyshev
É La base óptima para expresar interpolaciones polinomialescon nodos Chebyshev se conoce como la base de polinomiosde Chebyshev.É Recordemos que los polinomios de Chebyshev están definidos
para z ∈ [−1,1] por
T0(z) = 1T1(z) = zT2(z) = 2z2 − 1T3(z) = 4z3 − 3z
...
Tj(z) = 2zTj−1(z)−Tj−2(z).
É Pueden ser definidos para intervalos arbitrarios [a,b] vía latransformación z = 2 x−a
b−a − 1 para x ∈ [a,b].©Randall Romero Aguilar, PhD SP-6534 / 2020.I 29
É Combinando la base de polinomios de Chebyshev con losnodos de interpolación de Chebyshev resulta en una ecuaciónde interpolación extremadamente bien condicionada.É La matriz de interpolación Φ asociada con la interpolación de
Chebyshev tiene elemento típico
Φij = cos
�(n− i + 0.5)(j − 1)π
n
�.
É La matriz de interpolación de Chebyshev es ortogonal, esdecir, Φ′Φ es diagonal.É Su número de condición es
p2, sin importar el grado de
interpolación, lo cual está cerca del mínimo absoluto de 1.É Esto implica que los coeficientes base puede calcularse con
precisión, sin importar el número de funciones base.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 30
5 10 15 20 25 303
2
1
0
1
2
3Lo
g10
Erro
rLog10 Polynomial Approximation Error for Runge's Function
Chebychev NodesUniform Nodes
Figura 7.8: Interpolación Matrix Condition Number
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 31
3. Interpolación con splines
Introducción
É Los splines polinomiales por partes, o simplemente splines ,son una clase rica y flexible de funciones que puedenutilizarse en vez de polinomios de algo grado para aproximaruna función real en un intervalo acotado.É En general, un spline de orden k consiste en una serie de
segmentos polinomiales de grado k unidos de tal manera quese preserve la continuidad de las derivadas de orden k − 1 ymenores.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 32
É Los puntos en los cuales las piezas polinomiales se unen,ν1 < ν2 < . . .< νp, se llaman los puntos de quiebre del spline.É Por convención, el primer y último punto de quiebre son los
extremos del intervalo de aproximación [a,b].É Un spline de orden general k con p puntos de quiebre puede
caracterizarse por (p − 1)(k + 1) parámetros, dado que cadauno de los p − 1 segmentos polinomiales está definido por susk + 1 coeficientes.É No obstante, por definición un spline debe ser continuo y
tener derivadas continuas hasta el orden k − 1 en cada uno delos p − 2 puntos de quiebre interiores, lo que impone k(p − 2)condiciones.É Por tanto, un spline de orden k con p puntos de quiebre está
en realidad caracterizados porn = (k + 1)(p − 1)− k(p − 2) = p + k − 1 parámetros libres.É No debe sorprenden que entonces un spline general de orden
k con p puntos de quiebre puede escribirse como unacombinación lineal de n = p + k − 1 funciones base.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 33
É En la práctica se utilizan dos clases de splines con frecuencia.É Un spline de primer orden o spline lineal es una serie de
segmentos de línea unidos para formar una función continua.É Un spline de tercer orden o spline cúbico es una serie de
segmentos de polinomios cúbicos unidos para formar unafunción continuamente diferenciable dos veces.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 34
Splines lineales
É Los splines lineales usan segmentos de línea para conectarpuntos en el gráfico de la función que se está aproximando.É En la práctica, son particularmente fáciles de construir y de
trabajar, lo que explica su amplia popularidad.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 35
Figura 7.9: Interpolación spline lineal
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 36
Un spline lineal con n+ 1 nodos de interpolación equi-espaciadosx0,x1, . . . ,xn en el intervalo [a,b] puede escribirse como lacombinación lineal de las n+ 1 funciones base
ϕj(x) =
1− |x−xj |h |x − xj | ≤ h
0 otherwise.
donde h = b−an es la distancia entre los nodos.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 37
0.0
1.0Spline 0 Spline 1 Spline 2 Spline 3
0.0
1.0Spline 4 Spline 5 Spline 6 Spline 7
-1 10.0
1.0Spline 8
-1 1
Spline 9
-1 1
Spline 10
-1 1
Spline 11
Linear Spline Basis Functions on [-1,1]
Figura 7.10: Linear Spline Basis Functions on [0,1]
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 38
Algunas propiedades de los splines lineales
É En ocasiones a las funciones base el spline lineal se les llamanfunciones “sombrero”.É Cada función bases es cero en todas partes, excepto en un
angosto soporte de ancho 2h.É En cualquier punto del soporte, a los sumo dos funciones base
difieren de cero.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 39
É Calcular los coeficientes base para una aproximación de splinelineal es un asunto trivial.É Por construcción, ϕi(xj) es igual a uno si i = j , pero cero de lo
contario; es decir, la matriz de interpolación Φ es la matrizidentidad.É Por ello, los coeficientes base son simplemente iguales a la
función evaluada en los nodos de interpolación, ci = f (xi), yla aproximación de spline lineal de f tiene la forma
f (x) =n∑
j=0f (xj)ϕj(x).
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 40
É Evaluar un spline lineal y su derivada en un punto arbitrario xes muy fácil.É Como a lo sumo dos funciones base son distintas de cero en
cualquier punto, solo se requiere evaluar dos funciones base.É Específicamente, si x está entre xi−1 and xi , entonces
f (x) =(x − xi−1)ci +(xi − x)ci−1
hy
f ′(x) = ci − ci−1h
.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 41
No obstante, por sus limitaciones el spline lineal es una pobreescogencia para la mayoría de las aplicaciones de economíacomputacional:É Su primera derivada es discontinua, y sus derivadas de orden
superior son cero en casi todas partes.É Por lo tanto son muy deficiente para aproximar primeras
derivadas no pueden aproximar derivadas de orden superior.É Pero en muchas aplicaciones económicas, las derivadas son de
interés fundamental para el economista.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 42
Splines cúbicos
É Un spline cúbico es una serie de segmentos polinomialescúbicos unidos para formar una función dos vecescontinuamente diferenciable .É Los splines cúbicos mantienen la simplicidad de los splines
lineales, pero tienen primera y segunda derivadas.É Por ello, cuando se requiere una aproximación suave,
preferimos los splines cúbicos a los lineales.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 43
0.0
1.0Spline 0 Spline 1 Spline 2 Spline 3
0.0
1.0Spline 4 Spline 5 Spline 6 Spline 7
-1 10.0
1.0Spline 8
-1 1
Spline 9
-1 1
Spline 10
-1 1
Spline 11
Cubic Spline Basis Functions on [-1,1]
Figura 7.11: Splines cúbicos en [0,1]
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 44
Algunas propiedades de los splines cúbicos
É Cada función base es cero en todas partes, excepto en unsoporte angosto.É Cada función base y sus derivadas son cero en los extremos de
su soporte.É En cualquier punto del soporte, a lo sumo cuatro funciones
base difieren de cero.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 45
É Calcular los coeficientes base para una aproximación desplines cúbicos también es relativamente fácil.É Por construcción, en cada nodo de interpolación a lo sumo
cuatro funciones base son distintas de cero.É Por ello, la matriz de interpolación consistirá
mayoritariamente de ceros, con elementos distintos de ceroconcentrados alrededor de la diagonal.É Como tal, la matriz de interpolación puede almacenarse en
formato “disperso”, reduciendo el espacio requerido y elnúmero de operaciones necesarias para resolver la ecuaciónde interpolación.É Además, la matriz es bien condicionada.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 46
4. Consideraciones adicionales
Interpolación multidimensional
É Los métodos univariados de interpolación pueden extendersea más dimensiones aplicando principios de productostensoriales.É Consideremos el problema de interpolar una función real
bivariada f en el intervalo
I = {(x ,y) | ax ≤ x ≤ bx ,ay ≤ y ≤ by}.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 47
É Sean ϕx1 ,ϕx
2 , . . . ,ϕxnx
y x1,x2, . . . ,xnx nx funciones baseunivariadas y nx nodos de interpolación para el intervalo[ax ,bx ].É Sean ϕy
1 ,ϕy2 , . . . ,ϕy
nyy y1,y2, . . . ,yny ny funciones base
univariadas y ny nodos de interpolación para el intervalo[ay ,by ].
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 48
É Entonces podemos construir una base bivariada de n = nxnyfunciones definidas en I tomando el producto tensorial de lasfunciones base univariadas:
ϕij(x ,y) = ϕxi (x)ϕ
yj (y)
para i = 1,2, . . . ,nx y j = 1,2, . . . ,ny .É De manera similar, podemos construir una cuadrícula de
n = nxny nodos de interpolación para I formando el productocartesiano de los nodos de interpolación univariados:
{ (xi ,yj) | i = 1,2, . . . ,nx ; j = 1,2, . . . ,ny}.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 49
En general, los esquemas de interpolación multivariada basada enproducto tensorial heredan las cualidades favorables de sus padresunivariados:É La interpolación multivariada con splines produce matrices de
interpolación dispersas.É La interpolación multivariada con polinomios de Chebyshev
produce matrices de interpolación ortogonales y biencondicionadas.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 50
É Sin embargo, los esquemas de interpolación multidimensionalbasados en productos tensoriales sufren de la maldición de ladimensionalidad.É Específicamente, el número de funciones base y de nodos de
interpolación crece exponencialmente con la dimensión deldominio de la función.É Por ejemplo, si escogemos n funciones base y nodos de
interpolación en cada una de las d dimensiones, la base deproducto tensorial contendría nd funciones y la cuadrícula deinterpolación (producto cartesiano) contendría nd nodos deinterpolación.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 51
É Para trabajar directamente con bases de producto tensorial serequiere conocimientos de álgebra de tensores.É No obstante, no necesitamos dominar el álgebra de tensores.É Todas las operaciones de producto tensoriales requeridos para
resolver problemas de economía computacional sonmanejadas eficientemente por el paquete CompEcon.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 52
Escogiendo un método de aproximación
É La interpolación con polinomios de Chebyshev tiende asuperar a la interpolación spline cuando se está aproximandouna función muy suave.É No obstante, si la función tiene discontinuidades en su primer
o segunda derivadas, las funciones spline a veces sedesempeñan bien o mejor.É Además, si la dimensión del problema es alta, la interpolación
spline tiene una ventaja porque su matriz de interpolación esdispersa.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 53
Función Nodos Splinelineal
Splinecúbico
Polinomio deChebyshev
e−x 10 -1.82 -4.42 -9.2220 -2.45 -5.86 -15.0030 -2.81 -6.64 -15.00
|x |0.5 10 -0.48 -0.48 -0.4720 -0.64 -0.67 -0.6230 -0.73 -0.77 -0.71
Log10 de los errores de aproximación para funciones suave y conpicos en [−1,1], para distintos esquemas de interpolación
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 54
5. Paquete CompEcon
La clase Basis
En CompEcon hay tres clases para representar bases deinterpolación:
BasisChebyshev - define una base de ChebyshevBasisSpline - define una base splineBasisLinear - define una base lineal
Para trabajar con estas bases, seguimos estos pasos:
1. definimos un objeto base
2. ajustamos la base a la función
3. evaluamos la base en los puntos de interpolación
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 55
Definiendo un objeto base
Paso 1:
basis = BASIS(n,a,b,order)
BASIS - clase de base (’BasisChebyshev’ o ’BasisSpline’)n - número de funciones base y de nodosa - extremo izquierdo del intervalo de interpolaciónb - extremo derecho del intervalo de interpolaciónorder - orden opcional del spline (predeterminado: 3
para cúbico)
basis - una instancia de la clase BASIS.nodes - nodos de interpolación.Phi() - matriz de interpolación.c - coeficientes de la base
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 56
Ajustando una función
Paso 2:Ya sea
basis.y = y_at_nodeso bien
basis.c = new_coef
basis - una instancia de la clase BASISy_at_nodes - valores conocidos de la función en los nodos
new_coef - nuevos coeficientes de interpolación
basis el objecto es actualizado en sitio
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 57
Evaluando la función de interpolación
Paso 3:
y = basis(x, d)
basis - una instancia de la clase BASISx - punto(s) de evaluaciónd - orden de diferenciación
y - valor o derivada aproximada
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 58
Evaluando funciones base
Aunque rara vez es necesario cuando se trabaja con estas clases,también podemos calcular las funciones base en puntos deinterpolación arbitrarios.
phi = basis.Phi(x, d)
basis - una instancia de la clase BASISx - punto(s) de evaluaciónd - orden de diferenciación
phi - funciones o derivadas base evaluadas en x
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 59
Ejemplo 1:Aproximación univariada
Construyamos una aproximación de f (x) = exp(−x) en elintervalo [−1,1] y evaluamos qué tan bien se ajusta a la función y asu primer derivada.Paso 1: Creamos funciones para f y sus derivadas:
def f(x): return np.exp(-x)def d1(x): return -np.exp(-x)def d2(x): return np.exp(-x)
Paso 2: Creamos una base de polinomios de Chebyshev yajustamos la función f:
n, a, b = 10, -1, 1F = BasisChebyshev(n, a, b, f=f)
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 60
Paso 3: Usamos F para evaluar la interpolación de polinomios deChebyshev y sus derivadas:
x = np.linspace(a, b, 501)ffit = F(x)dfit1 = F(x, 1)dfit2 = F(x, 2)
Paso 4: Graficamos los residuos de aproximación en unacuadrícula refinada:
plt.plot(x, ffit-f(x))plt.plot(x, dfit1-d1(x))plt.plot(x, dfit2-d2(x))
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 61
1.00 0.75 0.50 0.25 0.00 0.25 0.50 0.75 1.00x
6
4
2
0
2
4
6Er
ror
1e 10 Chebychev Approximation Error - Function
Figura 7.12: Error de aproximación de Chebyshev con 10 nodos para e−x
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 62
1.00 0.75 0.50 0.25 0.00 0.25 0.50 0.75 1.00x
4
2
0
2
4
6Er
ror
1e 8 Chebychev Approximation Error - First Derivative
Figura 7.13: Error de aproximación de Chebyshev para la primera derivada de e−x
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 63
1.00 0.75 0.50 0.25 0.00 0.25 0.50 0.75 1.00x
2.0
1.5
1.0
0.5
0.0
Erro
r1e 6 Chebychev Approximation Error - Second Derivative
Figura 7.14: Error de aproximación de Chebyshev para la segunda derivada de e−x
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 64
Ejemplo 2:Aproximación bivariada
Construyamos una interpolación con polinomios de Chebyshevpara la función bivariadaPaso 1: Creamos funciones para f y sus derivadas hasta de
orden 2:
exp, cos, sin = np.exp, np.cos, np.sin
f = lambda x: cos(x[0]) / exp(x[1])d1 = lambda x: -sin(x[0]) / exp(x[1])d2 = lambda x: -cos(x[0]) / exp(x[1])d11 = lambda x: -cos(x[0]) / exp(x[1])d12 = lambda x: sin(x[0]) / exp(x[1])d22 = lambda x: cos(x[0]) / exp(x[1])
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 65
Paso 2: Creamos una base de polinomios de Chebyshev yajustamos la función f:
n, a, b = 6, 0, 1F = BasisChebyshev([n, n], a, b, f=f)
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 66
Paso 3: Para calcular las derivadas parciales ∂ f∂ x1
y ∂ f∂ x2
de lainterpolación en x = (0.5,0.5) , ejecutamos
x = np.array([[0.5],[0.5]])dfit1 = F(x, [1, 0])dfit2 = F(x, [0, 1])
Para calcular las derivadas parciales ∂2f∂ x2
1, ∂ 2f∂ x1∂ x2
, y ∂2f∂ x2
2de la
interpolación, ejecutamos
dfit11 = F(x, [2, 0])dfit22 = F(x, [0, 2])dfit12 = F(x, [1, 1])
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 67
Paso 4: Para graficar el residuo de la aproximación, ejecutamos:
nplot = [101, 101]X = nodeunif(nplot, [a, a], [b, b])error = (F(x) - f(x)).reshape(nplot)X1, X2 = XX1.shape = nplotX2.shape = nplot
plt.figure()ax = fig1.add_subplot(1, 1, 1, projection='3d')ax.plot_surface(X1, X2, error, rstride=1, cstride=1,
cmap=cm.coolwarm, linewidth=0, antialiased=False)
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 68
x1
0.00.2
0.40.6
0.81.0
x2
0.00.2
0.40.6
0.81.0
erro
r1e
6
1.00
0.75
0.50
0.25
0.00
0.25
0.50
0.75
1.00
Chebychev Approximation Error
Figura 7.15: Error de aproximación de polinomios Chebyshev (6 por 6) para cos(x1)exp(x2)
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 69
6. Ecuaciones funcionales
Las ecuaciones funcionales son muy utilizadas para analizaseconomías dinámicas, por ejemploÉ ecuaciones de BellmanÉ ecuaciones de EulerÉ equilibrios de expectativas racionalesÉ ecuaciones diferenciales ordinariasÉ ecuaciones diferenciales parciales
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 70
É Formalmente, una ecuación funcional tiene la forma
F (f ,x) = 0 para todo x ∈ S,
donde f es una función real desconocida definida en elconjunto S ⊂ℜd y F es un mapeo real con dos argumentos,una función real f definida en S y un elemente x de S.É Para una función f : S 7→ ℜ dada, el mapeo real x 7→ F (f ,x)
en S se conoce como el residuo de f .É Una solución de la ecuación funcional es una función f cuyo
residuo es cero para todo x ∈ S.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 71
É Como un ejemplo, consideremos una simple ecuación deBellman
V (x) = maxy∈S {u(x ,y)+δV (y)} for all x ∈ S
donde u es una función real conocida, 0< δ < 1, y S es unintervalo acotado en ℜ.É La ecuación de Bellman es una ecuación funcional cuya
incógnita es la “función valor” V , una función real definida enS.É La ecuación de Bellman puede escribirse en la forma canónica
F (V ,x) = 0 para todo x ∈ S
siempre y cuando definamos
F (V ,x)≡ V (x)−maxy∈S {u(x ,y)+δV (y)}
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 72
É Una ecuación funcional es fundamentalmente difícil deresolver porque la incógnita es toda una función f que debesatisfacer un número infinto de condiciones, una para cadapunto x de S.É Aunque algunas ecuaciones funcionales encontradas en
economía tienen solución de forma cerrada, la vasta mayoríano la tiene.É Sin embargo, numéricamente podemos calcular soluciones
aproximadas con precisión, usando extensiones naturales delos métodos de interpolación.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 73
Método de colocación
É Calcularemos soluciones aproximadas a ecuacionesfuncionales numéricamente, usando el método de colocación.É El método de colocación requiere que la función de solución f
se aproxime utilizando una combinación lineal de n funcionesbase conocidas ϕ1,ϕ2, . . . ,ϕn definidas en S:
f (x)≈n∑
j=1cjϕj(x).
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 74
É Los coeficientes base c1, c2, . . . , cn se fijan requiriendo que elresiduo de aproximación sea cero, no en todos los x en S, sinomás bien en n nodos de colocación apropiadamente escogidosx1,x2, . . . ,xn in S:
F
n∑
j=1cjϕj , xi
!= 0, i = 1,2, . . . ,n.
É Esta ecuación es llamada la ecuación de colocación.É La incógnita de la ecuación de colocación no es la función f
deseada, sino los coeficientes base c1, c2, . . . , cn de suaproximante.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 75
É El método de colocación reemplaza un problema de resolveruna ecuación funcional de dimensión infinita yfundamentalmente difícil con un problema de búsqueda deraíces de dimensión finita, que puede resolverse usando losmétodos usuales de ecuaciones no lineales.É Utilizaremos colocación para resolver los modelos económicos
dinámicos que encontramos más adelante en el curso.É Introduciremos el método de colocación aplicándolo primero
a algunos ejemplos relativamente fáciles.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 76
Ejemplo 3:Función implícita
É Dada una función g :ℜ2 7→ ℜg(x ,y) = y−2 + y−5 − 2x
encontremos una función f :ℜ 7→ ℜ tal que:
g(x , f (x)) = 0, x ∈ [1,5].
É El teorema de la función implícita garantiza que tal funciónexiste, es única, y es continuamente diferenciable.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 77
É Para resolver numéricamente la ecuación funcional usandocolocación, aproximamos la función incógnita usando unacombinación lineal de n funciones base ϕ1,ϕ2, . . . ,ϕnconocidas:
f (x)≈n∑
j=1cjϕj(x).
É Luego fijamos los coeficientes base c1, c2, . . . , cn requiriendoque el aproximante satisfaga la ecuación funcional en n nodosde colocación x1,x2, . . . ,xn apropiadamente escogidos:
g(xi ,n∑
j=1cjϕj(xi)) = 0, i = 1,2, . . . ,n.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 78
É Es decir, resolvemos las n ecuaciones no lineales de colocación n∑
j=1cjϕj(xi)
!−2
+
n∑
j=1cjϕj(xi)
!−5
−2xi = 0, i = 1,2, . . . ,n
para los n coeficientes de base desconocidos c1, c2, . . . , cn.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 79
Para resolver la ecuación de colocación en Python:
Paso 1: Creamos una BasisChebyshev para representar f ,yobtenemos sus nodos
n, a, b = 31, 1, 5F = BasisChebyshev(n, a, b)x = F.nodes
donde donde usamos un esquema de interpolación de 31 nodos ypolinomios de Chebyshev.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 80
Paso 2: Definimos una función resid que calcula el residuo deaproximación en los nodos base x, para un vector de coeficientesbase arbitrario c:
def resid(c):F.c = c # actualizar coeficientes basef = F(x) # interpolar en los nodos base xreturn f ** -2 + f ** -5 - 2 * x
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 81
Paso 3: Resolvemos la ecuación de colocación para loscoeficientes base:
c0 = np.zeros(n) # valor inicial para coeficientesc0[0] = 0.2F.c = NLP(resid).broyden(c0)
Aquí hemos usado broyden para encontrar el vector de coeficientesc que hace que los residuos sean cero en los nodos de colocación.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 82
Paso 4: Graficamos la aproximación en una cuadrícula refinada:
x = np.linspace(a, b, 1000)plt.plot(x, F(x))
1.0 1.5 2.0 2.5 3.0 3.5 4.0 4.5 5.0x
0.65
0.70
0.75
0.80
0.85
0.90
0.95
1.00
f(x)
Implicit Function
Figura 7.16: Función implícita©Randall Romero Aguilar, PhD SP-6534 / 2020.I 83
Paso 5: Graficamos el residuo en una cuadrícula refinada denodos para evaluar la calidad de la aproximación:
plt.plot(x, resid(F.c))
1.0 1.5 2.0 2.5 3.0 3.5 4.0 4.5 5.0x
0.8
0.6
0.4
0.2
0.0
0.2
0.4
0.6
0.8
Res
idua
l
1e 8 Functional Equation Residual
Figura 7.17: Residuos de la ecuación funcional©Randall Romero Aguilar, PhD SP-6534 / 2020.I 84
Ejemplo 4:Oferta monopolística
É Un monopolista que enfrenta una curva de demanda q = d(p)fija la producción q para maximizar sus ganancias, de maneraque
dπdq
= p + q dpdq− k(q) = 0
donde p is precio, dpdq es el efecto marginal del producto
monopolista sobre el precio, y k(q) es el costo marginal.É La curva de oferta efectiva del monopolista q = s(p), la cual
da la cantidad q que está dispuesto a producir a un preciodado p, está caracterizado por la ecuación funcional
p +s(p)d ′(p) − k[s(p)] = 0, p > 0.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 85
É Para resolver la ecuación funcional numéricamente usadocolocación, aproximamos la curva de oferta efectivadesconocida usando una combinación lineal de n funcionesbase conocidas ϕ1,ϕ2, . . . ,ϕn:
s(p)≈n∑
j=1cjϕj(p).
É Luego fijamos los coeficientes base c1, c2, . . . , cn requiriendoque el aproximante satisfaga la condición de optimalidad deprimer orden en n nodos de colocación apropiadamenteescogidos p1,p2, . . . ,pn:
pi +n∑
j=1cjϕj(pi)
d ′(pi)− k
n∑
j=1cjϕj(pi)
!= 0, i = 1,2, . . . ,n.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 86
É Derivemos la curva de oferta efectiva del monopolista parap ∈ [0.5,2.5] cuando
d(p) = p−3.5
yk(q) =pq + q2.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 87
Para resolver la ecuación de colocación en Python:Paso 1: Creamos una BasisChebyshev para representar la
cantidad q, y obtenemos sus nodos p (precios):
n, a, b = 21, 0.5, 2.5Q = BasisChebyshev(n, a, b)p = Q.nodes
donde usamos un esquema de interpolación de 21 nodos ypolinomios de Chebyshev.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 88
Paso 2: Definimos una función resid que calcula el residuo dela aproximación en los nodos base p, para un vector arbitrario decoeficientes base c:
def resid(c):Q.c = cq = Q(p)return p + q/(-3.5*p**(-4.5)) - np.sqrt(q) - q**2
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 89
Paso 3: Resolvemos la ecuación de colocación para loscoeficientes base:
c0 = np.zeros(n) # valor inicial para coefsc0[0] = 2monopoly = NLP(resid)Q.c = monopoly.broyden(c0)
Aquí usamos broyden para encontrar el vector de coeficientes cque hace que los residuos sean cero en los nodos de colocación.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 90
Paso 4: Graficamos el aproximante en una cuadrícula refinada:
p = np.linspace(a, b, 1000)plt.plot(Q(p), p)
0.15 0.20 0.25 0.30 0.35 0.40 0.45Quantity
0.50
0.75
1.00
1.25
1.50
1.75
2.00
2.25
2.50
Pric
e
Monopolist's Effective Supply Curve
Figura 7.18: Monopolist’s Effective Supply Curve©Randall Romero Aguilar, PhD SP-6534 / 2020.I 91
Paso 5: Graficamos el residuo en una cuadrícula refinada denodos para evaluar la calidad de la aproximación:
plt.plot(p, resid(Q.c))
0.50 0.75 1.00 1.25 1.50 1.75 2.00 2.25 2.50Price
3
2
1
0
1
2
3
Res
idua
l
1e 7 Functional Equation Residual
Figura 7.19: Functional Equation Residual
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 92
Ejemplo 5:Equilibrio de Cournot
É Consideremos un mercado oligopolístico de m empresasidénticas que enfrentan una curva de demanda comúnq = d(p).É Bajo el supuesto de equilibrio de Cournot, cada empresa i
toma como fija la producción de sus competidores cuandodecide su propia producción.É Es decir, la empresa i asume que el impacto marginal de su
decisión de producir qi sobre el precio de mercado p estádado por
dpdqi
=1
d ′(p) .
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 93
É Bajo el supuesto de equilibrio de Cournot, la condición demaximización de ganancias para la empresa i es
dπdqi
= p +qi
d ′(p) − k(qi) = 0,
donde k(·) es la función de costo marginal de la empresarepresentativa.É La curva de oferta efectiva de la empresa representativa
q = f (p), la cual da la cantidad q que está dispuesta aproducir a un precio dado p, están caracterizada por laecuación funcional
p +f (p)d ′(p) − k[f (p)] = 0, p > 0.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 94
É Para resolver la ecuación funcional numéricamente porcolocación, aproximamos la curva de oferta efectiva de laempresa representativa usando una combinación lineal de nfunciones base conocidas ϕ1,ϕ2, . . . ,ϕn:
f (p)≈n∑
j=1cjϕj(p).
É Luego fijamos los coeficientes base c1, c2, . . . , cn requiriendoque
pi +n∑
j=1cjϕj(pi)
d ′(pi)− k
n∑
j=1cjϕj(pi)
!= 0
en n nodos de colocación (precios) apropiadamente escogidosp1,p2, . . . ,pn.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 95
É Derivemos la curva de oferta efectiva de la empresarepresentativa para p ∈ [1,2] si
d(p) = p−η
yk(q) = αpq + q2,
donde α= 1 y η= 3.5.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 96
Para resolver la ecuación de colocación en Python:Paso 1: Creamos una BasisChebyshev para representar la
cantidad ofrecida s, y obtenemos sus nodos p (prices):
n, a, b = 25, 0.5, 2.0S = BasisChebyshev(n,a,b,
labels=['price'],y=np.ones(n))p = S.nodes
donde usamos un esquema de interpolación de 25 nodos ypolinomios de Chebyshev.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 97
Paso 2: Definimos una función resid que calcula el residuo dela aproximación en los nodos base p, para un vector arbitrario decoeficientes base c:
alpha, eta = 1.0, 3.5
def resid(c):S.c = c # actualizar coeficientes de interpolaciónq = S(p) # calcular cantidad ofrecida en precios nodoreturn p - q*(p**(eta+1)/eta) - alpha*np.sqrt(q) - q**2
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 98
Paso 3: Resolvemos la ecuación de colocación para loscoeficientes base:
cournot = NLP(resid)S.c = cournot.broyden(S.c, tol=1e-12)
Aquí usamos broyden para encontrar un vector c que haga losresiduos igual a cero en los nodos de colocación.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 99
Paso 4: Graficamos la demanda y la oferta de 5 empresas, enuna cuadrícula refinada:
D = lambda p: p**(-eta) # función de demandaprices = np.linspace(a, b, 501)plt.plot(5*S(prices),prices, D(prices),prices)
0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0Quantity
0.6
0.8
1.0
1.2
1.4
1.6
1.8
2.0
Pric
e
Cournot Effective Firm Supply Function
SupplyDemand
Figura 7.20: Demanda de mercado y oferta efectiva con 5 empresas idénticas
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 100
Paso 5: Graficamos el residuo en una cuadrícula refinada denodos para evaluar la calidad de la aproximación:
plt.plot(prices, resid(S.c))
0.6 0.8 1.0 1.2 1.4 1.6 1.8 2.0Quantity
4
2
0
2
4
Res
idua
l
1e 11 Residual Function for Cournot Problem
Figura 7.21: Residuo de la maximización de ganancias de la empresa representativa
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 101
0 2 4 6 8 10 12Quantity
0.6
0.8
1.0
1.2
1.4
1.6
1.8
2.0
Pric
e
m=1m=3
m=5m=10
m=15m=20
demand
Industry Supply and Demand Functions
Figura 7.22: Demanda de mercadoy oferta efectiva con número variante de empresasidénticas
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 102
0 5 10 15 20 25Number of Firms
0.6
0.7
0.8
0.9
1.0
1.1
1.2Pr
ice
Cournot Equilibrium Price as Function of Industry Size
Figura 7.23: Precio de equilibrio en función del número de empresas
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 103
References I
Miranda, Mario J. y Paul L. Fackler (2002). Applied ComputationalEconomics and Finance. MIT Press. isbn: 0-262-13420-9.
Romero-Aguilar, Randall (2016). CompEcon-Python. url:http://randall-romero.com/code/compecon/.
©Randall Romero Aguilar, PhD SP-6534 / 2020.I 104
Recommended