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

1.

Методы решения систем нелинейных
уравнений
Цель лекции: на примере метода Ньютона и
метода спуска рассмотреть технологию
решения задачи нахождения корней системы
нелинейных уравнений.
Дана система уравнений:
f1 ( x1 , x2 ,..., xn ) 0,
f 2 ( x1 , x2 ,..., xn ) 0,
………………………..
f n ( x1 , x2 ,..., xn ) 0.

2.

Введем обозначения
x1
x x2 , F ( x )
x
n 0
0
O ... .
...
0
f1 ( x ) f1 ( x1 , x2 ,..., xn )
f 2 ( x ) f 2 ( x1 , x2 ,..., xn )
...
...
...
...
f n ( x ) f n ( x1 , x2 ,...xn )

3.

Тогда исходную систему запишем
F (x) 0
относительно векторной функции F и
векторного аргумента x . Следовательно,
исходную задачу можно рассматривать как
задачу о нулях нелинейного отображения
F : Rn Rn .
В такой постановке задача является
обобщением задачи о нахождении решения
нелинейного уравнения для случая задачи
большой размерности.

4.

Однако, переход от
n 1
к
n 2
вносит в задачу нахождения нулей свою
специфику.
Метод Ньютона решения систем
нелинейных уравнений.
Пусть исходная система приведена к виду:
x1 1 ( x1 , x2 ,..., xn ),
x2 2 ( x1 , x2 ,..., xn ),
……………………..
xn n ( x1 , x2 ,..., xn ).

5.

или в компактной форме:
1 ( x ) 1 ( x1 , x2 ,..., xn )
2 ( x ) 2 ( x1 , x2 ,..., xn )
x ( x ) ...
...
...
...
( x ) ( x , x ,...x )
n
n n 1 2
Для задачи о неподвижной точке нелинейного
отображения
: Rn Rn
запишем

6.

формальное равенство:
где
( x ),
определяет метод простых
k
итераций и
k 0,1,2,..., n.
Пусть известно
x
x
( k 1)
(k )
k - е приближение
( x , x ,..., x )
(k )
1
(k )
2
(k )
n
одного из изолированных корней
1
2
n
x ( x , x ,..., x )
векторного уравнения
F ( x ) 0.
(k )

7.

Тогда точный корень уравнения можно
x x
представить:
(k )
x ,
(k )
где
x
(k )
поправка (погрешность корня). Имеем
F (x
(k )
x ) 0. Предполагая, что F (x )
(k )
непрерывно дифференцируема в некоторой
(k )
выпуклой области, содержащей x и x ,
разложим левую часть уравнения
F (x
(k )
x ) 0 по степеням малого
вектора x
(k )
(k )
,
ограничиваясь линейными

8.

