Main Content

gmres

선형 연립방정식 풀기 — 일반화된 최소 잔차법(Generalized Minimum Residual Method)

설명

예제

x = gmres(A,b)일반화된 최소 잔차법(Generalized Minimum Residual Method) 방법을 사용하여 x에 대한 선형 연립방정식 A*x = b를 풉니다. 시도가 성공한 경우 gmres는 수렴을 확인하는 메시지를 표시합니다. 최대 반복 횟수 이후에도 gmres가 수렴하지 않거나 어떠한 이유로든 중단될 경우 상대 잔차 norm(b-A*x)/norm(b)와, 이 계산이 중지된 반복 횟수가 포함된 진단 메시지가 표시됩니다. 이 구문의 경우 gmres는 다시 시작하지 않습니다. 최대 반복 횟수는 min(size(A,1),10)입니다.

예제

x = gmres(A,b,restart)restart회의 내부 반복 시마다 메서드를 다시 시작합니다. 최대 외부 반복 횟수는 outer = min(size(A,1)/restart,10)입니다. gmres가 각 외부 반복에 대해 restart회의 내부 반복을 수행하므로 최대 총 반복 횟수는 restart*outer입니다. restartsize(A,1) 또는 []인 경우 gmres는 다시 시작하지 않으며, 최대 총 반복 횟수는 min(size(A,1),10)입니다.

예제

x = gmres(A,b,restart,tol)은 이 방법의 허용오차를 지정합니다. 디폴트 허용오차는 1e-6입니다.

예제

x = gmres(A,b,restart,tol,maxit)는 총 반복 횟수가 restart*maxit를 초과하지 않도록 최대 외부 반복 횟수를 지정합니다. maxit[]이면 gmres는 디폴트 값인 min(size(A,1)/restart,10)을 사용합니다. restartsize(A,1) 또는 []이면 최대 총 반복 횟수는 restart*maxit가 아닌 maxit입니다. 최대 총 반복 횟수 내에서 수렴하지 않을 경우 gmres는 진단 메시지를 표시합니다.

예제

x = gmres(A,b,restart,tol,maxit,M)은 선조건자 행렬 M을 지정하고 시스템 M1Ax=M1b를 풀어 x를 계산합니다. 선조건자 행렬을 사용하면 문제의 수치적 속성과 계산 효율성을 개선할 수 있습니다.

예제

x = gmres(A,b,restart,tol,maxit,M1,M2)M = M1*M2가 되도록 선조건자 행렬 M의 인수를 지정합니다.

예제

x = gmres(A,b,restart,tol,maxit,M1,M2,x0)은 해 벡터 x에 대한 초기 추측값을 지정합니다. 디폴트 값은 0으로 구성된 벡터입니다.

예제

[x,flag] = gmres(___)는 알고리즘이 성공적으로 수렴하는지 여부를 지정하는 플래그를 반환합니다. flag = 0이면 수렴이 성공한 것입니다. 이 출력 구문은 위에 열거된 구문에 나와 있는 입력 인수를 원하는 대로 조합하여 사용할 수 있습니다. flag 출력값을 지정할 경우 gmres는 진단 메시지를 표시하지 않습니다.

예제

[x,flag,relres] = gmres(___)는 선조건자 행렬 M을 포함하는 상대 잔차 norm(M\(b-A*x))/norm(M\b)도 반환합니다. flag0이면 relres <= tol입니다.

예제

[x,flag,relres,iter] = gmres(___)x가 계산된 내부 반복 횟수와 내부 반복 횟수를 벡터 [outer inner]로 반환합니다. 외부 반복 횟수는 범위 0 <= iter(1) <= maxit 내에 있고 내부 반복 횟수는 범위 0 <= iter(2) <= restart 내에 있습니다.

예제

