О выборе начального приближения в итерационных алгоритмах решения уравнения X − AᵀX⁻¹A = Q
Розглянуто алгоритм розв’язання матричного рівняння. У цьому алгоритмі початкове наближення будується за допомогою лінійних матричних нерівностей. Для уточнення отриманого наближення використовується процедура Ньютона. На прикладах показано ефективність алгоритму і у випадках, коли власні значення м...
Saved in:
| Published in: | Проблемы управления и информатики |
|---|---|
| Date: | 2011 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/207280 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | О выборе начального приближения в итерационных алгоритмах решения уравнения X − AᵀX⁻¹A = Q / В.Б. Ларин // Проблемы управления и информатики. — 2011. — № 1. — С. 81–86. — Бібліогр.: 22 назви. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859733253135532032 |
|---|---|
| author | Ларин, В.Б. |
| author_facet | Ларин, В.Б. |
| citation_txt | О выборе начального приближения в итерационных алгоритмах решения уравнения X − AᵀX⁻¹A = Q / В.Б. Ларин // Проблемы управления и информатики. — 2011. — № 1. — С. 81–86. — Бібліогр.: 22 назви. — рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Розглянуто алгоритм розв’язання матричного рівняння. У цьому алгоритмі початкове наближення будується за допомогою лінійних матричних нерівностей. Для уточнення отриманого наближення використовується процедура Ньютона. На прикладах показано ефективність алгоритму і у випадках, коли власні значення матричного пучка, асоційованого з цим рівнянням, лежать на колі одиничного радіуса, тобто коли використання традиційних алгоритмів є проблематичним.
The algorithm of solution of the matrix equation is considered. In this algorithm, the starting value is constructed by use of the linear matrix inequalities. For improving the received starting value, the Newton procedure is used. On the example, the efficiency of the algorithm is shown also in cases when eigenvalues of the matrix pencil associated with this equation lay on the unit circle. Using in these cases the traditional algorithms is problematic.
|
| first_indexed | 2025-12-01T14:28:27Z |
| format | Article |
| fulltext |
© В.Б. ЛАРИН, 2011
Международный научно-технический журнал
«Проблемы управления и информатики», 2011, № 1 81
МЕТОДЫ ОБРАБОТКИ ИНФОРМАЦИИ
УДК 517. 977. 58
В.Б. Ларин
О ВЫБОРЕ НАЧАЛЬНОГО ПРИБЛИЖЕНИЯ
В ИТЕРАЦИОННЫХ АЛГОРИТМАХ
РЕШЕНИЯ УРАВНЕНИЯ X A
T
X
1A Q
Введение. В различных задачах управления (см., например, [1–4]) возникает
необходимость решать те или иные матричные уравнения. Поэтому сравнительно
простые матричные уравнения привлекали и продолжают привлекать внимание
исследователей [5–15]. В частности, это относится и к уравнению
,1T QAXAX (1)
где nnRQ — симметричная неотрицательно-определенная матрица, A
nnR — произвольная квадратная матрица, верхний индекс T означает транс-
понирование. Уравнение (1) играет важную роль в различных приложениях
(см., например, [7] и ссылки на источники). Так, в теории случайных процес-
сов [7] возникает задача факторизации полинома
.)( 1T AzzAQzN (2)
Используя решение (1), можно факторизовать полином (2), т.е. представить его в
виде [7]
),()()( 111T AzXIXzXAIzN (3)
здесь и далее I — единичная матрица соответствующего размера.
В связи с упомянутыми приложениями предложен ряд алгоритмов построе-
ния решения (1), а именно:
1) построение точных решений [12];
2) преобразование (1) в уравнение Риккати [7, 12, 16];
3) метод удвоения интервала [15, 16];
4) метод матричных сигнум-функций [15, 16].
Кроме этих «прямых» методов следует отметить итерационные алгоритмы
[8, 9, 17], многие из которых требуют «достаточно хорошего» начального при-
ближения [9].
Как правило, упомянутые выше алгоритмы ориентированы на .0Q В этом
случае полином (2) не имеет собственных значений на окружности единичного
радиуса [7], причем если — собственное значение, то и /1 — собственное
значение. Поэтому если X — максимальное решение (1), то, как показано в [7],
собственные значения фигурирующей в (3) матрицы AX 1
лежат внутри окруж-
ности единичного радиуса. Однако если ослабить ограничение, накладываемое на
82 ISSN 0572-2691
матрицу ,Q т.е. считать, что ,0Q то возможна ситуация, когда некоторые из
собственных значений матрицы ,1AX
а следовательно, и некоторые из соб-
ственных значений матричного пучка, соответствующего (1) [7], лежат на окруж-
ности единичного радиуса [16, 18].
В этом случае упомянутые «прямые» методы неэффективны, и для решения
такого рода задач в [16, 18, 19] было предложено использовать соотношение
Басcа, которое связано с нахождением собственных значений характеристическо-
го полинома соответствующей матрицы. Эти собственные значения необходимы
для выбора той или иной факторизации упомянутого полинома.
Отметим, что аналогичная задача, связанная с факторизацией полинома
,)( 1T AzzAQzR т.е. представление его в виде
),()()( 111T AzXIXzXAIzR
сводится (см. соотношение (4.4.10) [1]) к нахождению решения уравнения, анало-
гичного (1), а именно:
.1T QAXAX
(4)
В [13] использовались линейные матричные неравенства (ЛМН) для нахождения
решения (4). Причем, как показано (на примере) в [13], полученное с помощью
ЛМН приближенное решение (4) в случае, когда собственные значения матрицы
AX 1 лежат на окружности единичного радиуса, может служить хорошим
начальным приближением. В этой связи целесообразно рассмотреть возможность
использования ЛМН для получения начального приближения для максимального
решения (1).
Линейные матричные неравенства. Сопоставим (1) следующее нелинейное
матричное неравенство:
.1T QAXAX
(5)
В качестве начального приближения для нахождения максимального решения (1)
выберем (5), имеющее минимальный след и удовлетворяющее условию .0X
Известно [20], что неравенство (5) можно представить в виде следующего ЛМН:
.0
T
XA
AQX
(6)
Таким образом, задачу выбора начального приближения для нахождения мак-
симального решения (1) можно сформулировать в терминах стандартной задачи
ЛМН, а именно, найти матрицу ,X имеющую минимальный след (mantrace (X)),
удовлетворяющую условиям (6) и .0X Это стандартная задача ЛМН [21], и для
ее решения можно использовать стандартную процедуру mincx.m пакета MATLAB.
Для уточнения полученного таким образом начального приближения можно
использовать ту или иную процедуру [9], например процедуру Ньютона (алго-
ритм 4.3 [8]). Изложим суть этой процедуры. Пусть 0X — начальное приближе-
ние решения (1), полученное, например, с помощью описанного выше алгоритма
ЛМН. Последующее приближение находится следующим образом. Для ,2,1n
вычисляются матрицы .1
1AXL nn
Следующее приближение находится с помо-
щью решения уравнения
.2 TT ALQLXLX nnnnn (7)
Международный научно-технический журнал
«Проблемы управления и информатики», 2011, № 1 83
Решение уравнения (7). Для решения (7) могут использоваться различные
алгоритмы, см., например, [6]. Известно [22], что, используя прямое произведение
матриц (), решение матричного уравнения (7) можно свести к решению системы
линейных уравнений. Пусть
,
T
T
1
nX
X
x ,
T
T
1
nC
C
c
где ii CX , — строки матриц ,nX .2 T ALQC n Решение (7) определяется сле-
дующей системой уравнений:
,cGx .TT
nn LLIIG (8)
Однако если 1L ( L — спектральный радиус матрицы nL ), то для реше-
ния (7) можно использовать более простой алгоритм [16]. Согласно [10] при
1L решение (7) )( XXn можно представить в виде сходящегося ряда
,
0
j
jjCBAX ,T
nLA .nLB (9)
Рассмотрим следующую последовательность частных сумм ряда (9), а именно
матрицы :jX
,)()(
1
j
j
j
jj BXAXX
,2)( jj (10)
2)()1( ][ jj AA ,][ 2)()1( jj BB
.,2,1,0,0 jCX
Быстрота сходимости последовательности jX к решению (7) обусловлена тем,
что каждому индексу j в (10) соответствует сумма j2 членов ряда (9). Отметим,
что в случае TBA этот алгоритм совпадает с известным алгоритмом решения
уравнения Ляпунова [1, 5].
В [5] применительно к уравнению Ляпунова проведено сравнение эффектив-
ности этого алгоритма и приведенного выше алгоритма прямых произведе-
ний [22]. В результате сделан вывод, что алгоритм прямых произведений (соот-
ношение (8)) эффективнее только при .10n
Существенно, что алгоритм, определяемый (10), может быть реализован при
использовании процедуры Symbolic Toolbox пакета MATLAB. Это, в свою оче-
редь, позволяет находить решение (7) с высокой точностью (см. пример 3.1 [16]).
Для иллюстрации эффективности описанного выше алгоритма решения (1)
рассмотрим следующие примеры.
Пример 1 (Ex. 5 [9]):
,
47,389,2
47,347,3
A .IQ
Пример 2 (Ex. 6 [9]):
,
~
~
41,1
A
A
A ,
1375,00649519,02598076,0
0649519,02125,015,0
2598076,015,01,0
~
A .IQ
84 ISSN 0572-2691
Пример 3 (Ex. 7 [9]):
,
6010
2050
A .
42
23
Q
Пример 4:
,
10
11
A .0Q
Пример 5 (аналог примера 6.4 [16]):
,}9,,2,1,0{diag A }.0,,0,0,10{diag Q
Для решения этих примеров обращались к описанной выше процедуре ЛМН,
затем полученное решение уточнялось путем использования одной итерации ме-
тода Ньютона (7). Для решения (7) привлекалось соотношение (8). Таким обра-
зом, были получены решения примеров. Как и в [9], оценка точности решения
)(X определялась так:
.1T
QAXAXer (11)
Соответствующие этим решениям погрешности (8) приведены в таблице (по-
грешность er соответствует приближенному решению, полученному с помощью
ЛМН; er — погрешность решения, полученного после использования одной
итерации (7)).
Таблица
Номер примера er
er
1 6,68 ·1011 1,2 ·1015
2 3,8 ·1011 5,8 ·1016
3 1,25 ·109 3 ·1014
4 1,7 ·1011 6,7 ·1016
5 2,7 ·1011 3,6 ·1015
Отметим, что в последних двух примерах собственные значения матрицы
AX 1
лежат на окружности единичного радиуса, поэтому использование для ре-
шения этих примеров традиционных алгоритмов проблематично.
Так, точное решение примера 4 имеет вид
.
21
12
3
1
X
Следовательно, собственные значения матрицы запишем
,
11
12
3
11
AX
)3(
2
1
2,1 i лежат на окружности единичного радиуса. Аналогичная
ситуация и в примере 5. Точное решение имеет вид ,}9,,2,1,10{diag X
следовательно, матрица .}1,,1,0{diag1
AX Другими словами, 9 из 10 соб-
ственных значений матрицы AX 1
равны 1.
Международный научно-технический журнал
«Проблемы управления и информатики», 2011, № 1 85
Отметим, что, сравнивая оценки точности, приведенные во второй и третьей
строках таблицы, можно констатировать, что одна итерация с использованием ме-
тода Ньютона обеспечивает существенное повышение точности. В свою очередь,
это можно интерпретировать как факт, что начальное приближение, полученное
с помощью ЛМН, достаточно близко к точному решению.
Заключение. Рассмотрен алгоритм решения матричного уравнения (1).
В этом алгоритме начальное приближение строится с помощью ЛМН. Для уточ-
нения полученного приближения используется процедура Ньютона. На примерах
показана эффективность алгоритма и в случаях, когда собственные значения
матричного пучка, ассоциированного с этим уравнением, лежат на окружности
единичного радиуса, т.е. когда использование традиционных алгоритмов проб-
лематично.
В.Б. Ларін
ПРО ВИБІР ПОЧАТКОВОГО НАБЛИЖЕННЯ
В ІТЕРАЦІЙНИХ АЛГОРИТМАХ
РОЗВ’ЯЗАННЯ РІВНЯННЯ X A
T
X
1A Q
Розглянуто алгоритм розв’язання матричного рівняння. У цьому алгоритмі
початкове наближення будується за допомогою лінійних матричних нерівно-
стей. Для уточнення отриманого наближення використовується процедура
Ньютона. На прикладах показано ефективність алгоритму і у випадках, коли
власні значення матричного пучка, асоційованого з цим рівнянням, лежать
на колі одиничного радіуса, тобто коли використання традиційних алгорит-
мів є проблематичним.
V.B. Larin
ON THE CHOICE OF THE INITIAL
APPROXIMATION IN ITERATIVE ALGORITHMS
OF SOLUTION OF THE EQUATION X A
T
X
1A Q
The algorithm of solution of the matrix equation is considered. In this algorithm the
starting value is constructed by use of the linear matrix inequalities. For improving
the received starting value the Newton procedure is used. On the example, the effi-
ciency of algorithm is shown also in the cases when eigenvalues of the matrix pencil
which is associated with this equation lay on the unit circle. Using in these cases the
traditional algorithms is problematic.
1. Aliev F.A., Larin V.B. Optimization of linear control systems: Analytical methods and computa-
tional algorithms. — Amsterdam : Gordon and Breach Sci. Publ., 1998. — 261 p.
2. Larin V.B. Control problems for wheeled robotic vehicle // Int. Appl. Mech. — 2009. — 45,
N 4. — P. 363–388.
3. Aliev F.A., Larin V.B. Optimization problems for periodic systems // Ibid. — 2009. — 45,
N 11. — P. 1162–1188.
4. Larin V.B. On selection of program trajectory of motion for compound wheeled transport robot //
Ibid. — 2010. — 46, N 3. — P. 291–299.
5. Pace I.S., Barnett S. Comparison of numerical methods for solving Lyapunov matrix equations //
Int. J. Contr. — 1972. — 15. — P. 907–915.
6. Gardiner J.D., Laub A.J., Amato J.J., Moler C.B. Solution of the Sylvester matrix equation
AXBT CXDT E // ACM Transact. on Mathemat. Software. — 1992. — 18, N 2. —
P. 223–231.
86 ISSN 0572-2691
7. Ferrante A., Levy B.C. Hermitian solution of the equation X Q N X 1X * // Linear Algebra
Appl. — 1996. — 247. — P. 359–373.
8. Meini B. Efficient computation of the extreme solutions of X AX 1A = Q and X AX 1A = Q,
Hermitian solutions of the equation X Q N X 1N * // Mathemat. of Comput. — 2001. — 71,
N 239. — P. 1189–1204.
9. Ivanov I.G., Hasanov V.I., Uhlig F. Improved methods and starting values to solve the matrix
equations X AX 1A = I iteratively // Ibid. — 2004. — 74, N 249. — P. 263–278.
10. Jiang T., Wei M. On solutions of the matrix equations X AXB C and CBXAX // Linear
Algebra and its Appl. — 2003. — 367. — P. 225–233.
11. Larin V.B. Determination both stabilizing and antistabilizing solutions of the discrete-time algebraic
Riccati equation // Int. J. of Appl. Math. and Mech. — 2007. — 3, N 1. — P. 42–60.
12. Adam M., Assimakis N., Sanida F. Algebraic solutions of the matrix equations X ATX 1A Q
and X ATX 1A Q // Int. J. of Algebra. — 2008. — 2, N 11. — P. 501–518.
13. Larin V.B. About finding the maximal and minimal solutions of the equation X ATX 1A Q //
Int. J. of Appl. Math and Mech. — 2008. — 4, N 4. — P. 10–15.
14. Ларин В.Б. О решении уравнения Сильвестра // Проблемы управления и информатики. —
2009. — № 1. — С. 29–34.
15. Ларин В.Б. Алгоритмы решения уравнения X ATX 1A Q // Там же. — 2009. — № 2. —
С. 7–13.
16. Larin V.B. Solution of matrix equations in problems of the mechanics and control // Int. Appl.
Mech. — 2009. — 45, N 8. — P. 847–872.
17. El-Sayed S. M., Ran A.C.M. On an iteration method for solving a class of nonlinear matrix equa-
tions // SIAM J. Matrix Anal. Appl. — 2001. — 23, N 3. — P. 632–645.
18. Aliev F.A., Larin V.B. About use of the Bass relations for solutions of matrix equations // Appl.
and Comp. Math. — 2009. — 8, N 2. — P. 152–162.
19. Ларин В.Б., Алиев Ф.А. Об использовании соотношения Басса при решении матричных
уравнений // Докл. НАН Азербайджана. — 2008. — № 4. — С. 15–25.
20. Boyd S., Ghaoui L.E., Feron E., Balakrishnan V. Linear matrix inequalities in system and control
theory. — Philadelphia : SIAM, 1994. — 193 p.
21. Gahinet P., Nemirovski A., Laub A.J., Chilali M. LMI control Toolbox user’s guide. — The
MathWorks Inc., 1995. — 289 p.
22. Ланкастер П. Теория матриц. — М.: Наука, 1978. — 280 с.
Получено 09.09.2010
|
| id | nasplib_isofts_kiev_ua-123456789-207280 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2025-12-01T14:28:27Z |
| publishDate | 2011 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Ларин, В.Б. 2025-10-04T18:38:43Z 2011 О выборе начального приближения в итерационных алгоритмах решения уравнения X − AᵀX⁻¹A = Q / В.Б. Ларин // Проблемы управления и информатики. — 2011. — № 1. — С. 81–86. — Бібліогр.: 22 назви. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207280 517.977.58 10.1615/JAutomatInfScien.v43.i2.10 Розглянуто алгоритм розв’язання матричного рівняння. У цьому алгоритмі початкове наближення будується за допомогою лінійних матричних нерівностей. Для уточнення отриманого наближення використовується процедура Ньютона. На прикладах показано ефективність алгоритму і у випадках, коли власні значення матричного пучка, асоційованого з цим рівнянням, лежать на колі одиничного радіуса, тобто коли використання традиційних алгоритмів є проблематичним. The algorithm of solution of the matrix equation is considered. In this algorithm, the starting value is constructed by use of the linear matrix inequalities. For improving the received starting value, the Newton procedure is used. On the example, the efficiency of the algorithm is shown also in cases when eigenvalues of the matrix pencil associated with this equation lay on the unit circle. Using in these cases the traditional algorithms is problematic. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Методы обработки информации О выборе начального приближения в итерационных алгоритмах решения уравнения X − AᵀX⁻¹A = Q Про вибір початкового наближення в ітераційних алгоритмах розв’язання рівняння X − AᵀX⁻¹A = Q On the choice of the initial approximationin iterative algorithms ofsolution of the equation X − AᵀX⁻¹A = Q Article published earlier |
| spellingShingle | О выборе начального приближения в итерационных алгоритмах решения уравнения X − AᵀX⁻¹A = Q Ларин, В.Б. Методы обработки информации |
| title | О выборе начального приближения в итерационных алгоритмах решения уравнения X − AᵀX⁻¹A = Q |
| title_alt | Про вибір початкового наближення в ітераційних алгоритмах розв’язання рівняння X − AᵀX⁻¹A = Q On the choice of the initial approximationin iterative algorithms ofsolution of the equation X − AᵀX⁻¹A = Q |
| title_full | О выборе начального приближения в итерационных алгоритмах решения уравнения X − AᵀX⁻¹A = Q |
| title_fullStr | О выборе начального приближения в итерационных алгоритмах решения уравнения X − AᵀX⁻¹A = Q |
| title_full_unstemmed | О выборе начального приближения в итерационных алгоритмах решения уравнения X − AᵀX⁻¹A = Q |
| title_short | О выборе начального приближения в итерационных алгоритмах решения уравнения X − AᵀX⁻¹A = Q |
| title_sort | о выборе начального приближения в итерационных алгоритмах решения уравнения x − aᵀx⁻¹a = q |
| topic | Методы обработки информации |
| topic_facet | Методы обработки информации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/207280 |
| work_keys_str_mv | AT larinvb ovyborenačalʹnogopribliženiâviteracionnyhalgoritmahrešeniâuravneniâxatx1aq AT larinvb provibírpočatkovogonabližennâvíteracíinihalgoritmahrozvâzannârívnânnâxatx1aq AT larinvb onthechoiceoftheinitialapproximationiniterativealgorithmsofsolutionoftheequationxatx1aq |