레굴라 팔시

수학에서, 섭정팔시, 허위의 위치법, 또는 허위의 위치법은 하나의 미지의 방정식을 푸는 아주 오래된 방법이다. 이 방법은, 변형된 형태로, 여전히 사용되고 있다. 간단히 말해서, 방법은 변수에 대해 시험("거짓") 값을 사용한 다음 결과에 따라 시험 값을 조정하는 시행착오 기법이다. 이것을 때때로 "가시와 점검"이라고도 한다. 그 방법의 버전은 대수학의 출현과 방정식의 사용을 앞섰다.

예를 들어, (현대 표기법으로 표기된) 식 x + x/4 = 15의 해결책을 요구하는 라인드 파피루스의 문제 26을 예로 들어보자. 이것은 잘못된 자세로 해결된다.^[1] 먼저, x = 4를 얻으려면 왼쪽에서 4 + 4/4 = 5를 추측하십시오. 정수값을 산출하기 때문에 이 추측이 좋은 선택이다. 그러나 4는 너무 작은 3배의 값을 주기 때문에 원래 방정식의 해법은 아니다. 보상하려면 x(현재 4로 설정됨)에 3을 곱한 후 다시 대체하여 12 + 12/4 = 15를 구하여 솔루션이 x = 12인지 확인하십시오.

최신 버전의 기법은 새로운 시험 값을 선택하는 체계적인 방법을 채택하고 있으며, 해결책에 대한 근사치를 얻을 수 있는지 여부와 구할 수 있다면 근사치를 얼마나 빨리 찾을 수 있는지에 대한 문제와 관련이 있다.

두 가지 역사적 유형

허위입장법의 두 가지 기본적인 형태는 역사적으로 구분할 수 있는데, 단순 허위입장과 이중 허위입장을 구분할 수 있다.

단순 허위입장은 직접적인 비례가 수반되는 문제를 해결하기 위한 것이다. 그러한 문제는 다음과 같은 형태로 대수적으로 쓰여질 수 있다: x를 다음과 같이 결정한다.

${\displaystyle ax=b,}$

a와 b가 알려지면 방법은 테스트 입력 값 x′을 사용하고, 해당 출력 값 b′을 곱셈으로 찾는 것으로 시작한다:xx′ = b′. 정답 그 비례 조정에 의해,)).mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output.sfrac.tion,.mw-parser-output.sfrac .tion{디스플레이:inline-block, vertical-align:-0.5em, font-size:85%;text-align:센터}.mw-parser-output.sfrac .num,.mw-parser-output.sfrac .den{디스플레이:블록, line-height:1em, 마진:00.1e 발견된다.M}.mw-parser-output.sfrac .den{border-top:1px 고체}.mw-parser-output .sr-only{국경:0;클립:rect(0,0,0,0), 높이:1px, 마진:-1px, 오버 플로: 숨어 있었다. 패딩:0;위치:절대, 너비:1px}b/ b′)′.

이중의 거짓입장은 보다 어려운 문제를 푸는 것을 목표로 하고 있는데, 그 형식은 다음과 같이 x를 결정한다.

${\displaystyle f(x)=ax+c=0,}$

라고 알려지면

