Метод итераций с переходом к уравнению. Решение нелинейных уравнений. Системы нелинейных уравнений

Задание:

1) Используя метод итераций, решить систему

2) Используя метод Ньютона, решить систему

нелинейных уравнений с точностью до 0,001.

Задание №1Используя метод итераций, решить систему нелинейных уравнений с точностью до 0,001.

Теоретическая часть.

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

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

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

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

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

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

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

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

.

Варианты заданий

№1. 1)
2)

№2. 1)
2)

№3. 1)
2)

№4. 1)
2)

№5. 1)
2)

№6. 1)
2)

№7. 1)
2)

№8. 1)
2)

№9. 1)
2)

№10.1)
2)

№11.1)
2)

№12.1)
2)

№13.1)
2)

№14.1)
2)

№15.1)
2)

№16.1)
2)

№17.1)
2)

№18.1)
2)

№19.1)
2)

№20.1)
2)

№21. 1)
2)

№22. 1)
2)

№23. 1)
2)

№24. 1)
2)

№25. 1)
2)

№26. 1)
2)

№27. 1)
2)

№28. 1)
2)

№29. 1)
2)

№30. 1)
2)

Образец выполнения задания

№1. 1)
2)

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

Перепишем данную систему в виде:

Отделение корней производим графически (рис.1). Из графика видим, что система имеет одно решение, заключенное в области D: 0<х <0,3;-2,2<y <-1,8.

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

Так как ,то имеем в области D

+ = ;

+ =

Таким образом, условия сходимости выполняются.

Таблица №2

п
	0,15	-2	-0,45	-0,4350	-0,4161	-0,1384
	0,1616	-2,035	-0,4384	-0,4245	-0,4477	-0,1492
	0,1508	-2.0245	-0,4492	-0,4342	-0,4382	-0,1461
	0.1539	-2,0342.	-0,4461	-0.4313	-0,4470	-0,1490
	0.1510	-2,0313	-0,4490	-0,4341	-0,4444	-0.1481
	0,1519	-2,0341	-0,4481	-0,4333	-0,4469	-0,1490
	0,1510	-2.0333	-0.449	-0,4341	-0.4462	-0,1487
	0.1513	-2.0341	-0,4487	-0,4340	-0,4469	-0.1490
	0.1510	-2,0340

За начальные приближения принимаем х о =0,15, у 0 = -2.

(таб.№2). Тогда ответ запишется:

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

Отделение корней производим графически (рис.2). Для построения графиков функций составим таблицу значений функций и , входящих в первое и второе уравнения (табл. I).

Значения для x можно брать исходя из следующих условий: из первого уравнения 1≤1,2х+0,4≤1 , т.е. 1,16≤х≤0,5 ; из второго уравнения , т.е. . Таким образом, .

Система имеет два решения. Уточним одно из них, принадлежащее области D: 0,4<x <0,5;

0,76<y <0,73. За начальное приближение примем Имеем:

Таблица №3

x	-1,1	-1	-0,8	-0,6	-0,2	-0,4		0,2	0,4	0,5
х 2	1.21		0,64	0,36	0,04	0,16		0,04	0.16	0,25
0,8 х 2	0,97	0,8	0,51	0,29	0,032	0,13		0,032	0,13	0,2
1 -0,8 х 2	0,03	0,2	0,49	0,71	0,97	0,87		0,97	0.87	0,8
	0,02	0,13	0,33	0,47	0,65	0,58	0,67	0,65	0,58	0.53
	±0,14	±0,36	±0,57	±0,69	±0,81	±0,76	±0,82	±0.81	±0,76	±0.73
1,2x	-1,32	-1,2	-0,9б"	-0,72	-0,24	-0,48		0,24	0,48	0,6
0,4+1,2x	-0,92	-0,8	-0,56	-0,32	0,16	-0,08	0,4	0,64	0.88
2x-y	-1.17	-0,93	-0,59	-0,33	0,16	-0,08	0,41	0,69	2.06 1,08	1,57
	-1,03	-1,07	-1,01	-0,87	-0,56	-0,72	-0,41	-0,29	-1,26 -1,28	-0.57

Уточнение корней проводим методом Ньютона:

где ; ;

;
;

Все вычисления производим по таблице 3

