Метод Ньютона (метод касательных). Решение систем нелинейных алгебраических уравнений

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

Так как

   

   

то в области D имеем

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

Вычисления производим по формулам

         

За начальные приближения принимаем x0=0.15 и y0=-2

n	xn	yn	xn-0,6	sin(xn-0,6)	cosyn
0	0,15	-2	-0,45	-0,435	-0,4161	-0,1387
1	0,16128	-2,035	-0,4387	-0,4248	-0,4477	-0,1492
2	0,15077	-2,0248	-0,4492	-0,4343	-0,4385	-0,1462
3	0,15382	-2,0343	-0,4462	-0,4315	-0,4471	-0,149
4	0,15098	-2,0315	-0,449	-0,4341	-0,4446	-0,1482
5	0,1518	-2,0341	-0,4482	-0,4333	-0,4469	-0,149
6	0,15104	-2,0333	-0,449	-0,434	-0,4462	-0,1487
7	0,15126	-2,034	-0,4487	-0,4338	-0,4468	-0,1489
8	0,15105	-2,0338	-0,4489	-0,434	-0,4467	-0,1489

Так как δ≤ε, где , то

Ответ: 

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

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

Пусть известно приближение xi(k) решения системы нелинейных уравнений xi*. Введем в рассмотрение поправку Dxi как разницу между решением и его приближением: 

,

Подставим полученное выражение для xi* в исходную систему.

Неизвестными в этой системе нелинейных уравнений являются поправки Dxi. Для определения Dxi нужно решить эту систему. Но решить эту задачу так же сложно, как и исходную. Однако эту систему можно линеаризовать, и, решив ее, получить приближенные значения поправок Dxi для данного приближения, т.е. Dxi(k). Эти поправки не позволяют сразу получить точное решение , но дают возможность приблизиться к решению, – получить новое приближение решения

,  

Для линеаризации системы следует разложить функцию fi в ряды Тейлора в окрестности xi(k), ограничиваясь первыми дифференциалами.

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

,    

Все коэффициенты этого уравнения можно вычислить, используя последнее приближение решения xi(k). Для решения системы линейных уравнений при n=2,3 можно использовать формулы Крамера, при большей размерности системы n – метод исключения Гаусса.

Значения поправок используются для оценки достигнутой точности решения. Если максимальная по абсолютной величине поправка меньше заданной точности e, расчет завершается. Таким образом, условие окончания расчета:

Можно использовать и среднее значение модулей поправок:

В матричной форме систему можно записать как:

 

где:

,  -  матрица Якоби (производных),

- вектор поправок

- вектор-функция

W(X(k)) – матрица Якоби, вычисленная для очередного приближения.

F(X(k)) –  вектор-функция, вычисленная для очередного приближения.

Выразим вектор поправок ∆X(k) из :

где W-1 – матрица, обратная матрице Якоби.

Окончательно формула последовательных приближений метода Ньютона  решения СНУ в матричной форме имеет вид:

 

Достаточные условия сходимости для общего случая имеют очень сложный вид, и на практике проверяются редко. Нужно отметить, что метод сходится очень быстро (за 3 – 5 итераций), если det|W| ¹ 0 и начальное приближение X(0) выбрано близким к решению (отличаются не более чем на 10%).

Алгоритм решения СНУ методом Ньютона состоит в следующем:

1) Задается размерность системы n, требуемая точность ε, начальное приближенное решение .

2) Вычисляются элементы матрицы Якоби 

3) Вычисляется обратная матрица .

4) Вычисляется вектор функция ,  , .

5) Вычисляются вектор поправок  

6) Уточняется решение  

7) Оценивается достигнутая точность 

8) Проверяется условие завершения итерационного процесса δ≤ε

Если оно не соблюдается, алгоритм выполняется снова с пункта 2.

Для уменьшения количества арифметических действий Рафсон предложил не вычислять обратную матрицу W-1, а вычислять поправки как решение СЛУ: , данный метод получил название метод Ньютона-Рафсона.

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

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

Используя метод Ньютона, решить систему нелинейных уравнений с точностью до 0,002.

Отделение корней производим графически.

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

