You are currently browsing the monthly archive for noviembre 2013.

El blog, que empezó para servir de mero canal de comunicación asíncrono entre dos o tres personas, acaba de superar las mil visitas mensuales. Aunque no conozco a casi ninguno de mis lectores,

¡GRACIAS A TODOS! 🙂

blogStats   blogMap

Anuncios

psiAlpha

phiAlpha1

psiAlpha2

psiAlpha3

Seguimos con el post anterior. Vamos a utilizar ahora siete puntos separados de la siguiente manera:

x_0

x_1:=x_0+n^2 h

x_2:=x_0 + (n^2+n) h

x_3:=x_0 + (n^2+n+1) h

x_4:=x_0 + (n^2+n+2) h

x_5:=x_0 + (n^2+2n+2) h

x_6:=x_0 + (2n^2+2n+2) h

El caso mas sencillo es cuando tenemos cinco puntos:

(x_0,y_0), (x_1,y_1), (x_2,y_2), (x_3,y_3), (x_4,y_4),

de manera que:

x_1-x_0 = 2(x_2-x_1) = 2(x_3-x_2) = x_4-x_3.

Tal y como escribimos en el anterior post, el polinomio general para cinco puntos quedaria:

L(x) = y_0 l_0(x) + y_1 l_1(x) + y_2 l_2(x) + y_3 l_3(x) + y_4 l_4(x),

donde:

l_0(x) = \frac{x-x_1}{x_0-x_1} \frac{x-x_2}{x_0-x_2} \frac{x-x_3}{x_0-x_3} \frac{x-x_4}{x_0-x_4},

l_1(x) = \frac{x-x_0}{x_1-x_0} \frac{x-x_2}{x_1-x_2} \frac{x-x_3}{x_1-x_3} \frac{x-x_4}{x_1-x_4},

l_2(x) = \frac{x-x_0}{x_2-x_0} \frac{x-x_1}{x_2-x_1} \frac{x-x_3}{x_2-x_3} \frac{x-x_4}{x_2-x_4},

l_3(x) = \frac{x-x_0}{x_3-x_0} \frac{x-x_1}{x_3-x_1} \frac{x-x_2}{x_3-x_2} \frac{x-x_4}{x_3-x_4},

l_4(x) = \frac{x-x_0}{x_4-x_0} \frac{x-x_1}{x_4-x_1} \frac{x-x_2}{x_4-x_2} \frac{x-x_3}{x_4-x_3}.

Dado que tratamos de aproximar la segunda derivada, tenemos, en el caso de equidistancia quedaría:

\frac{d^2}{dx^2}u_i = \frac{-u_{i-2}+16u_{i-1}-30u_i+16u_{i+1}-u_{i+2}}{12 h^2}.

Vamos a ver que queda ahora en nuestro caso. Reescribimos los l_i(x) en función de x_0 de manera que, por ejemplo, tenemos:

l_0(x) = \frac{x-x_1}{x_0-x_1} \frac{x-x_2}{x_0-x_2} \frac{x-x_3}{x_0-x_3} \frac{x-x_4}{x_0-x_4} =

=\frac{x-x_0-2h}{x_0-x_0-2h} \frac{x-x_0-3h}{x_0-x_0-3h} \frac{x-x_0-4h}{x_0-x_0-4h} \frac{x-x_0-6h}{x_0-x_0-6h} =

=\frac{(x-x_0-2h)(x-x_0-3h)(x-x_0-4h)(x-x_0-6h)}{144h^4},

que para x=x_2=x_0+3h (2h+h), la segunda derivada queda:

\frac{d^2}{dx^2} l_0(x) |_{x=x_2} = -\frac{1}{72h^2}.

Haciendo lo mismo para todas las derivadas segundas de todos los l_i(x), obtenemos la siguiente formula en diferencias finitas:

\frac{d^2}{dx^2}u_i = \frac{-u_{i-3} + 81 u_{u-1} - 160 u_i + 81 u_{i+1} - u_{i+3}}{72h^2},

donde los índices hacen referencia a una malla inicial equiespaciada.

Para el mismo denominador, antes teniamos:

