bicg

쌍켤레 기울기법(BiConjugate Gradients Method)

구문

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


설명

x = bicg(A,b)는 선형 연립방정식 A*x = b를 풀어 x를 구합니다. nxn 계수 행렬 A는 크기가 큰 정사각 희소 행렬이어야 합니다. 열 벡터 b는 길이가 n이어야 합니다. A는 함수 핸들 afun일 수 있으며, afun(x,'notransp')는 A*x를, afun(x,'transp')는 A'*x를 각각 반환합니다.

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

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

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

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

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

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

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

플래그(flag)	수렴
0	bicg가 maxit 반복 횟수 내에, 기대한 허용오차 tol로 수렴되었습니다.
1	bicg가 maxit의 횟수만큼 반복되었지만 수렴되지 않았습니다.
2	선조건자 M은 조건이 나쁜 행렬입니다.
3	bicg가 정체되었습니다. 연속된 2회의 반복이 동일했습니다.
4	bicg를 실행하는 동안 계산된 스칼라 수량 중 하나가 너무 작아지거나 커져 계산을 계속할 수 없습니다.

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

[x,flag,relres] = bicg(A,b,...)는 상대 잔차 norm(b-A*x)/norm(b)도 반환합니다. flag가 0인 경우 relres <= tol입니다.

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

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

예제

bicg에 행렬 입력값 사용

이 예제에서는 행렬 입력값을 bicg에 사용하는 방법을 보여줍니다. bicg에 다음 코드를 실행하면

n = 100; 
on = ones(n,1); 
A = spdiags([-2*on 4*on -on],-1:1,n,n);
b = sum(A,2); 
tol = 1e-8; 
maxit = 15;
M1 = spdiags([on/(-2) on],-1:0,n,n); 
M2 = spdiags([4*on -on],0:1,n,n);

x = bicg(A,b,tol,maxit,M1,M2);

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

bicg converged at iteration 9 to a solution with relative
residual 5.3e-009

bicg에 함수 핸들 사용

이 예제에서는 이전 예제의 행렬 A를 행렬, 벡터 간 곱 함수 afun의 핸들로 바꿉니다. 이 예제는 파일 run_bicg에 포함되어 있으며, 이 파일은 다음과 같이 동작합니다.

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

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

다음을 run_bicg라는 파일에 추가합니다.

function x1 = run_bicg
n = 100; 
on = ones(n,1); 
b = afun(on,'notransp'); 
tol = 1e-8; 
maxit = 15;
M1 = spdiags([on/(-2) on],-1:0,n,n); 
M2 = spdiags([4*on -on],0:1,n,n);
x1 = bicg(@afun,b,tol,maxit,M1,M2);

    function y = afun(x,transp_flag)
       if strcmp(transp_flag,'transp')      % y = A'*x
          y = 4 * x;
          y(1:n-1) = y(1:n-1) - 2 * x(2:n);
          y(2:n) = y(2:n) - x(1:n-1);
       elseif strcmp(transp_flag,'notransp') % y = A*x
          y = 4 * x;
          y(2:n) = y(2:n) - 2 * x(1:n-1);
          y(1:n-1) = y(1:n-1) - x(2:n);
       end
    end
end

다음을 입력하면

x1 = run_bicg;

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

bicg converged at iteration 9 to a solution with ...
relative residual 
5.3e-009

bicg에 선조건자(Preconditioner) 사용

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

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

load west0479;
A = west0479;

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

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

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

tol = 1e-12;
maxit = 20;

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

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

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

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

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

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

행렬 A가 비대칭 행렬이므로 ilu를 사용하여 선조건자(Preconditioner)를 만듭니다.

[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] = bicg(A,b,tol,maxit,L,U);

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

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

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.

확장 기능

GPU 배열

Parallel Computing Toolbox™를 사용해 GPU(그래픽스 처리 장치)에서 실행하여 코드 실행 속도를 높일 수 있습니다.

사용법 관련 참고 및 제한 사항:

• 입력값 A가 희소 행렬이면:

  • 오직 1개의 희소 행렬 선조건자 M이 지원됩니다.

  • 2개의 선조건자 M1과 M2를 사용하는 경우 두 선조건자 모두 함수여야 합니다.

  • GPU 배열에 대해 bigc는 정체를 감지하지 않습니다(플래그 3). 대신 수렴 실패를 보고합니다(플래그 1).

자세한 내용은 GPU에서 MATLAB 함수 실행하기 (Parallel Computing Toolbox) 항목을 참조하십시오.

분산 배열

Parallel Computing Toolbox™를 사용하여 대규모 배열을 클러스터의 결합된 메모리에 걸쳐 분할할 수 있습니다.

사용법 관련 참고 및 제한 사항:

• M1이 함수이면 이는 각 행에 독립적으로 적용됩니다.

자세한 내용은 Run MATLAB Functions with Distributed Arrays (Parallel Computing Toolbox) 항목을 참조하십시오.

참고 항목

bicgstab | cgs | gmres | ilu | lsqr | minres | mldivide | pcg | qmr | symmlq

도움말 항목

• 함수 핸들 생성하기

R2006a 이전에 개발됨

×

Open Example (ko_KR)

A modified version of this example exists on your system. Do you want to open this version instead? (ko_KR)

No, overwrite the modified version (ko_KR) Yes (ko_KR)