Автор работы: Пользователь скрыл имя, 13 Сентября 2015 в 13:09, дипломная работа
В данной выпускной квалификационной рассматриваются методы решения систем нелинейных уравнений и нахождения их корней с заданной точностью.
Введение 3
Глава I. Приближенное решение систем нелинейных уравнений различными методами 4
1.1.Метод простой итерации 4
1.2.Метод Ньютона для решения нелинейных уравнений. 9
1.3.Метод хорд 14
1.4.Методы спуска. 17
Глава II. Метод Ньютона для решения нелинейных задач. 23
2.1 Общие замечания о сходимости процесса Ньютона. 23
2.2. Существование корней системы и сходимость процесса Ньютона. 30
2.3 Быстрота сходимости процесса Ньютона. 35
2.4 Модифицированный метод Ньютона. …37
Заключение. 41
Список использованной литературы 4
Тогда условие завершения вычислений записывается в виде:
где - заданная погрешность вычислений. Необходимо отметить, что при отыскании корня метод хорд нередко обеспечивает более быструю сходимость, чем метод половинного деления.
1.4 Методы спуска
Для решения задачи минимизации функционала в большинстве случаев применяются методы спуска. При заданном приближении определяются какое-либо направление, в котором функционал убывает и производится перемещение приближения в этом направлении. Если величина перемещения взята не очень большой, то значение функционала обязательно уменьшится.
Рассмотрим на примере метод спуска.
При исследовании сходимости метода Зейделя в случае системы уравнений , при мы писали циклический метод покоординатного спуска минимизации функции при заданном приближении отыскивается значение , при котором достигается затем нужно отыскать значение , при котором достигается и т.д. Процесс циклически повторяется.
Обозначим через приближение, получаемое при спуске из по координате Присваивая приближению, получающемуся при спуске по очередной координате, следующий номер, можно записать приближения метода циклического покоординатного спуска в виде.
При практической реализации этого метода возникает проблема минимизации функций одной переменной. Рассмотрим отдельно задачу минимизации функций одной переменной при начальном приближении к точке минимума . Так как эта задача обычно не может быть решена точно, то часто поступают следующим образом: берут некоторые значения , и строят параболу удовлетворяющую условиям
Абсциссу точки минимума принимают за следующее приближение . Уже в одномерном случае можно построить пример, когда последовательность точек, получаемых по описываемому методу, не обязательно сходится к искомой точке экстремума функции Ф.
Даже если на каждом шаге отыскивается абсолютный экстремум функции по соответствующей координате, то уже при может случиться, что итерационный процесс сходится не к искомой точке абсолютного экстремума, а к некоторой точке локального экстремума. Спуск в циклическом порядке необязателен. Если из рассмотрения проводившихся ранее вычислений видно, что спуск по каким-либо координатам обеспечивает наибольшее убывание , то иногда целесообразен более частый спуск по этим координатам.
В других случаях при каждом после получения приближения выбирается некоторая совокупность координат
производятся независимые спуски по координатам этой группы исходя из приближения , т. е. находят точки . Далее вычисляется
и соответствующая минимуму точка принимается за .
Иногда номер очередной координаты, по которой осуществляется спуск, выбирается не детерминированно. В этом случае говорят о случайном покоординатном спуске.
Другой вариант метода спуска — метод наискорейшего (градиентного) спуска. Следующее приближение отыскивается в виде
Значение определяется из условия
т. е. этот алгоритм опять состоит в последовательной минимизации функции одной переменной .
Как и в методе покоординатного спуска, в методе наискорейшего спуска нет необходимости полного решения вспомогательной задачи минимизации функции одной переменной. В окрестности точки своего минимума эта функция меняется мало, и тщательное нахождение ее точки минимума не приводит к существенному эффекту. В случае метода наискорейшего спуска вопрос об объеме вычислений при минимизации вспомогательных функций одной переменной должен решаться также с учетом относительной трудоемкости вычисления значений функции и ее градиента.
Для иллюстрации решения вопроса о выборе метода рассмотрим следующую типичную задачу: решается нелинейная краевая задача для системы обыкновенных дифференциальных уравнений. В этой главе будет показано, что эта задача сводится к решению нелинейной системы уравнений :
обладающей следующими свойствами.
Количество операций при отыскании одного значения и при одновременном отыскании всех значений , в той же точке одинаково; обозначим его через . Количество операций при непосредственном отыскании значений и при одновременном отыскании всех значений в той же точке одинаково. Обозначим его через ; обычно .
Тогда при решении задачи методом Ньютона целесообразно вычислять производные , пользуясь приближенной формулой
Область сходимости метода Ньютона обычно невелика, поэтому по крайней мере на начальном этапе итераций целесообразно свести решение этой задачи к минимизации некоторого функционала и применить какой- либо из методов спуска. Рассмотрим простейший случай функционала
множители , называемые масштабными, подбираются из условий конкретной задачи.
Пусть полученное приближение и решено сделать
спуск в направлении . Вычисляют приближенные значения производных в этом направлении:
На прямой имеем
,
поэтому следующее приближение определяют из условия
Отметим, что в данном случае существен вопрос о разумном выборе е в формуле (2).
Задача минимизации функции при наличии ограничений, так называемая задача условной минимизации, формулируется следующим образом. Ищется величина
при условиях
(1.23)
(1.24)
При решении этой задачи возникают дополнительные трудности по сравнению с решением задачи отыскания безусловного минимума, в которой ищется
— нижняя грань всему пространству .
Непосредственное использование многих из описанных выше методов становится невозможным, и возникает необходимость в их модификации.
В то же время задача минимизации функции при ограничениях типа (4), (5) является весьма актуальной для приложений. Например, существует целый раздел математики — линейное программирование, — занимающийся решением задачи (3)-(5) в случае, когда — линейные функции аргументов
Среди других методов, связанных с решением задачи (3)-(5), упомянем метод штрафа. Строится последовательность функций ), удовлетворяющая следующим условиям:
1) определена при всех
2)
3) Если существуют точки и такие, что
,
то .
Вместо решения исходной задачи (3)-(5) решается задача отыскания минимума при достаточно больших .
Часто вместо первого условия на функцию требуют выполнения более слабого условия. Функция определена в точках некоторой односвязной области при приближении точки к границе области или при (в случае, когда область неограниченная).
В отдельных случаях условие 3) также несколько модифицируется.
Приведем пример построения такой функции Для этого соотношения (4), (5) записываются в таком виде, что будут определены при всех (или при всех из ).
Вводится некоторая невозрастающая функция определенная при такая, что
Например можно взять
.
В качестве берется функция
Наличие слагаемою заставляет смещаться точку экстремума в область, где ; в то время как
наличие слагаемого заставляет смещаться точку экстремумa в область, где .
Метод штрафа обладает следующим недостатком. Оказывается, что при больших λ структура линий уровня , как правило, такова, что сходимость методов минимизации существенно замедляется. Искусство применения метода штрафа при решении конкретных задач состоит в удачном выборе функции такой, что при заданной близости значений нижней грани замедление скорости сходимости применяемого итерационного метода будет минимальным.
В связи с отмеченными недостатками метода штрафа разработано большое число других методов решения задачи условной минимизации (3)-(5).
Глава II. Метод Ньютона для решения нелинейных задач
2.1 Общие замечания о сходимости процесса Ньютона
Рассмотрим нелинейную систему уравнений
с действительными числами.
Совокупность аргументов можно рассмотреть как
Аналогично можно будет рассмотреть совокупность функций представляет собой также .
Поэтому система (2.0) кратко может быть записана так:
Для решения системы (2.1) воспользуемся методом последовательных приближений.
Представим, что найдено приближение
одного из изолированных корней векторного уравнения (2.1). Тогда, точный корень уравнения (2.1) можно будет представить в виде
где погрешность корня.
Подставив выражение (2.2) в уравнение (2.1), получим:
Предполагая, что ф-ия непрерывно дифференцируема в некоторой выпуклой области, содержащей и , разложим левую часть уравнения (2.3) по степеням малого вектора , ограничиваясь линейными членами,
(2.4)
или в развернутом виде
(2.5)
Из формул (2.4) и (2.5) можно считать, что под производной нужно подразумевать матрицу Якоби системы функций относительно переменных , то есть
или же в краткой записи
Система (2.5) может представлять собой линейную систему относительно поправок с матрицей , поэтому формула (2.4) так же может быть записана как :
Отсюда, предполагаем, что матрица неособенная, тогда получаем
Отсюда следует,
(2.6)