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

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

Метод Мюллера развивает идею метода секущих, который строит на каждом шаге итерации прямые, проходящие через две точки на графике y = f(x). Вместо этого метод Мюллера использует три точки, строит параболу, проходящую через эти три точки, и в качестве следующего приближения берёт точку пересечения параболы и оси 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 для метода Ньютона. Таким образом, метод секущих будет выполняться за большее число шагов, чем метод Мюллера и метод Ньютона.

Точнее, если $\xi$ обозначает не кратный корень $f$ (то есть $f(\xi )=0,\ f'(\xi )\neq 0)$, $f$ трижды непрерывно дифференцируема, и начальные приближения $x_{0}$, $x_{1}$, и $x_{2}$ были достаточно близки к $\xi$, то итерации удовлетворяют соотношению

$\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 (англ.)