Simetría de la matriz de diferenciación

Question

Tengo un problema de computación numérica de los valores propios de Laplace-Beltrami operador. Yo uso meshfree Funciones de Base Radial (RBF) enfoque para la construcción de la diferenciación de la matriz $D$. Las pruebas de mi código en simples colectores (por ejemplo, en una unidad de la esfera) muestra que calcula los autovalores de a $D$ a menudo tienen distinto de cero imaginaria, aunque todos ellos deben ser real.

---

(Para simplificar, me voy a referir a la Kansa RBF método a partir de ahora).

Dado un conjunto de puntos de $\vec{\mathbf x} = \left\{x _i \right\}_{i=1}^{n}$ y una función de $f$ nos dicen que $D$ es la diferenciación de la matriz (para el operador de Laplace) si $D \,f\left(\vec{\mathbf x} \right) = \Delta f\left(\vec{\mathbf x} \right)$.

La diferenciación de la matriz se construye como $D = B\cdot A^{-1}$ donde $B$ es la métrica de la matriz para RBF expansión de $\Delta f$, e $A$ es la métrica de la matriz para RBF expansión de $f$. Tanto en $A$ $B$ son simétricas, por lo $D$ también debe ser simétrica. Sin embargo, los complejos autovalores reales de la matriz significa que $D$ no es simétrica, a pesar del hecho de que $D$ está formado por todas las matrices simétricas.

Por lo que entiendo, la simetría sólo podía ser violado cuando se calcula la inversa de la matriz métrica $A$, especialmente si $A$ es un mal condicionado de la matriz. Mi pregunta es:

¿Cuáles son los métodos para "symmetrizing" diferenciación métrica de las matrices?

Alternativamente,

Cómo deshacerse de la asimetría que se da cuando se calcula numéricamente la inversa de una matriz simétrica y causado por la máquina de error de redondeo?

---

EDITAR: A continuación es un ejemplo de cómo construir la diferenciación de la matriz $D$ para el operador de Laplace.

---

Dado: el Dominio $\Omega$ en el espacio Euclidiano, el conjunto de puntos de $\vec{\mathbf x} = \left\{x _i \right\}_{i=1}^{n}$.

Objetivo: Encontrar numéricamente autovalores del operador de Laplace $\Delta = \nabla ^2$ definido en $\Omega$.

La solución consta de tres pasos:

1. Construir la diferenciación de la matriz $D$ que actuará como operador de Laplace para cualquier función estimada en un dado (finito) conjunto de puntos de $\vec{\mathbf x}$.
2. Calcular los autovalores de a $D$.
3. Comparar los valores propios de a $D$ con valores propios de la Laplaciano $\Delta$, con lo que la estimación del error.

Nota que los autovalores de a $\Delta$ son positivos, por lo tanto, buena diferenciación de la matriz $D$ también tendrá todos los autovalores positivos, por lo tanto, $D$ se $symmetric$ a fin de imitar con precisión la acción de operador $\Delta$ sobre las funciones estimada en $\vec{\mathbf x}$.

Por lo tanto tengo que encontrar una manera de construir la diferenciación de la matriz $D$ y para asegurarse de que es simétrica.

---

Considere una función de $\phi_i = \phi_i(x) = \phi(\| x_i - x\|)$ conoce como Función de Base Radial (o RBF) centrado en $x_i\in \vec{\mathbf x}$. El conjunto $\{\phi_i\}_{i=1}^{n}$ de RBFs centrado en $\vec{\mathbf x}$ puede ser utilizado para aproximar cualquier función de $f(x)$: $$f(x) \approx \sum_{i=1}^{n} \alpha_i \phi_i(x) = \sum_{i=1}^{n} \alpha_i \phi(\| x_i - x\|) \label{1} \tag{1}$$ Denota el vector de coeficientes de $\vec{\boldsymbol{\alpha}} = \{ \alpha_i\}_{i=1}^{n}$ y un vector de valores de$f$$\vec{\mathbf x}$$\vec{\mathbf{f}} = f\left(\vec{\mathbf x}\right)$ . Entonces podemos escribir la RBF expansión de $f$ en la matriz de la forma: $$\label{2}\etiqueta{2} \begin{bmatrix}f\left( x_1 \right)\\ f\left( x_1 \right)\\ \vdots \\ f\left( x_n \right) \end{bmatrix} = \begin{bmatrix} \phi_{1} \left(x_{1}\right) & \phi_{1} \left( x_2 \right) & \cdots & \phi_{1} \left(x_n \right) \\ \phi_{2} \left(x_{1}\right) & \phi_{2} \left( x_2 \right) & \cdots & \phi_{2} \left(x_n \right) \\ \vdots & \vdots & \ddots & \vdots \\ \phi_{n} \left(x_{1}\right) & \phi_{n} \left( x_2 \right) & \cdots & \phi_{n} \left(x_n \right) \end{bmatrix} \begin{bmatrix} \alpha_1 \\ \alpha_2 \\ \vdots \\ \alpha_n\end{bmatrix} \iff \vec{\mathbf{f}} = \Phi \, \vec{\boldsymbol{\alpha}} \implica \vec{\boldsymbol{\alpha}} = \Phi^{-1}\vec{\mathbf{f}},$$ donde $\Phi_{ij} = \phi_i(x_j) = \phi\left(\left\|x_i - x_j \right\| \right)$.