\frac{d^2}{dx^2}u_i = \frac{-6u_{i-2}+96u_{i-1}-180u_i+96u_{i+1}-6u_{i+2}}{72 h^2}.

Podemos hacer lo mismo para cada uno de los puntos x=x_0, x=x_1=x_0+2h, x=x_3=x_0+4h y x=x_4=x_0+6h:

\frac{d^2}{dx^2}u_{i-3} = \frac{40 u_{i-3} -243 u_{i-1} + 352 u_i -162 u_{i+1} + 13 u_{i+3}}{36 h^2}

\frac{d^2}{dx^2}u_{i-2} = \frac{7 u_{i-3} - 32 u_i + 27 u_{i+1} - 2 u_{i+3}}{36 h^2}

\frac{d^2}{dx^2}u_{i+1} =\frac{-2 u_{i-3} + 27 u_{i-1} - 32 u_i -+7 u_{i+3}}{36 h^2}

\frac{d^2}{dx^2}u_{i+3} =\frac{13 u_{i-3} -162 u_{i-1} + 352 u_i -243 u_{i+1} + 40 u_{i+3}}{36 h^2}

 En el caso de x=x_0+4h (3h+h), tenemos:

\frac{d^2}{dx^2}u_i = \frac{-u_{i-4} + 256_{u-1} - 510 u_i + 256 u_{i+1} - u_{i+4}}{140h^2}.

Dados n+1 puntos:

(x_0,y_0), \ldots, (x_n,y_n),

definimos el polinomio interpolador de Lagrange:

L(x) := \Sigma_{i=0}^n y_i l_i(x)

donde:

l_i(x) := \Pi_{0 \leq j \leq n,j \neq i} \frac{x-x_j}{x_i-x_j}.

Con esto, tenemos:

\frac{d^n}{dx^n}L(x) = \Sigma_{i=0}^n y_i \frac{d^n}{dx^n}l_i(x)

Supongamos que tenemos n=2:

(x_0,y_0), (x_1,y_1).

En este caso, tenemos:

L(x) = y_0 l_0(x) + y_1 l_1(x)

con:

l_0(x) = \frac{x-x_1}{x_0-x_1}

l_1(x) = \frac{x-x_0}{x_1-x_0}

Como tenemos dos puntos, únicamente podemos aproximar la primera derivada:

\frac{d}{dx} L(x) = y_0 \frac{d}{dx} l_0(x) + y_1 \frac{d}{dx} l_1(x)

con:

\frac{d}{dx} l_0(x) = \frac{1}{x_0-x_1}

\frac{d}{dx} l_1(x) = \frac{1}{x_1-x_0},

de manera que:

\frac{d}{dx}L(x) = \frac{y_1 - y_0}{x_1 - x_0}.

Con esto, tenemos las aproximaciones de primer orden:

u_x(x_0) = u_x(x_1) = \frac{y_1 - y_0}{x_1-x_0},

que, en índices, queda:

\frac{d}{dx}u_i \approx \frac{u_{i+1}-u_i}{h_x},

\frac{d}{dx}u_{i+1} \approx \frac{u_{i+1}-u_i}{h_x},

donde h_x = x_1 - x_0 (y que es lógico, ya que la derivada será una constante).

Supongamos ahora que tenemos tres puntos:

(x_0,y_0),(x_1,y_1),(x_2,y_2).

En este caso tenemos:

L(x) = y_0 l_0(x) + y_1 l_1(x) + y_2 l_2(x),

\frac{d}{dx} L(x) = y_0 \frac{d}{dx} l_0(x) + y_1 \frac{d}{dx} l_1(x) + y_2 \frac{d}{dx} l_2(x),

\frac{d^2}{dx^2} L(x) = y_0 \frac{d^2}{dx^2} l_0(x) + y_1 \frac{d^2}{dx^2} l_1(x) + y_2 \frac{d^2}{dx^2} l_2(x).

Ahora tenemos:

l_0(x) = \frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)} = \frac{x^2 + (-x_1-x_2)x + x_1x_2}{(x_0-x_1)(x_0-x_2)},

l_1(x) = \frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)} = \frac{x^2 + (-x_0-x_2)x + x_0x_2}{(x_1-x_0)(x_1-x_2)},

