WikiSort.ru - Не сортированное

Метод Мюллера — итерационный численный метод для решения уравнения ${\displaystyle f(x)=0}$ непрерывной функции. Был представлен Давидом Мюллером в 1956 году.

Метод Мюллера развивает идею метода секущих, который строит на каждом шаге итерации прямые, проходящие через две точки на графике f. Вместо этого, метод Мюллера использует три точки, строит параболу, проходящую через эти три точки, и в качестве следующего приближения берёт точку пересечения параболы и оси 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.

См. также

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

Ссылки

• Модуль для метода Мюллера от John H. Mathews (недоступная ссылка) (англ.)