La convergencia del Método de Gradiente Conjugado para Positiva Semi-Definida la Matriz de

Question

Deje $A\in\mathbb{R}^{N\times N}$ ser positivo semi-definida la matriz, dado $b\in\mbox{Col}\left(A\right)$ queremos resolver el sistema de ecuaciones $Ax=b$ . Para agregar una notación, definimos $\left<u,v\right>_{A}:=u^{\top}Av$ y dado de partida adivinar $x^{0}$ definimos $d^{0}=r^{0}=b-Ax^{0}$ . El proceso iterativo de gradiente conjugado método ahora sigue estos actualización de ecuaciones: $$\alpha^{n}:=\frac{\left(d^{n}\right)^{\top}r^{n}}{\left\Vert d^{n}\right\Vert _{A}}$$ $$x^{n+1}=x^{n}+\alpha^{n}d^{n}$$ $$r^{n+1}:=b-Ax^{n+1}$$ $$d^{n+1}=r^{n+1}-\frac{\left<d^{n},r^{n+1}\right>_{A}}{\left\Vert d^{n}\right\Vert _{A}}d^{n} $$ Ahora, me han demostrado que, dada $A$ es positivo semi-definida, a continuación, $\left\Vert d^{n}\right\Vert _{A}=0$ iff $d^{n}=0$ y me han demostrado que $d^{n}\in\mbox{Col}\left(A\right)$ para todos los $n$ , la combinación de estos dos hechos muestra que $\alpha^{n}$ es bien definido y el método puede ser aplicado a positiva semi-definida matrices. Ahora quiero demostrar que, dado que el término de error $e^{n}:=\hat{x}-x^{n}$ (donde $\hat{x}$ es una solución para $Ax=b$ ) y dado que el $e^{n}\notin\ker\left(A\right)$ tenemos $\left\Vert e^{n}\right\Vert _{A}\to0$ al $n\to\infty$. También sería suficiente para mostrar que el $\frac{\left\Vert e^{n+1}\right\Vert _{A}}{\left\Vert e^{n}\right\Vert _{A}}<1$. Yo se recomienda buscar en representación del resto, el error y la solución actual en un eigenbasis de $A$ pero no he logrado conseguir en cualquier lugar, la ayuda sería muy apreciada.

Prueba de monotónica error disminución: Primero observar que $$e_{n+1}=x_{n+1}-\hat{x}=x_{n}+\alpha_{n}d_{n}-\hat{x}_{n}=e_{n}+\alpha_{n}d_{n}$$ Por lo tanto: $$\left\Vert e_{n+1}\right\Vert _{A}^{2}=\left(e_{n}+\alpha_{n}d_{n}\right)^{\top}A\left(e_{n}+\alpha_{n}d_{n}\right)$$ $$=e_{n}^{\top}Ae_{n}+\alpha_{n}e_{n}^{\top}Ad_{n}+\alpha_{n}\overbrace{d_{n}^{\top}Ae_{n}}^{=e_{n}^{\top}Ad_{n}}+\alpha_{n}^{2}d_{n}^{\top}Ad_{n}$$ $$=\left\Vert e_{n}\right\Vert _{A}^{2}+2\left(\frac{r_{n}^{\top}d_{n}}{d_{n}^{\top}Ad_{n}}\right)e_{n}^{\top}Ad_{n}+\left(\frac{r_{n}^{\top}d_{n}}{d_{n}^{\top}Ad_{n}}\right)^{2}d_{n}^{\top}Ad_{n}$$ $$=\left\Vert e_{n}\right\Vert _{A}^{2}+2\left(\frac{r_{n}^{\top}d_{n}}{d_{n}^{\top}Ad_{n}}\right)e_{n}^{\top}Ad_{n}+\frac{\left(r_{n}^{\top}d_{n}\right)^{2}}{d_{n}^{\top}Ad_{n}}$$ $$=\left\Vert e_{n}\right\Vert _{A}^{2}+2\left(\frac{\left(-Ae_{n}\right)^{\top}d_{n}}{d_{n}^{\top}Ad_{n}}\right)e_{n}^{\top}Ad_{n}+\frac{\left(\left(-Ae_{n}\right)^{\top}d_{n}\right)^{2}}{d_{n}^{\top}Ad_{n}}$$ $$=\left\Vert e_{n}\right\Vert _{A}^{2}-2\left(\frac{e_{n}^{\top}Ad_{n}}{d_{n}^{\top}Ad_{n}}\right)\overbrace{d_{n}^{\top}Ae_{n}}^{=e_{n}^{\top}Ad_{n}}+\frac{\left(e_{n}^{\top}Ad_{n}\right)^{2}}{d_{n}^{\top}Ad_{n}}$$ $$=\left\Vert e_{n}\right\Vert _{A}^{2}-2\frac{\left(e_{n}^{\top}Ad_{n}\right)^{2}}{d_{n}^{\top}Ad_{n}}+\frac{\left(e_{n}^{\top}Ad_{n}\right)^{2}}{d_{n}^{\top}Ad_{n}}=\left\Vert e_{n}\right\Vert _{A}^{2}-\frac{\left(e_{n}^{\top}Ad_{n}\right)^{2}}{\left\Vert d_{n}\right\Vert _{A}^{2}}<\left\Vert e_{n}\right\Vert _{A}^{2}$$ He utilizado el demostrar fácilmente igualdad de $r_{n}=-Ae_{n}$ y que la última vez que la desigualdad se cumple siempre y cuando $e_{n}\neq0$.

