Про ефективний метод розв'язування некоректних задач з розрідженими матрицями

Для знаходження наближень з наперед заданою точністю до нормального узагальненого або до зваженого нормального узагальненого розв’язків системи лінійних алгебраїчних рівнянь з додатно напіввизначеною симетричною розрідженою матрицею. Запропоновано метод триетапної регуляризації. Для нахождения прибл...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Veröffentlicht in:	Теорія оптимальних рішень
Datum:	2013
1. Verfasser:	Попов, О.В.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2013
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/85045
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:	Про ефективний метод розв'язування некоректних задач з розрідженими матрицями / О.В. Попов // Теорія оптимальних рішень: Зб. наук. пр. — 2013. — № 12. — С. 77-81. — Бібліогр.: 4 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-85045
record_format	dspace
spelling	Попов, О.В. 2015-07-18T16:45:06Z 2015-07-18T16:45:06Z 2013 Про ефективний метод розв'язування некоректних задач з розрідженими матрицями / О.В. Попов // Теорія оптимальних рішень: Зб. наук. пр. — 2013. — № 12. — С. 77-81. — Бібліогр.: 4 назв. — укр. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/85045 519.6 Для знаходження наближень з наперед заданою точністю до нормального узагальненого або до зваженого нормального узагальненого розв’язків системи лінійних алгебраїчних рівнянь з додатно напіввизначеною симетричною розрідженою матрицею. Запропоновано метод триетапної регуляризації. Для нахождения приближений с наперед заданной точностью к нормальному обобщенному или к взвешенному нормального обобщенному решениям системы линейных алгебраических уравнений с положительно полуопределенной разреженной симметричной матрицей предложен метод трехэтапной регуляризации. A three-staged regularization method is proposed for the finding within a priori given accuracy of approximations either to normal generalized or weighted normal generalized solutions of linear algebraic system with positive semi-defined sparse symmetric matrix. uk Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Про ефективний метод розв'язування некоректних задач з розрідженими матрицями Об эффективном методе решения некорректных задач с разреженными матрицами On the efficient method for the solving of incorrect problems with sparse matrices Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Про ефективний метод розв'язування некоректних задач з розрідженими матрицями
spellingShingle	Про ефективний метод розв'язування некоректних задач з розрідженими матрицями Попов, О.В.
title_short	Про ефективний метод розв'язування некоректних задач з розрідженими матрицями
title_full	Про ефективний метод розв'язування некоректних задач з розрідженими матрицями
title_fullStr	Про ефективний метод розв'язування некоректних задач з розрідженими матрицями
title_full_unstemmed	Про ефективний метод розв'язування некоректних задач з розрідженими матрицями
title_sort	про ефективний метод розв'язування некоректних задач з розрідженими матрицями
author	Попов, О.В.
author_facet	Попов, О.В.
publishDate	2013
language	Ukrainian
container_title	Теорія оптимальних рішень
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
format	Article
title_alt	Об эффективном методе решения некорректных задач с разреженными матрицами On the efficient method for the solving of incorrect problems with sparse matrices
description	Для знаходження наближень з наперед заданою точністю до нормального узагальненого або до зваженого нормального узагальненого розв’язків системи лінійних алгебраїчних рівнянь з додатно напіввизначеною симетричною розрідженою матрицею. Запропоновано метод триетапної регуляризації. Для нахождения приближений с наперед заданной точностью к нормальному обобщенному или к взвешенному нормального обобщенному решениям системы линейных алгебраических уравнений с положительно полуопределенной разреженной симметричной матрицей предложен метод трехэтапной регуляризации. A three-staged regularization method is proposed for the finding within a priori given accuracy of approximations either to normal generalized or weighted normal generalized solutions of linear algebraic system with positive semi-defined sparse symmetric matrix.
issn	XXXX-0013
url	https://nasplib.isofts.kiev.ua/handle/123456789/85045
citation_txt	Про ефективний метод розв'язування некоректних задач з розрідженими матрицями / О.В. Попов // Теорія оптимальних рішень: Зб. наук. пр. — 2013. — № 12. — С. 77-81. — Бібліогр.: 4 назв. — укр.
work_keys_str_mv	AT popovov proefektivniimetodrozvâzuvannânekorektnihzadačzrozrídženimimatricâmi AT popovov obéffektivnommetoderešeniânekorrektnyhzadačsrazrežennymimatricami AT popovov ontheefficientmethodforthesolvingofincorrectproblemswithsparsematrices
first_indexed	2025-11-26T17:31:19Z
last_indexed	2025-11-26T17:31:19Z
_version_	1850765567944818688
fulltext	Теорія оптимальних рішень. 2013 77 ÒÅÎÐ²ß ÎÏÒÈÌÀËÜÍÈÕ Ð²ØÅÍÜ Для знаходження наближень з наперед заданою точністю до нормального узагальненого або до зваженого нормального узагаль- неного розв’язків системи лінійних алгебраїчних рівнянь з додатно напіввизначеною симетричною роз- рідженою матрицею. Запропоно- вано метод триетапної регуляри- зації.  О.В. Попов, 2013 ÓÄÊ 519.6 Î.Â. ÏÎÏÎÂ ÏÐÎ ÅÔÅÊÒÈÂÍÈÉ ÌÅÒÎÄ ÐÎÇÂ’ßÇÓÂÀÍÍß ÍÅÊÎÐÅÊÒÍÈÕ ÇÀÄÀ× Ç ÐÎÇÐ²ÄÆÅÍÈÌÈ ÌÀÒÐÈÖßÌÈ Вступ. Математичне моделювання та пов’я- заний з ним комп’ютерний експеримент нині є одним з основних засобів вивчення різно- манітних явищ природи, процесів у сус- пільстві, економіці, науці, техніці тощо. При математичному моделюванні в різних галу- зях часто виникають розрахункові (дискретні або напівдискретні) задачі з надвеликою кількістю рівнянь, яка може перевищувати 10 7 , причому дані цих задач мають розрі- джену структуру. У багатьох випадках роз- в’язування систем лінійних алгебраїчних рівнянь (СЛАР) складає основу дослідження математичної моделі. Причому, як правило, розв'язування СЛАР або пов’язаних із СЛАР задач займає значну частину (50 % і більше) часу розв'язування всієї задачі загалом. Наприклад, СЛАР виникають при дискрети- зації крайових задач проекційно-різницевим методом (скінченних різниць, скінченних елементів). Матриці таких СЛАР мають розріджену структуру, тобто кількість ненульових еле- ментів матриці складає kn, де n – порядок матриці, а k << n, а сама структура визнача- ється нумерацією невідомих задачі. У деяких випадках матриця СЛАР виявля- ється напіввизначеною. Такі СЛАР виника- ють, наприклад, у результаті дискретизації при розрахунку міцності незакріплених кон- струкцій. СЛАР з напіввизначеною матри- цею мають єдиний розв’язок на підпросторі – нормальний узагальнений розв’язок або О.В. ПОПОВ 78 Теорія оптимальних рішень. 2013 нормальний псевдорозв’язок, який можна знайти методом найменших квадратів або зважених найменших квадратів, який дозволяє врахувати «вагу» окремих невідомих задачі. Через те, що дані прикладних моделей задаються з похибками, можуть змінитися властивості СЛАР, що розв’язуються. Наприклад, додатно напіввизначена матриця може стати додатно визначеною або навпаки знако- невизначеною. Тому є актуальним отримання достовірного нормального уза- гальненого розв’язку такої СЛАР. В роботах [1, 2] запропоновано метод триетапної регуляризації для отри- мання наближення до нормального узагальненого розв’язку СЛАР з наперед заданою точністю. Цей метод ефективно реалізується на сучасних високопроду- ктивних комп’ютерах, у тому числі з паралельною організацією обчислень. У даній роботі цей метод поширюється на знаходження зваженого нормального псевдорозв’язку СЛАР. Постановки задач. Розглянемо систему лінійних алгебраїчних рівнянь (СЛАР) з розрідженою симетричною додатно напіввизначеною матрицею A = A T , A ≥ 0 порядку n і рангу k Ax = b. (1) Такі СЛАР виникають, зокрема, при розв’язуванні методом скінченних елементів задач розрахунку міцності конструкцій, якщо на границі задано напруги (сили). Задача (1) має розв’язок на підпросторі – узагальнений розв’язок у значенні найменших квадратів або псевдорозв’язок – будь-який вектор х0, для якого евк- лідова норма нев'язки досягає найменшого значення: 0min . x Ax b Ax b− = − (2) Розв’язок хн, який має найменшу евклідову норму н x xx = 0 min (3) є єдиним і називається нормальним узагальненим розв’язком або нормальним псевдорозв’язком. Поряд з задачею (2), (3) доцільно розглянути задачу зважених найменших квадратів з симетричними додатно визначеними матрицями-вагами M = M T та M -1 . У цьому випадку зваженим узагальненим розв’язком у значенні найменших квадратів або зваженим псевдорозв’язком називається будь-який вектор 0 ,x для якого зважена норма нев'язки досягає найменшого значення: 11 0min −− −=− MMx bAxbAx , (4) де ║y║K = (y T Ky) ½ . Розглядатимемо випадок, коли M – розріджена матриця, множина ненульових елементів (структура) якої збігається з множиною нену- льових елементів матриці A або є її підмножиною. А розв’язок хн, який має найменшу зважену норму ПРО ЕФЕКТИВНІ МЕТОДИ РОЗВ’ЯЗУВАННЯ НЕКОРЕКТНИХ ЗАДАЧ З РОЗРІДЖЕНИМИ … Теорія оптимальних рішень. 2013 79 MxMн xx 0 min= (5) називається зваженим нормальним узагальненим розв’язком або зваженим нор- мальним псевдорозв’язком. Розглянемо також збурену СЛАР ,Ax b= (6) де bbb ∆+= та ║∆b║ ≤ εb║b║ або 1 1bM M b b− −∆ ≤ ε . (7) Розв’язування задач. Задачу зважених найменших квадратів (4), (5) у ви- падку симетричної додатно визначеної матриці M можна досить просто звести до задачі (2), (3) з іншими матрицею та правою частиною. Наприклад, наступ- ним чином. Враховуючи, що M симетрична додатно визначена матриця, існує її розви- нення MLL T MM = . Виходячи з того, що dCybLxLALLbAx M T M T MM M −≡−=− −−− − 11 1 , yxLx T MM ≡= , де T MM ALLC −−= 1 , bLd M 1−= , xLy T M= , замість задачі (4), (5) отримаємо задачу найменших квадратів виду (2), (3) з симетричною напіввизначеною матрицею C та правою частиною d. Але матриця C зберігає розріджену структуру матриці A тільки за умови, що матриця M – діагональна. В інших випадках наповненість матриці C збільшується і в загальному випадку її слід вважати щільною. Зауважимо також, що для збуреної СЛАР (6), (7), позначаючи bLd M 1−= , маємо задачу dCy = , b d d d− ≤ ε . (8) Нормальний узагальнений розв’язок задачі (1), тобто розв’язок задачі най- менших квадратів (2), (3) з симетричною напіввизначеною матрицею можна об- числити, використовуючи сингулярне розвинення матриці, яке для симетричних матриць збігається з розвиненням за власними векторами A = UΛU T (Λ – діаго- нальна матриця власних значень). Проте матриця власних векторів U є щільною матрицею загального вигляду, яка не зберігає розріджену структуру (наприклад, стрічкову) матриці СЛАР A. Тому для таких випадків, як правило, використову- ються різні методи регуляризації. Для розв'язування задачі (2), (3) в [3] запропоновано метод двоетапної регу- ляризації. В роботі [1] запропоновано метод триетапної регуляризації, в якому розв’язано проблему вибору параметра регуляризації, який дозволяє обчислити наближення до узагальненого розв'язку з наперед заданою точністю. Наближення до нормального псевдорозв’язку u отримуємо, послідовно розв’язуючи дві СЛАР (при довільно вибраному параметрі α > 0) (A + αI) z = bk, (A + αI) u = Az; (9) О.В. ПОПОВ 80 Теорія оптимальних рішень. 2013 Точність отриманого наближення оцінюється величиною [1] µ)εα2(δ/ bAxux +=≤− , (10) де µ – максимальне власне значення матриці 1( ) .A I −+ α Для обчислення набли- ження до µ виконуємо один крок степеневого методу, тобто розв’язуємо СЛАР 1 max)( −       =+ i i uuwIA α та знаходимо i i wmaxµ ≈ . Якщо виконується нерівність δ ≤ ε, то необхідна точність ε досягнута при вибраному значенні α. Якщо нерівність не виконується, то за формулою 1 1 2 bA  ε α ≤ − ε  µ  визначається нове значення зсуву і розв'язуються системи (9) з матрицею A + α1I – обчислюється нове наближення u, яке забезпечує необхідну точність ε нормального псевдорозв’язку. Даний метод можна використати для обчислення наближення до нормаль- ного узагальненого розв’язку задачі (8), за яким можна знайти наближення до зваженого нормального псевдорозв’язку задачі (6), (7). Але такий підхід вимагає обчислення в явному вигляді матриці C, яка може втратити розріджену структу- ру, та вектора d . Тому доцільно так модифікувати метод триетапної регуляриза- ції, щоб оперувати з матрицями A, M та вектором b і уникнути цих обчислень. Тоді при довільно вибраному параметрі α0 > 0, наприклад, α0 = 0,01, набли- ження до зваженого нормального псевдорозв’язку u отримуємо, послідовно розв’язуючи дві СЛАР (A + αM) z = bk, (A + αM) u = Az. (11) Далі розв’язуємо СЛАР ( ) 1 ( ) max i i A M w Mu u − + α = та обчислюємо µ max i i w≈ – наближення до максимального власного значення узагальненої алгебраїчної проблеми Mv = µ(A + αM)v. По суті виконується один крок варіанту степеневого методу для узагальненої проблеми. Аналогічно [1] можна отримати оцінку виду (10) точності наближеного зваженого нормального псевдорозв’язку µ)εα2(δ/ 1 b T MMMM ALLxux −−+=≤− . Тепер, якщо виконується нерівність δ ≤ ε, то необхідна точність ε досягнута при вибраному значенні α. Якщо нерівність не виконується, то за формулою 1 1 0,5(ε / µ )T M M b L AL − −α ≤ − ε визначається нове значення зсуву та розв'язуються системи (11) з матрицею A + α1M – обчислюється нове наближення u, яке забез- печує необхідну точність ε зваженого нормального псевдорозв’язку. ПРО ЕФЕКТИВНІ МЕТОДИ РОЗВ’ЯЗУВАННЯ НЕКОРЕКТНИХ ЗАДАЧ З РОЗРІДЖЕНИМИ … Теорія оптимальних рішень. 2013 81 Висновки. Метод триетапної регуляризації є альтернативою методам, заснованим на сингулярному або зваженому сингулярному розвиненнях матриць. Перевагою методу триетапної регуляризації є менша кількість арифме- тичних операцій. При використанні алгоритмів сингулярного розвинення не вдається істотно зменшити кількість арифметичних операцій у зв'язку з необ- хідністю обчислення всіх сингулярних векторів. Достоїнства алгоритму три- етапної регуляризації підсилюється для розріджених матриць. Запропоновані схеми методу триетапної регуляризації поділяються на де- кілька підзадач з розрідженими матрицями, розв’язання яких ефективно реалізу- ється [4] на сучасних високопродуктивних комп’ютерах, у тому числі з пара- лельною організацією обчислень. А.В. Попов ОБ ЭФФЕКТИВНОМ МЕТОДЕ РЕШЕНИЯ НЕКОРРЕКТНЫХ ЗАДАЧ С РАЗРЕЖЕННЫМИ МАТРИЦАМИ Для нахождения приближений с наперед заданной точностью к нормальному обобщенному или к взвешенному нормального обобщенному решениям системы линейных алгебраических уравнений с положительно полуопределенной разреженной симметричной матрицей предло- жен метод трехэтапной регуляризации. A.V. Popov ON THE EFFICIENT METHOD FOR THE SOLVING OF INCORRECT PROBLEMS WITH SPARSE MATRICES A three-staged regularization method is proposed for the finding within a priori given accuracy of approximations either to normal generalized or weighted normal generalized solutions of linear algebraic system with positive semi-defined sparse symmetric matrix. 1. Химич А.Н., Яковлев М.Ф. О решении систем с матрицами неполного ранга // Компью- терная математика. – 2003. – № 1. – C. 1–15. 2. Попов А.В., Химич А.Н. Исследование и решение первой основной задачи теории упру- гости // Компьютерная математика. – 2003. – № 2. – С. 105–114. 3. Морозов В.А. Методы регуляризации неустойчивых задач. – М.: Изд-во МГУ, 1987. – 216 с. 4. Химич А.Н., Попов А.В., Полянко В.В. Алгоритмы параллельных вычислений для задач линейной алгебры с матрицами нерегулярной структуры // Кибернетика и системный анализ. – 2011. – № 6. – С. 159–174. Одержано 15.03.2013

Про ефективний метод розв'язування некоректних задач з розрідженими матрицями

Institution

Ähnliche Einträge