Метод Мюллера - Mullers method

Метод Мюллера это алгоритм поиска корней, а числовой метод решения уравнений вида ж(Икс) = 0. Впервые он был представлен Дэвид Э. Мюллер в 1956 г.

Метод Мюллера основан на секущий метод, который на каждой итерации строит линию через две точки на графике ж. Вместо этого метод Мюллера использует три точки, строит парабола через эти три точки и пересекает Икс-ось с параболой в качестве следующего приближения.

Отношение рецидива

Метод Мюллера - это рекурсивный метод, который генерирует приближение корень ξ из ж на каждой итерации. Начиная с трех начальных значений Икс₀, Икс₋₁ и Икс₋₂, первая итерация вычисляет первое приближение Икс₁, вторая итерация вычисляет второе приближение Икс₂, третья итерация вычисляет третье приближение Икс₃и т. д. Следовательно k^th итерация генерирует приближение Икс_k. Каждая итерация принимает в качестве входных данных три последних сгенерированных приближения и значение ж в этих приближениях. Следовательно k^th итерация принимает на входе значения Икс_k-1, Икс_k-2 и Икс_k-3 и значения функции ж(Икс_k-1), ж(Икс_k-2) и ж(Икс_k-3). Приближение Икс_k рассчитывается следующим образом.

Парабола у_k(Икс), проходящая через три точки (Икс_k-1, ж(Икс_k-1)), (Икс_k-2, ж(Икс_k-2)) и (Икс_k-3, ж(Икс_k-3)). Когда написано в Форма Ньютона, у_k(Икс) является

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

куда ж[Икс_k-1, Икс_k-2] и ж[Икс_k-1, Икс_k-2, Икс_k-3] обозначают разделенные различия. Это можно переписать как

${\displaystyle y_{k}(x)=f(x_{k-1})+w(x-x_{k-1})+f[x_{k-1},x_{k-2},x_{k-3}]\,(x-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}].\,}$

Следующая итерация Икс_k теперь дается как решение, наиболее близкое к Икс_k-1 квадратного уравнения у_k(Икс) = 0. Это дает отношение повторения

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

В этой формуле знак следует выбирать так, чтобы знаменатель был как можно большим по величине. Мы не используем стандартную формулу для решения квадратные уравнения потому что это может привести к потеря значимости.

Обратите внимание, что Икс_k может быть сложным, даже если все предыдущие итерации были реальными. Это контрастирует с другими алгоритмами поиска корней, такими как секущий метод, Обобщенный метод секущих Сиди или же Метод Ньютона, чьи итерации останутся реальными, если начать с действительных чисел. Наличие сложных итераций может быть преимуществом (если кто-то ищет сложные корни) или недостатком (если известно, что все корни действительны), в зависимости от проблемы.

Скорость схождения

В порядок сходимости метода Мюллера составляет примерно 1,84. Это можно сравнить с 1,62 для секущий метод и 2 для Метод Ньютона. Таким образом, метод секущей дает меньший прогресс за итерацию, чем метод Мюллера и метод Ньютона.

Точнее, если ξ обозначает единственный корень ж (так ж(ξ) = 0 и ж'(ξ) ≠ 0), ж трижды непрерывно дифференцируема, и начальные предположения Икс₀, Икс₁, и Икс₂ взяты достаточно близкими к ξ, то итерации удовлетворяют

${\displaystyle \lim _{k\to \infty }{\frac {|x_{k}-\xi |}{|x_{k-1}-\xi |^{\mu }}}=\left|{\frac {f'''(\xi )}{6f'(\xi )}}\right|^{(\mu -1)/2},}$

где μ ≈ 1,84 - положительное решение ${\displaystyle x^{3}-x^{2}-x-1=0}$.

Обобщения и родственные методы

Метод Мюллера соответствует параболе, т.е. многочлен, к последним трем полученным точкам ж(Икс_k-1), ж(Икс_k-2) и ж(Икс_k-3) на каждой итерации. Можно обобщить это и подобрать многочлен п_{k, м}(Икс) из степень м до конца м+1 балл в k^th итерация. Наша парабола у_k записывается как п_k,2 в этих обозначениях. Степень м должно быть 1 или больше. Следующее приближение Икс_k сейчас один из корней п_{k, м}, т.е. одно из решений п_{k, м}(Икс) = 0. Принимая м= 1 получаем метод секущих, тогда как м= 2 дает метод Мюллера.

Мюллер подсчитал, что последовательность {Икс_k}, сходится к корню ξ с порядком μ_м где μ_м положительное решение ${\displaystyle x^{m+1}-x^{m}-x^{m-1}-\dots -x-1=0}$.

Однако этот метод намного сложнее для м> 2, чем для м= 1 или м= 2, потому что намного сложнее определить корни многочлена степени 3 или выше. Другая проблема заключается в том, что, похоже, нет рецепта, какой из корней п_{k, м} выбрать в качестве следующего приближения Икс_k за м>2.

Эти трудности преодолеваются Обобщенный метод секущих Сиди в котором также используется полином п_{k, м}. Вместо того, чтобы пытаться решить п_{k, м}(Икс) = 0, следующее приближение Икс_k вычисляется с помощью производной от п_{k, м} в Икс_k-1 в этом методе.

Рекомендации

• Мюллер, Дэвид Э., "Метод решения алгебраических уравнений с помощью автоматического компьютера", Математические таблицы и другие вспомогательные средства для вычислений, 10 (1956), 208-215. JSTOR  2001916
• Аткинсон, Кендалл Э. (1989). Введение в численный анализ, 2-е издание, раздел 2.4. John Wiley & Sons, Нью-Йорк. ISBN  0-471-50023-2.
• Бэрден, Р. Л. и Фейрес, Дж. Д. Числовой анализ, 4-е издание, стр. 77ff.
• Нажмите, WH; Теукольский С.А.; Феттерлинг, штат Вашингтон; Фланнери, ВР (2007). «Раздел 9.5.2. Метод Мюллера». Числовые рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN  978-0-521-88068-8.