PDF / Лекции

(С) ИиКМ РХТУ сентябрь 2003г. Калинкин Владимир Николаевич

1

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

2x

− x 2

−1 = 0

введем обозначение

f 1(x1 , x2 ) = 2x1 − x22 −1

3x 21

− x2

− 2 = 0

f (x , x

) =3x2

− x

−2

1

2

2

1

2

1

2

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

f

(x

, x

,x

,....., x

n

) = 0

1

1

2

3

f2 (x1 , x2 ,x3

,....., xn ) = 0

→ →

→

или

f ( x) = 0 .

. . . . . . . . .

f

n

(x

, x

2

,x

3

,....., x

n

) = 0

1

→

Решением СНУ является такой вектор x* при подстановке которого в систему последняя

обращается в тождество.

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

→

→ →

Преобразуем Систему нелинейных уравнений к эквивалентному виду x

=ϕ( x) . Выберем

→(0)

некоторое начальное приближение x

, и последующие приближения найдем по

→

(1)

→ →(0)

→(2)

→ →(1)

→(3)

→ →(2)

формулам x

=ϕ( x ) , x

=ϕ

( x

) , x

=ϕ

( x ) , ……., а произвольное приближение

→(k +1)

→ →(k )

→(k )

→(k +1)

→(k )

запишем как: x

=ϕ( x ) . На каждой итерации вычисляем вектор ∆ x

= x

− x .

→(k )

|| ≤ ε

, где ε заданная

И проверяем условие окончания итерационного процесса || ∆ x

точность.

Решить приведенную выше систему. Преобразуем каждое уравнение.

→

2

x =ϕ

(x)

=

x2 +1

→0

0.5

1

1

3

. За начальное приближение примем x =

x

=ϕ

→

2x2

−1

0.5

2

2

(x) =

1

x

(1)

→(0)

