Cómo aproximar numéricamente el gradiente de la función en un triangular de malla

Question

Debido a un arbitrario (digamos 2D) malla triangular, con los conocidos $(x_i,y_i)$ ubicaciones de puntos, y los valores numéricos de la función $f$ de ellos (ya sea en los nodos, o en los centroides de los triángulos, no importa) como este ejemplo al azar, ¿cómo puedo obtener una aproximación numérica de la dirección y el módulo del gradiente en los nodos?

Puedo conseguir direccional degradados a los nodos adyacentes o elementos, pero no sé cómo unirse a ellos para crear un general de gradiente. Tengo la sensación de que esto implicará algún tipo de solución de mínimos cuadrados.

PD: si es pertinente, se puede asumir funciones lineales en los triángulos.

EDIT: no tengo conocimiento de la terminología, sino como una prueba inicial que puedo comprobar si el gradiente que se aproxima de forma lineal, y cuadráticamente de la real gradiente (por las pruebas en contra de una conocida plano y a la parábola). En la actualidad leer más sobre esto.

Answer 1

EDIT: Hemos encontrado una nueva en mi opinión la solución más elegante, ver esta respuesta.

Otra forma es primero calcular el gradiente en cada triángulo: $\nabla f|_T = [a,b]$ donde

$$\begin{bmatrix} x_1 & y_1 & 1 \\ x_2 & y_2 & 1 \\ x_3 & y_3 & 1 \end{bmatrix} \begin{bmatrix} a \\ b \\ c \end{bmatrix} = \begin{bmatrix} f(x_1,y_1) \\ f(x_2,y_2)\\ f(x_3,y_3) \end{bmatrix}$$

(somos el ajuste de un avión $p(x,y) = ax+by+c$ en cada triángulo).

Para calcular el gradiente en cada nodo sólo tenemos que utilizar un promedio ponderado de todos los triángulos que contienen ese nodo. Podemos hacerlo mediante el ángulo de $\alpha_{n,T}$ de cada triángulo $T$ en nuestro nodo $n$.

$$\nabla f_{n} = \frac{1}{2\pi} \sum_{T \in N} \alpha_{n,T}\nabla f|_T$$

Alternativamente, usted puede pesar cada una de las $\nabla f|_T$ por el área de la correspondiente triángulo (y normalizar a través de la superficie total de los alrededores de los triángulos). Esto tiene la ventaja de que también podemos reutilizar los pesos. Ambos métodos tienen la desventaja de que usted también necesita saber todos los elementos del nodo determinado se encuentre en, no sólo los bordes.

---

Otro método que sólo utiliza el conocimiento de los bordes es adecuado $p(x,y) = ax+by+c$ (a través de mínimos cuadrados) para todos los puntos que tienen bordes a nuestro nodo. De nuevo, esto no es muy adecuado para los no regulares de las mallas.

Answer 2

Este va a ser un poco de "fuerza bruta". El error de esta aproximación se escala como $\mathcal{O}(h)$ donde $h$ es el tamaño de la malla.

Tomar un punto de $(x_0, y_0)$ $i$ vecinos. Podemos calcular derivados en la dirección de los vecinos por:

$$\vec{f_i'} \approx \frac{f(x_0, y_0) - f(x_i, y_i)}{r_i} \begin{bmatrix} (x_0 - x_i)/r_i \\ (y_0 - y_i)/r_i \end{bmatrix}$$

donde $r$ la distancia está dada por $\sqrt{(x_0 - x_i)^2 + (y_0 -y_i)^2}$.

A partir de aquí: usted tiene $i$ aproximaciones para el gradiente en el punto. Tomar un promedio ponderado de las aproximaciones (donde los pesos son definidos por la distancia que la cierra puntos tienen la mayor influencia)

$$\vec{f_{\text{final}}'} = \left(\sum_i \frac{1}{r_i}\right)^{-1} \left(\sum_i \frac{\vec{f_i'}}{r_i}\right)$$

Answer 3

La clave de la cosa que usted necesita hacer es buscar "discretos geometría diferencial", que es esencialmente todo acerca de temas como este.

