Метод Ньютона. Метод ньютона оптимизации

Моделирование в электроэнергетике - Численные методы решения нелинейных уравнений. Метод Ньютона для решения уравнений с одной переменной

Численные методы решения нелинейных уравнений. Метод Ньютона для решения уравнений с одной переменной

Метод Ньютона (также известный как метод касательных) — это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643-1727), под именем которого и обрёл свою известность.

Метод был описан Исааком Ньютоном в рукописи De analysi per aequationes numero terminorum infinitas(лат.Об анализе уравнениями бесконечных рядов), адресованной в 1669 году Барроу, и в работе De metodisfluxionum et serierum infinitarum (лат.Метод флюксий и бесконечные ряды) или Geometria analytica(лат.Аналитическая геометрия) в собраниях трудов Ньютона, которая была написана в 1671 году. Однако описание метода существенно отличалось от его нынешнего изложения: Ньютон применял свой метод исключительно к полиномам. Он вычислял не последовательные приближения xn, а последовательность полиномов и в результате получал приближённое решение x.

Впервые метод был опубликован в трактате Алгебра Джона Валлиса в 1685 году, по просьбе которого он был кратко описан самим Ньютоном. В 1690 году Джозеф Рафсон опубликовал упрощённое описание в работеAnalysis aequationum universalis (лат. Общий анализ уравнений). Рафсон рассматривал метод Ньютона как чисто алгебраический и ограничил его применение полиномами, однако при этом он описал метод на основе последовательных приближений xn вместо более трудной для понимания последовательности полиномов, использованной Ньютоном.

Наконец, в 1740 году метод Ньютона был описан Томасом Симпсоном как итеративный метод первого порядка решения нелинейных уравнений с использованием производной в том виде, в котором он излагается здесь. В той же публикации Симпсон обобщил метод на случай системы из двух уравнений и отметил, что метод Ньютона также может быть применён для решения задач оптимизации путём нахождения нуля производной или градиента.

В соответствии с данным методом задача поиска корня функции сводится к задаче поиска точки пересечения с осью абсцисс касательной, построенной к графику функции .

Рис.1. График изменение функции

Проведенная в любой точке касательная линия к графику функции определяется производной данной функции в рассматриваемой точке, которая в свою очередь определяется тангенсом угла α (). Точка пересечения касательной с осью абсцисс определяется исходя из следующего соотношения в прямоугольном треугольнике: тангенс угла в прямоугольном треугольнике определяется отношением противолежащего катета к прилежащему катету треугольнику. Таким образом, на каждом шаге строится касательная к графику функции в точке очередного приближения .Точка пересечения касательной с осью Ox будет являться следующей точкой приближения . В соответствии с рассматриваемым методом расчет приближенного значения корня на i-итерации производится по формуле:

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

Условием окончания итерационного процесса является выполнение следующего условия:

где ˗ допустимая погрешность определения корня.

Метод обладает квадратичной сходимостью. Квадратичная скорость сходимость означает, что число верных знаков в приближённом значении удваивается с каждой итерацией.

Математическое обоснование

Пусть дана вещественная функция , которая определена и непрерывна на рассматриваемом участке. Необходимо найти вещественный корень рассматриваемой функции.

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

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

Производная сжимающего отображения определяется в следующем виде:

Выразим из данного выражение переменную при условии принятого ранее утверждения о том, что при необходимо обеспечить условие . В результате получим выражение для определения переменной :

С учетом этого сжимающая функция прием следующий вид:

Таким образом, алгоритм нахождения численного решения уравнения сводится к итерационной процедуре вычисления:

Алгоритм нахождения корня нелинейного уравнения по методу Ньютона для уравнения с одной переменной

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

2. Выполнить расчет приближенного значения корня функции в соответствии с формулой:

3. Проверяем приближенное значение корня на предмет заданной точности, в случае:

- если разность двух последовательных приближений станет меньше заданной точности , то итерационный процесс заканчивается.

- если разность двух последовательных приближений не достигает необходимой точности , то необходимо продолжить итерационный процесс и перейти к п.2 рассматриваемого алгоритма.

Пример решения уравнений

по методу Ньютона для уравнения с одной переменной

