루트 찾기 알고리즘

근찾기 알고리즘(root-finding algorithm)은 수학과 컴퓨팅에서 연속 함수의 0을 찾는 알고리즘입니다.실수에서 실수로 또는 복소수에서 복소수로 이어지는 함수 $f$ 의 0은 $f (x)$ = $0$ 이 되는 숫자 $x$ 입니다. 일반적으로 함수의 0은 정확히 계산되거나 닫힌 형태로 표현될 수 없기 때문에 근찾기 알고리즘은 부동소수점 수 또는 a로 표현되는 근사치를 0에 제공합니다.작은 격리 간격 또는 복잡한 루트의 디스크(오류 경계와 함께 대략적인 출력과 동일한 간격 또는 디스크 출력).^[1]

방정식 $f (x)$ = $g (x)$ 를 푸는 것은 함수 $h (x)$ = $f (x)$ – $g (x$ )의 근을 구하는 것과 같습니다 $.$ 따라서 근찾기 알고리즘을 사용하면 연속 함수로 정의된 모든 방정식을 풀 수 있습니다.그러나 대부분의 루트 찾기 알고리즘은 모든 루트를 찾을 것이라고 보장하지는 않습니다. 특히 이러한 알고리즘이 루트를 찾지 못한다면 루트가 존재하지 않는다는 것을 의미하지는 않습니다.

대부분의 수치 근찾기 방법은 반복을 사용하여 근을 향해 수렴하는 수열을 한계로 생성합니다.시작 값으로 루트에 대한 하나 이상의 초기 추측이 필요한 경우, 알고리즘을 반복할 때마다 루트에 대한 보다 정확한 근사치가 연속적으로 생성됩니다.반복은 어느 시점에서 중지되어야 하므로 이러한 방법은 정확한 해가 아니라 근에 대한 근사치를 생성합니다.많은 방법은 이전 값에 대한 보조 함수를 평가하여 후속 값을 계산합니다.따라서 한계는 원래 방정식의 근을 고정점으로 하고 이러한 고정점으로 빠르게 수렴하기 위해 선택되는 보조 함수의 고정점입니다.

수치해석에서는 일반적인 근찾기 알고리즘의 거동을 연구합니다.그러나 다항식의 경우, 다항식의 대수적 특성이 가장 효율적인 알고리즘에 기본이기 때문에 근찾기 연구는 일반적으로 컴퓨터 대수에 속합니다.알고리즘의 효율성은 주어진 함수의 특성에 크게 좌우될 수 있습니다.예를 들어, 많은 알고리즘이 입력 함수의 도함수를 사용하는 반면 다른 알고리즘은 모든 연속 함수에 대해 작업합니다.일반적으로 수치 알고리즘은 함수의 모든 근을 찾는 것이 보장되지 않기 때문에 근을 찾지 못한다고 해서 근이 없다는 것이 증명되지는 않습니다.그러나 다항식의 경우, 실수가 없음을 증명하기 위해 대수적 속성을 사용하고, 위치한 고유한 루트에 대한 수치적 방법(일반적으로 뉴턴 방법)의 수렴을 보장할 수 있을 만큼 충분히 작은 별도의 간격(또는 복잡한 루트의 디스크)에 루트를 찾는 특정 알고리즘이 있습니다.

브라켓방식

브래킷 방법은 루트가 포함된 연속적으로 작은 간격(대괄호)을 결정합니다.간격이 충분히 작으면 루트가 발견된 것입니다.이들은 일반적으로 연속 함수가 구간의 끝점에서 반대 부호의 값을 가질 경우, 함수가 구간에서 적어도 하나의 근을 갖는다는 것을 주장하는 중간값 정리를 사용합니다.따라서 함수가 구간의 끝점에서 반대 부호를 갖도록 구간부터 시작해야 합니다.그러나 다항식의 경우 구간의 근 수에 대한 정보를 얻기 위한 다른 방법(데카르트의 부호 규칙, 부단의 정리, 스투름의 정리)이 있습니다.이는 다항식의 실근 분리를 위한 효율적인 알고리듬으로 이어지는데, 이는 모든 실근을 보장된 정확도로 찾는 것을 보장합니다.

