- Метод Ньютона-Рафсона
-
Метод Ньютона (также известный как метод касательных) — это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727), под именем которого и обрёл свою известность. Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Улучшением метода является метод хорд и касательных. Также метод Ньютона может быть использован для решения задач оптимизации, в которых требуется определить нуль первой производной либо градиента в случае многомерного пространства.
Содержание
Описание метода
Обоснование
Чтобы численно решить уравнение методом простой итерации, его необходимо привести к следующей форме: , где — сжимающее отображение.
Для наилучшей сходимости метода в точке очередного приближения должно выполняться условие . Решение данного уравнения ищут в виде , тогда:
В предположении, что точка приближения «достаточно близка» к корню , и что заданная функция непрерывна , окончательная формула для такова:
С учётом этого функция определяется выражением:
Эта функция в окрестности корня осуществляет сжимающее отображение[1], и алгоритм нахождения численного решения уравнения сводится к итерационной процедуре вычисления:
По теореме Банаха последовательность приближений стремится к корню уравнения .
Геометрическая интерпретация
Основная идея метода заключается в следующем: задаётся начальное приближение вблизи предположительного корня, после чего строится касательная к исследуемой функции в точке приближения, для которой находится пересечение с осью абсцисс. Эта точка и берётся в качестве следующего приближения. И так далее, пока не будет достигнута необходимая точность.
Пусть — определённая на отрезке [a, b] и дифференцируемая на нём действительнозначная функция. Тогда формула итеративного исчисления приближений может быть выведена следующим образом:
-
- ,
где α — угол наклона касательной в точке .
Следовательно искомое выражение для имеет вид:
-
- .
Итерационный процесс начинается с некого начального приближения x0 (чем ближе к нулю, тем лучше, но если предположения о нахождении решения отсутствуют, методом проб и ошибок можно сузить область возможных значений, применив теорему о промежуточных значениях).
Алгоритм
- Задаются начальным приближением x0.
- Пока не выполнено условие остановки, в качестве которого можно взять или (то есть погрешность в нужных пределах), вычисляют новое приближение: .
Пример
Иллюстрация применения метода Ньютона к функции f(x) = cosx − x3 с начальным приближением в точке x0 = 0,5. Согласно способу практического определения скорость сходимости может быть оценена как тангенс угла наклона графика сходимости, то есть в данном случае равна двум. Рассмотрим задачу о нахождении положительных x, для которых cosx = x3. Эта задача может быть представлена как задача нахождения нуля функции f(x) = cosx − x3. Имеем выражение для производной . Так как для всех x и x3 > 1 для x > 1, очевидно, что решение лежит между 0 и 1. Возьмём в качестве начального приближения значение x0 = 0,5, тогда:
Подчёркиванием отмечены верные значащие цифры. Видно, что их количество от шага к шагу растёт (приблизительно удваиваясь с каждым шагом): от 1 к 2, от 2 к 5, от 5 к 10, иллюстрируя квадратичную скорость сходимости.
Условия применения
Рассмотрим ряд примеров, указывающих на недостатки метода.
Контрпримеры
-
- Если начальное приближение недостаточно близко к решению, то метод может не сойтись.
Пусть
Тогда
Возьмём нуль в качестве начального приближения. Первая итерация даст в качестве приближения единицу. В свою очередь, вторая снова даст нуль. Метод зациклится и решение не будет найдено. В общем случае построение последовательности приближений может быть очень запутанным.
-
- Если производная не непрерывна в точке корня, то метод может расходиться в любой окрестности корня.
Рассмотрим функцию:
Тогда и всюду, кроме 0.
В окрестности корня производная меняет знак при приближении x к нулю справа или слева. В то время, как: для .
Таким образом не ограничено вблизи корня, и метод будет расходиться, хотя функция всюду дифференцируема, её производная не равна нулю в корне, бесконечно дифференцируема везде, кроме как в корне, а её производная ограничена в окрестности корня.
-
- Если не существует вторая производная в точке корня, то скорость сходимости метода может быть заметно снижена.
Рассмотрим пример:
Тогда и за исключением , где она не определена.
На очередном шаге имеем ,
Скорость сходимости полученной последовательности составляет приблизительно 4/3. Это существенно меньше, нежели 2, необходимое для квадратичной сходимости, поэтому в данном случае можно говорить лишь о линейной сходимости, хотя функция всюду непрерывно дифференцируема, производная в корне не равна нулю, и бесконечно дифференцируема везде, кроме как в корне.
-
- Если производная в точке корня равна нулю, то скорость сходимости не будет квадратичной, а сам метод может преждевременно прекратить поиск, и дать неверное для заданной точности приближение.
Пусть
Тогда и следовательно . Таким образом сходимость метода не квадратичная, а линейная, хотя функция всюду бесконечно дифференцируема.
Ограничения
Пусть задано уравнение , где и надо найти его решение.
Ниже приведена формулировка основной теоремы, которая позволяет дать чёткие условия применимости. Она носит имя советского математика и экономиста, лауреата Нобелевской премии по экономике 1975 года «за вклад в теорию оптимального распределения ресурсов» Леонида Витальевича Канторовича (1912—1986) и является одной из многочисленных теорем, ставших результатами его научных изысканий.
Теорема Канторовича.
Если существуют такие константы , что:
- на , то есть существует и не равна нулю;
- на , то есть ограничена;
- на , и ;
Причём длина рассматриваемого отрезка . Тогда справедливы следующие утверждения:
- на существует корень x * уравнения ;
- если , то итерационная последовательность сходится к этому корню: ;
- погрешность может быть оценена по формуле .
Из последнего из утверждений теоремы в частности следует квадратичная сходимость метода:
Тогда ограничения на исходную функцию будут выглядеть так:
- функция должна быть ограничена;
- функция должна быть гладкой, дважды дифференцируемой;
- её первая производная f'(x) равномерно отделена от нуля;
- её вторая производная должна быть равномерно ограничена.
Историческая справка
Метод был описан Исааком Ньютоном в рукописи De analysi per aequationes numero terminorum infinitas (лат. Об анализе уравнениями бесконечных рядов), адресованной в 1669 году Барроу, и в работе De metodis fluxionum et serierum infinitarum (лат. Метод флюксий и бесконечные ряды) или Geometria analytica (лат. Аналитическая геометрия) в собраниях трудов Ньютона, которая была написана в 1671 году. В своих работах Ньютон вводит такие понятия, как разложение функции в ряд, бесконечно малые и флюксии (производные в нынешнем понимании). Указанные работы были изданы значительно позднее: первая вышла в свет в 1711 году благодаря Уильяму Джонсону, вторая была издана Джоном Кользоном в 1736 году уже после смерти создателя. Однако описание метода существенно отличалось от его нынешнего изложения: Ньютон применял свой метод исключительно к полиномам. Он вычислял не последовательные приближения xn, а последовательность полиномов и в результате получал приближённое решение x.
Впервые метод был опубликован в трактате Алгебра Джона Валлиса в 1685 году, по просьбе которого он был кратко описан самим Ньютоном. В 1690 году Джозеф Рафсон опубликовал упрощённое описание в работе Analysis aequationum universalis (лат. Общий анализ уравнений). Рафсон рассматривал метод Ньютона как чисто алгебраический и ограничил его применение полиномами, однако при этом он описал метод на основе последовательных приближений xn вместо более трудной для понимания последовательности полиномов, использованной Ньютоном. Наконец, в 1740 году метод Ньютона был описан Томасом Симпсоном как итеративный метод первого порядка решения нелинейных уравнений с использованием производной в том виде, в котором он излагается здесь. В той же публикации Симпсон обобщил метод на случай системы из двух уравнений и отметил, что метод Ньютона также может быть применён для решения задач оптимизации путём нахождения нуля производной или градиента.
В 1879 году Артур Кэли в работе The Newton-Fourier imaginary problem (англ. Проблема комплексных чисел Ньютона-Фурье) был первым, кто отметил трудности в обобщении метода Ньютона на случай мнимых корней полиномов степени выше второй и комплексных начальных приближений. Эта работа открыла путь к изучению теории фракталов.
Обобщения и модификации
Метод одной касательной
В целях уменьшения числа обращений к значениям производной функции применяют так называемый метод одной касательной.
Формула итераций этого метода имеет вид
Суть метода заключается в том, чтобы вычислять производную лишь один раз, в точке начального приближения , а затем использовать это значение на каждой последующей итерации:
-
- .
При таком выборе в точке выполнено равенство
и если отрезок, на котором предполагается наличие корня и выбрано начальное приближение , достаточно мал, а производная непрерывна, то значение будет не сильно отличаться от и, следовательно, график пройдёт почти горизонтально, пересекая прямую , что в свою очередь обеспечит быструю сходимость последовательности точек приближений к корню.
Этот метод можно также рассматривать, как модернизацию метода хорд (секущих), где число следует выбрать равным .
Многомерный случай
Обобщим полученный результат на многомерный случай. Пускай необходимо найти решение системы:
Выбирая некоторое начальное значение , последовательные приближения находят путём решения систем уравнений:
-
- ,
где .
Применительно к задачам оптимизации
Пускай необходимо найти минимум функции многих переменных . Эта задача равносильна задаче нахождения нуля градиента . Применим изложенный выше метод Ньютона:
-
- ,
где — гессиан функции .
В более удобном итеративном виде это выражение выглядит так:
Следует отметить, что в случае квадратичной функции метод Ньютона находит экстремум за одну итерацию.
Нахождение матрицы Гессе связано с большими вычислительными затратами, и зачастую не представляется возможным. В таких случаях альтернативой могут служить квазиньютоновские методы, в которых приближение матрицы Гессе строится в процессе накопления информации о кривизне функции.
Метод Ньютона — Рафсона
Метод Ньютона-Рафсона является улучшением метода Ньютона нахождения экстремума, описанного выше. Основное отличие заключается в том, что на очередной итерации каким-либо из методов одномерной оптимизации выбирается оптимальный шаг:
-
- ,
где
Для оптимизации вычислений применяют следующее улучшение: вместо того, чтобы на каждой итерации заново вычислять гессиан целевой функции, ограничиваются начальным приближением и обновляют его лишь раз в шагов, либо не обновляют вовсе.
Применительно к задачам о наименьших квадратах
На практике часто встречаются задачи, в которых требуется произвести настройку свободных параметров объекта или подогнать математическую модель под реальные данные. В этих случаях появляются задачи о наименьших квадратах:
Эти задачи отличаются особым видом градиента и матрицы Гессе:
где — матрица Якоби вектор-функции , — матрица Гессе для её компоненты .
Тогда очередное направление определяется из системы:
Метод Гаусса — Ньютона
Метод Гаусса — Ньютона строится на предположении о том, что слагаемое доминирует над . Это требование не соблюдается, если минимальные невязки велики, т.е. если норма сравнима с максимальным собственным значением матрицы . В противном случае можно записать:
Таким образом, когда норма близка к нулю, а матрица имеет полный столбцевой ранг, направление мало отличается от Ньютоновского (с учётом ), и метод может достигать квадратичной скорости сходимости, хотя вторые производные и не учитываются. Улучшением метода является алгоритм Левенберга — Марквардта, основанный на эвристических соображениях.
Обобщение на комплексную плоскость
До сих пор в описании метода использовались функции, осуществляющие отображения в пределах множества действительных значений. Однако метод может быть применён и для нахождения нуля функции комплексного переменного. При этом процедура остаётся неизменной:
Особый интерес представляет выбор начального приближения . Ввиду того, что функция может иметь несколько нулей, в различных случаях метод может сходиться к различным значениям, и вполне естественно возникает желание выяснить, какие области обеспечат сходимость к тому или иному корню. Этот вопрос заинтересовал Артура Кейли ещё в 1879 году, однако разрешить его смогли лишь в 70-х годах двадцатого столетия с появлением вычислительной техники. Оказалось, что на пересечениях этих областей (их принято называть областями притяжения) образуются так называемые фракталы — бесконечные самоподобные геометрические фигуры.
Ввиду того, что Ньютон применял свой метод исключительно к полиномам, фракталы, образованные в результате такого применения, обрели название фракталов Ньютона или бассейнов Ньютона.
Литература
- Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.
- Амосов А.А., Дубинский Ю. А., Копченова Н.П. Вычислительные методы для инженеров. — М.: Мир, 1998.
- Бахвалов Н.С., Жидков Н.П., Кобельков Г.Г. Численные методы. — 8-е изд.. — М.: Лаборатория Базовых Знаний, 2000.
- Вавилов С. И. Исаак Ньютон. — М.: Изд. АН СССР, 1945.
- Волков Е.А. Численные методы. — М.: Физматлит, 2003.
- Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
- Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.
- Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — Энергоатомиздат, 1972.
- Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
- Морозов А.Д. Введение в теорию фракталов. — МИФИ, 2002.
Примечания
- ↑ Доказательство:
Пусть дана функция действительного переменного дважды непрерывно дифференцируемая в своей области определения, производная которой нигде не обращается в нуль:
-
- .
-
- .
-
- .
-
- .
-
См. также
Ссылки
-
Wikimedia Foundation. 2010.