세컨트법

세컨트 방법의 처음 두 번 반복.빨간색 곡선은 f함수를 나타내고, 파란색 선은 secants이다.이 특별한 경우에 제분법은 가시적인 뿌리로 수렴하지 않는다.

수치해석에서는 secant method가 secant lines의 연속된 뿌리를 사용하여 함수 f의 루트에 더 잘 근사하게 하는 뿌리 찾기 알고리즘이다.세컨트 방법은 뉴턴의 방법의 유한차 근사치라고 생각할 수 있다.그러나 이차적인 방법은 뉴턴의 방법보다 3000년 이상 앞서 있다.^[1]

방법

이차 방법은 반복 관계에 의해 정의된다.

${\displaystyle x_{n}=x_{n-1}-f(x_{n-1}){\frac {x_{n-1}-x_{n-2}}{f(x_{n-1})-f(x_{n-2})}}={\frac {x_{n-2}f(x_{n-1})-x_{n-1}f(x_{n-2})}{f(x_{n-1})-f(x_{n-2})}}.}$

재발 관계에서 알 수 있듯이, 제2의 방법에는₀ x와₁ x라는 두 개의 초기값이 필요하며, 이는 근본에 가깝게 눕도록 이상적으로 선택해야 한다.

방법의 파생

초기값₀ x와 x부터₁ 위의 그림과 같이 포인트(x₀, f(x₀))와 (x₁, f(x₁))를 통해 선을 구성한다.경사-절편 형식에서 이 선의 방정식은 다음과 같다.

${\displaystyle y={\frac {f(x_{1}-f(x_{0})-f(x_{0}}}}{x_{0}}}}(x-x_{1})+f(x_{1}){1}.}$

이 선형 함수의 루트, 즉 y = 0과 같은 x 값

${\displaystyle x=x_{1}-f(x_{1}-f({1}-x_{0}){\frac {x_{1}{0}{f(x_{1})-f(x_{0}}}}}}}.}$

그런 다음 x의 새로운 값을 x로₂ 사용하고 x와₀ x₁ 대신 x와₁ x를₂ 사용하여 프로세스를 반복한다.x₃, x₄ 등에 대해 충분히_n 높은 정밀도(x와 x의_n−1 충분한 작은 차이)에 도달할 때까지 이 과정을 계속한다.

${\displaystyle {\begin{aligned}x_{2}&=x_{1}-f(x_{1}){\frac {x_{1}-x_{0}}{f(x_{1})-f(x_{0})}},\\[6pt]x_{3}&=x_{2}-f(x_{2}){\frac {x_{2}-x_{1}}{f(x_{2})-f(x_{1})}},\\[6pt]&\,\,\,\vdots \\[6pt]x_{n}&=x_{n-1}-f(x_{n-1}){\frac {x_{n-1}-x_{n-2}}{f(x_{n-1})-f(x_{n-2})}}.\end{정렬}}}$

수렴