[x,flag,relres,iter,resvec] = gmres(___)는 첫 번째 잔차 norm(M\(b-A*x0))을 포함하여 각 내부 반복에서 잔차 노름으로 구성된 벡터도 반환합니다. 이들은 선조건자가 적용된 시스템에 대한 잔차 노름입니다.

예제

모두 축소

디폴트 설정으로 gmres를 사용하여 정사각 선형 시스템을 풀고 풀이 과정에 사용된 허용오차 및 반복 횟수를 조정합니다.

50%의 밀도를 갖고 주대각선에 0이 아닌 값을 갖는 희소 형식의 확률 행렬 A를 만듭니다. Ax=b의 우변에 해당하는 확률 벡터 b도 만듭니다.

rng default
A = sprandn(400,400,0.5) + 12*speye(400);
b = rand(400,1);

gmres를 사용하여 Ax=b를 풉니다. 출력 표시에는 상대 잔차 오차 b-Axb의 값이 포함됩니다.

x = gmres(A,b);
gmres stopped at iteration 10 without converging to the desired tolerance 1e-06
because the maximum number of iterations was reached.
The iterate returned (number 10) has relative residual 0.35.

기본적으로 gmres는 10회 반복과 1e-6의 허용오차를 사용하는데 이 알고리즘으로는 이 행렬에 대해 10회의 반복 내에 수렴할 수 없습니다. 잔차는 아직 큽니다. 이는 더 많은 반복(또는 선조건자 행렬)이 필요함을 알려줍니다. 알고리즘이 쉽게 수렴할 수 있도록 큰 허용오차를 사용할 수도 있습니다.

1e-4의 허용오차와 100회의 반복으로 시스템을 다시 풉니다.

tol = 1e-4;
maxit = 100;
x = gmres(A,b,[],tol,maxit);
gmres stopped at iteration 100 without converging to the desired tolerance 0.0001
because the maximum number of iterations was reached.
The iterate returned (number 100) has relative residual 0.0045.

허용오차가 더 느슨해지고 반복 횟수가 늘어나도 수렴을 위해 잔차 오차가 충분히 개선되지 않았습니다. 반복 알고리즘이 이런 식으로 정체 상태에 빠진다는 것은 선조건자 행렬이 필요하다는 의미입니다. 하지만 gmres에는 내부 반복 횟수를 제어하는 입력값도 있습니다. gmres는 내부 반복에 값을 지정함으로써 외부 반복 1회당 더 많은 작업을 처리합니다.

restart 값 100과 maxit 값 20으로 시스템을 다시 풉니다. gmres는 100회의 반복을 한 번 수행하는 대신 다음번 재시작 전까지 100회의 반복을 수행하는 작업을 20번 반복합니다.

restart = 100;
maxit = 20;
x = gmres(A,b,restart,tol,maxit);
gmres(100) converged at outer iteration 2 (inner iteration 75) to a solution with relative residual 9.3e-05.

이 예제에서는 gmres에 큰 재시작 값을 지정한 결과 허용된 반복 횟수 내에 하나의 해로 수렴할 수 있습니다. 그러나 A 또한 클 경우에는 재시작 값이 크면 메모리를 많이 사용할 수 있습니다.

재시작되지 않는 gmres에 선조건자 행렬을 사용하여 선형 시스템을 푸는 효과를 검토합니다.

479×479 실수 비대칭 희소 행렬인 west0479를 불러옵니다.

load west0479
A = west0479;

Ax=b의 참(True) 해가 1로만 구성된 벡터가 되도록 b를 정의합니다.

b = sum(A,2);

허용오차와 최대 반복 횟수를 설정합니다.

tol = 1e-12;
maxit = 20;

gmres를 사용하여 요청된 허용오차와 반복 횟수로 해를 구합니다. 풀이 과정에 대한 정보를 반환하는 5개의 출력값을 지정합니다.

  • xA*x = b의 계산된 해입니다.

  • fl0은 알고리즘의 수렴 여부를 나타내는 플래그입니다.

  • rr0은 계산된 답 x의 상대 잔차입니다.

  • it0x이 계산된 내부 반복 횟수와 외부 반복 횟수를 나타내는 요소를 2개 가진 벡터 [outer inner]입니다.

  • rv0b-Ax의 잔차 내역으로 구성된 벡터입니다.