l_2(x) = \frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)} = \frac{x^2 + (-x_0-x_1)x + x_0x_1}{(x_2-x_0)(x_2-x_1)}.

\frac{d}{dx} l_0(x) = \frac{2x + (-x_1-x_2)}{(x_0-x_1)(x_0-x_2)},

\frac{d}{dx} l_1(x) = \frac{2x+(-x_0-x_2)}{(x_1-x_0)(x_1-x_2)},

\frac{d}{dx} l_2(x) = \frac{2x+(-x_0-x_1)}{(x_2-x_0)(x_2-x_1)}.

\frac{d^2}{dx^2} l_0(x) = \frac{2}{(x_0-x_1)(x_0-x_2)},

\frac{d^2}{dx^2} l_1(x) = \frac{2}{(x_1-x_0)(x_1-x_2)},

\frac{d^2}{dx^2} l_2(x) = \frac{2}{(x_2-x_0)(x_2-x_1)}.

De esta manera, por ejemplo, tenemos que:

\frac{d^2}{dx^2}L(x) = y_0 \frac{2}{(x_0-x_1)(x_0-x_2)} + y_1 \frac{2}{(x_1-x_0)(x_1-x_2)} + y_2 \frac{2}{(x_2-x_0)(x_2-x_1)},

que, en el caso de tener los puntos equiespaciados (h_x:=x_{i+1}-x_{i} con 0 \leq i \leq 1), queda la aproximación de segundo orden:

\frac{d^2}{dx^2}u(x) = \frac{y_0 - 2 y_1 + y_2}{h_x^2},

que además, como era de esperar, es independiente de x:

\frac{d^2}{dx^2}u_{i-1} \approx \frac{u_{i-1}-2u_i+u_{i+1}}{h_x^2},

\frac{d^2}{dx^2}u_i \approx \frac{u_{i-1}-2u_i+u_{i+1}}{h_x^2},

\frac{d^2}{dx^2}u_{i+1} \approx \frac{u_{i-1}-2u_i+u_{i+1}}{h_x^2}.

¿Qué pasa con la primera derivada? En este caso, el resultado si que depende de x (por lo que tendremos un resultado diferente en función de si la x vale x_0, x_1 o x_2) y lo que obtenemos es:

\frac{d}{dx} L(x) = y_0 \frac{2x + (-x_1-x_2)}{(x_0-x_1)(x_0-x_2)} + y_1 \frac{2x + (-x_0-x_2)}{(x_1-x_0)(x_1-x_2)} + y_2 \frac{2x + (-x_1-x_2)}{(x_2-x_0)(x_2-x_1)},

por lo que:

\frac{d}{dx} L(x_0) = y_0 \frac{2x_0 + (-x_1-x_2)}{(x_0-x_1)(x_0-x_2)} + y_1 \frac{2x_0 + (-x_0-x_2)}{(x_1-x_0)(x_1-x_2)} + y_2 \frac{2x_0 + (-x_1-x_2)}{(x_2-x_0)(x_2-x_1)}

\frac{d}{dx} L(x_1) = y_0 \frac{2x_1 + (-x_1-x_2)}{(x_0-x_1)(x_0-x_2)} + y_1 \frac{2x_1 + (-x_0-x_2)}{(x_1-x_0)(x_1-x_2)} + y_2 \frac{2x_1 + (-x_1-x_2)}{(x_2-x_0)(x_2-x_1)}

\frac{d}{dx} L(x_2) = y_0 \frac{2x_2 + (-x_1-x_2)}{(x_0-x_1)(x_0-x_2)} + y_1 \frac{2x_2 + (-x_0-x_2)}{(x_1-x_0)(x_1-x_2)} + y_2 \frac{2x_2 + (-x_1-x_2)}{(x_2-x_0)(x_2-x_1)},

que, con equiespaciado, quedan:

L'(x_0) = \frac{3 y_0 -4 y_1 + y_2}{2 h_x},

L'(x_1) = \frac{y_0 -2 y_1 + y_2}{2 h_x} y

L'(x_2) = \frac{y_0 -4 y_1 + 3 y_2}{2 h_x}.

Laplaciano en cartesianas:

\Delta u = \Sigma_i \frac{\partial^2}{\partial x_i^2}u

1d

\frac{u_{i-1}-2u_i+u_{i+1}}{h^2} = f_i

\frac{1}{h^2}u_{i-1} + \frac{1}{h^2}u_{i+1} +\frac{-2}{h^2}u_i= f_i

2d

\frac{u_{i-1,j}-2u_{i,j}+u_{i+1,j}}{h_x^2} + \frac{u_{i,j-1}-2u_{i,j}+u_{i,j+1}}{h_y^2} = f_{i,j}

i fijo:

\frac{1}{h_y^2}u_{i,j-1} + \frac{1}{h_y^2}u_{i,j+1} +(\frac{-2}{h_x^2}+\frac{-2}{h_y^2})u_{i,j}= g_{i,j}(:=f_{i,j} + \frac{-1}{h_x^2}u_{i-1,j} + \frac{-1}{h_x^2}u_{i+1,j})

j fijo:

\frac{1}{h_x^2}u_{i-1,j} + \frac{1}{h_x^2}u_{i+1,j} +(\frac{-2}{h_x^2}+\frac{-2}{h_y^2})u_{i,j}= g_{i,j}(:=f_{i,j} + \frac{-1}{h_y^2}u_{i,j-1} + \frac{-1}{h_y^2}u_{i,j+1})

3d

\frac{u_{i-1,j,k}-2u_{i,j,k}+u_{i+1,j,k}}{h_x^2} + \frac{u_{i,j-1,k}-2u_{i,j,k}+u_{i,j+1,k}}{h_y^2} + \frac{u_{i,j,k-1}-2u_{i,j,k}+u_{i,j,k+1}}{h_z^2} = f_{i,j,k}

i,j fijos:

\frac{1}{h_z^2}u_{i,j,k-1} + \frac{1}{h_z^2}u_{i,j,k+1} +(\frac{-2}{h_x^2}+\frac{-2}{h_y^2}+\frac{-2}{h_z^2})u_{i,j,k}= g_{i,j,k}

(g_{i,j,k}:=f_{i,j,k} + \frac{-1}{h_x^2}u_{i-1,j,k} + \frac{-1}{h_x^2}u_{i+1,j,k} + \frac{-1}{h_y^2}u_{i,j-1,k} + \frac{-1}{h_y^2}u_{i,j+1,k})

i,k fijos:

\frac{1}{h_y^2}u_{i,j-1,k} + \frac{1}{h_y^2}u_{i,j+1,k} +(\frac{-2}{h_x^2}+\frac{-2}{h_y^2}+\frac{-2}{h_z^2})u_{i,j,k}= g_{i,j,k}

(g_{i,j,k}:=f_{i,j,k} + \frac{-1}{h_x^2}u_{i-1,j,k} + \frac{-1}{h_x^2}u_{i+1,j,k} + \frac{-1}{h_z^2}u_{i,j,k-1} + \frac{-1}{h_z^2}u_{i,j,k+1})

j,k fijos:

\frac{1}{h_x^2}u_{i-1,j,k} + \frac{1}{h_x^2}u_{i+1,j,k} +(\frac{-2}{h_x^2}+\frac{-2}{h_y^2}+\frac{-2}{h_z^2})u_{i,j,k}= g_{i,j,k}

(g_{i,j,k}:=f_{i,j,k} + \frac{-1}{h_y^2}u_{i,j-1,k} + \frac{-1}{h_y^2}u_{i,j+1,k} + \frac{-1}{h_z^2}u_{i,j,k-1} + \frac{-1}{h_z^2}u_{i,j,k+1})

