Смекни!
smekni.com

по дисциплине «технология/методология научных исследований» на тему «Метод Ньютона для функций одной переменной»

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

ГОУВПО «Самарский государственный

архитектурно-строительный университет»

Факультет информационных систем и технологий

Кафедра прикладной математики и вычислительной техники

РЕФЕРАТ

по дисциплине

«ТЕХНОЛОГИЯ/МЕТОДОЛОГИЯ НАУЧНЫХ ИССЛЕДОВАНИЙ»

на тему

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

III СЕМЕСТР 2КУРС

Научный руководитель: Пиявский Семён Авраамович

Проверили: Выполнила: студентка ГИП 107 Сулковская А.С.

Общая оценка____________________

Методический руководитель Оценка Дата

2007 год


Введение

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

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

Достоинства метода Ньютона:

1) если минимизируемая функция является квадратической, то метод позволит найти минимум за один шаг;

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

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

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

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

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

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

Чтобы численно решить уравнение

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

Для наилучшей сходимости метода в точке очередного приближения

должно выполняться условие
. Решение данного уравнения ищут в виде
, тогда:

В предположении, что точка приближения «достаточно близка» к корню

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

С учётом этого функция

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

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

сводится к итерационной процедуре вычисления:

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

.

Иллюстрация метода Ньютона (синим изображена функция

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

[править] Геометрическая интерпретация

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

Пусть

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

,

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

.

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

имеет вид:

.

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