${\displaystyle f(x_{1}=b_{1},\qquad f(x_{2})=b_{2}.}$

이중 거짓 위치는 수학적으로 선형 보간과 동일하다. 한 쌍의 시험 입력과 해당 출력 쌍을 사용함으로써, 이 알고리즘의 결과는 다음과 같다.^[2]

${\displaystyle x={\frac {b_{1}x_{2}-b_{2}x_{1}{1}{b_{1}-b_{2}}:}}}$

암기하고 기계적으로 실행될 것이다. 실제로, 로버트 레코드가 그의 예술적 배경 (c. 1542년)에서 준 규칙은 다음과 같다.^[2]

부착 선형 함수의 경우,

${\displaystyle f(x)=ax+c,}$

이중 거짓 위치는 정확한 해결책을 제공하는 반면, 비선형 함수 f의 경우 반복에 의해 연속적으로 개선될 수 있는 근사치를 제공한다.

역사

단순한 거짓 위치 기법은 고대 바빌로니아 수학의 쐐기풀 판과 고대 이집트 수학의 파피리 판에서 발견된다.^[3][1]

이중의 거짓 입장은 후기에 순수한 산술 알고리즘으로서 생겨났다. 기원전 200년부터 AD 100년까지 거슬러 올라가는 고대 중국 수학 문헌인 '수학적 예술에 관한 9장(The Nine Chapters on the Mathematical Art)'에서 7장의 대부분은 알고리즘에 전념했다.^[4] 거기서, 그 절차는 구체적인 산술적 논거에 의해 정당화되었다. 그리고 나서, 원뿔형 섹션의 secant line이라고 부르는 것을 포함하는 것을 포함하여, 매우 다양한 이야기 문제들에 창조적으로 적용되었다. 보다 일반적인 예는 다음과 같은 "공동구매" 문제다.^[5]

이제 한 품목을 공동으로 구입하고, 모든 사람이 8 [코인]을 기부하고, 초과분은 3이고, 모든 사람이 7을 기부하고, 적자는 4이다. 인원수, 품목가격, 각각 얼마인가? 답변: 7명, 품목가격 53.^[6]

9세기에서 10세기 사이에 이집트 수학자 아부 카밀은 두 가지 오류의 서(Kitab al-khaṭaʾan)로 알려진 이중의 거짓 위치의 사용에 대해 지금은 잃어버린 논문을 썼다. 중동에서 이중 거짓으로 쓴 글 중 가장 오래된 것은 레바논 바알벡 출신의 아랍 수학자 쿠스타 이븐 루카(10세기)의 글이다. 그는 형식적인 유클리드식 기하학적 증거로 그 기법을 정당화했다. 중세 이슬람 수학의 전통 내에서 이중의 거짓 직위는 hisb al-khaṭaʾan("두 가지 오류에 의한 책략")으로 알려져 있었다. 수세기 동안 상업적, 법률적 질문(쿠란적 상속 규칙에 따른 부동산 칸막이)과 같은 실제적인 문제뿐만 아니라 순수하게 오락적인 문제를 해결하기 위해 사용되었다. 알고리즘은 흔히 이븐 알 야사민에게 귀속된 구절과 알 하사르와 이븐 알 바나가 설명하는 균형척도 등 연상학의 도움을 받아 외워졌는데, 이 세 가지 모두 모로코 태생의 수학자들이다.^[7]

피사의 레오나르도(Fibonacci)는 자신의 책인 Liber Abaci(AD 1202)의 13장을 그가 아랍 출처로부터 배운 알-카하아제인(al-khaṭaʾan)의 방법 뒤에 레귤레이션(regulitis elchatan)을 테칭하면서 이중 허위직위의 사용법을 설명하고 실증하는 데 바쳤다.^[7] 1494년, 파키올리는 그의 책 Summa de orcalica에서 el cataym이라는 용어를 사용했는데, 아마도 피보나치에서 따온 용어일 것이다. 다른 유럽 작가들은 파키올리를 따라 했고 때때로 라틴어나 자국어로 번역하기도 했다. 예를 들어 타르타글리아는 라틴어 버전의 파키올리 용어를 1556년 자국어 "거짓말하는 입장"으로 번역한다.^[8] 파키올리의 용어는 16세기 유럽 작품에서 거의 사라졌고 이 기술은 "거짓의 법칙" "입장의 법칙" "거짓의 법칙"과 "거짓의 법칙"과 같은 다양한 이름으로 바뀌었다. Regula Palsi는 1690년에 라틴어 버전의 거짓 규칙으로 등장한다.^[2]

몇몇 16세기 유럽 작가들은 진실을 찾는 과학에서 그 방법의 이름에 대해 사과할 필요성을 느꼈다. 예를 들어 1568년 험프리 베이커는 다음과 같이 말한다.^[2]

거짓의 법칙은 거짓이나 거짓을 가르치기 때문에 그렇게 명명된 것이 아니라, 어떤 수를 써서라도 참된 수를 찾도록 가르치며, 실제로 행해지고 있는 모든 속된 규칙 중에서 이것이 가장^e 탁월하다.

수치해석

거짓 위치의 방법은 선형 함수에 대한 정확한 해결책을 제공하지만, 더 직접적인 대수 기술은 이러한 함수에 대한 그것의 사용을 대체했다. 그러나, 수치해석에서는 이중의 거짓 위치가 반복적인 수치 근사 기법에 사용되는 뿌리 찾기 알고리즘이 되었다.

더 복잡한 방정식의 대부분을 포함한 많은 방정식은 반복적인 숫자 근사치로만 풀 수 있다. 이는 미지의 수량의 다양한 값을 시도하는 시행착오로 구성된다. 이러한 시행착오는 절차의 각 단계에서 해결책에 대한 새로운 추정치를 계산함으로써 유도될 수 있다. 계산된 추정치에 도달할 수 있는 많은 방법들이 있고 레굴라 팔시는 이것들 중 하나를 제공한다.

방정식을 주어 f (x) = 0의 형태를 갖도록 모든 항을 한쪽으로 이동시킨다. 여기서 f는 미지의 변수 x의 일부 함수다. 이 방정식을 만족하는 값 c, 즉 f (c) = 0은 함수 f의 루트 또는 0으로 불리며 원래 방정식의 해법이다. f가 연속함수이고 f (a₀)와 f (b₀)가 반대 부호인 두 개의₀ a와 b가₀ 존재하는 경우, 중간값 정리에 의해 함수 f는 구간(a₀, b₀)에 뿌리를 두고 있다.

그러한 뿌리에 대한 근사치를 얻기 위해 사용할 수 있는 뿌리 찾기 알고리즘은 많다. 가장 흔한 방법 중 하나는 뉴턴의 방법이지만, 특정 상황에서 뿌리를 찾지 못할 수 있고, 함수의 파생상품의 연산이 필요하기 때문에 계산적으로 비용이 많이 들 수도 있다. 다른 방법이 필요하며 하나의 일반적인 등급의 방법은 2점 브래킷링 방법이다. 이러한 방법은 (a_k, b_k)가 f의 루트를 포함하도록 k번째 단계에서 축소 간격[a_k, b_k]의 시퀀스를 생성하여 진행한다.

2점 브래킷 방식

이러한 방법은 f(x)가 반대 신호를 갖는 시행착오에 의해 처음 발견되는 두 개의 x 값으로 시작한다. 연속성 가정 하에서 f의 루트는 이 두 값들, 즉 이 값들이 뿌리를 "브래킷"할 수 있도록 보장된다. 그런 다음 이 두 값 사이의 점을 엄격히 선택하여 루트를 여전히 대괄호로 묶는 더 작은 간격을 만드는 데 사용한다. c가 선택된 지점인 경우, 더 작은 구간이 c에서 끝점으로 가고 여기서 f(x)는 f(c)의 반대편 기호를 가진다. f (c) = 0인 있음직하지 않은 경우, 루트가 발견되고 알고리즘이 중지된다. 그렇지 않으면 원하는 정확도에 대한 근사치를 얻기 위해 필요한 만큼 절차를 반복한다.

현재 간격에서 선택한 점은 용액의 추정치라고 생각할 수 있다. 이 방법의 다른 변화는 이 솔루션 추정치를 계산하는 다른 방법을 포함한다.

브래킷을 보존하고 솔루션 추정치가 브래킷링 간격의 내부에 있는지 확인하면 솔루션 추정치가 솔루션 쪽으로 수렴된다는 것을 보장할 수 있으며, 이는 뉴턴의 방법이나 세컨트 방법과 같은 다른 루트 찾기 방법으로는 보장할 수 없다.

이분법이라 불리는 가장 단순한 변동은 브라켓팅 간격의 중간점으로 용액 추정치를 계산한다. 즉, k단계에서 현재 브래킷팅 간격이 [a_k, b_k]인 경우, 새로운 용액 추정치_k c는 다음을 통해 얻는다.

${\displaystyle c_{k}={\frac {a_{k}+b_{k}}}{2}}.}$