Таблица 3			0,10	0,017	-0,0060	0,0247	-0,0027	-0,0256	0,0001	0,0004
		0,2701	0,0440	-0,0193	0,0794	-0,0080	-0,0764	-0,0003	0,0013
		2,6197	3,2199	2,9827	3,1673
		-0,0208	-2,25	0,1615	-2,199	0,1251	-2,1249	0,1452	-2,2017
		-1,1584	0,64	-1,523	0,8	-1,4502	0,7904	-1,4904	0,7861
		0,1198	-0,0282	-0,0131	0,059	-0,0007	-0,0523	-0,0002	0,0010
		0,9988	0,0208	0,9869	-0,1615	0,9921	-0,1251	-0,9894	-0,1452
	0,55	0,733	1,6963	1,7165
		0,128	0,8438	0,2	0,8059	0,1952	0,7525	0,1931	0,8079
		0,4	0,75	0,50	-0,733	0,4940	-0,7083	0,4913	-0,7339	0,4912	-0,7335	Ответ: x ≈0,491 y ≈ 0,734
n

Контрольные вопросы

1) Представьте на графике возможные случаи решения системы двух нелинейных уравнений.

2) Сформулируйте постановку задачи о решении системы n-линейных уравнений.

3) Приведите итерационные формулы метода простой итерации в случае системы двух нелинейных уравнений.

4) Сформулируйте теорему о локальной сходимости метода Ньютона.

5) Перечислите трудности, возникающие при использовании метода Ньютона на практике.

6) Объяснить каким образом можно модифицировать метод Ньютона.

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

Лабораторная работа №3

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

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

При решении задач моделирования поведения химических систем достаточно часто приходится решать системы уравнений, нелинейных по отношению к переменным. Системы 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 обозначить следующим образом то условие прохождения графика функции через все таблично заданные точки можно записать в виде следующей системы: Другой пример - поиск экстремума (минимума или максимума) функции нескольких переменных Условием экстремума является одновременное равенство нулю всех частных производных функции. Таким образом, необходимо решить систему уравнений следующего вида, которая, в общем случае, будет нелинейной

Все люди от природы стремятся к знанию. (Аристотель. Метафизика)

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

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

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

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

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

В простейшем случае у нас имеется функция , заданная на отрезке (a , b ) и принимающая определенные значения.

Каждому значению x из этого отрезка мы можем сопоставить число , это и есть функциональная зависимость, ключевое понятие математики.

Нам нужно найти такое значение при котором такие называются корнями функции

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

Метод деления пополам

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

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

Алгоритм состоит в следующем.

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

Поделим отрезок пополам и введем среднюю точку .

Тогда либо , либо .

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

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

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

К достоинствам метода деления пополам следует отнести его высокую надежность и простоту.

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

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

Метод Ньютона: теоретические основы

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

Уравнение касательной к функции в точке имеет вид:

В уравнении касательной положим и .

Тогда алгоритм последовательных вычислений в методе Ньютона состоит в следующем:

Сходимость метода касательных квадратичная, порядок сходимости равен 2.

Таким образом, сходимость метода касательных Ньютона очень быстрая.

Запомните этот замечательный факт!

Без всяких изменений метод обобщается на комплексный случай.

Если корень является корнем второй кратности и выше, то порядок сходимости падает и становится линейным.

Упражнение 1 . Найти с помощью метода касательных решение уравнения на отрезке (0, 2).

Упражнение 2. Найти с помощью метода касательных решение уравнения на отрезке (1, 3).

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

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

Визуализация метода Ньютона

Метод Ньютона (метод касательных) применяется в том случае, если уравнение f (x ) = 0 имеет корень , и выполняются условия:

1) функция y = f (x ) определена и непрерывна при ;

2) f (a )· f (b ) < 0 (функция принимает значения разных знаков на концах отрезка [a ; b ]);

3) производные f" (x ) и f"" (x ) сохраняют знак на отрезке [a ; b ] (т.е. функция f (x ) либо возрастает, либо убывает на отрезке [a ; b ], сохраняя при этом направление выпуклости);

Основная идея метода заключается в следующем: на отрезке [a ; b ] выбирается такое число x 0 , при котором f (x 0 ) имеет тот же знак, что и f "" (x 0 ), т. е. выполняется условие f (x 0 )· f "" (x ) > 0 . Таким образом, выбирается точка с абсциссой x 0 , в которой касательная к кривой y = f (x ) на отрезке [a ; b ] пересекает ось Ox . За точку x 0 сначала удобно выбирать один из концов отрезка.

Рассмотрим метод Ньютона на конкретном примере.

Пусть нам дана возрастающая функция y = f(x) =x 2 -2, непрерывная на отрезке (0;2), и имеющая f " (x) = 2 x > 0 и f "" (x) = 2 > 0 .

