Метод Мюллера - это алгоритм поиска корней , численный метод решения уравнений вида f ( x ) = 0. Впервые он был представлен Дэвидом Э. Мюллером в 1956 году.
Метод Мюллера основан на методе секущих , который на каждой итерации строит линию, проходящую через две точки на графике f . Вместо этого метод Мюллера использует три точки, строит параболу через эти три точки и принимает пересечение оси x с параболой в качестве следующего приближения.
Отношение повторения
Метод Мюллера - это рекурсивный метод, который генерирует приближение корня ξ функции f на каждой итерации. Начиная с трех начальных значений x 0 , x −1 и x −2 , первая итерация вычисляет первое приближение x 1 , вторая итерация вычисляет второе приближение x 2 , третья итерация вычисляет третье приближение x 3 и т. Д. к - й итерации порождает приближение х к . Каждая итерация принимает в качестве входных данных три последних сгенерированных приближения и значение f в этих приближениях. Следовательно, k- я итерация принимает на входе значения x k -1 , x k -2 и x k -3, а также значения функций f ( x k -1 ), f ( x k -2 ) и f ( x k -3. ). Приближение x k вычисляется следующим образом.
Строится парабола y k ( x ), проходящая через три точки ( x k -1 , f ( x k -1 )), ( x k -2 , f ( x k -2 )) и ( x k -3 , f ( x k -3 )). Когда записано в форме Ньютона , y k ( x ) есть
где f [ x k -1 , x k -2 ] и f [ x k -1 , x k -2 , x k -3 ] обозначают разделенные разности . Это можно переписать как
где
Следующая итерация x k теперь задается как решение, наиболее близкое к x k -1 квадратного уравнения y k ( x ) = 0. Это дает рекуррентное соотношение
В этой формуле следует выбирать такой знак, чтобы знаменатель был как можно большим по величине. Мы не используем стандартную формулу для решения квадратных уравнений, потому что это может привести к потере значимости .
Обратите внимание, что x k может быть комплексным, даже если все предыдущие итерации были действительными. Это контрастирует с другими алгоритмами поиска корней, такими как метод секущей , обобщенный метод секущей Сиди или метод Ньютона , итерации которых останутся действительными, если начать с действительных чисел. Наличие сложных итераций может быть преимуществом (если кто-то ищет сложные корни) или недостатком (если известно, что все корни действительны), в зависимости от проблемы.
Скорость сходимости
Порядок сходимости методы Мюллера составляет примерно 1,84. Это можно сравнить с 1,62 для метода секущих и 2 для метода Ньютона . Таким образом, метод секущей достигает меньшего прогресса за итерацию, чем метод Мюллера, а метод Ньютона - больше.
Точнее, если ξ обозначает единственный корень f (так что f (ξ) = 0 и f '(ξ) ≠ 0), f трижды непрерывно дифференцируемо, а начальные предположения x 0 , x 1 и x 2 равны взято достаточно близко к ξ, то итерации удовлетворяют
где μ ≈ 1,84 - положительное решение .
Метод Мюллера подбирает параболу, то есть полином второго порядка , к последним трем полученным точкам f ( x k -1 ), f ( x k -2 ) и f ( x k -3 ) на каждой итерации. Можно обобщить это и подогнать полином p k, m ( x ) степени m к последним m +1 точкам на k- й итерации. Наша парабола y k записывается в этих обозначениях как p k , 2 . Степень m должна быть 1 или больше. Следующее приближение x k теперь является одним из корней p k, m , то есть одним из решений p k, m ( x ) = 0. Принимая m = 1, мы получаем метод секущих, тогда как m = 2 дает метод Мюллера.
Мюллер вычислил, что сгенерированная таким образом последовательность { x k } сходится к корню ξ с порядком μ m, где μ m - положительное решение уравнения.
Однако этот метод намного сложнее для m > 2, чем для m = 1 или m = 2, потому что намного сложнее определить корни многочлена степени 3 или выше. Другая проблема заключается в том, что, похоже, нет рецепта, какой из корней p k, m выбрать в качестве следующего приближения x k для m > 2.
Эти трудности преодолеваются с помощью обобщенного метода секущих Сиди, который также использует полином p k, m . Вместо попытки решить p k, m ( x ) = 0, следующее приближение x k вычисляется с помощью производной p k, m в x k -1 в этом методе.
Рекомендации
- Мюллер, Дэвид Э., "Метод решения алгебраических уравнений с помощью автоматического компьютера", " Математические таблицы и другие средства вычислений" , 10 (1956), 208-215. JSTOR 2001916
- Аткинсон, Кендалл Э. (1989). Введение в численный анализ , 2-е издание, раздел 2.4. John Wiley & Sons, Нью-Йорк. ISBN 0-471-50023-2 .
- Бэрден, Р.Л. и Фейрес, Д.Д. Численный анализ , 4-е издание, стр. 77ff.
- Нажмите, WH; Теукольский, С.А. Феттерлинг, Вашингтон; Фланнери, ВР (2007). «Раздел 9.5.2. Метод Мюллера» . Числовые рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN 978-0-521-88068-8.