이를 통해 c가_k a와_k b_k 사이에 있음을 보장하고, 이에 따라 솔루션을 향한 수렴을 보장한다.

각 단계에서 브래킷팅 간격의 길이가 절반으로 줄어들기 때문에 평균적으로 이분법 오차는 각 반복에 따라 절반으로 줄어든다. 따라서 세 번 반복할 때마다 이 방법은 정확도에서 대략 2의³ 인수를 얻는다.

레지울라 팔시(거짓 위치) 방법

거짓 위치 방법의 처음 두 번 반복. 빨간색 곡선은 f함수를 나타내고 파란색 선은 secants이다.

이분법 정합률은 다른 용액 추정치를 사용하여 개선할 수 있다.

regula falsi 방법은 현재 브래킷링 간격에서 함수의 끝점에 결합하는 선 세그먼트의 x 절편으로서 새로운 솔루션 추정치를 계산한다. 본질적으로 루트는 브라켓팅 간격의 라인 세그먼트에 의해 실제 기능을 교체한 다음 해당 라인 세그먼트에서 고전적인 이중 거짓 위치 공식을 사용하여 근사치를 산출하고 있다.^[9]

보다 정확하게는 k-th 반복에서 브라켓팅 간격이 (a_k, b_k)라고 가정한다. 그림과 같이 점(a_k, f (a_k) 및 (b_k, f (b_k))를 통해 선을 구성한다. 이 선은 함수 f의 그래프의 제2차 또는 현이다. 점 기울기 형태에서 그 방정식은 다음과 같이 주어진다.

${\displaystyle y-f(b_{k}={\frac {f_{k}-f(a_{k})-f(a_{k}}}{b_-a_{k}}}}(x-b_{k})).}$