초기$$ 값 $x{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$ 및 $x{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$}이 루트에 충분히 가까운$$ 경우$$ secant $방법$의 x ${\displaystyle n_{}}$ ${\$displaystyle $x_{n$$}$이 f ${\displaystystyle f}$의 루트로 수렴된다.융합의 순서는 φ으로, 여기서.

${\displaystyle \varphi ={\frac {1+{\sqrt{5}}{2}}:\약 1.15}$

황금 비율이다.특히 수렴은 초선형이지만 상당히 2차적인 것은 아니다.

$이{\displaystyle }$ 결과는 f ${\displaystyle f}$이(가) 연속적으로 2배 차이가 나고 문제의 루트는 단순하다는 일부 기술 조건에서만 유지된다(즉, 다중성 1)

초기 값이 루트에 충분히 가깝지 않으면 제2의 방법이 수렴된다는 보장이 없다."가까운 정도"에 대한 일반적인 정의는 없지만, 그 기준은 함수가${\displaystyle }$[${\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$] $[\displaystyle [x_{0},x_{1}]$ 간격에 얼마나 "wiggly"인지와 관계가 있다$.$ 예를 들어, $f{\displaystyle }$ ${\displaystyle f}$가 그 간격에 따라$$ 다를 수 있고 $f{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$= ${\displaystyle 0}$ ${\displaystystystystyf=0}$이 있다.알고리즘이 수렴되지 않을 수 있다.

다른 뿌리 찾기 방법과의 비교

제분법은 이분법처럼 뿌리가 고사리처럼 남아 있을 것을 요구하지 않으며, 따라서 항상 수렴하지 않는다.거짓 위치법(또는 regula falsi)은 secant 방법과 동일한 공식을 사용한다.However, it does not apply the formula on ${\displaystyle x_{n-1}}$ and ${\displaystyle x_{n-2}}$, like the secant method, but on ${\displaystyle x_{n-1}}$ and on the last iterate ${\displaystyle x_{k}}$ such that ${\displaystyle f(x_{k})}$ and ${\displaystyle f(x_{n-}}$${\displaystyle 1_{}}$) ${\displaystyle f(x_{n-1})$에는 다른 기호가 있다.이는 잘못된 위치 방법이 항상 수렴한다는 것을 의미하지만, 단지 선형적인 수렴 순서와 함께 수렴한다는 것을 의미한다.초선형 수렴 순서를 갖는 괄호는 ITP 방법이나 일리노이 방법과 같은 거짓 위치 방법(Regula falsi § regula falsi의 개선사항 참조)의 개선으로 얻을 수 있다.

세컨트 방법의 재발 공식은 뉴턴의 방법의 공식에서 도출할 수 있다.

${\displaystyle x_{n}=x_{n-1}-{\frac {f(x_{n-1}}){f'(x_{n-1}}}}}}$

유한한 값의 근사치를 사용하여 $작은{\displaystyle }$ {$${\$displaystyle \epsilon$에 대해 다음을 수행하십시오.

${\displaystyle f'(x_{n-1})\approx {\frac {f(x_{n-1})-f(x_{n-2})}{x_{n-1}-x_{n-2}}}\approx {\frac {f(x_{n-1}+{\frac {\epsilon }{2}})-f(x_{n-1}-{\frac {\epsilon }{2}})}{\epsilon }}}$

제분법은 파생상품이 근사치로 대체되어 준뉴턴 방식으로 해석될 수 있다.

뉴턴의 방법과 제2의 방법을 비교해 보면 뉴턴의 방법이 더 빨리 수렴되는 것을 알 수 있다(순서 2는 φ 6 1.6과 대조된다).그러나 뉴턴의 방법은 모든 단계에서$$ $f{\displaystyle }$ ${\displaystyle f}$과 파생 $f{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$의 평가가 필요한 반면, secant 방법은 $f{\displaystyle }$ ${\displaystyle f}$의 평가만 요구하기 때문에 실제로 secant 방법이 더 빠른 경우도 있다$.$예를 들어 $f{\displaystyle }$ ${\displaystyle$ f$}$을(를) 평가하는 데 그 파생상품 평가만큼 많은 시간이$$ 소요되고 다른 모든 비용을 소홀히 한다고 가정할 경우, 뉴턴의 방법의 한 단계와 동일한 비용에 대해 세컨트 방법의 두 단계(오차의 로그 factor² 2.6 감소)를 수행할 수 있다(사실에 의한 오류 로그 감소).또는 2)를 사용하여 secant 방법이 더 빠를 것이다.그러나, 파생상품의 평가를 위해 병렬 처리를 고려한다면, 뉴턴의 방법은 여전히 더 많은 단계를 사용하지만 시간적으로는 더 빠르게 그것의 가치를 증명한다.

일반화

브로이든의 방법은 세컨트 방법을 둘 이상의 차원으로 일반화한 것이다.

다음 그래프는 f 함수를 빨간색으로, 마지막 secant 선을 굵은 파란색으로 나타낸다.그래프에서 secant 선의 x 절편은 f의 근원에 대한 좋은 근사치로 보인다.

계산 예제

아래에서는 python 프로그래밍 언어로 secant 메소드가 구현된다.

그런 다음 초기 지점 ${\displaystyle {x\mathrm{}}_{}}$ 0${\displaystyle {}_{}}$= ${\displaystyle 10}$ ${\displaystyle x_{0}=10}$ 및$$ $x{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$= ${\displaystyle 30}$ ${\displaystyle x_{1}=30}$의 함수 f(x) = x² - 612의 루트를 찾기 위해 적용한다.

반항하다 secant_message(f, x0, x1, 반복해서):     """제분법을 사용하여 계산된 루트를 반환하십시오."""     을 위해 i 에 범위(반복해서):         x2 = x1 - f(x1) * (x1 - x0) / 둥둥 뜨다(f(x1) - f(x0))         x0, x1 = x1, x2     돌아오다 x2  반항하다 f_message(x):     돌아오다 x ** 2 - 612  뿌리를 내리다 = secant_message(f_message, 10, 30, 5)  인화하다(f"루트:{뿌리를 내리다}")  # 루트 : 24.738633748750722 

메모들

참고 항목

• 거짓입장법

참조

• Avriel, Mordecai (1976). Nonlinear Programming: Analysis and Methods. Prentice Hall. pp. 220–221. ISBN 0-13-623603-0.
• Allen, Myron B.; Isaacson, Eli L. (1998). Numerical analysis for applied science. John Wiley & Sons. pp. 188–195. ISBN 978-0-471-55266-6.

외부 링크

• 전체론적 수치적 방법 연구소의 세컨트 방법 노트, PPT, Mathcad, Mapatica, Matrixlab
• Weisstein, Eric W. "Secant Method". MathWorld.