Методы обновления столбцово-строчных факторных матриц для ускоренного решения нелинейных систем алгебраических уравнений большой размерности

Предложены методы столбцового, строчного, столбцово-строчного и многорангового обновления факторных матриц, получаемых в результате CR-факторизации. Даны оценки вычислительной сложности методов CR-обновления матриц и определены условия эффективного их применения в составе итерационного метода Ньютон...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2013
1. Verfasser:	Саух, С.Е.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України 2013
Schriftenreihe:	Электронное моделирование
Schlagworte:	Математические методы и модели
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/100852
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. — Т. 35, № 4. — С. 3-19. — Бібліогр.: 8 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-100852
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-1008522025-02-09T14:26:52Z Методы обновления столбцово-строчных факторных матриц для ускоренного решения нелинейных систем алгебраических уравнений большой размерности Саух, С.Е. Математические методы и модели Предложены методы столбцового, строчного, столбцово-строчного и многорангового обновления факторных матриц, получаемых в результате CR-факторизации. Даны оценки вычислительной сложности методов CR-обновления матриц и определены условия эффективного их применения в составе итерационного метода Ньютона решения нелинейных систем алгебраических уравнений. Представлены экспериментальные результаты использования методов CR-обновления матриц для решения тестовых систем нелинейных уравнений большой размерности. Запропоновано методи стовпцевого, рядкового, стовпцево-рядкового і багаторангового оновлення факторних матриць, що утворюються в результаті CR-факторізації. Дано оцінки обчислювальної складності методів CR-оновлення матриць і визначено умови ефективного їх застосування у складі ітераційного методу Ньютона розв’язку нелінійних систем алгебраїчних рівнянь. Представлено експериментальні результати застосування методів CR-оновлення матриць для розв’язування тестових систем нелінійних рівнянь великої розмірності. A column, row, column-row and multi-rank methods of updating the factor matrices derived from CR-matrix factorization are proposed. We obtain estimates of the computational complexity of the CR-updating methods. The conditions for their effective use in the Newton iterative method for solving nonlinear algebraic equations are determined. The experimental results of using the CR-updating methods of test matrices for solution of large scale systems of nonlinear equations are presented. 2013 Article Методы обновления столбцово-строчных факторных матриц для ускоренного решения нелинейных систем алгебраических уравнений большой размерности / С.Е. Саух // Электронное моделирование. — 2013. — Т. 35, № 4. — С. 3-19. — Бібліогр.: 8 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/100852 591.6 ru Электронное моделирование application/pdf Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Математические методы и модели Математические методы и модели
spellingShingle	Математические методы и модели Математические методы и модели Саух, С.Е. Методы обновления столбцово-строчных факторных матриц для ускоренного решения нелинейных систем алгебраических уравнений большой размерности Электронное моделирование
description	Предложены методы столбцового, строчного, столбцово-строчного и многорангового обновления факторных матриц, получаемых в результате CR-факторизации. Даны оценки вычислительной сложности методов CR-обновления матриц и определены условия эффективного их применения в составе итерационного метода Ньютона решения нелинейных систем алгебраических уравнений. Представлены экспериментальные результаты использования методов CR-обновления матриц для решения тестовых систем нелинейных уравнений большой размерности.
format	Article
author	Саух, С.Е.
author_facet	Саух, С.Е.
author_sort	Саух, С.Е.
title	Методы обновления столбцово-строчных факторных матриц для ускоренного решения нелинейных систем алгебраических уравнений большой размерности
title_short	Методы обновления столбцово-строчных факторных матриц для ускоренного решения нелинейных систем алгебраических уравнений большой размерности
title_full	Методы обновления столбцово-строчных факторных матриц для ускоренного решения нелинейных систем алгебраических уравнений большой размерности
title_fullStr	Методы обновления столбцово-строчных факторных матриц для ускоренного решения нелинейных систем алгебраических уравнений большой размерности
title_full_unstemmed	Методы обновления столбцово-строчных факторных матриц для ускоренного решения нелинейных систем алгебраических уравнений большой размерности
title_sort	методы обновления столбцово-строчных факторных матриц для ускоренного решения нелинейных систем алгебраических уравнений большой размерности
publisher	Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
publishDate	2013
topic_facet	Математические методы и модели
url	https://nasplib.isofts.kiev.ua/handle/123456789/100852
citation_txt	Методы обновления столбцово-строчных факторных матриц для ускоренного решения нелинейных систем алгебраических уравнений большой размерности / С.Е. Саух // Электронное моделирование. — 2013. — Т. 35, № 4. — С. 3-19. — Бібліогр.: 8 назв. — рос.
series	Электронное моделирование
work_keys_str_mv	AT sauhse metodyobnovleniâstolbcovostročnyhfaktornyhmatricdlâuskorennogorešeniânelinejnyhsistemalgebraičeskihuravnenijbolʹšojrazmernosti
first_indexed	2025-11-26T20:16:01Z
last_indexed	2025-11-26T20:16:01Z
_version_	1849885370221592576
fulltext	ÓÄÊ 591.6 Ñ.Å. Ñàóõ, ä-ð òåõí. íàóê Èí-ò ïðîáëåì ìîäåëèðîâàíèÿ â ýíåðãåòèêå èì. Ã.Å. Ïóõîâà ÍÀÍ Óêðàèíû (Óêðàèíà, 03164, Êèåâ-164, óë. Ãåíåðàëà Íàóìîâà, 15, òåë. 4249164, e-mail: ssaukh@gmail.com) Ìåòîäû îáíîâëåíèÿ ñòîëáöîâî-ñòðî÷íûõ ôàêòîðíûõ ìàòðèö äëÿ óñêîðåííîãî ðåøåíèÿ íåëèíåéíûõ ñèñòåì àëãåáðàè÷åñêèõ óðàâíåíèé áîëüøîé ðàçìåðíîñòè Ïðåäëîæåíû ìåòîäû ñòîëáöîâîãî, ñòðî÷íîãî, ñòîëáöîâî-ñòðî÷íîãî è ìíîãîðàíãîâîãî îáíîâëåíèÿ ôàêòîðíûõ ìàòðèö, ïîëó÷àåìûõ â ðåçóëüòàòå CR-ôàêòîðèçàöèè. Äàíû îöåíêè âû÷èñëèòåëüíîé ñëîæíîñòè ìåòîäîâ CR-îáíîâëåíèÿ ìàòðèö è îïðåäåëåíû óñëîâèÿ ýô- ôåêòèâíîãî èõ ïðèìåíåíèÿ â ñîñòàâå èòåðàöèîííîãî ìåòîäà Íüþòîíà ðåøåíèÿ íåëè- íåéíûõ ñèñòåì àëãåáðàè÷åñêèõ óðàâíåíèé. Ïðåäñòàâëåíû ýêñïåðèìåíòàëüíûå ðåçóëüòàòû èñïîëüçîâàíèÿ ìåòîäîâ CR-îáíîâëåíèÿ ìàòðèö äëÿ ðåøåíèÿ òåñòîâûõ ñèñòåì íåëèíåéíûõ óðàâíåíèé áîëüøîé ðàçìåðíîñòè. Çàïðîïîíîâàíî ìåòîäè ñòîâïöåâîãî, ðÿäêîâîãî, ñòîâïöåâî-ðÿäêîâîãî ³ áàãàòîðàíãîâîãî îíîâëåííÿ ôàêòîðíèõ ìàòðèöü, ùî óòâîðþþòüñÿ â ðåçóëüòàò³ CR-ôàêòîð³çàö³¿. Äàíî îö³í- êè îá÷èñëþâàëüíî¿ ñêëàäíîñò³ ìåòîä³â CR-îíîâëåííÿ ìàòðèöü ³ âèçíà÷åíî óìîâè åôåêòèâ- íîãî ¿õ çàñòîñóâàííÿ ó ñêëàä³ ³òåðàö³éíîãî ìåòîäó Íüþòîíà ðîçâ’ÿçêó íåë³í³éíèõ ñèñòåì àëãåáðà¿÷íèõ ð³âíÿíü. Ïðåäñòàâëåíî åêñïåðèìåíòàëüí³ ðåçóëüòàòè çàñòîñóâàííÿ ìåòîä³â CR-îíîâëåííÿ ìàòðèöü äëÿ ðîçâ’ÿçóâàííÿ òåñòîâèõ ñèñòåì íåë³í³éíèõ ð³âíÿíü âåëèêî¿ ðîçì³ðíîñò³. Ê ë þ ÷ å â û å ñ ë î â à: ðàçðåæåííûå ìàòðèöû, îáíîâëåíèå ìàòðèö, ñòîëáöîâî-ñòðî÷íàÿ ôàêòîðèçàöèÿ. Ïðè èñïîëüçîâàíèè âû÷èñëèòåëüíûõ ìåòîäîâ äëÿ ðåøåíèÿ ðàçëè÷íûõ ìàòåìàòè÷åñêèõ çàäà÷ ÷àñòî âîçíèêàåò íåîáõîäèìîñòü ìíîãîêðàòíîãî ðå- øåíèÿ ñèñòåì ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé. Òàê, â ñèìïëåêñ ìåòî- äå Äàíöèãà ðåøåíèÿ çàäà÷ ëèíåéíîãî ïðîãðàììèðîâàíèÿ íà êàæäîì èòåðà- öèîííîì øàãå íåîáõîäèìî ðåøàòü ñèñòåìû ëèíåéíûõ óðàâíåíèé äâàæäû [1]. Ìåòîä Ëåìêå ðåøåíèÿ çàäà÷ äîïîëíèòåëüíîñòè [2], à òàêæå ìåòîäû Íüþòîíà ðåøåíèÿ íåëèíåéíûõ ñèñòåì àëãåáðàè÷åñêèõ óðàâíåíèé è çàäà÷ îïòèìè- çàöèè òðåáóþò ðåøåíèÿ ëèíåéíûõ ñèñòåì óðàâíåíèé íà êàæäîé èòåðàöèè [3]. Â çàäà÷àõ áîëüøîé ðàçìåðíîñòè çàòðàòû âû÷èñëèòåëüíûõ ðåñóðñîâ íà ìíîãîêðàòíîå ðåøåíèå ñèñòåì ëèíåéíûõ óðàâíåíèé ñòàíîâÿòñÿ äîìèíè- ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 4 3 МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ � Ñ.Å. Ñàóõ, 2013 ðóþùèìè, ÷òî îáóñëîâëåíî òðóäîåìêîñòüþ àëãîðèòìîâ ôàêòîðèçàöèè ìàò- ðèö. Äëÿ ñîêðàùåíèÿ âû÷èñëèòåëüíûõ çàòðàò êàæäûé ðàç ïðè îáíîâëåíèè áàçèñà ïåðåìåííûõ â ñèìïëåêñ ìåòîäå, à òàêæå â ìåòîäå Ëåìêå èñïîëü- çóþòñÿ àëãîðèòìû LU-îáíîâëåíèÿ ôàêòîðíûõ ìàòðèö [4, 5]. Àëãîðèòìû óñêîðåííîãî áëî÷íîãî èëè ÷àñòè÷íîãî LU-îáíîâëåíèÿ ìàòðèö ßêîáè ïðè- ìåíÿþòñÿ â èòåðàöèîííûõ ìåòîäàõ Íüþòîíà ðåøåíèÿ ñèñòåì íåëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé áîëüøîé ðàçìåðíîñòè [6]. Ñóùåñòâóþùèå àëãîðèòìû îáíîâëåíèÿ ôàêòîðíûõ ìàòðèö îñíîâàíû íà ìåòîäå LU-ôàêòîðèçàöèè, áîëåå òðóäîåìêîì ïî ñðàâíåíèþ ñ ìåòîäîì ñòîëáöîâî-ñòðî÷íîé (CR) ôàêòîðèçàöèè [7]. Îáëàäàÿ ñâîéñòâîì àäàïòèâ- íîñòè ê äèíàìè÷åñêè âûáèðàåìûì âåäóùèì ýëåìåíòàì, ìåòîä CR-ôàêòî- ðèçàöèè ìàòðèö íå òðåáóåò ïåðåñòàíîâîê ñòðîê è ñòîëáöîâ, ÷òî ïîçâîëÿåò ñóùåñòâåííî, â ñðåäíåì áîëåå ÷åì íà òðåòü, ñîêðàòèòü âðåìÿ âû÷èñëåíèé. Ïîýòîìó ðàçðàáîòêà ìåòîäîâ CR-îáíîâëåíèÿ ôàêòîðíûõ ìàòðèö ÿâëÿåòñÿ àêòóàëüíîé. Ìåòîä CR-ôàêòîðèçàöèè ìàòðèö. Îñíîâîé ìåòîäà CR-ôàêòîðèçà- öèè ÿâëÿåòñÿ ïîñëåäîâàòåëüíîñòü äåéñòâèé, âûïîëíÿåìûõ íàä çàäàíîé n n� ìàòðèöåé A â ñîîòâåòñòâèè ñ ôîðìóëàìè A A C Ri j j i( , )� � � � 1 1 1 1 , A ii j( , ) ( ,:)� � � 1 1 1 0, A ji j( , ) (:, )� � � 1 1 1 0, i n1 1 2�{ , ,..., }, j n1 1 2�{ , ,..., }; A A C Ri j i j j i( , ) ( , )� � � �� 2 2 1 1 2 2 , A ii j( , ) ( ,:)� � � 2 2 2 0, A ji j( , ) (:, )� � � 2 2 2 0, i n2 1 2�{ , ,..., }, i i2 1� , j n2 1 2�{ , ,..., }, j j2 1� ; (1) .................................................................................................................. A A C Ri j i j j in n n n n n( , ) ( , )� � � �� 1 1 0, i nn �{ , ,..., }1 2 , i i k nn k� � �{ \| , ,..., }1 2 1 , j nn �{ , ,..., }1 2 , j j k nn k� � �{ \| , ,..., }1 2 1 . Åñëè ìíîæåñòâà âåêòîð-ñòîëáöîâ è âåêòîð-ñòðîê îáúåäèíèòü â ìàòðèöû ñîîòâåòñòâåííî C C C Cj j jn � \| \| 1 2 � è R R R Ri i i T n � \| \| 1 2 � , òî ïîëó÷èì ðàç- ëîæåíèå A CR C Rj i s n s s � � � 1 . Ìåòîäû CR-îáíîâëåíèÿ ìàòðèö. Èçìåíåíèå çíà÷åíèé ýëåìåíòîâ p-ãî ñòîëáöà èñõîäíîé ìàòðèöû. Ïóñòü â ñîîòâåòñòâèè ñ (1) äëÿ èñõîä- íîé ìàòðèöû A ïîëó÷åíû ôàêòîðíûå ìíîæèòåëè C è R: A CR� . (2) Ñ.Å. Ñàóõ 4 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 4 Íàéäåì ôàêòîðíûå ìíîæèòåëè ìàòðèöû A, îáðàçîâàííîé èç èñõîäíîé ìàòðèöû A çàìåíîé åå p-ãî ñòîëáöà A a a ap p p np T : \| \|� 1 2 � íà ñòîëáåö A a a a: \| \|p p p np T� 1 2 � : A A� �A Ap p p T( ): : e , (3) ãäå e p T � \| \|0 1 0 1� � — âåêòîð-ñòðîêà, âñå ýëåìåíòû êîòîðîãî ðàâíû íóëþ, çà èñêëþ÷åíèåì p-ãî, ðàâíîãî åäèíèöå. Äëÿ ýòîãî âûðàæåíèå (3) çàïèøåì â òîæäåñòâåííîì âèäå A A� ��A AA Ap p T p p T1 : e e e , (4) èëè A � �A E p p T p p T( )v e e e , (5) ãäå âåêòîð v p pA� �1 A : , î÷åâèäíî, ÿâëÿåòñÿ ðåøåíèåì óðàâíåíèÿ A p pv � A : èëè CR p pv � A : . (6) Ñëåäóåò çàìåòèòü, ÷òî èñïîëüçóåìîå â âûðàæåíèÿõ (4) è (5) ïðîèç- âåäåíèå âåêòîðîâ e ep p T ïðåäñòàâëÿåò ñîáîé n n� ìàòðèöó, âñå ýëåìåíòû êîòîðîé ðàâíû íóëþ çà èñêëþ÷åíèåì p-ãî äèàãîíàëüíîãî ýëåìåíòà, ðàâ- íîãî åäèíèöå. Ïîýòîìó, ñîäåðæàùååñÿ â (5) ìàòðè÷íîå âûðàæåíèå âèäà E p p T�e e â äàëüíåéøåì áóäåì ïðåäñòàâëÿòü ìàòðèöåé E p � 1 1 0 1 1 � � , ïîä÷åðêèâàÿ åå îòëè÷èå îò åäèíè÷íîé ìàòðèöû E òîëüêî p-ì íóëåâûì äèàãîíàëüíûì ýëåìåíòîì. Ñëåäîâàòåëüíî, E p p T p� �e e E . (7) Ó÷èòûâàÿ ñîîòíîøåíèÿ (5)�(7), âûðàæåíèå (3) ïðåäñòàâèì â âèäå ïðîèç- âåäåíèÿ òðåõ ìàòðè÷íûõ ìíîæèòåëåé: A E V� �CR CRp p p T p( )v e . (8) Ìåòîäû îáíîâëåíèÿ ñòîëáöîâî-ñòðî÷íûõ ôàêòîðíûõ ìàòðèö ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 4 5 Òðåòèé îáíîâëÿþùèé ìíîæèòåëü âèäà V Ep p p p T p p pp np v v v v � �v e 1 1 1 1 2 � � � � èìååò ïðîñòóþ ñòðóêòóðó, ÷òî ïîçâîëÿåò íåïîñðåäñòâåííî èñïîëüçîâàòü ðàçëîæåíèå (8) ìàòðèöû A â ðàçëè÷íûõ âû÷èñëèòåëüíûõ àëãîðèòìàõ. Òàê, îñóùåñòâëÿÿ ïîèñê âåêòîðà íåèçâåñòíûõ X íåëèíåéíîé ñèñòåìû óðàâíåíèé F X( ) �0 (9) èòåðàöèîííûì ìåòîäîì Íüþòîíà, ïî èçâåñòíûì çíà÷åíèÿì ýëåìåíòîâ âåêòîðà X k �1 íà k-é èòåðàöèè ôîðìèðóåì ñèñòåìó ëèíåàðèçîâàííûõ óðàâ- íåíèé F X F X F X X X( ) ( ) ( )k k X X k k k � � �� 1 1 1 0 � � (10) îòíîñèòåëüíî èñêîìîãî âåêòîðà X k . Ïóñòü ìàòðèöà ßêîáè � �F / X îáëàäàåò îñîáåííîñòüþ òàêîé, ÷òî ýëå- ìåíòû ëèøü îäíîãî åå p-ãî ñòîëáöà ôóíêöèîíàëüíî çàâèñÿò îò íåèçâåñò- íîé x p , ò.å. âñå ôóíêöèè-ýëåìåíòû \| ( ) ( ) ( ) \|f f f n T 1 2X X X� âåêòîð-ôóíê- öèè F X( ) ÿâëÿþòñÿ ëèíåéíûìè ïî âñåì ïåðåìåííûì, êðîìå ïåðåìåííîé x p , îòíîñèòåëüíî êîòîðîé îíè ÿâëÿþòñÿ íåëèíåéíûìè. Íàïðèìåð, äëÿ ñèñòåìû íåëèíåéíûõ óðàâíåíèé x x x1 2 33 5 3 � , 4 2 21 2 2 2 3x x x x � , 3 2 11 2 2 2 3x x x x �( ) ìàòðèöà ßêîáè èìååò âèä � � F X � 1 3 5 4 1 2 2 3 2 3 1 2 2 2 x x . Òîãäà, ñëåäóÿ (6) è (8), ìíîæåñòâî òðóäîåìêèõ âû÷èñëèòåëüíûõ ïðîöåäóð ôàêòîðèçàöèè ìàòðèö � �F / X X X k� �1 , âõîäÿùèõ â óðàâíåíèå (10), ìîæíî Ñ.Å. Ñàóõ 6 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 4 çàìåíèòü îäíîðàçîâîé ïðîöåäóðîé âû÷èñëåíèÿ íà ïåðâîé èòåðàöèè ôàê- òîðíûõ ìíîæèòåëåé C è R ìàòðèöû A X X � � � �F / X 0 è èñïîëüçîâàòü èõ äëÿ ïîñëåäîâàòåëüíîãî ðåøåíèÿ ñèñòåì óðàâíåíèé âèäà CR ( ) ( )X X F X 1 0 0� � � ïðè k �1, CR CR p p p T k k k p X X p k ( )( ) ( ), : E � � � � � � � � v e X X F X v F / X 1 1 1� � � � �� ïðè k �1, (11) ãäå � �F / X X X p k� �1 : — p-é ñòîëáåö ìàòðèöû ßêîáè, ýëåìåíòû êîòîðîãî çàâèñÿò îò çíà÷åíèÿ x p k �1. Íà êàæäîé èòåðàöèè k �2 3, ,... àëãîðèòì ðåøåíèÿ ñèñòåì óðàâíåíèé (11) ñîñòîèò èç ñëåäóþùèõ òðåõ øàãîâ. Àëãîðèòì 1. 1. Ðåøåíèå ñèñòåìû óðàâíåíèé CR p X X p kv F / X� � �� 1 : îòíîñèòåëü- íî âåêòîðà v p . 2. Ðåøåíèå ñèñòåìû óðàâíåíèéCR k Y F X� � �( 1 )îòíîñèòåëüíî âåêòîðà Y. 3. Ðåøåíèå ñèñòåìû óðàâíåíèé ( )( )E p p p T k k � �� v e X X Y 1 îòíîñèòåëü- íî èñêîìîãî âåêòîðà X k . Ðåøåíèå êàæäîé èç ïðåäñòàâëåííûõ ñèñòåì óðàâíåíèé íå òðåáóåò ãðîìîçäêèõ âû÷èñëåíèé, ÷òî çíà÷èòåëüíî óñêîðÿåò âûïîëíåíèå èòåðà- öèîííûõ ïðîöåäóð ìåòîäà Íüþòîíà. Èçìåíåíèe çíà÷åíèé ýëåìåíòîâ ìíîæåñòâà ñòîëáöîâ èñõîäíîé ìàòðèöû. Åñëè â èñõîäíîé ìàòðèöå A CR� îäíîâðåìåííî çàìåíèòü ñòîëá- öû A pj: ñòîëáöàìè A :pj , íîìåðà êîòîðûõ p j îáðàçóþò ìíîæåñòâî P � �{ , , ..., }p p pJ1 2 , è òàêèì ñïîñîáîì ñôîðìèðîâàòü íîâóþ ìàòðèöó A, òî ôîðìóëà îáíîâëåíèÿ ôàêòîðíûõ ìíîæèòåëåé ïðèìåò âèä A E V=CR CRp p p j J p p T PJ j j{ , , ..., }1 2 1 � � � � � � � � � � v e , (12) ãäå ìàòðèöà E{ , , ..., }p p pJ1 2 îòëè÷àåòñÿ îò åäèíè÷íîé ìàòðèöû E íóëåâûìè çíà÷åíèÿìè äèàãîíàëüíûõ ýëåìåíòîâ â ïîçèöèÿõ p p pJ1 2, ,..., ; äëÿ� �p Pj âåêòîðû îáíîâëåíèÿ v pj óäîâëåòâîðÿþò ñèñòåìàì óðàâíåíèèé CR p pj j v � A : (13) è âìåñòå ñ ìàòðèöåé E{ , , ..., }p p pJ1 2 îáðàçóþò ìàòðèöó îáíîâëåíèÿ Ìåòîäû îáíîâëåíèÿ ñòîëáöîâî-ñòðî÷íûõ ôàêòîðíûõ ìàòðèö ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 4 7 V EP p p p j J p p T p p p p J j j J � � � { , , ..., }1 2 1 1 1 1 1 11 v e v v v v � � � p p p p p p n p n p J J J J 1 1 1 1 1 1 � � � � � � v v v v . (14) Î÷åâèäíî, èñïîëüçîâàíèå ôîðìóëû (12) ïîçâîëÿåò ðàñøèðèòü âîçìîæ- íîñòè àëãîðèòìà 1 óñêîðåííîãî ðåøåíèÿ ëèíåàðèçîâàííûõ ñèñòåì óðàâ- íåíèé âèäà (10) íà ñëó÷àé, êîãäà ýëåìåíòû ìíîæåñòâà ñòîëáöîâ P p�{ ,1 p pJ2 ,..., } ìàòðèöû ßêîáè � �F / X ôóíêöèîíàëüíî çàâèñÿò îò íåèçâåñòíûõ x x xp p pJ1 2 , , ..., , ò.å. âñå ôóíêöèè-ýëåìåíòû \| ( ) ( ) ( ) \|f f f n T 1 2X X X� âåêòîð- ôóíêöèè F X( ) ÿâëÿþòñÿ ëèíåéíûìè ïî âñåì ïåðåìåííûì, êðîìå ïåðå- ìåííûõ x x xp p pJ1 2 , , ..., , îòíîñèòåëüíî êîòîðûõ îíè ÿâëÿþòñÿ íåëèíåé- íûìè. Â ýòîì ñëó÷àå âìåñòî ñèñòåì óðàâíåíèé (11) çàïèøåì CR ( ) ( )X X F X 1 0 0� � � ïðè k �1, CR p p p j J p p T k k J j j E{ , , ..., } ( ) 1 2 1 1 � � � � � � � � � � � � � v e X X F ( ), : X v F / X k j p X X p p P CR j k j � � � � � � �� 1 1� � ïðè k �1. (15) Îòëè÷èå àëãîðèòìà ðåøåíèÿ ñèñòåìû óðàâíåíèé (15) îò àëãîðèòìà 1 ðåøåíèÿ ñèñòåìû óðàâíåíèé (11) çàêëþ÷àåòñÿ â òîì, ÷òî íà øàãå 1 íåîáõî- äèìî ðåøèòü J ñèñòåì óðàâíåíèé CR p X X pj k j v F / X� � �� 1 : äëÿ � �p Pj , à íà øàãå 3 — áîëåå ñëîæíóþ ñèñòåìó óðàâíåíèé âèäà E{ , , ..., } ( )p p p j J p p T k k J j j1 2 1 1 � � � � � � � � � � � � v e X X Y . (16) Ïðèíèìàÿ âî âíèìàíèå ñòðóêòóðó ìàòðèöû îáíîâëåíèÿ (14), áûñòðîå ðå- øåíèå ñèñòåìû óðàâíåíèé (16) îñóùåñòâëÿåòñÿ ïîñðåäñòâîì ðåøåíèÿ ïîä- ñèñòåìû óðàâíåíèé ðàçìåðíîñòüþ J, êîòîðàÿ ñâÿçûâàåò ïîäìíîæåñòâî ýëåìåíòîâ ïðàâûõ ÷àñòåé Y{ , , ..., }p p pJ1 2 ñ ïîäìíîæåñòâîì èñêîìûõ ýëåìåí- òîâ ( ){ , , ..., }X X k k p p pJ � �1 1 2 , è çàòåì íàõîæäåíèÿ îñòàëüíûõ ýëåìåíòîâ âåê- Ñ.Å. Ñàóõ 8 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 4 òîðà ( )X X k k� �1 ïî ïðîñòûì ÿâíûì âûðàæåíèÿì ñ èñïîëüçîâàíèåì â íèõ ïîäñòàíîâîê óæå íàéäåíûõ çíà÷åíèé ( ){ , , ..., }X X k k p p pJ � �1 1 2 . Èçìåíåíèå çíà÷åíèé ýëåìåíòîâ q-é ñòðîêè èñõîäíîé ìàòðèöû. Íàéäåì ôàêòîðíûå ìíîæèòåëè ìàòðèöû A, îáðàçîâàííîé èç èñõîäíîé ìàòðèöû A CR� çàìåíîé åå q-é ñòðîêè A a a aq q q qn: \| \|� 1 2 � ñòðîêîé A a a aq q q qn: \| \|� 1 2 � : A A� �A Aq q qe ( ): : , (17) ãäå e q T� \| 0 1 0 0� � — âåêòîð-ñòîëáåö, âñå ýëåìåíòû êîòîðîãî ðàâíû íóëþ, çà èñêëþ÷åíèåì q-ãî, ðàâíîãî åäèíèöå. Äëÿ ýòîãî âûðàæåíèå (17) çàïèøåì â òîæäåñòâåííîì âèäå: A A� ��A A A Aq q q q T e e e: 1 , (18) èëè A � � ( )E Aq q T q qe e e u , (19) ãäå âåêòîð-ñòðîêà uq q A� � A : 1, î÷åâèäíî, ÿâëÿåòñÿ ðåøåíèåì óðàâíåíèÿ uq qA � A : èëè uq qCR � A : . (20) Çàìåòèì, ÷òî èñïîëüçóåìîå â âûðàæåíèÿõ (18), (19) ïðîèçâåäåíèå âåêòîðîâ e eq q T ïðåäñòàâëÿåò ñîáîé n n� ìàòðèöó, âñå ýëåìåíòû êîòîðîé ðàâíû íóëþ çà èñêëþ÷åíèåì q-ãî äèàãîíàëüíîãî ýëåìåíòà, ðàâíîãî åäèíè- öå. Ïîýòîìó ñîäåðæàùååñÿ â (19) ìàòðè÷íîå âûðàæåíèå E q q T�e e ìîæíî ïðåäñòàâèòü â âèäå ìàòðèöû E q q T q� �e e E . Ñ ó÷åòîì ñîîòíîøåíèé (19), (20) âûðàæåíèå (17) çàïèøåì â âèäå ïðîèçâåäåíèÿ òðåõ ìàòðè÷íûõ ìíîæèòåëåé: A E U� �( )q q q qCR CRe u . (21) Çäåñü ïåðâûé îáíîâëÿþùèé ìíîæèòåëü U Eq q q q q q qq qnu u u u � �e u 1 1 1 1 2 � � � � Ìåòîäû îáíîâëåíèÿ ñòîëáöîâî-ñòðî÷íûõ ôàêòîðíûõ ìàòðèö ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 4 9 èìååò ïðîñòóþ ñòðóêòóðó, ÷òî ïîçâîëÿåò íåïîñðåäñòâåííî èñïîëüçîâàòü ðàçëîæåíèå (21) ìàòðèöû A â ðàçëè÷íûõ âû÷èñëèòåëüíûõ àëãîðèòìàõ. Âíîâü îáðàùàÿñü ê èòåðàöèîííîìó ìåòîäó Íüþòîíà ðåøåíèÿ íåëèíåé- íîé ñèñòåìû óðàâíåíèé (9), ðàññìîòðèì ïîñëåäîâàòåëüíîñòü ðåøåíèÿ ëèíåà- ðèçîâàííûõ ñèñòåì óðàâíåíèé (10) äëÿ ñëó÷àÿ, êîãäà ýëåìåíòû ëèøü îäíîé q-é ñòðîêè ìàòðèöû ßêîáè� �F / Xôóíêöèîíàëüíî çàâèñÿò îò çíà÷åíèé âåêòî- ðà íåèçâåñòíûõ X, ò.å. êîãäà âñå ôóíêöèè-ýëåìåíòû \| ( ) ( ) ( ) \|f f f n T 1 2X X X� âåêòîð-ôóíêöèè F X( ) — ëèíåéíûå ïî âñåì ïåðåìåííûì, êðîìå ôóíêöèè f q ( )X , êîòîðàÿ ÿâëÿåòñÿ íåëèíåéíîé. Íàïðèìåð, ïîñòðîåííàÿ äëÿ ñèñòåìû íåëèíåéíûõ óðàâíåíèé x x x1 2 33 5 3 � , x x x1 2 2 3 200� , 3 10 11 2 3x x x � ìàòðèöà ßêîáè èìååò âèä � � F X � 1 3 5 2 3 10 1 2 2 3 1 2 3 1 2 2x x x x x x x . Òîãäà, ñëåäóÿ (20) è (21), ìíîæåñòâî òðóäîåìêèõ âû÷èñëèòåëüíûõ ïðî- öåäóð ôàêòîðèçàöèè ìàòðèö � �F / X X X k� �1 , âõîäÿùèõ â óðàâíåíèå (10), ìîæíî çàìåíèòü îäíîðàçîâîé ïðîöåäóðîé âû÷èñëåíèÿ íà ïåðâîé èòåðàöèè ôàêòîðíûõ ìíîæèòåëåé C è R ìàòðèöû A X X � � � �F / X 0 è èñïîëüçîâàòü èõ äëÿ ïîñëåäîâàòåëüíîãî ðåøåíèÿ ñèñòåì óðàâíåíèé CR ( ) ( )X X F X 1 0 0� � � ïðè k �1, ( ) ( ) ( ), : Eq q q k k k q X X q CR CR k � � � � � � � � � e u X X F X u F / X 1 1 1� � � �� ïðè k �1, (22) ãäå � �F / X X X q k� �1 : — q-ÿ ñòðîêà ìàòðèöû ßêîáè, ýëåìåíòû êîòîðîé â îáùåì ñëó÷àå çàâèñÿò îò çíà÷åíèé ýëåìåíòîâ âåêòîðà X k �1. Íà êàæäîé èòåðàöèè k �2 3, ,... àëãîðèòì ðåøåíèÿ ñèñòåì óðàâíåíèé (22) ðåàëèçóåòñÿ ïîñëåäîâàòåëüíûì âûïîëíåíèåì ñëåäóþùèõ òðåõ øàãîâ. Àëãîðèòì 2. 1. Ðåøåíèå ñèñòåìû óðàâíåíèé u F / Xq X X q CR k� � �� 1 : îòíîñèòåëü- íî âåêòîð-ñòðîêè uq . 2. Ðåøåíèå ñèñòåìû óðàâíåíèé( ) ( )Eq q q k � � � e u Y F X 1 îòíîñèòåëüíî âåêòîðà Y. Ñ.Å. Ñàóõ 10 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 4 3. Ðåøåíèå ñèñòåìû óðàâíåíèé CR k k( )X X Y� ��1 îòíîñèòåëüíî èñêî- ìîãî âåêòîðà X k . Çàìåòèì, ÷òî âû÷èñëèòåëüíûå ñëîæíîñòè àëãîðèòìîâ 1 è 2 èäåí- òè÷íû. Èçìåíåíèå çíà÷åíèé ýëåìåíòîâ ìíîæåñòâà ñòðîê èñõîäíîé ìàòðè- öû. Åñëè â èñõîäíîé ìàòðèöå A CR� îäíîâðåìåííî çàìåíèòü ñòðîêè A qi : ñòðîêàìè A qi : , íîìåðà êîòîðûõ qi îáðàçóþò ìíîæåñòâîQ q q qI�{ , ,..., }1 2 , è òàêèì ñïîñîáîì ñôîðìèðîâàòü íîâóþ ìàòðèöó A , òî ôîðìóëà îáíîâëåíèÿ ôàêòîðíûõ ìíîæèòåëåé ïðèìåò âèä A E U= CR CRq q q i I q q QI i i { , , ..., }1 2 1 � � �� e u , (23) ãäå ìàòðèöà E{ , , ..., }q q qI1 2 îòëè÷àåòñÿ îò åäèíè÷íîé ìàòðèöû E íóëåâûìè çíà÷åíèÿìè äèàãîíàëüíûõ ýëåìåíòîâ â ïîçèöèÿõ Q q q qI�{ , ,..., }1 2 ; äëÿ � �q Qi âåêòîð-ñòðîêè îáíîâëåíèÿ u qi óäîâëåòâîðÿþò ñèñòåìàì óðàâ- íåíèèé u q q i i CR � A : (24) è âìåñòå ñ ìàòðèöåé E{ , , ..., }q q qI1 2 îáðàçóþò ìàòðèöó îáíîâëåíèÿ U EQ q q q i I q q q q q q q I i i I u u u � � � { , , ..., }1 2 1 1 1 1 1 1 1 e u � � � � u u u u u q n q q q q q q n I I I I I 1 1 1 1 1 � � � � � . (25) Î÷åâèäíî, èñïîëüçîâàíèå ôîðìóëû (23) ïîçâîëÿåò ðàñøèðèòü âîçìîæíîñ- òè àëãîðèòìà 2 óñêîðåííîãî ðåøåíèÿ ëèíåàðèçîâàííûõ ñèñòåì óðàâíåíèé (10) íà ñëó÷àé, êîãäà ýëåìåíòû ìíîæåñòâà ñòðîêQ q q qI�{ , ,..., }1 2 ìàòðèöû ßêîáè � �F / X ôóíêöèîíàëüíî çàâèñÿò îò X, ò.å. êîãäà âñå ôóíêöèè-ýëå- ìåíòû \| ( ) ( ) ( ) \|f f f n T 1 2X X X� âåêòîð-ôóíêöèè F X( ) — ëèíåéíûå ïî âñåì ïåðåìåííûì, êðîìå ôóíêöèé f f fq q qI1 2 ( ) ( ) ( )X X X� , êîòîðûå ÿâëÿþòñÿ íåëèíåéíûìè. Â ýòîì ñëó÷àå âìåñòî ñèñòåìû óðàâíåíèé (22) ïîëó÷àåì Ìåòîäû îáíîâëåíèÿ ñòîëáöîâî-ñòðî÷íûõ ôàêòîðíûõ ìàòðèö ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 4 11 CR ( ) ( )X X F X 1 0 0� � � ïðè k �1, E e u X X F{ , , ..., } ( ) (q q q i I q q k k I i i CR 1 2 1 1 � � �� X u F / X k i q X X q q Q CR i k i � � � � � � � � � � � � � � � 1 1 ), : � � ïðè k �1. (26) Îòëè÷èå àëãîðèòìà ðåøåíèÿ ñèñòåìû (26) îò àëãîðèòìà 2 ðåøåíèÿ ñèñòåìû (22) çàêëþ÷àåòñÿ â òîì, ÷òî íà øàãå 1 íåîáõîäèìî ðåøèòü I ñèñòåì óðàâíåíèé u F / Xq X X qi k i CR � � �� 1 : äëÿ � �q Qi , à íà øàãå 2 — áîëåå ñëîæíóþ ñèñòåìó óðàâíåíèé âèäà E{ , , ..., } ( )q q q i I q q k I i i1 2 1 1 � � �� e u Y F X . (27) Ïðèíèìàÿ âî âíèìàíèå ñòðóêòóðó ìàòðèöû îáíîâëåíèÿ (25), áûñòðîå ðåøåíèå ñèñòåìû óðàâíåíèé (26) îñóùåñòâëÿåòñÿ ïîñðåäñòâîì ðåøåíèÿ ïðîñòåéøåé ïîäñèñòåìû óðàâíåíèé ðàçìåðíîñòüþ n I� ñ åäèíè÷íîé äèàãî- íàëüíîé ìàòðèöåé, êîòîðàÿ ñâÿçûâàåò ïîäìíîæåñòâî ýëåìåíòîâ ïðàâûõ ÷àñ- òåé F X� � { , , ..., }( )q q q k I1 2 1 ñ ïîäìíîæåñòâîì èñêîìûõ ýëåìåíòîâ Y�{ , , ..., }q q qI1 2 , è âû÷èñëåíèÿ çíà÷åíèé îñòàëüíûõ ýëåìåíòîâ âåêòîðà Y{ , , ..., }q q qI1 2 â ðåçóëü- òàòå ðåøåíèÿ ðåäóöèðîâàííîé ñèñòåìû óðàâíåíèé ðàçìåðíîñòè I I� . Îäíîâðåìåííîå èçìåíåíèå çíà÷åíèé ýëåìåíòîâ ìíîæåñòâà ñòðîê è ñòîëáöîâ èñõîäíîé ìàòðèöû. Åñëè â èñõîäíîé ìàòðèöå A CR� îäíî- âðåìåííî çàìåíèòü ñòîëáöû A pj: ñòîëáöàìè A :pj , íîìåðà êîòîðûõ p j îáðà- çóþò ìíîæåñòâî P p p pJ�{ , ,..., }1 2 , à ñòðîêè A qi : — ñòðîêàìè A qi : , íîìåðà êîòîðûõ îáðàçóþò ìíîæåñòâî Q q q qI�{ , ,..., }1 2 , è òàêèì ñïîñîáîì ñôîð- ìèðîâàòü íîâóþ ìàòðèöó A, òî ôîðìóëà îáíîâëåíèÿ ôàêòîðíûõ ìíîæè- òåëåé ïðèìåò âèä A E E= CRq q q i I q q p pI i i { , , ..., } { , , ...1 2 1 2 1 � � �� e u , }p j J p p T Q PJ j j CR � � � � � � � � � � 1 v e U V . (28) Èñïîëüçîâàíèå ôîðìóëû (28) ïîçâîëÿåò ðàñøèðèòü âîçìîæíîñòè àëãîðèòìîâ 1 è 2 óñêîðåííîãî ðåøåíèÿ ëèíåàðèçîâàííûõ ñèñòåì óðàâíå- íèé âèäà (10) íà ñëó÷àé, êîãäà ýëåìåíòû ìíîæåñòâà ñòðîêQ q q qI�{ , ,..., }1 2 è ñòîëáöîâ P p p pJ�{ , ,..., }1 2 ìàòðèöû ßêîáè � �F / X ôóíêöèîíàëüíî çàâè- ñÿò îò X. Â ýòîì ñëó÷àå ïîëó÷àåì CR ( ) ( )X X F X 1 0 0� � � ïðè k �1, Ñ.Å. Ñàóõ 12 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 4 U VQ P k k k i q X X q CR q Q CR i k i ( ) ( ), : X X F X u F / X � � � � � � � � � � 1 1 1� � , : � � � � � � � � � � � � � � � �� p P CRj p X X pj k j v F / X� � 1 ïðè k �1. (29) Íà êàæäîé èòåðàöèè k �2 3, ,... àëãîðèòì ðåøåíèÿ ñèñòåìû óðàâíåíèé (29) ðåàëèçóåòñÿ ïîñðåäñòâîì ïîñëåäîâàòåëüíîãî âûïîëíåíèÿ ñëåäóþùèõ ïÿòè øàãîâ. Àëãîðèòì 3. 1. Ðåøåíèå I ñèñòåì óðàâíåíèé u F / Xq X X qi k i CR � � �� 1 : îòíîñèòåëüíî âåêòîð-ñòðîê uqi . 2. Ðåøåíèå J ñèñòåì óðàâíåíèé CR p X X pj k j v F / X� � �� 1 : îòíîñèòåëü- íî âåêòîðîâ v pj . 3. Ðåøåíèå ñèñòåìû óðàâíåíèéUQ k Y F X� � �( )1 îòíîñèòåëüíî âåêòîðà Y, ãäå ìàòðèöà U EQ q q q i I q qI i i = e u{ , , ..., }1 2 1 � èìååò âèä (25). 4. Ðåøåíèå ñèñòåìû óðàâíåíèé CR Z Y� îòíîñèòåëüíî âåêòîðà Z. 5. Ðåøåíèå ñèñòåìû óðàâíåíèé VP k k( )X X Z� ��1 îòíîñèòåëüíî èñêî- ìîãî âåêòîðà X k , ãäå ìàòðèöàV EP p p p j J p p T J j j = v e{ , , ..., }1 2 1 � èìååò âèä (14). Äîáàâëåíèå ê èñõîäíîé ìàòðèöå ìàòðèöû áîëåå íèçêîãî ðàíãà. Åñëè ê èñõîäíîé ìàòðèöå A CR� äîáàâëÿåòñÿ ìàòðèöà �A s s s= m � c r 1 ðàíãà m n�� , òî òàêîé ñïîñîá ôîðìèðîâàíèÿ íîâîé ìàòðèöû A � A A� íàçû- âàåòñÿ ìíîãîðàíãîâûì îáíîâëåíèåì ìàòðèöû A. Â ýòîì ñëó÷àå ìàòðèöà �A ïðåäñòàâëÿåòñÿ ñóììîé m ïàðíûõ ïðîèçâåäåíèé n-ìåðíûõ âåêòîð-ñòîëá- öîâ { \| , }cs s m�1 è âåêòîð-ñòðîê{ \| , }rs s m�1 . Èñïîëüçóÿ ôàêòîðíûå ìíîæèòåëè C è R ìàòðèöû A, ïðåäñòàâèì ìàò- ðèöó A â âèäå A W� � � A A CR C Rs s s= m m� c r 1 , ãäå Wm — ìàòðèöà îáíîâëåíèÿ, W E Em m s s T s= m m s� � � �� { , , ..., } { , , ..., }1 2 1 1 2c e e rs s= m mE 1 1 2 � � �� E{ , , ..., }. Ìåòîäû îáíîâëåíèÿ ñòîëáöîâî-ñòðî÷íûõ ôàêòîðíûõ ìàòðèö ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 4 13 Çäåñü n-ìåðíûå ìíîæåñòâà âåêòîð-ñòîëáöîâ { \| , }cs s m�1 è âåêòîð-ñòðîê { \| , }rs s m�1 îïðåäåëÿþòñÿ ðåøåíèåì ñèñòåì óðàâíåíèé âèäà { \| , }C s ms sc c� �1 , { \| , }r rs sR s m� �1 , (30) à ìàòðèöà E{ , , ..., }1 2 m îòëè÷àåòñÿ îò åäèíè÷íîé ìàòðèöû E íóëåâûìè çíà- ÷åíèÿìè ïåðâûõ m åå äèàãîíàëüíûõ ýëåìåíòîâ. Åñëè ó÷åñòü îñîáåííîñòè ñëàãàåìûõ ìàòðèöû Wm, òî ìîæíî ïîñòðîèòü äîñòàòî÷íî ïðîñòîé ñïîñîá åå ïàðàìåòðè÷åñêîãî îáðàùåíèÿ ïðè ðåøåíèè ñîîòâåòñòâóþùèõ ñèñòåì ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé. Ïîêàæåì ýòî íà ñëåäóþùåì ïðèìåðå. Ïóñòü îáíîâëåíèå ìàòðèöû ßêîáè ÿâëÿåòñÿ ìíîãîðàíãîâûì, ò.å. � � � � F X F X c r c r X X X X s k s k s= m s k s k s k CR � � � � � � � � � 1 0 1 1 1 1 1 = m 1 . (31) Òîãäà óðàâíåíèå (10) äëÿ k �1 ìîæíî ïðåäñòàâèòü â âèäå ðàñøèðåííîé ñèñòåìû óðàâíåíèé CR k k s s k s= m k( ) ( )X X c F X� � �� 1 1 1 1� , { ( )} , � s s k k k s m = r X X � � � �1 1 1 , (32) ñîäåðæàùåé íå òîëüêî èñêîìûé âåêòîð ïåðåìåííûõ X k , íî è ìíîæåñòâî íåèçâåñòíûõ ïàðàìåòðîâ { } , � s s m�1 . Äëÿ íàõîæäåíèÿ çíà÷åíèé ïàðàìåòðîâ { } , � s s m�1 ðàçðåøèì âåðõíþþ ÷àñòü ñèñòåìû (32) îòíîñèòåëüíî âåêòîðà ( )X X k k� �1 è ïîäñòàâèì ïîëó÷åííîå äëÿ íåãî âûðàæåíèå â íèæíþþ ÷àñòü ýòîé ñèñòåìû. Â ðåçóëüòàòå íàéäåì � �s s k k t t k t= m s CR= r F X c � � � �� 1 1 1 1 1 ( ) ( ) �1, m , èëè � �s t s t k t= m s k s s k s = CR + w c w F X w r � � � � � � � � � � � � � � � 1 1 1 1 ( ) 1, m . (33) Òàêèì îáðàçîì, íà êàæäîé èòåðàöèè k �2 3, ,... àëãîðèòì ðåøåíèÿ ñèñ- òåìû óðàâíåíèé (32) ðåàëèçóåòñÿ ïîñðåäñòâîì ïîñëåäîâàòåëüíîãî âûïîë- íåíèÿ òðåõ øàãîâ. Ñ.Å. Ñàóõ 14 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 4 Àëãîðèòì 4. 1. Ðåøåíèå ïîäñèñòåì óðàâíåíèé {w rs s k s m CR � � � 1 1 } , â ñèñòåìå (32) îòíîñèòåëüíî âåêòîð-ñòðîê{ws s m } ,�1 . 2. Ðåøåíèå ïîäñèñòåìû óðàâíåíèé � �s t s t k t= m s k s m =+ w c w F X � � � � � � � � � 1 1 1 1 ( ) , â ñèñòåìå (33) îòíîñèòåëüíî ìíîæåñòâà èñêîìûõ ïàðàìåòðîâ {� s s m } ,�1 . 3. Ðåøåíèå ïîäñèñòåìû óðàâíåíèé CR k k k( ) ( )X X F X� � � �� 1 1 � � � s s k s= m c 1 1 â (32) îòíîñèòåëüíî èñêîìîãî âåêòîðà X k . Îöåíêà âû÷èñëèòåëüíîé ñëîæíîñòè àëãîðèòìîâ CR-îáíîâëåíèÿ ôàêòîðíûõ ìàòðèö. Êàê ïðàâèëî, ïðè íåçíà÷èòåëüíîì êîëè÷åñòâå ñòîëá- öîâ P p p pJ�{ , ,..., }1 2 , ñòðîê Q q q qI�{ , ,..., }1 2 è ðàíãå m îáíîâëåíèÿ èñõîä- íîé ìàòðèöû A, ò.å. ïðè J n�� , I n�� è m n�� ÷èñëî íåíóëåâûõ ýëåìåíòîâ nnz P( )V , nnz Q( )U è nnz m( )W ñîîòâåòñòâóþùèõ ìàòðèö îáíîâëåíèÿVP ,UQ è Wm îêàçûâàåòñÿ ñóùåñòâåííî ìåíüøå ÷èñëà íåíóëåâûõ ýëåìåíòîâ nnz C R( )A A ôàêòîðíûõ ìàòðèö C A è R A îáíîâëåííîé ìàòðèöû A. Äëÿ ðåøåíèÿ âñïîìîãàòåëüíûõ ñèñòåì óðàâíåíèé (13), (24) è (30) òðåáóåòñÿ ñîîòâåòñòâåííî ( )J n 1 2, ( )I n 1 2 è 2 1 2( )m n îïåðàöèé óìíî- æåíèÿ. Äëÿ ðåøåíèÿ ñèñòåì óðàâíåíèé ñ ìàòðèöàìèVP ,UQ , Wm òðåáóåòñÿ 1 3 3J � 1 3 2J J , 1 3 1 3 3 2I I I� , 2 3 2 3 23 2m m m� îïåðàöèé óìíîæåíèÿ íà ôàêòî- ðèçàöèþ è ðåøåíèå ñîîòâåòñòâóþùèõ ïîäñèñòåì óðàâíåíèé, à òàêæå J n J( )� , I n I( )� , 2m n m( )� îïåðàöèé óìíîæåíèÿ íà ïîäñòàíîâêè íàéäåííûõ ðå- øåíèé â îñòàëüíûå óðàâíåíèÿ. Òàêèì îáðàçîì, ÷èñëî îïåðàöèé óìíîæå- íèÿ íà ðåøåíèå îáíîâëåííûõ ñèñòåì óðàâíåíèé áóäåò ñëåäóþùåå: ( ) ( )J n J J J J n J � �1 1 3 1 3 2 3 2 , ( ) ( )I n I I I I n I � �1 1 3 1 3 2 3 2 , 2 1 2 3 2 3 22 3 2( ) ( )m n m m m m n m � � . Î÷åâèäíî, ïðè âûïîëíåíèè óñëîâèé n J�� , n I�� , n m�� ÷èñëî îïåðàöèé óìíîæåíèÿ ìîæíî îöåíèâàòü âåëè÷èíàìè ( )J n 1 2, ( )I n 1 2, 2 1 2( )m n . Îòñþäà ñëåäóåò, ÷òî ïðè äîñòà÷íî áîëüøèõ ðàçìåðíîñòÿõ n èñõîäíîé ìàò- ðèöû A ñîêðàùåíèå ÷èñëà îïåðàöèé ïðè èñïîëüçîâàíèè ìåòîäîâ îáíîâëå- íèÿ ôàêòîðíûõ ìàòðèö ñîñòàâèò ~ ( ) n J 3 3 1 , ~ ( ) n I 3 3 1 , ~ ( ) n m 3 6 1 . Ìåòîäû îáíîâëåíèÿ ñòîëáöîâî-ñòðî÷íûõ ôàêòîðíûõ ìàòðèö ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 4 15 Ïîëó÷åííûå îöåíêè ñâèäåòåëüñòâóþò î ìíîãîêðàòíîì ñîêðàùåíèè ÷èñëà âûïîëíÿåìûõ îïåðàöèé óìíîæåíèÿ ïðè èñïîëüçîâàíèè ïðåäñòàâ- ëåííûõ âûøå ìåòîäîâ îáíîâëåíèÿ ôàêòîðíûõ ìàòðèö âìåñòî ìåòîäà èõ ïîâòîðíîé ôàêòîðèçàöèè. Ðåçóëüòàòû ýêñïåðèìåíòàëüíûõ èññëåäîâàíèé. Â îñíîâó èññëå- äîâàíèé ïîëîæåí ïðîãðàììíûé êîä, íàïèñàííûé íà ÿçûêå Ñ++, â êîòîðîì èìïëåìåíòèðîâàíû èòåðàöèîííàÿ ôîðìóëà (10) ðåøåíèÿ òåñòîâûõ ñèñòåì íåëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé âèäà A x p p T X G e B � �( ) 0 , (34) ôîðìóëû (1) CR-ôàêòîðèçàöèè ðàçðåæåííûõ n n� ìàòðèö A è àëãîðèòì 1 îáíîâëåíèÿ ôàêòîðíûõ ìàòðèö C è R. Ìàòðèöû A âçÿòû ñ âåá-ñàéòà [8]. Äëÿ êàæäîé òàêîé ìàòðèöû â ñèñòåìå óðàâíåíèé (34) âåêòîð B ïðèíÿò ðàâíûì âåêòîðó A1 G ( )1 , ãäå 1 — åäèíè÷- íûé âåêòîð. Âåêòîð G ( )x p ñôîðìèðîâàí èç ñîâîêóïíîñòè íóëåâûõ ýëå- ìåíòîâ, ðàñïîëàãàåìûõ â òåõ æå ïîçèöèÿõ, ÷òî è íóëåâûå ýëåìåíòû ñòîëá- öà A p: ìàòðèö A, è íåíóëåâûõ ýëåìåíòîâ, îïðåäåëÿåìûõ ïîëèíîìèàëüíû- ìè ôóíêöèÿìè âèäà g x i n x i n x i n i p p p� � � � � � � � � � � � � � � � � � � 2 1 2 1 3 1 4 . Èç âîçìîæíûõ ðåøåíèé òåñòîâûõ ñèñòåì óðàâíåíèé (34) âçÿò âåêòîð X 1� . Äëÿ åãî âû÷èñëåíèÿ ïî èòåðàöèîííîé ôîðìóëå (10) íà÷àëüíûå çíà÷åíèÿ ýëåìåíòîâ x i 0 âåêòîðà X 0 äëÿ âñåõ èíäåêñîâ i p� óñòàíàâëèâàåì ðàâíûìè åäèíèöå, à çíà÷åíèå x p 0 — ðàâíûì íóëþ. Ïðèçíàêîì çàâåðøåíèÿ èòåðàöèé ìåòîäà Íüþòîíà ïðèíÿòî âûïîëíåíèå óñëîâèÿ x xp k p k� �� 1 810 . Ïî çàâåðøåíèè èòåðàöèîííûõ âû÷èñëåíèé íàéäåííûå çíà÷åíèÿ ýëåìåí- òîâ èñêîìîãî âåêòîðà X ñîïîñòàâëÿëèñü ñ òî÷íûìè åäèíè÷íûìè çíà÷åíèÿ- ìè è îöåíèâàëàñü íîðìà ïîãðåøíîñòè ðåøåíèé e x ni i n � � � ( )1 2 1 . Âû÷èñëåíèÿ âûïîëíÿëèñü íà êîìïüþòåðå Intel P4 (Chipset Intel 865 PE, FSB 800 MHz, CPU 3.0GHz with HT, Dual Channel Memory 1 GB: 2x512MB, DDR400), ðàáîòàþùåì ïîä óïðàâëåíèåì îïåðàöèîííîé ñèñòåìû Microsoft Windows XP. Îáùèå õàðàêòåðèñòèêè ìàòðèö A è çàòðàòû âû÷èñëèòåëüíûõ ðåñóðñîâ íà èõ CR-ôàêòîðèçàöèþ ïðåäñòàâëåíû â òàáë. 1, à â òàáë. 2 — çàòðàòû íà èòåðàöèîííîå ðåøåíèå òåñòîâûõ ñèñòåì íåëèíåéíûõ óðàâíåíèé (34) â Ñ.Å. Ñàóõ 16 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 4 Ìåòîäû îáíîâëåíèÿ ñòîëáöîâî-ñòðî÷íûõ ôàêòîðíûõ ìàòðèö ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 4 17 Íàçâàíèå ìàòðèöû A ×èñëî èòåðàöèé ìåòîäà Íüòîíà Çàòðàòû âðåìåíè (ñ) íà èòåðàöèîííûå âû÷èñëåíèÿ Óñêîðåíèå âû÷èñëåíèé S, ðàçû Ñðåäíåêâàäðà- òè÷åñêîå îòêëîíåíèå ïîëó÷åííîãî ðåøåíèÿ îò òî÷íîãî ñ ôàêòîðèçàöèåé ìàòðèö � �F/ X X X k� �1 ñ îáíîâëåíèåì ìàòðèö C è R ASIC_680ks 18 1 360, 513 6, 344 226 4,91e-08 ASIC_680k 9 27 323, 799 3, 047 10 087 6,72e-07 ASIC_320ks 139 23 290, 313 54, 563 429 1,73e-12 ASIC_320k 136 101 252, 283 46, 563 2 190 1,67e-12 bcircuit 24 25, 500 2, 500 10 3,88e-11 circuit_4 35 41, 379 1, 531 27 1,87e-09 dc3 20 2 481, 757 1, 953 1337 3,19e-10 hcircuit 37 17, 304 2, 688 6 1,57e-14 largebasis 31 803, 484 30, 984 26 2,46e-12 onetone2 4 46, 858 0, 265 234 1,81e-09 rajat24 31 6 829, 621 13, 531 521 1,86e-11 sherman5 8 3, 426 0, 031 125 9,14e-14 Zhao1 19 4 815, 511 5, 281 961 4,08e-15 Òàáëèöà 2 Íàçâàíèå ìàòðèöû A Ðàçìåðíîñòü n ×èñëî íåíóëåâûõ ýëåìåíòîâ ìàòðèöû Çàòðàòû âðåìåíè íà ôàêòîðèçàöèþ âèäà A = CR, c Íîìåð ñòîëáöà p A C + R ASIC_680ks 682712 1693767 5667160 79,657 50000 ASIC_680k 682862 2638997 6618616 3415,094 50000 ASIC_320ks 321671 1316085 5604966 168,375 5000 ASIC_320k 321821 1931828 5058746 749,672 50000 bcircuit 68902 375558 1049898 1,000 5000 circuit_4 80209 307604 420128 1,172 5000 dc3 116835 766396 1140264 130,516 5000 hcircuit 105676 513072 625005 0,406 50000 largebasis 440020 5240084 22945358 25,750 5000 onetone2 36057 222596 1955857 15,531 500 rajat24 358172 1946979 4105540 227,203 50000 sherman5 3312 20793 178273 0,485 500 Zhao1 33861 166453 12677567 267,235 450 Òàáëèöà 1 ñëó÷àå CR-ôàêòîðèçàöèè ìàòðèö ßêîáè � � � �F / X G / X X X X X� �� k kA1 1 ïî ôîðìóëàì (1) è â ñëó÷àå îáíîâëåíèÿ ôàêòîðíûõ ìàòðèö C è R ïî àëãîðèòìó 1. Êàê âèäíî èç òàáë. 1 è 2, äîñòèãíóòî çíà÷èòåëüíîå ñîêðàùåíèå âðå- ìåíè âû÷èñëåíèé âî âñåõ òåñòîâûõ ïðèìåðàõ â ñëó÷àå ïðèìåíåíèÿ àëãî- ðèòìà îáíîâëåíèÿ. Âåëè÷èíû óñêîðåíèé ñëåäóåò ñîïîñòàâëÿòü ñî ñðåä- íèìè çàòðàòàìè íà âû÷èñëåíèå îäíîãî ýëåìåíòà ôàêòîðíûõ ìàòðèö C è R, ïîñêîëüêó ðåàëèçàöèÿ àëãîðèòìà CR-ôàêòîðèçàöèè ðàçðåæåííûõ ìàòðèö áîëüøîé ðàçìåðíîñòè ñâÿçàíà ñ ñóùåñòâåííûìè ðàñõîäàìè âû÷èñëèòåëü- íûõ ðåñóðñîâ íà âûïîëíåíèå âñïîìîãàòåëüíûõ îïåðàöèé [7]. Ðåçóëüòàòû òàêîãî ñîïîñòàâëåíèÿ ïðåäñòàâëåíû íà ðèñóíêå, ãäå íà ìíî- æåñòâå ïðèìåðîâ ïîêàçàíà ëèíèÿ òðåíäà óñêîðåíèé è åå óðàâíåíèå. Áëèç- êèé ê ëèíåéíîìó õàðàêòåð çàâèñèìîñòè âåëè÷èíû óñêîðåíèÿ âû÷èñëåíèé îò ñðåäíåé âåëè÷èíû çàòðàò íà âû÷èñëåíèå îäíîãî ýëåìåíòà ôàêòîðíûõ ìàòðèö ñâèäåòåëüñòâóåò î öåëåñîîáðàçíîñòè ïðèìåíåíèÿ àëãîðèòìîâ îá- íîâëåíèÿ ôàêòîðíûõ ìàòðèö â ñëó÷àÿõ, êîãäà çàòðàòû íà CR-ôàêòîðè- çàöèþ ìàòðèö ßêîáè ñòàíîâÿòñÿ çíà÷èòåëüíûìè. Âûâîäû Ïðåäëîæåííûå ìåòîäû ñòîëáöîâîãî, ñòðî÷íîãî, ñòîëáöîâî-ñòðî÷íîãî è ìíîãîðàíãîâîãî îáíîâëåíèÿ ôàêòîðíûõ ìàòðèö â ñîâîêóïíîñòè ñ ìåòîäîì CR-ôàêòîðèçàöèè ìàòðèö (íàçîâåì òàêóþ ñîâîêóïíîñòü ìåòîäîâ ìåòîäà- ìè CR-îáíîâëåíèÿ ìàòðèö) îáåñïå÷èâàþò ñóùåñòâåííîå óñêîðåíèå âû- Ñ.Å. Ñàóõ 18 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 4 ASIC_680ks ASIC_680k ASIC_320ks ASIC_320k bcircuit circuit_4 dc3 hcircuit largebasis onetone2 rajat24sherman5 Zhao1 S = 2 10� 7 t 1,01 ,R = 0 9327 1 10 100 1000 10000 100000 1 0E-07, 1 0E-06, 1 0E-05, 1 0E-04, 1 0E-03, t, c S, ðàçû Óñêîðåíèå âû÷èñëåíèé íà ýòàïå èòåðàöèîííîãî ðåøåíèÿ òåñòîâûõ ñèñòåì íåëèíåéíûõ óðàâíåíèé áîëüøîé ðàçìåðíîñòè âèäà (34): t — ñðåäíåå âðåìÿ âû÷èñëåíèé îäíîãî ýëå- ìåíòà ìàòðèö C è R ÷èñëåíèé ïðè ðåøåíèè íåëèíåéíûõ ñèñòåì àëãåáðàè÷åñêèõ óðàâíåíèé èòåðàöèîííûì ìåòîäîì Íüþòîíà. Ìåòîäû CR-îáíîâëåíèÿ íå îêàçûâàþò âëèÿíèÿ íà ñõîäèìîñòü èòåðàöèîííûõ ïðîöåäóð ìåòîäà Íüþòîíà è îáåñ- ïå÷èâàþò âûñîêóþ ýôôåêòèâíîñòü ðåøåíèÿ ñèñòåì óðàâíåíèé áîëüøîé ðàçìåðíîñòè, ñîäåðæàùèõ íåçíà÷èòåëüíóþ ÷àñòü íåëèíåéíûõ ôóíêöèé, îïðåäåëåííûõ íà íåáîëüøîì ïîäìíîæåñòâå èñêîìûõ íåèçâåñòíûõ. A column, row, column-row and multi-rank methods of updating the factor matrices derived from CR-matrix factorization are proposed. We obtain estimates of the computational complexity of the CR-updating methods. The conditions for their effective use in the Newton iterative method for solving nonlinear algebraic equations are determined. The experimental results of using the CR-updating methods of test matrices for solution of large scale systems of nonlinear equations are presented. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. Dantzig G.B., Thapa M.N. Linear programming. 1: Introduction. — NY. : Springer, 1997. — 436 p. 2. Cottle R.W., Pang J.-S., Stone R.E. The Linear Complementarity Problem. — Philadelphia : SIAM, 1992. — 762 p. 3. http://www.springerlink.com/content/978-3-540-35447-1#secion=424811&page=1&loñus=13 4. Eldersveld S.K., Saunders M.A. A block-LU update for large-scale linear programming // SIAM J. on Matrix Analysis and Applications. — 1992. — Vol. 13, ¹ 1. — P. 191—201. 5. http://www.mcs.anl.gov/uploads/cels/papers/P1565.pdf 6. Tewarson R.P., Zhang Yin Sparse quasi-Newton LU updates // Intern. J. for Numerical Methods in Engineering. — 2005. — Vol. 24, ¹ 6. — P. 1093—1100. 7. Ñàóõ Ñ.Å. Ìåòîä CR-ôàêòîðèçàöèè ìàòðèö áîëüøîé ðàçìåðíîñòè // Ýëåêòðîí. ìîäå- ëèðîâàíèå. — 2007. — 29, ¹ 6. — Ñ. 3 — 22. 8. http://www.cise.ufl.edu/research/sparse/matrices/index.html Ïîñòóïèëà 20.06.13 ÑÀÓÕ Ñåðãåé Åâãåíüåâè÷, ä-ð òåõí. íàóê, ãë. íàó÷. ñîòð. Èí-òà ïðîáëåì ìîäåëèðîâàíèÿ â ýíåðãåòèêå èì. Ã.Å. Ïóõîâà ÍÀÍ Óêðàèíû. Â 1978 ã. îêîí÷èë Êèåâñêèé èí-ò èíæåíåðîâ ãðàæäàíñêîé àâèàöèè. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — ÷èñëåííûå îïåðàòîðíûå ìåòîäû ðåøåíèÿ äèôôåðåíöèàëüíûõ óðàâíåíèé, äåêîìïîçèöèîííûå è èòåðàöèîííûå ìåòîäû ðåøåíèÿ ëèíåéíûõ ñèñòåì áîëüøîé ìåðíîñòè, ìàòåìàòè÷åñêîå ìîäåëèðîâàíèå òåõíîëîãè÷åñêèõ ïðî- öåññîâ â ýíåðãåòèêå è ãàçîòðàíñïîðòíûõ ñèñòåìàõ, ýêîíîìèêî-ìàòåìàòè÷åñêèå ìåòîäû ìî- äåëèðîâàíèÿ ôèíàíñîâûõ è ìàêðîýêîíîìè÷åñêèõ ïðîöåññîâ. Ìåòîäû îáíîâëåíèÿ ñòîëáöîâî-ñòðî÷íûõ ôàêòîðíûõ ìàòðèö ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 4 19

Методы обновления столбцово-строчных факторных матриц для ускоренного решения нелинейных систем алгебраических уравнений большой размерности

Institution

Ähnliche Einträge