이 페이지의 최신 내용은 아직 번역되지 않았습니다. 최신 내용은 영문으로 볼 수 있습니다.

gmres

일반화된 최소 잔차법(Generalized Minimum Residual Method)(재시작 포함)

구문

x = gmres(A,b)
gmres(A,b,restart)
gmres(A,b,restart,tol)
gmres(A,b,restart,tol,maxit)
gmres(A,b,restart,tol,maxit,M)
gmres(A,b,restart,tol,maxit,M1,M2)
gmres(A,b,restart,tol,maxit,M1,M2,x0)
[x,flag] = gmres(A,b,...)
[x,flag,relres] = gmres(A,b,...)
[x,flag,relres,iter] = gmres(A,b,...)
[x,flag,relres,iter,resvec] = gmres(A,b,...)

설명

x = gmres(A,b)는 선형 연립방정식 A*x = b를 풀어 x를 구합니다. nxn 계수 행렬 A는 크기가 큰 정사각 희소 행렬이어야 합니다. 열 벡터 b는 길이가 n이어야 합니다. A는 함수 핸들 afun일 수 있으며, afun(x)A*x를 반환합니다. 이 구문의 경우 gmres는 다시 시작하지 않습니다. 최대 반복 횟수는 min(n,10)입니다.

함수를 파라미터화하기에는 함수 afun과 아래에서 설명하는 선조건자(Preconditioner) 함수 mfun에 추가 파라미터를 제공하는(필요한 경우) 방법이 설명되어 있습니다.

gmres가 수렴할 경우 해당 효과에 대한 메시지가 표시됩니다. 최대 반복 횟수 이후에도 gmres가 수렴하지 않거나 어떠한 이유로든 중지될 경우 상대 잔차 norm(b-A*x)/norm(b)와, 이 계산이 중지되거나 실패한 반복 횟수가 표시된 경고 메시지가 출력됩니다.

gmres(A,b,restart)restart 내부 반복 시마다 메서드를 다시 시작합니다. 최대 외부 반복 횟수는 min(n/restart,10)입니다. 최대 총 반복 횟수는 restart*min(n/restart,10)입니다. restartn 또는 []인 경우 gmres는 다시 시작하지 않으며, 최대 총 반복 횟수는 min(n,10)입니다.

gmres(A,b,restart,tol)은 계산 방식에 허용오차를 지정하는 데 사용됩니다. tol[]이면 gmres는 디폴트 값인 1e-6을 사용합니다.

gmres(A,b,restart,tol,maxit)은 최대 외부 반복 횟수를 지정합니다. 총 반복 횟수는 restart*maxit을 초과하지 않습니다. maxit[]이면 gmres는 디폴트 값인 min(n/restart,10)을 사용합니다. restartn 또는 []이면 최대 총 반복 횟수는 (restart*maxit이 아닌) maxit입니다.

gmres(A,b,restart,tol,maxit,M)gmres(A,b,restart,tol,maxit,M1,M2)는 선조건자 M 또는 M = M1*M2를 사용하여 시스템 inv(M)*A*x = inv(M)*b에서 효과적으로 x를 구합니다. M[]이면 gmres는 선조건자(Preconditioner)를 적용하지 않습니다. Mmfun(x)M\x를 반환하도록 하는 함수 핸들 mfun일 수 있습니다.

gmres(A,b,restart,tol,maxit,M1,M2,x0)에는 최초의 초기 추측값을 지정할 수 있습니다. x0[]이면 gmres는 디폴트 값(0으로만 이루어진 벡터)을 사용합니다.

[x,flag] = gmres(A,b,...)는 수렴 플래그도 반환합니다.

flag = 0

gmresmaxit 외부 반복 횟수 내에, 기대한 허용오차 tol로 수렴되었습니다.

flag = 1

gmresmaxit의 횟수만큼 반복되었지만 수렴되지 않았습니다.