В качестве примера, рассмотрим решение нелинейного уравнения методом Ньютона для уравнения с одной переменной. Корень необходимо найти с точностью в качестве первого приближения .

Вариант решения нелинейного уравнения в программном комплексе MathCADпредставлен на рисунке 3.

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

Рис.2. Результаты расчета по методу Ньютона для уравнения с одной переменной

Для обеспечения заданной точности при поиске приближенного значения корня уравнения в диапазоне необходимо выполнить 4 итерации. На последнем шаге итерации приближенное значение корня нелинейного уравнения будет определяться значением: .

Рис.3. Листинг программы в MathCad

Модификации метода Ньютона для уравнения с одной переменной

Существует несколько модификаций метода Ньютона, которые направлены на упрощение вычислительного процесса.

Упрощенный метод Ньютона

В соответствии с методом Ньютона требуется вычислять производную функции f(x) на каждом шаге итерации, что ведет к увеличению вычислительных затрат. Для уменьшения затрат, связанных с вычислением производной на каждом шаге расчета, можно произвести замену производной f’(xn) в точке xn в формуле на производную f’(x0) в точке x0. В соответствии с данным методом расчета приближенное значение корня определяется по следующей формуле:

Таким образом, на каждом шаге расчета строятся прямые, которые параллельны касательной к кривой y=f(x) в точке B0 (см. рис.4). Преимуществом данного метода является то, что производная функции вычисляется один раз.

Рис.4. Модифицированный метод Ньютона

Разностный метод Ньютона

В соответствии с методом Ньютона требуется вычислять производную функции f(x) на каждом шаге итерации, что не всегда удобно, а иногда практически невозможно. Данный способ позволяет производную функции заменить разностным отношением (приближенным значением):

В результате приближенное значение корня функции f(x) будет определяться выражением разностного метода Ньютона:

Двух шаговый метод Ньютона

В результате приближенное значение корня функции f(x) будет определяться следующим выражением:

где

Рис.5. Двух шаговый метод Ньютона

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

Для того, чтобы добавить Ваш комментарий к статье, пожалуйста, зарегистрируйтесь на сайте.

simenergy.ru

Реферат Метод Ньютона Рафсона

скачать

Реферат на тему:

План:

1 Описание метода
- 1.1 Обоснование
- 1.2 Геометрическая интерпретация
- 1.3 Алгоритм
- 1.4 Пример
2 Условия применения
- 2.1 Контрпримеры
- 2.2 Ограничения
3 Историческая справка
4 Обобщения и модификации
- 4.1 Метод одной касательной
- 4.2 Многомерный случай
- 4.3 Применительно к задачам оптимизации
- 4.4 Метод Ньютона — Рафсона
- 4.5 Применительно к задачам о наименьших квадратах
- 4.6 Метод Гаусса — Ньютона
- 4.7 Обобщение на комплексную плоскость

Введение

Метод Ньютона, алгоритм Ньютона (также известный как метод касательных) — это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727), под именем которого и обрёл свою известность. Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Улучшением метода является метод хорд и касательных. Также метод Ньютона может быть использован для решения задач оптимизации, в которых требуется определить нуль первой производной либо градиента в случае многомерного пространства.

1. Описание метода

1.1. Обоснование

Чтобы численно решить уравнение методом простой итерации, его необходимо привести к следующей форме: , где — сжимающее отображение.

Для наилучшей сходимости метода в точке очередного приближения должно выполняться условие . Решение данного уравнения ищут в виде , тогда:

В предположении, что точка приближения «достаточно близка» к корню , и что заданная функция непрерывна , окончательная формула для такова:

С учётом этого функция определяется выражением:

Эта функция в окрестности корня осуществляет сжимающее отображение[1], и алгоритм нахождения численного решения уравнения сводится к итерационной процедуре вычисления:

По теореме Банаха последовательность приближений стремится к корню уравнения .

1.2. Геометрическая интерпретация

Основная идея метода заключается в следующем: задаётся начальное приближение вблизи предположительного корня, после чего строится касательная к исследуемой функции в точке приближения, для которой находится пересечение с осью абсцисс. Эта точка и берётся в качестве следующего приближения. И так далее, пока не будет достигнута необходимая точность.