이제 이 선의 x 절편, 즉 y = 0에 대한 x의 값이 되도록 c를_k 선택하고 이 값을 대체하여 구하십시오.

${\displaystyle f(b_{k}+{\frac {f_{k}-f(a_{k})-f(a_{k}}}{b_a_{k}}}}}(c_{k}-b_{k}}}=0).}$

c에_k 대해 이 방정식을 풀면 다음과 같은 결과를 얻을 수 있다.

${\displaystyle c_{k}=b_{k}-f(b_{k}){\frac {b_{k}-a_{k}}{f(b_{k})-f(a_{k})}}={\frac {a_{k}f(b_{k})-b_{k}f(a_{k})}{f(b_{k})-f(a_{k})}}.}$

이 마지막 대칭 형태는 계산상의 이점을 가지고 있다.

해결책이 다가오면 a와_k b는_k 매우 가까워질 것이고, 거의 항상 같은 징조일 것이다. 그러한 뺄셈은 유의한 자리수를 잃을 수 있다. f (b_k)와 f (a_k)는 항상 반대 부호이기 때문에 개선된 공식의 분자에서 "절제"는 사실상 추가(분모에서도 뺄셈인 것처럼)이다.

반복 번호 k에서 숫자 c는_k 위와 같이 계산한 다음 f (a_k)와 f (c_k)가 같은 기호를 가진 경우 a_{k + 1} = c와_k b = b를_{k + 1k} 설정하고, 그렇지 않으면 a_{k + 1} = a와_k b_{k + 1} = c를_k 설정한다. 이 과정은 뿌리가 충분히 잘 근사해질 때까지 반복된다.

위의 공식은 제분법에도 사용되지만 제분법은 항상 마지막 두 개의 계산된 점을 유지하므로 약간 빠른 반면, 브래킷을 보존하지 않고 수렴하지 않을 수 있다.

레굴라 팔시가 항상 수렴하고, 속도 저하를 피하는 데 능한 버전을 가지고 있다는 사실은 속도가 필요할 때 좋은 선택이 된다. 그러나 수렴 속도는 이분법보다 떨어질 수 있다.

분석