(0.52

+1

0.625

→(0)

0.125

→(0)

1

=

ϕ

1

( x

)

=

2

=

;

∆ x

=

;

|| ∆ x

|| =1.7544

→(0)

−

x2

ϕ

( x

3

0.52

2

−1.25

-1.75

2

)

x

(2)

→(1)

(−1.252

+1

1.281

→(1)

0.656

→(1)

1

=

ϕ

1

( x

)

=

2

=

;

∆ x

=

;

|| ∆ x

|| = 0.7802

x

→(1)

2

0.422

2

0.625

−

2

−0.828

ϕ

( x

)

3

2

x

(3)

→(2)

(−0.8282

+1

0.843

→(2)

0 - 0.438

→(2)

1

=

ϕ

1

( x

)

=

2

=

;

∆ x

=

; || ∆ x

|| = 3.7784

x

→(2)

2

2.924

3.753

2

3

−

2

ϕ

( x

)

1.281

2

Итерационный процесс расходится.

Попробуем, по другому осуществить преобразование.

x =ϕ

→

=

x2 +2

(x)

1

1

3

→

x2 =ϕ

2 (x) = 2 x1 −1

→(k )

∂ x

(С) ИиКМ РХТУ сентябрь 2003г. Калинкин Владимир Николаевич

2

x1

(1)

→(0)

0.5 + 2

0.913

→(0)

0.413

→(0)

=

ϕ1

( x

(0)

)

=

3

∆ x

→

=

;

=

; || ∆ x || = 0.648

x2

0.000

−0.500

ϕ

( x

)

2 0.5 −

1

2

x

(2)

0.816

→(1)

||= 0.9138

x

(3)

0.985

||

→(2)

||= 0.202

1

=

;

|| ∆ x

1

=

;

∆ x

x2

0.909

x2

0.796

x

(4)

0.965

→(3)

||= 0.189

x

(5)

0.997

||

→(4)

||= 0.038

1

=

;

|| ∆ x

1

=

;

∆ x

x2

0.985

x2

0.965

Процесс сходится к решению.

Если не удаётся преобразовать исходную СНУ к итерационному виду, который будет сходится, то можно воспользоваться общим приемом.

→ → → = → → → → → = → →
f ( x)	= 0;	λ f ( x) = 0; x = x+ λ f ( x) . Итерационную формулу запишем
→(k +1)	→(k )	= → →(k )	=
x	= x	+ λ f ( x	) , где матрицу λ можно представить диагональной, а подбором

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

Метод Ньютона-Рафсона

			→(k )		→
Пусть известно некоторое приближение x				к решению x* тогда запишем исходную
→ →(k )	→(k )	→	→(k )	→	→(k )
систему в виде f ( x	+ ∆ x	) = 0 , где ∆ x		= x* − x . Разложим функцию в ряд Тейлора

и ограничимся линейными членами.

→ →(k ) →(k )		→ →(k )	→ →(k )	→(k )
			∂ f ( x )		→
f ( x	+ ∆ x ) =	f ( x ) +		∆ x	= 0 и

→→(k )

∂f ( x

→(k )

∂x

)	→(k )	→ →(k )
	∆ x	= − f ( x ) .

→(k )

Это система линейных уравнений относительно ∆ x . Обозначим матрицу частных производных, как матрицу

			→(k )	→(k )			→(k )
			∂f1 ( x )	∂f1 ( x )		.	∂f1 ( x		)
			∂x	∂x			∂x
								n
	→ →(k )		1		2
			→(k )	→(k )			→(k )
= (k )	= ∂ f ( x )		∂f2 ( x )	∂f 2 ( x )		.	∂f 2 ( x		)
Якоби[J (k ) ]= J		=
	→(k )		∂x1	∂x2			∂xn
	∂ x		.	.		.	.
			→(k )	→(k )			→(k )
			∂fn ( x )	∂f n ( x )		.	∂f n ( x		)
			∂x	∂x			∂x
					2			n
			1

	→(k )
Тогда ∆ x		= [J (k )
→(k +1)	→(k )	→(k )
x	= x	+ ∆ x

]−1	→ →(k )
	(− f ( x	)) , а новое приближение к решению СНУ будет иметь вид:
	→(k +1)	→(k )	+[J (k ) ]−1	→ →(k )
или x		= x		(− f ( x )) . Условие окончания

итерационного процесса является выполнения неравенства

→(k )	→(k )	→(k +1)	→(k )
∆ x	≤ ε, где ∆ x	= || x	− x || .

(С) ИиКМ РХТУ сентябрь 2003г. Калинкин Владимир Николаевич

3

→0

=

0.5

2

− 2 x

Решить приведенный выше пример. x

0.5 и

[J ]= 6 x

−1

2

1

x1

(1)

x1

(0)

2

− 2

x20

−1

→(0)

0.5

2

−1

−1

−0.25

−

f1

( x

)

=

x

=

x

6

x0

−1

→

(0)

=

0.5

−

3

−1.75

−1

2

2

1

f

2

( x

)

0.5

−1

1

−0.25

2

→(0)

=

1.5

→(0)

−

=

∆ x

;

|| ∆ x || = 3.132

0.5

−3

2

−1.75

3.25

2.75

x

(2)

1.323

→(1)

||=1.53

x

(3)

1.070

→(2)

||= 0.684

1

=

;

|| ∆ x

1

=

;

|| ∆ x

x2

1.878

x2

1.243

x

(4)

1.007

→(3)

||= 0.223

x

(5)

1.000

→(4)

||= 0.029

1

=

;

|| ∆ x

1

=

;

|| ∆ x

x2

1.029

x2

1.001

(С) ИиКМ РХТУ сентябрь 2003г. Калинкин Владимир Николаевич

1

Методы одномерной оптимизации.

Дана некоторая функция f(x) от одной переменной x, надо определить такое значение x*, при котором функция f(x) принимает экстремальное значение. Под ним обычно понимают минимальное или максимальное значения. В общем случае функция может иметь одну или несколько экстремальных течек. Нахождение этих точек с заданной точностью можно разбить на два этапа. Сначала экстремальные точки отделяют, т.е. определяются отрезки, которые содержат по одной экстремальной точке, а затем уточняют до требуемой точности ε. Отделение можно осуществить, как графически, так и табулированием. Все методы уточнения точек экстремумов будем рассматривать относительно уточнения минимума на заданном отрезке.

Метод деления на три равных отрезка.

1.Дан отрезок [a;b] на котором определена функция f(x) и точность ε. Надо уточнить точку минимума с заданной точностью. Введём новое обозначение точек x1=a и x4=b. И вычислим Z=1/3.

2.Делим отрезок на три равные части и определяем точку x2=x1+Z(x4-x1) и точку x3=x4-Z(x4-x1). Вычисляем значения функции в этих точках F2=f(x2) F3=f(x3).

3.Определяем новый отрезок, содержащий точку экстремума, сравнив значения функций F2 и F3. Если F2 < F3, то границы нового отрезка определим как x1=x1, а x4=x3, иначе x1=x2, а x4=x4.

4.Проверяем условие окончания итерационного процесса | x4-x1 | ≤ 2ε. Если оно выполняется, то

определим решение, как x=(x4-x1)/2 и значение функции в этой точке f(x). Иначе перейдем на пункт 2.

начало

a, b, ε || f(x).

x1 := a; x4:=b: Z=1/3

x2:=x1+Z(x4-x1); x3:=x4-Z(x4-x1) F2:=f(x2); F3:=f(x3)

F2<F3

x1:=x2						x4=x3

|x4-x1|≤2ε

x:=(x1+x4)/2

x, f(x)

конец

Введем понятие эффективности, как отношение доли сокращения отрезка к количеству вычисления функции на одной итерации тогда Q=0,33/2≈0,17

(С) ИиКМ РХТУ сентябрь 2003г. Калинкин Владимир Николаевич	2
Попробуем увеличить долю сокращения отрезка

Метод деления отрезка пополам.

1.Дан отрезок [a;b] на котором определена функция f(x) и точность ε. Надо уточнить точку минимума с заданной точностью. Введём новое обозначение точек x1=a и x4=b.

2.Делим отрезок пополам и определяем точку середины x2=(x4+x1)/2 и точку x3, отстоящую на незначительное расстояние от середины x3=x2+(x4-x1)/100. Вычисляем значения функции в этих точках

F2=f(x2) F3=f(x3).

3.Определяем новый отрезок, содержащий точку экстремума, сравнив значения функций F2 и F3. Если F2 < F3, то границы нового отрезка определим как x1=x1, а x4=x3, иначе x1=x2, а x4=x4.

4.Проверяем условие окончания итерационного процесса | x4-x1 | ≤ 2ε. Если оно выполняется, то

определим решение, как x=(x4-x1)/2 и значение функции в этой точке f(x). Иначе перейдем на пункт 2.

начало

a, b, ε || f(x).

x1 := a; x4:=b

x2:=(x1+x4)/2; x3:=x2+(x4-x1)/100 F2:=f(x2); F3:=f(x3)

F2<F3

x1:=x2						x4=x3

|x4-x1|≤2ε

x:=(x1+x4)/2

x, f(x)

конец

Эффективность метода Q≈0,5/2=0,25

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

D		L	D
x1	x2	x3	x4
d		d

x1

x2 l x3

x4

(С) ИиКМ РХТУ сентябрь 2003г. Калинкин Владимир Николаевич

3

D d

D

(L − 2D)

2

2

=

; d = L

− 2D; l = L

− D;

=

; DL − D

= L

− 2DL

L

l

L

(L − D)

2

D

D 2

D

делим на L

−

−1 +

2

= 0

L

L

L

Заменяем Z =

D

Z 2 −3Z +1 = 0

L

Решая получим Z =

(3 −

5) ≈ 0.3819

2

Метод золотого сечения.

1. Дан отрезок [a;b] на котором определена функция f(x) и точность ε. Надо уточнить точку минимума с заданной точностью. Вычислим Z = (3 −2 5) и введём новое обозначение точек x1=a и x4=b

2.Делим отрезок на три части и определяем точку x2=x1+Z(x4-x1) и точку x3=x4-Z(x4-x1). Вычисляем значения функции в этих точках F2=f(x2) F3=f(x3).

3.Определяем новый отрезок, содержащий точку экстремума, сравнив значения функций F2 и F3. Если F2 < F3, то пункт 4 иначе пункт 5

4.границы нового отрезка определим как x1=x1, x4=x3, а x3=x2, F3=F2, x2=x1+Z(x4-x1) и F2=f(x2) пункт 6

5.границы нового отрезка определим как x1=x2, x4=x4, а x2=x3, F2=F3, x3=x4-Z(x4-x1) и F3=f(x3) пункт 6

6.Проверяем условие окончания итерационного процесса | x4-x1 | ≤ 2ε. Если оно выполняется, то

определим решение, как x=(x4-x1)/2 и значение функции в этой точке f(x). Иначе перейдем на пункт 3.

	начало
	a, b, ε ||			f(x).
	x1 := a; x4:=b:			Z =	3 − 5
					2

x2:=x1+Z(x4-x1); x3:=x4-Z(x4-x1) F2:=f(x2); F3:=f(x3)

F2<F3

x1:=x2						x4=x3

|x4-x1|≤2ε

x:=(x1+x4)/2

x, f(x)

конец

Эффективность метода Q=0,38/1≈0,38

(С) ИиКМ РХТУ сентябрь 2003г. Калинкин Владимир Николаевич		1
Методы многомерной оптимизации.
Дана некоторая функция многих переменных f(x1,x2,x3,…..,xn) или		→
		f ( x) надо найти такое
→	→
значение x * , при котором функция	f (x* ) принимает экстремальное значение (минимальное или

→→

*x

максимальное). Некоторая функция f ( x) в точке		имеет минимум, если в любой сколь угодно
	→	→	→
малой окрестности точки x * выполняется условие		f ( x) > f (x* ) и максимум, если выполняется
→	→
условие f ( x) < f (x* ) .

→

Процесс поиска экстремального значения иногда называют оптимизацией. Функцию f ( x)

→

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

→

1) вид функции f ( x) ;

2) границы поиска по каждой переменной [a1;b1], [a2;b2],…..,[an;bn] либо, вместо границ,

				(0)
			x1
может быть задана начальная точка поиска экстремума x		(0)	x2(0)			;
			=
			.....
				(0)
3)	точность поиска экстремума.		xn

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

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

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