членами
x ) F ( x ) F ( x ) x .
Под производной F (x ) следует понимать
матрицу Якоби системы функций f1 , f 2 ,..., f n
F (x
(k )
(k )
(k )
относительно переменных
(k )
(k )
x1 , x2 ,..., xn , т.е.
f i
F ( x ) W ( x)
, (i, j 1,2,.., n).
x j

9.

F ( x ) W ( x ) x 0.
f i
Если det W ( x ) det
0, то
x j
(k )
Тогда
x
(k )
1
(k )
(k )
W ( x ) F ( x ).
(k )
(k )
Следовательно, метод Ньютона для решения
исходной системы состоит в построении
итерационной последовательности:
x
( k 1)
x
(k )
1
W ( x ) F ( x ), k=0,1,2,
(k )
(k )
Если поправки достаточно малы, счет закончен

10.

Пример. Найти методом Ньютона решение
системы уравнений
f1 ( x , y, z) x y z 1,
2
2
2
f3 ( x , y, z) 3x 4 y z ,
2
2
f 2 ( x , y, z) 2 x y 4 z ,
2
2
исходя из начального приближения
x0 y0 z0 0,5.

11.

Полагая
x
(0)
0 .5
0.5 ,
0 .5
f1 ( x, y, z )
f 2 ( x, y , z )
f ( x) f 3 ( x, y, z ) .
2
2
2
x
y
z
1
имеем
2
2
f ( x) 2 x y 4 z .
3x 2 4 y z 2

12.

Подставляя данные, получаем
0.25
(0)
f ( x ) 1.25 . Составим матрицу Якоби:
1.00
1
2 x 2 y 2 z
1 1
0
W ( x ) 4 x 2 y 4 , W ( x ) 2 1 4 ,
6 x 4 2 z
3 4 1

13.

При этом
1
1 1
0
W ( x ) 2 1 4 40.
3 4 1
Т.к. 0, то найдем обратную ей матрицу
15 5 5
1
1
0
W ( x ) 14 2 6
40
11 7 1

14.

3
8
7
20
11
40
1
8
3
.
20
1
40
1
8
1
20
7
40
Получим первое приближение:
x
(1)
x
( 0)
1
W ( x )F ( x )
( 0)
( 0)

15.

а
3
0 .5 8
7
0.5
20
0.5 11
40
1
8
1
20
7
40
1
8 0.25 0.875
3
. 1.25 0.500 .
20
1 1.00 0.375
40
Аналогично находим дальнейшие приближения
( 3)
В результате получим ( x )
x 0.7852, y 0.4966, z 0.3699.

16.

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

17.

Пусть задана система
f ( x , y ) 0,
g ( x , y ) 0.
Образуем новую функцию
( x , y ) f ( x , y ) g ( x , y ) .
2
2
Т.к. эта функция не отрицательна, то всегда
найдется точка ( x , y ) такая, что
( x , y ) ( x , y ) 0, ( x, y) R2 .

18.

z
z ( x, y )
y
( x , y )
( xk , yk )
grad ( xk , yk )
x
( xk 1 , yk 1 )

19.

Т.е., если удается получить точку
( x , y ),
минимизирующую функцию ( x, y ), и если
при этом окажется, что
min ( x, y ) ( x , y ) 0, то точка ( x , y )
( x , y ) R2
истинное решение системы, т.к.
( x , y ) 0
f ( x , y ) 0,
g ( x , y ) 0.

20.

Последовательность точек ( xk , yk )
(
x
,
y
) минимума
приближений к точке
функции ( x, y ) получают по формуле
xk 1 xk
pk
k ,
yk 1 yk
qk
где k 0,1,..., ( pk , qk ) вектор, определяющий
направление минимизации, а k скалярная
величина, характеризующая величину шага
минимизации.

21.

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

22.

Направление наибольшего возрастания
функции в данной точке показывает её
градиент в этой точке. Поэтому
x ( xk , yk )
pk
( xk , yk ) ( x , y )
y
k
k
q
k
антиградиент функции
( x, y ).

23.

Тогда суть градиентного метода
xk 1 xk
x ( xk , yk )
.
k
(
x
,
y
)
y k k
yk 1 yk
Достоинство градиентного метода решения
нелинейных систем – глобальная сходимость.
Главный недостаток – медленная сходимость.

24.

Пример. Найти максимум функции
f x1 x2 ( x1 3) ( x2 4)
2
2
Методом скорейшего спуска при ограничениях:
x1 x2 20,
x1 0, x2 0.
Функция f является выпуклой, поэтому
её локальный максимум совпадает с глобальным. Оптимум достигается внутри области
решений системы ограничений. Градиент
f ( x2 2x1 6), ( x1 2x2 8).

25.

Пусть исходная точка x0 (2,1). Подставляя
координаты x0 в выражение градиента,
получим f 0 (3,8). Используя формулу
x1 x0 a f ,
получим
x1 (2,1) a(3,8) (2 3a), (1 8a).
f1 (3 2a), (8 13a).
Используя скалярное произведение векторов
f ( xk 1 ) f ( xk ) 0,

26.

найдём
a.
f 0 f1 (3,8)((3 2a), (8 13a))
3(3 2a) 8(8 13a) 73 98a 0.
Отсюда а=0,7449 – величина длины шага.
Тогда координаты следующей точки и
градиента:
x1 (2 3 0.7449), (1 8 0.7449) (4.25,7),
f1 (3 2 0.7449), (8 13 0.7449) (4.5, 1.75),

27.

Выполняя в цикле представленные расчёты,
процесс итерации заканчиваем при
достижении заданной точности отклонения
xk xk 1 .
В нашем примере итоги расчёта:
x6 (6.6566,7.3278), f ( x6 ) 24.333257

28.

Пример. Найти направление наискорейшего
возрастания функции
2
z x xy 5 в точке M 0 (1, 1) и
вычислить значение производной в этом
направлении.
Решение. Координаты градиента данной
функции: z / x 2 x y, z / y x.
Итак,
f ( x, y ) (2 x y, x). В точке M 0 (1, 1)
градиент имеет координаты f (1, 1) (1,1).

29.

По координатам градиента видно, что
искомое направление дифференцирования
0
45
с осью Ох
составляет угол
Значение производной в этом направлении
( z / ) max f (1, 1)
1 1 2.
2
2