flag = 2

선조건자 M은 조건이 나쁜 행렬입니다.

flag = 3

gmres가 정체되었습니다. 연속된 2회의 반복이 동일했습니다.

flag0이 아닌 경우 반환되는 해 x는 모든 반복에 걸쳐 계산된 최소 노름(Norm) 잔차를 가집니다. flag 출력값이 지정된 경우에는 메시지가 표시되지 않습니다.

[x,flag,relres] = gmres(A,b,...)는 상대 잔차 norm(b-A*x)/norm(b)도 반환합니다. flag0인 경우 relres <= tol입니다. 세 번째 출력값 relres는 선조건자가 적용된 시스템의 상대 잔차입니다.

[x,flag,relres,iter] = gmres(A,b,...)x가 계산된 시점의 외부 반복 횟수와 내부 반복 횟수도 모두 반환합니다. 여기서 0 <= iter(1) <= maxit이고 0 <= iter(2) <= restart입니다.

[x,flag,relres,iter,resvec] = gmres(A,b,...)는 각 내부 반복 시점에서의 잔차 노름(Residual Norm) 벡터도 반환합니다. 이들은 선조건자가 적용된 시스템에 대한 잔차 노름입니다.

예제

gmres에 행렬 입력값 사용

A = gallery('wilk',21);  
b = sum(A,2);
tol = 1e-12;  
maxit = 15; 
M1 = diag([10:-1:1 1 1:10]);

x = gmres(A,b,10,tol,maxit,M1);

다음 메시지가 표시됩니다.

gmres(10) converged at outer iteration 2 (inner iteration 9) to 
a solution with relative residual 3.3e-013

gmres에 함수 핸들 사용

이 예제에서는 이전 예제의 행렬 A를 행렬, 벡터 간 곱 함수 afun의 핸들로 바꾸고 선조건자(Preconditioner) M1을 backsolve 함수 mfun의 핸들로 바꿉니다. 이 예제는 함수 run_gmres에 포함되어 있으며, 이 함수는 다음과 같이 동작합니다.

  • 첫 번째 인수로 함수 핸들 @afun을 사용하여 gmres를 호출합니다.

  • run_gmres의 모든 변수를 afunmfun에 사용할 수 있도록, afunmfun을 중첩 함수로 포함시킵니다.

아래에는 run_gmres 코드가 나와 있습니다.

function x1 = run_gmres
n = 21;
b = afun(ones(n,1));
tol = 1e-12;  maxit = 15; 
x1 = gmres(@afun,b,10,tol,maxit,@mfun);
 
    function y = afun(x)
        y = [0; x(1:n-1)] + ...
              [((n-1)/2:-1:0)'; (1:(n-1)/2)'].*x + ...
              [x(2:n); 0];
    end
 
    function y = mfun(r)
        y = r ./ [((n-1)/2:-1:1)'; 1; (1:(n-1)/2)'];
    end
end

다음을 입력하면

x1 = run_gmres;

MATLAB®에 다음 메시지가 표시됩니다.

gmres(10) converged at outer iteration 2 (inner iteration 10) 
to a solution with relative residual 1.1e-013.

재시작 없이 선조건자(Preconditioner) 사용

이 예제에서는 gmres를 재시작하지 않고 선조건자를 사용하는 방법을 보여줍니다.

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

load west0479;
A = west0479;

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

tol = 1e-12;
maxit = 20;

참(True) 해가 1로만 이루어진 벡터가 되도록 b를 정의합니다.

b = full(sum(A,2));
[x0,fl0,rr0,it0,rv0] = gmres(A,b,[],tol,maxit);

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

gmres의 동작을 플로팅합니다.

semilogy(0:maxit,rv0/norm(b),'-o');
xlabel('Iteration number');
ylabel('Relative residual');

이 플롯을 통해 해가 천천히 수렴됨을 알 수 있습니다. 선조건자(Preconditioner)가 결과를 개선시킬 수 있습니다.

