Метод Мюллера — итерационный численный метод для решения уравнения ${\displaystyle 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} )) по формуле Ньютона записывается следующим образом

${\displaystyle 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} ] суть разделённые разности . Это уравнение можно переписать в виде

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

где

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

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

${\displaystyle 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 для метода Ньютона. Таким образом, метод секущих будет выполняться за большее число шагов, чем метод Мюллера и метод Ньютона.

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

${\displaystyle \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 это положительный корень уравнения ${\displaystyle 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 .

См. также

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

Ссылки

• (англ.)