이등분법

가장 간단한 근찾기 알고리즘은 이등분 방법입니다. $f$ 를 연속 함수라고 하고, f $(a)$ 와 $f (b$ )가 반대 부호 $($ 괄호)를 갖는 구간 [ $a,$ b $]$ 를 $안다고$ 가정합니다 $.$ $c$ =( $a$ + $b)/2$ 를 구간의 중간(구간을 이등분하는 중점 또는 점)이라고 합니다. $그러면$ f $(a)$ 와 $f (c),$ $또는$ f $(c)$ 와 f $(b)$ 중 하나는 반대 부호를 가지며, 하나는 구간 크기를 2로 나눕니다.이등분 방법은 강력하지만, 반복할 때마다 1비트의 정확도를 얻습니다.따라서 ε 근사근을 찾는 데 필요한 함수 평가 수는 $\log _{2}{\frac {b-a}{\varepsilon }}$ 2 ⁡ b - $\log _{2}{\frac {b-a}{\varepsilon }}$ ε ${\displaystyle$ \ $log$ _ ${2}{\frac {b-a}{\varepsilon}}}$ 입니다 $\log _{2}{\frac {b-a}{\varepsilon }}$ 다른 방법은 적절한 조건에서 더 빨리 정확도를 얻을 수 있습니다.

위위(정규위)

false position method, 일명 regular false method는 이등분법과 유사하지만 이등분 검색의 구간 중간값 대신 구간의 끝점에서 표시된 함수 값을 연결하는 선의 x절편을 사용합니다. 즉,

c={\frac {af(b)-bf(a)}{f(b)-f(a)}}

false position은 secant 방법과 유사하지만, 마지막 두 점을 유지하는 대신 한 점을 근의 양쪽에 유지해야 합니다.false position method는 bisection method보다 빠를 수 있고 secant method처럼 절대 발산되지 않을 수 있지만 $f (c$ )에 대한 잘못된 부호를 초래할 수 있는 반올림 오류로 인해 일부 순진한 구현에서 수렴에 실패할 수 있습니다 $.$ 일반적으로 $f$ 의 변화율이 루트 근처에서 클 경우 발생할 수 있습니다.

ITP 방식

