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

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

Лекция

2. Постановка задачи

Решить систему нелинейных уравнений:
F1 ( x , y ) 0
F2 ( x , y ) 0
2

3. Этапы решения

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

4. Существование и единственность решения.

100
80
корень один
F2(x,y)
60
40
F1(x,y)
20
0
-6
-4
-2
0
2
4
6
-20
-40
-60
-80
4

5. Существование и единственность решения.

150
корней нет
100
F1(x,y)
50
F2(x,y)
0
-6
-4
-2
0
2
4
6
-50
-100
5

6. Существование и единственность решения.

140
корня три
F2(x,y)
120
100
80
60
40
F1(x,y)
20
0
-6
-4
-2
0
2
4
6
-20
6

7. Этап 3

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

8.

Методы решения
систем нелинейных уравнений
Для применения известных численных
методов исходная система может быть
приведена к виду:
x=φ1(x,y);
y=φ2(x,y);
8

9.

Метод Якоби (простых итераций)
Алгоритм поиска решения задается
формулами
xn+1= φ1(xn,yn);
yn+1= φ2(xn,yn).
9

10. Метод Гаусса - Зейделя

Алгоритм поиска решения задается
формулами
x n+1= φ1(xn,yn);
yn+1= φ2(xn+1,yn).
Процесс вычисления заканчивается, когда
xn xn 1 и yn yn 1
10

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

Общий вид системы нелинейных уравнений:
F1(x1, x2, x3, …, xn) = 0
F2(x1, x2, x3, …, xn) = 0
………………………….
Fn(x1, x2, x3, …, xn) = 0
11

12. Метод Якоби

x1m+1 = f1(x1m, x2m, x3m, …, xnm)
x2m+1 = f2(x1m, x2m, x3m, …, xnm)
x3m+1 = f3(x1m, x2m, x3m, …, xnm)
………………………………..
xnm+1 = fn(x1m, x2m, x3m, …, xnm)
12

13. Метод Гаусса - Зейделя

x1m+1 = f1(x1m, x2m, x3m, …, xnm)
x2m+1 = f2(x1m+1, x2m, x3m, …, xnm)
x3m+1 = f3(x1m+1, x2m+1, x3m, …, xnm)
……………………………………..
xnm+1 = fn(x1m+1, x2m+1, x3m+1, …, xnm)
13

14. Пример 1

Дана система
y x 1
2
2
y x 4
Построим графики этих
уравнений
14

15. Пример 1

y x 1
2
2
y
x
4
6
4
2
0
-2,5
-2
-1,5
-1
-0,5
0
0,5
1
1,5
2
2,5
-2
-4
-6
15

16. Пример 1

Приведем систему к виду
1
1 xk 1 , yk 1
xk y
k 1
2
yk 4 xk 1 2 xk 1 , yk 1
16

17. Пример 1

1
xk y
k 1
2
y
4
x
k 1
k
Пример 1
2,5
Корень x=0,52
x0=1
y=1,93
y0=2
2,0
1,5
1,0
0,5
0,0
0
0,2
0,4
0,6
0,8
1
1,2
1,4
18

18. Пример 1

2,5
1
xk y
k 1
2
y
4
x
k 1
k
Сходимость к корню
x=0,52 y=1,93
2,0
1,5
1,0
x0=1,8
y0=0,8
0,5
0,0
0
0,5
1
1,5
2
2,5
-0,5
-1,0
-1,5
-2,0
19

19. Пример 1

1
xk y
k 1
4
y x
1
k
k 1
2
xk 1
Пример 1
3,0
2,0
1,0
x0=-1,8
y0=-0,8
0,0
-2,5
-2
-1,5
-1
-0,5
0
0,5
1
1,5
-1,0
-2,0
Сходимость к корню
x=-0,52 y=-1,93
-3,0
-4,0
20

20. Пример 1

4
y
x
1
k
k 1
2
xk 1
x 1
k y
k
Пример 1
3
2
1
x0=-1,8
y0=-0,8
0
-2,5
-2
-1,5
-1
-0,5
0
0,5
1
1,5
-1
-2
Сходимость к корню
x=-0,52 y=-1,93
-3
-4
21

21. Пример 1

выводы
Вычисления в методе последовательных
приближений просты
Однако сложно найти такую систему
которая была бы эквивалентна исходной
системе и одновременно обеспечивала бы
сходимость
22

22. выводы

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

23. Метод Ньютона

Запишем систему двух уравнений с двумя
неизвестными в векторной форме:
F( z ) 0
x
z
y
f 1( x , y )
вектор функция
F
f 2( x , y )
24

24. Метод Ньютона

Обобщая формулу Ньютона на многомерный
случай получим:
k 1
z
'
z F z
k
k
1
F z
k
25

25. Метод Ньютона

f1
x
'
F z
f 2
x
f1
y
f 2
y
матрица Якоби вектор функции
26

26. Метод Ньютона

Пример 1 (метод Ньютона)
Применим метод к исходной системе
y x 1
F ( z ) 2
2
y x 4
y
'
F ( z )
2x
y x 1
2
2
y x 4
y x 1 0
2
2
y
x
4 0
x
2y
28

27. Операции с матрицами

Пример 1 (метод Ньютона)
Найдем матрицу, обратную к матрице производных:
F ( z )
'
1
2y x
2
2 2x y
2 y 2x
1
29

28. Пример 1 (метод Ньютона)

Окончательно получим итерационную схему
2
2
2
y
xy
1
x x y 4
x
2
2
2 y 2x
z
2
2
y 2 x xy 1 y x y 4
2
2
2 y 2x
30

29. Пример 1 (метод Ньютона)

3
2
1
x0=-1,8
y0=-0,8
0
-2,5
-2
-1,5
-1
-0,5
0
0,5
1
1,5
-1
-2
Сходимость к корню
x=-1,93 y=- 0,52
-3
-4
32