Teniendo en cuenta el error en el método de cg, calcular un límite inferior para el número de condición

Question

Edit: Si falta información, por favor, dime y voy a editar la pregunta. Gracias de nuevo!

El gradiente conjugado (cg) método fue aplicado a una Matriz positiva definida $A$. Es sabido que $||e||_A=1$ $||e^{10}||_A=2^{-9}$ (donde $e$ es el error de $||e^k||_A= ||x-x^k||_A$). Calcular con esta información un límite inferior para $κ(A)$ (donde $κ$ es la condición número) y compararla con la ecuación $$k \geq \frac{1}{2}(\sqrt{κ(A)}\ln(2/ε))$$ donde ε es el factor por el cual el error es reducido, se define como $$||e^k||_A= ||x-x^k||_A \leq ε||e^0||_A$$

He aquí lo que tengo hasta ahora. Si lo he entendido correctamente $ε=2^{-9}/1=2^{-9}$. Sin embargo yo no podía entender cómo la única de la que puedo calcular la condición de número. No la condición requieren un conocimiento de la matriz y a la inversa? $κ=||A||||A^{-1}||$

He calculado lo $κ$ debe ser el uso de la ecuación de $k \geq \frac{1}{2}(\sqrt{κ(A)}\ln(2/ε))$ y tengo $$10 \geq \frac{6.93}{2}(\sqrt{κ(A)})$$ $$2.89 \geq \sqrt{κ(A)}$$ $$8.33 \geq κ(A)$$

¿Cómo puedo seguir adelante? Gracias de antemano!

Answer 1

Mi intento ... yo no soy de las matemáticas chico, así que siéntase libre de tirar la basura!

Creo que se debe utilizar la relación entre la velocidad de convergencia de CG y la condición de la $A$-matriz. Verificación de estas notas de la conferencia para los detalles completos, me refiero específicamente a la fórmula (52) en la página 36

$$ \lvert\lvert e_{(i)}\rvert\rvert_A\leq % 2\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^i% \lvert\lvert e_{(0)}\rvert\rvert_A $$

donde $e_{(0)}=x_{(0)}-x$ es el error inicial. En su caso $\lvert\lvert e_{(0)}\rvert\rvert_A=1$ $i=10$

$$ \frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\geq% \left(\frac{\lvert\lvert e_{(10)}\rvert\rvert_A}{2}\right)^{1/10}=\frac{1}{2} $$

la última ecuación se puede resolver fácilmente observando que $f(\kappa)=(\sqrt{k}-1)/(\sqrt{\kappa}+1)$ es una función monótonamente creciente en $[1,\infty)$, por lo tanto si $f(\bar{\kappa})= 1/2 \Rightarrow$$f(\kappa > \bar{\kappa})\geq 1/2$, lo que supone el límite inferior $\kappa\geq\bar{\kappa}$. El valor de $\bar{\kappa}$ se obtiene la solución de

$$ \frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}=\frac{1}{2}\Rightarrow\bar{\kappa}=3^2=9 $$

Por lo tanto el límite inferior debe ser $\kappa\geq 9$. Ahora, en las notas de la conferencia que he utilizado, la dirección de la desigualdad se invierte, por lo que se debe calcular un límite inferior también... pero no estoy seguro de eso! Saludos!