Número de condición y $LU$ descomposición

Question

Considere $A: n \times n$ no singular y los factores $L$ y $U$ de $A$ obtenidos con la estrategia de pivotaje parcial, como: $PA = LU$ . Prueba de que $$\kappa_{\infty}(A) \geq \dfrac{||A||_{\infty}}{\min_{j}|u_{jj}|}.$$

El número de condición $\kappa_{\infty}(A)$ se define por $\kappa_{\infty}(A)=||A||_{\infty}||A^{-1}||_{\infty}$ .

Todo lo que pude mostrar fue que $\kappa_{\infty}(A) \geq \dfrac{||A||_{\infty}}{n ||U||_{\infty}}$ .

Pero no puedo conseguir el " $n$ "del denominador.

Esta pregunta me parece que tiene algún truco que no consigo entender. Discutí con algunos colegas y pensamos que esta pregunta es incorrecta. Pero aún así, no sabemos cómo demostrarlo.

Answer 1

Pista:

Eliminemos la matriz de permutación (supongamos que $A=LU$ ) y obsérvese que el pivotaje parcial implica que los valores absolutos de los elementos bajo la diagonal unitaria de $L$ están limitadas desde arriba por $1$ .

Ahora intenta usar esto: $$|u_{ii}^{-1}|=|e_i^TU^{-1}e_i| =|e_i^TA^{-1}Le_i| \leq\|A^{-T}e_i\|_1\|Le_i\|_\infty \leq\|A^{-T}\|_1 =\|A^{-1}\|_\infty.$$

Utilizamos los hechos que $|x^Ty|\leq\|x\|_1\|y\|_\infty$ para vectores y $\|X^T\|_1=\|X\|_\infty$ para matrices.

Answer 2

Respuesta parcial:

Lo que debemos mostrar es: $$||A^{-1}||_{\infty} \geq \frac 1 {\min_{j}|u_{jj}|}$$ Tenemos más: $$||A^{-1}|| = ||(PA)^{-1}||= ||(LU)^{-1}|| = ||U^{-1}L^{-1}||$$

Ahora, la diagonal de una matriz triangular invertida es simplemente la diagonal de la matriz triangular original con cada elemento invertido.

Más $i$ se elija de forma que $\min_j U_{j,j} = U_{i,i}$ y que $(A)_{k,l}$ representan la entrada de $A$ en el $k$ -ésima fila y $l$ -th columna.

Entonces tenemos: $$||U^{-1}L^{-1}||\ge |(U^{-1}L^{-1})_{i,i}| = \left|\sum_{k=1}^n (R^{-1})_{i,k}(L^{-1})_{k,i}\right| \\\\ =\left|(R^{-1})_{i,i}(L^{-1})_{i,i}+\sum_{k=1\\ k\neq i}^n (R^{-1})_{i,k}(L^{-1})_{k,i}\right| \\\\ =\left|\frac 1{\min_j U_{j,j}} + \sum_{k=1\\ k\neq i}^n (R^{-1})_{i,k}(L^{-1})_{k,i}\right|$$

Por lo tanto, para demostrar la desigualdad, ahora tenemos que demostrar $$\sum_{k=1\\ k\neq i}^n (R^{-1})_{i,k}(L^{-1})_{k,i}\ge 0$$