ITP 방법은 secant 방법과 같이 smooth 함수의 근에 초선형 수렴을 보장하면서 bissection 방법의 최악의 경우와 동일한 근을 브라켓화하는 유일한 방법입니다.또한 루트 위치에 대한 연속적인 분포에 대해 평균적으로 이등분 방법을 능가하는 것이 보장된 유일한 알려진 방법입니다(ITP Method# 참조).분석).이는 브래킷 간격뿐만 아니라 내부의 모든 지점이 이등분 방법만큼 빠르게 수렴하는 최소 간격을 추적함으로써 수행됩니다.조회된 점 c의 구성은 보간(정규 가성과 유사), 잘라내기(정규 가성과 유사한 정칙 가성을 조정), 그리고 나서 최소 간격에 투영하는 세 단계를 따릅니다.이러한 단계를 결합하면 매끄러운 함수에 대한 보간 기반 방법과 유사한 보장이 있는 동시에 minmax 최적 방법이 생성되며, 실제로 매끄러운 함수와 매끄럽지 않은 함수 모두에서 이등분 방법과 보간 기반 방법을 능가할 것입니다.

보간

많은 루트 찾기 프로세스는 보간에 의해 작동합니다.이것은 함수를 낮은 차수의 다항식으로 근사화하기 위해 근의 마지막 계산 근사치를 사용하는 것으로 구성되며, 이 근사치 근에서 동일한 값을 사용합니다.그런 다음 다항식의 근을 계산하여 함수의 근의 새로운 근사값으로 사용하고 프로세스를 반복합니다.

두 개의 값을 사용하면 차수 1의 다항식(즉, 함수의 그래프를 선으로 근사하는 것)으로 함수를 보간할 수 있습니다.이것이 secant method의 기본입니다.세 개의 값이 포물선으로 함수의 그래프를 근사화하는 이차 함수를 정의합니다.이것이 뮬러의 방법입니다.

규칙 가성은 또한 보간 방법으로, 반드시 마지막 두 계산점이 아닌 두 점을 선으로 보간하는 것으로 secant 방법과 다릅니다.

반복법

모든 근찾기 알고리즘은 반복으로 진행되지만, 반복적인 근찾기 방법은 일반적으로 새로운 근삿값을 얻기 위해 근의 마지막 계산 근사값에 적용되는 보조 함수 정의로 구성된 특정 유형의 반복을 사용합니다.보조 기능의 고정 지점(원하는 정밀도까지)에 도달하면 반복이 중지됩니다. 즉, 새 계산 값이 이전의 값에 충분히 가까울 때입니다.

뉴턴 방법(및 이와 유사한 도함수 기반 방법)

뉴턴의 방법은 함수 f가 연속 도함수를 갖는다고 가정합니다.뉴턴의 방법은 근에서 너무 멀리 시작하면 수렴하지 않을 수 있습니다.그러나 수렴할 때는 이등분 방법보다 빠르며, 대개는 2차적입니다.뉴턴의 방법은 또한 고차원적인 문제에 쉽게 일반화되기 때문에 중요합니다.수렴 차수가 높은 뉴턴식 방법은 하우스홀더의 방법입니다.뉴턴 방법 다음의 첫 번째 방법은 입방정합차를 갖는 핼리 방법입니다.

세컨트법

뉴턴 방법의 도함수를 유한한 차이로 대체하면, 우리는 시언트 방법을 얻습니다.이 방법은 도함수의 계산(또는 존재)이 필요하지 않지만 가격은 수렴 속도가 느립니다(순서는 약 1.6(황금비)입니다).시언트 방법을 고차원으로 일반화한 것이 브로이든의 방법입니다.

슈테펜센법

다항식 적합을 사용하여 세컨트 방법에 사용된 유한 차분의 2차 부분을 제거하여 미분을 더 잘 근사화하면 2차 수렴을 가지며 (좋은 것과 나쁜 것 모두) 행동은 뉴턴 방법과 본질적으로 동일하지만 미분을 필요로 하지 않는 스테펜센 방법을 얻을 수 있습니다.

고정점반복법

우리는 함수의 근을 찾기 위해 고정점 반복을 사용할 수 있습니다. $f(x)$ 을 $f(x)$ 찾기 $f(x)=0$ 함수 $f(x)$ f $f(x)$ ( x ) {\displaystyle $f (x$ $f(x)=0$ = 0 ${\displaystyle$ f $(x$ )= $0})$ 를 0으로 설정한 경우, $f(x)=0$ ( $f(x)=0$ = $f(x)=0$ ${\displaystyle$ f $(x$ )= $0}$ 이 $x=g(x)$ = g $x=g(x)$ ( $x=g(x)$ ${\displaystyle$ x ( $x)}$ 이 되도록 방정식을 $x$ ${\$ displaystyle x = g ( $x$ $)}$ 로 바꿉니다(참고,각 $f(x)=0$ $g(x)$ = 0 ${\$ $displaystyle$ $f(x$ ) $g(x)$ = $f(x)=0$ {\ $displaystyle$ f(x) = $0}$ 함수에 $g(x)$ 많은 g $x$ ) 함수가 있습니다.다음으로 $x_{n+1}=g(x_{n})$ 의 각 면을 x n $x_{n+1}=g(x_{n})$ + $x_{n+1}=g(x_{n})$ = g $x_{n+1}=g(x_{n})$ ( $x_{n+1}=g(x_{n})$ $x_{n+1}=g(x_{n})$ ) ${\displaystyle x_{n+1$ } = $g(x_{n})}$ 로 레이블을 지정하여 반복을 수행합니다.그런 다음 x $x_{1}$ ${\$ 에 대한 값을 선택하고 $x_{1}$ 함수의 루트 쪽으로 수렴할 때까지 반복합니다.반복이 수렴되면 루트로 수렴됩니다. $|g'(root)|<1$ < $|g'(root)|<1$ ${\displaystyle g'(루트)$ < $1}$ 인 경우에만 반복이 수렴됩니다 $|g'(root)|<1$

$f(x)=0$ ( $f(x)=0$ = 0 ${\displaystyle f(x$ )= $0}$ 을 $x=g(x)$ = g ( $x=g(x)$ ${\displaystyle$ x= $g(x)}$ 로 변환하는 예로 $x=g(x)$ 함수 $f(x)=x^{2}+x-1$ ( x $f(x)=x^{2}+x-1$ = $f(x)=x^{2}+x-1$ $f(x)=x^{2}+x-1$ + x - $f(x)=x^{2}+x-1$ ${\displaystyle f(x$ )= $x^{2}$ + $x-1}$ 이 주어지면 다음 방정식 중 하나로 다시 씁니다 $f(x)=x^{2}+x-1$

x_{n+1}=(1/x_{n})-1

x_{n+1}=(1/x_{n})-1

+

x_{n+1}=(1/x_{n})-1

=

( 1

x_{n+1}=(1/x_{n})-1

/

x_{n+1}=(1/x_{n})-1

x_{n+1}=(1/x_{n})-1

)

x_{n+1}=(1/x_{n})-1

-

x_{n+1}=(1/x_{n})-1

{\displaystyle x_

}=(

1/x_{n})-1

x_{n+1}=1/(x_{n}+1)

x_{n+1}=1/(x_{n}+1)

+

x_{n+1}=1/(x_{n}+1)

=

x_{n+1}=1/(x_{n}+1)

/

x_{n+1}=1/(x_{n}+1)

(

x_{n+1}=1/(x_{n}+1)

x_{n+1}=1/(x_{n}+1)

+

x_{n+1}=1/(x_{n}+1)

)

{\displaystyle x_

}=

1/(x_{n}+1

x_{n+1}=1-x_{n}^{2}

x_{n+1}=1-x_{n}^{2}

+

x_{n+1}=1-x_{n}^{2}

=

1 -

x_{n+1}=1-x_{n}^{2}

n

x_{n+1}=1-x_{n}^{2}

{\displaystyle x_

}=

1-x_{n}^{2

x_{n+1}=x_{n}^{2}+2x_{n}-1

n

x_{n+1}=x_{n}^{2}+2x_{n}-1

+

x_{n+1}=x_{n}^{2}+2x_{n}-1

=

x_{n+1}=x_{n}^{2}+2x_{n}-1

n

x_{n+1}=x_{n}^{2}+2x_{n}-1

+

x_{n+1}=x_{n}^{2}+2x_{n}-1

x_{n+1}=x_{n}^{2}+2x_{n}-1

x_{n+1}=x_{n}^{2}+2x_{n}-1

-

x_{n+1}=x_{n}^{2}+2x_{n}-1

{\displaystyle x_

}=

x_{n}^{2}+2x_{n}-1

또는

x_{n+1}=\pm {\sqrt {1-x_{n}}}

x_{n+1}=\pm {\sqrt {1-x_{n}}}

+

x_{n+1}=\pm {\sqrt {1-x_{n}}}

=

±

x_{n+1}=\pm {\sqrt {1-x_{n}}}

-

x_{n+1}=\pm {\sqrt {1-x_{n}}}

x_{n+1}=\pm {\sqrt {1-x_{n}}}

{\displaystyle x_

}=\

pm {\sqrt {1-x_{n

역내삽법

보간 방법에서 복소수 값이 나타나는 것은 역 off의 보간을 통해 방지할 수 있으며, 결과적으로 역 2차 보간 방법이 생성됩니다.다시, 수렴은 secant 방법보다 점근적으로 빠르지만, 역 이차 보간은 반복이 루트에 근접하지 않을 때 종종 잘 작동하지 않습니다.

메소드 조합

브렌트법

Brent의 방법은 이등분법, secant법 및 역 이차 보간법의 조합입니다.매번 반복할 때마다 Brent의 방법은 이 세 가지 방법 중에서 어떤 방법이 가장 효과적일 것인지를 결정하고 그 방법에 따라 단계를 수행합니다.이것은 견고하고 빠른 방법을 제공하므로 상당한 인기를 누리고 있습니다.

라이더즈 메소드

Riders의 방법은 구간 중간 지점의 함수 값을 사용하여 근에 대한 지수 보간을 수행하는 하이브리드 방법입니다.이를 통해 이등분 방법에 비해 최대 2배 이상의 반복 횟수가 보장되는 빠른 수렴을 얻을 수 있습니다.

다항식의 근

다항식 근을 찾는 것은 역사를 통틀어 많은 연구의 대상이 된 오래된 문제입니다.이에 대한 증거는 19세기까지 대수학이 다항식의 이론을 의미했다는 것입니다.

고차원에서 뿌리 찾기

이등분 방법은 더 높은 차원으로 일반화되었습니다. 이러한 방법을 일반화된 이등분 방법이라고 합니다.^[2]^[3]각 반복 시 도메인은 두 부분으로 분할되며 알고리즘은 적은 수의 함수 평가를 기반으로 이 두 부분 중 어떤 부분이 루트를 포함해야 하는지 결정합니다.일 차원에서, 결정 기준은 함수에 반대 부호가 있다는 것입니다.방법을 여러 차원으로 확장하는 데 있어 주요 과제는 쉽게 계산할 수 있는 기준을 찾는 것이며, 루트의 존재를 보장하는 것입니다.

푸앵카레-미란다 정리는 직사각형에 근이 존재하는지에 대한 기준을 제공하지만 삼각형의 전체 경계에서 함수를 평가해야 하기 때문에 확인하기가 어렵습니다.

또 다른 기준은 크로네커의 정리에 의해 주어집니다.^[4]직사각형에 대한 함수 f의 위상차가 0이 아닌 경우, 직사각형은 적어도 하나의 루트 off를 포함해야 합니다.이 기준은 Stenger^[5] 및 Kearfott와 같은 여러 근찾기 방법의 기초가 됩니다.^[6]그러나 위상학적 정도를 계산하는 것은 시간이 많이 걸릴 수 있습니다.

세 번째 기준은 특성 다면체를 기준으로 합니다.이 기준은 특성 이분법이라는 방법으로 사용됩니다.^[2]^{: 19--}위상차를 계산할 필요는 없으며 함수 값의 부호만 계산하면 됩니다.필요한 평가 수는 최소 $\log _{2}(D/\epsilon )$ 2 ⁡ $\log _{2}(D/\epsilon )$ ( $\log _{2}(D/\epsilon )$ / ϵ $\log _{2}(D/\epsilon )$ ) $\log _{2}(D/\epsilon )$ {\ $displaystyle \log _{2}(D/\epsilon )}$ 이며 $\log _{2}(D/\epsilon )$ 여기서 D는 특성 다면체의 가장 긴 모서리의 길이입니다.상한이 아니라 평가 횟수의 하한을 증명합니다.

네 번째 방법은 단순화에 중간값 정리를 사용합니다.^[8]다시 말하지만, 쿼리 수에 대한 상한은 주어지지 않습니다.

참고 항목

Broyden의 방법 – 다변수 사례에 대한 준-뉴턴 근찾기 방법

암호학적으로 안전한 의사 난수 생성기 – 루트 찾기 알고리즘으로 해결할 수 없도록 설계된 함수 유형
GNU 과학 도서관
Graffe의 방법 – 다항식 근을 찾는 알고리즘
Lill's method – 다항식의 실수에 대한 그래픽 방법
Msolve – 임의로 높은 정밀도로 다항식의 근을 근사화하는 소프트웨어
다중도(수학) – 일반 공식을 참으로 만들기 위해 개체를 세야 하는 횟수
n번째 루트 알고리즘
다항식 체계 – 다변량 다항식의 근
칸토로비치 정리 – 뉴턴 방법의 수렴에 대하여

참고문헌

^ Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P. (2007). "Chapter 9. Root Finding and Nonlinear Sets of Equations". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.
^ ^a ^b Mourrain, B.; Vrahatis, M. N.; Yakoubsohn, J. C. (2002-06-01). "On the Complexity of Isolating Real Roots and Computing with Certainty the Topological Degree". Journal of Complexity. 18 (2): 612–640. doi:10.1006/jcom.2001.0636. ISSN 0885-064X.
^ Vrahatis, Michael N. (2020). Sergeyev, Yaroslav D.; Kvasov, Dmitri E. (eds.). "Generalizations of the Intermediate Value Theorem for Approximating Fixed Points and Zeros of Continuous Functions". Numerical Computations: Theory and Algorithms. Lecture Notes in Computer Science. Cham: Springer International Publishing. 11974: 223–238. doi:10.1007/978-3-030-40616-5_17. ISBN 978-3-030-40616-5. S2CID 211160947.
^ "Iterative solution of nonlinear equations in several variables". Guide books. Retrieved 2023-04-16.
^ Stenger, Frank (1975-03-01). "Computing the topological degree of a mapping inRn". Numerische Mathematik. 25 (1): 23–38. doi:10.1007/BF01419526. ISSN 0945-3245. S2CID 122196773.
^ Kearfott, Baker (1979-06-01). "An efficient degree-computation method for a generalized method of bisection". Numerische Mathematik. 32 (2): 109–127. doi:10.1007/BF01404868. ISSN 0029-599X. S2CID 122058552.
^ ^a ^b Vrahatis, M. N.; Iordanidis, K. I. (1986-03-01). "A rapid Generalized Method of Bisection for solving Systems of Non-linear Equations". Numerische Mathematik. 49 (2): 123–138. doi:10.1007/BF01389620. ISSN 0945-3245.
^ Vrahatis, Michael N. (2020-04-15). "Intermediate value theorem for simplices for simplicial approximation of fixed points and zeros". Topology and its Applications. 275: 107036. doi:10.1016/j.topol.2019.107036. ISSN 0166-8641.

추가열람

J.M. McNamee: "다항식의 근에 대한 수치적 방법 - 제1부", Elsevier (2007).
J.M. McNamee and Victor Pan: "다항식의 근에 대한 수치적 방법 - Part II", Elsevier (2013).

[1] Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P. (2007). "Chapter 9. Root Finding and Nonlinear Sets of Equations". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.

[:0-2] Mourrain, B.; Vrahatis, M. N.; Yakoubsohn, J. C. (2002-06-01). "On the Complexity of Isolating Real Roots and Computing with Certainty the Topological Degree". Journal of Complexity. 18 (2): 612–640. doi:10.1006/jcom.2001.0636. ISSN 0885-064X.

[3] Vrahatis, Michael N. (2020). Sergeyev, Yaroslav D.; Kvasov, Dmitri E. (eds.). "Generalizations of the Intermediate Value Theorem for Approximating Fixed Points and Zeros of Continuous Functions". Numerical Computations: Theory and Algorithms. Lecture Notes in Computer Science. Cham: Springer International Publishing. 11974: 223–238. doi:10.1007/978-3-030-40616-5_17. ISBN 978-3-030-40616-5. S2CID 211160947.

[4] "Iterative solution of nonlinear equations in several variables". Guide books. Retrieved 2023-04-16.

[5] Stenger, Frank (1975-03-01). "Computing the topological degree of a mapping inRn". Numerische Mathematik. 25 (1): 23–38. doi:10.1007/BF01419526. ISSN 0945-3245. S2CID 122196773.

[6] Kearfott, Baker (1979-06-01). "An efficient degree-computation method for a generalized method of bisection". Numerische Mathematik. 32 (2): 109–127. doi:10.1007/BF01404868. ISSN 0029-599X. S2CID 122058552.

[:2-7] Vrahatis, M. N.; Iordanidis, K. I. (1986-03-01). "A rapid Generalized Method of Bisection for solving Systems of Non-linear Equations". Numerische Mathematik. 49 (2): 123–138. doi:10.1007/BF01389620. ISSN 0945-3245.

[8] Vrahatis, Michael N. (2020-04-15). "Intermediate value theorem for simplices for simplicial approximation of fixed points and zeros". Topology and its Applications. 275: 107036. doi:10.1016/j.topol.2019.107036. ISSN 0166-8641.

[1]

[2]

[3]

[4]

[5]

[6]

[8]

v t 루트 찾기 알고리즘
브래킷(도함수 없음)	이등분법 레굴라푸시 ITP 방식
뉴턴 경이다.	뉴턴 방법
준뉴턴	멀러법 세컨트법
혼합법	브렌트법 라이더즈 메소드
다항식 방법	베어스토의 방법 젠킨스-트라우브 방법 라게르법

Search