Псевдопроекционные алгоритмы оценивания, основанные на аппроксимации операции ортогонального проецирования
Одним з найбільш ефективних і найбільш простих в обчислювальному відношенні однокрокових алгоритмів оцінювання є алгоритм Качмажа, запропонований в [1]. У багатьох подальших роботах було розглянуто можливість прискорення алгоритму Качмажа шляхом використання не одного, а ряду вимірювань. Роботи [8,...
Gespeichert in:
| Veröffentlicht in: | Проблемы управления и информатики |
|---|---|
| Datum: | 2020 |
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2020
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/208708 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Псевдопроекционные алгоритмы оценивания, основанные на аппроксимации операции ортогонального проецирования / Б.Д. Либероль, О.Г. Руденко, А.А. Бессонов // Проблемы управления и информатики. — 2020. — № 2. — С. 16-33. — Бібліогр.: 17 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860238368901693440 |
|---|---|
| author | Либероль, Б.Д. Руденко, О.Г. Бессонов, А.А. |
| author_facet | Либероль, Б.Д. Руденко, О.Г. Бессонов, А.А. |
| citation_txt | Псевдопроекционные алгоритмы оценивания, основанные на аппроксимации операции ортогонального проецирования / Б.Д. Либероль, О.Г. Руденко, А.А. Бессонов // Проблемы управления и информатики. — 2020. — № 2. — С. 16-33. — Бібліогр.: 17 назв. — рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Одним з найбільш ефективних і найбільш простих в обчислювальному відношенні однокрокових алгоритмів оцінювання є алгоритм Качмажа, запропонований в [1]. У багатьох подальших роботах було розглянуто можливість прискорення алгоритму Качмажа шляхом використання не одного, а ряду вимірювань. Роботи [8, 9] послужили поштовхом до розробки нового класу багатокрокових проекційних алгоритмів [10–14], в яких при побудові оцінки на n-му кроці використовується не тільки нова інформація, як це відбувається в алгоритмі Качмажа, а й інформація про ряд попередніх кроків n – 1, n – 2 .... . Кількість таких кроків визначає пам’ять алгоритму. При цьому завдяки кращій екстраполяції і фільтрації у ряді випадків вдається домогтися істотного скорочення часу ідентифікації. Реалізація багатокрокового (S-крокового) проекційного алгоритму вимагає обчислення зворотної матриці спостережень розмірності S S. В [11–14] встановлено властивості випадкових псевдообернених матриць і матриць проеційованих, які дозволили визначити швидкість збіжності даних алгоритмів і зробити висновок про те, що урахування в даних алгоритмах інформації про S попередніх кроків рівносильне в сенсі швидкості збіжності зменшенню розмірності вихідного простору N на S. У даній роботі пропонуються і досліджуються псевдопроекційні алгоритми, що володіють близькими до багатокрокових проекційних алгоритмів властивостями, але більш прості в реалізації. Дані алгоритми використовують апроксимацію операції точного проеціювання і будуються на основі однокрокового адаптивного алгоритму Качмажа. Отримано оцінки швидкості збіжності запропонованих процедур і показано, що використання такої апроксимації дозволяє при незначному зниженні швидкості збіжності алгоритмів істотно спростити їх реалізацію та підвищити обчислювальну стійкість внаслідок усунення операції обертання матриці спостережень.
Kaczmarz algorithm proposed in [1] is one of the most effective and most computationally simple one-step estimation algorithms. In a number of subsequent studies the possibility of acceleration algorithm Kaczmarz by the use of not one but a series of measurements was examined. Research made in [8, 9] was a push for the development of a new class of algorithms — multistage projection algorithms [10–14], in which during the construction of estimates on the n-th step not only new information is used, as it comes in Kaczmarz algorithm, but also information about number of previous steps n–1, n–2 .... . The number of these steps determines the algorithm’s memory. In this case, thanks to a better extrapolation and filtering, in some cases it is possible to reduce significantly the time of identification. The implementation of multi-step ( S -step) projection algorithm requires the computation of the inverse matrix of observations with S S dimension. In [11–14] properties of random pseudoinverse matrix and the projection matrix are set. It helped to determine the rate of convergence of these algorithms and conclude that taking into account information about previous S steps is equivalent in terms of convergence speed to reduction of dimension N in the original space to S. In this paper we propose and investigate pseudoprojective algorithms that have close to the multi-stage projection algorithm properties, but are simpler to implement. These algorithms use an approximation of the exact projection operation and are based on one-step Kaczmarz adaptive algorithm. Estimates of the convergence rate of the proposed procedures are obtained. It is shown that the use of such approximation allows, with a slight decrease in the convergence rate of the algorithms, to simplify significantly their implementation and increase computational stability due to eliminating the rotation operation of the observation matrix.
|
| first_indexed | 2025-12-07T18:26:58Z |
| format | Article |
| fulltext |
© Б.Д. ЛИБЕРОЛЬ, О.Г. РУДЕНКО, А.А. БЕССОНОВ, 2020
16 ISSN 0572-2691
УДК 004.852
Б.Д. Либероль, О.Г. Руденко, А.А. Бессонов
ПСЕВДОПРОЕКЦИОННЫЕ АЛГОРИТМЫ
ОЦЕНИВАНИЯ, ОСНОВАННЫЕ
НА АППРОКСИМАЦИИ ОПЕРАЦИИ
ОРТОГОНАЛЬНОГО ПРОЕЦИРОВАНИЯ
Ключевые слова: алгоритм Качмажа, проекционный алгоритм, рекуррентная
процедура, асимптотическая оценка, точность идентификации.
Введение
Многие задачи управления, прогнозирования, распознавания образов и т.д.
связаны с построением модели вида
,T
nnny +=
xc (1)
где ny — наблюдаемый выходной сигнал;
T
21 )...,,,( Nnnnn xxx=x — вектор
входных сигналов 1N ;
T
21 )...,,,(
= Ncccc — вектор искомых (оцениваемых)
параметров 1N ; n — помеха; T — символ транспонирования; n — дискретное
время, сводится к минимизации некоторого наперед выбранного функционала
качества (критерия идентификации) от ошибки оценивания. Использование квад-
ратичного функционала приводит к различным алгоритмам идентификации,
позволяющим получить оценки c искомого вектора
c при нормальных распре-
делениях помехи n .
Одним из наиболее эффективных и наиболее простых в вычислительном от-
ношении одношаговых алгоритмов оценивания является алгоритм Качмажа,
предложенный в работе [1] и имеющий вид
,
2
T
1
1 n
n
nnn
nn
y
x
x
xc
cc −
−
−
+= (2)
где • — евклидова норма.
Оценки скорости сходимости данного алгоритма при идентификации стацио-
нарных объектов впервые получены в [2–6]. Если в [2–4] рассматривался регу-
лярный случай, то в [5, 6] были получены оценки, учитывающие статистические
свойства сигналов и помех.
Для повышения вычислительной устойчивости алгоритма (2) В.М. Чадеев [2, 3]
предложил его модификацию — регуляризованный алгоритм, использующий в
знаменателе помимо
2
nx некоторое положительное число, параметр регуляриза-
ции. В работах [5, 6] получены неасимптотические и асимптотические оценки
скорости сходимости регуляризованного алгоритма Качмажа, которые показали,
что введение регуляризующей добавки, улучшая устойчивость алгоритма, приво-
дит к замедлению скорости его сходимости.
Возможность ускорения алгоритма Качмажа путем использования не одного,
а ряда измерений рассмотрена в [7]. В настоящей публикации исследовалась
модификация алгоритма Качмажа, достаточно эффективна при оценивании не-
стационарных параметров.
Международный научно-технический журнал
«Проблемы управления и информатики», 2020, № 2 17
Публикации Ш.Г. Лелашвили [8, 9] послужили толчком к разработке нового
класса алгоритмов — многошаговых проекционных алгоритмов [10–14], в кото-
рых при построении оценки на n-м шаге используется не только вновь поступаю-
щая информация, как это происходит в алгоритме Качмажа, но и информация о
ряде предыдущих шагов n – 1, n – 2… Количество таких шагов определяет память
алгоритма. При этом благодаря лучшей экстраполяции и фильтрации в ряде слу-
чаев удается добиться существенного сокращения времени идентификации. Пре-
имущества такого подхода отмечались в [15], а в [16] проведен сравнительный
анализ одно- и двухшаговых алгоритмов. Общая форма многошаговых алгорит-
мов изучалась в [8–14]. В этих работах рассматривался проекционный алгоритм
вида
,)( TT S
n
s
n
s
n
s
nn YXXX -1
c = (3)
где T
11 )...,,,( +−−= snnn
S
n yyyY — вектор 1S ; T
11 )...,,,( +−−= Snnn
s
nX xxx —
матрица .NS
В [11–14] установлены свойства случайных псевдообратных матриц и матриц
проецирования, которые позволили определить скорость сходимости данных ал-
горитмов и сделать вывод, что учет в данных алгоритмах информации об S
предыдущих шагах равносилен в смысле скорости сходимости уменьшению раз-
мерности исходного пространства N на S. Таким образом, применение многоша-
говых проекционных алгоритмов позволяет существенно ускорить процесс
идентификации и является достаточно эффективным при оценивании нестаци-
онарных параметров [12, 14].
Как видно из (3), реализация алгоритма требует вычисления обратной матри-
цы наблюдений
-1)( Ts
n
s
n XX размерности .SS
Радикальным способом уменьшения требуемого объема памяти и упрощения
многошаговых алгоритмов является использование рекуррентных соотношений
для вычисления оценок (рекуррентная форма данных алгоритмов предложена в
[10]). Однако, как показывает практика, хотя рекуррентные алгоритмы устраняют
необходимость операции обращения матриц, что значительно упрощает вычисле-
ния и снижает чувствительность к ошибкам округления, для их реализации требу-
ется значительное количество арифметических операций. В связи с этим пред-
ставляет интерес разработка алгоритмов, обладающих близкими к проекционным
алгоритмам свойствами, но более простых в реализации. Так как наиболее про-
стым, но достаточно эффективным одношаговым проекционным алгоритмом яв-
ляется алгоритм Качмажа (2), целесообразно рассмотреть процедуры, использу-
ющие многократное применение этого алгоритма.
Рассматриваемые в данной статье методы осуществляют аппроксимацию опе-
рации ортогонального проецирования вектора ошибки 11 −
− −= nn cc на )(S
nL —
линейную оболочку S входных векторов 11 ...,,, +−− Snnn xxx .
Процедуры последовательного проецирования
При построении процедур оценивания используются известные свойства
матриц проецирования, сформулированные в леммах 1 и 2.
Лемма 1. Матрицы проецирования симметричны )( TPP = и идемпотентны
)( 2 PP = .
Лемма 2. Пусть P — оператор проецирования на линейное подпростран-
ство . Тогда, если подпространство , то
18 ISSN 0572-2691
,, ⊥ +== PPPPPP (4)
где ⊥ — ортогональное дополнение к в .
Доказательства лемм приводятся в [17].
Для удобства применения используемых свойств матриц, входящих в алго-
ритмы оценивания, будем сразу формулировать их для случая, когда эти матрицы
строятся по S последовательным векторам входного сигнала 11 ...,,, +−− Snnn xxx ,
хотя все формулы справедливы и в общем случае. Так, лемма 2 в применении к под-
пространствам snL= (линейная оболочка s векторов 11 ...,,, +−− Snnn xxx ) и
isinL −−= (линейная оболочка s–i векторов 11 ...,,, +−− Snnn xxx ) дает следую-
щее свойство операторов проецирования на вложенные линейные оболочки
snisin LL −− :
,
,
1
1
1
1 −
−⊥
−
−
−
−
−
−
−
−
+=
==
S
nn L
S
n
S
n
iS
in
S
n
iS
in
iS
in
S
n
PPP
PPPPP
x
(5)
где 1
1
−
−⊥ S
nn Lx — компонента вектора nx , ортогональная подпространству
1
1
−
−
S
nL ).
В этих методах проецирование 1−n на )(S
nL производится в несколько эта-
пов, шаг алгоритма разбивается на несколько подшагов. На n-й итерации после
поступления нового вектора nx производится первый подшаг по стандартному
алгоритму Качмажа (2), т.е. 1−n ортогонально проецируется на nx (полученную
проекцию обозначим n ):
.)( 1
)1(
−−= nnn PI (6)
Матрица проецирования на вектор nx имеет вид
.
2
T
)1(
n
nn
nP
x
xx
=
Обозначим )( )(
||1
S
nn L− ортогональную проекцию вектора 1−n на )(S
nL .
При точном проецировании — 0)( )(
|| = S
nn L , при псевдопроецировании —
.0)( )(
|| S
nn L
Задача построения метода состоит в поиске алгоритма, уменьшающего
величину проекции n на )(S
nL . В этом случае скорость сходимости алгоритма
будет приближаться к скорости сходимости алгоритма с точным проецирова-
нием. Как показано ниже, для получения скорости сходимости, близкой к ско-
рости сходимости алгоритма с точным проецированием, достаточно добиться
уменьшения )( )(
||
S
nn L в раз. Точному проецированию отвечает = , но
уже при 32 − для 1− SN достигается скорость сходимости, близкая к
алгоритму с точным проецированием. Для получения таких предлагаются
следующие процедуры.
Процедура 1. Осуществляется последовательное проецирование n на пред-
шествующие векторы: 11 , ,, +−− Snnn xxx .
Международный научно-технический журнал
«Проблемы управления и информатики», 2020, № 2 19
Процедура 2. Осуществляется проецирование n на некоторый вектор nz ,
направление которого коррелирует с направлением проекции n на )(S
nL . В каче-
стве такого вектора может быть взят, например, вектор вида
.
)1(
1
1
nin
S
i
n Pz = −
−
=
Процедура 3. При NS 5,0 производится повторное проецирование на век-
тор 1+−Snx .
Исследование вопросов сходимости процедур
Проведем сначала оценку скорости сходимости алгоритмов как функцию па-
раметра , характеризующего убывание проекции вектора n на )(S
nL . Для вы-
числения скорости сходимости рассмотрим
22
1,/ 1 nnxxn nn
M −= −−
. (7)
Утверждение 1. Для рассматриваемых псевдопроекционных процедур вели-
чина nnn −= −1 определяется соотношением
,
1
11
1
1
1
1
1
11
2
−−
−
−
+−
−
+−
= nn
N
S
sNsN
(8)
причем для процедуры 1 e , а для процедуры 2 2= .
Здесь };{
2
ii M = ii cc −=
— ошибка оценивания.
Доказательство. Учитывая подшаг nn → −1 по алгоритму Качмажа, запишем
.
2222
1
22
1 nnnnnn −+−=− −−
Известно, что [2, 3, 6]
.
1 2
1
22
1,/ 1 −− =−
− nnnxx
N
M
nn
(9)
Векторы n и n имеют разные проекции на )(S
nL , но их проекции на ⊥)(S
nL —
ортогональное дополнение к )(S
nL — одинаковы, так как проецирование на
направление, лежащее в )(S
nL , не может изменить величину проекции на ⊥)(S
nL .
Это утверждение справедливо и в случае, когда n получается из n проециро-
ванием на )1(
1
−
−
S
nL . Поэтому можем записать
.)()(
2
)1(
1||
2
)1(
1
22 −
−
−
− −=−
S
nn
S
nnnn LL
Введем параметр соотношением
( ) ( ) ,
1 2
)1(
1||
2
)1(
1||
=
−
−
−
−
S
nn
S
nn LMLM (10)
20 ISSN 0572-2691
отражающим тот факт, что рассматриваемые модифицированные алгоритмы
уменьшают проекцию вектора
'
n на )1(
1
−
−
S
nL в среднем в раз. Перепишем (9)
( ) .)
1
1(}{
1
}{
2
)1(
1||,/
2
1,/
22
1,/
11
1
−+=
=−=
−
−−
−
−−
−
S
nnxxnxx
nnxxn
LMMM
N
M
nnnn
nn
Для анализа сходимости процедур потребуются некоторые результаты, уста-
навливаемые следующей леммой.
Лемма 3. Пусть в пространстве NE будет ортонормированный базис
Neee ,,, 21 , первые 1−S векторов которого образуют линейное подпростран-
ство, натянутое на 1−S вектор 21 , ,, +−− Snnn xxx . Тогда при принятых пред-
положениях относительно статистических свойств сигналов имеет место формула
),(
)2(
2
)2(
1
}{
)1(
1
)1(
1
−
−
−
− −
+
+
+
−
=
S
ne
S
nee PI
NN
I
NN
S
PPPM (11)
где
.xxe};{}{
1
,x/x 1
−
=•=•
− nneMM
nn
Доказательство. Рассмотрим операторы проецирования на e и )1(
1
−
−
S
nL :
....,, T
11
T
11
)1(
1
T)1(
−−
−
− ++=== SS
S
nene eeeePeePPP
В базисе 121 ,,, − Seee оператор e
S
ne PPP
)1(
1
−
−
запишем следующим образом:
,)...( TT
11
T
11
T)1(
1 eeeeeeeePPP SSe
S
ne −−
−
− ++=
где ).1...,,0,0(,),0...,,1,0(),0...,,0,1( T
1
T
2
T
1 === −Seee
Учитывая, что
)()(TT , ii
ii eeeeee == — i-я компонента вектора ,e имеем
,)( 2)(TT i
ii eeeee =
.)...(
)...(
T2)1(2)2(2)1(
T2)1(2)2(2)1()1(
1
eeeee
eeeeePPP
S
S
e
S
ne
−
−−
−
+++=
=+++=
Выпишем компоненты этой матрицы в выбранном базисе
.
)......()...(
...
)......()...(
2)(2)1(2)1()1()(2)1(2)1(
)()1(2)1(2)1(2)1(2)1(2)1(
)1(
1
++++
++++
=
−−
−−
−
−
NSNS
NSS
e
S
ne
eeeeeee
eeeeeee
PPP
Вычислим математическое ожидание обеих частей данной матрицы, кото-
рое сводится к усреднению правой части по вектору e . Функция распределе-
ния этого случайного вектора обладает угловой симметрией вследствие того,
что компоненты nx имеют нулевое математическое ожидание и одинаковую
дисперсию. Поэтому недиагональные члены матрицы, имеющие вид
Международный научно-технический журнал
«Проблемы управления и информатики», 2020, № 2 21
,,)...( )()(2)1(2)1( jieeee jiS ++ −
при усреднении дают 0. При усреднении диаго-
нальных элементов встречаются выражения двух типов:
}{
2)(2)(
22
ji
e eeMM = и },{
4)(
4
i
e eMM =
причем при 1−= Sji присутствуют члены первого и второго вида, а при
1−= Sji — только первого.
Вычислим 22M . С учетом явного вида функции распределения вектора x ,
которая в силу независимости компонент — просто произведение N гауссовских
функций с одинаковыми параметрами, имеем
,)2(,)( 12|||| 2 −− =
= xexf x
для 22M получаем
....
||||
...
||||
}{ )()1(
4
2)(2)(
||||
4
2)(2)(2)(2)( 2 N
ji
N
ji
x
ji
e dxdx
xx
e
xx
MeeM
xx
x
−
−
−
=
=
Введем функцию от параметра
.
||||
)(
4
2)(2)(
|||| 2
x
x
x d
xx
eJ
ji
−
−=
Воспользовавшись известной формулой дифференцирования по параметру,
продифференцируем )(J дважды по :
....... )()1(2)(2)()...(
2
2 2)(2)1( Njixx dxdxxxe
J N
−
++−
−
=
N -мерный интеграл распадается на произведение N однократных интегралов.
Интегрирование по 2−N переменным (кроме i - и j -й) дает просто нормиро-
вочный множитель 1− . Интегрирование по i - и j -й переменным дает дис-
персию, умноженную на нормировочный множитель:
.
2
1)(2)(2)(
=
−
− ixx dxe
ii
С учетом этого получаем
.
4
1
22
2
N
J
=
Интегрируя это дифференциальное уравнение дважды по , с учетом оче-
видного граничного условия 0→J при →
.
)2(
1
)(
+
=
NN
J
N
Таким образом, для 22M имеем
.
)2(
1
|||| 4
2)(2)(
+
=
NN
xx
M
ji
e
x
22 ISSN 0572-2691
4M вычисляем аналогичным способом:
;
|||||||| 4
4)(
4
4)( 2
x
xx
x
x d
x
e
x
M
i
N
i
−
=
;
||||
)(
4
4)(2
x
x
x
d
x
eJ
i
−
=
.)(24)(
1
4)(
2
2 )(2
ixi
N
i dxexdxe
J i
−
−
−
==
x
x
Обозначая
,
2)(
0
==
− dxeJ
ix
получаем
.
4
3
;
4
3
22
0
2
5.0
22
0
2
24)( )(
N
xi JJ
dxex
i
=
=
= −−
Это отличается от полученного на предыдущей странице выражения для
2
2
J
только множителем 3. Окончательно выражение для 4M принимает вид
.
)2(
3
|||| 4
4)(
4
+
=
=
NN
x
MM
i
x
x
Для искомого математического ожидания оператора e
S
ne PPP
)1(
1
−
−
в выбранном
базисе имеем
=
−
− }{
)1(
1 e
S
nee PPPM
−
−
−
−
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
−
+
−
−
−
+
−
−
=
)2(
1
0
0
)2(
1
|
|
|
0
|
0
|
|
|
)2(
2
)2(
1
0
0
)2(
2
)2(
1
NN
S
NN
S
NNNN
S
NNNN
S
.
Учитывая вид матрицы )1(
1
−
−
S
nP в этом базисе, получаем окончательно выра-
жение (11). Так как по определению
,)()( 1
)1(
1
)1(
1|| −
−
−
−
− −= ne
S
n
S
nn PIPL
то имеем
1
)1(
1
)1(
11
2
)1(
1|| )()()( −
−
−
−
−−
−
− −−= ne
S
n
S
ne
T
n
S
nn PIPPPIL
Международный научно-технический журнал
«Проблемы управления и информатики», 2020, № 2 23
и с учетом (4),(5), т.е. того, что ,)(
)1(
1
2)1(
1
−
−
−
− =
S
n
S
n PP можем записать
.2)( 1
)1(
1
T
11
)1(
1
T
11
)1(
1
T
1
2
)1(
1|| −
−
−−−
−
−−−
−
−−
−
− +−= ne
S
nenn
S
nenn
S
nn
S
nn PPPPPPL (12)
Тогда выражение для ( )
−
−
2
)1(
1||
S
nn LM примет вид
( ) }.{
)2(
1
)2(
22
1}{
2
1
2
1
2
)1(
1|| −−
−
−
+
−
+
+
+−=
nn
S
nn M
NN
S
NNN
MLM (13)
Введение параметра соотношением
( ) }{
2
1
2
)1(
1|| −
−
− =
n
S
nn MLM (14)
позволяет записать формулу (13) в виде
.
)2(
1
)2(
22
1
2
1
2
|| −
+
−
−
+
+−=
nne M
NN
S
NNN
M
А для интересующей нас величины с точностью до )( 2−No получаем
}.{
122
1
1
1
1 2
122 −
−
+
+−
−+= nM
N
s
NNN
(15)
Для определения входящего в (15) параметра поступим следующим образом:
вычислим величину проекции
.)( )(
2
)1(
1|| n
S
n
T
n
S
nn PL =
−
−
Воспользуемся снова свойством оператора проецирования на вложенные
линейные оболочки, которыми в нашем случае будут )(S
nP и )(
1
S
nP −
:
.
)1(
1
)(
⊥
+=
−
− e
S
n
S
n PPP Здесь введено обозначение ⊥e для вектора ePI
S
n )(
)1(
1
−
−− .
Будем считать, что
).()( )(
||
)1(
1||
S
nn
S
nn LL
−
−
Это предположение оправдывается анализом последующих результатов и
выполняется с точностью до величин порядка ).( 1−So Тогда можно записать
( ) ( )
( )
+
=
=
−
=
⊥
−
−⊥
−
−
−
−
−
−
2
||
2
)1(
1||
22
)1(
1
2
)1(
1||
1
1
1
ne
S
nn
nPen
S
n
S
nn
PML
PMPMLM S
n
(16)
по определению параметра , введенного как показатель уменьшения квадрата
длины проекции вектора n на )1(
1
−
−
S
nL .
Учитывая, что
24 ISSN 0572-2691
,)( 1| −−= nen PI ,)(
)1(
1 ePIe
S
n
−
−⊥ −=
получаем
.)()( 11
2
)1(
1
)1(
1
−− −−= −
−⊥
−
−⊥
neLee
T
nnLe
PIPPIP S
n
S
n
Проведем усреднение по вектору e , выбирая базис, в котором, как и ранее,
оператор проецирования )1(
1
−
−
S
nP имеет канонический вид.
Для ⊥e в этом базисе имеем
).,,,,,(
1
NS
S
eeooe =
−
⊥
Поскольку оператор проецирования на вектор x есть
2T −
xxx , можем запи-
сать соотношение
.
)(
)( T
2
TT
T
⊥
⊥
⊥⊥ ===
⊥⊥
ee
e
eeee
PPPP eeee
Для усреднения произведений операторов проецирования, входящих в фор-
мулу (15), воспользуемся леммой 3. При этом
);(
)2(
2
)2(
1
}{
)1(
1
−
−−
+
+
+
−
=
⊥
S
neee PI
NN
I
NN
S
PPPM
);(
1
1
}{
)1(
1
−
−−
−
=
⊥
S
ne PI
S
PM
).(
1
}{}{
)1(
1
T −
−⊥ −==
⊥
S
nee PI
N
eeMPPM
Окончательно, с учетом того, что введение параметра позволяет записать
},{}{
2
11
)1(
1
T
1 −−
−
−− = nn
S
nn MPM
для интересующей нас величины }{
2
nee PM
⊥
получаем
.
122
1
1
)1(}{
2
2
12
2
N
S
NNS
PM nnee
−
+
+−
−
−= −⊥
Подставляя полученный результат в соотношение (15), выпишем уравнение
для , дающее вместе с (14) систему, при решении которого получаем оценку
скорости сходимости рассматриваемого алгоритма:
;
22
1
1
)1(
2
122
1
1
)1)(1(
22
+−
−
−+
−
−
+−
=+−
NNS
S
NN
}.{
)2(
22
1
1
1
1 2
1−
+
+−
−+= nM
NNNN
Решение этой системы с точностью до величин более высокого порядка ма-
лости дает для выражение
}.{
1
1
2
1
1
2
1
1
1 2
11
2
−−
−
−
−
−
−
= nM
S
SS
(17)
Международный научно-технический журнал
«Проблемы управления и информатики», 2020, № 2 25
Анализ этой формулы показывает, что уже при 2= и 1− SN скорость
сходимости упрощенного проекционного алгоритма близка к скорости сходимо-
сти алгоритма с точным проецированием, что подтверждается численным моде-
лированием. При → из (17) видно, что при 1− SN скорость сходимости,
вычисленная по рассмотренной методике, очень близка к скорости сходимости
S-шагового проекционного алгоритма [11, 13], что оправдывает предположе-
ния, поскольку → соответствует полному аннулированию проекции n на
)1(
1
−
−
S
nL , и мы приходим к алгоритму с точным проецированием.
Отметим, что хотя формально условие 1− SN не учитывалось, сделанные
в ходе вычислений предположения при 1~SN − будут несправедливыми, эффек-
тивное значение приближается к единице и формула (17) теряет смысл.
Отметим теперь, какие значения достигаются в предложенных вариантах
алгоритмов. Шаг процедуры 1 состоит из S подшагов: нулевого по алгоритму
Качмажа и последующих )1( −S -подшагов повторного проецирования на векторы
121 ,, , +−−− Snnn xxx . Можно показать, что при этом убывание
2
||n в )1( −S -
мерном подпространстве )1(
1
−
−
S
nL происходит быстрее, чем убывает величина
2
n в пространстве той же размерности за S шагов по алгоритму Качмажа, по-
тому что величина проекции
2
||n на текущий вектор nx оказывается в среднем
больше, чем на другие векторы, на которые последнее проецирование произво-
дилось позднее.
Таким образом, для процедуры 1 получаем оценку
e.~,
1
1
1
1
−
−
−S
S
В процедуре 2 после нулевого подшага по алгоритму Качмажа по nx осу-
ществляется подшаг в направлении вектора
ininnin
s
i
n cy −−−−
=
−= xxz )( T
1
1
в соответствии с
.
2
T
n
n
nn
nn z
z
z
−=
Оценим, как будет уменьшаться величина проекции n на )1(
1
−
−
S
nL , что и даст
нам оценку параметра , поскольку он определяется из (10) как степень этого
уменьшения. Вектор nz лежит в )1(
2
−
−
S
nL , его направление оказывается коррелиро-
ванным с направлением проекции 1−n на )1(
2
−
−
S
nL , обозначаемой ||1−n . По опре-
делению )1(
2
−
−
S
nP и ||1−n с учетом подшага по алгоритму Качмажа имеем
;1
)1(
1||1 −
−
−− = n
S
nn P ;||1
)1(
1|| −
−
− = n
S
nn P .)(
)1(
1|| n
S
nn n
PIP −=
−
− z
Поскольку )1(
1
−
−
S
nn Lz , по свойству проекционных операторов (4)
26 ISSN 0572-2691
;
)1(
1 nn
PPP
S
n zz =
−
− .|||||| nnn n
P −= z
Отсюда
||
T2
||
2
|| nnnn n
P −= z
с учетом явного вида оператора проецирования на вектор nz
.
)(
}{}{
2
2T
||2
||
2
−=
n
nn
nn MMM
z
z
Будем характеризовать уменьшение }{
2
||nM величиной
2
||
2
||}, { nnnnM −= . Оценим эту величину, считая, что ||n независимы
от 121 , , , +−−− Snnn xxx . Это соответствует тому, что проекции n на векторы
11 ,,, +−− Snnn xxx имеют в среднем одинаковую величину, потому что основ-
ной вклад в эти проекции дает подшаг nn → • по вектору nx , независимому
от векторов 121 , ,, +−−− Snnn xxx .
При вычислении }{M для упрощения записи примем обозначения
);(
)1(
1||
−
−=
S
nn L ;diin =−x .
)1(
1 d
S
n LL =
−
−
Введем в dL базис }{ ie так, чтобы 11 ,|| ee = . Размерность L обозна-
чим l . В данном случае 1−= Sl , но для общности вычисления проведем при
произвольном l .
Разложим n на составляющие ||n и ,
⊥
n .|| ⊥+= nnn
Имеем далее
,||n
T
nn
T
n = zz
поскольку ⊥n ортогонально )1(
1
−
−
S
nL , а значит, и всем векторам из )1(
1
−
−
S
nL . В
упрощенных обозначениях имеем
,)( T
1
1
ii
S
i
n dd=
−
=
z
2T
1
1
||
T )( i
S
i
nn d=
−
=
z
и в выбранном базисе ii dd 1
T = ( id1 — первая компонента id ).
Для получаем
.
)(
dd)(
}{
T
11
1
1,
2
11
2
11
}{
2
2
2
||
T
++
=
=
−
=
−
jiji
S
ji
s
d
n
nn
dddd
MMM
i
z
z
(18)
Для вычисления этой величины рассмотрим матрицу размерности
)1( − Sl , столбцами которой являются координаты векторов id , )1...,,1( −= Si
в выбранном базисе l -мерного пространства L . Элементы этой матрицы —
независимые гауссовы случайные величины с нулевым математическим ожида-
нием и одинаковой дисперсией, и )(M получается усреднением выражения в
(18) по )1( − Sl -мерному фазовому пространству, являющимся прямым произве-
дением )1( −S l - мерных пространств, отвечающих векторам id . Представим это
Международный научно-технический журнал
«Проблемы управления и информатики», 2020, № 2 27
пространство как прямое произведение l )1( −S -мерных пространств, отвечаю-
щих векторам )1,0(, −= SkDK , компонентами которых являются строки матри-
цы , т.е. KiiK dD = .
При введенных векторах KD величина }{M выражается следующим образом:
,
)(
}{
2T
11
4
1
}{
=
= m
l
m
D
DD
D
MM (19)
поскольку из определения KD следует
.)( 2T
1
1
11
,1,
1,,
11
,1,
1,,
k
l
k
jkikji
lksji
kji
kjkji
lksji
kji
DDdDDDdddd
i
=
=−=
=
=−=
=
==
Плотность распределения вероятности величин iD в )1( − Sl -мерном про-
странстве компонент набора }{ iD имеет вид
)}.(exp{
2
1
2
1
)1(
−
−
++−
s
Sl
DD
Воспользуемся формулой
.0,
1
de
0
=−
z
z
ztz
Подставив в нее знаменатель дроби для из (19)
.
2
2
1
1
1
2
1
+=
= D
DD
Dz m
Tl
m
Получим для }{M следующее выражение:
.exp
)}({}{
1
2
1
2
2
1
1
1
2
1
2
1
2
1
)1(
dtdDdDD
D
DD
Dt
DDexpM
l
m
Tl
m
s
l
Sl
+
++−
=
=
−
−
−
−
(20)
Изменив в (20) порядок интегрирования (интегрируя сначала по lDD ,,2
при фиксированном 1D ), получим произведение )1(1 −− Sl -мерных интегралов,
каждый из которых (обозначим их 1J ) имеет вид
1
))((
1
1 .e...
T2
−
+
−
+
−
+−
−
=
S
DtD
S
dDJ n
28 ISSN 0572-2691
Здесь n — единичный вектор
1
11
−
DD . Но 1J не зависит от n , поскольку
подынтегральная функция инвариантна относительно поворота. Поэтому вы-
числим 1J в базисе, в котором ne 1 .
В этом случае выражение, стоящее в экспоненте, равно
)()( 2
1
2
2
2
1 −+++++ SDDDt
и )1( −S -мерный интеграл распадается на произведение 2−S интегралов, даю-
щих с множителем нормировки
единицу, и интеграла
,de 1
)( 2
1 DJ
Dt+−
−
=
который легко вычисляется и равен .
t+
Остается вычислить интеграл по 1D и t . Сначала вычислим интеграл по 1D :
.e 1
2
1
)(
1
2
1 dDDJ
Dt+−
−
=
Поскольку
,de)(
1
1
2
1
−
−
−
==
S
D
DJ
имеем
.
1
2
1)(
1
1
tt
SJ
J
S
t
+
+
−
=
−=
−
+=
И окончательно, используя формулу
,
1
)(
1
0
−
=+
+−
−
ν
a
dxxa
получаем для }{ nM выражение
.
1
1
)1(
2
1
}{ 2
)(
0
−+
−
=+
−
=
+
−
Sl
S
dtt
s
M
Sl
n
При 1−= Sl 5,0}{ =nM , что отвечает значению параметра 2= . Таким
образом, доказано утверждение 1.
Рассмотрим теперь, с какой скоростью будет сходиться алгоритм, в котором
используется процедура 3. Вычислить эту скорость можно, не используя прибли-
жение, полученное выше для алгоритмов с .1− SN
Утверждение 2. Процедура 3 сходится со скоростью геометрической про-
грессии со знаменателем
N
+
−=
1
1 , (21)
Международный научно-технический журнал
«Проблемы управления и информатики», 2020, № 2 29
где зависит от соотношения S и .N
Доказательство. Проецирование на вектор sn−x при 1S может умень-
шить величину
2
n , потому что предыдущие 1−S шагов алгоритма изменяют
направление вектора n по сравнению с его направлением на )( Sn− -м шаге, ко-
гда он перпендикулярен sn−x и 0T = −− snSn x .
Поэтому сначала рассмотрим вспомогательную задачу, формулируемую так:
насколько в среднем увеличивается квадрат нормы проекции вектора на вектор e
после итерации по алгоритму Качмажа вдоль случайного вектора b . Пусть векто-
ры e и b независимы (это справедливо для проецирования на вновь приходящие
векторы nx ). Введя обозначения eP и bP для операторов проецирования на век-
торы e и b , с учетом явного вида eP и bP вычислим величину
2
ebM ,
−= )( bPI , где, как и ранее, = eP , .= ee P
Имеем
})()({ 2T
2
−−=
bebeb PIPPIMM (22)
и задача сводится к усреднению по случайному вектору b операторов ebPP и
beb PPP . Так как b не зависит от e ,
,
1
}]{[}{ eebeb P
N
PPMPPM == (23)
поскольку
.
1
}{ I
N
PM bb = (24)
Математическое ожидание оператора beb PPP вычислялось выше даже в бо-
лее общей ситуации. В нашем случае имеем
.
)2(
2
)2(
1
}{ ebebb P
NN
I
NN
PPPM
+
+
+
= (25)
Окончательно с точностью до членов )( 2−No получаем
.
12
1
2
2
2
2
+
−=
NN
M ee
Ясно, что если рассматривается проецирование на вектор 1+−Snx , на который
уже производилось проецирование на одном из предыдущих шагов, то эта ситуа-
ция моделируется задачей, аналогичной рассмотренной выше, но с корреляцией
между векторами и e , поскольку проекция n на 1+−Snx в среднем в раз
меньше, чем проекция n на случайно ориентированный вектор e . Введенный
здесь параметр как раз и будет характеризовать, насколько дополнительно
уменьшится величина квадрата нормы после проецирования на вектор 1+−Snx , на
который уже производилось проецирование 1−S шагов назад (тогда вектор
1+− Sn не зависел от этого вектора 1+−Snx ). После )1( −S -го шага 1+− Sn
и 1+−Snx ортогональны, затем проекция in− на 1+−Snx возрастает по величине,
30 ISSN 0572-2691
но если величина проекции на случайным образом ориентированный вектор e
дается формулой 21T ][}{ = −NPM e , то сохраняющаяся «антикорреляция» век-
торов in− и 1+−Snx приводит к тому, что величина проекции n на 1+−Snx будет
меньше. Этот факт описывается соотношением
,
1
}{
2
=
N
PM e
T
e где .1
Формулы (22) и (23) не изменятся и подстановка в (22) дает формулу
.
12
1
2
2
2
2
+
−=
NN
M eeb (26)
Работу алгоритма теперь можно описать следующим образом. Шаг по алго-
ритму Качмажа дает убывание величины }{
2
nM в
11 −− N раз, а производимое
затем проецирование на вектор 1+−Snx уменьшает
2
еще в
11 −− N раз. Урав-
нение для определения параметра получается итерированием соотношений (22)
и (26) с учетом изменения
2
на каждом шаге. Обозначим it математическое
ожидание проекции n на вектор nx после i шагов алгоритма iinM = + }{
2
.
С учетом этого имеем следующую систему рекуррентных уравнений:
−=−=
+−=
−
+
−−
+
,1,0), 1(
,)21(
1
1
21
1
SiN
NNtt
iii
iiii
(27)
причем Ii = +12 , = i2 . Начальные условия при 0=i после шага по алгоритму
Качмажа дают 0=ot , oo = .
Решение системы (26) в общем виде запишем так:
);1( 1
1
1
−
=
+ −= Nj
j
oi
.1
2
1
1
11
1
−
−=
−
===
+
NN
t i
l
i
i
lj
i
l
i (28)
Необходимо определить, какое значение примет it на )1(2 −S -м шаге, по-
скольку на этом шаге происходит повторное проецирование на вектор nx , вели-
чина
2
n уменьшается как раз на
1−N , и скорость сходимости процедуры 3
будет выражаться формулой
.
1
1
1
1
−
−=
N
Поскольку по определению параметра имеем
,)1(2)1(2
2
)1(2
2
)1(2 −−−+−+
==
− SSSnSn
N
tM (29)
Международный научно-технический журнал
«Проблемы управления и информатики», 2020, № 2 31
то в принципе подстановка )1(2 −St и )1(2 − S из общего решения дает уравнение
для . Получим это уравнение, выписанное с точностью до членов )( 1−No , по-
скольку реально всегда 1N . При этом
.11 1
−
−= +
NN
ii
Выразив 2+it и 2+i через it и i , с учетом того, что
)21)(21( 1
1
12 −
+
− −−= NN ii , можно записать с точностью до членов
,2 22
2 ii Ntit += −
+ .2 ii = +
Отсюда находим
,1
)1(2 o
S
S = −
− ).(2 )2()2(22
)1(2
−−−
− ++= SS
oS Nt
Этот вывод более нагляден, чем формальное разложение общего решения си-
стемы (26), даваемого формулами (27), по малому параметру
1−N . Подставляя
)1(2 −St и )1(2 − S в (28), получаем для алгебраическое уравнение
).1(21 211 −−− ++++=− SNN (30)
При →s из (29) имеем уравнение для 1)1(1 −+=− N :
,
)1(
21
1
2 −
+=−
NN
имеющее положительный корень
121 −−= N , что согласуется с «геометриче-
ской моделью» уравнения, даваемой проекционным алгоритмом, так как усло-
вие →s означает, что «память» о проецировании на вектор nx уже стерта
и дополнительное проецирование на этот вектор увеличивает скорость сходи-
мости ровно вдвое, если эту скорость характеризовать величиной −1 . При
11 −SN из (30) получаем
.
)1(2
1
1
1
−
+−
N
S
N
При Ns ~ с учетом того, что
1)1(1 −+−= N , получаем для уравнение
,
2
1
11
1
2
1
+
−−
+
=
−s
которое при 1~1−SN можно преобразовать к виду
.1
1
2
1
)1(
−
+
=
−
+−
N
S
e
Например, при 5,01 =−SN имеем корень 7,0= .
32 ISSN 0572-2691
Скорость сходимости алгоритма с такой же глубиной S будет равной скоро-
сти сходимости многошагового проекционного алгоритма (с точным проецирова-
нием) при .4,0 NS
Заключение
Как показали результаты исследований, использование аппроксимации опера-
тора ортогонального проецирования в алгоритмах оценивания позволяет при незна-
чительном снижении скорости сходимости алгоритмов существенно упростить их
реализацию и повысить их вычислительную устойчивость вследствие устранения
операции обращения матрицы наблюдений. При этом для гарантированного улуч-
шения их вычислительных свойств целесообразно применить достаточно простую в
данном случае процедуру регуляризации алгоритма Качмажа с использованием су-
ществующих рекомендаций по выбору параметра регуляризации [6].
ABSTRACTS
Б.Д. Лібероль, О.Г. Руденко, О.О. Безсонов
ПСЕВДОПРОЕКЦІЙНІ АЛГОРИТМИ ОЦІНЮВАННЯ,
ЩО БАЗУЮТЬСЯ НА АПРОКСИМАЦІЇ ОПЕРАЦІЇ
ОРТОГОНАЛЬНОГО ПРОЕЦІЮВАННЯ
Одним з найбільш ефективних і найбільш простих в обчислювальному відно-
шенні однокрокових алгоритмів оцінювання є алгоритм Качмажа, запропоно-
ваний в [1]. У багатьох подальших роботах було розглянуто можливість прис-
корення алгоритму Качмажа шляхом використання не одного, а ряду вимірю-
вань. Роботи [8, 9] послужили поштовхом до розробки нового класу
багатокрокових проекційних алгоритмів [10–14], в яких при побудові оцінки на
n-му кроці використовується не тільки нова інформація, як це відбувається в
алгоритмі Качмажа, а й інформація про ряд попередніх кроків n – 1, n – 2 .... .
Кількість таких кроків визначає пам’ять алгоритму. При цьому завдяки кращій
екстраполяції і фільтрації у ряді випадків вдається домогтися істотного
скорочення часу ідентифікації. Реалізація багатокрокового (S-крокового)
проекційного алгоритму вимагає обчислення зворотної матриці спостережень
розмірності .SS В [11–14] встановлено властивості випадкових псевдообер-
нених матриць і матриць проеційованих, які дозволили визначити швидкість
збіжності даних алгоритмів і зробити висновок про те, що урахування в даних
алгоритмах інформації про S попередніх кроків рівносильне в сенсі швидкості
збіжності зменшенню розмірності вихідного простору N на S. У даній роботі
пропонуються і досліджуються псевдопроекційні алгоритми, що володіють
близькими до багатокрокових проекційних алгоритмів властивостями, але
більш прості в реалізації. Дані алгоритми використовують апроксимацію опе-
рації точного проеціювання і будуються на основі однокрокового адаптивного
алгоритму Качмажа. Отримано оцінки швидкості збіжності запропонованих
процедур і показано, що використання такої апроксимації дозволяє при незнач-
ному зниженні швидкості збіжності алгоритмів істотно спростити їх реалізацію
та підвищити обчислювальну стійкість внаслідок усунення операції обертання
матриці спостережень.
Ключові слова: алгоритм Качмажа, проекційний алгоритм, рекурентна проце-
дура, асимптотична оцінка, точність ідентифікації.
B.D. Liberol, O.G. Rudenko, A.A. Bezsonov
PSEUDOPROJECTION ESTIMATION ALGORITHMS
BASED ON APPROXIMATION OF ORTHOGONAL
PROJECTION OPERATION
Kaczmarz algorithm proposed in [1] is one of the most effective and most computa-
tionally simple one-step estimation algorithms. In a number of subsequent studies the
possibility of acceleration algorithm Kaczmarz by the use of not one but a series of
Международный научно-технический журнал
«Проблемы управления и информатики», 2020, № 2 33
measurements was examined. Research made in [8, 9] was a push for the develop-
ment of a new class of algorithms — multistage projection algorithms [10–14], in
which during the construction of estimates on the n-th step not only new information
is used, as it comes in Kaczmarz algorithm, but also information about number of
previous steps n–1, n–2 .... . The number of these steps determines the algorithm’s
memory. In this case, thanks to a better extrapolation and filtering, in some cases it is
possible to reduce significantly the time of identification. The implementation of
multi-step ( S -step) projection algorithm requires the computation of the inverse ma-
trix of observations with SS dimension. In [11–14] properties of random
pseudoinverse matrix and the projection matrix are set. It helped to determine the rate
of convergence of these algorithms and conclude that taking into account information
about previous S steps is equivalent in terms of convergence speed to reduction of
dimension N in the original space to S. In this paper we propose and investigate
pseudoprojective algorithms that have close to the multi-stage projection algorithm
properties, but are simpler to implement. These algorithms use an approximation of
the exact projection operation and are based on one-step Kaczmarz adaptive algo-
rithm. Estimates of the convergence rate of the proposed procedures are obtained. It
is shown that the use of such approximation allows, with a slight decrease in the con-
vergence rate of the algorithms, to simplify significantly their implementation and in-
crease computational stability due to eliminating the rotation operation of the obser-
vation matrix.
Keywords: Kaczmarz algorithm, projection algorithm, recursive procedure,
asymptotic estimate, identification accuracy.
REFERENCES
1. Kaczmarz, S. Approximate solution of systems of linear equations. Int. J. of Control. 1993. № 57.
P. 1269–1271. https://doi.org/10.1080/00207179308934446.
2. Чадеев В.М. Определение динамических характеристик объектов в процессе их нормаль-
ной эксплуатации для целей самонастройки. Автоматика и телемеханика. 1964. 25. № 9.
С. 1302–1306.
3. Райбман Н.С., Чадеев В.М. Адаптивные модели в системах управления. М.: Сов. радио,
1966. 156 с.
4. Aved'jan A.D. Bestimmung der Parameter linearer Modelle stationarer und instationarer Strecken.
Messen, steuern, regeln. 1971. N 9. P. 348–350.
5. Руденко, О.Г. Оценка скорости сходимости одношаговых устойчивых алгоритмов иденти-
фикации. Доклады АН УССР. Сер. А. Физ-мат. и техн. науки. 1982. № 1. C. 64–66.
6. Либероль, Б.Д., Руденко, О.Г., Бессонов, А.А. Исследование сходимости одношаговых
адаптивных алгоритмов идентификации. Международный научно-технический журнал
«Проблемы управления и информатики». 2018. № 5. С.19–32.
7. Либероль, Б.Д., Руденко, О.Г., Тимофеев, В.А. Модифицированный алгоритм Качмажа для
оценивания параметров нестационарных объектов. Проблемы управления и информатики.
1995. № 4. С. 81–89
8. Лелашвили, Ш. Г. Применение одного итерационного метода для анализа многомерных
автоматических систем. Схемы автоматического управления. 1965. С.19–33.
9. Лелашвили, Ш. Г. Некоторые вопросы построения статистической модели многомерных
объектов. Автоматическое управление. 1967. С. 59–96.
10. Аведьян, Э.Д. Модифицированные алгоритмы Качмажа для оценки параметров линейных
объектов. Автоматика и телемеханика. 1978. № 5. C. 64–72.
11. Ищенко Л.А., Либероль Б.Д., Руденко О.Г. Проекционные алгоритмы идентификации ли-
нейных объектов. Докл. АН УССР. Сер. А. 1985. № 7. C. 62–64.
12. Ищенко Л.А., Либероль Б.Д., Руденко О.Г. Адаптивное оценивание параметров нестацио-
нарных объектов. Докл. АН УССР. Сер. А. 1985. № 12. C. 70–72.
13. Ищенко Л.А., Либероль Б.Д., Руденко О.Г. О свойствах одного класса многошаговых адап-
тивных алгоритмов идентификации Кибернетика. 1986. №1. С.92–96.
14. Либероль Б.Д., Руденко О.Г. О свойствах проекционных алгоритмов оценивания парамет-
ров нестационарных объектов. Докл. АН УССР. Сер. А. 1990. № 4. C. 71–74.
15. Цыпкин Я.З. Адаптация и обучение в автоматических системах. М.: Наука, 1968. 399 с.
16. Поляк Б.Т Сравнение скорости сходимости одношаговых и многошаговых алгоритмов оп-
тимизации при налички помех измерений. Изв. АН СССР. Техническая кибернетика.1974.
№ 5. С. 9–12.
17. Себер Дж. Линейный регрессионный анализ. М.: Мир, 1980. 456 с.
Получено 02.12.2019
|
| id | nasplib_isofts_kiev_ua-123456789-208708 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2025-12-07T18:26:58Z |
| publishDate | 2020 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Либероль, Б.Д. Руденко, О.Г. Бессонов, А.А. 2025-11-04T16:08:00Z 2020 Псевдопроекционные алгоритмы оценивания, основанные на аппроксимации операции ортогонального проецирования / Б.Д. Либероль, О.Г. Руденко, А.А. Бессонов // Проблемы управления и информатики. — 2020. — № 2. — С. 16-33. — Бібліогр.: 17 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/208708 004.852 10.1615/JAutomatInfScien.v52.i3.20 Одним з найбільш ефективних і найбільш простих в обчислювальному відношенні однокрокових алгоритмів оцінювання є алгоритм Качмажа, запропонований в [1]. У багатьох подальших роботах було розглянуто можливість прискорення алгоритму Качмажа шляхом використання не одного, а ряду вимірювань. Роботи [8, 9] послужили поштовхом до розробки нового класу багатокрокових проекційних алгоритмів [10–14], в яких при побудові оцінки на n-му кроці використовується не тільки нова інформація, як це відбувається в алгоритмі Качмажа, а й інформація про ряд попередніх кроків n – 1, n – 2 .... . Кількість таких кроків визначає пам’ять алгоритму. При цьому завдяки кращій екстраполяції і фільтрації у ряді випадків вдається домогтися істотного скорочення часу ідентифікації. Реалізація багатокрокового (S-крокового) проекційного алгоритму вимагає обчислення зворотної матриці спостережень розмірності S S. В [11–14] встановлено властивості випадкових псевдообернених матриць і матриць проеційованих, які дозволили визначити швидкість збіжності даних алгоритмів і зробити висновок про те, що урахування в даних алгоритмах інформації про S попередніх кроків рівносильне в сенсі швидкості збіжності зменшенню розмірності вихідного простору N на S. У даній роботі пропонуються і досліджуються псевдопроекційні алгоритми, що володіють близькими до багатокрокових проекційних алгоритмів властивостями, але більш прості в реалізації. Дані алгоритми використовують апроксимацію операції точного проеціювання і будуються на основі однокрокового адаптивного алгоритму Качмажа. Отримано оцінки швидкості збіжності запропонованих процедур і показано, що використання такої апроксимації дозволяє при незначному зниженні швидкості збіжності алгоритмів істотно спростити їх реалізацію та підвищити обчислювальну стійкість внаслідок усунення операції обертання матриці спостережень. Kaczmarz algorithm proposed in [1] is one of the most effective and most computationally simple one-step estimation algorithms. In a number of subsequent studies the possibility of acceleration algorithm Kaczmarz by the use of not one but a series of measurements was examined. Research made in [8, 9] was a push for the development of a new class of algorithms — multistage projection algorithms [10–14], in which during the construction of estimates on the n-th step not only new information is used, as it comes in Kaczmarz algorithm, but also information about number of previous steps n–1, n–2 .... . The number of these steps determines the algorithm’s memory. In this case, thanks to a better extrapolation and filtering, in some cases it is possible to reduce significantly the time of identification. The implementation of multi-step ( S -step) projection algorithm requires the computation of the inverse matrix of observations with S S dimension. In [11–14] properties of random pseudoinverse matrix and the projection matrix are set. It helped to determine the rate of convergence of these algorithms and conclude that taking into account information about previous S steps is equivalent in terms of convergence speed to reduction of dimension N in the original space to S. In this paper we propose and investigate pseudoprojective algorithms that have close to the multi-stage projection algorithm properties, but are simpler to implement. These algorithms use an approximation of the exact projection operation and are based on one-step Kaczmarz adaptive algorithm. Estimates of the convergence rate of the proposed procedures are obtained. It is shown that the use of such approximation allows, with a slight decrease in the convergence rate of the algorithms, to simplify significantly their implementation and increase computational stability due to eliminating the rotation operation of the observation matrix. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Методы оптимизации и оптимальное управление Псевдопроекционные алгоритмы оценивания, основанные на аппроксимации операции ортогонального проецирования Псевдопроекційні алгоритми оцінювання, що базуються на апроксимації операції ортогонального проеціювання Pseudoprojection estimation algorithms based on approximation of orthogonal projection operation Article published earlier |
| spellingShingle | Псевдопроекционные алгоритмы оценивания, основанные на аппроксимации операции ортогонального проецирования Либероль, Б.Д. Руденко, О.Г. Бессонов, А.А. Методы оптимизации и оптимальное управление |
| title | Псевдопроекционные алгоритмы оценивания, основанные на аппроксимации операции ортогонального проецирования |
| title_alt | Псевдопроекційні алгоритми оцінювання, що базуються на апроксимації операції ортогонального проеціювання Pseudoprojection estimation algorithms based on approximation of orthogonal projection operation |
| title_full | Псевдопроекционные алгоритмы оценивания, основанные на аппроксимации операции ортогонального проецирования |
| title_fullStr | Псевдопроекционные алгоритмы оценивания, основанные на аппроксимации операции ортогонального проецирования |
| title_full_unstemmed | Псевдопроекционные алгоритмы оценивания, основанные на аппроксимации операции ортогонального проецирования |
| title_short | Псевдопроекционные алгоритмы оценивания, основанные на аппроксимации операции ортогонального проецирования |
| title_sort | псевдопроекционные алгоритмы оценивания, основанные на аппроксимации операции ортогонального проецирования |
| topic | Методы оптимизации и оптимальное управление |
| topic_facet | Методы оптимизации и оптимальное управление |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/208708 |
| work_keys_str_mv | AT liberolʹbd psevdoproekcionnyealgoritmyocenivaniâosnovannyenaapproksimaciioperaciiortogonalʹnogoproecirovaniâ AT rudenkoog psevdoproekcionnyealgoritmyocenivaniâosnovannyenaapproksimaciioperaciiortogonalʹnogoproecirovaniâ AT bessonovaa psevdoproekcionnyealgoritmyocenivaniâosnovannyenaapproksimaciioperaciiortogonalʹnogoproecirovaniâ AT liberolʹbd psevdoproekcíiníalgoritmiocínûvannâŝobazuûtʹsânaaproksimacííoperacííortogonalʹnogoproecíûvannâ AT rudenkoog psevdoproekcíiníalgoritmiocínûvannâŝobazuûtʹsânaaproksimacííoperacííortogonalʹnogoproecíûvannâ AT bessonovaa psevdoproekcíiníalgoritmiocínûvannâŝobazuûtʹsânaaproksimacííoperacííortogonalʹnogoproecíûvannâ AT liberolʹbd pseudoprojectionestimationalgorithmsbasedonapproximationoforthogonalprojectionoperation AT rudenkoog pseudoprojectionestimationalgorithmsbasedonapproximationoforthogonalprojectionoperation AT bessonovaa pseudoprojectionestimationalgorithmsbasedonapproximationoforthogonalprojectionoperation |