f(x1,x2)

x1

x2

уровням.

→

Дана целевая функция f ( x) = x12 + x22 , которая графически

представляет собой поверхность параболоида вращения.

Проведем сечения поверхности равно отстоящими плоскостями, которые параллельны плоскости изменения переменных x1 и x2.

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

Рассечем заданную поверхность функции тремя плоскостями по

y = x2		+ x2	=1	y	2	= x2	+ x2	= 2	y	3	= x2	+ x2	= 3
1	1	2				1	2				1	2

Тогда линии уровня будут подставлять окружности с соответствующими радиусами

R1=√1=1

R2=√2=1.4

R3=√3=1.73

(С) ИиКМ РХТУ сентябрь 2003г. Калинкин Владимир Николаевич

2

x2

x1

Все методы многомерной оптимизации делятся на два класса:

1)Градиентные

2)Безградиентные

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

1

0

0

→

0

→

1

→

0

оси. e

1 =

e

2 =

……….. e n =

.

.

.

0

0

1

→

→

∂f

→

∂f

→

∂f

→

grad ( f ( x)) =

e1 +

e 2

+......... +

e n

∂x

∂x

∂x

2

n

1

∂f

→

→

∂f

1

∂f

0

∂x1

Для случая функции двух переменных grad ( f ( x)) =

