Решение задачи взвешенных наименьших квадратов с симметричной положительно полуопределенной матрицей
Рассматривается алгоритм трехэтапной регуляризации для задачи взвешенных наименьших квадратов с симметричной положительно полуопределенной матрицей. Получены оценки погрешности метода трехступенчатой регуляризации для нахождения взвешенного нормального псевдорешения задачи WLS. Представлено выражени...
Saved in:
| Date: | 2009 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Subjects: | |
| Online Access: | http://dspace.nbuv.gov.ua/handle/123456789/6257 |
| 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: | Решение задачи взвешен-ных наименьших квадратов с симметричной положительно полуопределенной матрицей / Е.А. Николаевская, А.Н. Химич, М.Ф. Яковлев // Компьютерная математика. — 2009. — № 1. — С. 60-66. — Бібліогр.: 7 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-6257 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-62572010-02-23T12:01:11Z Решение задачи взвешенных наименьших квадратов с симметричной положительно полуопределенной матрицей Николаевская, Е.А. Химич, А.Н. Яковлев, М.Ф. Системный анализ Рассматривается алгоритм трехэтапной регуляризации для задачи взвешенных наименьших квадратов с симметричной положительно полуопределенной матрицей. Получены оценки погрешности метода трехступенчатой регуляризации для нахождения взвешенного нормального псевдорешения задачи WLS. Представлено выражения для параметра регуляризации, гарантирующего заданную точность приближения к взвешенному нормальному псевдорешению. Розглядається алгоритм триетапної регуляризації для задачі зважених найменших квадратів із симетричною додатно напіввизначеною матрицею. Отримано оцінки похибки методу триетапної регуляризації для знаходження зваженого нормального псевдорозв’язку задачі WLS. Представлено вирази для параметру регуляризації, які гарантують задану точність зваженого нормального псевдорозв’язку. The algorithm of three-stage regularization for weighed least-squares problem with a symmetric positively semi-definite matrix is considered. The error estimations of the three-stage regularization method for finding the weighed normal pseudosolution of WLS problem are obtained. Expressions for the parameter of regularization, which guarantee the prescribed accuracy of the weighed normal pseudosolution, are presented. 2009 Article Решение задачи взвешен-ных наименьших квадратов с симметричной положительно полуопределенной матрицей / Е.А. Николаевская, А.Н. Химич, М.Ф. Яковлев // Компьютерная математика. — 2009. — № 1. — С. 60-66. — Бібліогр.: 7 назв. — рос. ХХХХ-0003 http://dspace.nbuv.gov.ua/handle/123456789/6257 519.6 ru Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Системный анализ Системный анализ |
| spellingShingle |
Системный анализ Системный анализ Николаевская, Е.А. Химич, А.Н. Яковлев, М.Ф. Решение задачи взвешенных наименьших квадратов с симметричной положительно полуопределенной матрицей |
| description |
Рассматривается алгоритм трехэтапной регуляризации для задачи взвешенных наименьших квадратов с симметричной положительно полуопределенной матрицей. Получены оценки погрешности метода трехступенчатой регуляризации для нахождения взвешенного нормального псевдорешения задачи WLS. Представлено выражения для параметра регуляризации, гарантирующего заданную точность приближения к взвешенному нормальному псевдорешению. |
| format |
Article |
| author |
Николаевская, Е.А. Химич, А.Н. Яковлев, М.Ф. |
| author_facet |
Николаевская, Е.А. Химич, А.Н. Яковлев, М.Ф. |
| author_sort |
Николаевская, Е.А. |
| title |
Решение задачи взвешенных наименьших квадратов с симметричной положительно полуопределенной матрицей |
| title_short |
Решение задачи взвешенных наименьших квадратов с симметричной положительно полуопределенной матрицей |
| title_full |
Решение задачи взвешенных наименьших квадратов с симметричной положительно полуопределенной матрицей |
| title_fullStr |
Решение задачи взвешенных наименьших квадратов с симметричной положительно полуопределенной матрицей |
| title_full_unstemmed |
Решение задачи взвешенных наименьших квадратов с симметричной положительно полуопределенной матрицей |
| title_sort |
решение задачи взвешенных наименьших квадратов с симметричной положительно полуопределенной матрицей |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2009 |
| topic_facet |
Системный анализ |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/6257 |
| citation_txt |
Решение задачи взвешен-ных наименьших квадратов с симметричной положительно полуопределенной матрицей / Е.А. Николаевская, А.Н. Химич, М.Ф. Яковлев // Компьютерная математика. — 2009. — № 1. — С. 60-66. — Бібліогр.: 7 назв. — рос. |
| work_keys_str_mv |
AT nikolaevskaâea rešeniezadačivzvešennyhnaimenʹšihkvadratovssimmetričnojpoložitelʹnopoluopredelennojmatricej AT himičan rešeniezadačivzvešennyhnaimenʹšihkvadratovssimmetričnojpoložitelʹnopoluopredelennojmatricej AT âkovlevmf rešeniezadačivzvešennyhnaimenʹšihkvadratovssimmetričnojpoložitelʹnopoluopredelennojmatricej |
| first_indexed |
2025-07-02T09:12:33Z |
| last_indexed |
2025-07-02T09:12:33Z |
| _version_ |
1836525869782269952 |
| fulltext |
60 Компьютерная математика. 2009, № 1
Ñèñòåìíûé àíàëèç
Рассматривается алгоритм трех-
этапной регуляризации для задачи
взвешенных наименьших квадра-
тов с симметричной положи-
тельно полуопределенной матри-
цей. Получены оценки погрешнос-
ти метода трехступенчатой ре-
гуляризации для нахождения взве-
шенного нормального псевдореше-
ния задачи WLS. Представлено вы-
ражения для параметра регу-
ляризации, гарантирующего задан-
ную точность приближения к
взвешенному нормальному псевдо-
решению.
© Е.А. Николаевская,
А.Н. Химич, М.Ф. Яковлев,
2009
ÓÄÊ 519.6
Å.À. ÍÈÊÎËÀÅÂÑÊÀß, À.Í. ÕÈÌÈ×, Ì.Ô. ßÊÎÂËÅÂ
ÐÅØÅÍÈÅ ÇÀÄÀ×È ÂÇÂÅØÅÍÍÛÕ
ÍÀÈÌÅÍÜØÈÕ ÊÂÀÄÐÀÒÎÂ
Ñ ÑÈÌÌÅÒÐÈ×ÍÎÉ ÏÎËÎÆÈÒÅËÜÍÎ
ÏÎËÓÎÏÐÅÄÅËÅÍÍÎÉ ÌÀÒÐÈÖÅÉ
Введение. Много прикладных задач сводится
к задачам наименьших квадратов и взвешен-
ных наименьших квадратов [1]. Значительно
меньше работ посвящено теории возмущений
решения задачи взвешенных наименьших
квадратов.
В работе [2] предложен алгоритм двух-
этапной регуляризации решения СЛАУ. Для
получения нормального псевдорешения с
заданной точностью по этому алгоритму ре-
шена проблема выбора параметра регуляри-
зации [3]. Алгоритм трехэтапной регуляри-
зации используется в [4] для исследования и
решения первой основной задачи теории уп-
ругости.
В данной работе рассматривается метод
трёхэтапной регуляризации для задачи взве-
шенных наименьших квадратов.
1. Постановка задачи. Рассмотрим задачу
взвешенных наименьших квадратов с поло-
жительно определенными весами M и 1−M
1min −
∈ MSx
x , { | min},MS x Ax b= − = (1)
где mmRA ×∈ – симметричная положительно
полуопределенная матрица (A=AT, A ≥ 0) ран-
га k, mmRM ×∈ – симметричная положи-
тельно определенная матрица весов, .mb R∈
Рассмотрим возмущенную задачу
( ){ }1min , | =min ,
M Mx S
x S x Ax b b−
∈
= − +Δ (2)
РЕШЕНИЕ ЗАДАЧИ ВЗВЕШЕННЫХ НАИМЕНЬШИХ КВАДРАТОВ С СИММЕТРИЧНОЙ…
Компьютерная математика. 2009, № 1 61
где
bbb Δ+= , xxx Δ+= . (3)
Положим, что для погрешности элементов правой части выполняется сле-
дующее соотношение:
.bM Mb bΔ ≤ ε (4)
2. Алгоритм трёхэтапной схемы регуляризации для решения задачи
взвешенных наименьших квадратов. Представим норму невязки в виде
dCybMxMAMMbAx M −=−=−
−
2
1
2
1
2
1
2
1
,
где 2
1
2
1
AMMC = , bMd 2
1
= , xMy 2
1
−
= .
Таким образом приходим к задаче
y
Sy∈
min , min}|{ =−= dCyxS .
Пусть имеем в общем случае несовместную систему линейных алгебраиче-
ских уравнений
dCy ≅ (5)
и возмущенную задачу
dyC ≅ , (6)
где bMd 2
1
= , xMy 2
1
−
= . Обозначим CS Imˆ = , CS ker~
= – соответственно
образ и ядро матрицы С. Тогда любой вектор mRx∈ можно представить в виде
xxx ~ˆ += , Sx ˆˆ∈ , Sx ~~∈ .
Учитывая введенные обозначения для задач (5), (6) можна записать
dyC ˆˆ = , (7)
dyC ˆˆ = , (8)
где ŷ , ŷ – нормальные псевдорешения задач (5), (6) соответственно.
Е.А. НИКОЛАЕВСКАЯ, А.Н. ХИМИЧ, М.Ф. ЯКОВЛЕВ
Компьютерная математика. 2009, № 1 62
Рассмотрим следующий алгоритм решения задачи. При произвольно выбран-
ном параметре α (например, α = 0,01) выполняются следующие шаги алгоритма:
( )C E z d+ α = , (9)
( )C E u Cz+ α = , (10)
i
i
H u
uu
max
= , (11)
( ) HC E w u+ α = , (12)
max i
i
wμ = , (13)
1
1
2 bC⎛ ⎞ε
α ≤ − ε⎜ ⎟μ⎝ ⎠
. (14)
Решение u является приближением к нормальному псевдорешению задачи
(5). После нахождения u, проверяется достигнута ли точность ε . Если точность
не достигнута, выполняются этапы (11)–(14) для определения значения парамет-
ра 1α , обеспечивающего достижение заданной точности. Данные четыре этапа
алгоритма реализуют второй шаг итерационного степенного метода определе-
ния максимального по модулю собственного значения матрицы ( ) 1C E −+ α , то μ
в (13) – приближение к собственному значению ( ) 1
k
−λ + α [5].
После нахождения приближения к псевдорешению проверяется выполнение
неравенства
( )12 bMMA −α + ε μ ≤ ε . (15)
Если неравенство выполняется, то необходимая точность ε достигнута при
заданном произвольном α. Если неравенство не выполняется, то, как вышеопи-
сано, по формуле (14) определяется новое значение α1, которое должно обеспе-
чить необходимую точность, и по формулам (9), (10) вычисляется приближение
к взвешенному нормальному псевдорешению.
В работе [2] установлена сходимость u к нормальному псевдорешению за-
дачи (5) при 0α→ .
РЕШЕНИЕ ЗАДАЧИ ВЗВЕШЕННЫХ НАИМЕНЬШИХ КВАДРАТОВ С СИММЕТРИЧНОЙ…
Компьютерная математика. 2009, № 1 63
Заметим, что система (9) эквивалентна системе двух уравнений:
( ) ˆ ˆ ˆˆC E z d d d+ α = = + Δ , (16)
z d d dα = = + Δ ,
а уравнение (10) в силу zCzCzCCz ˆ~ˆ =+= можно записать так
( ) ˆC E u Cz+ α = . (17)
Приближение к взвешенному нормальному псевдорешению задачи (1) вы-
числяется по формуле
uMv 2
1
= .
Оценим погрешность взвешенного нормального псевдорешения задачи (1).
Лемма 1. Для погрешности взвешенного нормального псевдорешения зада-
чи (1) имеет место оценка
M
M
MMMMMM
M
M
b
b
AA
x
xx
ˆ
ˆ
ˆ
ˆˆ
111
1
1 Δ
≤
−
−−−
−
− + ,
где +
−1MM
A – взвешенная псевдообратная матрица Мура – Пенроуза, bbb ˆˆˆ −=Δ .
Задачу (2) будем считать хорошо обусловленной, если свойства задачи и
погрешность исходных данных позволяют получить заданную точность
ε решения, т. е.
1 1 1
ˆ
ˆ
M
MM MM MM
M
b
A A
b
− − −
+
Δ
≤ ε . (18)
Теорема. Для погрешности приближения к взвешенному нормальному псев-
дорешению имеет место следующая оценка:
1
1
ˆˆ
1 1
ˆˆ
m mM M
k k k kM M
bv x
x b
−
−
Δ− ⎛ ⎞ ⎛ ⎞μ μα α
≤ + + +⎜ ⎟ ⎜ ⎟μ + α μ + α μ + α μ + α⎝ ⎠ ⎝ ⎠
, (19)
Е.А. НИКОЛАЕВСКАЯ, А.Н. ХИМИЧ, М.Ф. ЯКОВЛЕВ
Компьютерная математика. 2009, № 1 64
где kμ – наименьшее отличное от нуля собственное значение матрицы
2
1
2
1
AMMC = (или его оценка снизу), mμ – её максимальное собственное зна-
чение (или его оценка сверху).
Доказательство леммы и теоремы легко получить из [3], используя обозна-
чения 2
1
2
1
AMMC = , bMd ˆˆ 2
1
= , xMy ˆˆ 2
1
−
= , vMu 2
1
−
= и взвешенные вектор-
ные нормы [6]:
1ˆˆˆ 2
1
2
1
−−=−=−
−−
MxvxMvMyu ,
M
bbMd ˆˆˆ 2
1
== .
Для достижения необходимой точности параметр α выберем из условия
1
1
ˆ
ˆ
M
M
v x
x
−
−
−
≤ ε .
Тогда с точностью до малых второго порядка можно получить оценку
( )
1 (1 2 ) (1 2 )
k k m b
k m b
μ εμ − μ ε
α ≤
− ε + μ − ε + μ + ε
, (20)
где
ˆ
ˆ
M
b
M
b
b
Δ
ε = .
В случае точно заданных исходных данных оценка (13) преобразуется к виду
1
1
ˆ
1 ,
ˆ
mM
k kM
v x
x
−
−
− ⎛ ⎞α μ
≤ +⎜ ⎟μ + α μ + α⎝ ⎠
а для параметра α справедлива оценка
РЕШЕНИЕ ЗАДАЧИ ВЗВЕШЕННЫХ НАИМЕНЬШИХ КВАДРАТОВ С СИММЕТРИЧНОЙ…
Компьютерная математика. 2009, № 1 65
2
1 (1 2 )
k
k m
μ ε
α ≤
− ε + μ − ε + μ
, (21)
которая получена с точностью до малых второго порядка.
Таким образом, получено значение параметра α, при использовании двух
шагов вышеприведенного алгоритма.
Для получения достоверного решения системы (5) необходимо, чтобы ис-
ходные данные удовлетворяли условию (18) (задача хорошо обусловлена).
Выбор параметра α, который удовлетворяет (21), будет гарантировать заданную
точность приближения к взвешенному нормальному псевдорешению.
Заключение. Трехэтапная схема регуляризации является альтернативой ме-
тоду, основанном на алгоритме взвешенного сингулярного разложения [7]. Пре-
имуществом трехэтапной схемы регуляризации – меньшее количество арифме-
тических операций.
Достоинства алгоритма трехэтапной регуляризации усиливаются для мат-
риц специальной структуры, например, ленточных. При использовании алго-
ритма взвешенного сингулярного разложения не удается существенно умень-
шить количество арифметических операций учитывая необходимость вычисле-
ния всех сингулярных векторов.
О.А. Ніколаєвська, О.М. Хіміч, М.Ф. Яковлев
РОЗВ'ЯЗОК ЗАДАЧІ ЗВАЖЕНИХ НАЙМЕНШИХ КВАДРАТІВ
ІЗ СИМЕТРИЧНОЮ ДОДАТНО НАПІВВИЗНАЧЕНОЮ МАТРИЦЕЮ
Розглядається алгоритм триетапної регуляризації для задачі зважених найменших квадратів
із симетричною додатно напіввизначеною матрицею. Отримано оцінки похибки методу
триетапної регуляризації для знаходження зваженого нормального псевдорозв’язку задачі
WLS. Представлено вирази для параметру регуляризації, які гарантують задану точність
зваженого нормального псевдорозв’язку.
E.A. Nikolevskaya, A.N. Khimich, M.F. Yakovlev
SOLUTION TO THE WEIGHTED LEAST-SQUARES PROBLEM WITH A SYMMETRIC
POSITIVELY SEMI-DEFINITE MATRIX
The algorithm of three-stage regularization for weighed least-squares problem with a symmetric
positively semi-definite matrix is considered. The error estimations of the three-stage regularization
method for finding the weighed normal pseudosolution of WLS problem are obtained. Expressions
for the parameter of regularization, which guarantee the prescribed accuracy of the weighed normal
pseudosolution, are presented.
Е.А. НИКОЛАЕВСКАЯ, А.Н. ХИМИЧ, М.Ф. ЯКОВЛЕВ
Компьютерная математика. 2009, № 1 66
1. Ben Israel A., Greville T.N.E. Generalized Inverse: Theory and Applications. – New
York: Springer Verlag, 2003. – 400 p.
2. Морозов В.А. Методы регуляризации неустойчивых задач. – М.: Изд-во Московско-
го ун-та, 1987. – 217 с.
3. Химич А.Н., Яковлев М.Ф. О решении систем с матрицами неполного ранга // Ком-
пьютерная математика. – 2003. – № 1. – C. 1–15.
4. Попов А.В., Химич А.Н. Исследование и решение первой основной задачи теории
упругости // Компьютерная математика. – 2003. – № 2. – С. 105–114.
5. Уилкинсон Дж., Райнш К. Справочник алгоритмов на языке АЛГОЛ. Линейная ал-
гебра. – М.: Машиностроение, 1976. – 389 с.
6. Химич А.Н., Николаевская Е.А. Анализ достоверности компьютерных решений сис-
тем линейных алгебраических уравнений с приближенно заданными исходными
данными // Кибернетика и системный анализ. – 2008. – № 6. – С. 83–95.
7. Химич А.Н., Николаевская Е.А. Решение задачи взвешенных наименьших квадратов
с приближенно заданными исходными данными // Теорія оптимальних рішень. –
2008. – № 7. – C. 132–139.
Получено 15.12.2008
Oá àâòîðàõ:
Николаевская Елена Анатольевна,
младший научный сотрудник
Института кибернетики имени В.М. Глушкова НАН Украины,
e-mail elena_nea@ukr.net
Химич Александр Николаевич,
доктор физико-математических наук, заведующий отделом
Института кибернетики имени В.М. Глушкова НАН Украины,
e-mail : dept150@insyg.kiev.ua
Яковлев Михаил Федорович,
кандидат физико-математических наук, старший научный сотрудник
Института кибернетики имени В.М. Глушкова НАН Украины.
|