Es el complemento de Schur mejor acondicionado que el original de la matriz?

Question

Considere el siguiente sistema lineal (en forma de bloque) con s.p.d. matriz: $$ \begin{pmatrix} A & B\\ B^\top & C \end{pmatrix} \begin{pmatrix} x\\y \end{pmatrix} = \begin{pmatrix} f\\g \end{pmatrix} $$ Me pregunto si la eliminación de algunas de las variables que hace mejorar el condicionamiento de la matriz de un sistema. Si eliminamos $y$ en primer lugar, mediante la sustitución de $y = C^{-1}g - C^{-1}B^\top x$ el siguiente sistema, se obtiene: $$ (A - BC^{-1}B^\la parte superior) x = f - BC^{-1}g. $$ La matriz del nuevo sistema es simplemente el complemento de Schur de la cuadra $C$.

La pregunta es si el número acondicionado de que el sistema resultante es menor que el número acondicionado de la original? El caso de $C = I$ es particularmente interesante.

He intentado usar la fórmula $$ 0 = \det \begin{pmatrix} A - \lambda I& B\\ B^\top & C - \lambda I \end{pmatrix} = \det(C - \lambda I) \det(A - \lambda I - B (C - \lambda I)^{-1}B^\la parte superior), $$ pero no hubo suerte, a pesar de $A - B (C - \lambda I)^{-1}B^\top$ parece estar muy cerca a $A - BC^{-1}B^\top$.

Experimentos numéricos muestran que la Schur complment siempre es mejor acondicionado que el de la matriz original, aquí está mi código.

Los experimentos también muestran que no sólo s.p.d, pero también en diagonal dominante M-matrices de compartir esta propiedad.

Answer 1

Lema. Si $P$ $Q$ dos $n\times n$ Hermitian matrices y $\operatorname{nullity}(Q)=k>0$, el mínimo autovalor de a $P+Q$ está acotada arriba por la $k$-ésimo mayor autovalor de a $P$.

La prueba del lema. Por Courant-Fischer minimax principio, \begin{align} \lambda_\min(P+Q) &=\min_{\|x\|=1}x^\ast(P+Q)x\\ &\le\min\limits_{\substack{x\in\ker(Q)\\ \|x\|=1}}x^\ast(P+Q)x\\ &=\min\limits_{\substack{x\in\ker(Q)\\ \|x\|=1}}x^\ast Px\\ &\le\max\limits_{\substack{V\subseteq\mathbb C^n\\ \dim V=k}} \min\limits_{\substack{x\in V\\ \|x\|=1}}x^\ast Px\\ &=\lambda_k^{\downarrow}(P).\ {}_{\large\square} \end{align}

Ahora, de regreso a su pregunta. Supongamos $A$$k\times k$$C$$(n-k)\times(n-k)$. Denotar por $S$ el complemento de Schur $A-BC^{-1}B^\top$. Su bloque de matriz se $P+Q$, donde $$ P=\pmatrix{S\\ &0}\ \text{ y }\ P=\pmatrix{BC^{-1/2}\\ C^{1/2}}\begin{matrix}\pmatrix{C^{-1/2}B^\top&C^{1/2}}\\ {}\end{matriz}. $$ Tenemos $\lambda_\min(P+Q)\le\lambda_k^{\downarrow}(P)=\lambda_\min(S)$ por nuestro lema y $\lambda_\max(S)=\lambda_\max(P)\le\lambda_\max(P+Q)$ porque $Q\succeq0$. Desde $\lambda_\min(P+Q)>0$, llegamos a la conclusión de que $$ \kappa(S)=\frac{\lambda_\max(S)}{\lambda_\min(S)}\le\frac{\lambda_\max(P+Q)}{\lambda_\min(P+Q)}=\kappa(P+Q). $$