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

Метод Мюллера — итерационный численный метод для решения уравнения $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^{\prime }(\xi )\ne 0)$, $f$ трижды непрерывно дифференцируема, и начальные приближения $x_0$, $x_1$, и $x_2$ были достаточно близки к $\xi$, то итерации удовлетворяют соотношению

$\underset{k\to \mathrm{\infty }}{\lim }\frac{|x-x_k|}{|x-x_{k-1}{|}^p}={\left|\frac{f^{‴}(\xi )}{6f^{\prime }(\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Шаблон:Ref-en