Анализ возмущения решения задачи взвешенных наименьших квадратов

The weighed least squares problem is considered. Estimations of error of pseudosolution by perturbation of initial data of problem by condition of not saving of rank of the perturbation of matrix, etc rank(Ā) ≠ rank(A) are received.

Saved in:
Bibliographic Details
Published in:Теорія оптимальних рішень
Date:2007
Main Authors: Химич, А.Н., Николаевская, Е.А.
Format: Article
Language:Russian
Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2007
Online Access:https://nasplib.isofts.kiev.ua/handle/123456789/84989
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:Анализ возмущения решения задачи взвешенных наименьших квадратов / А.Н. Химич, Е.А. Николаевская // Теорія оптимальних рішень: Зб. наук. пр. — 2007. — № 6. — С. 12-20. — Бібліогр.: 10 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
_version_ 1859831100443983872
author Химич, А.Н.
Николаевская, Е.А.
author_facet Химич, А.Н.
Николаевская, Е.А.
citation_txt Анализ возмущения решения задачи взвешенных наименьших квадратов / А.Н. Химич, Е.А. Николаевская // Теорія оптимальних рішень: Зб. наук. пр. — 2007. — № 6. — С. 12-20. — Бібліогр.: 10 назв. — рос.
collection DSpace DC
container_title Теорія оптимальних рішень
description The weighed least squares problem is considered. Estimations of error of pseudosolution by perturbation of initial data of problem by condition of not saving of rank of the perturbation of matrix, etc rank(Ā) ≠ rank(A) are received.
first_indexed 2025-12-07T15:32:47Z
format Article
fulltext 12 Теорія оптимальних рішень. 2007, № 6 ÒÅÎÐ²ß ÎÏÒÈÌÀËÜÍÈÕ Ð²ØÅÍÜ Рассматривается задача взве- шенных наименьших квадратов. Получены оценки погрешности взвешенного нормального псевдо- решения при условии не сохране- ния ранга возмущенной матрицы, т.е. )()( ArankArank ≠ .  А.Н. Химич, Е.А. Николаевская, 2007 ÓÄÊ 519.6 À.Í. ÕÈÌÈ×, Å.À. ÍÈÊÎËÀÅÂÑÊÀß ÀÍÀËÈÇ ÂÎÇÌÓÙÅÍÈß ÐÅØÅÍÈß ÇÀÄÀ×È ÂÇÂÅØÅÍÍÛÕ ÍÀÈÌÅÍÜØÈÕ ÊÂÀÄÐÀÒΠВведение. Исследованию задач взвешенных наименьших квадратов и разработке методов их решения посвящено значительное количе- ство работ [1 – 3]. Значительно меньше работ посвящено теории возмущения решения взвешенных наименьших квадратов. В рабо- тах [4 – 6] рассматриваются оценки погреш- ности взвешенной псевдообратной матрицы и взвешенного псевдорешения в случае, ко- гда ранг матрицы исходной задачи не меня- ется при возмущении элементов матрицы. В данной работе рассматривается задача взве- шенных наименьших квадратов с положи- тельно определенными весами, при условии, что ранг исходной матрицы не сохраняется. Получены оценки погрешности взвешенного нормального псевдорешения при возмуще- нии матрицы и правой части в общем случае несовместной системы линейных алгебраи- ческих уравнений в рамках заданной модели погрешности исходных данных. 1. Предварительные сведения. Введем обозначения. Пусть nm R × множество матриц размерностью nm × . Для матрицы nm RA ×∈ обозначим T A матрицу, транспонированную к А, )(Arank – ранг матрицы А; )(Aℜ – множество образов матрицы А; ( )AN – нуле- вое подпространство А; – евклидова век- торная и согласованная с ней спектральная матричная нормы; I – единичная матрица. Для произвольной матрицы nm RA ×∈ и симметричных матриц M и N порядка АНАЛИЗ ВОЗМУЩЕНИЯ РЕШЕНИЯ ЗАДАЧИ ВЗВЕШЕННЫХ НАИМЕНЬШИХ КВАДРАТОВ Теорія оптимальних рішень. 2007, № 6 13 m и n соответственно, единственная матрица nm RX ×∈ , удовлетворяющая таким условиям: AAXA = , XXAX = , MAXMAX T =)( , NXANXA T =)( (1) называется взвешенной псевдообратной матрицей Мура – Пенроуза для матри- цы А и обозначается += MNAX . Обозначим # A взвешенную транспонированную матрицу к А, P и Q – взвешенные проекционные матрицы, т.е MANA T1# −= . (2) ++ == T MN T MN AAAAP , TT MNMN AAAAQ ++ == , ++ == T MN T MN AAAAP , TT MNMN AAAAQ ++ == , (3) где AAA ∆+= – возмущенная матрица. Пусть m Rx ∈ , n Ry ∈ . Взвешенные векторные и матричные нормы опреде- лены таким образом: xMx M 2 1 = , yNy N 2 1 = , (4) 2 1 2 1 1 max − = == ANMAxA MxMN N , nm RA ×∈ , (5) 2 1 2 1 1 max − = == AMNByB NyNM M , mn RB ×∈ . (6) Взвешенная псевдообратная матрица Мура – Пенроуза + MNA может быть представлена в виде взвешенного сингулярного разложения [7]. Пусть nm RA ×∈ и kArank =)( , M и N – положительно-определенные матри- цы порядка m и n соответственно. Тогда существуют матрицы mm RU ×∈ и nn RV ×∈ , удовлетворяющие условию IMUU T = и IVNV T =−1 , такие, что T V D UA       = 00 0 , MU D VNA T MN         = − −+ 00 01 1 , (7) где ( )kD µ...,,µ,µdiag 21= , 0µ...µµ 21 >≥≥≥ k и 2µ i – ненулевые собствен- ные значения матрицы AA # . Неотрицательные значения iµ называются взве- шенными сингулярными значениями матрицы А, причем 1µ= MN A , k NM MNA µ 1 =+ . Взвешенное SVD матрицы А обеспечивает М – ортонормальный базис век- торов и 1− N – ортонормальный базис векторов, т.е. столбцы U и V, соответст- А.Н. ХИМИЧ, Е.А. НИКОЛАЕВСКАЯ Теорія оптимальних рішень. 2007, № 6 14 венно, такие, что матрица становится диагональной если трансформирована в эти два базиса. Лемма 1 [8]. Пусть nm REA ×∈, . )(µ Ai и )(µ EAi + – взвешенные сингу- лярные значения матриц А и A соответственно. Тогда MNiiMNi EAEAEA +≤+≤− )(µ)(µ)(µ . 2. Постановка задачи. Рассмотрим задачу взвешенных наименьших квад- ратов с положительно определенными весами NCx x ∈ min , min}|{ =−= M bAxxC , (8) где nm RA ×∈ – матрица неполного ранга, m Rb ∈ . Наряду с задачей (8) рассмотрим задачу с приближенно заданными исход- ными данными NCx x ∈ min , ( ) ( ) min}|{ =∆+−∆+= M bbxAAxC , (9) где ,AAА ∆+= bbb ∆+= , xxx ∆+= . (10) Будем предполагать, что для погрешности элементов матрицы и правой части выполняются такие соотношения: .ε,ε MbMMNAMN bbAA ≤∆≤∆ (11) Существование М – взвешенного решения наименьших квадратов с мини- мальной N – нормой следует из [9]. 3. Оценка погрешности взвешенного псевдорешения. Лемма 2 [6]. Пусть nm RAA ×∈∆, , )()( ArankArank = и 1<∆ + NM MNMN AA . Тогда NM MNMN NM MN NM MN AA A A + + + ∆− ≤ 1 . Лемма 3 [6]. Пусть ++ −= MNMN AAG , AАА ∆+= и )()( ArankArank = . Тогда G может быть представлена в виде ( ) ( ).1 QIANAAANPIAAAG MNMN T MN T MNMN −+∆−+∆−= +++−++ (12) Используя представление проекционных матриц (3) можем получить сле- дующий результат. Теорема 1. Если )()( ArankArank = , то MMMM QIQQIQ )()( −=− . Доказательство. Запишем взвешенное сингулярное разложения матриц А и A : T UDVA = , T VDUA = . Из (3) и предположения о том, что А и A имеют одинаковый ранг, следует АНАЛИЗ ВОЗМУЩЕНИЯ РЕШЕНИЯ ЗАДАЧИ ВЗВЕШЕННЫХ НАИМЕНЬШИХ КВАДРАТОВ Теорія оптимальних рішень. 2007, № 6 15 MU I UQ Tk       = 00 0 , MU I UQ Tk       = 00 0 . Определим ортогональную матрицу mm RW ×∈ с подматрицами ijW соот- ношением { { km k kmk WW WW WUU T − −       == } } 2221 1211 11 . Тогда . 00 0 0 00 00 0 0 00 00 0 0 00 00 0 0 00 00 0 0 00 00 0 )( 12 12 1111 2 1 2 1 2 1 2 1 2 1 2 1 W W I W I U I UU I U MU I UMMU I UM MMU I MUU I UM MU I MUU I UQIQ km kT km Tk T km Tk T km Tk MM T km Tk MM =      =            =            = =            = =            = =            =− −− − − − − Точно также можно проверить, что 21)( WQIQ MM =− . Остается показать, что 2112 WW = . Пусть km Rx −∈ – произвольный вектор. Положим, km k x y −      = } }0 . Используя ортогональность W, имеем 2 22 2 12 222 xWxWWyyx +=== , откуда 2 22 22 12 xWxxW −= . Следовательно, 22 22 1 2 12 1 2 12 1min1max km xx sxWxWW − == −=−== , где kms − – наименьшее сингулярное число 22W . Аналогично, из 2 22 2 21 222 xWxWyWyx TTT +=== получаем А.Н. ХИМИЧ, Е.А. НИКОЛАЕВСКАЯ Теорія оптимальних рішень. 2007, № 6 16 2 2 22 1 2 21 1min1 km T x sxWW − = −=−= . Из равенства 2112 WW = следует утверждение теоремы. Введём проекционные матрицы: ++ == T MN T MN AAAAP , TT MNMN AAAAQ ++ == , ++ == T MNk T MNkk AAAAP , TT MNkMNkk AAAAQ ++ == , (13) где kArankArank k == )()( . Теорема 2. Предположим, что выполняется условие 2 1 <∆ + NM MNMN AA , kArankArank => )()( . Тогда имеет место оценка         + ∆ + − ≤ − NMN M А NMN M А АN Nk xA r h xA b h h x xx εε2 ε21 , (14) где NMMNMN AAAh ||||||||)( += – взвешенное число обусловленности матрицы А, + MNA – взвешенная псевдообратная матрица Мура – Пенроуза, символы MN и NM обозначают взвешенные матричные нормы в соответствии с (4) – (6), Axbr −= – невязка. Доказательство. Для получения оценки используем способ из [10], осно- ванный на сингулярном разложении матриц. Представим А в виде (7) T VDUА = . (15) Как известно, какова бы ни была прямоугольная матрица A размерности nm × , всегда существует разложение (7), где VU , – ортогональные матрицы, удовлетворяющие условию IUMU T = и IVNV T =−1 , D – прямоугольная матрица размерности nm × с неотрицательными элементами на диагонали, ко- торые являются взвешенными сингулярными числами матрицы A . Наряду с (15) рассмотрим разложение ,T kk VDUА = (16) где kD – прямоугольная матрица, первые к диагональных элементов которой отличны от нуля и совпадают с соответствующими элементами матрицы D , а все остальные элементы равны нулю. Взвешенное нормальное псевдорешение задачи (9) будем аппроксимировать kx взвешенным нормальным псевдорешением задачи Nk Cx x ∈ min , min}|{ =−= M k bxAxC . (17) АНАЛИЗ ВОЗМУЩЕНИЯ РЕШЕНИЯ ЗАДАЧИ ВЗВЕШЕННЫХ НАИМЕНЬШИХ КВАДРАТОВ Теорія оптимальних рішень. 2007, № 6 17 Матрица kA построена в соответствии (16) имеет ранг к, такой же, как и матрица невозмущенной задачи. Таким образом, проблема оценки погрешности псевдорешения для матриц, ранг которых изменился, сведена к случаю, когда ранги матриц одинаковы [6]. Учитывая данный факт, используем для оценки NNk xxx /− . Выражение для погрешности взвешенных псевдообратных матриц в этом случае приобрета- ет вид ( )[ ]( ) ( )[ ] ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ).)( QIAAPIAAAA QIAAPIAAAAAA QIAAPIAPQA QIAPIQAPIQIAPI QAPIQIAPQAPQIAPQAP QIQAAPIPG MNkMNkMNMNk MNkMNkMNMNkMNMNk MNkMNkMNkMNk MNkMNkMNkk MNkkMNkMNkMNkkMNkk MNMNkkkk −+−−−= =−+−−−= =−+−−−= =−−+−−−−+ +−−−−−−+= =−+−−+= ++++ ++++++ ++++ +++ +++++ ++ Используя результаты леммы 3, получаем ( ) ( ).1 QIANAAANPIAAAAAG MNkMN T MN T kMNMNkMNMNkk −+∆−−∆−=−= +++−++++ Переходя к разности, получаем ( ) ( ) ).(1 bbAbQIANxAANPIAxAxx MNkMNk T MN T kMNkk −+−−∆−+∆=− +++−+ (19) Переходя к взвешенной норме приходим ( ) ( ) ( ) ( ) .)( )( 1 1 N MNk N MNk N T MN T k N MNk N MNk MNk T MN T kMNkNk bbAbQIA NxAANPIAxAbbA bQIANxAANPIAxAxx −+−+ +∆−+∆≤−+ +−−∆−+∆=− ++ +−++ ++−+ (20) Учитывая, что rrQIbQI =−=− )()( , Аxbr −= , bAx MN += (21) и используя результаты леммы 3 можем записать ( ) ( ) ≤−=− +++ N MNkMNk N MNk rQIAAAbQIQA ,)()( MMMk NM MNkMMMk NM MNk rQIQArQIQA −=−≤ ++ (22) =−=−=− −++ 2 1 2 1 )()()( MQIAAMQIAAQIQ kMN MM kMNMMk =−−=−= −+−−+− 2 1 2 1 2 1 2 1 2 1 2 1 )()()()()( MQIMMAAAMMQIMAAM k TTT MNk T MN А.Н. ХИМИЧ, Е.А. НИКОЛАЕВСКАЯ Теорія оптимальних рішень. 2007, № 6 18 NM MNMNMNMN AAMANANMMANANM +−+−+− ∆≤∆≤∆= − 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 . Подставив полученный результат в (22) получим неравенство ( ) MNM MNMNNM MNk N kMNk rAAAbQIQA +++ ∆≤− . (23) Подставив (23) в (20), получим относительную погрешность взвешенного нор- мального псевдорешения ≤ ∆ + ∆ + +∆+∆≤ − +++ ++ N MNM MNk N MMNNM MN NM MNk NM MNMNMNNM MNk N Nk x bA x rAAA AAAA x xx     + ∆ + ∆ ∆− ≤ + + NMN M MN MN NM MNMNk MNNM MN xA b A A AA AA 2 1    ∆ + + NMN M MN MN MNNM MN xA r A A AA . (24) Оценим kk AAA −=∆ : .2 0 00 1 MNMN MN T k MNMN k MN k MN kMNk AAV D U AAAAAAAAA ∆≤∆+      = =∆+−≤∆+−=−=∆ + Кроме того условие данной теоремы 2 1 <∆ + NM MNMN AA приводит к нера- венству 1<∆ + NM MNMNk AA , что является необходимым для корректности вы- ражения (24). Учитывая это, из (24) получаем оценку (14) для погрешности нор- мального взвешенного псевдорешения. Аналогично (13) введём проекционные матрицы: ++ == T MNl T MNll AAAAP , TT MNlMNll AAAAQ ++ == , ++ == T MN T MN AAAAP , TT MNMN AAAAQ ++ == , (25) Теорема 3. Предположим, что lArankArank => )()( , 2 1 µ < ∆ l MN A . Тогда имеет место оценка АНАЛИЗ ВОЗМУЩЕНИЯ РЕШЕНИЯ ЗАДАЧИ ВЗВЕШЕННЫХ НАИМЕНЬШИХ КВАДРАТОВ Теорія оптимальних рішень. 2007, № 6 19         + ∆ + ∆− ≤ − NMN M l А NMN M A lMN l N Nl xA r xA b Ax xx µ µ εε2 µ/21 µ/µ 11 , (26) где iµ – взвешенные сингулярные числа матрицы А. Доказательство. Наряду с задачей (8) рассмотрим задачу Nl Cx x ∈ min , min}|{ =−= Ml bxAxC (27) с матрицей T ll VUDA = ранга l. Аналогично, записывая (24) для задач (9), (27), ранги матриц которых сов- падают получаем ( ) ( ),1 QIANAAANPIAAAAAG MNMNl T MNl T MNlMNMNlMN −+∆−+∆−=−= +++−++++ ( ) ( ) ).(1 bbAbQIANxAANPIAxAxx MNMN T MNl T MNl −+−−∆−−∆=− +++−+ Учитывая результаты леммы 2 и, переходя к нормам, приходим к оценке ≤ − + ∆ + +∆+∆≤ − +++ ++ N MNM MN N MMNNM MNl NM MN NM MNlMNMNNM MN N Nl x bbA x rAAA AAAA x xx , 2 1    ∆ +     + − + ∆ ∆− ≤ + + + NMN M MN MN MNNM MNl NMN M MN MN NM MNlMNl MNNM MNl xA r A A AA xA bb A A AA AA откуда следует (26), т.е. утверждение теоремы 3. Заключение. Получены строгие оценки взвешенного нормального псевдо- решения в случае, когда ранг матрицы задачи с точными исходными данными не совпадает с рангом матрицы возмущенной задачи. Оценки получены во взве- шенных матрично-векторных нормах для симметричных положительно- определенных весов. О.М. Хіміч, О.А. Ніколаєвська АНАЛІЗ ЗБУРЕННЯ РОЗВ’ЯЗКУ ЗАДАЧІ ЗВАЖЕНИХ НАЙМЕНШИХ КВАДРАТІВ Розглядається задача зважених найменших квадратів. Отримані оцінки похибки зваженого нормального псевдорозв’язку внаслідок збурення вихідних даних задачі за умовою не збере- ження рангу збуреної матриці, тобто )()( ArankArank ≠ . А.Н. ХИМИЧ, Е.А. НИКОЛАЕВСКАЯ Теорія оптимальних рішень. 2007, № 6 20 A.N. Khimich, Е.А. Nikolaevskaya ANALYSIS OF PERTURBATION SOLUTION IN WEIGHTED LEAST SQUARES PROBLEM The weighed least squares problem is considered. Estimations of error of pseudosolution by perturbation of initial data of problem by condition of not saving of rank of the perturbation of matrix, etc )()( ArankArank ≠ are received. 1. Ben Israel A., Greville T.N.E. Generalized Inverse: Theory and Applications. – New York: Willey, 1974. – 436 p. 2. Голуб Дж., Ван Лоун. Матричные вычисления. – М.: Мир, 1999. – 549 с. 3. Химич А.Н. Оценки возмущений для решения задачи наименьших квадратов // Ки- бернетика и системный анализ. – 1996. – № 3. – С. 142 – 145. 4. Chen G.L. Minimum property of weighted condition number in matrix perturbation prob- lems // J. East China Normal Univ. – 1996. – N 1 – P. 1 – 7. 5. Wei Y. Perturbation bound of singular linear systems // Applied Math. Computation. – 1999. – N 105. – P. 211 – 220. 6. Химич А.Н., Николаевская Е.А. Оценка погрешности решения задачи взвешенных наименьших квадратов // Компьютерная математика. – Киев: Ин – ут кибернетики им. В.М. Глушкова НАН Украины, 2006. – № 3. – С. 36 – 45. 7. Van Loan C.F. Generalizing the singular value decomposition // SIAM J. Numerical Analysis. – 1976. – N 13. – P. 76 – 83. 8. Wei Y., Wang D. Condition numbers and perturbation of weighted Moore-Penrose inverse and weighted least squares problem // Applied Math. Computation. – 2003. – N 145. – P. 45 – 58. 9. Сергиенко И.В., Галба Е.Ф., Дейнека В.С. Предельные представления взвешенных псевдообратных матриц с положительно-определенными весами и регуляризация задач // Кибернетика и системный анализ. – 2003. – № 6. – С. 46 – 65. 10. Химич А.Н. Оценки возмущений для решения задачи наименьших квадратов // Ки- бернетика и системный анализ. – 1996. – № 3. – С. 142 – 145. Получено 23.04.2007
id nasplib_isofts_kiev_ua-123456789-84989
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn XXXX-0013
language Russian
last_indexed 2025-12-07T15:32:47Z
publishDate 2007
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
record_format dspace
spelling Химич, А.Н.
Николаевская, Е.А.
2015-07-18T06:04:51Z
2015-07-18T06:04:51Z
2007
Анализ возмущения решения задачи взвешенных наименьших квадратов / А.Н. Химич, Е.А. Николаевская // Теорія оптимальних рішень: Зб. наук. пр. — 2007. — № 6. — С. 12-20. — Бібліогр.: 10 назв. — рос.
XXXX-0013
https://nasplib.isofts.kiev.ua/handle/123456789/84989
519.6
The weighed least squares problem is considered. Estimations of error of pseudosolution by perturbation of initial data of problem by condition of not saving of rank of the perturbation of matrix, etc rank(Ā) ≠ rank(A) are received.
ru
Інститут кібернетики ім. В.М. Глушкова НАН України
Теорія оптимальних рішень
Анализ возмущения решения задачи взвешенных наименьших квадратов
Analysis of perturbation solution in weighted least squares problem
Article
published earlier
spellingShingle Анализ возмущения решения задачи взвешенных наименьших квадратов
Химич, А.Н.
Николаевская, Е.А.
title Анализ возмущения решения задачи взвешенных наименьших квадратов
title_alt Analysis of perturbation solution in weighted least squares problem
title_full Анализ возмущения решения задачи взвешенных наименьших квадратов
title_fullStr Анализ возмущения решения задачи взвешенных наименьших квадратов
title_full_unstemmed Анализ возмущения решения задачи взвешенных наименьших квадратов
title_short Анализ возмущения решения задачи взвешенных наименьших квадратов
title_sort анализ возмущения решения задачи взвешенных наименьших квадратов
url https://nasplib.isofts.kiev.ua/handle/123456789/84989
work_keys_str_mv AT himičan analizvozmuŝeniârešeniâzadačivzvešennyhnaimenʹšihkvadratov
AT nikolaevskaâea analizvozmuŝeniârešeniâzadačivzvešennyhnaimenʹšihkvadratov
AT himičan analysisofperturbationsolutioninweightedleastsquaresproblem
AT nikolaevskaâea analysisofperturbationsolutioninweightedleastsquaresproblem