[x,fl0,rr0,it0,rv0] = gmres(A,b,[],tol,maxit);
fl0
fl0 = 1
rr0
rr0 = 0.7603
it0
it0 = 1×2

     1    20

gmres가 요청된 반복 횟수인 20회 이내에 요청된 허용오차 1e-12으로 수렴하지 않으므로 fl0은 1이 됩니다. gmres가 반환하는 최적 근사해(Approximate Solution)는 (it0(2) = 20 참조) 마지막 해입니다. MATLAB®은 잔차 내역을 rv0에 저장합니다.

이러한 느린 수렴을 개선할 수 있도록 선조건자 행렬을 지정할 수 있습니다. A는 비대칭 행렬이므로 ilu를 사용하여 선조건자 M=L U를 생성합니다. 대각선상에 있지 않으면서 값이 1e-6보다 작은 요소는 무시하도록 기각 허용오차를 지정합니다. LUgmres에 대한 입력값으로 지정하여 선조건이 적용된 시스템 M-1A x=M-1b를 풉니다. 선조건자를 지정하면 gmres는 출력값 rr1rv1에 대해 선조건이 적용된 시스템의 잔차 노름을 계산합니다.

[L,U] = ilu(A,struct('type','ilutp','droptol',1e-6));
[x1,fl1,rr1,it1,rv1] = gmres(A,b,[],tol,maxit,L,U);
fl1
fl1 = 0
rr1
rr1 = 1.1870e-13
it1
it1 = 1×2

     1     6

ilu 선조건자를 사용한 결과 6번째 반복에서 미리 정해진 허용오차 1e-12보다 작은 상대 잔차가 생성됩니다. 첫 번째 잔차 rv1(1)norm(U\(L\b))으로, 여기서 M = L*U입니다. 마지막 잔차 rv1(end)norm(U\(L\(b-A*x1)))입니다.

각 반복마다 상대 잔차를 플로팅하면 gmres의 진행률을 추적할 수 있습니다. 각 해의 잔차 내역을 플로팅하고, 지정된 허용오차에 대한 선을 추가합니다.

semilogy(0:length(rv0)-1,rv0/norm(b),'-o')
hold on
semilogy(0:length(rv1)-1,rv1/norm(U\(L\b)),'-o')
yline(tol,'r--');
legend('No preconditioner','ILU preconditioner','Tolerance','Location','East')
xlabel('Iteration number')
ylabel('Relative residual')

Figure contains an axes object. The axes object with xlabel Iteration number, ylabel Relative residual contains 3 objects of type line, constantline. These objects represent No preconditioner, ILU preconditioner, Tolerance.

재시작된 gmres에 선조건자를 사용합니다.

479×479 실수 비대칭 희소 행렬인 west0479를 불러옵니다.

load west0479
A = west0479;

Ax=b의 참(True) 해가 1로만 구성된 벡터가 되도록 b를 정의합니다.

b = sum(A,2);

기각 허용오차 1e-6으로 불완전 LU 선조건자를 구성합니다.

[L,U] = ilu(A,struct('type','ilutp','droptol',1e-6));

재시작된 gmres를 사용하는 이점은 메서드를 실행하는 데 필요한 메모리의 양을 제한할 수 있다는 점입니다. 재시작이 없으면 gmres는 크릴로프(Krylov) 부분공간의 기저를 유지하는 데 maxit 벡터의 저장 공간을 요구하게 됩니다. gmres는 각 단계에서 모든 이전 벡터와 직교해야 합니다. 재시작은 외부 반복당 사용되는 작업 공간의 양과 작업의 양을 제한합니다.

