Метод Мюллера (Bymk; BZllyjg)

Метод Мюллера — итерационный численный метод для решения уравнения $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 (англ.)