f (a₀)와 f (b₀)가 서로 반대되는 기호로 초기 끝점 a와₀ b가₀ 선택되기 때문에 각 단계에서 끝점 중 하나가 f의 근원에 가까워질 것이다. 만약 f의 두 번째 파생상품이 간격에 일정한 기호(그래서 변곡점이 없다면, 하나의 엔드포인트(f 역시 같은 기호를 가진 엔드포인트)는 컨버전스 엔드포인트가 업데이트되는 동안 이후의 모든 반복에 대해 고정된 상태를 유지할 것이다. 그 결과, 이분법과는 달리 괄호 폭은 0이 되는 경향이 없다(0이 기호(f ) = -사인(f ") 주변의 변곡점에 있지 않는 한). 그 결과, 잘못된 위치를 선택하는 데 사용되는 f(x)에 대한 선형 근사치는 가능한 한 빨리 개선되지 않는다.

이 현상의 한 예는 기능이다.

${\displaystyle f(x)=2x^{3}-4x^{2}+3x}$

초기 브래킷[-1,1]에 표시한다. 왼쪽 끝, -1은 절대 교체되지 않으며(처음 세 번 반복한 후에는 변경되지 않으며, f "는 간격에 음수임) 따라서 브래킷 너비가 1 아래로 떨어지지 않는다. 따라서 오른쪽 끝점은 선형 속도로 0에 접근한다(정확한 자릿수는 선형적으로 증가하고, 수렴 속도는 2/3이다).^{[citation needed]}

불연속 함수의 경우 이 방법은 함수가 부호를 변경하는 지점(예: 1/x 또는 부호 함수의 경우 x = 0)만 찾을 것으로 예상할 수 있다. 기호가 변경되는 점 외에도, 기능이 그 지점에서 정의되지 않았거나(또는 다른 값이 있는 경우)라도(예를 들어, f (x) = abs(x) - x가² 0일 때 x = 0에서, f (0) = 5에서, [-0.5, 3.0] 구간부터 시작하여 함수의 한계가 0인 지점까지 수렴하는 방법도 가능하다. 방법이 영점 한계치 또는 부호 변경으로 수렴되지 않는 것은 수학적으로 가능한 일이지만, 두 엔드포인트 모두 부호가 변하지 않는 불연속부에 수렴되기 위해서는 무한히 일련의 우연의 연속이 필요하기 때문에, 실제로 이것은 문제가 되지 않는다.

${\displaystyle f(x)={\frac {1}{1}(x-1)^{2}}+{\frac {1}{{1}(x+1)^{2}}.}$

이분법의 방법은 이러한 가상의 융합 문제를 피한다.

레굴라 팔시의 개선

비록 리굴라 팔시는 항상 이분법보다 훨씬 빠른 속도로 수렴하지만, 때때로 그 수렴을 엄청나게 늦출 수 있는 상황들이 있다. 이 문제는 레굴라 팔시만의 문제가 아니다. 이분법 외에 모든 수치 방정식 해결 방법은 어떤 조건에서는 느린 수렴 또는 무 수렴 문제를 가질 수 있다. 때때로 뉴턴의 방법과 세컨트 방법은 수렴하는 대신 분산되기도 하며, 레굴라 팔시의 수렴을 느리게 하는 동일한 조건에서 수렴하는 경우가 많다.

그러나, 비록 레굴라 팔시가 가장 좋은 방법 중 하나이고, 심지어 원래의 개선되지 않은 버전에서도 종종 최선의 선택이 될 것이다. 예를 들어, 파생상품이 평가하는데 엄청나게 많은 시간이 소요되기 때문에 뉴턴을 사용하지 않을 때, 또는 뉴턴과 연속 대체물이 수렴하지 못했을 때 말이다.

Regula 팰시의 고장 모드는 다음과 같이 쉽게 감지할 수 있다. 동일한 엔드포인트가 연속으로 두 번 유지된다. 비교적 비정상적인 불리한 상황으로 인해 속도가 느려지는 것을 피하기 위해 선택한, 수정된 잘못된 위치를 선택함으로써 문제를 쉽게 해결할 수 있다. 레굴라 팔시에 대한 많은 개선사항이 제안되었다. 그 중 일리노이 알고리즘과 앤더슨-비외크 알고리즘 두 가지가 아래에 설명되어 있다.

일리노이 알고리즘

일리노이 알고리즘은 새로운 y-값(즉, f (c_k))이 이전 값(f (c_{k − 1})과 동일한 기호를 가질 때 다음 추정 계산에서 유지된 엔드 포인트의 y-값을 절반으로 나누며, 이는 이전 단계의 엔드포인트가 유지됨을 의미한다. 따라서 다음과 같다.

${\displaystyle c_{k}={\frac {{}{1}{2}}f(b_{k})a_{k}-f(a_{k}b_{k}}}}{\frac {1}{1}{1}{2}}f(b_{k}-f})-f(a_{k}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$

또는

${\displaystyle c_{k}={\frac {f(b_{k})a_{k}-{1}{1}{1}{1}{frac {1}{{{k_}b}-{k}}-{f(b_{k}}-{1}{1},}}}}}}}}},},},},},}$