불완전 LU 인수를 선조건자로 사용하여 gmres(3), gmres(4), gmres(5)를 실행합니다. 1e-12의 허용오차와 20회의 최대 외부 반복을 사용합니다.

tol = 1e-12;
maxit = 20;
[x3,fl3,rr3,it3,rv3] = gmres(A,b,3,tol,maxit,L,U);
[x4,fl4,rr4,it4,rv4] = gmres(A,b,4,tol,maxit,L,U);
[x5,fl5,rr5,it5,rv5] = gmres(A,b,5,tol,maxit,L,U);
fl3
fl3 = 0
fl4
fl4 = 0
fl5
fl5 = 0

재시작된 각 경우에서 gmres가 상대 잔차를 1e-12의 미리 정해진 허용오차 미만으로 유도하기 때문에 fl3, fl4fl5는 모두 0입니다.

다음 플롯은 재시작된 각 gmres 메서드의 수렴 내역을 보여줍니다. gmres(3)은 외부 반복 5, 내부 반복 3에서 수렴합니다(it3 = [5, 3]). 이것은 외부 반복 6, 내부 반복 0과 같기 때문에 최종 눈금 6에 표시됩니다.

semilogy(1:1/3:6,rv3/norm(U\(L\b)),'-o');
h1 = gca;
h1.XTick = (1:6);
title('gmres(N) for N = 3, 4, 5')
xlabel('Outer iteration number');
ylabel('Relative residual');
hold on
semilogy(1:1/4:3,rv4/norm(U\(L\b)),'-o');
semilogy(1:1/5:2.8,rv5/norm(U\(L\b)),'-o');
yline(tol,'r--');
hold off
legend('gmres(3)','gmres(4)','gmres(5)','Tolerance')
grid on

Figure contains an axes object. The axes object with title gmres(N) for N = 3, 4, 5, xlabel Outer iteration number, ylabel Relative residual contains 4 objects of type line, constantline. These objects represent gmres(3), gmres(4), gmres(5), Tolerance.

일반적으로 내부 반복 횟수가 클수록 gmres가 외부 반복 한 번당 수행하는 작업이 많아지고 그에 따라 더 빨리 수렴합니다.

gmres에 해의 초기 추측값을 제공하는 효과를 검토합니다.

삼중대각 희소 행렬을 만듭니다. x의 예상 해가 1로 구성된 벡터가 되도록 각 행의 합을 Ax=b의 우변에 대한 벡터로 사용합니다.

n = 900;
e = ones(n,1);
A = spdiags([e 2*e e],-1:1,n,n);
b = sum(A,2);

gmres를 사용하여 Ax=b를 두 번 풉니다. 한 번은 디폴트 초기 추측값을 사용하여 풀고, 다른 한 번은 해에 대한 양호한 초기 추측값을 사용하여 풉니다. 두 해 모두에 200회의 반복과 디폴트 허용오차를 사용합니다. 모든 요소가 0.99로 이루어진 벡터로 두 번째 해의 초기 추측값을 지정합니다.

maxit = 200;
x1 = gmres(A,b,[],[],maxit);
gmres converged at iteration 27 to a solution with relative residual 9.5e-07.
x0 = 0.99*e;
x2 = gmres(A,b,[],[],maxit,[],[],x0);
gmres converged at iteration 7 to a solution with relative residual 6.7e-07.

이 예제에서는 초기 추측값을 제공한 결과 gmres가 더 빨리 수렴되었습니다.

중간 결과 반환하기

for 루프에서 gmres를 호출하여 중간 결과를 얻는 데도 초기 추측값을 사용할 수 있습니다. 솔버에 대한 각 호출은 몇 회의 반복을 수행한 후 계산된 해를 저장합니다. 그런 다음 저장된 해를 다음 반복 배치의 초기 벡터로 사용합니다.

