Mayor autovalor de una simétrica positiva definida la matriz de clasificación en una de las actualizaciones

Question

Tengo un $n \times n$ simétrica positiva definida la matriz de $A$ que me repetidamente la actualización por medio de dos números consecutivos-una de las actualizaciones de la forma

$A' = A + e_j u^T +u e_j^T$

donde $\{e_i: 1 \leq i \leq n\}$ es el estándar de la base.

Yo también calcular las actualizaciones a $A^{-1}$ el uso de Sherman-Morrison. Debido a la naturaleza de las actualizaciones, la matriz $A'$ está garantizado para ser no-singular y positiva definida.

Me gustaría seguir la pista de el mayor y el menor autovalor de la matriz. Desde que tengo la inversa, un método para el cálculo de la más grande (o más pequeño) autovalor sería suficiente.

Sé que puedo calcular el eigendecomposition de $A$ y actualización en $O(n^2)$ pero me preguntaba si no era un método más eficiente ya que sólo se preocupan por una particular autovalor (y no en todos acerca de los vectores propios).

Un límite inferior en el autovalor, también podría ser útil, pero habría que ser apretado. Gershgorin discos parecen demasiado flojo.

Por último, si tengo que ir a través de la eigendecomposition ruta, los punteros a qué algoritmos se utilizan en la práctica para la eficiencia computacional y numérico de la estabilidad?

Answer 1

Usted podría utilizar aleatorizado de enfermedad vesicular porcina para obtener la dominante vectores propios de a $A'$ $(A')^{-1}$ a través de la aplicación de ellos a un puñado de prueba al azar de los vectores. Es un método de probabilidades, pero no son rigurosos límites en la probabilidad de fallos en términos de número de vectores de pruebas, y usted no tiene que utilizar muchos vectores de pruebas antes de que la probabilidad de fracaso se convierte en absurdamente pequeño como $1e-10$.

Usted puede mantener la misma prueba al azar de vectores de paso a paso y, a continuación, usted no tiene que volver a aplicar la matriz original $A$ en pasos posteriores.

Answer 2

No soy experto en este campo. Aquí están algunas evidentes límites, pero no estoy seguro de si puede ayudar. $$\lambda_\max(A')=\max\{x^TA'x = x^TAx + 2x_j\langle x,u\rangle:\|x\|_2=1\}.$$ Por el triángulo de la desigualdad, un evidente límite superior es $\lambda_\max(A') \le \lambda_\max(A) + 2\|u\|$. La igualdad se produce cuando $u$ es un múltiplo de a $e_j$ $e_j$ es un autovector correspondiente a $\lambda_\max(A)$.

Considerando los tres casos $x_j=0,\, x=\frac{u}{\|u\|}$$x=e_j$, un evidente límite inferior está dado por $$\lambda_\max(A') \ge \max\left\{\lambda_\max(A_j),\ \frac{u^TAu}{\|u\|^2} + 2u_j,\ a_{jj} + 2u_j\right\}, $$ donde $A_j$ denota la submatriz de a $A$ obtenido por la eliminación de la $j$fila y el $j$-ésima columna. La igualdad se produce cuando, por ejemplo, $A=I$$u=e_j$. Mediante el entrelazado de la desigualdad, usted puede conseguir un poco más débil obligado por la sustitución de $\lambda_\max(A_j)$$\lambda_2^\downarrow(A)$, la segunda mayor autovalor de a $A$.