Русская Википедия:Метод Мюллера
Метод Мюллера — итерационный численный метод для решения уравнения <math>f(x)=0</math> непрерывной функции. Был представлен Давидом Мюллером в 1956 году.
Метод Мюллера развивает идею метода секущих, который строит на каждом шаге итерации прямые, проходящие через две точки на графике y = f(x). Вместо этого метод Мюллера использует три точки, строит параболу, проходящую через эти три точки, и в качестве следующего приближения берёт точку пересечения параболы и оси x.
Рекуррентная формула
Три изначально необходимых значения обозначаются как xk, xk−1 и xk−2. Парабола, проходящая через три точки (xk, f(xk)), (xk−1, f(xk−1)) и (xk−2, f(xk−2)) по формуле Ньютона записывается следующим образом
- <math>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}],</math>
где f[xk, xk−1] и f[xk, xk−1, xk−2] суть разделённые разности. Это уравнение можно переписать в виде
- <math>y = f(x_k) + w(x - x_k) + f[x_k, x_{k-1}, x_{k-2}] \, (x - x_k)^2,</math>
где
- <math>w = f[x_k, x_{k-1}] + f[x_k, x_{k-2}] - f[x_{k-1}, x_{k-2}].</math>
Следующая итерация даёт корень квадратного уравнения y = 0. Из этого выходит рекуррентная формула
- <math>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}]}}.</math>
В этой формуле знак выбирается таким образом, чтобы знаменатель был больше по абсолютной величине. Стандартная формула для решения квадратных уравнений не используется, так как это может привести к потере значимых разрядов.
Приближение xk+1 может быть комплексным числом, даже если все предыдущие приближения были вещественными, в отличие от других алгоритмов численного поиска корней (метод секущих или метод Ньютона), где приближения будут оставаться вещественными, если начинать с вещественного числа. Наличие комплексных итераций может быть как преимуществом (если ищется комплексный корень), так и недостатком (если известно, что все корни вещественные).
Скорость сходимости
Скорость сходимости метода Мюллера составляет примерно 1,84. Её можно сравнить с 1,62 для метода секущих и 2 для метода Ньютона. Таким образом, метод секущих будет выполняться за большее число шагов, чем метод Мюллера и метод Ньютона.
Точнее, если <math>\xi</math> обозначает не кратный корень <math>f</math> (то есть <math>f(\xi) = 0,\ f'(\xi) \neq 0)</math>, <math>f</math> трижды непрерывно дифференцируема, и начальные приближения <math>x_0</math>, <math>x_1</math>, и <math>x_2</math> были достаточно близки к <math>\xi</math>, то итерации удовлетворяют соотношению
- <math>\lim_{k \to \infty} \frac{|x - x_k|}{|x - x_{k-1}|^p} = \left| \frac{f(\xi)}{6f'(\xi)} \right|^{(p-1)/2},</math>
где p ≈ 1,84 это положительный корень уравнения <math>x^3 - x^2 - x - 1 = 0</math>.
Литература
- 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.
См. также
- Метод секущих
- Обратная параболическая интерполяция
- Метод Ньютона
- Метод хорд
- Метод дихотомии
- Численное решение уравнений
Ссылки