예를 들어, 다음 코드는 100회의 반복을 4번 수행하며, for 루프를 통과한 후 매번 해 벡터를 저장합니다.

x0 = zeros(size(A,2),1);
tol = 1e-8;
maxit = 100;
for k = 1:4
    [x,flag,relres] = gmres(A,b,[],tol,maxit,[],[],x0);
    X(:,k) = x;
    R(k) = relres;
    x0 = x;
end

X(:,k)는 for 루프의 반복 k회에서 계산된 해 벡터이고, R(k)는 이 해의 상대 잔차입니다.

gmres에 계수 행렬 A 대신 A*x를 계산하는 함수 핸들을 제공하여 선형 시스템을 풉니다.

gallery에 의해 생성되는 윌킨슨 테스트 행렬 중 하나는 21×21 삼중대각 행렬입니다. 행렬을 미리 봅니다.

A = gallery('wilk',21)
A = 21×21

    10     1     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     1     9     1     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     1     8     1     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     1     7     1     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     1     6     1     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     1     5     1     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     1     4     1     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     1     3     1     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     1     2     1     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     1     1     1     0     0     0     0     0     0     0     0     0     0
      ⋮

윌킨슨 행렬은 특수한 구조를 갖고 있으므로 연산 A*x를 함수 핸들로 나타낼 수 있습니다. A에 벡터를 곱할 때 결과 벡터의 대부분의 요소는 0입니다. 결과에 있는 0이 아닌 요소는 A의 0이 아닌 삼중대각선 요소에 해당합니다. 또한 주대각선에만 0과 1이 아닌 요소가 있습니다.

표현식 Ax는 다음과 같이 표현됩니다.

Ax=[1010001910001810017100161001510014100130001000110][x1x2x3x4x5x21]=[10x1+x2x1+9x2+x3x2+8x3+x4x19+9x20+x21x20+10x21].

결과 벡터는 다음과 같이 세 벡터의 합으로 작성할 수 있습니다.

Ax=[0+10x1+x2x1+9x2+x3x2+8x3+x4x19+9x20+x21x20+10x21+0]=[0x1x20]+[10x19x210x21]+[x2x210].

MATLAB®에서 이러한 벡터를 만들어서 더하여 A*x의 값을 제공하는 함수를 작성합니다.

function y = afun(x)
y = [0; x(1:20)] + ...
    [(10:-1:0)'; (1:10)'].*x + ...
    [x(2:21); 0];
end

(이 함수는 예제 끝에 로컬 함수로 저장되어 있습니다.)

이제 A*x를 계산하는 함수 핸들을 gmres에 제공하여 선형 시스템 Ax=b를 풉니다. 1e-12의 허용오차와 15회의 외부 반복, 재시작 전 10회의 내부 반복을 사용합니다.

b = ones(21,1);
tol = 1e-12;  
maxit = 15;
restart = 10;
x1 = gmres(@afun,b,restart,tol,maxit)
gmres(10) converged at outer iteration 5 (inner iteration 10) to a solution with relative residual 5.3e-13.
x1 = 21×1

    0.0910
    0.0899
    0.0999
    0.1109
    0.1241
    0.1443
    0.1544
    0.2383
    0.1309
    0.5000
      ⋮

afun(x1)이 1로 구성된 벡터를 생성하는지 확인합니다.

afun(x1)
ans = 21×1

    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
      ⋮

로컬 함수(Local Function)

function y = afun(x)
y = [0; x(1:20)] + ...
    [(10:-1:0)'; (1:10)'].*x + ...
    [x(2:21); 0];
end

입력 인수

모두 축소

계수 행렬로, 정사각 행렬 또는 함수 핸들로 지정됩니다. 이 행렬은 선형 시스템 A*x = b의 계수 행렬입니다. 일반적으로 A는 큰 희소 행렬이거나 큰 희소 행렬과 열 벡터의 곱을 반환하는 함수 핸들입니다.

A를 함수 핸들로 지정

