- •ЧИСЛЕННЫЕ МЕТОДЫ ОПТИМИЗАЦИИ
- •Метод Левенберга—Марквардта
- •Метод Левенберга—Марквардта
- •Обращение матриц
- •Формула Шермана-Моррисона-Вудбери
- •Формула Шермана-Моррисона-Вудбери
- •Формула Шермана-Моррисона-Вудбери
- •Формула Шермана-Моррисона- Вудбери
- •Формула Шермана-Моррисона-Вудбери
- •Формула Шермана-Моррисона-Вудбери
- •Формула Шермана-Моррисона-Вудбери
- •Метод Левенберга—Марквардта
- •Примеры задач
- •Примеры задач
- •Примеры задач
- •Примеры задач
- •Примеры задач
- •Примеры задач
- •Литература
ЧИСЛЕННЫЕ МЕТОДЫ ОПТИМИЗАЦИИ
Оптимизация. Обращение матриц.
Константин Ловецкий Ноябрь 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 |