Пусть — определённая на отрезке и дифференцируемая на нём вещественнозначная функция. Тогда формула итеративного исчисления приближений может быть выведена следующим образом:

где α — угол наклона касательной в точке .

Следовательно искомое выражение для имеет вид:

Итерационный процесс начинается с некоего начального приближения x0 (чем ближе к нулю, тем лучше, но если предположения о нахождении решения отсутствуют, методом проб и ошибок можно сузить область возможных значений, применив теорему о промежуточных значениях).

1.3. Алгоритм

Задается начальное приближение x0.
Пока не выполнено условие остановки, в качестве которого можно взять или (то есть погрешность в нужных пределах), вычисляют новое приближение: .

1.4. Пример

Иллюстрация применения метода Ньютона к функции f(x) = cosx − x3 с начальным приближением в точке x0 = 0,5.

График последовательных приближений.	График сходимости.
Согласно способу практического определения скорость сходимости может быть оценена как тангенс угла наклона графика сходимости, то есть в данном случае равна двум.

Рассмотрим задачу о нахождении положительных x, для которых cosx = x3. Эта задача может быть представлена как задача нахождения нуля функции f(x) = cosx − x3. Имеем выражение для производной f'(x) = − sinx − 3x2. Так как для всех x и x3 > 1 для x > 1, очевидно, что решение лежит между 0 и 1. Возьмём в качестве начального приближения значение x0 = 0,5, тогда:

Подчёркиванием отмечены верные значащие цифры. Видно, что их количество от шага к шагу растёт (приблизительно удваиваясь с каждым шагом): от 1 к 2, от 2 к 5, от 5 к 10, иллюстрируя квадратичную скорость сходимости.

2. Условия применения

Иллюстрация расхождения метода Ньютона, применённого к функции с начальным приближением в точке .

Рассмотрим ряд примеров, указывающих на недостатки метода.

2.1. Контрпримеры

Если начальное приближение недостаточно близко к решению, то метод может не сойтись.

Пусть

Тогда

Возьмём нуль в качестве начального приближения. Первая итерация даст в качестве приближения единицу. В свою очередь, вторая снова даст нуль. Метод зациклится и решение не будет найдено. В общем случае построение последовательности приближений может быть очень запутанным.

График производной функции при приближении к нулю справа.

Если производная не непрерывна в точке корня, то метод может расходиться в любой окрестности корня.

Рассмотрим функцию:

Тогда и всюду, кроме 0.

В окрестности корня производная меняет знак при приближении x к нулю справа или слева. В то время, как для .

Таким образом не ограничено вблизи корня, и метод будет расходиться, хотя функция всюду дифференцируема, её производная не равна нулю в корне, бесконечно дифференцируема везде, кроме как в корне, а её производная ограничена в окрестности корня.

Если не существует вторая производная в точке корня, то скорость сходимости метода может быть заметно снижена.

Рассмотрим пример:

Тогда и за исключением , где она не определена.

На очередном шаге имеем :

Скорость сходимости полученной последовательности составляет приблизительно 4/3. Это существенно меньше, нежели 2, необходимое для квадратичной сходимости, поэтому в данном случае можно говорить лишь о линейной сходимости, хотя функция всюду непрерывно дифференцируема, производная в корне не равна нулю, и бесконечно дифференцируема везде, кроме как в корне.

Если производная в точке корня равна нулю, то скорость сходимости не будет квадратичной, а сам метод может преждевременно прекратить поиск, и дать неверное для заданной точности приближение.

Пусть

Тогда и следовательно . Таким образом сходимость метода не квадратичная, а линейная, хотя функция всюду бесконечно дифференцируема.

2.2. Ограничения

Пусть задано уравнение , где и надо найти его решение.

Ниже приведена формулировка основной теоремы, которая позволяет дать чёткие условия применимости. Она носит имя советского математика и экономиста, лауреата Нобелевской премии по экономике 1975 года «за вклад в теорию оптимального распределения ресурсов» Леонида Витальевича Канторовича (1912—1986) и является одной из многочисленных теорем, ставших результатами его научных изысканий.

Теорема Канторовича.

Если существуют такие константы , что:

на , то есть существует и не равна нулю;
на , то есть ограничена;
на , и ;

Причём длина рассматриваемого отрезка . Тогда справедливы следующие утверждения:

на существует корень уравнения ;
если , то итерационная последовательность сходится к этому корню: ;
погрешность может быть оценена по формуле .

Из последнего из утверждений теоремы в частности следует квадратичная сходимость метода:

Тогда ограничения на исходную функцию будут выглядеть так:

функция должна быть ограничена;
функция должна быть гладкой, дважды дифференцируемой;
её первая производная равномерно отделена от нуля;
её вторая производная должна быть равномерно ограничена.

3. Историческая справка

Метод был описан Исааком Ньютоном в рукописи «Об анализе уравнениями бесконечных рядов» (лат. «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») был первым, кто отметил трудности в обобщении метода Ньютона на случай мнимых корней полиномов степени выше второй и комплексных начальных приближений. Эта работа открыла путь к изучению теории фракталов.

4. Обобщения и модификации

Иллюстрация последовательных приближений метода одной касательной, применённого к функции с начальным приближением в точке .

4.1. Метод одной касательной

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

Формула итераций этого метода имеет вид:

Суть метода заключается в том, чтобы вычислять производную лишь один раз, в точке начального приближения , а затем использовать это значение на каждой последующей итерации:

При таком выборе в точке выполнено равенство:

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

Этот метод можно также рассматривать, как модернизацию метода хорд (секущих), где число следует выбрать равным

4.2. Многомерный случай

Обобщим полученный результат на многомерный случай.

Пускай необходимо найти решение системы:

Выбирая некоторое начальное значение , последовательные приближения находят путём решения систем уравнений:

где .

4.3. Применительно к задачам оптимизации

Пусть необходимо найти минимум функции многих переменных . Эта задача равносильна задаче нахождения нуля градиента . Применим изложенный выше метод Ньютона:

где — гессиан функции .

В более удобном итеративном виде это выражение выглядит так:

Следует отметить, что в случае квадратичной функции метод Ньютона находит экстремум за одну итерацию.

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

4.4. Метод Ньютона — Рафсона

Метод Ньютона — Рафсона является улучшением метода Ньютона нахождения экстремума, описанного выше. Основное отличие заключается в том, что на очередной итерации каким-либо из методов одномерной оптимизации выбирается оптимальный шаг:

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

4.5. Применительно к задачам о наименьших квадратах

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

Эти задачи отличаются особым видом градиента и матрицы Гессе:

где — матрица Якоби вектор-функции , — матрица Гессе для её компоненты .

Тогда очередное направление определяется из системы:

4.6. Метод Гаусса — Ньютона

Метод Гаусса — Ньютона строится на предположении о том, что слагаемое доминирует над . Это требование не соблюдается, если минимальные невязки велики, то есть если норма сравнима с максимальным собственным значением матрицы . В противном случае можно записать:

Таким образом, когда норма близка к нулю, а матрица имеет полный столбцевой ранг, направление мало отличается от ньютоновского (с учётом ), и метод может достигать квадратичной скорости сходимости, хотя вторые производные и не учитываются. Улучшением метода является алгоритм Левенберга — Марквардта, основанный на эвристических соображениях.

4.7. Обобщение на комплексную плоскость

Бассейны Ньютона для полинома пятой степени . Разными цветами закрашены области притяжения для разных корней. Более тёмные области соответствуют большему числу итераций.

До сих пор в описании метода использовались функции, осуществляющие отображения в пределах множества вещественных значений. Однако метод может быть применён и для нахождения нуля функции комплексного переменного. При этом процедура остаётся неизменной:

Особый интерес представляет выбор начального приближения . Ввиду того, что функция может иметь несколько нулей, в различных случаях метод может сходиться к различным значениям, и вполне естественно возникает желание выяснить, какие области обеспечат сходимость к тому или иному корню. Этот вопрос заинтересовал Артура Кейли ещё в 1879 году, однако разрешить его смогли лишь в 70-х годах двадцатого столетия с появлением вычислительной техники. Оказалось, что на пересечениях этих областей (их принято называть областями притяжения) образуются так называемые фракталы — бесконечные самоподобные геометрические фигуры.

