A convergência de solucionadores iterativos clássicos para sistemas lineares é determinada pelo raio espectral da matriz de iteração, . Para um sistema linear geral, é difícil determinar um parâmetro SOR ideal (ou até bom) devido à dificuldade em determinar o raio espectral da matriz de iteração. Abaixo, incluí muitos detalhes adicionais, incluindo um exemplo de um problema real em que o peso ideal da SOR é conhecido.ρ(G)
Raio espectral e convergência
O raio espectral é definido como o valor absoluto do maior valor próprio de magnitude. Um método convergirá se e um raio espectral menor significar uma convergência mais rápida. O SOR funciona alterando a divisão da matriz usada para derivar a matriz de iteração com base na escolha de um parâmetro de ponderação ω , diminuindo, esperançosamente, o raio espectral da matriz de iteração resultante.ρ<1ω
Divisão de matriz
Para a discussão abaixo, assumirei que o sistema a ser resolvido é dado por
Ax=b,
com uma iteração do formulário
x(k+1)=v+Gx(k),
onde é um vetor e o número da iteração k é denotado x ( k ) .vkx(k)
O SOR leva uma média ponderada da iteração antiga e uma iteração de Gauss-Seidel. O método Gauss-Seidel se baseia em uma divisão de matriz da forma
A=D+L+U
onde é a diagonal de A , L é uma matriz triangular inferior contendo todos os elementos de A estritamente abaixo da diagonal e R é uma matriz triangular superior contendo todos os elementos de A estritamente acima da diagonal. A iteração de Gauss-Seidel é então dada porDALARA
x(k+1)=(D+L)−1b+GG−Sx(k)
e a matriz de iteração é
GG−S=−(D+L)−1U.
O SOR pode então ser escrito como
x(k+1)=ω(D+ωL)−1b+GSORx(k)
Onde
GSOR=(D+ωL)−1((1−ω)D−ωU).
ω
SOR ideal
Um exemplo realista em que o coeficiente de ponderação ideal é conhecido surge no contexto da resolução de uma equação de Poisson:
∇2u=f in Ωu=g on ∂Ω
A discretização desse sistema em um domínio quadrado em 2D usando diferenças finitas de segunda ordem com espaçamento uniforme de grade resulta em uma matriz simétrica com 4 na diagonal, -1 imediatamente acima e abaixo da diagonal e mais duas bandas de -1 a alguma distância do diagonal. Existem algumas diferenças devido às condições de contorno, mas essa é a estrutura básica. Dada essa matriz, a escolha comprovadamente ótima para o coeficiente SOR é dada por
ω=21+sin(πΔx/L)
ΔxL
Como você pode ver, o SOR atinge a precisão da máquina em cerca de 100 iterações, momento em que Gauss-Seidel é cerca de 25 ordens de magnitude pior. Se você quiser brincar com este exemplo, incluí o código MATLAB que usei abaixo.
clear all
close all
%number of iterations:
niter = 150;
%number of grid points in each direction
N = 16;
% [x y] = ndgrid(linspace(0,1,N),linspace(0,1,N));
[x y] = ndgrid(linspace(-pi,pi,N),linspace(-pi,pi,N));
dx = x(2,1)-x(1,1);
L = x(N,1)-x(1,1);
%desired solution:
U = sin(x/2).*cos(y);
% Right hand side for the Poisson equation (computed from U to produce the
% desired known solution)
Ix = 2:N-1;
Iy = 2:N-1;
f = zeros(size(U));
f(Ix,Iy) = (-4*U(Ix,Iy)+U(Ix-1,Iy)+U(Ix+1,Iy)+U(Ix,Iy-1)+U(Ix,Iy+1));
figure(1)
clf
contourf(x,y,U,50,'linestyle','none')
title('True solution')
%initial guess (must match boundary conditions)
U0 = U;
U0(Ix,Iy) = rand(N-2);
%Gauss-Seidel iteration:
UGS = U0; EGS = zeros(1,niter);
for iter=1:niter
for iy=2:N-1
for ix=2:N-1
UGS(ix,iy) = -1/4*(f(ix,iy)-UGS(ix-1,iy)-UGS(ix+1,iy)-UGS(ix,iy-1)-UGS(ix,iy+1));
end
end
%error:
EGS(iter) = sum(sum((U-UGS).^2))/sum(sum(U.^2));
end
figure(2)
clf
contourf(x,y,UGS,50,'linestyle','none')
title(sprintf('Gauss-Seidel approximate solution, iteration %d', iter))
drawnow
%SOR iteration:
USOR = U0; ESOR = zeros(1,niter);
w = 2/(1+sin(pi*dx/L));
for iter=1:niter
for iy=2:N-1
for ix=2:N-1
USOR(ix,iy) = (1-w)*USOR(ix,iy)-w/4*(f(ix,iy)-USOR(ix-1,iy)-USOR(ix+1,iy)-USOR(ix,iy-1)-USOR(ix,iy+1));
end
end
%error:
ESOR(iter) = sum(sum((U-USOR).^2))/sum(sum(U.^2));
end
figure(4)
clf
contourf(x,y,USOR,50,'linestyle','none')
title(sprintf('Gauss-Seidel approximate solution, iteration %d', iter))
drawnow
figure(5)
clf
semilogy(EGS,'b')
hold on
semilogy(ESOR,'r')
title('L2 relative error')
xlabel('Iteration number')
legend('Gauss-Seidel','SOR','location','southwest')
Esse lado das coisas não é realmente minha especialidade, mas não acho que seja um teste super justo para muitas aplicações realistas.
Não tenho certeza de quais valores você estava usando para c e r , mas suspeito que você estava trabalhando com matrizes extremamente mal condicionadas. (Abaixo está um código Python mostrando que essas podem não ser as matrizes mais invertíveis.)
Se você realmente precisasse inverter matrizes dessa condição, a) usaria um método especializado eb) provavelmente deveria apenas encontrar um novo campo 😉
Para matrizes bem condicionadas de qualquer tamanho, o SOR provavelmente será mais rápido. Para problemas reais em que a velocidade é importante, seria raro usar o SOR - do lado sofisticado, há muito melhor nos dias de hoje; No lado lento, mas confiável, o SOR não é o melhor que você pode fazer.
fonte
OK, então para matrizes simétricas deste rei:
(Isso é apenas observação empírica, nada rigoroso)
fonte