선택적으로 계수 행렬을 행렬이 아닌 함수 핸들로 지정할 수도 있습니다. 함수 핸들은 전체 계수 행렬을 구성하는 대신 행렬-벡터 곱을 반환하여 계산을 보다 효율적으로 만듭니다.

함수 핸들을 사용하려면 함수 시그니처 function y = afun(x)를 사용하십시오. 함수를 파라미터화하기에서는 필요한 경우 함수 afun에 추가 파라미터를 제공하는 방법을 설명합니다. 함수 호출 afun(x)A*x의 값을 반환해야 합니다.

데이터형: double | function_handle
복소수 지원 여부:

선형 방정식의 우변으로, 열 벡터로 지정됩니다. b의 길이는 size(A,1)이어야 합니다.

데이터형: double
복소수 지원 여부:

재시작 전의 내부 반복 횟수로, 스칼라 정수로 지정됩니다. 이 입력값을 maxit 입력값과 함께 사용하여 최대 반복 횟수 restart*maxit를 제어할 수 있습니다. restart[] 또는 size(A,1)인 경우 gmres는 다시 시작하지 않으며, 총 반복 횟수는 maxit입니다.

restart 값이 크면 일반적으로 수렴 동작이 우수해지나 시간 및 메모리 요구 사항도 높아집니다.

데이터형: double

방법에 대한 허용오차로, 양의 스칼라로 지정됩니다. 이 입력값을 사용하여 계산에서 정확도와 런타임 간의 상호 절충 관계를 조정할 수 있습니다. gmres 함수가 성공하려면 허용된 반복 횟수 내에서 허용오차를 충족해야 합니다. tol 값이 작을수록 계산을 완료하려면 답이 더 정밀해야 합니다.

데이터형: double

최대 외부 반복 횟수로, 양의 정수 스칼라로 지정됩니다. gmres 함수가 더 많은 반복을 거쳐 허용오차 tol을 충족할 수 있도록 하려면 maxit의 값을 늘리십시오. 일반적으로 tol의 값이 작을수록 계산을 완료하려면 더 많은 반복이 필요합니다.

restart 입력값도 지정된 경우 총 반복 횟수는 restart*maxit입니다. 그러지 않은 경우 총 반복 횟수는 maxit입니다.

maxit의 디폴트 값은 restart가 지정되었는지 여부에 따라 달라집니다.

  • restart가 지정되지 않았거나 [] 또는 size(A,1)로 지정된 경우, maxit의 디폴트 값은 min(size(A,1),10)입니다.

  • restart가 범위 1 <= restart < size(A,1) 내의 값으로 지정된 경우, maxit의 디폴트 값은 min(ceil(size(A,1)/restart),10)입니다.

데이터형: double

선조건자 행렬로, 행렬 또는 함수 핸들의 개별 인수로 지정됩니다. 선조건자 행렬 M 또는 그 행렬 계수 M = M1*M2를 지정하여 선형 시스템의 수치적 특성을 개선하고 gmres 함수가 빠르게 수렴하도록 할 수 있습니다. 불완전 행렬 분해 함수 iluichol을 사용하여 선조건자 행렬을 생성할 수 있습니다. 분해 전에 equilibrate를 사용하여 계수 행렬의 조건수를 개선할 수도 있습니다. 선조건자에 대한 자세한 내용은 선형 시스템을 위한 반복법 항목을 참조하십시오.

gmres 함수는 지정되지 않은 선조건자를 단위 행렬로 처리합니다.

M을 함수 핸들로 지정

선택적으로 M, M1 또는 M2를 행렬이 아닌 함수 핸들로 지정할 수도 있습니다. 함수 핸들은 전체 선조건자 행렬을 구성하는 대신 함수-벡터 연산을 수행하여 계산을 보다 효율적으로 만듭니다.