Ввиду того, что Ньютон применял свой метод исключительно к полиномам, фракталы, образованные в результате такого применения, обрели название фракталов Ньютона или бассейнов Ньютона.

Литература

Акулич И. Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.
Амосов А. А., Дубинский Ю. А., Копченова Н. П. Вычислительные методы для инженеров. — М.: Мир, 1998.
Бахвалов Н. С., Жидков Н. П., Кобельков Г. Г. Численные методы. — 8-е изд.. — М.: Лаборатория Базовых Знаний, 2000.
Вавилов С. И. Исаак Ньютон. — М.: Изд. АН СССР, 1945.
Волков Е. А. Численные методы. — М.: Физматлит, 2003.
Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.
Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. — Энергоатомиздат, 1972.
Максимов Ю. А.,Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
Морозов А. Д. Введение в теорию фракталов. — МИФИ, 2002.

Примечания

wreferat.baza-referat.ru

Метод ньютона в оптимизации • ru.knowledgr.com

В исчислении метод Ньютона - повторяющийся метод для нахождения корней дифференцируемой функции (т.е. решения уравнения). В оптимизации метод Ньютона применен к производной дважды дифференцируемой функции, чтобы найти корни производной (решения), также известен как постоянные пункты.

Метод

Метод ньютона пытается построить последовательность из начального предположения, которое сходится к таким образом что. Это - постоянный пункт.

Второе расширение Тейлора заказа приблизительно (где):

и достигает его экстремума, когда его производная относительно равна нолю, т.е. когда:

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

будет сходиться к корню, т.е. для который.

Геометрическая интерпретация

Геометрическая интерпретация метода Ньютона - то, что при каждом повторении каждый приближается квадратной функцией вокруг, и затем предпринимает шаги к максимуму/минимуму той квадратной функции (в более высоких размерах, это может также быть пунктом седла). Отметьте что, если, оказывается, квадратная функция, то точный экстремум найден за один шаг.

Более высокие размеры

Вышеупомянутая повторяющаяся схема может быть обобщена к нескольким размерам, заменив производную с градиентом, и аналог второй производной с инверсией матрицы Мешковины. Каждый получает повторяющуюся схему

Обычно метод Ньютона изменен, чтобы включать маленький размер шага вместо

Это часто делается, чтобы гарантировать, что условия Вольфа удовлетворены в каждом шаге повторения.

Где применимо, метод Ньютона сходится намного быстрее к местному максимуму или минимуму, чем спуск градиента. Фактически, у каждого местного минимума есть район, таким образом, что, если мы начинаем с метода Ньютона с размером шага, сходится квадратным образом (если Мешковина обратимая и Липшиц непрерывная функция в том районе).

Нахождение инверсии Мешковины в высоких размерах может быть дорогой операцией. В таких случаях вместо того, чтобы непосредственно инвертировать Мешковину лучше вычислить вектор как решение системы линейных уравнений

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

С другой стороны, если ограниченная оптимизация сделана (например, со множителями Лагранжа), проблема может стать одним из открытия пункта седла, когда Мешковина будет симметрична неопределенный, и решение должно будет быть сделано с методом, который будет работать на такой, такой как вариант LDL факторизации Cholesky или сопряженного остаточного метода.

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

Если Мешковина близко к необратимой матрице, перевернутая Мешковина может быть численно нестабильной, и решение может отличаться. В этом случае определенные искусственные приемы попробовали в прошлом, которые изменили успех с определенными проблемами. Можно, например, изменить Мешковину, добавив матрицу исправления, чтобы сделать положительным определенный. Один подход к diagonalize, и выберите так, чтобы имел те же самые собственные векторы как, но с каждым отрицательным собственным значением, замененным

Подход эксплуатировал в алгоритме Levenberg–Marquardt (который использует приблизительную Мешковину), должна добавить чешуйчатая матрица идентичности к Мешковине, с масштабом, приспособленным при каждом повторении по мере необходимости. Для большой и маленькой Мешковины повторения будут вести себя как спуск градиента с размером шага. Это приводит к более медленной но более надежной сходимости, где Мешковина не предоставляет полезную информацию.

См. также

Метод квазиньютона

Спуск градиента

Алгоритм Gauss-ньютона

