켤레기울기법

켤레기울기법 또는 공역기울기법(, )이란 수학에서 대칭인 양의 준정부호행렬(陽-準定符號行列, 영어: positive-semidefinite matrix)을 갖는 선형계의 해를 구하는 수치 알고리즘이다. 이는 보통 반복알고리즘으로 풀리고, 따라서 숄레스키 분해와 같은 방법이나  직접 풀기에 너무 큰 계가 갖는 희소행렬 등에 사용하기 적합하다. 그러한 계는 편미분 방정식들이나 최적화 문제들을 수치적으로 풀 때 자주 등장한다.

켤레기울기법은 또한 에너지 최소화같은 제약조건이 없는 최적화문제를 풀 수 있다. 이것은 Magnus Hestenes와 Eduard Stiefel에 의해 개발되었다.

방법의 설명
우리는 다음과 같은 선형 계의 방정식을 풀기 원한다고 가정하자.
Ax = b
A는 n x n 대칭행렬이고 (i.e. AT = A), 양의 정부호행렬 positive definite (i.e.  Rn에서 모두 0이 아닌 벡터들 x에 관하여 xTAx > 0 )이고, 실수이고, x, b는 n x 1 실수 인 열벡터이다.

여기서 우리는 이 계의 유일한 해를 라고 하자.

직접적 방법으로서 공역 구배법
다음과 같이
 일 때,

두개의 영이 아닌 벡터들을  u 과 v를 켤레라고 하자. (A에 대하여)
A는 대칭이고 양의 정부호를 갖는 행렬이기 때문에 왼쪽 변이 내적으로 정의 된다.

만일 두개의 벡터가 이 내적에 대하여 수직이면 그것들을 켤레라고 한다.

켤레가 되는것은 대칭관계이다: 만일 u가 v에 켤레이면
v가 u에 켤레이다.

 
는 n개 상호적인 켤레 방향들의 집합이라고 가정하자.
그러면 는 의 기저이고,
그래서  내에서  우리는
그 해 의 를 확장시킬 수 있다:

그리고 우리가 보면

어떤 에 관하여,

(왜냐하면 는 상호적인 켤레이기 때문에)

이 결과는 위에 정의된 내적을 고려하면서 이 결과는 아마도 매우 명백하다.

이것은 Ax = b 방정식을 풀 때 다음의 방법을 쓴다. :
n개의 켤레 방향들의 수열을 찾고, 그런뒤 그 계수들 을 계산한다.

반복적 방법으로서 공역 구배법
만일 우리가 켤레 벡터들을 pk 신중하게 선택하고, 우리는 그 해  의 좋은 근사 값을 얻기 위해서 그들의 모두가 필요하지 않을 수 있다.
그래서 우리는 반복적인 방법으로서 공역 구배법을 보기를 원한다.
n이 매우 커서 직접적인 방법으로 풀기에 시간이 매우 많이 걸리는 계들의 경우 이 방법을 거의 정확하게 풀게 해준다.

의 초기 추측값을 x0라고 하자.
우리는 일반성을 잃지 않고 x0 = 0 (마찬가지로, 대신에 그 계를 Az = b − Ax0 ) 라고 가정할 수 있다.
x0와 함께 시작하여 우리는 그 해를 찾고, 각각의 반복에서 우리는 그 해 (우리에게 잘알려지지 않은 해) 에 근접한게 무엇인지 알려주는 측도가 필요하다.
이 측도는 그 해 가 또한
다음의 이차함수의 유일하게 최소치라는 사실로부터 나왔다.
그래서 만일  f(x)가 반복에 있어서 작아진다면 그것은 우리가  에 가까이 간다는 것을 의미한다.

x = x0에서 f의 구배(영어:gradient)의 음의 값이 되도록  처음 기저 p0를 잡는다.

그 f의 구배(영어:gradient)가 Ax−b와 같고,  추측 해x0를 가지고 시작한다.
(우리는 만일 우리가 다른 어떤 것을 추측할 이유가 없다면   가 0 이고 그 집합을 x0 0으로 항상 추측할 수 있다. )
이것을 p0 = b−Ax0라고 두자.
그 기저안에 다른 벡터들은 그 구배(영어:gradient)에 켤레가 될 것이다.
그래서 이 방법의 이름이 공역 구배법(영어:conjugate gradient method)이다.

우선 k번째 단계에서 rk를 유수(영어:residue)라고 하자:

rk는 x = xk에서 음의 f의 구배(gradient)라는 점을 염두에 두고,
그래서 경사 하강법은 rk 방향에서 움직일 것이다.
여기, 우리는 그 방향들 pk이 각각 다른것과 켤레라고 주장한다.
이 시행은 충분히 합리적인데,
우리는 또한 다음 찾는 방향은  최근의 유수와 이전의 모든 검색방향들에 의해서 정하게 한다.

그 공역 제약조건은 직교-유형의 제약조건이고 그래서, 그 알고리즘은 그램 -슈미트와 유사하다.

이것은 다음의 표현과 같다:

(수렴에 켤레성 제약조건의 영향에 관한 문서의 상단에 있는 그림을 참조)
이 방향에 따르면, 그 다음 최적의 위치는 다음에 의해 주어진다.

를 포함함

(pk 와xk-1 가 켤레이기 때문에 마지막 등식이 성립한다.)

그 결과의 알고리즘
그 위에 알고리즘은 공역 구배법의 가장 간단한 설명을 제공한다.
일견에, 그 알고리즘에 명시된대로 이전의 검색 방향들과 유수 벡터들의 저장이 필요할 뿐만 아니라
많은 행렬 벡터의 곱셉들이 필요로 하고, 따라서 계산하는데 비용이 많이 들 수 있다.
그러나 그 알고리즘의 근접한 분석은 다음 과 같이 볼 수 있다.

모든  i < k에 관하여 rk+1는 pi과 켤레이다.
(예를 들어 귀납법에 의해 증명될 수 있다) 그러므로 오직 rk, pk,
그리고 xk 이  rk+1, pk+1, 그리고 xk+1를 세우는데 필요로 한다.
게다가 오직 하나의 행렬-벡터 곱셈이 각각의 반복적인 계산마다 필요하다.

실수이고, 대칭행렬이고 양의 정부호 행렬인 A에 관하여 Ax = b를 푸는 알고리즘 방법은 밑에 상세히 설명되어 있다.

그 입력 벡터  x0는 거의 정확한 초기 해나 0이 될 수 있다.
이것은 위에 명시된 정확한 절차의 다른 식이다.

이것은 일반적으로 자주 사용되는 알고리즘이다. 이와 같은 식은은 비선형 공역 구배법인 플레처 리브스에서 또한 사용된다.

알파와 베타의 계산
알고리즘에서,  는
가 에 직교가 되도록 선택된다. 그 분모는 다음과 같이 단순화된다.

때문에 그 는  가 에 켤레가 되도록 선택된다. 처음에,  는

를 이용하고, 마찬가지로 , 의 분자는 다음과 같이 다시 쓰면,

 과  처음 구상에 의해 직교이기 때문에 그분모는 다음과 같이 다시 쓰면,

검색 방향들 은 켤레이고 다시 그 유수들과 직교라는 사실을 이용하여 이 알고리즘에서 를
제거한 후를 얻는다.

함수 (프로그래밍) 예제
function [x] = conjgrad(A,b,x)
    r=b-A*x;
    p=r;
    rsold=r'*r;

    for i=1:1e6
        Ap=A*p;
        alpha=rsold/(p'*Ap);
        x=x+alpha*p;
        r=r-alpha*Ap;
        rsnew=r'*r;
        if sqrt(rsnew)<1e-10
              break;
        end
        p=r+rsnew/rsold*p;
        rsold=rsnew;
    end
end

수치적 예제 
공역 구배법을 설명하기 위해서, 우리는 간단한 예를 들겠다.
다음과 같은 선형 계인 Ax = b을 고려하면

 

그 계의 거의 정확한 해를 찾기 위해서
우리는 초기 추측값을 설정하여 공역 구배법의 두 단계만에 수행할 것이다.

해 
참고에 따르면 정확한 해는 :: 

우리의 첫번째 단계는 x0과 연관된 유수 벡터 r0를 계산 하는 것이다.

이 유수는 식 r0 = b - Ax0으로부터 계산되고, 그리고 우리에 경우에는 다음과 같다.

 

이것은 첫번째 반복 계산이기 때문에, 우리는 우리의 초기 검색방향p0 으로써 유수 벡터 r0를 사용할 것이다.

앞으로의 반복 계산에서 pk를 선택하는 방법은 변할 것이다.

우리는 이제 위의 관계를 이용하여 이제 스칼라 α0를 계산한다.

우리는 그 식을 이용하여 x1을 계산 할 수 있다.

이 결과는 첫번째 반복 계산을 완료되고, 그 계에 "향상된" 거의 정확한 해x1가 된다.
우리는 이제 이동하여 이 식을 이용하여 새로운 유수 벡터 r1를 계산할 것이다.

그 과정속에서 우리의 다음 단계는 다음 검색 방향 p1를 결정하는데 결과적으로 사용될 스칼라 β0를 계산하는 것이다.

이제, 이 스칼라 β0를 이용하여, 우리는 그 관계를 이용하여 다음 검색 방향 p1을 계산 할 수 있다.

우리는 α0에서 사용했던 같은 방식으로
새로 얻은 p1를 이용하여 이제 스칼라 α1를 계산 할 수 있다.

마지막으로, 우리는 x1을 찾았던 같은 방법으로 x2를 찾는다.

그 결과, x2는 그 계의 해에 x1 과 x0보다 "더나은" 근사치가 된다.

만일 제한된 정밀도 대신에 이 예에서 정확한 계산이 되었다면, 그 정확한 해는 이론적으로 n=2 반복수행 후 도달 할 것이다.
(n은 그 계의 크기임).

수치선형대수학
최적화 알고리즘