Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
численные методы оптимизации / Численные методы оптимизации_11.pptx
Скачиваний:
63
Добавлен:
15.04.2015
Размер:
863.98 Кб
Скачать

ЧИСЛЕННЫЕ МЕТОДЫ ОПТИМИЗАЦИИ

Оптимизация. Обращение матриц.

Константин Ловецкий Ноябрь 2011

Кафедра систем телекоммуникаций

1

Метод Левенберга—Марквардта

Алгоритм Левенберга—Марквардта (Levenberg- Marquardt Algorithm, LMA) является наиболее распространенным алгоритмом оптимизации. Он превосходит по производительности метод наискорейшего спуска и другие методы сопряженных

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

градиентного метода и метода Гаусса-Ньютона,

однако впоследствии выяснилось, что данный алгоритм можно также рассматривать как метод доверительных интервалов.

7/1/19

2

Метод Левенберга—Марквардта

Таким образом, алгоритм Левенберга представляется в виде последовательности действий:

• 1. Вычислить параметр на очередной итерации по правилу xi 1 xi (H I ) 1 f (xi )

2. Оценить невязку в новом векторе параметров.

3. Если в результате вычисления параметра невязка

увеличилась, вернуться на шаг назад (т.е. восстановить прежние значения весов) и увеличить в 10 раз. Затем повторить выполнение, начиная с шага 1.

4. Если в результате вычисления параметра невязка

уменьшилась, принять текущий шаг (т.е. оставить новые значения весов) и уменьшить в 10 раз.

7/1/19

3

Обращение матриц

Формула Шермана-Моррисона-Вудбери.

Пусть A – невырожденная nxn матрица и пусть U и V – mxn матрицы, причем m≤n. Тогда

A UV T

обратима тогда и только тогда, когда обратима

In V T A 1U

и

A UV T 1 A 1 A 1U In V T A 1U 1 V T A 1.

 

Доказательство.

 

 

 

 

 

n

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

A UV

T

1

A

1

 

 

V

T

A

1

 

1

V

T

A

1

 

 

 

 

A

U I

 

 

U

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

AA 1 UV T A 1 U

In V T A 1U 1 V T A 1 UV T A 1U In V T A 1U 1 V T A 1

In UV T A 1 U In V T A 1U 1 In V T A 1U 1 V T A 1 In UV T A 1 UV T A 1

In U 1 V T A 1 In

7/1/19

4

Формула Шермана-Моррисона-Вудбери

Рассмотрим важный специальный случай, когда m=1; U и V являются в этом случае векторами - столбцами размерности n (u и v) и формула Шермана-Моррисона-Вудбери принимает вид

A uvT 1 A 1 A 1u 1 / (1 vT A 1u 1 vT A 1.

There are different versions. The first one goes directly back to Woodbury:

(1)

A UV T 1 A 1 A 1U In V T A 1U 1 V T A 1.

There is also a more general form, which can be expressed in two different ways.

The first one is easier to be understood, while the second one is more general.

(2)

A UDV T 1 A 1

A 1U D 1 V T A 1U 1 V T A 1.

The ladder results also in a special version, which I think is very nice.

(3)

A UDV

T

 

1

U A

1

1

V

T

A

1

1

D

1

.

 

 

 

U D

 

 

U

 

 

REFERENCES:

Golub, G. H. and Van Loan, C. F. Matrix Computations, 3rd ed. Baltimore, MD: Johns Hopkins, p. 50, 1996.

7/1/19

5

Формула Шермана-Моррисона-Вудбери

Обратим матрицу

 

A1

 

a11

a12

a13

L a1,n 1

a1n

 

 

A

 

a

a

a L a

a

 

 

 

2

 

21

22

23

2,n 1

2 n

A

 

 

 

 

L

L

L L

L

 

 

M

L

 

 

A

 

an1

an2

an3

L an,n 1

ann

 

 

n

 

 

 

 

 

 

 

используя формулу Шермана-Моррисона-Вудбери:

B I

, C B 1

I

, u e , vT A eT .

 

 

0

n

 

 

0 0

 

 

n

1

1

1

1

1

 

 

B B u v

T

, C C

 

 

 

T

C u )

 

T

C

.

 

0

1 / (1

v

C u v

1 0

1 1

1

 

 

1

0 1

 

0 1 1 0

 

7/1/19

6

Формула Шермана-Моррисона-Вудбери

Далее используем A2

и второй столбец

A

для

определения B2 B1 u2v2T , где u2 e2 , vT A

eT

 

2

2

2

Продолжая, получим

Bn A и обратную матрицу Cn

Важно отметить, что не возникает необходимости хранить матрицы Bk . Кроме того, для сокращения числа операций при вычисленииCk , определим

w C u

z

k

vT C

k 1

,

k k 1 k

 

k

 

тогда Ck Ck 1 1/ (1 zkuk ) wk zk

 

 

 

 

 

7/1/19

7

Формула Шермана-Моррисона- Вудбери

Пример. Найдем обратную к матрице

 

 

 

 

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

A 1

 

 

 

 

1

 

 

 

 

 

Пусть B0 I4 , C0

I4 ,

 

1

тогда

2

0

1

6

 

 

 

 

 

 

 

 

 

 

B 0

1

0

0

 

0

0

1

0

 

 

0

0

1

 

0

 

0

1

6

 

3

1

4

 

3

1

1

 

 

2

3

0

 

 

 

0.5

0

0.5

3

 

 

 

 

 

 

 

 

 

0

1

0

0

 

C1

 

 

 

0

0

1

0

 

 

 

0

0

0

1

 

 

 

 

7/1/19

8

Формула Шермана-Моррисона-Вудбери

21 B2 00

21 B3 10

21 B4 11

0

1

6

 

 

 

0.5

0

0.5

3

 

3

1

4

 

 

 

 

0.333

0.5

0.333

 

,

C2

0.1666

 

0

1

0

 

0

0

1

0

 

 

 

 

0

0

1

 

 

 

0

0

0

1

 

 

 

 

 

0

3

3

0

0

3

3

2

16

1 ,

110 41

1 61 4 1 1

30

,

 

 

0.5

 

 

0

 

 

 

 

0.333

C3

0.1666

 

0

 

0.5

 

 

 

 

 

0

 

 

0

 

 

37

 

 

 

64

 

 

 

 

 

 

C4 A 1

 

4

7

 

 

26

 

 

 

15

 

 

 

 

 

17

 

 

 

10

0.5 3

0.50.333

0.51.5

01

34 45

45

14 18

912

7/1/19

9

Формула Шермана-Моррисона-Вудбери

7/1/19

10