Newton's Method
미분 가능한 연속 함수 f 인 f(x)=0을 푸는 여러 가지 방법 중 하나이다.
구간 [a, b]에서 함수 f(x)가 미분 가능하고 함수의 해도 포함하고 있다고 가정한다.
기본적인 방법은 폐구간 [a, b]에서 실수 {R}에 대해 정의된 함수 f:[a, b]->{R} 이 미분가능할 때 임의의 x{n}에 대해서 x{n+1}을 라고 하고, 이를 계속 반복하게 되면 특정 조건 하에 x{n}은 점점 함수 f(a)=0을 만족하는 a에 수렴하게 된다.
반복 계산을 정지하기 위한 정지조건은 할선법에서 사용된 것 중 하나가 쓰인다.
장점
- 매우 효과적인 방법
- 오차가 제곱에 비례해서 줄어들기 때문에 시행을 몇 번만 해도 매우 빠른 속도로 수렴한다.
- 4~5번의 반복 실행으로 10-6승 정도의 작은 오차 범위를 갖는 근을 구한다.
단점
- 초기 가정치 x0를 근에 충분히 가깝게 하지 않으면 수렴하지 않는다.
- 접선이 거의 수평인 즉 f'(x{0})=0인 x0를 선택해선 안 된다.
- 기술적으로 완전히 수렴하지 못한다.
- 함수 f(x)의 1차 도함수 f ’(x)의 계산도 반드시 필요하다. (근사 시키는 함수 f(x)가 미분 가능한지를 먼저 확인)
Secant method
뉴턴의 방법은 매우 빠른 대신 미분을 해야 한다는 단점이 있었습니다. 이번에 소개할 할선법(Secant method)은 뉴턴의 방법과 같은 아이디어를 사용하면서 미분을 하지 않는 방법입니다. 할선법의 특이한 점은, 뉴턴의 방법에서 미분계수의 역할을 평균 변화율이 대신하는 것입니다. 미분 대신 평균 변화율을 사용하기 때문에 시작점이 두 개 필요합니다.
할선의 근을 연속적으로 찾는 것으로 시행한다. 뉴턴 방법에서 도함수를 사용하는 대신 함숫값2개를 사용하는 근사로 생각할 수도 있다. 할선법은 다음과 같이 반복적 시행으로 정의된다
허용 오차를 ε이라고 할 때, 할선법은 정지조건에서 정지한다
- 할선법의 오차들의 비율이 피보나치 수로 나오는 것을 알 수 있다.
- 할선법은 이분법보다 빠르게 근으로 근사한다.
Bisection method
수학에서 이분법은 근이 반드시 존재하는 폐구간을 이분한 후, 이 중 근이 존재하는 하위 폐구간을 선택하는 것을 반복하여서 근을 찾는 알고리즘이다. 간단하고 견고하며 해의 대략적 위치를 안다면 일정 오차 내에 있는 1개의 해는 무조건 도출이 가능하나, 상대적으로 느린 방식이다. 이분법은 근이 존재한다는 것 자체를 전제로 구간을 설정하는 것이므로 근이 존재할 가능성은 100%이므로 방정식이 간단하고 근 자체가 가장 중요한 목적인 경우 가장 적합한 방법이다.
구간에서 함수의 부호가 (+)에서 (-)로 혹은 (-)에서 (+)로 바뀌면 근이 존재
구간 [a, b]를 이등분하여 부호가 바뀌면 이분법을 계속 반복
함수의 부호가 더 이상 바뀌지 않을 때 이분법을 중단
이분법은 단일한 근의 추정 위치를 가르쳐주기보다는 오직 해가 존재하는 폐구간만을 결과로 제공한다. 이분법을 n번 반복하였을 때 오차의 최댓값의 절댓값은 해 구간의 전체 길이인 아래와 같다.
제시된 식은 이분법을 허용 가능한 오차의 범위까지 구하기 위해서 몇 번을 반복하여야 하는가를 미리 고려할 때 유용하다. 두 번째 식을 이용하여, 허용 가능한 오차 ε 이하의 추정 해를 구하고 싶다면 이분법을 아래의 식을 만족하는 n 번 이상 반복하여야 한다. 이분법의 단점은 근을 찾아가는 실행 속도가 느리다.
찾고자 하는 값의 범위를 반복 시마다 반으로 줄여서 찾는 전산 과학 분야의 이진 검색과 유사하다.
f가 폐구간 [a, b] 에서 연속 함수이며 f(a)f(b) < 0 이면, 이분법은 f의 해에 대해서 수렴한다. 사실상 오차가 각 반복마다 반으로 줄어드는 것이다. 그러므로 이 방법은 해에 대해서 선형적으로 수렴하나, 그 속도는 상당히 느리다. 다른 말로 표현하면 이분법은 f(a)와f(b)가 서로 다른 부호를 가지고 있는 한 수렴하는 것을 보장한다.
Information science time
뉴턴의 방법과 할선법의 공통점은 선형 함수로근사한다는 것입니다. 선형함수로 문제를 변형 시켜서 쉽게 풀고, 그 결과를 다시 문제에 넣어 더 비슷한 문제를 만들어 푸는 것입니다. 이렇게 문제를 선형성을 갖도록 변형시키는 것을 선형화(linearization)라고 합니다.
뉴턴 방법의 단점은 도함수를 알고 있어야 한다는 것입니다. 컴퓨터로 코딩을 한다면, 루프(Loop)를 조금만 돌려도 되는 장점을 가진 대신, 미분하느라 루프를 한 바퀴를 도는 데 시간이 오래 걸리는 단점을 가졌다고 할 수 있습니다. 방정식의 근이 여러 개가 있을 때는 초기값에 따라 하나의 근으로만 수렴하게 되니 주의해야 합니다..
댓글