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

Метод Мюллераитерационный численный метод для решения уравнения непрерывной функции. Был представлен Давидом Мюллером в 1956 году.

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

Рекуррентная формулаПравить

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

 

где f[xkxk−1] и f[xk, xk−1, xk−2] суть разделённые разности. Это уравнение можно переписать в виде

 

где

 

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

 

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

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

Скорость сходимостиПравить

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

Точнее, если   обозначает не кратный корень   (то есть  ,   трижды непрерывно дифференцируема, и начальные приближения  ,  , и   были достаточно близки к  , то итерации удовлетворяют соотношению

 

где p ≈ 1,84 это положительный корень уравнения  .

ЛитератураПравить

  • 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.

См. такжеПравить

СсылкиПравить