МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

СУМСКИЙ ГОСУДАСТВЕННЫЙ УНИВЕРСИТЕТ

кафедра информатики

КУРСОВАЯ РАБОТА

ПО КУРСУ:

Численные методы

«Итерационные методы решения систем нелинейных уравнений»

1. Методы решения систем нелинейных уравнений. Общая информация

2.1 Метод простых итераций

2.2 Преобразование Эйткена

2.3 Метод Ньютона

2.3.1 Модификации метода Ньютона

2.3.2 Квазиньютоновские методы

2.4 Другие итерационные методы решения систем нелинейных уравнений

2.4.1 Метод Пикара

2.4.2 Метод градиентного спуска

2.4.3 Метод релаксаций

3. Реализация итерационных методов программно и с помощью математического пакета Maple

3.1 Метод простых итераций

3.2 Метод градиентного спуска

3.3 Метод Ньютона

3.4 Модифицированный метод Ньютона

Список использованной литературы

1. Методы решения нелинейных уравнений. Общая информация.

Пусть нам дана система уравнений, где

- некоторые нелинейные операторы: (1.1)

Она может быть также представлена в матричном виде:

(1.1)

Её решением называется такое значение

, для котрого

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

Обозначим через Х вектор-столбец (х 1 , х 2 ,..., х n ) T и запишем систему уравнений в виде формулы (1.2): F (Х ) = 0, где F = (f 1 , f 2 ,..., f n ) T .

Подобные системы уравнений могут возникать непосредственно, например, при конструировании физических систем, или опосредованно. Так, к примеру, при решении задачи минимизации некоторой функции G (х )часто необходимо определить те точки, в которых градиент этой функции равен нулю. Полагая F = grad G, получаем нелинейную систему.

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

. Если итерационный процесс сходится, то граничное значение является решением данной системы уравнений.

Для полноты представления о методах нахождения решения системы необходимо разъяснить такое понятие, как "скорость сходимости". Если для последовательности x n , сходящейся к пределу х * , верна формула

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

2. Итерационные методы решения систем нелинейных уравнений

2.1 Метод простых итераций

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

f i (x 1 ,x 2 ,...x n) = 0, i =1,2,..n ;

Приведём систему уравнений к специальному виду:

(2.1)

Или в векторном виде

. (2.2)

Причем переход к этой системе должен быть только при условии, что

является сжимающим отображением.

Используя некоторое начальное приближение X (0) = (x 1 (0) ,x 2 (0) ,...x n (0))

построим итерационный процесс X (k+1) =  (X (k)). Расчёты продолжаются до выполнения условия

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

Проведём обоснование метода в некоторой норме

пространства .

Приведём теорему о сходимости, выполнение условий которой приводит к нахождению решения системы.

Теорема (о сходимости). Пусть

1). Вектор-функция Ф(х) определена в области

; выполняется условие

3). Справедливо неравенство

Тогда в итерационном процессе:

, – решение системы уравнений; ,

Замечание. Неравенство условия 2) есть условие Липшица для вектор -функции Ф(х) в области S с константой

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

Доказательство . Поскольку

, то для приближения в силу предположения 3) имеем . Это значит, что . Покажем, что , k=2,3,… причём для соседних приближений выполняется неравенство (2.3)

Будем рассуждать по индукции. При

утверждение справедливо, т.к. и . Допустим, что приближения принадлежат S, и неравенство (2.3) выполнено для . Поскольку , то для с учётом условия 2) теоремы имеем .

По индуктивному предположению

Решение нелинейных уравнений

Пусть требуется решить уравнение

Где
– нелинейная непрерывная функция.

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

Полное решение поставленной задачи можно разделить на 3 этапа:

Установить количество, характер и расположение корней уравнения (1).

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

Найти значение корней с требуемой точностью (уточнить корни).

Существуют различные графические и аналитические методы решения первых двух задач.

Наиболее наглядный метод отделения корней уравнения (1) состоит в определении координат точек пересечения графика функции
с осью абсцисс. Абсциссы точек пересечения графика
с осью
являются корнями уравнения (1)

Промежутки изоляции корней уравнения (1) можно получить аналитически, опираясь на теоремы о свойствах функций, непрерывных на отрезке.

