Aplicación segura de métodos iterativos en matrices diagonalmente dominantes

Suponga que el siguiente sistema lineal se da

\begin{matrix} (1) & L x = c, \end{matrix}

$Lx=c,\tag1$ donde

L

$L$ es el Laplaciano ponderado que se sabe que es positivo

s e m i -

$semi-$ definido con un espacio nulo unidimensional dividido por

1_{n} = (1, \dots, 1) \in R^{n}

$1_n=(1,\dots,1)\in\mathbb{R}^n$ , y la varianza de traducción de

x \in R^{n}

$x\in\mathbb{R}^{n}$ , es decir,

x + a 1_{n}

$x+a1_n$ no cambia el valor de la función (cuya derivada es

(1)

$(1)$ ) Las únicas entradas positivas de

están en su diagonal, que es una suma de los valores absolutos de las entradas negativas fuera de la diagonal.

L

$L$

He encontrado en una muy citados trabajos académicos en su campo que, aunque es en diagonal dominante, métodos tales como gradiente conjugado, Gauss-Seidl, Jacobi, podrían aún ser utilizados con seguridad para resolver . La razón es que, debido a la invariancia de la traducción, es seguro fijar un punto (por ejemplo, eliminar la primera fila y columna de y la primera entrada de ), convirtiendo así a $L$ $not~strictly$ $(1)$ $L$ $c$ $L$ $strictly$ matriz diagonalmente dominante. De todos modos, el sistema original se resuelve en forma completa de , con . $(1)$ $L\in\mathbb{R}^{n\times n}$

¿Es correcta esta suposición y, de ser así, cuáles son las razones alternativas? Estoy tratando de entender cómo se mantiene la convergencia de los métodos.

