Warum funktioniert der konjugierte Gradient mit diesem unsymmetrischen Vorkonditionierer?

In diesem vorherigen Thread wurde der folgende multiplikative Weg vorgeschlagen, um die symmetrischen Vorkonditionierer und P 2 für das symmetrische System A x = b zu kombinieren : P - 1- Kombination : = P - 1 1 + P - 1 2 ( I - A P - 1 1 ) = P - 1 1 + P - 1 2 - P $P_1$$P_2$$Ax=b$

$$\begin{align} P_\text{combo}^{-1} :=& P_1^{-1} + P_2^{-1}(I - A P_1^{-1})\\ =&P_1^{-1} + P_2^{-1} - P_2^{-1} A P_1^{-1}. \end{align}$$

Dieser kombinierte Vorkonditionierer ist nicht symmetrisch. Ich habe jedoch versucht, es trotzdem in konjugierten Verläufen in verschiedenen Kontexten zu verwenden, und die Methode scheint immer gut zu konvergieren. Warum ist das?

---

Beispiel 1: Zufallsmatrizen.

% Testing multiplicative combination of preconditioners
n = 500;
[U,S,~] = svd(randn(n,n)); A = U*S*U';
[W1,S1,~] = svd(randn(n,n)); noise1 = W1*S1*W1';
[W2,S2,~] = svd(randn(n,n)); noise2 = W2*S2*W2';
P1 = A + 0.5 * noise1;
P2 = A + 0.5 * noise2;

solve_P = @(x) P1\x + P2\x - P2\(A*(P1\x));

b = randn(n,1);
x_true = A\b;
pcg(A,b,1e-6,n);
pcg(A,b,1e-6,n,P1);
x = pcg(A,b,1e-6,n,solve_P);
norm(x_true - x)/norm(x_true)

Hier ist die Ausgabe, die ich bekomme:

pcg converged at iteration 127 to a solution with relative residual 9.9e-07.
pcg converged at iteration 62 to a solution with relative residual 6.8e-07.
pcg converged at iteration 51 to a solution with relative residual 8.1e-07.
relative error= 4.23e-07

---

Beispiel 2: Kombination von Multigrid mit unvollständigem Cholesky zur Lösung der Poisson-Gleichung.

n = 50; N = n^2;
A = gallery('poisson',n); %Laplacian on n-by-n grid, zero dirichlet BC

L = ichol(A);
solve_P1 = @(x) L'\(L\x);
% Combinatorial multigrid: http://www.cs.cmu.edu/~jkoutis/cmg.html
solve_P2 = cmg_sdd(A); 

solve_P = @(x) solve_P1(x) + solve_P2(x) - solve_P1(A*solve_P2(x));

b = randn(N,1);
x_true = A\b;
pcg(A,b,1e-6,N);
pcg(A,b,1e-6,N,solve_P1);
pcg(A,b,1e-6,N,solve_P2);
x = pcg(A,b,1e-6,N,solve_P);
disp(['relative error= ', num2str(norm(x_true - x)/norm(x_true),3)])

Dafür bekomme ich die Ergebnisse:

pcg converged at iteration 131 to a solution with relative residual 8.4e-07.
pcg converged at iteration 44 to a solution with relative residual 6e-07.
pcg converged at iteration 19 to a solution with relative residual 7e-07.
pcg converged at iteration 12 to a solution with relative residual 4.7e-07.
relative error= 5.2e-07

---

Anmerkungen:

• Ich habe auch das gleiche qualitative Verhalten bei Matrizen gesehen, das in komplizierteren / realistischeren Situationen auftritt.
• $Ax=b$$e$$r$$Ae=r$$P_1$$A$$P_2$$A$

Kurz gesagt, die Orthogonalisierung der Krylov-Vektoren erfolgt in Bezug auf den Operator, jedoch nicht in Bezug auf den Vorkonditionierer.

Okay, sagen wir, wir wollen lösen$Ax=b$$B$

$$\begin{align*} \hat{v}_1=\tilde{v}_1 =& Bb\\ v_1 =& \tilde{v}_1 / c_1\\ \\ \hat{v}_i =& BAv_{i-1}\\ \tilde{v}_i=&\hat{v}_i-\sum\limits_{j=1}^{i-1} \langle Av_k,\hat{v}_i\rangle v_k\\ v_i =& \tilde{v}_i/c_i\\ c_i =& \sqrt{\langle \tilde{v}_i,\tilde{v}_i\rangle} \end{align*}$$

• $\hat{v}_i$
• $\tilde{v}_i$
• $v_i$

Das Interessante daran ist, dass wir eine Reihe von Eigenschaften erhalten. Die beiden, die für Sie wirklich wichtig sind, sind

1. $\textrm{span}\{v_i\}_{i=1}^m = \textrm{span}\{(BA)^{i-1}(Bb)\}_{i=1}^m$
2. $V^TAV = I$

$\hat{v}_i$$BAv_{i-1}$$v_1$$Bb$$\tilde{v}_i$$B$$A$

Angenommen, wir möchten das System lösen$Ax=b$$x$$\beta$

$$AV\beta = b$$ $$V^TAV\beta = V^Tb$$ $V^TAV=I$ $$\beta = V^Tb$$ $$x = VV^Tb.$$ $B$$A$$B$$B$$A$$B$

Verlieren wir etwas mit einer unsymmetrischen $B$$\langle Br_i,r_j\rangle = 0$$i\neq j$$\langle BAv_i,Av_j\rangle=0$$|i-j|\geq 2$$B$

$B$$B$

Lesen Sie http://www.sciencedirect.com/science/article/pii/S1877050915010492 "Unsymmetrische Vorkonditionierung für konjugierte Gradienten- und steilste Abstiegsmethoden"