Если, например, функция
непрерывна на отрезке
и
, то согласно теореме Больцано – Коши, на отрезке
существует хотя бы один корень уравнения (1)(нечетное количество корней).

Если функция
удовлетворяет условиям теоремы Больцано-Коши и монотонна на этом отрезке, то на
существует только один корень уравнения (1).Таким образом, уравнение (1) имеет на
единственный корень, если выполняются условия:

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

Полезным средством для отделения корней является также использование теоремы Штурма.

Решение третьей задачи осуществляется различными итерационными (численными) методами: методом дихотомии, методом простой итерации, методом Ньютона, методом хорд и т.д.

Пример Решим уравнение
методом простой итерации . Зададим
. Построим график функции.

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

Напомним, что исходное уравнение (1) в методе простой итерации преобразуется к виду
и итерации осуществляются по формуле:

(3)

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

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

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

для
. Обратите внимание, что условие сходимости выполняется не
, поэтому мы и берем отрезок изоляции корня
. Попутно заметим, что при представлении нашего уравнения в виде
, не выполняется условие сходимости метода:
на отрезке
. На графике видно, что
возрастает быстрее, чем функция
­­ (|tg| угла наклона касательной к
на отрезке
)

Выберем
. Организуем итерации по формуле:

Программно организуем процесс итераций с заданной точностью:

> fv:=proc(f1,x0,eps)

> k:=0:

x:=x1+1:

while abs(x1-x)> eps do

x1:=f1(x):

print(evalf(x1,8)):

print(abs(x1-x)):

:printf("Кол. итер.=%d ",k):

end :

На 19 итерации мы получили корень нашего уравнения

c абсолютной погрешностью

Решим наше уравнение методом Ньютона . Итерации в методе Ньютона осуществляются по формуле:

Метод Ньютона можно рассматривать как метод простой итерации с функцией, тогда условие сходимости метода Ньютона запишется в виде:

.

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

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

Программно организуем процесс итераций с заданной точностью. На 4 итерации получим корень уравнения

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

методом Ньютона с
, находим корень уравнения на [-1,5;-1]:

Задание : Решить нелинейные уравнения с точностью

0.

деления отрезка пополам (дихотомии)

простой итерации.

Ньютона (касательных)

секущих – хорд.

Варианты заданий рассчитываются следующим образом: номер по списку делится на 5 (
), целая часть соответствует номеру уравнения, остаток – номеру метода.

Кафедра физхимии ЮФУ (РГУ)
ЧИСЛЕННЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ
Материалы к лекционному курсу
Лектор – ст. преп. Щербаков И.Н.

Системы нелинейных уравнений

При решении задач моделирования поведения химических систем достаточно часто приходится решать системы уравнений, нелинейных по отношению к переменным. Системы n линейных уравнений с n неизвестными x 1 , x 2 , ..., x n в общем случае принято записывать следующим образом:

где F 1 , F 2 ,…, F n – любые функции независимых переменных, в том числе и нелинейные относительно неизвестных.

Как и в случае систем линейных уравнений, решением системы является такой вектор (или векторы) (X * ) , который при подстановке обращает одновременно все уравнения системы в тождества.

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

Рассмотрим несколько простейших итерационных методов решения систем нелинейных уравнений, а именно, метод простой итерации, метод Зейделя и метод Ньютона.

Метод простой итерации

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

Выбирая затем вектор начального приближения

подставляют его в преобразованную систему уравнений. Из первого уравнения получают новое приближение к первой переменной, из второго – второй и т. д. Полученное уточненное значение переменных снова подставляют в эти уравнения и т.д.Таким образом, на (i+1 ) -м шаге итерационной процедуры имеем

Метод Зейделя

Модификация Зейделя алгоритма простой итерации заключается в использовании уточненных значений переменных уже на текущем итерационном шаге. Так, для уточнения значений первой переменной используются только значения предыдущего шага, для второй переменной – значение x 1 текущего шага, а остальных – от предыдущего и т.д.:

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

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

Рассмотрим метод на примере системы двух уравнений с двумя неизвестными:

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

Вспомним, что для функции одной переменной разложение в ряд Тейлора в окрестности некоторой точки x 0 имеет следующий вид:

после пренебрежения всеми членами, кроме линейного:

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

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