함수 핸들을 사용하려면 함수 시그니처 function y = mfun(x)를 사용하십시오. 함수를 파라미터화하기에서는 필요한 경우 함수 mfun에 추가 파라미터를 제공하는 방법을 설명합니다. 함수 호출 mfun(x)M\x 또는 M2\(M1\x)의 값을 반환해야 합니다.

데이터형: double | function_handle
복소수 지원 여부:

초기 추측값으로, 길이가 size(A,2)인 열 벡터로 지정됩니다. gmres에 디폴트 값인 0으로 구성된 벡터보다 더 합리적인 초기 추측값 x0을 제공할 수 있는 경우 이 초기 추측값은 계산 시간을 절약하고 알고리즘이 더 빨리 수렴하도록 할 수 있습니다.

데이터형: double
복소수 지원 여부:

출력 인수

모두 축소

선형 시스템 해로, 열 벡터로 반환됩니다. 이 출력값은 선형 시스템 A*x = b에 대한 근사해를 제공합니다. 계산이 성공한 경우(flag = 0), relrestol보다 작거나 같습니다.

계산이 성공하지 않으면(flag ~= 0), gmres 함수가 반환하는 해 x는 모든 반복에 대해 최소 잔차 노름이 계산된 해입니다.

수렴 플래그로, 다음 표에 있는 스칼라 값 중 하나로 반환됩니다. 수렴 플래그는 계산의 성공 여부를 나타내며 여러 가지 형태의 실패를 구분합니다.

플래그 값

수렴

0

성공 — gmres 함수가 maxit 반복 횟수 내에, 기대한 허용오차 tol로 수렴되었습니다.

1

실패 — gmres 함수가 maxit회만큼 반복되었지만 수렴되지 않았습니다.

2

실패 — 선조건자 행렬 M 또는 M = M1*M2의 조건이 나쁩니다.

3

실패 — 연속된 2회의 반복이 동일한 결과를 반환한 후 gmres 함수가 정체되었습니다.

4

실패 — gmres 알고리즘으로 계산된 스칼라 수량 중 하나가 너무 작아지거나 커져 계산을 계속할 수 없습니다.

상대 잔차 오차로, 스칼라로 반환됩니다. 상대 잔차 오차 relres = norm(M\(b-A*x))/norm(M\b)는 답의 정확도를 나타냅니다. gmres는 상대 잔차 계산에 선조건자 행렬 M을 포함하는 반면 대부분의 다른 반복 솔버는 선조건자 행렬을 포함하지 않습니다. 계산이 maxit회의 반복 내에서 허용오차 tol로 수렴하면 relres <= tol입니다.

데이터형: double

외부 및 내부 반복 횟수로, 요소를 2개 가진 벡터 [outer inner]로 반환됩니다. 이 출력값은 x의 계산된 답이 계산된 내부 및 외부 반복 횟수를 나타냅니다.

  • restart가 지정되지 않았거나 [] 또는 size(A,1)로 지정된 경우, outer = 1이고 모든 반복은 내부 반복으로 간주됩니다.

  • restart가 범위 1 <= restart < size(A,1) 내에 있는 값으로 지정된 경우, 외부 반복 횟수는 범위 0 <= outer <= maxit 내에 있고 내부 반복 횟수는 범위 0 <= inner <= restart 내에 있습니다.

데이터형: double

잔차 오차로, 벡터로 반환됩니다. 잔차 오차 norm(M\(b-A*x))는 알고리즘이 주어진 x의 값에 얼마나 가깝게 수렴하는지를 나타냅니다. gmres는 상대 잔차 계산에 선조건자 행렬 M을 포함하는 반면 대부분의 다른 반복 솔버는 선조건자 행렬을 포함하지 않습니다. resvec 내 요소 개수는 총 반복 횟수와 동일합니다(restart가 사용된 경우, 이 값은 최대 restart*maxit입니다). resvec의 내용을 검사하여 restart, tol 또는 maxit의 값을 변경할지 여부를 결정할 수 있습니다.