Алгоритм Levenberg–Marquardt

Трастовая область

Метод Nelder-меда

Примечания

Avriel, Мордекай (2003). Нелинейное программирование: анализ и методы. Dover Publishing. ISBN 0-486-43227-0.
.
Nocedal, Jorge & Wright, Стивен Дж. (1999). Числовая оптимизация. Спрингер-Верлэг. ISBN 0-387-98793-2.
.

ru.knowledgr.com

Метод Ньютона - это... Что такое Метод Ньютона?

Метод Ньютона, алгоритм Ньютона (также известный как метод касательных) — это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727). Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Улучшением метода является метод хорд и касательных. Также метод Ньютона может быть использован для решения задач оптимизации, в которых требуется определить нуль первой производной либо градиента в случае многомерного пространства.

Описание метода

Обоснование

С учётом этого функция определяется выражением:

По теореме Банаха последовательность приближений стремится к корню уравнения .

Геометрическая интерпретация

где — угол наклона касательной в точке .

Следовательно искомое выражение для имеет вид:

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

Алгоритм

Задается начальное приближение .
Пока не выполнено условие остановки, в качестве которого можно взять или (то есть погрешность в нужных пределах), вычисляют новое приближение: .

Пример

Рассмотрим задачу о нахождении положительных , для которых . Эта задача может быть представлена как задача нахождения нуля функции . Имеем выражение для производной . Так как для всех и для , очевидно, что решение лежит между 0 и 1. Возьмём в качестве начального приближения значение , тогда:

Условия применения

Иллюстрация расхождения метода Ньютона, применённого к функции с начальным приближением в точке .

Рассмотрим ряд примеров, указывающих на недостатки метода.

Контрпримеры

Если начальное приближение недостаточно близко к решению, то метод может не сойтись.

Пусть

Тогда

График производной функции при приближении к нулю справа.

Рассмотрим функцию:

Тогда и всюду, кроме 0.

В окрестности корня производная меняет знак при приближении к нулю справа или слева. В то время, как для .

Рассмотрим пример:

Тогда и за исключением , где она не определена.

На очередном шаге имеем :

Если производная в точке корня равна нулю, то скорость сходимости не будет квадратичной, а сам метод может преждевременно прекратить поиск, и дать неверное для заданной точности приближение.

Пусть

Ограничения

Пусть задано уравнение , где и надо найти его решение.

Ниже приведена формулировка основной теоремы, которая позволяет дать чёткие условия применимости. Она носит имя советского математика и экономиста Леонида Витальевича Канторовича (1912—1986).

Теорема Канторовича.

Если существуют такие константы , что:

на , то есть существует и не равна нулю;
на , то есть ограничена;
на , и ;

Причём длина рассматриваемого отрезка . Тогда справедливы следующие утверждения:

на существует корень уравнения ;
если , то итерационная последовательность сходится к этому корню: ;
погрешность может быть оценена по формуле .

Из последнего из утверждений теоремы в частности следует квадратичная сходимость метода:

Тогда ограничения на исходную функцию будут выглядеть так:

функция должна быть ограничена;
функция должна быть гладкой, дважды дифференцируемой;
её первая производная равномерно отделена от нуля;
её вторая производная должна быть равномерно ограничена.

Историческая справка

Метод был описан Исааком Ньютоном в рукописи «Об анализе уравнениями бесконечных рядов» (лат. «De analysi per aequationes numero terminorum infinitas»), адресованной в 1669 году Барроу, и в работе «Метод флюксий и бесконечные ряды» (лат. «De metodis fluxionum et serierum infinitarum») или «Аналитическая геометрия» (лат. «Geometria analytica») в собраниях трудов Ньютона, которая была написана в 1671 году. В своих работах Ньютон вводит такие понятия, как разложение функции в ряд, бесконечно малые и флюксии (производные в нынешнем понимании). Указанные работы были изданы значительно позднее: первая вышла в свет в 1711 году благодаря Уильяму Джонсону, вторая была издана Джоном Кользоном в 1736 году уже после смерти создателя. Однако описание метода существенно отличалось от его нынешнего изложения: Ньютон применял свой метод исключительно к полиномам. Он вычислял не последовательные приближения , а последовательность полиномов и в результате получал приближённое решение .