=

+

∂x1

∂x2

0

1

∂f

∂x2

Основные свойства градиента:

1)Норма градиента определяет скорость изменения функции в направление градиента.

2)Градиент всегда направлен в сторону наиболее быстрого возрастания функции, т.е. в этом направлении норма вектора градиента максимальна.

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

дана функция

→

+ x2

→

=

1

f ( x) = x2

. Вычислить вектор градиент в точке x

1

2

2

∂f

2x

2

→

→

∂x

grad ( f ( x)) =

=

1

=

1

∂f

2x2

4

∂x2

Градиентный метод.

→

1.Дана функция n переменных f ( x) . Также заданы точность ε, величина параметра

→(0)

шага h и точка начального приближения x расположенная в области поиска экстремума.

(С) ИиКМ РХТУ сентябрь 2003г. Калинкин Владимир Николаевич

3

2.За текущее значение вектора приближения принимаем начальное приближение

→

→(0)

→

x

= x

и вычисляем значение функции в этой точке FX= f ( x)

∂f

∂x

1

→

∂f

∂f

3.

Вычисляем вектор градиента G =

=

∂x2

единичный вектор градиента

→

∂ x

...

∂f

∂x

n

→

→1

G

V =

→

|| G ||

4.

→

→

→

Делаем шаг в направление антиградиента z