Aplicar el operador de Laplace a la RBF expansión $\eqref{1}$ de una función de $f$, obtenemos $\Delta \vec{\mathbf{f}} = \Delta\Phi\, \vec{\boldsymbol{\alpha}},$ donde $\Delta\Phi_{ij} := \Delta\phi_i(x_j) = \Delta \phi\left(\left\|x_i - x_j \right\| \right)$. Sustituyendo $\vec{\boldsymbol{\alpha}}$$\eqref{2}$, obtenemos $$\Delta \vec{\mathbf{f}} = \Delta \Phi\cdot \Phi^{-1} \cdot \vec{\mathbf{f}}.$$ Denotando $A = \Phi$$B = \Delta \Phi$, escribimos la diferenciación de la matriz: $$D = \Delta \Phi\cdot\Phi^{-1} = B \cdot A^{-1} \implica D \vec{\mathbf{f}} = \Delta \vec{\mathbf{f}}$$ para cualquier función de $f$ estimado en puntos de $\vec{\mathbf{x}}$.

Answer 1

Si $A$ $B$ son simétricas que no significa que $B A^{-1}$ es también simétrica $$(B A^{-1})^\top = A^{-\top}B^\top = A^{-1} B.$$ La última matriz es igual a $B A^{-1}$ si $A$ $B$ conmutan (que es el mismo que tienen el mismo conjunto de vectores propios).

Una combinación simétrica podría ser $B^{1/2} A^{-1} B^{1/2}$ o $A^{-1/2}BA^{-1/2}$, pero no estoy seguro de que funcionaría como un $\Delta$ aproximación. Aquí $B^{1/2}$ es simétrica raíz cuadrada dada por $$B = Q \operatorname{diag}(\lambda_1, \lambda_2, \dots, \lambda_n) Q^\top\\ B^{1/2} = Q\operatorname{diag}(\sqrt\lambda_1, \sqrt\lambda_2, \dots, \sqrt\lambda_n) Q^\la parte superior$$

Para la segunda pregunta - muchas implementaciones, por ejemplo, LAPACK, tienen rutinas para matrices simétricas que aceptar sólo la mitad de ella (superior o inferior). Por lo tanto, no hay errores de redondeo pueden hacer que la matriz asimétrica ya que las rutinas de nunca tener acceso a la otra mitad de la matriz. Por ejemplo, el autovalor solvers de tridiagonal matrices simplemente no tienen una opción para devolver valores complejos de autovalores.

Answer 2

Gracias por una gran pregunta. Uno de los problemas es la interpolación de datos dispersos, otra es la aproximación de los derivados, a menudo se resuelve mediante el RBF y diferencias finitas, correspondientemente.

Creo que es demasiado optimista esperar a tener todavía un bien planteado RBF interpolación problema el uso de los derivados de la función de base. La clase de RBF núcleos que puede ser utilizado con éxito en la interpolación de datos arbitrarios es limitada y no se cierra en virtud de la diferenciación. Aunque sus derivados son vistos en una de Hermite RBF interpolación sobre muestras de la función y sus derivados; la manera que usted la esperanza de que ellos a la aproximación de Laplace usando la función de punto de información de la evaluación sólo no está garantizado para trabajar bien. La falta de simetría podría ser el menor de sus problemas.

Yo sugeriría que la combinación de la RBF interpolación con un finito de diferencias, el Laplaciano Discreto de la matriz. Después de todo, la diferenciación es una operación local, mientras que RBF está destinado a tener en cuenta multi-escala de tendencias en los datos. La combinación de la matriz sería simétrica entonces, creo yo.

Answer 3

Ahora veo que me estaba explicando algo equivocado, acabamos de llegar a lo que ya tenemos, solo calculado con un poco más estable algoritmo. De hecho, en el nonorthogonal caso, se obtiene la matriz de $A$. Eso no es un problema, nunca se debe mirar en la forma $DA^{-1}$. Es lo que llamamos un generalizada autovalor problema, y tiene que ser escrita en la forma

$$(D-\lambda A)\vec{v}=0$$ (observe que $A$ sustituye a la identidad). Eso es lógicamente correcto, porque en este contexto, $I$ es reemplazado por la métrica. Este tipo de problemas es resuelto de forma rutinaria, ya sea para algoritmos específicos para generalizada de valores propios, o bien, mediante la descomposición de Cholesky de la matriz $A$ (o un poco menos eficiente, utilizando autovalor de la descomposición de $B$, cambiando las cosas y terminar con autovalor de la descomposición de $D$).

Esto viene precisamente de su condición de ortogonalidad - debido a la ortogonalidad se define a través de $A$ lugar de identidad (un diferente producto interior), los vectores propios no ser ortogonales en el sentido tradicional. Eso es lo que la Cholesky/A-Autovalor de descomposición: orthogonalizes los vectores en su métrica. Así,

$$A=LL^T$$ $$(L^{-1} D{L^{T}}^{-1} -\lambda I ) (L^{T} \vec{v})=0$$

Lo siento por la confusión antes.