Запишем для функции F 1 2-х переменных линейную часть разложения в ряд Тейлора в окрестности выбранной точки

для второго уравнения, аналогично

Если значения переменных x 1 и x 2 являются решением, то оба уравнения системы должны обратиться в ноль, поэтому полученные разложения приравниваем нулю.

Для краткости записи введем следующие обозначения:

Приращение i -ой переменной

Значение первой частной производной функции F j по переменной x i при значении переменных

– значение j -ой функции при соответствующих значениях переменных, то есть невязка j ‑го уравнения.

Получим систему линейных уравнений 2 x 2 относительно приращения переменных

Или, в матричной форме,

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

Сложение его с вектором начального приближения дает новые значения переменных.

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

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

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

3. Решается система линейных уравнений относительно приращений переменных.

4. к вектору начального приближения прибавляется вектор приращений

5. проверяется условие сходимости и, если оно не достигнуто, то процедура повторяется с п. 2.

Метод легко обобщается на систему уравнений любой размерности.

Для функции F 1 n переменных линейная часть разложения в ряд Тейлора в окрестности точки записывается так

После разложения всех уравнений системы и используя введенные ранее обозначения, после преобразования получим систему линейных уравнений порядка n относительно приращения переменных Δ x i

Или, в матричной форме,

В сокращенном виде можно записать так - (F" )(Δ x ) = - (F ) , где матрица значений частных производных – (F" ) – называется матрицей Якоби или якобианом системы уравнений.

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

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

где эпсилон – достаточно малое число.

Методы контроля сходимости итерационных методов
решения систем

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

1. Норма (эвклидова или -максимум) вектора невязок

2. Эвклидова норма вектора относительных отклонений переменных

3. Норма-максимум вектора относительных отклонений

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

Матрица частных производных (в аналитическом виде)

Система линейных уравнений

Может быть решена аналитически или методом Крамера или методом обращения матрицы. Возьмем начальное приближение x = 0,15, y = 0,17

Первая итерация:

Матрица Якоби - вектор значений функции Рассчитанный вектор поправок Новое приближение x = 0,15 + 0,028704 = 0,178704, y = 0,17 + 0,090926 = 0,260926 Вторая итерация: Рассчитанный вектор поправок Новое приближение x = 0,196656, y = 0,293359 Третья итерация: Рассчитанный вектор поправок Новое приближение x = 0,199867, y = 0,299739 Уже на 6-й итерации эвклидова норма вектора невязок составляет 2.8∙10 -13 , максимальное относительное изменение переменных составляет 1.6∙10 -12 и решение сходится к x = 0.2, y = 0.3 с абсолютной погрешностью менее 5∙10 -7 . Метод простой итерации при этих же начальных условиях сходится с такой точностью на 33-м шаге, модификация Зейделя – на 31-м шаге. На рисунке ниже представлен пример организации вычислений при решении рассмотренной системы в программе MS Excel
Пояснения: В ячейки В3 и В4 помещены начальные приближения к решению системы (значения х 0 и у 0 , соответственно). В диапазоне ячеек D3:E4 помещены формулы для вычисления матрицы Якоби, при условии что х находится в ячейке В3, а у - в ячейке В4 (формулы приведены на рисунке ниже). В ячейках G3:G4 рассчитывается значение вектора невязок с отрицательным знаком.
В ячейке Н3 вычисляется эвклидова норма вектора невязок. В ячейках I3:I4 - решается система линейных уравнений и вычисляется вектор поправок к решению. Для этого обращается матрица коэффициентов системы (матрица Якоби) и умножается на вектор-столбец свободных членов (отрицательный вектор невязок). Формула в этот диапазон ячеек вводится как формула массива . Рядом - в ячейке J3 - рассчитывается норма вектора поправок для контроля сходимости (см. формулы на рисунке ниже).
Полученные в ячейках I3:I4 значения поправок на втором итерационном цикле прибавляются к начальному приближению (в ячейках В6:В7) и далее вычисления повторяются аналогично первому циклу. Набранные в строках 6 и 7 рабочего листа формулы могут копироваться до тех пор, пока не будет достигнута необходимая точность.

Задачи, сводящиеся к решению системы нелинейных уравнений

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

Расчетная формула метода Ньютона имеет вид:

где n=0,1,2,..

Геометрически метод Ньютона означает, что следующее приближение к корню есть точка пересечения с осью ОХ. касательной, проведенной к графику функцииy=f(x) в точке .

Теорема о сходимости метода Ньютона.

Пусть - простой корень уравнения, в некоторой окрестности которого функция дважды непрерывно дифференцируема.

Тогда найдется такая малая - окрестность корня, что при произвольном выборе начального приближенияиз этой окрестности итерационная последовательность метода Ньютона не выходит за пределы окрестности и справедлива оценка

Метода Ньютона (1) чувствителен к выбору начального приближения x 0 .

На практике для монотонной сходимости метода необходимо :

1-ая производная f(x)

2-ая производная f(x) должна быть знакопостоянна на интервале локализации [ a , b ] изолированного корня;

за начальное приближение x 0 выбирается та граница интервала локализации, на которой произведение функции на ее 2-ю производную больше нуля (f(c)f ’’ (c) > 0 , где с – одна из границ интервала) .

. При заданной точности >

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

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

Метод простой итерации (метод последовательных повторений).

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

Это преобразование можно выполнить различными способами.

Функция называется итерационной функцией.

Расчетная формула метода простой итерации имеет вид:

где n=0,1,2,..

Теорема о сходимости метода простой итерации.

Пусть в некоторой - окрестности корняфункциянепрерывно дифференцируема и удовлетворяет неравенству

где 0 < q < 1 - постоянная.

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

со скоростью геометрической последовательности и справедлива оценка погрешности:

Критерий окончания итерационного процесса .

При заданной точности >0 вычисления следует вести до тех пор пока не окажется выполненным неравенство

Если величина , то можно использовать более простой критерий окончания итераций:

Если в неравенстве (5) q > 1 , то итерационный метод (4) расходится.

Если в неравенстве (5) q = 1 , то итерационный метод (4) может как сходится так и расходится.

В том случае, если q > = 1 , то итерационный метод (4) расходится и

применяется метод простой итерации с итерационным параметром .

Ключевой момент в применении состоит в эквивалентном преобразовании уравнения :

αf(x) = 0

x = x +αf(x) , (9)

где α – итерационный параметр (вещественная константа).

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

x (n+1) = x (n) + αf(x (n) ) , (10)

где n=0,1,2,..

Итерационный процесс, построенный по форме (10) сходится , если:

1-ая производная функции f(x) знакопостоянна и ограничена на интервале локализации изолированного корня ;

знак итерационного параметра α противоположен знаку 1-ой производной функции f(x) на интервале локализации изолированного корня ;

модуль значения итерационного параметра α оценивается из неравенства

| α | < 2/M , (11)

где М – максимум модуля 1-ой производной функции f(x)

Тогда при таком выборе итерационного параметра  метод (10) сходится при любом значении начального приближения, принадлежащем интервалу , со скоростью геометрической прогрессии со знаменателем q равным

где m – минимум модуля 1-ой производной функции f(x) на интервале локализации изолированного корня .

Система нелинейных уравнений имеет вид:

Здесь - неизвестные переменные, а система (7) называется нормальной системой порядка, если хотя бы одна из функций нелинейна.

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

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

Метод простых итераций для решения систем нелинейных уравнений

Из исходной системы (7) путем эквивалентных преобразований переходим к системе вида:

Итерационный процесс, определяемый формулами

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

Распишем первое условие:

Распишем второе условие:

Рассмотрим один из способов приведения системы (7) к виду (8), допускающему сходящиеся итерации.

Пусть задана система второго порядка вида:

Требуется привести ее к виду:

Умножим первое уравнение системы на неизвестную постоянную, второе - на, затем сложим их и добавим в обе части уравнения. Получим первое уравнение преобразованной системы

Неизвестные постоянные определим из достаточных условий сходимости

Запишем эти условия более подробно:

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

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

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

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

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

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

Трудности при использовании метода Ньютона:

существует ли обратная матрица?

не выходит ли за пределы области?

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

Но ответа на второй вопрос, модифицированный метод Ньютона не дает.

Итерационный процесс по формулам (8) или (10) заканчивается, если выполняется следующее условие

Достоинством метода Ньютона является его быстрая сходимость по сравнению с методом простых итераций.