Рисунок 1 . f(x) =x 2 -2

Уравнение касательной в общем виде имеет представление:

y-y 0 = f " (x 0)·(x-x 0).

В нашем случае: y-y 0 =2x 0 ·(x-x 0). В качестве точки x 0 выбираем точку B 1 (b; f(b)) = (2,2). Проводим касательную к функции y = f(x) в точке B 1 , и обозначаем точку пересечения касательной и оси Ox точкой x 1 . Получаем уравнение первой касательной:y-2=2·2(x-2), y=4x-6.

Ox: x 1 =

Рисунок 2. Результат первой итерации

y=f(x) Ox через точку x 1 , получаем точку В 2 =(1.5; 0.25) . Снова проводим касательную к функции y = f(x) в точке В 2 , и обозначаем точку пересечения касательной и оси Ox точкой x 2 .

Уравнение второй касательной: y -0.25=2*1.5(x -1.5), y = 3 x - 4.25.

Точка пересечения касательной и оси Ox: x 2 = .

Рисунок 3. Вторая итерация метода Ньютона

Затем находим точку пересечения функции y=f(x) и перпендикуляра, проведенного к оси Ox через точку x 2 , получаем точку В 3 и так далее.

Рисунок 4. Третий шаг метода касательных

Первое приближение корня определяется по формуле:

= 1.5.

Второе приближение корня определяется по формуле:

=

Третье приближение корня определяется по формуле:

Таким образом, i -ое приближение корня определяется по формуле:

Вычисления ведутся до тех пор, пока не будет достигнуто совпадение десятичных знаков, которые необходимы в ответе, или заданной точности e - до выполнения неравенства | xi - xi -1 | < e .

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

Рисунок 5. Корень из 2, посчитанный на калькуляторе

Как видно, уже на третьем шаге мы получили погрешность меньше 0.000002.

Таким образом можно вычислить значение величины "корень квадратный из 2" с любой степенью точности. Этот замечательный метод был изобретен Ньютоном и позволяет находить корни очень сложных уравнений.

Метод Ньютона: приложение на С++

В данной статье мы автоматизируем процесс вычисления корней уравнений, написав консольное приложение на языке C++. Разрабатывать его мы будем в Visual C++ 2010 Express, это бесплатная и очень удобная среда разработки С++.

Для начала запустим Visual C++ 2010 Express. Появится стартовое окно программы. В левом углу нажмем «Создать проект».

Рис. 1. Начальная страница Visual C++ 2010 Express

В появившемся меню выберем «Консольное приложение Win32», введем имя приложение «Метод_Ньютона».

Рис. 2. Создание проекта

// Метод_Ньютона.cpp: определяет точку входа для консольного приложения #include "stdafx.h" #include using namespace std; float f(double x) //возвращает значение функции f(x) = x^2-2 float df(float x) //возвращает значение производной float d2f(float x) // значение второй производной int _tmain(int argc, _TCHAR* argv) int exit = 0, i=0;//переменные для выхода и цикла double x0,xn;// вычисляемые приближения для корня double a, b, eps;// границы отрезка и необходимая точность cout<<"Please input \n=>"; cin>>a>>b; // вводим границы отрезка, на котором будем искать корень cout<<"\nPlease input epsilon\n=>"; cin>>eps; // вводим нужную точность вычислений if (a > b) // если пользователь перепутал границы отрезка, меняем их местами if (f(a)*f(b)>0) // если знаки функции на краях отрезка одинаковые, то здесь нет корня cout<<"\nError! No roots in this interval\n"; if (f(a)*d2f(a)>0) x0 = a; // для выбора начальной точки проверяем f(x0)*d2f(x0)>0 ? xn = x0-f(x0)/df(x0); // считаем первое приближение cout<<++i<<"-th iteration = "< while(fabs(x0-xn) > eps) // пока не достигнем необходимой точности, будет продолжать вычислять xn = x0-f(x0)/df(x0); // непосредственно формула Ньютона cout<<++i<<"-th iteration = "< cout<<"\nRoot = "< cout<<"\nExit?=>"; } while (exit!=1); // пока пользователь не ввел exit = 1

Посмотрим, как это работает. Нажмем на зеленый треугольник в верхнем левом углу экрана, или же клавишу F5.

Если происходит ошибка компиляции «Ошибка error LNK1123: сбой при преобразовании в COFF: файл недопустим или поврежден», то это лечится либо установкой первого Service pack 1, либо в настройках проекта Свойства -> Компоновщик отключаем инкрементную компоновку.

Рис. 4. Решение ошибки компиляции проекта