Ya hace casi dos meses que no escribo nada en el blog :-(. Es hora de añadir algo.

El Block Cyclic Reduction es un algoritmo rápido para resolver sistemas de ecuaciones de manera directa cuya matriz tiene estructura tridiagonal por bloques.

Supongamos que tenemos una discretización de un volumen mediante cinco puntos para las x, tres puntos para las y y siete puntos para las z (necesitamos que sean números impares).

Para la dimensión z tenemos:

A_3 = \left(  \begin{array}{ccccccc}  6 & -1 & 0 & 0 & 0 & 0 & 0 \\  -1 & 6 & -1 & 0 & 0 & 0 & 0 \\  0 & -1 & 6 & -1 & 0 & 0 & 0 \\  0 & 0 & -1 & 6 & -1 & 0 & 0\\  0 & 0 & 0 & -1 & 6 & -1 & 0 \\  0 & 0 & 0 & 0 & -1 & 6 & -1\\  0 & 0 & 0 & 0 & 0 & -1 & 6  \end{array}  \right)

-I_3 =\left(  \begin{array}{ccccccc}  -1 & 0 & 0 & 0 & 0 & 0 & 0 \\  0 & -1 & 0 & 0 & 0 & 0 & 0 \\  0 & 0 & -1 & 0 & 0 & 0 & 0 \\  0 & 0 & 0 & -1 & 0 & 0 & 0 \\  0 & 0 & 0 & 0 & -1 & 0 & 0 \\  0 & 0 & 0 & 0 & 0 & -1 & 0 \\  0 & 0 & 0 & 0 & 0 & 0 & -1  \end{array}  \right)

Para la dimensión y no queda:

A_2 = \left(  \begin{array}{ccc}  A_3 & -I_3 & 0 \\  -I_3 & A_3 & -I_3 \\  0 & -I_3 & A_3  \end{array}  \right); \,\,\, -I_2 = \left(  \begin{array}{ccc}  -I_3 & 0 & 0 \\  0 & -I_3 & 0 \\  0 & 0 & -I_3  \end{array}  \right)

Y, finalmente, para la dimensión x obtenemos:

A_1 = \left(  \begin{array}{ccccc}  A_2 & -I_2 & 0 & 0 & 0 \\  -I_2 & A_2 & -I_2 & 0 & 0 \\  0 & -I_2 & A_2 & -I_2 & 0 \\  0 & 0 & -I_2 & A_2 & -I_2 \\  0 & 0 & 0 & -I_2 & A_2  \end{array}  \right).

Ahora todo es fácilmente generalizable a n dimensiones x_1, x_2, \ldots, x_n con t_1, t_2, \ldots, t_n puntos en cada dimensión, ya que nos queda A_i una matriz tridiagonal por bloques con t_i \times t_i bloques donde cada uno está formado por matrices A_{i-1} en la diagonal, -I_{i-1} arriba y debajo de la diagonal y 0 en el resto, todas de dimensión t_{i-1} \times t_{i-1} con i=1,\ldots, n. En A_n tenemos el stencil (-1,2n,-1).

En el caso que estamos tratando, para cada fila par de A_1 podemos multiplicarla por A_2 y sumarla a las filas impares anterior y posterior, de manera que eliminamos las variables pares:

-v^1_{j-2} + ((A_2)^2 - 2I_2)v^1_j - v^1_{j+2} = b^1_{j-1} + A_2 b^1_j + b^1_{j+1},

(el ^1 hace referencia a las x y no corresponde a potencias… Para resolver las k impares simplemente:

A_2 v^1_k = b^1_{k} + v^1_{k-1} + v^1_{k+1}. )

Y resulta que definiendo B_2:=(A_2)^2 - 2 I_2, nos queda una matriz B_1 de la misma estructura que A_1, por lo que podemos aplicar este metodo de manera recursiva hasta llegar a tener una sola ecuación (para esto, no basta con que tengamos un número impar de nodos, necesitamos algo como N=2^{k+1}-1).

Llegados a este punto, si estamos con v^n, resolvemos como queramos, pero si estamos en otra variable v^i con i\neq n, la matriz vuelve a tener la misma estructura, pero con una dimensión menos, y volvemos a aplicar el mismo algoritmo.

Tenemos dos lugares distintos donde aplicar recursividad: el primero por ir agrupando de tres en tres las ecuaciones de una dimensión de trabajo (A_i \rightarrow B_i \rightarrow \ldots \rightarrow F_i, F por poner algo :-)); el otro cuando, llegados a una sola ecuación aplicando la recursividad anterior, nos quedan mas dimensiones por resolver (B_{j+1}, B_{j+2}, \ldots ).

noviembre 2013
L M X J V S D
« Sep   Dic »
 123
45678910
11121314151617
18192021222324
252627282930