Si el método de Jacobi es convergente con , ¿qué podría uno decir sobre el radio espectral de la matriz de iteración , donde es la matriz diagonal con entradas de en su diagonal? Es , por lo tanto, diferente de las garantías de convergencia general para $(1)$ $\rho$ $D^{-1}(D-L)$ $D$ $L$ $\rho(D^{-1}(D-L)\leq1$ ? Pregunto esto ya que los valores propios de la matriz laplaciana con unos en la diagonaldebenestar en el rango . $\rho(D^{-1}(D-L))<1$ $D^{-1}L$ $[0, 2]$

Del trabajo original:

......................................

En cada iteración, calculamos un nuevo diseño (x (t +1), y (t + 1)) resolviendo el siguiente sistema lineal: Sin pérdida de generalidad podemos fijar la ubicación de uno de los sensores (utilizando el grado de libertad de traducción del localizado estrés) y obtener una matriz estrictamente diagonalmente dominante. Por lo tanto, podemos usar de forma segura la iteración de Jacobi para resolver (8)

\begin{matrix} (8) & L \cdot x (t + 1) = L (x (t), y (t)) \cdot x (t) L \cdot y (t + 1) = L (x (t), y (t)) \cdot y (t) \end{matrix}

$L · x(t + 1) = L(x(t),y(t)) · x(t) \\ L · y(t + 1) = L(x(t),y(t)) · y(t) \tag 8$

.......................................

En lo anterior, la noción de "iteración" está relacionada con el procedimiento de minimización subyacente, y no debe confundirse con la iteración de Jacobi. Entonces, el sistema es resuelto por Jacobi (iterativamente), y luego la solución se compra al lado derecho de (8), pero ahora para otra iteración de la minimización subyacente. Espero que esto aclare el asunto.

Tenga en cuenta que encontré ¿Qué solucionadores lineales iterativos convergen para matrices semidefinidas positivas? , pero estoy buscando una respuesta más elaborada.

linear-algebra optimization iterative-method matrix linear-solver usero
fuente

¿Podría publicar un enlace o una cita al trabajo altamente citado?

Geoff Oxberry

Se puede recuperar de: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.164.1421 Dado que no se espera que lea todo el trabajo, eche un vistazo a la p.7 (abajo). Supongo que la elección de los solucionadores iterativos está justificada, pero creo que se necesita una justificación mejor (o, al menos, diferente).

usero

Me pregunto si estos tipos son de la misma comunidad que los preacondicionadores combinatorios.

shuhalo

Respuestas:

La iteración de Jacobi se puede demostrar convergente.

Lo primero que debe asegurarse es que , que es la condición para la existencia de la solución (supongo que , de lo contrario necesita ) porque dijo . Usaremos la convención de que $c^T \mathbf{1}_n = 0$ $L=L^T$ $c\in (\mathrm{Ker} L^T)^\perp$ $V_0:=\mathrm{Ker} L = \mathrm{span}\{\mathbf{1}_n\}$ $V_0$ es también la matriz con columnas siendo la base ortonormal de la misma. En su caso, . $V_0:=\mathbf{1}_n/\sqrt{n}$

Luego, para los errores de la iteración de Jacobi en el sistema original, tiene donde

e_{1} = (I - D^{- 1} L) e_{0} = (I - D^{- 1} L) (P e_{0} + V_{0} a) = (I - D^{- 1} L) P e_{0} + V_{0} a,

$e_1 = (I-D^{-1}L)e_0 = (I-D^{-1}L) (P e_0 + V_0a)=(I-D^{-1}L) P e_0 + V_0a,$

es la proyección ortogonal sobre

. De la iteración anterior, sabemos que

de la cual tenemos la matriz de iteración

Eso no

P := I - V_{0} V_{0}^{'}

$P:=I-V_0V_0'$

V_{1} := V_{0}^{⊥}

$V_1:=V_0^\perp$

P e_{1} = P (I - D^{- 1} L) P e_{0},

$P e_1 = P (I-D^{-1}L) P e_0,$

S

$S$

V_{1}

$V_1$

S := P (I - D^{- 1} L) P .

$S: = P (I-D^{-1}L) P.$

tiene los mismos espectros (excepto ceros) con la siguiente matriz

S

$S$

Queremos que el radio espectral de

menor que uno para demostrar la convergencia.

\tilde{S} := (I - D^{- 1} L) P P = (I - D^{- 1} L) P = (I - D^{- 1} L) (I - V_{0} V_{0}^{'}) = I - D^{- 1} L - V_{0} V_{0}^{'} .

$\tilde{S}:= (I-D^{-1}L) P P=(I-D^{-1}L) P=(I-D^{-1}L)(I-V_0V_0')\\ =I-D^{-1}L-V_0V_0'.$

S

$S$

La siguiente cita es antigua y se conserva solo como referencia. Ver después de la nueva prueba.

En su caso, Y puede verificar que es estrictamente dominante en diagonal utilizando el supuesto de que las entradas deson positivas en diagonal y negativas en caso contrario. Para mostrar que los valores propios de son reales, observamos que la matriz es autoadjunta bajo el producto interno $V_0V_0'=\frac{1}{n}\mathbf{1}_{n\times n}.$ $D^{-1}L+V_0V_0'$ $L$ $D^{-1}L+V_0V_0'$ $<x,y>:=y^TDx.$

Si no está en su forma específica, no he encontrado una respuesta a la pregunta de convergencia. ¿Alguien podría aclarar esto? $V_0$

Tenga en cuenta que es el eigen-vector correspondiente al valor propio de . En base a la observación, llamamos al Teorema 2.1 de los Valores propios de matrices actualizadas de rango uno con algunas aplicaciones de Jiu Ding y Ai-Hui Zhou. $V_0$ $1$ $I-D^{-1}L$

$u$ $v$ $n$ $u$ $A$ $\lambda_1$ $A+uv^T$ $\{\lambda_1+u^Tv,\lambda_2,\ldots,\lambda_n\}$

$\tilde{S}$ $I-D^{-1}L$ $1$ $-1$ $\rho(I-D^{-1}L)\subset (-1,1]$ $\rho(\tilde{S})\subset (-1,1)$

Hui Zhang
fuente

D^{- 1} L

$D^{-1}L$

[0, 2)

$[0, 2)$

(0, 2)

$(0, 2)$

0

$0$

0

$0$

I - D^{- 1} L

$I-D^{-1}L$

1

$1$

I - D^{- 1} L

$I-D^{-1}L$

0

$0$

D^{- 1} L

$D^{-1}L$

[0, 2]

$[0,2]$

2

$2$

2

$2$

2

$2$

I - D^{- 1} L

$I-D^{-1}L$

\leq 1

$\leq 1$

L

$L$

V_{1}

$V_1$

D^{- 1} L

$D^{−1}L$

2

$2$

c

$c$

V_{0}

$V_0$

I - D^{- 1} L - V_{0} V_{0}^{'}

$I-D^{-1}L-V_0V_0'$

s r

$sr$

I - D^{- 1} L

$I-D^{-1}L$

(0, 1]

$(0, 1]$

- \frac{1}{n}

$-\frac{1}{n}$

s r < 1

$sr<1$

\frac{1}{n}

$\frac{1}{n}$

\frac{1}{n} 1_{n \times n}

$\frac{1}{n}\mathbf{1}_{n\times n}$

s r

$sr$

I - D^{- 1} L

$I-D^{-1}L$

s r

$sr$

s r

$sr$

V_{0}

$V_0$

Los métodos de Krylov nunca usan explícitamente la dimensionalidad del espacio en el que iteran, por lo tanto, puede ejecutarlos en sistemas singulares siempre que mantenga las iteraciones en el subespacio no nulo. Esto normalmente se realiza proyectando el espacio nulo en cada iteración. Hay dos cosas que pueden salir mal, la primera es mucho más común que la segunda.

El preacondicionador es inestable cuando se aplica al operador singular. Los solucionadores directos y la factorización incompleta pueden tener esta propiedad. Como cuestión práctica, simplemente elegimos diferentes preacondicionadores, pero hay formas más basadas en principios para diseñar preacondicionadores para sistemas singulares, por ejemplo, Zhang (2010) .
$x$ $A x$

Para resolver sistemas singulares usando PETSc, ver KSPSetNullSpace(). La mayoría de los métodos y preacondicionadores pueden resolver sistemas singulares. En la práctica, el pequeño espacio nulo para PDE con condiciones de contorno de Neumann casi nunca es un problema, siempre que informe al solucionador de Krylov sobre el espacio nulo y elija un preacondicionador razonable.

$A x = b$ $b$ $A$ $b$

Jed Brown
fuente

Q

$Q$

A_{1} = Q^{T} A Q

$A_1 = Q^T A Q$

A_{1}

$A_1$

A_{1}

$A_1$

Z

$Z$

(I - Z) P^{- 1} A x = (I - Z) P^{- 1} b

$(I-Z)P^{-1} A x = (I-Z)P^{-1} b$

Hmm, parece que respondí a un comentario que fue eliminado. Dejaré el comentario aquí en caso de que sea útil.

Jed Brown

d i a g (A)

$diag(A)$

X_{k + 1} = D^{- 1} (b - (A - D) X_{k})

$X_{k+1}=D^{-1}(b-(A-D)X_k)$

X_{k + 1}

$X_{k+1}$

X_{k}

$X_{k}$

N = Z Z^{T}

$N=ZZ^T$

Z

$Z$

I - N

$I-N$

Z

$Z$

N = I - Z Z^{T}

$N=I-ZZ^T$ es el proyector.)

Jed Brown