Мы будем искать корни у функции f(x) = x2-2 .

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

У нас появилось окно приложения:

Рис. 5. Ввод входных данных

Введем границы отрезка 3 и 5, и точность 0.05. Программа, как и надо, выдала сообщение об ошибке, что на данном отрезке корней нет.

Рис. 6. Ошибка «На этом отрезке корней нет!»

Выходить мы пока не собираемся, так что на сообщение «Exit?» вводим «0».

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

Рис. 7. Вычисление корня с необходимой точностью

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

Чтобы выйти из приложения, введем «Exit?» => 1.

Метод секущих

Чтобы избежать вычисления производной, метод Ньютона можно упростить, заменив производную на приближенное значение, вычисленное по двум предыдущим точкам:

Итерационный процесс имеет вид:

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

Порядок сходимости метода секущих ниже, чем у метода касательных и равен в случае однократного корня .

Эта замечательная величина называется золотым сечением:

Убедимся в этом, считая для удобства, что .

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

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

После подстановки имеем: и

Для сходимости необходимо, чтобы было положительным, поэтому .

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

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

Как только начнется рост, вычисления прекращают и последнюю итерацию не используют.

Такая процедура определения момента окончания итераций называется приемом Гарвика.

Метод парабол

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

Для этого заменим, аналогично методу секущих, функцию интерполяционной параболой проходящей через точки , и .

В форме Ньютона она имеет вид:

Точка определяется как тот из корней этого полинома, который ближе по модулю к точке .

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

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

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

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

Задачу нахождения решений уравнений можно формулировать как задачу нахождения корней: , или как задачу нахождения неподвижной точки.

Пусть и — сжатие: (в частности, тот факт, что — сжатие, как легко видеть, означает, что).

По теореме Банаха существует и единственна неподвижная точка

Она может быть найдена как предел простой итерационной процедуры

где начальное приближение — произвольная точка промежутка .

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

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

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

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

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

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

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

ПО КУРСУ:

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

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

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) теоремы имеем .

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

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

Рассмотрим, как данный метод реализуется при решении СЛАУ. Метод простой итерации имеет следующий алгоритм:

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

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

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

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

x - =β - +α*x -

Это можно сделать множеством способов, например, так: из первого уравнения выразить х 1 через другие неизвестные, из второго- х 2 , из третьего- х 3 и т.д. При этом используем формулы:

α ij = -(a ij / a ii)

i = b i /a ii
Следует снова убедиться, что полученная система нормального вида соответствует условию сходимости:

∑ (j=1) |α ij |≤ 1, при этом i= 1,2,...n

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

x (0) - начальное приближение, выразим через него х (1) , далее через х (1) выразим х (2) . Общая формула а матричном виде выглядит так:

x (n) = β - +α*x (n-1)

Вычисляем, пока не достигнем требуемой точности:

max |x i (k)-x i (k+1) ≤ ε

Итак, давайте разберем на практике метод простой итерации. Пример:
Решить СЛАУ:

4,5x1-1.7x2+3.5x3=2
3.1x1+2.3x2-1.1x3=1
1.8x1+2.5x2+4.7x3=4 с точностью ε=10 -3

Посмотрим, преобладают ли по модулю диагональные элементы.

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

7,6x1+0.6x2+2.4x3=3

Из третьего вычтем первое:

2,7x1+4.2x2+1.2x3=2

Мы преобразовали исходную систему в равноценную:

7,6x1+0.6x2+2.4x3=3
-2,7x1+4.2x2+1.2x3=2
1.8x1+2.5x2+4.7x3=4

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

x1=0.3947-0.0789x2-0.3158x3
x2=0.4762+0.6429x1-0.2857x3
x3= 0.8511-0.383x1-0.5319x2

Проверяем сходимость итерационного процесса:

0.0789+0.3158=0,3947 ≤ 1
0.6429+0.2857=0.9286 ≤ 1
0.383+ 0.5319= 0.9149 ≤ 1 , т.е. условие выполняется.

0,3947
Начальное приближение х (0) = 0,4762
0,8511

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

0,08835
x (1) = 0,486793
0,446639

Подставляем новые значения, получаем:

0,215243
x (2) = 0,405396
0,558336

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

x (7) = 0,441091

Проверим правильность полученных результатов:

4,5*0,1880 -1.7*0,441+3.5*0,544=2,0003
3.1*0,1880+2.3*0,441-1.1x*0,544=0,9987
1.8*0,1880+2.5*0,441+4.7*0,544=3,9977

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

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