Впервые метод был опубликован в трактате «Алгебра» Джона Валлиса в 1685 году, по просьбе которого он был кратко описан самим Ньютоном. В 1690 году Джозеф Рафсон опубликовал упрощённое описание в работе «Общий анализ уравнений» (лат. «Analysis aequationum universalis»). Рафсон рассматривал метод Ньютона как чисто алгебраический и ограничил его применение полиномами, однако при этом он описал метод на основе последовательных приближений вместо более трудной для понимания последовательности полиномов, использованной Ньютоном. Наконец, в 1740 году метод Ньютона был описан Томасом Симпсоном как итеративный метод первого порядка решения нелинейных уравнений с использованием производной в том виде, в котором он излагается здесь. В той же публикации Симпсон обобщил метод на случай системы из двух уравнений и отметил, что метод Ньютона также может быть применён для решения задач оптимизации путём нахождения нуля производной или градиента.

Обобщения и модификации

Метод одной касательной

Формула итераций этого метода имеет вид:

При таком выборе в точке выполнено равенство:

Многомерный случай

Обобщим полученный результат на многомерный случай.

Пусть необходимо найти решение системы:

где .

Применительно к задачам оптимизации

где — гессиан функции .

В более удобном итеративном виде это выражение выглядит так:

Следует отметить, что в случае квадратичной функции метод Ньютона находит экстремум за одну итерацию.

Метод Ньютона — Рафсона

Применительно к задачам о наименьших квадратах

Эти задачи отличаются особым видом градиента и матрицы Гессе:

где — матрица Якоби вектор-функции , — матрица Гессе для её компоненты .

Тогда очередное направление определяется из системы:

Метод Гаусса — Ньютона

Обобщение на комплексную плоскость

Литература

Акулич И. Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.
Амосов А. А., Дубинский Ю. А., Копченова Н. П. Вычислительные методы для инженеров. — М.: Мир, 1998.
Бахвалов Н. С., Жидков Н. П., Кобельков Г. Г. Численные методы. — 8-е изд.. — М.: Лаборатория Базовых Знаний, 2000.
Вавилов С. И. Исаак Ньютон. — М.: Изд. АН СССР, 1945.
Волков Е. А. Численные методы. — М.: Физматлит, 2003.
Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.
Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. — Энергоатомиздат, 1972.
Максимов Ю. А.,Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
Морозов А. Д. Введение в теорию фракталов. — МИФИ, 2002.

Примечания

См. также

Ссылки

dik.academic.ru

Метод Ньютона - это... Что такое Метод Ньютона?

Метод Ньютона, алгоритм Ньютона (также известный как метод касательных) — это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727). Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Улучшением метода является метод хорд и касательных. Также метод Ньютона может быть использован для решения задач оптимизации, в которых требуется определить нуль первой производной либо градиента в случае многомерного пространства.

Описание метода

Обоснование

С учётом этого функция определяется выражением:

По теореме Банаха последовательность приближений стремится к корню уравнения .

Геометрическая интерпретация

где — угол наклона касательной в точке .

Следовательно искомое выражение для имеет вид:

Алгоритм

Задается начальное приближение .
Пока не выполнено условие остановки, в качестве которого можно взять или (то есть погрешность в нужных пределах), вычисляют новое приближение: .

Пример

Условия применения

Иллюстрация расхождения метода Ньютона, применённого к функции с начальным приближением в точке .

Рассмотрим ряд примеров, указывающих на недостатки метода.

Контрпримеры

Если начальное приближение недостаточно близко к решению, то метод может не сойтись.

Пусть

Тогда

График производной функции при приближении к нулю справа.

Рассмотрим функцию:

Тогда и всюду, кроме 0.

В окрестности корня производная меняет знак при приближении к нулю справа или слева. В то время, как для .

Рассмотрим пример:

Тогда и за исключением , где она не определена.

На очередном шаге имеем :

Если производная в точке корня равна нулю, то скорость сходимости не будет квадратичной, а сам метод может преждевременно прекратить поиск, и дать неверное для заданной точности приближение.

Пусть

Ограничения

Пусть задано уравнение , где и надо найти его решение.