함수의 해당 측에서 다음 c가_k 발생하도록 하기 위해 엔드포인트 값 중 하나를 저중량화한다.^[10] 위에서 사용한 계수 ½은 임의로 보이지만, 초선형 수렴을 보장한다(방사적으로 알고리즘은 수정 단계 후 2개의 정규 단계를 수행하며, 수렴 순서는 1.442이다). 훨씬 더 나은 초선형 수렴 속도를 제공하는 리스케일링을 선택하는 다른 방법들이 있다.^[11]

위의 레굴라 팔시에 대한 조정은 일부 학자들에 의해 일리노이 알고리즘이라고 불린다.^[10][12] 포드(1995)는 이것과 다른 유사한 초선형 변형을 거짓 위치의 방법으로 요약하고 분석한다.^[11]

앤더슨-뵈르크 알고리즘

k-th 반복에서 브라켓팅 간격이 [a_k, b_k]이고 새로 계산된 추정치 c의_k 함수 값이 f (b_k)와 동일한 부호를 갖는다고 가정하자. 이 경우 새로운 브래킷링 간격[a_{k + 1}, b_{k + 1}] = [a_k, c_k]와 왼쪽 끝점이 유지된다. (지금까지는 일반 레굴라 팔시(Regula Palsi)와 일리노이 알고리즘과 같다.)

그러나 일리노이 알고리즘은 f (a_k)에 1/2을 곱하는 반면 앤더슨-Björck 알고리즘은 m을 곱하며, 여기서 m은 다음 두 값 중 하나를 가진다.^[13]

$${\displaystyle {\frac{fraged}m'&=1-{{{f_{k}}}{f(b_{f)}}}}{f(m&={\m&={case}m'}}{{{{{{1}{\ext}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}\end{case}\end{aigned}}$$

단순한 뿌리의 경우 앤더슨-비외르크는 연습에서 매우 좋은 성과를 낸다.^[14]

ITP 방식

Given ${\displaystyle \kappa _{1}\in (0,\infty ),\kappa _{2}\in \left[1,1+\phi \right)}$, ${\displaystyle n_{1/2}\equiv \lceil (b_{0}-a_{0})/2\epsilon \rceil }$ and ${\displaystyle n_{0}\in [0,\infty )}$ where ${\displaystyle \pi$}은$$(는) ${\displaystyle \mathrm{각}}$ $반복{\displaystyle }$ j${\displaystyle }$= 0${\displaystyle ,}$ 1,${\displaystyle \mathrm{2...}}$에서 황금 $배급량{\displaystyle \frac{\mathrm{}}{}}$ 1 ${\displaystyle \frac{2}{}}$($1$+${\displaystyle 5\sqrt{\mathrm{}}}$ )$${\$displaystyle${1$}{1$}{$1}{{\tqrt{5}}}}}}}}$이다$.$$j=0,1,2...$$}$ ITP$$ 메서드는 포인트 $x{\displaystyle {}_{}}$ ${\displaystyle {\text{ITP}}_{}}$ ${\$$ITP}}:$3단계$$:

1. [인터폴레이션 단계] bisection 및 regula falsi 지점 계산: x ${\displaystyle {1\mathrm{}}_{}}$/ ${\displaystyle {2\mathrm{}}_{}}$ ${\displaystyle {}_{}\frac{}{}a\frac{}{}}$ + ${\displaystyle \frac{\mathrm{}}{}}$ ${\displaystyle \frac{2}{}}$ ${\$}{2}$}}$ 및$$${\displaystyle {}_{}}$ ${\displaystyle x_{}}$ ${\displaystyle {}_{}b\frac{}{}}$ ${\displaystyle \frac{f}{}}$( a${\displaystyle \frac{}{}}$)${\displaystyle \frac{}{}}$- ${\displaystyle \frac{f}{}}$(${\displaystyle \frac{}{}}$)${\displaystyle \frac{}{}}$- ${\displaystyle \frac{f}{}}$ (${\displaystyle \frac{}{}}$) - f${\displaystyle \frac{}{}}$( )${\$ ;
2. [Truncation Step] Perturb the estimator towards the center: ${\displaystyle x_{t}\equiv x_{f}+\sigma \delta }$ where ${\displaystyle \sigma \equiv {\text{sign}}(x_{1/2}-x_{f})}$ and ${\di$$splaystyle \equiv \min\{\kappa _{1$} $b-a ^{\cappa _{2}}, x_{1/2}-x_{f} \}}}}}$ ;
3. [Projection Step] 추정기를 minmax 간격으로 투영: $x{\displaystyle {}_{}}$ ${\displaystyle {\text{ITP}}_{}{1\mathrm{}}_{}}$1 / ${\displaystyle {2\mathrm{}}_{}}$ -${\displaystyle {}_{}{}_{}}$ ${\displaystyle k_{}}$ { k ${\$$ITP}}\equiv x_{1/2}-\sigma \rho _{k}}$ where ${\displaystyle \rho _{k}\equiv \min \left\{\epsilon 2^{n_{1/2}+n_{0}-j}-{\frac {b-a}{2}}, x_{t}-x_{1/2} \right\}}$.

f($x{\displaystyle {\text{ITP}}_{}}$ )${\displaystyle f(x_{\text$} 함수$$값이 점에 있어서$$ $ITP}}}}$을(를) 쿼리한 다음, 각 끝에서 반대 기호의 함수 값으로 하위간격을 유지하여 루트를 괄호화하도록 간격을 줄인다. 이 3단계 절차에서는 이분법(bisection method)의 minmax 속성을 추정치뿐만 아니라 이분법(secant method)의 초선형 정합성이 향유된다는 것을 보장한다. 그리고 매끄러운 기능 및 비매끄러운 기능 하에서 이분법 및 보간법을 모두 능가하는 것으로 관찰된다.^[15]

현실적 고려

컴퓨터를 사용하여 하나의 방정식, 즉 몇 개의 방정식을 풀 때, 이분법 방법은 적절한 선택이다. 비록 이분법이 다른 방법들만큼 빠르지 않지만(최선을 다하고 문제가 없을 때) 그럼에도 불구하고, 이분법은 유용한 속도로 수렴할 수 있으며, 각 반복에서 오차를 대략 절반으로 줄임으로써 3회 반복마다 대략 소수 자릿수의 정확도를 얻는다.

수동 계산의 경우 계산기에 의해 더 빠른 방법을 사용하고자 하는 경향이 있으며, 보통은 그렇지만 항상은 아니지만 이분법보다 더 빨리 수렴한다. 그러나 컴퓨터는 이분법을 사용하더라도 방정식을 원하는 정확도로 신속하게 해결할 수 있기 때문에 신뢰도가 낮은 방법을 사용함으로써 시간을 절약하려고 할 필요가 없으며 모든 방법은 이분법보다 신뢰성이 떨어진다.

컴퓨터 프로그램이 실행되는 동안 방정식을 매우 많이 풀어야 하는 경우는 예외일 것이다. 그러면 더 빠른 방법에 의해 절약된 시간이 상당할 수 있다.

