Слайд 2
Метод Ньютона
Метод Ньютона (также известный как метод касательных)
— это итерационный численный метод нахождения корня (нуля) заданной
функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727). Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Улучшением метода является метод хорд и касательных.
В случае решения задач оптимизации, в которых требуется определить нуль первой производной либо градиента в случае многомерного пространства. предполагается, что функция дважды непрерывно дифференцируема. Отыскание минимума функции производится при помощи отыскания стационарной точки, т.е. точки , удовлетворяющей уравнению, которое решается методом Ньютона.
Слайд 3
Историческая справка
Метод был описан Исааком Ньютоном в рукописи
«Об анализе уравнениями бесконечных рядов» (лат. «De analysi per
aequationes numero terminorum infinitas»), адресованной в 1669 году Барроу, и в работе «Метод флюксий и бесконечные ряды» (лат. «De metodis fluxionum et serierum infinitarum») или «Аналитическая геометрия» (лат. «Geometria analytica») в собраниях трудов Ньютона, которая была написана в 1671 году. В своих работах Ньютон вводит такие понятия, как разложение функции в ряд, бесконечно малые и флюксии (производные в нынешнем понимании). Указанные работы были изданы значительно позднее: первая вышла в свет в 1711 году благодаря Уильяму Джонсону, вторая была издана Джоном Кользоном в 1736 году уже после смерти создателя. Однако описание метода существенно отличалось от его нынешнего изложения: Ньютон применял свой метод исключительно к полиномам. Он вычислял не последовательные приближения , а последовательность полиномов и в результате получал приближённое решение.
Слайд 4
Историческая справка
Впервые метод был опубликован в трактате «Алгебра»
Джона Валлиса в 1685 году, по просьбе которого он
был кратко описан самим Ньютоном. В 1690 году Джозеф Рафсон опубликовал упрощённое описание в работе «Общий анализ уравнений» (лат. «Analysis aequationum universalis»). Рафсон рассматривал метод Ньютона как чисто алгебраический и ограничил его применение полиномами, однако при этом он описал метод на основе последовательных приближений вместо более трудной для понимания последовательности полиномов, использованной Ньютоном. Наконец, в 1740 году метод Ньютона был описан Томасом Симпсоном как итеративный метод первого порядка решения нелинейных уравнений с использованием производной в том виде, в котором он излагается здесь. В той же публикации Симпсон обобщил метод на случай системы из двух уравнений и отметил, что метод Ньютона также может быть применён для решения задач оптимизации путём нахождения нуля производной или градиента.
Слайд 5
Суть метода
Поиск решения осуществляется путём построения последовательных приближений
и основан на принципах простой итерации. Метод обладает квадратичной
сходимостью. В случае решения задач оптимизации предполагается, что функция дважды непрерывно дифференцируема. Отыскание минимума функции f(x) производится при помощи отыскания стационарной точки x*, т.е. точки , удовлетворяющей уравнению f’(x)=0, которое решается методом Ньютона.
Если xk– точка, полученная на k-м шаге, то функция аппроксимируется своим уравнением касательной:
y=f’(xk)+(x- xk)f’’(xk),
а точка xk+1 выбирается как пересечение этой прямой с осью Ох, т.е. xk+1 = xk – f’(xk)/f’’(xk).
Слайд 6
Неудобство метода
Неудобство этого метода состоит в необходимости вычисления
в каждой точке первой и второй производных. Значит, он
применим лишь тогда, когда функция имеет достаточно простую аналитическую форму, чтобы производные могли быть вычислены в явном виде вручную. Действительно, всякий раз, когда решается новая задача, необходимо выбрать две специфические подпрограммы (функции) вычисления производных и , что не позволяет построить общие алгоритмы, т.е. применимые к функции любого типа.
Слайд 7
Когда начальная точка итераций достаточно близка к искомому
минимуму, скорость сходимости метода Ньютона в общем случае квадратическая.
Однако, глобальная сходимость метода Ньютона, вообще говоря, не гарантируется.
Хороший способ гарантировать глобальную сходимость этого метода состоит в комбинировании его с другим методом для быстрого получения хорошей аппроксимации искомого оптимума. Тогда несколько итераций метода Ньютона, с этой точкой в качестве исходной, достаточны для получения превосходной точности.
Слайд 8
Ограничения
Ограничения на исходную функцию будут выглядеть так:
функция должна быть ограничена;
функция должна быть гладкой,
дважды дифференцируемой;
её первая производная равномерно отделена от нуля;
её вторая производная должна быть равномерно ограничена.
В случае решения задачи оптимизации под функцией понимаем ее производную.
Слайд 9
Пример
Рассмотрим задачу о нахождении положительных x, для которых
cosx=x^3. Эта задача может быть представлена как задача нахождения
нуля функции f(x)=cosx – x^3. Имеем выражение для производной f’(x)= - sinx – 3x^2. Так как для всех cosx<=0 и для x b x^3>1 и для x>1, очевидно, что решение лежит между 0 и 1. Возьмём в качестве начального приближения значение x0=0,5 , тогда:
Подчёркиванием отмечены верные значащие цифры. Видно, что их количество от шага к шагу растёт (приблизительно удваиваясь с каждым шагом): от 1 к 2, от 2 к 5, от 5 к 10, иллюстрируя квадратичную скорость сходимости.
