켤레기울기법
켤레기울기법 또는 공역기울기법(, )이란 수학에서 대칭인 양의 준정부호행렬(陽-準定符號行列, 영어: positive-semidefinite matrix)을 갖는 선형계의 해를 구하는 수치 알고리즘이다. 이는 보통 반복알고리즘으로 풀리고, 따라서 촐스키 분해와 같은 방법이나 직접 풀기에 너무 큰 계가 갖는 희소행렬 등에 사용하기 적합하다. 그러한 계는 편미분 방정식들이나 최적화 문제들을 수치적으로 풀 때 자주 등장한다.
켤레기울기법은 또한 에너지 최소화같은 제약조건이 없는 최적화문제를 풀 수 있다. 이것은 Magnus Hestenes와 Eduard Stiefel에 의해 개발 되었다.
우리는 다음과 같은 선형 계의 방정식을 풀기 원한다고 가정하자.
A는 n x n 대칭행렬이고 (i.e. A = A), 양의 준정부호행렬 positive definite (i.e. R에서 모두 0이 아닌 벡터들 x에 관하여 xAx > 0 )이고, 실수이고, x, b는 n x 1 실수 인 열벡터이다.
여기서 우리는 이 계의 유일한 해를 formula_1라고 하자.
다음과 같이
두개의 영이 아닌 벡터들을 "u" 과 "v" 를 켤레라고 하자. ("A"에 대하여)
A는 대칭이고 양의 정부호를 갖는 행렬이기 때문에 왼쪽 변이 내적으로 정의 된다.
만일 두개의 벡터가 이 내적에 대하여 수직이면 그것들을 켤레라고 한다.
켤레가 되는것은 대칭관계이다: 만일 u가 v에 켤레이면
v가 u에 켤레이다.
는 n개 상호적인 켤레 방향들의 집합이라고 가정하자.
그러면 formula_5 는 formula_6의 기저이고,
그래서 formula_5내에서 우리는
그 해 formula_8의 formula_9 를 확장시킬 수 있다:
그리고 우리가 보면
어떤 formula_12에 관하여,
이 결과는 위에 정의된 내적을 고려하면서 이 결과는 아마도 매우 명백하다.
이것은 Ax = b 방정식을 풀 때 다음의 방법을 쓴다. :
n개의 켤레 방향들의 수열을 찾고, 그런뒤 그 계수들 formula_16을 계산한다.
만일 우리가 켤레 벡터들을 p 신중하게 선택하고, 우리는 그 해 formula_1 의 좋은 근사 값을 얻기 위해서 그들의 모두가 필요하지 않을 수 있다.
그래서 우리는 반복적인 방법으로서 공역 구배법을 보기를 원한다.
"n"이 매우 커서 직접적인 방법으로 풀기에 시간이 매우 많이 걸리는 계들의 경우 이 방법을 거의 정확하게 풀게 해준다.
formula_1의 초기 추측값을 x라고 하자.
우리는 일반성을 잃지않고 x = 0 (마찬가지로, 대신에 그 계를 Az = b − Ax ) 라고 가정할 수 있다.
x와 함께 시작하여 우리는 그 해를 찾고, 각각의 반복에서 우리는 그 해 formula_1(우리에게 잘알려지지 않은 해) 에 근접한게 무엇인지 알려주는 측도가 필요하다.
이 측도는 그 해 formula_1가 또한
다음의 이차함수의 유일하게 최소치라는 사실로부터 나왔다.
그래서 만일 f(x)가 반복에 있어서 작아진다면 그것은 우리가 formula_1에 가까이 간다는 것을 의미한다.
x = x에서 "f"의 구배(영어:gradient)의 음의 값이 되도록 처음 기저 p를 잡는다.
그 "f"의 구배(영어:gradient)가 Ax−b와 같고, 추측 해x를 가지고 시작한다.
이것을 p = b−Ax라고 두자.
그 기저안에 다른 벡터들은 그 구배(영어:gradient)에 켤레가 될 것이다.
그래서 이 방법의 이름이 "공역 구배법"(영어:"conjugate gradient method")이다.
우선 "k"번째 단계에서 r 를 "유수"(영어:residue)라고 하자:
formula_24
r는 x = x에서 음의 "f"의 구배(gradient)라는 점을 염두에 두고,
그래서 경사 하강법은 r 방향에서 움직일 것이다.
여기, 우리는 그 방향들 p이 각각 다른것과 켤레라고 주장한다.
이 시행은 충분히 합리적인데,
우리는 또한 다음 찾는 방향은 최근의 유수와 이전의 모든 검색방향들에 의해서 정하게 한다.
그 공역 제약조건은 직교-유형의 제약조건이고 그래서, 그 알고리즘은 "그램 -슈미트"와 유사하다.
이것은 다음의 표현과 같다:
이 방향에 따르면, 그 다음 최적의 위치는 다음에 의해 주어진다.
를 포함함
그 위에 알고리즘은 공역 구배법의 가장 간단한 설명을 제공한다.
일견에, 그 알고리즘에 명시된대로 이전의 검색 방향들과 유수 벡터들의 저장이 필요할 뿐만 아니라
많은 행렬 벡터의 곱셉들이 필요로 하고, 따라서 계산하는데 비용이 많이 들 수 있다.
그러나 그 알고리즘의 근접한 분석은 다음 과 같이 볼 수 있다.
모든 "i < k"에 관하여 r는 p과 켤레이다.
(예를 들어 귀납법에 의해 증명될 수 있다) 그러므로 오직 r, p,
그리고 x 이 r, p, 그리고 x를 세우는데 필요로 한다.
게다가 오직 하나의 행렬-벡터 곱셈이 각각의 반복적인 계산마다 필요하다.
실수이고, 대칭행렬이고 양의 정부호 행렬인 A에 관하여 Ax = b를 푸는 알고리즘 방법은 밑에 상세히 설명되어 있다.
그 입력 벡터 x는 거의 정확한 초기 해나 0이 될 수 있다.
이것은 위에 명시된 정확한 절차의 다른 식이다.
formula_28
이것은 일반적으로 자주 사용되는 알고리즘이다. 이와 같은 식은formula_29은 비선형 공역 구배법인 플레처 리브스에서 또한 사용된다.
알고리즘에서, formula_30 는
formula_31가 formula_32에 직교가 되도록 선택된다. 그 분모는 다음과 같이 단순화된다.
formula_33
formula_34때문에 그 formula_29 는 formula_36 가 formula_37에 켤레가 되도록 선택된다. 처음에, formula_29 는
formula_39
formula_40를 이용하고, 마찬가지로 formula_41, formula_29의 분자는 다음과 같이 다시 쓰면,
formula_43
formula_31 과 formula_32 처음 구상에 의해 직교이기 때문에 그분모는 다음과 같이 다시 쓰면,
formula_46
검색 방향들 formula_37은 켤레이고 다시 그 유수들과 직교라는 사실을 이용하여 이 알고리즘에서 formula_30를
제거한 후formula_49를 얻는다.
공역 구배법을 설명하기 위해서, 우리는 간단한 예를 들겠다.
다음과 같은 선형 계인 Ax = b을 고려하면
그 계의 거의 정확한 해를 찾기 위해서
우리는 초기 추측값을 설정하여 공역 구배법의 두 단계만에 수행할 것이다.
참고에 따르면 정확한 해는 :: formula_52
우리의 첫번째 단계는 x과 연관된 유수 벡터 r를 계산 하는 것이다.
이 유수는 식 r = b - Ax으로 부터 계산 되고, 그리고 우리에 경우에는 다음과 같다.
이것은 첫번째 반복 계산이기 때문에, 우리는 우리의 초기 검색방향p 으로써 유수 벡터 r 를 사용할 것이다.
앞으로의 반복 계산에서 p를 선택하는 방법은 변할 것이다.
우리는 이제 위의 관계를 이용하여 이제 스칼라 α를 계산한다.
우리는 그 식을 이용하여 x을 계산 할 수 있다.
이 결과는 첫번째 반복 계산을 완료되고, 그 계에 "향상된" 거의 정확한 해x가 된다.
우리는 이제 이동하여 이 식을 이용하여 새로운 유수 벡터 r를 계산할 것이다.
그 과정속에서 우리의 다음 단계는 다음 검색 방향 p를 결정하는데 결과적으로 사용될 스칼라 β를 계산하는 것이다.
이제, 이 스칼라 β를 이용하여, 우리는 그 관계를 이용하여 다음 검색 방향 p을 계산 할 수 있다.
우리는 α에서 사용했던 같은 방식으로
새로 얻은 p를 이용하여 이제 스칼라 α를 계산 할 수 있다.
마지막으로, 우리는 x을 찾았던 같은 방법으로 x를 찾는다.
그 결과, x는 그 계의 해에 x 과 x보다 "더나은" 근사치가 된다.
만일 제한된 정밀도 대신에 이 예에서 정확한 계산이 되었다면, 그 정확한 해는 이론적으로 "n"=2 반복수행 후 도달 할 것이다.
("n"은 그 계의 크기임).