뮬러의 방법

이 글에는 참고문헌, 관련 독서 또는 외부 링크 목록이 수록되어 있으나 인라인 인용구가 부족하여 출처가 불분명하다. 보다 정확한 인용문을 도입하여 이 기사를 개선할 수 있도록 도와주십시오. (2020년 2월) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

뮬러의 방법은 f(x) = 0 형식의 방정식을 풀기 위한 숫자 방법인 뿌리 찾기 알고리즘. 데이비드 E가 처음 제시한 것이다. 1956년 뮬러

뮬러의 방법은 f의 그래프에 있는 두 점을 통과하는 선을 반복할 때마다 구성하는 제2의 방법에 기초한다.대신 뮬러의 방법은 세 점을 사용하고, 이 세 점을 통해 포물선을 구성하고, 포물선과 X축의 교차점을 다음 근사치로 삼는다.

재발관계

뮬러의 방법은 각 반복에서 f의 루트 ξ의 근사치를 생성하는 재귀적 방법이다.초기값 x₀, x₋₁, x부터₋₂ 첫 번째 반복은 첫 번째 근사치 x를₁ 계산하고, 두 번째 반복은 두 번째 근사치₂ x를 계산하며, 세 번째 반복은 세 번째 근사치₃ x 등을 계산한다.따라서 k^th 반복은 근사 x를_k 생성한다. 각 반복은 이 근사치에서 마지막으로 생성된 근사치 3개와 f 값을 입력으로 사용한다.따라서 k^th 반복은 x_k-1, x_k-2 및 f_k-3(x_k-1), f(x_k-2), f(x) 및 f(x_k-3) 값을 입력하는 것으로 간주한다.근사 x는_k 다음과 같이 계산한다.

포물선 y_k(x)는 세 점(x_k-1, f(x_k-1), (x_k-2, f(x_k-2)) 및 (x_k-3, f(x_k-3))을 통과하는 포물선 y(x)가 생성된다.뉴턴 양식에 쓰여 있을 때 y_k(x)는

${\displaystyle y_{k}(x)=f(x_{k-1})+(x-x_{k-1}f[x_{k-2}]+(x-_{k-2})+(x-_{k-1}f[x_{k-1},x_{k-2},x_{k-3}),\},},},},}$

여기서 f[x_k-1, x_k-2]와 f[x_k-1, x_k-2, x_k-3]는 분단된 차이를 나타낸다.이것은 다음과 같이 다시 쓰여질 수 있다.

${\displaystyle y_{k-1}(x)=f(x_{k-1})+w(x-x_{k-1}+f[x_{k-1},x_{k-2},x_{k-3}]\,(x_{k-1})^{2},}$

어디에

${\displaystyle w=f[x_{k-1},x_{k-2}]+f[x_{k-1},x_{k-3}]-f[x_{k-2},x_{k-3}]]\,}$

다음 반복 x는_k 이제 2차 방정식_k y(x) = 0의_k-1 x에 가장 가까운 해법으로 주어진다. 이것은 재발 관계를 산출한다.

