Error relativo en la solución cuando la matriz está perturbada

Question

Supongamos que $A \in \mathbb{R}^{n \times n}$ es una matriz invertible y que $Ax=b$ para algunos $x,b \in \mathbb{R}^{n}$ . Si $\kappa(A)$ denota el número de condición de $A$ es bien sabido que si $b$ es perturbado por $\Delta b$ entonces $x$ se ve perturbado por $\Delta x$ que satisface $$ \frac{\|\Delta x \|}{\|x\|} \leq \kappa(A) \frac{\|\Delta b\|}{\|b\|}. $$

Si además $A$ también se perturba a $A+\Delta A$ que es invertible, me pregunto si es posible decir algo parecido como $$ \frac{\|\Delta x \|}{\|x\|} \leq \kappa(A) \left( \frac{\|\Delta A\|}{\|A\|}+ \frac{\|\Delta b\|}{\|b\|} \right). $$ En otras palabras, al cambiar ambos $A,b$ a $A+\Delta A, b+\Delta b$ La solución es cómo controlar el cambio. $x$ a $x+\Delta x$ ?

Answer 1

Sí, algo así es cierto. Puede encontrar la prueba, por ejemplo, en este libro y puede rodear estas líneas.

Tenemos $Ax=b$ y $(A+\Delta A)(x+\Delta x)=b+\Delta b$ . Esto da $(A+\Delta A)\Delta x=\Delta b-\Delta Ax$ . Si $A+\Delta A$ es invertible, tenemos $\Delta x=(A+\Delta A)^{-1}(\Delta b-\Delta Ax)$ . Tomar una norma y utilizar $\|b\|=\|Ax\|\leq\|A\|\|x\|$ da $$ \frac{\|\Delta x\|}{\|x\|} \leq \|(A+\Delta A)^{-1}\|\|A\|\left(\frac{\|\Delta b\|}{\|b\|}+\frac{\|\Delta A\|}{\|A\|}\right). \tag{$ \N - La estrella $} $$

Queda por acotar la norma de la inversa de $A+\Delta A$ . Desde $I=(A+\Delta A)^{-1}(A+\Delta A)$ tenemos $(A+\Delta A)^{-1}=A^{-1}-(A+\Delta A)^{-1}\Delta A A^{-1}.$ Si se toma la norma se obtiene $$ \|(A+\Delta A)^{-1}\|\leq \|A^{-1}\| + \|(A+\Delta A)^{-1}\|\|\Delta AA^{-1}\|. $$ por lo que si $\|\Delta AA^{-1}\|<1$ entonces $$ \|(A+\Delta A)^{-1}\|\leq\frac{\|A^{-1}\|}{1-\|\Delta AA^{-1}\|}. $$

Sustituyendo a ( $\star$ ) da que

Si ( $\ast$ ), entonces $$ \frac{\|\Delta x\|}{\|x\|} \leq \frac{\kappa(A)}{1-\|\Delta AA^{-1}\|}\left(\frac{\|\Delta b\|}{\|b\|}+\frac{\|\Delta A\|}{\|A\|}\right). $$

De $\|\Delta AA^{-1}\|\leq\|\Delta A\|\|A^{-1}\|$ se puede conseguir una declaración un poco más "ordenada".

Si $$ \frac{\|\Delta A\|}{\|A\|}<\frac{1}{\kappa(A)} $$ entonces $$ \frac{\|\Delta x\|}{\|x\|} \leq \frac{\kappa(A)}{1-\frac{\|\Delta A\|}{\|A\|}\kappa(A)}\left(\frac{\|\Delta b\|}{\|b\|}+\frac{\|\Delta A\|}{\|A\|}\right) $$ y si $\|\Delta A\|\leq\epsilon\|A\|$ y $\|\Delta b\|\leq\epsilon\|b\|$ entonces $$ \frac{\|\Delta x\|}{\|x\|} \leq \frac{2\epsilon\kappa(A)}{1-\epsilon\kappa(A)}. $$

Por supuesto, se puede eliminar el denominador "molesto" utilizando una suposición más fuerte. Por ejemplo, si $\epsilon\kappa(A)<1/2$ entonces $$ \frac{\|\Delta x\|}{\|x\|} \leq 4\epsilon\kappa(A). $$