그리고 나서, 프로그램은 뉴턴의 방법으로 시작할 수 있고, 만약 뉴턴이 수렴하지 않는다면, 일리노이주나 앤더슨-뵈르크 버전과 같이, 아마도 그것의 개선된 버전들 중 하나일 것이다. 혹은, 만약 그것조차 이분법만큼 수렴되지 않는다면, 이분법으로 전환하라. 이분법은 항상 유용하지만, 화려하지는 않지만, 유용한 비율로 수렴한다.

y의 변화가 매우 작아지고 x도 거의 변하지 않을 때, 그러면 뉴턴의 방법은 문제에 부딪히지 않고 수렴할 것이다. 따라서, 그러한 유리한 조건하에서, 만약 오류가 매우 작기를 원하고 매우 빠른 수렴을 원한다면, 뉴턴의 방법으로 전환할 수 있을 것이다.

예시 코드

C 프로그래밍 언어로 작성된 이 예제 프로그램은 일리노이 알고리즘의 예다. cos(x) = x인³ 양의 숫자 x를 찾기 위해 방정식은 f(x) = cos(x) - x³ = 0인 루트 찾기 형식으로 변환된다.

#include <stdio.h> #include <수학.h>  곱절로 하다 f(곱절로 하다 x) {    돌아오다 cas(x) - x*x*x; } /* s,t: 검색하는 간격의 끝점         [a, b 기사]    e: 상대 오류에 대한 상한의 절반    m: 최대 반복 횟수     [실제 구현에서 f는 함수-점자 유형의 매개 변수가 될 것이다.] */ 곱절로 하다 팔시메토드(곱절로 하다 s, 곱절로 하다 t, 곱절로 하다 e, 인트로 m) {    곱절로 하다 r, fr;    인트로 n, 옆구리를 = 0;    /* 구간의 끝점에서 시작 값 */    곱절로 하다 fs = f(s);    곱절로 하다 ft = f(t);     을 위해 (n = 0; n < m; n++) {       /* r은 기사 */에서 c이다.       r = (fs * t - ft * s) / (fs - ft);       만일 (팹(t - s) < e * 팹(t + s))          부숴뜨리다;       fr = f(r);        만일 (fr * ft > 0) {          /* fr과 ft는 부호가 같으며, r을 t에 복사 */          t = r; ft = fr;          만일 (옆구리를 == -1)             fs /= 2;          옆구리를 = -1;       } 다른 만일 (fs * fr > 0) {          /* fr과 fs는 부호가 같으며, r을 s에 복사한다 */          s = r; fs = fr;          만일 (옆구리를 == +1)             ft /= 2;          옆구리를 = +1;       } 다른 {          /* fr * f_ 매우 작음 (0과 같은 크기) */          부숴뜨리다;       }    }    돌아오다 r; }  인트로 본래의(공허하게 하다) {    활자화하다(%0.15f\n", 팔시메토드(0, 1, 5E-15, 100));    돌아오다 0; } 

이 코드를 실행한 후 최종 답은 약 0.865474033101614이다.

참고 항목

• ITP 방법, minmax와 superlinear convergence가 보장된 변화
• 허위입장법에 근거한 또 다른 뿌리 찾기 방법인 Ridders의 방법
• 브렌트의 방법

참조

추가 읽기

• Burden, Richard L.; Faires, J. Douglas (2000). Numerical Analysis (7th ed.). Brooks/Cole. ISBN 0-534-38216-9.
• Sigler, L.E. (2002). Fibonacci's Liber Abaci, Leonardo Pisano's Book of Calculation. Springer-Verlag. ISBN 0-387-40737-5.
• Roberts, A.M. (2020). "Mathematical Philology in the Treatise on Double False Position in an Arabic Manuscript at Columbia University". Philological Encounters. 5 (3–4): 3–4. doi:10.1163/24519197-BJA10007. S2CID 229538951. (이전에 출판되지 않은 중세 아랍어 원고의 이중 허위 위치에 관한 논문)