= x

− h V и вычисляем значение

→→

функции в точке z FZ= f ( z)

5.	Проверяем условие FZ < FX. Если условие выполняется, то за текущее приближение
→	→	→
принимаем		= z , FX=FZ и переходим на пункт 3.
6.		→
	Иначе, проверяем условие окончания h < ε, если оно выполняется, то выводим x и

FX.

7.Если не выполняется, то уменьшаем параметр шага h=h/3 и переходим на пункт 3.

начало

→(0)

, h, ε

||

→

x

f ( x)

→

→(0)

→

x

= x ; FX= f ( x)

→

∂f

→

1

→

G =

;

V =

G

→

→

∂ x

|| G ||

→

=

→

→

→

z

x

− h V ; FZ+ f ( z)

FZ<FX

| h | ≤ ε

→

, FX

x

h:=h/3

конец

(С) ИиКМ РХТУ сентябрь 2003г. Калинкин Владимир Николаевич

1

Симплексный метод

Симплексом в n-мерном пространстве называется выпуклый многоугольник с n+1 вершиной. n=2 треугольник

n=3

тетраэдр

Алгоритм метода (n=2)

→

1.

→

задаем функцию f( x ) , начальное приближение

x0 , точность eps и длину грани h

2.

→ →

→ →

h

→ →

0

вычисляем координаты вершин симплекса x1

= x0

x2 = x0 −

x3 = x0 +

0

h

→

→

→

3.

вычисляем значения функции в вершинах F1 = f (x1 )

F 2 = f (x2 )

F3 = f (x3 )

F худ

и

→

4.

определяем худшую вершину

x худ

5.

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

худшей вершины и проходящей через середину противоположной грани.

→

→

→

→

→

→

→

→

→

xср = 0.5 * (xост1 + xост2 )

V = xср − x худ

xотр = x худ + 2 V , вычисляем значение функции в

→

отраженной вершине F отр = f (xотр )

6. Сравниваем значения функции F отр ≤ F худ если да, то за новый симплекс принимаем

→

→ худ

симплекс с вершиной xотр вместо x и повторяем с пункта 3

7. Иначе проверяем условие окончания h<eps если условие не выполняется, то за

→

x0 принимаем лучшую вершину последнего симплекса, уменьшаем длину грани h=h/3 и повторяем с пункта 2.

8. Условие окончания выполняется. Выводим координаты и значение функции лучшей вершины.

пример:										2.5
			2	+3*x2	2	+x1*x2	,	→0
f(x1,x2)=15-4*x1-13*x2+x1								h=1, eps=0.2, x	=
										0
№	x1	x2	f(x1,x2)			h		точки симплекса и примечания
1	2.5	0.0	11.25			1		симплекс т.1,2,3		т.1	худшая отражаем
2	1.5	0.0	11.25
3	2.5	1.0	3.75
4	1.5	1.0	2.75					удачно симплекс 2,3,4				т.2 худшая отражаем
5	2.5	2.0	2.25					удачно симплекс 3,4,5				т.3 худшая отражаем
6	1.5	2.0	0.25					удачно симплекс 4,5,6				т.4 худшая отражаем
7	2.5	3	6.75					неудачно 1>0.4 h=h/3 = 0.33
1	1.5	2.0	0.25			0.33		симплекс т.1,2,3,		т.3 худшая отражаем
2	1.17	2.0	0.0289
3	1.5	2.33	0.742
4	1.17	1.67	0.299					удачно симплекс 1,2,4 т. 4 худшая
1	1.17	2.0	0.0289			0.11		симплекс т.1,2,3		т. 3 худшая отражаем
2	1.06	2.0	0.0036
3	1.17	2.11	0.0839
4	1.17	1.67	0.2995					неудача 0.11<0.2		ответ		т. 2