Una rápida y sucia respuesta que funciona bastante bien para el buen comportamiento de las mallas (es decir, aquellos en los que la valencia de cada vértice es bastante cerca de las 6, en lugar de ser, digamos, 14...) y donde los triángulos son más o menos iguales (no hay ángulos de menos de 20 grados, por ejemplo), es este:

$$ \nabla f (v) = \sum_{u\N(v)} \left( f(u) - f(v) \right), $$ donde $N(v)$ es el conjunto de vértices adyacentes a $v$ (es decir, los vértices $u$ con la propiedad de que $uv$ es un borde de la malla).

Answer 4

Esta idea se basa en @PiotrHughes respuesta, que por desgracia no proporciona buenos resultados incluso para el caso sencillo de una función lineal.

Idea: La idea es la siguiente: queremos calcular el gradiente en $P_0 = (x_0,y_0)$ a que los bordes de la $P_i = (x_i,y_i)$$i=1,2,3,...n$. Consideremos los vectores unitarios $d_i$ apuntan desde la $P_0$$P_i$, así que vamos a $r_i = P_i - P_0$$d_i = \frac{1}{||r_i||}(r_i)$.

Entonces el producto escalar $\nabla f(x_0,y_0) \cdot d_i$ es la derivada direccional en la dirección $d_i$. Estas derivadas direccionales se puede aproximar por $$\nabla f(x_0,y_0) \cdot d_i \approx \frac{f(x_i,y_i)-f(x_0,y_0)}{||r_i||}$$

Esto nos da una ecuación para cada borde, y si tenemos al menos dos no colinear bordes podemos resolver este sistema por $\nabla f(x_0,y_0)$ el uso de mínimos cuadrados.

Aplicación: Podemos simplificar este sistema

$$\begin{bmatrix} x_1-x_0 & y_1-y_0 \\ x_2-x_0 & y_2-y_0 \\ \vdots & \vdots \\ x_n - x_0 & y_n - y_0 \end{bmatrix} \nabla f(x_0,y_0) = \begin{bmatrix} f(x_1,y_1) - f(x_0,y_0) \\ f(x_2,y_2) - f(x_0,y_0) \\ \vdots \\ f(x_n,y_n) - f(x_0,y_0) \end{bmatrix}$$

Convergencia: La única aproximación que hemos hecho es el uso de las diferencias finitas para la aproximación de las derivadas direccionales. Suponiendo que tenemos una regular y cuasi uniforme de la familia de las mallas estos deben coincidir con el orden. Y es, sin duda, proporciona resultados exactos si $f$ es lineal.

---

EDIT: Equivalentemente, podemos reescribir la ecuación de arriba como

$$\begin{bmatrix} x_1-x_0 & y_1-y_0 & 1\\ x_2-x_0 & y_2-y_0 & 1\\ \vdots & \vdots &\vdots \\ x_n - x_0 & y_n - y_0 & 1\end{bmatrix} \begin{bmatrix} \nabla f(x_0,y_0) \\ f(x_0,y_0)\end{bmatrix}= \begin{bmatrix} f(x_1,y_1) \\ f(x_2,y_2) \\ \vdots \\ f(x_n,y_n) \end{bmatrix}$$

Ahora se hace muy evidente que estamos en el ajuste de un avión a través de los puntos circundantes. Que fue lo que me sugirió como un comentario aquí.

Answer 5

En primer lugar, si usted extender $f$ linealmente a lo largo de cada triángulo, y el resultado es una función no puede ser extendida a una función suave en un espacio de 3 dimensiones, a menos que el triángulo se encuentran en un plano. Para decirlo sin rodeos: el problema está mal planteado: desea que el gradiente de un no-función derivable.

Tal vez usted va a decir "Bueno, me acaba de dar el gradiente de cualquier differentiably función que tiene esos valores en los vértices", y de nuevo es el mal planteado, porque no e infinitamente muchas de tales funciones.

Lo que usted realmente necesita hacer es especificar el problema con más precisión (que es difícil de hacer). Usted podría, por ejemplo, decir que "Entre todos diff l funciones con esos valores, encontrar el uno cuyo cuadrado de la magnitud del gradiente tiene la menor integral sobre la superficie". Sin algún criterio, no hay una respuesta razonable a la pregunta.

En particular, hay una función suave $f$, cumpliendo su vértice valores, con la propiedad de que su gradiente en cada vértice es igual a cero.