Answer 1

Yo era una especie de curiosidad acerca de una respuesta a trabajar en un eigenbasis de $A$ porque solo puedo pensar en el tratamiento de la cg-método de Krylow-método y no puedo ver la conexión directa que hay. Por lo tanto, si usted termina para arriba con una solución yo sería feliz si pudiera compartirlo aquí.

En retorno, por lo menos puedo ofrecer la versión que yo ya sé. Básicamente es el enfoque estrictamente positiva definida matrices, pero bajo las condiciones dadas parece trabajar para la semi-definido así (que en realidad me sorprende un poco, pero no puedo ver por qué no funciona) $-$ por favor me corrija si estoy equivocado.

Como usted se refiere a un poste con simétrica positiva semi-definida matrices en los comentarios, he supuesto que la matriz dada aquí es simétrica, también. Aunque esto posiblemente no sea necesario (pero entonces te definitivamente tengo que prestar más atención a cómo se utiliza realmente el $A$-producto escalar).

También se ha señalado que el método es bien definido como en el de $b\in \mbox{Col}(A)$ y $r^n, d^n \in \mbox{Col}(A)$ todos los $n\in\mathbb{N}$.

Pequeñas Correcciones

En su post que define el $A$-producto escalar $\langle u, v\rangle_A = u^\top A v$. Desde que, por lo general definen $\Vert u \Vert_A = \sqrt{\langle u, u\rangle_A}$. Usando esta definición, la actualización de las reglas de cambio $$ \alpha^n = \frac{\langle d^n, r^n\rangle_I}{\Vert d^n \Vert^2_A} $$ y $$ d^{n+1} = r^{n+1} - \frac{\langle d^n, r^{n+1}\rangle_A}{\Vert d^n\Vert_A^2} d^n\text{.} $$

$A$-ortogonalidad de búsqueda de direcciones

Si usted ya sabe que la búsqueda de direcciones $A$ortogonales, puede omitir esta parte. Me decidí a elaborar un poco porque es la parte importante (para Krylow-los métodos en general).

Definimos $$ K_n(a,r^0) = \mbox{span}\{ A^k r^0 \mediados de k \in \{0,\dots,n-1\}\} $$ para todos los $n\in\mathbb{N}$. Reclamamos:

Para todos los $n\in\mathbb{N}$ hemos $$ K_n(a,r^0) = \mbox{span}\{d^j \mediados de los j \in \{0,\dots,n-1\} \} = \mbox{span}\{r^j \mid \{0,\dots,n-1\} \} $$ y pairwise $A$-ortogonalidad de las direcciones $d^j$ $j\in\{0,\dots,n\}$ mientras $r_j \neq 0$ todos los $j\in\{0,\dots,n\}$.

La prueba se realiza a través de la inducción, donde la inducción de la declaración es claramente cumplió para $n=0$. Así que supongamos que la instrucción tiene para algunos $n\in \mathbb{N}$ e intentar mostrar por $n+1$. Primero de todo, por la definición de $r^n$ (utilizando la definición de $x^n$) tenemos para todos los $j\in\{0,\dots,n\}$ $$ r^n = r^j - \sum_{i=j}^{n-1} \alpha^i Ad^i. $$ En consecuencia, este rendimientos para todos los $j\in\{0,\dots,n-1\}$ $$ \begin{array}{rl} \langle d^j, r^{n} \rangle_I & = \left\langle d^j, r^j - \textstyle\sum_{i=j}^{n-1} \alpha^j Ad^i \right\rangle_I \\ & = \langle d^j, r^j - \alpha^j A d^j \rangle_I \\ & = \left \langle d^j, r^j - \frac{\langle d^j, r^j\rangle_A}{\langle d^j, d^j\rangle_A} Ad^j \right \rangle_I \\ & = 0 \end{array} $$ donde se utilizó $\langle d^j, d^i\rangle_A = 0$ $i,j \in \{0,\dots, n-1\}$ $i\neq j$ a través de la inducción de la asunción. En particular, se ha $r^{n} \perp K_{n}(A,r^0)$ $K_{n}(A,r^0) = \mbox{span}\{d_0,\dots,d_{n-1}\}$ (también por hipótesis de inducción).