Теорема Канторовича.

Если существуют такие константы , что:

на , то есть существует и не равна нулю;
на , то есть ограничена;
на , и ;

Причём длина рассматриваемого отрезка . Тогда справедливы следующие утверждения:

на существует корень уравнения ;
если , то итерационная последовательность сходится к этому корню: ;
погрешность может быть оценена по формуле .

Из последнего из утверждений теоремы в частности следует квадратичная сходимость метода:

Тогда ограничения на исходную функцию будут выглядеть так:

функция должна быть ограничена;
функция должна быть гладкой, дважды дифференцируемой;
её первая производная равномерно отделена от нуля;
её вторая производная должна быть равномерно ограничена.

Историческая справка

Метод был описан Исааком Ньютоном в рукописи «Об анализе уравнениями бесконечных рядов» (лат. «De analysi per aequationes numero terminorum infinitas»), адресованной в 1669 году Барроу, и в работе «Метод флюксий и бесконечные ряды» (лат. «De metodis fluxionum et serierum infinitarum») или «Аналитическая геометрия» (лат. «Geometria analytica») в собраниях трудов Ньютона, которая была написана в 1671 году. В своих работах Ньютон вводит такие понятия, как разложение функции в ряд, бесконечно малые и флюксии (производные в нынешнем понимании). Указанные работы были изданы значительно позднее: первая вышла в свет в 1711 году благодаря Уильяму Джонсону, вторая была издана Джоном Кользоном в 1736 году уже после смерти создателя. Однако описание метода существенно отличалось от его нынешнего изложения: Ньютон применял свой метод исключительно к полиномам. Он вычислял не последовательные приближения , а последовательность полиномов и в результате получал приближённое решение .

Впервые метод был опубликован в трактате «Алгебра» Джона Валлиса в 1685 году, по просьбе которого он был кратко описан самим Ньютоном. В 1690 году Джозеф Рафсон опубликовал упрощённое описание в работе «Общий анализ уравнений» (лат. «Analysis aequationum universalis»). Рафсон рассматривал метод Ньютона как чисто алгебраический и ограничил его применение полиномами, однако при этом он описал метод на основе последовательных приближений вместо более трудной для понимания последовательности полиномов, использованной Ньютоном. Наконец, в 1740 году метод Ньютона был описан Томасом Симпсоном как итеративный метод первого порядка решения нелинейных уравнений с использованием производной в том виде, в котором он излагается здесь. В той же публикации Симпсон обобщил метод на случай системы из двух уравнений и отметил, что метод Ньютона также может быть применён для решения задач оптимизации путём нахождения нуля производной или градиента.

Обобщения и модификации

Метод одной касательной

Формула итераций этого метода имеет вид:

При таком выборе в точке выполнено равенство:

Многомерный случай

Обобщим полученный результат на многомерный случай.

Пусть необходимо найти решение системы:

где .

Применительно к задачам оптимизации

где — гессиан функции .

В более удобном итеративном виде это выражение выглядит так:

Следует отметить, что в случае квадратичной функции метод Ньютона находит экстремум за одну итерацию.

Метод Ньютона — Рафсона

Применительно к задачам о наименьших квадратах

Эти задачи отличаются особым видом градиента и матрицы Гессе:

где — матрица Якоби вектор-функции , — матрица Гессе для её компоненты .

Тогда очередное направление определяется из системы:

Метод Гаусса — Ньютона

Обобщение на комплексную плоскость

Литература

Акулич И. Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.
Амосов А. А., Дубинский Ю. А., Копченова Н. П. Вычислительные методы для инженеров. — М.: Мир, 1998.
Бахвалов Н. С., Жидков Н. П., Кобельков Г. Г. Численные методы. — 8-е изд.. — М.: Лаборатория Базовых Знаний, 2000.
Вавилов С. И. Исаак Ньютон. — М.: Изд. АН СССР, 1945.
Волков Е. А. Численные методы. — М.: Физматлит, 2003.
Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.
Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. — Энергоатомиздат, 1972.
Максимов Ю. А.,Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
Морозов А. Д. Введение в теорию фракталов. — МИФИ, 2002.

Примечания

См. также

Ссылки

3dic.academic.ru