Conjugate Gradient

• Conjugate Gradient 에 대해서 일단 간략하고 이해하고 쉽게 포스팅을 하도록 하겠다.

• Conjugate Gradient에 대해 정확하진 않지만 이해하기 쉽게 설명하도록 하겠다. 좀 더 자세한 내용을 알고 싶으신 분은 

J. Shewchuk. An introduction to the conjugate gradientmethod without the agonizing pain.

을 쭉 읽어보는 것을 적극 추천한다.

• Conjugate Gradient을 이용하는 이유는 

Ax = b

(이 때, A는 matrix, x는 vector, b도 vector)

을 풀고 싶을 때(즉, 연산을 통해 x를 구하고자 할 때) A의 매트릭스가 너무 커지게 되면 A의 역행렬을 b에 곱해서 구하는 계산자체가 매우 부담이 된다.(시간,연산량 측면에서...) 그래서 numerical method를 많이 이용하는데 그것의 일종이 Conjugate Gradient 방법이다. 좀 더 쉽게 말하면 직접 역행렬을 곱하는게 힘드니까 Conjugate Gradient 방법을 이용하여 근사해를 구하는 것이다. 

 이 포스팅의 핵심은 이 부분이다. Conjugate Gradient를 처음 보면 왜 이런방법을 쓰는지조차 이해가 안 될 것이다.(내가 그렇게 생각했기 때문에 지극히 개인적인 생각에서 포스팅을 작성하였다.) 그래서 그런 분들에게 어느 정도 감을 잡게 해주기 위해 이 글을 작성하였다. 

• Conjugate Gradient는 무엇이냐?

-> 이 부분도 간단하게 설명하도록 하겠다. 식을 단순히 스칼라 식으로 단순화 시켜서 컨셉만 이해해보면 Ax = b라는 것은 Ax^2 -bx = 상수 를 미분한 식이다. 이것을 거꾸로 이야기하면 이차식의 최소점을 찾는다는 것은 Ax = b의 해를 구한다는 것과 같은 말이 된다.(A가 양수인 경우에 한해서 이야기하는 것이다. 여러가지 조건이 붙는데 이 부분은 위에 논문을 읽으면 이해할 수 있을 것이다.) 그래서 이차식에 처음 대략적인 해로 예상되는 점을 하나 잡고 가장 빠르게 감소하는 방향으로 계속해서 근사화 시켜가다보면 결국 최저점에 가까운 점을 구할 수 있다는 것이 Conjugate Gradient의 기본적인 컨셉이다.

위에서도 계속해서 말하였지만 이 포스팅은 Conjugate Gradient의 아주 기본적인 컨셉만을 설명한 것이다. 그러니 이 글을 보고 조금이라도 Conjugate Gradient의 감이 잡혔다면 이제는 좀 더 자세하게 위의 논문을 참고하여 이해해보면 좋을 듯 싶다.