Además, sabemos $K_{n-1}(A,r^0) = \mbox{span}\{r^0,\dots,A^{n-2}r^0\}$ y por lo tanto $$ AK_{n-1}(a,r^0) = \mbox{span}\{Ar^0,\dots,A^{n-1}r^0\} \subseteq \mbox{span}\{r^0,\dots,A^{n-1}r^0\} = K_n(a,r^0)\text{,} $$ lo que implica $Ad^j \in K_n(A,r^0)$ todos los $j\in \{0,\dots,n-2\}$. Junto con $r^{n} \perp K_{n}(A,r^0)$ esto lleva a $$ \langle r^n, d^j \rangle_A = (r^n)^\top Ad^j = 0 $$ para todos los $j\in\{0,\dots,n-2\}$. En particular, tiene para todos los $j\in \{0,\dots,n-2\}$, por definición, de $d^n$ y pairwise $A$-ortogonalidad de $\{d^i\}_{i\in\{0,\dots,n-1\}}$ a través de la inducción de la asunción con la igualdad $$ \langle d^n, d^j\rangle_A = \left\langle r^n - \frac{\langle d^{n-1}, r^n\rangle_A}{\Vert d^{n-1}\Vert_A^2} d^{n-1}, d^j\right\rangle_A = 0\text{.} $$ Además, tenemos por supuesto $\langle d^n, d^{n-1}\rangle_A=0$, demasiado, lo cual es evidente por el uso de la definición de $d^n$ anterior. En total, tenemos que $\{d^i\}_{i\in\{0,\dots,n\}}$ es de a pares $A$-ortogonal.

Por definición de $r^n$ $d^n$ sigue que $\mbox{span}\{d^j \mid j \in \{0,\dots,n\} \} = \mbox{span}\{r^j \mid \{0,\dots,n\} \}$ (este es bastante obvio?). También, la definición de $r^n$ muestra $r^n \in K_{n+1}(A,r^0)$.

La pairwise $A$-ortogonalidad y $\{d^i\}_{i\in\{0,\dots,n\}} \subseteq \mbox{Col}(A)$ implica la independencia lineal de $\{d^i\}_{i\in\{0,\dots,n\}}$ (Este paso es importante! Si no podemos asegurar $d^i \in \mbox{Col}(A)$ esto no sería nunca más). Para $d^n \neq 0$ (que es la continuación de $r^n \neq 0$) consecuentemente tenemos $K_n(A,r_0) \subsetneq \mbox{span}\{d^0,\dots,d^n\}$ y por lo tanto tenemos $K_{n+1}(A,r^0) = \mbox{span}\{d^0,\dots,d^n\}$ porque $d_n \in K_{n+1}(A,r^0)$ tiene (que sigue de la definición de $d^n = r^n - \beta^n d^{n-1}$$r^n \in K_{n+1}(A,r^0)$$d^{n-1} \in K_n(A,r^0)$). Todo ello nos lleva a $$ K_n(a,r^0) = \mbox{span}\{d^j \mediados de los j \in \{0,\dots,n-1\} \} = \mbox{span}\{r^j \mid \{0,\dots,n-1\} \} $$ por lo que la demanda está demostrado.

La convergencia

Esta parte básicamente, utiliza los mismos argumentos que en la prueba anterior. Tan sólo para el caso de que la parte se omite o es parte del mal...

Deje $n\in\mathbb{N}$ $\hat{x}$ cumplir $A\hat{x} = b$. Luego tenemos a $A(\hat{x}-x^n) = b-Ax^n = r^n$. El uso de $A$-ortogonalidad de las $d^j$ tenemos para todos los $j\in \{0,\dots,n-1\}$ (igual que en la prueba anterior) $$ \langle r^n, d^j \rangle_I = \langle r^j - \estilo de texto \sum_{i=j}^{n-1} \alpha^i Ad^i, d^j \rangle_I = \langle r^j - ^j Ad^j, d^j \rangle_I = \langle r^j - \frac{\langle r^j, d^j\rangle_A}{\langle d^j, d^j\rangle_A} d^j, d^j \rangle_I = 0. $$ Debido a que el $d^j$ $A$- ortogonal, que no sea cero (cosa que ya convergente) y un subconjunto de a $\mbox{Col}(A)$ tenemos que la $d^j$ son linealmente independientes. Esto implica que para $n = \mbox{dim}(\mbox{Col}(A))$ tiene $\mbox{span}\{d_0,\dots,d_{n-1}\} = \mbox{Col}(A)$. A partir de la anterior propiedad continuación, se ha $r^n \perp \mbox{span}\{d_0,\dots,d_{n-1}\} = \mbox{Col}(A)$ pero por la construcción también tenemos $r^n \in \mbox{Col}(A)$. Esto implica $r^n = 0$. Así que tenemos $0 = r^n = b - Ax^n$ y por lo tanto $$ \Vert \hat{x}-x^n \Vert_A^2 = \langle \hat{x} - x, \hat{x}-x \rangle_A = (\hat{x}-x)^\la parte superior de Un(\hat{x}-x) = (\hat{x}-x)^\top r^n = 0\text{.} $$ En particular, se ha $\Vert \hat{x}-x^n \Vert_A^2 \to 0 $$n\to \infty$.