데이터형: double

세부 정보

모두 축소

일반화된 최소 잔차법(Generalized Minimum Residual Method)

일반화된 최소 잔차(GMRES) 알고리즘은 최소 잔차(MINRES) 알고리즘을 비대칭 행렬로 확대하기 위해 개발되었습니다.

GMRES 알고리즘은 켤레 기울기(CG) 방법과 마찬가지로 직교 시퀀스를 계산하지만, GMRES의 경우 시퀀스에 모든 이전 벡터를 저장해야 합니다. 별다른 조치 없이 이전 벡터를 저장하도록 두면 많은 메모리가 사용될 수 있습니다. 이 알고리즘의 "재시작된" 버전은 주기적으로 중간 시퀀스를 지우고 결과값을 다른 반복의 초기값으로 사용함으로써 이러한 시퀀스의 저장을 제어합니다.

적절한 "재시작" 값을 선택하는 것은 우수한 성능을 위해 반드시 필요하지만, 이러한 값을 선택하려면 무엇보다도 경험이 필요합니다. 재시작 전 반복 횟수가 너무 적으면 알고리즘이 너무 느리게 수렴하거나 아예 수렴하지 않을 수 있습니다. 그러나 재시작 값이 너무 크면 알고리즘의 저장공간 요구 사항이 늘어나 불필요한 작업을 하게 될 수 있습니다[1].

내부 및 외부 반복

내부 반복gmres가 재시작 전에 완료하는 반복입니다. 내부 반복 횟수는 restart 인수로 지정할 수 있습니다.

gmres가 재시작될 때마다 외부 반복 횟수가 늘어납니다. 최대 외부 반복 횟수는 maxit 인수로 지정할 수 있습니다. 디폴트 외부 반복의 횟수는 min(size(A,1)/restart,10)입니다.

예를 들어, restart를 지정하지 않으면 최대 반복 횟수는 maxit의 값으로 결정되고 gmres가 다시 재시작되지 않습니다.

If the restart argument is not specified and the value of maxit is 4, then gmres performs a total of 4 iterations.

그러나 restart를 지정하면 gmres 함수가 (maxit로 지정되는) 외부 반복마다 (restart로 지정되는) 여러 차례의 내부 반복을 수행합니다. 이 경우 최대 총 반복 횟수는 restart*maxit입니다.

If the restart argument is specified as 4, and the maxit argument is specified as 2, then gmres performs 4 inner iterations for each outer iteration for a total of 8 iterations.

  • 대부분의 반복법의 수렴 여부는 계수 행렬의 조건수 cond(A)에 따라 결정됩니다. A가 정사각 행렬인 경우 equilibrate를 사용하여 이 행렬의 조건수를 개선할 수 있으며, 이로 인해 대부분의 반복 솔버의 수렴이 보다 쉬워집니다. equilibrate를 사용하면 이후 equilibrate가 적용된 행렬 B = R*P*A*C를 분해할 때 더 나은 품질의 선조건자 행렬을 만들 수도 있습니다.

  • 계수 행렬을 인수 분해할 때 dissectsymrcm과 같은 행렬 재정렬 함수를 사용하여 계수 행렬의 행과 열을 치환하고 0이 아닌 요소의 개수를 최소화하여 선조건자를 생성할 수 있습니다. 이렇게 하면 이후 선조건이 적용된 선형 시스템을 푸는 데 필요한 메모리와 시간을 절약할 수 있습니다.

참고 문헌

[1] Barrett, R., M. Berry, T. F. Chan, et al., Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, SIAM, Philadelphia, 1994.

[2] Saad, Yousef and Martin H. Schultz, “GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems,” SIAM J. Sci. Stat. Comput., July 1986, Vol. 7, No. 3, pp. 856-869.

확장 기능

버전 내역

R2006a 이전에 개발됨

참고 항목

| | | | | |