A는 비대칭이므로 선조건자를 구성하기 위해 ilu를 사용합니다.

[L,U] = ilu(A,struct('type','ilutp','droptol',1e-5));
Error using ilu
There is a pivot equal to zero. Consider decreasing 
the drop tolerance or consider using the 'udiag' option.

참고로, MATLAB에서 불완전 LU를 생성할 경우 선조건자(Preconditioner)로 사용할 수 없는 특이 인자가 발생하기 때문에 불완전 LU를 생성할 수 없습니다.

오류 메시지에 표시된대로 기각 허용오차를 줄여서 다시 시도합니다.

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

gmres가 상대 잔차를 9.5436e-14(rr1의 값)으로 유도하므로 fl1은 0이 됩니다. 기각 허용오차가 1e-6인 불완전 LU 분해 선조건을 적용하면 6번째 반복(it1(2)의 값)에서 상대 잔차는 미리 정해진 허용오차 1e-12보다 작아집니다. 출력 인수 rv1(1)norm(M\b)입니다. 여기서 M = L*U입니다. 출력 인수 rv1(7)norm(U\(L\(b-A*x1)))입니다.

초기 추정값(반복 횟수 0)부터 각 반복마다 상대 잔차를 플로팅하면 gmres의 진행률을 추적할 수 있습니다.

semilogy(0:it1(2),rv1/norm(b),'-o');
xlabel('Iteration number');
ylabel('Relative residual');

재시작과 함께 선조건자(Preconditioner) 사용

이 예제에서는 gmres 재시작과 함께 선조건자(Preconditioner)를 사용하는 방법을 보여줍니다.

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

load west0479;
A = west0479;

참(True) 해가 1로만 이루어진 벡터가 되도록 b를 정의합니다.

b = full(sum(A,2));

이전 예제에서와 같이 불완전 LU 선조건자(Preconditioner)를 생성합니다.

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

재시작된 gmres를 사용하는 이점은 메서드를 실행하는 데 필요한 메모리의 양을 제한할 수 있다는 점입니다. 재시작이 없으면 gmres는 크릴로프(Krylov) 부분공간의 기저를 유지하는 데 maxit 벡터의 저장 공간을 요구하게 됩니다. gmres는 각 단계에서 모든 이전 벡터와 직교해야 합니다. 재시작은 외부 반복당 사용되는 작업 공간의 양과 작업의 양을 제한합니다. 참고로, 위에서 선조건자가 적용된 gmres가 6회 반복에서 수렴된다 하더라도 알고리즘이 20개의 기저 벡터를 허용하기 때문에 그 공간이 모두 할당됩니다.

gmres(3), gmres(4)gmres(5)를 실행합니다

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

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

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

figure
semilogy(1:1/3:6,rv3/norm(b),'-o');
h1 = gca;
h1.XTick = [1:1/3:6];
h1.XTickLabel = ['1';' ';' ';'2';' ';' ';'3';' ';' ';'4';' ';' ';'5';' ';' ';'6';];
title('gmres(3)')
xlabel('Iteration number');
ylabel('Relative residual');

figure
semilogy(1:1/4:3,rv4/norm(b),'-o');
h2 = gca;
h2.XTick = [1:1/4:3];
h2.XTickLabel = ['1';' ';' ';' ';'2';' ';' ';' ';'3'];
title('gmres(4)')
xlabel('Iteration number');
ylabel('Relative residual');

figure
semilogy(1:1/5:2.8,rv5/norm(b),'-o');
h3 = gca;
h3.XTick = [1:1/5:2.8];
h3.XTickLabel = ['1';' ';' ';' ';' ';'2';' ';' ';' ';' '];
title('gmres(5)')
xlabel('Iteration number');
ylabel('Relative residual');

참고 문헌

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

Saad, Youcef 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 이전에 개발됨