Похожие презентации:
Методы решения систем нелинейных уравнений
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.
38
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.
zz ( 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