x	-1,1	-1	-0,8	-0,6	-0,4	-0,2	0,2	0,4	0,5
x2	1,21	1	0,64	0,36	0,16	0,04	0,04	0,16	0,25
0.8x2	0,97	0,80	0,51	0,29	0,13	0,03	0,03	0,13	0,20
1-0.8x2	0,03	0,20	0,49	0,71	0,87	0,97	0,97	0,87	0,80
	0,02	0,13	0,33	0,47	0,58	0,65	0,65	0,58	0,53
y2	0,15	0,37	0,57	0,69	0,76	0,80	0,80	0,76	0,73
1.2x	-1,32	-1,2	-0,96	-0,72	-0,48	-0,24	0,24	0,48	0,6
0.4+1.2x	-0,92	-0,8	-0,56	-0,32	-0,08	0,16	0,64	0,88	1
2x-y	-1,17	-0,93	-0,59	-0,33	-0,08	0,16	0,69	1,08	1,57
y1	-1,03	-1,07	-1,01	-0,87	-0,72	-0,56	-0,29	-0,28	-0,57

Значения для x можно брать исходя из следующих условий:

  из первого уравнения -1<1.2x+4<1, т.е. -1.16<x<0.5;

  из второго уравнения - <x< , т.е. -1.12<x<1.12.

Таким образом,  -1.12<x<0.5.

Система имеет два решения. Уточним одно из них, принадлежащее области D: 0.4<x<0.5;  -0.76<y<-0.73 .

За начальное приближение примем x0=0.4; y0=-0.75.

Имеем следующие системы:

 

Найдем элементы матрицы Якоби , где , и значения функций в x0=0.4; y0=-0.75:

F(0,4;-0,75)=0,11978

G(0,4;-0,75)=-0,02825

где ;   ;

 

Итерационные формулы:

,

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

n	xn	0.8xn2	2xn-yn	sin(2xn-yn)	F(xn,yn)			detW	detW1	∆x
	yn	1.5yn2		cos(2xn-yn)	G(xn,yn)				detW2	∆y
0	0,40000	0,12800	1,55000	0,99978	0,11978	-1,15841	-0,02079	2,61973	0,27010	0,10310
	-0,75000	0,84375		0,02079	-0,02825	0,64000	-2,25000		0,04394	0,01677
1	0,50310	0,20249	1,73943	0,98581	-0,01791	-1,53568	0,16784	3,24291	-0,03790	-0,01169
	-0,73323	0,80644		-0,16784	0,00893	0,80496	-2,19969		-0,00071	-0,00022
2	0,49142	0,19319	1,71628	0,98944	-0,00026	-1,48994	0,14497	3,16440	-0,00057	-0,00018
	-0,73345	0,80692		-0,14497	0,00011	0,78627	-2,20034		-0,00005	-0,00001
3	0,49124
	-0,73346

Так как δ<ε, то можно прекратить производить вычисления. Таким образом, ответ: 

2.2.3.Метод спуска

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

           

 Из функций f(x,y), g(x,y) системы образуем новую функцию

Так как эта функция не отрицательная, то найдется точка (вообще говоря, не единственная) такая, что

Пространственная интерпретация метода наискорейшего спуска для функции:

 

Траектория наискорейшего спуска для функции в плоскости ХОУ

Следовательно, если тем или иным способом удается получить точку , минимизирующую функцию Ф(x,y), и если при этом окажется, что

, то точка - истинное решение системы, поскольку

Последовательность точек - приближений к точке минимума функции Ф(х,у) - обычно получают по рекуррентной формуле

     

где , - вектор, определяющий направление минимизации, а - скалярная величина, характеризующая величину шага минимизации (шаговый множитель). Учитывая геометрический смысл задачи минимизации функций двух переменных Ф(x,y) - "спуск на дно" поверхности z = Ф(x,y), итерационный метод можно назвать методом спуска, если вектор при каждом k является направлением спуска (т. e. существует такое , что , и если множитель подбирается так, чтобы выполнялось условие релаксации , означающее переход на каждой итерации в точку с меньшим значением минимизируемой функции.

Таким образом, при построении численного метода вида минимизации функции Ф(x,y) следует ответить на два главных вопроса: как выбирать направление спуска и как регулировать длину шага в выбранном направлении с помощью скалярного параметра - шагового множителя .

При выборе направления спуска естественным является выбор такого направления, в котором минимизируемая функция убывает наиболее быстро.

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