Метод Мюллера

Метод Мюллера — итерационный численный метод для вычисления корня заданной функции f(x) = 0. Был представлен Давидом Мюллером в 1956 году.

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

Рекуррентная формула

Три изначально необходимых значения обозначаются как x_k, x_k-1 и x_k-2. Парабола, проходящая через три точки (x_k, f(x_k)), (x_k-1, f(x_k-1)) и (x_k-2, f(x_k-2)), при записи в формуле Ньютона, является

$y = f(x_k) + (x-x_k) f[x_k, x_{k-1}] + (x-x_k) (x-x_{k-1}) f[x_k, x_{k-1}, x_{k-2}], \,$

где f[x_k, x_k-1] и f[x_k, x_k-1, x_k-2] обозначим разделённой разностью. Тогда уравнение можно переписать в виде

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

где

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

Следующая итерация даёт корень квадратного уравнения y = 0. Из этого выходит рекуррентная формула

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

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

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

Скорость сходимости

Скорость сходимости метода Мюллера составляет примерно 1.84. Её можно сравнить с 1.62 для метода секущих и 2 для метода Ньютона. Таким образом, метод секущих будет выполнятся за большее число шагов, чем метод Мюллера и метод Ньютона.

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

$\lim_{k\to\infty} \frac{|x-x_k|}{|x-x_{k-1}|^p} = \left| \frac{f'''(\xi)}{6f'(\xi)} \right|^{(p-1)/2},$

где p ≈ 1.84 это положительный корень уравнения $x^3 - x^2 - x - 1 = 0$.

Литература

• Muller, David E., "A Method for Solving Algebraic Equations Using an Automatic Computer," MTAC, 10 (1956), 208-215.
• Atkinson, Kendall E. (1989). An Introduction to Numerical Analysis, 2nd edition, Section 2.4. John Wiley & Sons, New York. ISBN 0-471-50023-2.
• Burden, R. L. and Faires, J. D. Numerical Analysis, 4th edition, pages 77ff.
• Press, William H., et al. (1992). Numerical Recipes in Fortran 77: The Art of Scientific Computing, 2nd edition, page 364. ISBN 0-521-43064-X.

См. также

• Метод секущих
• Метод Ньютона
• Метод хорд
• Метод дихотомии
• Численное решение уравнений

Ссылки

• Модуль для метода Мюллера от John H. Mathews (англ.)