브렌트 루트 찾기 알고리즘의 일반적인 구현에서 "e"변수는 무엇입니까?

Question

브렌트 근점 찾기 알고리즘의 표준 (수치 조리법 및 GSL C 버전이 동일 함) implementation을 읽고 변수 "e"의 의미를 이해할 수 없습니다. 사용법은 "e"가 대괄호 사이의 이전 거리라고 가정합니다. 그런데 왜 우리가 이분법을 사용할 때 "xm"(거리의 절반)으로 설정되어 있습니까?

Answer 1

저는 알고리즘에 익숙하지 않습니다. 그러나 C 소스와 알고리즘의 Wikipedia description을 비교할 수 있습니다. 알고리즘은 직설적 인 것처럼 보입니다 (루트를 찾는 메소드에 익숙한 경우). 그러나 C 구현은 포트란의 직접 포트처럼 보이므로 읽기가 어렵습니다.

가장 좋은 추측은 e이 루프 조건과 관련이 있다는 것입니다. 다음, e = b - a 나중에 if (fabs(e) <= tol ... : 이 repeat until f(b or s) = 0 or |b − a| is small enough (convergence)

C 소스는 말한다 :

은 위키 백과 (알고리즘의 라인 8) 말한다.

내가 변수의 목적이 책에서 명확하게 설명 될 수 있기를 바랍니다,하지만 분명히

---

이 좋아 :)없는 것, 여기 당신은 간다. 원래 구현 (algol 60)을 찾았습니다 here. 알고리즘의 좋은 설명 이외에, 그것은 (50 페이지에서 시작) 말한다 :

가 e가 마지막 전 단계에서 p/q의 값이 될 수 있습니다. |e| < δ 또는 |p/q| ≥ 1/2|e| 인 경우 이등분을 수행하십시오. 그렇지 않으면 우리는 Dekker의 알고리즘처럼 이분법 또는 보간을 수행합니다. 따라서, |e|은 모든 두 번째 단계에서 최소한 2의 계수만큼 감소하고, |e| < δ 이분법이 수행되어야 할 때. (A 양분 후 우리는 다음 단계 e = m 걸릴.)

그래서 e의 추가 데커의 알고리즘의 브렌트의 "기본 수정"입니다.

Answer 2

E는 "엡실론 (epsilon)"변수이며 근본적으로 얼마나 가깝게 가까워 졌는지 측정합니다. 특정 애플리케이션에 20 자리의 정밀도가 필요하지 않을 수 있으므로 엡실론을 사용하면 필요한 반복 횟수 (즉, 실행 시간)와 필요한 정확성 간의 균형을 맞출 수 있습니다.

부동 소수점 숫자로는 정확하지 않을 수 있으므로 엡실론은 약간 작은 0이 아닌 숫자 여야합니다. 실제 값은 응용 프로그램에 따라 다릅니다 ... 기본적으로 가장 큰 오류입니다.

Answer 3

양분 단계에서 간격은 정확히 반으로 나뉩니다. 따라서 간격의 현재 너비를 유지하는 e도 절반으로 줄어 듭니다.