${\displaystyle x_{k}=x_{k-1}-{\frac {2f(x_{k-1})-{w\pm {w^{2}-4f(x_{k-1}f[x_{k-1}}f[x_{k-1}}},x_{k-3}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}.}$

이 공식에서 부호는 분모가 가능한 크기만큼 크도록 선택해야 한다.우리는 2차 방정식을 푸는 데 표준 공식을 사용하지 않는다. 왜냐하면 그것이 유의성의 상실을 초래할 수 있기 때문이다.

x는_k 이전의 반복이 모두 실제였더라도 복잡할 수 있다는 점에 유의하십시오.이는 시던의 일반화된 시던트 방식이나 뉴턴의 방식과 같은 다른 뿌리 찾기 알고리즘과는 대조적인데, 이 알고리즘은 한 사람이 실수로 시작하면 그 반복이 현실로 유지된다.복잡한 이터레이트를 갖는 것은 문제에 따라 장점(복잡한 뿌리를 찾는 경우)이나 단점(모든 뿌리가 진짜라고 알려진 경우)이 될 수 있다.

수렴 속도

뮬러의 방법의 수렴 순서는 대략 1.84이다.이것은 제분법의 경우 1.62와 뉴턴의 방법의 경우 2와 비교할 수 있다.그래서 세컨트 방법은 뮬러의 방법보다 반복당 진척이 적고 뉴턴의 방법으로는 진보가 더 많이 된다.

더 정확히 말하면, ξ이 f의 단일 루트를 나타내는 경우(소 f(() = 0과 f'(ξ) ≠ 0), f는 연속적으로 3배 차이가 있으며, 초기 추측 x₀, x₁, x가₂ ξ에 충분히 가깝게 취해진다면, 이서레이트는 만족한다.

${\displaystyle \lim_{k\to \inflit }{\frac {x_{k}-\xi ^-\xi ^{\f-1}=\좌측 {\frac {f'(\xi )}}}{6f'(\xi )}}\오른쪽 ^{{(\mu -1)/2}}}$

여기서 μ μ μ μ 1.84는 ${\displaystyle {x\mathrm{}}^{}}$ $3{\displaystyle {}^{}}$- ${\displaystyle x{2\mathrm{}}^{}}$- ${\displaystyle \mathrm{x}}$ - ${\displaystyle 1}$= 0 ${\displaystyle x^{3}-x^{2}-x-1=0}$의 양용액이다$.$

일반화 및 관련 방법

뮬러의 방법은 포물선(즉, 2차 다항식)을 각 반복에서 얻은 마지막 세 점 f(x_k-1), f(x_k-2) 및 f(x_k-3)에 적합시킨다.이를 일반화할 수 있고 k^th 반복의 마지막 m+1 지점에 도 m의 다항식 p_k,m(x)를 맞출 수 있다.우리의 포물선 y는_k 이 표기법에 p로_k,2 표기되어 있다.도 m은 1 이상이어야 한다.다음 근사 x는_k 이제 p의_k,mk,m 뿌리, 즉 p(x)=0의 해결책의 하나이다.m=1을 취하면 secant method를 얻는 반면 m=2는 뮬러의 method를 준다.

뮬러는_m 이 방법으로 생성된 시퀀스 {x_k}이(가) x m +${\displaystyle {\mathrm{1_<i>m</i>}}^{}}$ -${\displaystyle {}^{}}$x ${\displaystyle {}^{}}$ -${\displaystyle 1^{}}$ -${\displaystyle {\mathrm{\mu }}^{}}$ -${\displaystyle x}$ m - 1 - x - x${\displaystyle }$- ${\displaystyle 1}$= ${\displaystyle 0}$의 양의$$용액인 $xm^{m+1}-x^{m-1$}-$x^{m-1-\dots -x-1=0}$을(으)로 수렴한다고 계산했다$.$

m>>2의 경우는 m=1이나 m=2의 경우보다 훨씬 어렵지만, 그 방법은 3도 이상의 다항식의 뿌리를 결정하는 것이 훨씬 어렵기 때문이다.또 다른 문제는 m>2의 다음 근사 x로_k 선택할 p의_k,m 뿌리에 대한 처방이 없어 보인다는 점이다.

이러한 어려움은 다항식 p를_k,m 채용하는 Sidi의 일반화된 secant 방법에 의해 극복된다.p_k,m(x)=0을 해결하려고 하는 대신, 다음 근사 x는_k 이 방법에서 p_k,m at x의_k-1 파생상품의 도움을 받아 계산한다.

계산 예제

아래에서 뮬러의 방법은 파이톤 프로그래밍 언어로 구현된다.그런 다음 f(x) = x² - 612 함수의 루트를 찾기 위해 적용한다.

로부터 타자 치기 수입하다 * 로부터 cmath 수입하다 sqrt  # 복잡한 숫자를 생성할 수 있으므로 복합 sqrt를 사용하십시오.  숫자 = 유니온[둥둥 뜨다, 복합적인] 펑크 = 호출 가능[[숫자], 숫자]   반항하다 div_div(f: 펑크, xs: 리스트[숫자]):     """분할된 차이 f[x0, x1, ...]를 계산하십시오."     만일 렌(xs) == 2:         a, b = xs         돌아오다 (f(a) - f(b)) / (a - b)     다른:         돌아오다 (div_div(f, xs[1:]) - div_div(f, xs[0:-1])) / (xs[-1] - xs[0])   반항하다 mullers_message(f: 펑크, xs: (숫자, 숫자, 숫자), 반복해서: 인트로) -> 둥둥 뜨다:     """뮬러의 방법을 사용하여 계산된 루트를 반환한다."""     x0, x1, x2 = xs     을 위해 _ 에 범위(반복해서):         w = div_div(f, (x2, x1)) + div_div(f, (x2, x0)) - div_div(f, (x2, x1))         s_s. = sqrt(w ** 2 - 4 * f(x2) * div_div(f, (x2, x1, x0)))         데님스 = [w + s_s., w - s_s.]         # 규모 높은 분모 찍기         x3 = x2 - 2 * f(x2) / 맥스.(데님스, 핵심을=복근)         # 진전         x0, x1, x2 = x1, x2, x3     돌아오다 x3   반항하다 f_message(x: 숫자) -> 숫자:     """"예시함수.더 비싼 기능으로는, 마지막으로 호출된 4개의 포인트의 메모가 유용할 수 있다."""     돌아오다 x ** 2 - 612   뿌리를 내리다 = mullers_message(f_message, (10, 20, 30), 5) 인쇄하다("루트:{}".형식을 갖추다(뿌리를 내리다))  # 루트 : (24.738633317099097+0j) 

참조

• Muller, David E, "자동 컴퓨터를 이용한 대수 방정식 해결 방법," 수학 표와 기타 연산 보조 도구, 10 (1956), 208-215. JSTOR 2001916
• 앳킨슨, 켄달 E. (1989년).수치해석에 대한 소개, 제2판 제2.4절.뉴욕 주, 존 와일리 & 선즈. ISBN0-471-50023-2.
• 짐, R. L.와 Fans, J. D.수치 분석, 제4판 77쪽
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 9.5.2. Muller's Method". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.

추가 읽기

• 글로벌 컨버전스 기능이 있는 브래킷링 모델: