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

cgs

켤레 기울기 제곱법(Conjugate Gradients Squared Method)

구문

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

설명

x = cgs(A,b)는 선형 연립방정식 A*x = b를 풀어 x를 구합니다. nxn 계수 행렬 A는 크기가 큰 정사각 희소 행렬이어야 합니다. 열 벡터 b는 길이가 n이어야 합니다. A를 함수 핸들 afun으로 지정하여 afun(x)A*x를 반환하도록 할 수 있습니다.

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

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

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

cgs(A,b,tol,maxit)는 최대 반복 횟수 maxit를 지정합니다. maxit[]이면 cgs는 디폴트 값인 min(n,20)을 사용합니다.

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

cgs(A,b,tol,maxit,M1,M2,x0)은 초기 추측값 x0을 지정합니다. x0[]이면 cgs는 디폴트 값(0으로만 이루어진 벡터)을 사용합니다.

[x,flag] = cgs(A,b,...)cgs의 수렴을 설명하는 해 x와 플래그를 반환합니다.

플래그(flag)

수렴

0

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

1

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

2

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

3

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

4

cgs를 실행하는 동안 계산된 스칼라 수량 중 하나가 너무 작아지거나 커져 계산을 계속할 수 없습니다.

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

[x,flag,relres] = cgs(A,b,...)는 상대 잔차 norm(b-A*x)/norm(b)도 반환합니다. flag0이면 relres <= tol입니다.

[x,flag,relres,iter] = cgs(A,b,...)x가 계산된 반복 횟수도 반환합니다(0 <= iter <= maxit).

[x,flag,relres,iter,resvec] = cgs(A,b,...)는 각 반복에서 잔차 노름으로 구성된 벡터와 norm(b-A*x0)을 반환합니다.

예제

cgs에 입력값으로 행렬 사용

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

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

cgs converged at iteration 13 to a solution with 
relative residual 2.4e-016.

cgs에 함수 핸들 사용

이 예제에서는 이전 예제의 행렬 A를 행렬, 벡터 간 곱 함수 afun의 핸들로 바꾸고 선조건자 M1을 backsolve 함수 mfun의 핸들로 바꿉니다. 예제는 다음과 같은 특징을 가진 run_cgs 파일에 포함되어 있습니다.

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

  • run_cgs의 모든 변수를 afunmyfun에 사용할 수 있도록 afun을 중첩 함수로 포함합니다.

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

function x1 = run_cgs
n = 21;
b = afun(ones(n,1));
tol = 1e-12;  maxit = 15; 
x1 = cgs(@afun,b,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_cgs

MATLAB®이 다음을 반환합니다.

cgs converged at iteration 13 to a solution with 
relative residual 2.4e-016.

cgs에 선조건자(Preconditioner) 사용

이 예제에서는 선조건자를 사용하는 방법을 보여줍니다.

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

load west0479;
A = west0479;

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

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

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

tol = 1e-12;
maxit = 20;

cgs를 사용하여 요청된 허용오차와 반복 횟수로 해를 구합니다.

[x0,fl0,rr0,it0,rv0] = cgs(A,b,tol,maxit);

cgs가 요청된 반복 횟수인 20회 이내에 요청된 허용오차 1e-12로 수렴하지 않으므로 fl0은 1이 됩니다. 사실상 cgs의 동작이 좋지 않기 때문에 초기 추측값(x0 = zeros(size(A,2),1))이 최적의 해가 되고 it0 = 0으로 반환됩니다. MATLAB은 잔차 내역을 rv0에 저장합니다.

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

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

이 플롯에서 해가 수렴하지 않음을 알 수 있습니다. 선조건자를 사용하여 결과를 향상시킬 수 있습니다.

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를 생성할 경우 선조건자로 사용할 수 없는 특이 인자가 발생하기 때문에 불완전 LU를 생성할 수 없습니다.

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

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

cgs가 상대 잔차를 4.3851e-014(rr1의 값)로 유도하므로 fl1은 0이 됩니다. 기각 허용오차가 1e-6인 불완전 LU 분해 선조건을 적용하면, 3번째 반복(it1의 값)에서 상대 잔차는 미리 정해진 허용오차 1e-12보다 작아집니다. 출력 인수 rv1(1)norm(b)가 되고 출력 인수 rv1(14)norm(b-A*x2)가 됩니다.

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

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

참고 문헌

[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] Sonneveld, Peter, “CGS: A fast Lanczos-type solver for nonsymmetric linear systems,” SIAM J. Sci. Stat. Comput., January 1989, Vol. 10, No. 1, pp. 36–52.

확장 기능

참고 항목

| | | | | | | | |

R2006a 이전에 개발됨