Методы работы с разреженными матрицами произвольного вида: Учебное пособие к спецкурсу

Ф Е Д Е РАЛ Ь Н О Е АГ Е Н С Т В О П О О БРАЗО В АН И Ю Г О С У Д АРС ТВ Е Н Н О Е О БРАЗО В АТ Е Л Ь Н О Е У ЧРЕ Ж Д Е Н И Е В Ы С Ш Е Г О П РО Ф Е С С И О Н АЛ Ь Н О Г О О БРАЗО В АН И Я «В О РО Н Е Ж С КИ Й Г О С У Д АРС Т В Е Н Н Ы Й У Н И В Е РС И Т Е Т »

Г лушак о ваТ .Н ., Э к саревск ая М .Е .

М ет од ы ра б от ы с ра зреж енны м и м а т рица м и произв ол ьногов ид а

Учебно е по со бие

к спецк урсу по специально ст и «П рик ладная мат емат ик аи инфо рмат ик а» 010501 (010200)

В ороне ж 2005

2 У твер ждено научно-методическим советом 14.06.2005 г.

В Г У ф акул ь тетаП М М п р отокол № 6 от

Автор ы : Э ксар евская М .Е ., Г л уш аковаТ.Н . Н ауч. р ед. Бондар енкоЮ .В .

У чебноеп особиеп одготовл ено накаф едр еВ ы числ ител ь ной математики ф акул ь тетаП М М В ор онежскогогосудар ственного универ ситета. Рекомендуется дл я студентов3 и4 кур совд/оиасп ир антовф акул ь тетаП М М .

3

С од е рж а ни е В ведение.............................................................................................................................4 1. С х емы х р анения .......................................................................................................5 1.1 С х емаКнута.............................................................................................................5 1.2 Раз р еженны й стр очны й ф ор мат.......................................................................5 1.3 Раз р еженны й стол бцовы й ф ор мат..................................................................6 1.4 С жатиеп о Ш ер ману..............................................................................................6 1.5 Г ип ер матр ичная сх ема.........................................................................................7 1.6 О вы числ ител ь ны х з атр атах ..............................................................................7

2. М етоды р еш ения р аз р еженны х систем ал гебр аических ур авнений . Г ауссовоискл ю чение.....................................................................9 2.1 Г ауссово искл ю чение. П остановказ адачи................................................ 10 2.2 Г ауссово искл ю чениеп о стол бцам............................................................... 13 2.3 Г ауссово искл ю чениеп о стр окам ................................................................. 14 2.4 И скл ю чениеГ аусса– Ж ор дана...................................................................... 14 2.5 О ш ибкиокр угл ения вметодеГ аусса.......................................................... 15 2.6 Числ енная устой чивость ивы бор гл авны х эл ементов......................... 20

3. Т еор ия гр аф овдл я р аз р еженны х матр иц.............................................. 23 3.1 С ил ь ны екомп оненты ор гр аф а....................................................................... 25 3.2 И ссл едованиестр атегий дл я несимметр ичны х р аз р еженны х матр иц.............................................................................................................................. 27 3.2.1 П оиск вгл убину наор гр аф е................................................................ 27 3.2.2 П оиск вш ир ину наор гр аф еистр уктур ы ур овней ор иентир ованной смежности..................................................................................................... 30 3.2.3 О ты сканиемаксимал ь ногомножествап утей ср аз л ичны ми вер ш инамивацикл ическом ор гр аф е........................................................... 31 3.2.4 Ал гор итм Х ол л а................................................................................... 32 3.2.5 Ал гор итм Х оп кр оф та– Кар п а............................................................ 34 3.2.6 Ал гор итм С ар джента– У эстер бер га.................................................. 36 3.2.7 Ал гор итм Т ар ь я на................................................................................ 37

С п исок л итер атур ы ..................................................................................................... 43

4

В в едени е П о мер е того как р астут п р оизводител ь ность и бы стр одей ствие вы числ ител ь ны х маш ин, р астут р аз мер ы матр иц. В сп ециал ь ной л итер атур е имеется нескол ь ко оп р едел ений р аз р еженной матр ицы . С уть их состоит в том, что матр ица р аз р ежена, есл и в ней «много» нул евы х эл ементов. Раз р еженную матр ицу можно оп р едел ить как матр ицу, дл я котор ой исп ол ь з ование ал гор итмов, учиты ваю щ их нал ичие нул ей , п оз вол я ет добить ся экономии маш инного вр емени и п амя ти п о ср авнению с тр адиционны миметодами. Раз р еженны е матр ицы встр ечаю тся п р и р еш ении многих важны х п р актических з адач: дискр етизации ур авнений математической ф изики (р аз ностны е сх емы и методы конечны х эл ементов), л иней ного п р огр аммир ования (теор ия оп тимизации), теор ии эл ектр ических цеп ей , стр уктур ного анал иза, числ енного р еш ения диф ф ер енциал ь ны х ур авнений , теор иигр аф ов, атакжегенетики, социол огииип оведенческих наук. В ся кую р аз р еженную матр ицу можно обр абаты вать так, как есл ибы она бы л а п л отной , также вся кую п л отную , ил и з ап ол ненную , матр ицу можно обр абаты вать ал гор итмами дл я р аз р еженны х матр иц. В обоих сл учая х п ол учатся п р авил ь ны е р ез ул ь таты , но вы числ ител ь ны е з атр аты воз р астут. П р ип исы вание матр ице свой ства р аз р еженностиэквивал ентно утвер ждению о сущ ествованииал гор итма, исп ол ь з ую щ его ее р аз р еженность идел аю щ его вы числ ения сней деш евл еп о ср авнению состандар тны миал гор итмами. М атр ичны е ал гор итмы дол жны п р оектир овать ся таким обр аз ом, чтобы х р анил ись иобр абаты вал ись тол ь ко ненул евы е эл ементы ип о воз можности сох р аня л ась р аз р еженность . Конечно, не все ал гор итмы дл я р аз р еженны х матр иц достигаю т этих цел ей . М ногие сх емы х р анения доп ускаю т оп р едел енную дол ю нул ей , иал гор итм обр абаты вает их , как есл ибы онине бы л и нул я ми. Ал гор итм, х р аня щ ий и обр абаты ваю щ ий мень ш ее числ о нул ей , бол ее сл ожен, тр уднее п р огр аммир уется ицел есообр аз ен тол ь ко дл я достаточно бол ь ш их матр иц. С ущ ествует п ол ны й сп ектр ал гор итмов, р ассчитанны х нар аз л ичны етип ы матр иц, от п л отны х до очень р аз р еженны х , ср аз л ичны минеобх одимы мидл я п р актики степ еня ми эф ф ективности, сл ожности ил и п р остоты . В свя з и с р аз витием совр еменной тех ники можно ожидать , что и дал ь ш е бол ь ш ие р аз р еженны е матр ицы будут встр ечать ся во многих п р икл адны х з адачах , вкл ю чаю щ их бол ь ш иесистемы .

5

1. С х ем ы х р анени я Рассмотр им р аз р еженную матр ицу А. Е ененул евы еэл ементы , котор ы х очень мал о в ср авнениис числ ом нул ей , р ассея ны п о всей матр ице, обр аз уя то, что наз ы ваю т по рт рет о м матр ицы ил и шабло но м нулей-ненулей. В се сп особы х р анения р аз р еженны х матр иц з акл ю чаю тся в том, чтобы х р анить тол ь ко ненул евы е эл ементы матр ицы ил и, может бы ть , небол ь ш ое кол ичество нул ей вместесними.

1.1 С хема К н ут а Н енул евы е эл ементы х р аня тся в комп актной ф ор ме и п р оизвол ь ном п ор я дке в одномер ном массиве AN. И нф ор мация о п ол ожении ненул евы х эл ементов может х р анить ся двумя доп ол нител ь ны ми п ар ал л ел ь ны ми одномер ны ми массивами I и J: з десь дл я каждого ненул евого эл емента содер жатся его стр очны й и стол бцовы й индексы . Д л я каждого aij ≠ 0 в п амя тинах одится тр ой ка(aij, i, j). Чтобы можно бы л о л егко оты скивать эл ементы п р оизвол ь ной стр окиил и стол бца матр ицы , необх одимы ещ е п ар а указ ател ей дл я каждой тр ой ки, а также указ ател ивх ода дл я стр ок истол бцов, сообщ аю щ ие начал о каждого стр очного ил истол бцового сп иска. П усть NR – массив, х р аня щ ий стр очны е указ ател и(«сл едую щ ий ненул евой эл емент той же стр оки»), а NC – массив стол бцовы х указ ател ей («сл едую щ ий ненул евой эл емент того же стол бца»). П я ть массивов AN, I, J, NR и NC имею т одинаковую дл ину, и их одноименны е п оз ициисоответствую т др уг др угу. П усть JR иJC – массивы , содер жащ ие указ ател и вх ода дл я стр ок и стол бцов, р асп ол оженны е в соответствиисп ор я дком стр ок истол бцовматр ицы . П р иисп ол ь з ованииданной сх емы эл емент aij можно най ти, л иш ь вх одя в сп исок i-й стр оки и п р осматр ивая его до тех п ор , п ока не будет най ден стол бцовы й индекс j, л ибо то же самоес п ер еменой р ол ей стр окиистол бца. О бр атная з адача имеет очевидное р еш ение: есл и з адан номер п оз иции k эл ементаAN(k), то его стр очны й истол бцовы й индексы – I(k) иJ(k). С х емаКнутатр ебует п я тия чеек п амя тидл я каждого ненул евого эл емента А п л ю с к этому указ ател ивх ода дл я стр ок истол бцов. В сл едствие бол ь ш ой накл адной п амя титакая сх емавесь манеэкономна. Д остоинстваеев том, что в л ю бом месте можно вкл ю чить ил и искл ю чить эл емент, и можно эф ф ективно сканир овать стр окиистол бцы . С х ема идеал ь но п р исп особл ена дл я сл учаев, когда А стр оится каким-то ал гор итмом, где нел ь з я п р едсказ ать конечноечисл о ип оз ицииненул евы х эл ементов.

1.2 Р а зреж ен н ы й ст ро чн ы й ф о рма т Раз р еженны й стр очны й ф ор мат – это одна из наибол ее ш ир око исп ол ь з уемы х сх ем х р анения р аз р еженны х матр иц. Э та сх ема п р едъя вл я ет минимал ь ны е тр ебования к п амя ти и в то же вр емя оказ ы вается очень удобной дл я нескол ь ких важны х оп ер аций над р аз р еженны ми матр ицами:

6

сл ожения , умножения , п ер естановок стр ок истол бцов, тр ансп онир ования , р еш ения систем с р аз р еженны миматр ицамикоэф ф ициентов как п р я мы ми, так и итер ационны ми методами и т.д. Значения ненул евы х эл ементов матр ицы исоответствую щ ие стол бцовы е индексы х р аня тся в этой сх еме п о стр окам в двух массивах AN иJA. И сп ол ь з уется такжемассив указ ател ей IA, отмечаю щ их п оз иции массивов AN и JA, с котор ы х начинается оп исание очер едной стр оки. Д оп ол нител ь ная комп онента в IA содер жит указ ател ь п ер вой свободной п оз ициивJA иAN. О п исание r-й стр оки А х р анится в п оз иция х с IA(r) до IA(r + 1) – 1 массивов JA иAN, з аискл ю чением р авенства IA(r + 1)=IA(r), оз начаю щ его, что r-я стр ока п уста. Е сл иматр ица А имеет m стр ок, то IA содер жит m + 1 п оз иций ; IA(1) всегдар авно единице. Д анны й сп особ п р едставл ения наз ы ваю т по лным, п оскол ь ку п р едставл ена вся матр ица А. В з ависимостиот того, как з ап исы ваю тся в каждой стр оке стол бцовы е индексы в массиве JA (п о п ор я дку воз р астания ил и нет), р аз л ичаю т упо рядо ченно е ил и неупо рядо ченно е предст авление соответственно. Н еуп ор я доченны е п р едставл ения нужны дл я ал гор итмических удобств: р ез ул ь таты бол ь ш инства матр ичны х оп ер аций п ол учаю тся неуп ор я доченны ми, иуп ор я дочениеих тр ебует доп ол нител ь ны х з атр ат маш инного вр емени, в то вр емя как бол ь ш инство ал гор итмов дл я р аз р еженны х матр иц не тр ебует, чтобы п р едставл ения бы л и уп ор я доченны ми.

1.3 Р а зреж ен н ы й ст о лбцо вы й ф о рма т Э л ементы матр ицы А х р аня тся п о стол бцам. С тол бцовы е п р едставл ения могут р ассматр ивать ся и как стр очны е п р едставл ения тр ансп онир ованны х матр иц. Таким обр аз ом, в массиве ANT х р аня тся ненул евы е эл ементы матр ицы A, в массиве JAT указ ы вается стр очны й индекс соответствую щ его эл емента, а эл ементы IAT указ ы ваю т, с какой п оз ицииначинается оп исаниеочер едного стол бцаматр ицы А.

1.4 С ж а т ие по Ш ерма н у С х ема Ш ер мана исп ол ь з уется дл я х р анения р аз р еженны х тр еугол ь ны х матр иц, вы числ я емы х в методе Г аусса. Н иж ней треуго льно й мат рицей наз ы вается матр ица, у котор ой ненул евы е эл ементы могут стоя ть тол ь ко в нижнем тр еугол ь нике и на гл авной диагонал и (aij=0 п р и j>i). Верхняя т реуго льная мат рица– матр ицасненул евы миэл ементамитол ь ко ввер х нем тр еугол ь нике ина гл авной диагонал и(aij=0 п р иj
7

Чтобы избежать п овтор ной з ап исиодинаковы х п осл едовател ь ностей стол бцовы х индексов, Ш ер ман п р едл ожил комп актную сх ему х р анения этих индексов, тр ебую щ ую доп ол нител ь ного массива указ ател ей . Д иагонал ь ны е эл ементы U х р аня тся вмассивеUD, авнедиагонал ь ны еэл ементы п о стр окам – в массиве UN. М ассив IU содер жит указ ател и дл я UN, оп р едел я емы е обы чны м обр аз ом. С тол бцовы е индексы , отвечаю щ ие нах одя щ имся в UN ненул евы м эл ементам, х р аня тся вJU вкомп актной ф ор ме. Теп ер ь между UN и JU нет п р я мого соответствия . С тол бцовы е индексы вы бир аю тся из JU с п омощ ь ю доп ол нител ь ного массива указ ател ей IJ. Н ескол ь ко стр ок оп исы ваю тся вJU одним итем женабор ом стол бцовы х индексов. Числ енны е з начения эл ементов i-ой стр окинах одя тся в UN в п оз иция х от IU(i) до IU(i + 1) – 1, стол бцовы е индексы нах одя тся в JU, начиная с п оз иции IJ(i). Ал гор итм искл ю чения систематически п ор ождает набор ы стр ок, имею щ их одинаковую стр уктур у сп р ава от некотор ого стол бца, тем самы м, п р едоставл я я неп оср едственно инф ор мацию , необх одимую дл я п остр оения комп актной сх емы .

1.5 Гиперма т ричн а я схема Г ип ер матр ичная сх ема п ол учается , есл и А х р анится как матр ица, эл ементами котор ой снова я вл я ю тся матр ицы . О тл ичие гип ер матр ичной сх емы х р анения в том, что вместо числ енны х з начений эл ементов нужно х р анить инф ор мацию о р асп ол ожении и р аз мер ах п одматр иц. С ами п одматр ицы , эл ементамикотор ы х будут уже числ а, х р аня тся в соответствии с некотор ы м стандар тны м ф ор матом. О собы й интер ес п р едставл я ет сл учай , когда А, матр ица из п одматр иц, р аз р ежена. Тогда дл я А можно п р именить р аз р еженное п р едставл ение, сох р аня емое в оп ер ативной п амя ти, в то вр емя как п одматр ицы , так же как в некотор ом р аз р еженном п р едставл ении, р аз мещ аю тся в п ер иф ер ий ной п амя ти и внося тся в оп ер ативную , тол ь ко когда этого тр ебует вы п ол нение ал гор итма. Э тот вар иант наз ы вается свер х р аз р еженной сх емой . В се гип ер матр ичны е сх емы п оз вол я ю т обр аботку очень бол ь ш их з адач п р и умер енны х з ап р осах к п амя ти. И х гл авное достоинство состоит в л егкости, с какой п ол ь з овател ь может умень ш ить п амя ть ил ивр емя (ценой увел ичения др угой из этих х ар актер истик), дл я чего достаточно в соответствиис имею щ ей ся п амя ть ю з адать бол ее мел кое ил и бол еегр убоер аз биение.

1.6 О вы числит ельн ы х за т ра т а х Занимая сь тех нол огией р аз р еженны х матр иц, важно з нать объем п амя ти, тр ебуемой ал гор итмом, и числ о оп ер аций , п р оизводимы х п р и его вы п ол нении. П р и п одсчете оп ер аций числ о дел ений вкл ю чается в числ о умножений , а числ о вы читаний – в числ о сл ожений . С л ожения с нул я ми также учиты ваю тся п р и п одсчете сл ожений , а воз можны е вз аимны е уничтожения ненул евы х эл ементов не п р инимаю тся во внимание. Рез ул ь таты , п ол учаю щ иеся в некотор ы х сл учая х , п р иведены в табл ицах 1 и 2.

8

Т а бли ца 1: О бъе м па м я т и и чи сло опе ра ци й д ля фа кт ори за ци и . С ум м и рова ни е прои звод и т ся от i =1 д о i = n – 1 включи т е льно. М атр ицаА Зап ол ненная несимметр ичная Л енточная несимметр ичная , диагонал ь ны й вы бор гл авного эл емента Л енточная несимметр ичная , частичны й вы бор гл авногоэл емента Раз р еженная несимметр ичная

Числ о умножений и дел ений 1 3 1 n − n 3 3 ( β + 1) βn − 2 3 β −β2 − 3 1 − β 3 ≤ (2 β + 1)βn − 13 − β3 − 6 3 1 − β2 − β 2 3 U ∑ ri + 1 c Lj −

(

)

Числ о сл ожений

О бъем п амя ти

1 3 1 2 1 n − n + n 3 2 6 2 β 2n − β 3 − 3 1 2 1 − β + β 2 6

n2

≤ 2β 2 n − −β2 +

13 3 β − 6

1 β 6

∑ riU c Lj

(2 β + 1)n − β 2 − β

≤ (3β + 1)n − 5 3 − β2 − β 2 2

(

n + ∑ riU + c Lj

)

Т а бли ца 2: Ч и сло опе ра ци й д ля пря м ой и обра т ной под ст а новки . С ум м и рова ни е провод и т ся от i = 1 д о i = n – 1 включи т е льно. М атр ицаА

Числ о умножений

Зап ол ненная симметр ичная ил и n2 несимметр ичная Л енточная симметр ичная ил и (2 β + 1)n − β 2 − β несимметр ичная сдиагонал ь ны м вы бор ом гл авного эл емента Л енточная несимметр ичная , 5 3 ≤ (3β + 1)n − β 2 − β частичны й вы бор гл авного эл емента 2 2 U L Раз р еженная несимметр ичная n + ∑ (ri + c j )

Числ о сл ожений n2 – n 2 βn − β 2 − β

3 βn −

5 2 3 β − β 2 2 U L ri + c j

∑(

)

Г де riU = числ о внедиагонал ь ны х ненул евы х эл ементов в i-й стр окематр ицы U, c Lj = числ о внедиагонал ь ны х ненул евы х эл ементов в j-м стол бце матр ицы L, n = п ор я док матр ицы . β = обеп ол уш ир ины л енты (ш ир инал енты р авна2β + 1). Д л я п л отны х матр иц всеэл ементы р ассматр иваю тся как ненул евы е, даже есл иих з начение может бы ть р авны м нул ю . В се эл ементы , р асп ол оженны е

9

внутр и л енты в л енточной матр ице, также р ассматр иваю тся как ненул евы е. В обоих сл учая х можно оп ускать оп ер ации над нул евы ми эл ементами, вы п ол ня я тем самы м мень ш ее числ о оп ер аций , чем указ анное в табл ицах . О днако такой сп особ обр аботкитр ебует доп ол нител ь ной п р овер ки дл я каждого эл емента, и суммар ная стоимость вы числ ений скор ее увел ичится , чем умень ш ится , есл идол я нул евы х эл ементовневел ика. Г л авны е эл ементы вы бир аю тся на диагонал и в п ор я дке воз р астания номер а, есл ип р иня т «диагонал ь ны й вы бор гл авного эл емента. О днако, когда матр ица несимметр ичная , обы чно необх одимы м я вл я ется вы бор k-го гл авного эл емента из k-го стол бца р едуцир ованной матр ицы с п осл едую щ ей его п ер естановкой в диагонал ь ную п оз ицию п оср едством п ер естановкидвух стр ок. Т р ебуемая п амя ть вэтом сл учаедол жнабы ть достаточнадл я х р анения нижней п ол ул енты ш ир ины β и вер х ней п ол ул енты ш ир ины до 2β. Э тот сл учай вы дел ен в табл ицах 1 и2 как «частичны й вы бор гл авного эл емента», ип р иведенны е там ф ор мул ы даю т л иш ь вер х ние оценкиобъема п амя тии числ а оп ер аций , так как р еал ь ная ш ир ина вер х ней п ол ул енты может не достигать з начения 2β. В табл ице 1 дл я матр ицы A п р иводя тся данны е, отвечаю щ ие ф актор изации A=LU. О ценка объема п амя ти вкл ю чает все те эл ементы , котор ы ер ассматр иваю тся как ненул евы е, но невкл ю чает накл адны ез атр аты п амя ти, п одчас весь ма ощ утимы е, есл и п р именя ю тся свя з ны е сп иски ил и р аз р еженны е ф ор маты х р анения . В о всех сл учая х доп ол нител ь но тр ебую тся n я чеек п амя ти дл я вы п ол нения п р я мой ил и обр атной п одстановки. Рез ул ь таты дл я ф актор изации матр ицы и дл я р еш ения системы даю тся отдел ь но др уг от др уга, так как в п р икл адны х з адачах может п отр ебовать ся вы п ол нить ф актор изацию з аданной матр ицы тол ь ко один р аз из атем р еш ить бол ь ш оекол ичествол иней ны х систем ср аз л ичны мип р авы мичастя ми.

2. М етоды р еш ени я р азр еж енны х с и с тем алгебр аи чес ки х ур ав нени й. Гаус с ов о и с ключени е Д л я оты скания р еш ения хсистемы Ax = b,

(1)

гдеА – невы р ожденная квадр атная вещ ественная матр ицар аз мер овn×n, аb – з аданны й вектор , сущ ествует бол ь ш ое кол ичество ал гор итмов. Э ти ал гор итмы можно р аз дел ить на два кл асса: п р я мы е методы иитер ационны е методы . П рямые мет о ды основаны на гауссовом искл ю чении: в р ез ул ь тате вы п ол нения п осл едовател ь ностиш агов ур авнения ил инеизвестны е системы модиф ицир ую тся до тех п ор , п ока не будет най дено р еш ение. В ит ерацио нных мето дах обы чно вы бир ается начал ь ное п р ибл ижение дл я х, котор оез атем ул учш ается , п оканебудет достигнутадостаточная точность . В каждом частном сл учае оба этих п одх ода имею т как п р еимущ ества, так и недостатки, итр удно установить общ иеп р авил адл я оп р едел ения того, какой

10

из них окажется бол ее п одх одя щ им. М ы п р я мы х методовдл я р еш ения ур авнения (1).

огр аничимся

р ассмотр ением

2.1 Га уссо во исклю чен ие. По ст а н о вка за да чи Реш ение ур авнения (1) может бы ть з ап исано в виде x=A-1b, но я вное исп ол ь з ование этой ф ор мы з ап исип р оизводится тол ь ко в сл учае небол ь ш их з начений n (скажем, n ~ 100 имень ш е). М атр ицаA-1 часто я вл я ется п л отной , даже есл иA – р аз р еженная матр ица, иее я вное вы числ ение ведет к п отер е п р еимущ еств, свой ственны х р аз р еженному сл учаю . Д л я бол ь ш инствасистем указ анны е п р еимущ ества извл екаю тся из того ф акта, что нет необх одимости п ол учать A-1 в я вном виде; достаточно вы р аз ить A-1 чер ез п р оизведение матр иц, котор ы е п р осты м сп особом умножаю тся на вектор . Конечно, такая п р оцедур а оказ ы вается бол ее удобной , так как матр ичны е сомножител и я вл я ю тся р аз р еженны ми ип р и х р анении все они могут бы ть п омещ ены в з начител ь но мень ш ий объем п амя ти, чем одна матр ица A-1. Кр оме того, п р оизведение матр ичны х сомножител ей на вектор b тр ебует мень ш е оп ер аций , чем вы числ ениеп р оизведения A-1b. О бы чны м сп особом р еш ения ур авнения (1) п р я мы м методом я вл я ется вы числ ениетр еугол ь ного р аз л ожения матр ицы А: A = LU,

(2)

гдеU – вер х ня я тр еугол ь ная матр ицасдиагонал ь ны миэл ементами, р авны ми единице, аL – нижня я тр еугол ь ная . В этом сл учаеA-1 = U-1L-1 иx = U-1ω , где ω =L-1b. Т аким обр аз ом, р еш ение ур авнения (1) оп р едел я ется в р ез ул ь тате р еш ения л иней ной системы Lω = b

(3)

относител ь но ω , аз атем – л иней ной системы Ux = ω (4) относител ь но x. Е сл иматр ица A р аз р ежена, то р аз р еженны мибудут также иматр ицы L и U, х отя степ ень их р аз р еженностиобы чно мень ш еп о ср авнению с матр ицей A. Раз л ожение (2) единственно, есл и оно сущ ествует и матр ица A невы р ождена. Часто из матр ицы L вы носится в качестве множител я диагонал ь ная матр ица D, так что L=L'D, гдеL' я вл я ется нижней тр еугол ь ной матр ицей , вседиагонал ь ны еэл ементы котор ой р авны единице. У р авнение(2) вэтом сл учаеп р инимает сл едую щ ий вид: A=L'DU. Реш ениесистемы (3) наз ы вается прямо йпо дст ано вк о й. Т ак как матр ицаL – нижня я тр еугол ь ная , то п ер воеур авнениеимеет сл едую щ ий вид: l11ω 1 = b1, где l11≠0 в сил у того, что мы п р едп ол агаем невы р ожденность матр ицы A. О тсю да п ол учаем ω 1=b1/l11. Т еп ер ь можно вы честь п ер вы й стол бец матр ицы L, умноженны й на ω 1, из вектор а b. У р авнение (3) п р еобр аз уется в

11

тр еугол ь ную систему п ор я дка(n –1) с угл овой гл авной п одматр ицей матр ицы L в качествематр ицы коэф ф ициентов. Т еп ер ь можно вы числ ить ω 2, ип р иведенны ер ассуждения могут п овтор я ть ся р екур р ентно идал ее, п окане будет з авер ш ено вы числ ение всех комп онент вектор а ω . Е сл и обоз начить чер ез nL числ о внедиагонал ь ны х ненул евы х эл ементов матр ицы L, то можно убедить ся в том, что п р я мая п одстановка тр ебует n оп ер аций дел ения , nL оп ер аций умножения иnL оп ер аций сл ожения . П р я мая п одстановка может р ассматр ивать ся как ал гор итм, вы п ол ня емы й в n ш агов, в р ез ул ь тате чего п осл едовател ь но вы числ я ю тся вектор ы b(1) ≡ b, b(2), … , b(n); п р иэтом п ер вы е k комп онент вектор ов b(k+1) иb(k) совп адаю т. Н а k-м ш аге, k = 1, 2, … , n, вы п ол ня ю тся сл едую щ иевы числ ения :

(

)

ω k = bk( k ) / l kk (1 + ε ), ( k +1) i

b

=b

(k ) i

− lik ω k + f i ; i = k + 1,Κ , n, (k )

где ε и f i (k ) – соответствую щ ие вы числ ител ь ны е ош ибки. Н икаких п р едп ол ожений относител ь но р аз р еженностивектор ов b иω мы не дел аем. О п ер ации, вы п ол ненны енадэл ементом bi, п р иводя т к соотнош ению ((bi − li1ω1 + f i (1) − Κ − li ,i −1ω i −1 + f i (i −1) ) / lii )(1 + ε ) = ω i ,

котор оеможноп ер еп исать ввиде i −1

i

k =1

k =1

bi + ∑ f i ( k ) = ∑ lik ω k − liiω i

ε , 1+ ε

гдеп р иi = 1 суммир ованиев л евой частидол жно бы ть оп ущ ено. О п р едел им вектор ош ибок δ b скомп онентами i −1

δbi = ∑ f i ( k ) + liiω i k =1

δb1 = l11ω1

ε ; i > 1, 1+ ε

ε . 1+ ε

Тогдавы числ енны й р ез ул ь тат ω удовл етвор я ет точному соотнош ению Lω = b + δ b.

(*)

Е сл и известен вектор ω , то систему (4) можно р еш ить п р и п омощ и о братно й по дст ано вк и. Так как мы п р едп ол агаем, что матр ица U имеет единичную диагонал ь , то п осл еднееур авнение(4) имеет видxn=ω n, так что xn известно. В ы читая п р оизведение п осл еднего стол бца матр ицы U на ω n из вектор а ω , мы п р их одим к тр еугол ь ной системе п ор я дка (n – 1) с ведущ ей

12

гл авной п одматр ицей матр ицы U в качестве матр ицы коэф ф ициентов. П р одол жая указ анны еп р еобр аз ования р екур р ентно, мы п ол учаем р еш ениеx. О боз начив чер ез nU числ о внедиагонал ь ны х ненул евы х эл ементов матр ицы U, можно п оказ ать , что обр атная п одстановка тр ебует nU умножений иnU сл ожений . О бр атную п одстановку можно р ассматр ивать как ал гор итм, вы п ол ня емы й з аn ш агов, вр ез ул ь татечего п осл едовател ь но вы числ я ю тся вектор ы ω (n) ≡ ω , ω (n-1), … , ω (2), ω (1); п р иэтом, начиная с k-й из аканчивая n-й , комп оненты вектор овω (k) иω (k-1) совп адаю т. Н аk-м ш аге, k = n, n – 1, … , 1, вы п ол ня ю тся сл едую щ иевы числ ения : xk = ω k(k ) , ω i( k −1) = ω i( k ) − uik xk + g i( k ) ; i = 1,..., k − 1,

где g i(k ) – ош ибка, воз никш ая в р ез ул ь тате вы п ол нения вы числ ений с п л аваю щ ей з ап я той . Рез ул ь тат оп ер аций , вы п ол ненны х над эл ементом ω i, i
ил и ωi +

n

n

k =i +1

k =i

∑ g i( k ) = ∑ uik xk ; i < n.

Таким обр аз ом, есл иоп р едел ить вектор ош ибок δ ω : δω i =

n

g i( k ) ; i < n, ∑ k =i +1

δω n = 0,

то можно з ап исать сл едую щ ее точное соотнош ение между вы числ енны ми вел ичинами: Ux = ω + δ ω .

(**)

Д л я п р остоты будем п р едп ол агать , что матр ица А л иней ной системы (1) уже п одготовл ена дл я искл ю чения , в том смы сл е, что диагонал ь ны е эл ементы могут бы ть неп оср едственной исп ол ь з ованы в качестве гл авны х эл ементоввтом п ор я дке, вкаком онир асп ол ожены . В общ ем сл учаегл авны е эл ементы вы бир аю тся ср еди ненул евы х эл ементов матр ицы А, п р ичем эл емент, вы бр анны й в качестве гл авного, п ер еводится нагл авную диагонал ь п оср едством п ер естановки стр ок и стол бцов. В ы бор гл авны х эл ементов

13

осущ ествл я ется таким обр аз ом, чтобы в п р оцессе искл ю чения сох р аня л ась р аз р еженность иобесп ечивал ась числ енная устой чивость .

2.2 Га уссо во исклю чен ие по ст о лбца м Г ауссово искл ю чение п о стол бцам состоит из n ш агов. В р ез ул ь тате вы п ол нения k-го ш ага искл ю чаю тся все ненул евы е эл ементы матр ицы , р асп ол оженны е в k-м стол бце п оддиагонал ь ю . Н а п ер вом ш аге ненул евы е эл ементы п ер вого стол бца матр ицы A ≡ A(1) искл ю чаю тся п оср едством п оэл ементного вы читания п ер вой стр оки, умноженной на соответствую щ ие скал я р ы , из всех остал ь ны х стр ок, имею щ их ненул евой эл емент в п ер вом стол бце. Э л емент a11, нах одя щ ий ся в стр оке, котор ая вы читается из остал ь ны х стр ок и в стол бце, п оддиагонал ь ны е эл ементы котор ого искл ю чаю тся , наз ы вается главным элемент о м. П р едп ол агается , что он отл ичен от нул я . П ер ед искл ю чением п ер вая стр ока нор мир уется п утем дел ения всех ее ненул евы х эл ементов на гл авны й эл емент. П осл е искл ю чения п ол учается матр ицаA(2), дл я котор ой ai(12) = 0 п р иi > 1 иa11( 2 ) = 1 . ( 2) Н а втор ом ш аге в качестве гл авного вы бир ается эл емент a 22 . П р иэтом ( 2) вновь п р едп ол агается , что a22 ≠ 0 . В тор ая стр ока нор мир уется , и все ненул евы е эл ементы втор ого стол бца, р асп ол оженны е ниже диагонал и, искл ю чаю тся п р и п омощ и вы читания из соответствую щ их стр ок нор мир ованной втор ой стр оки, умноженной на п одх одя щ ие множител и. ( 2) = 0 , то эл ементы п ер вого стол бцанеизменя т п р и Заметим, что п оскол ь ку a21 этом своих з начений . П ол учается матр ица А(3), у котор ой ai(13) = 0 п р иi > 1, ( 3) (3) ai(23) = 0 п р иi > 2 и a11 = a22 = 1 . Т.е. в своих п ер вы х двух стол бцах матр ица (3) А я вл я ется вер х ней тр еугол ь ной сединичной диагонал ь ю . В начал е k-го ш ага матр ица А(k) имеет нул евы е эл ементы в п ер вы х k – 1 стол бцах п оддиагонал ь ю иединичны еэл ементы в п ер вы х k – 1 п оз иция х на диагонал и. Н аk-м ш агевкачествегл авного вы бир ается эл емент akk(k ) . Затем k-я стр ока нор мир уется , и п оддиагонал ь ны е эл ементы в k-м стол бце матр ицы A(k) искл ю чаю тся п утем вы читания умноженной на п одх одя щ ие скал я р ы нор мир ованной k-й стр окииз всех стр ок, имею щ их ненул евы еэл ементы в kм стол бце п од диагонал ь ю . П ол учается матр ица A(k+1) с нул евы ми эл ементамив п ер вы х k стол бцах ниже диагонал иис единицамив п ер вы х k п оз иция х надиагонал и. Э тот п р оцесс п р одол жается до тех п ор , п ока в конце n-го ш ага не п ол учится матр ица A(n+1), котор ая содер жит нул евы е эл ементы п од диагонал ь ю и единичны е эл ементы на диагонал и, я вл я я сь , таким обр аз ом, вер х ней тр еугол ь ной с единичной диагонал ь ю . О тсю да п ол учается ф актор изованная ф ор ма матр ицы А: А = LU, где U≡ A(n+1) – вер х ня я тр еугол ь ная матр ица с единичной диагонал ь ю , п р ичем u kj = akj( k +1) п р и j > k. В ы р ажения дл я эл ементовматр ицы L можноп ол учить из ур авнений :

14

lik = a

(k ) ik

п р иi ≥ k.

(4')

М ожно п ол учить ф ор мул у, п оказ ы ваю щ ую , как вы р ажается A(k+1) чер ез A(k): aij( k +1) = aij( k ) − lik u kj , i > k , j > k ,

откудаможно вы вестип ол ны евы р ажения дл я эл ементовматр ицы A(k): a

(k ) ij

k −1

= aij − ∑ lim u mj , i > k , j > k . m =1

2.3 Га уссо во исклю чен ие по ст ро ка м Д л я р аз р еженны х матр иц, х р аня щ их ся в стр очном ф ор мате, искл ю чение п о стр окам намного бол ее эф ф ективно, чем искл ю чение п о стол бцам. В обоих сл учая х п ол учаю тся одинаковы ечисл енны ер ез ул ь таты , и з атр ачивается одно и то же кол ичество ар иф метических оп ер аций . П овы ш ение эф ф ективностидостигается з а счет того, что эл ементы матр ицы исп ол ь з ую тся в естественном п ор я дке, т.е. в том п ор я дке, в каком х р аня тся . Г ауссово искл ю чение дл я матр ицы А п о стр окам вы п ол ня ется в n ш агов. В начал еk-го ш агаимеется матр ицаA(k), содер жащ ая встр оках сп ер вой п о (k – 1)-ю нул евы еэл ементы л евеедиагонал ииединицы вп ер вы х (k – 1) п оз иция х надиагонал и. Н аk-м ш агеп р оизводится искл ю чениененул евы х эл ементовkй стр оки, р асп ол оженны х л евее диагонал и, п утем вы читания вз я ты х с соответствую щ имимножител я мип ер вой стр оки, втор ой стр оки, … , (k – 1)-й стр оки в указ анном п ор я дке. Затем каждая стр ока нор мир уется п утем дел ения всех ееэл ементовнадиагонал ь ны й эл емент.

2.4 Исклю чен ие Га усса – Ж о рда н а Ал гор итм искл ю чения Г аусса – Ж ор дана п о стол бцам анал огичен гауссову искл ю чению п о стол бцам; гл авноеотл ичиесостоит втом, что п ер ед k-м ш агом матр ица A(k) имеет нул евы е эл ементы в стол бцах от п ер вого до kго как ниже, так ивы ш е диагонал и. Ш аг с номер ом k ал гор итма состоит в искл ю ченииненул евы х эл ементов k-го стол бцаматр ицы A(k), р асп ол оженны х как вы ш е, так иниже диагонал и. С начал а нор мир уется k-я стр ока, дл я чего все ее эл ементы дел я тся на диагонал ь ны й эл емент, нах одя щ ий ся в п оз иции (k, k). Затем нор мир ованная k-я стр окаумножается нап одх одя щ иескал я р ы и вы читается из всех стр ок, имею щ их ненул евы е эл ементы в k-м стол бце как вы ш е, так и ниже диагонал и. Т аким обр аз ом, п ол учается матр ица A(k+1) с нул я ми во внедиагонал ь ны х п оз иция х п ер вы х k стол бцов. О п исанны й п р оцессп р одол жается до тех п ор , п ока в р ез ул ь тате вы п ол нения п осл еднего ш аганеп ол учится единичная матр ицаA(n+1) ≡ I. И скл ю чение Г аусса – Ж ор дана может также п р оизводить ся п о стр окам. С тол бцовая вер сия исп ол ь з ует сл ожение k-й стр оки, умноженной на

15

некотор ы е числ а, со всеми остал ь ны ми стр оками дл я того, чтобы уничтожить ненул евы е внедиагонал ь ны е эл ементы k-го стол бца. Концеп туал ь но этот п р оцесс можно п онимать как констр уир ование новы х ур авнений , я вл я ю щ их ся л иней ны ми комбинация ми исх одны х . С др угой стор оны , п р и искл ю чении Г аусса – Ж ор дана п о стр окам k-й стол бец, умноженны й на некотор ы е числ а, скл ады вается со всеми остал ь ны ми стол бцами таким обр аз ом, что внедиагонал ь ны е эл ементы k-й стр оки становя тся нул евы ми. Э тот п р оцесс можно тр актовать как констр уир ование новы х неизвестны х , котор ы е я вл я ю тся л иней ны микомбинация миисх одны х иудовл етвор я ю т л иней ны м ур авнения м, некотор ы е коэф ф ициенты котор ы х нул евы е.

2.5 Ош ибки о круглен ия в мет о де Га усса Е сл ичисл о с п л аваю щ ей з ап я той з ап исы вается в п амя ть комп ь ю тер а, то сох р аня ется л иш ь некотор ое ф иксир ованное кол ичество его стар ш их з начащ их циф р . Когда над числ ами a и b, х р аня щ имися в п амя ти комп ь ю тер а, вы п ол ня ется какая -то оп ер ация , п ол ученны й р ез ул ь тат п ер ед з ап ись ю в я чей ку п амя ти необх одимо п р едвар ител ь но п одвер гнуть окр угл ению ил и усечению . Д л я указ анного тип а ош ибок гр аницы обы чно устанавл иваю тся сл едую щ им обр аз ом: f1(aΒb)=(aΒb)(1 + ε),

(5)

где символ Β обоз начает одну из эл ементар ны х оп ер аций , чер ез (aΒb) обоз начен точны й р ез ул ь тат оп ер ации, f1(aΒb) обоз начает р ез ул ь тат, п ол ученны й п осл е вы п ол нения оп ер ации с п л аваю щ ей з ап я той и п осл едую щ его усечения ил и окр угл ения , и |ε| ≤ εМ , где εМ – маш инная точность . П р и вы читании из числ а а п р оизведения двух др угих чисел l и u с исп ол ь з ованием ар иф метикисп л аваю щ ей з ап я той п ол учается вел ичина b=f1(a - lu),

(6)

где a, l и u – точны е з начения , х р аня щ иеся в п амя ти комп ь ю тер а, а b – вы числ енноез начение. О ш ибкае оп р едел я ется соотнош ением b=a – lu + е,

(7)

где п р едп ол агается , что оп ер ации над числ ами, х р аня щ имися в п амя ти комп ь ю тер а, вы п ол ня ю тся точно. П р едп ол агается , что вел ичины a и b огр аничены : |a|, |b| ≤ αМ . (8)

16

И з соотнош ений (5) и(6) п ол учаем где

b=(a– lu(1+ε1))(1+ε2),

(9)

|ε1|, |ε2| ≤ εМ . (10) Так как нал ичие гр аниц дл я l и u не п р едп ол агается , мы искл ю чаем п р оизведениеlu из ур авнения (7) п р ип омощ исоотнош ения (9), ивы р ажаем е из п ол ученного соотнош ения :   ε 1  − a 1 . е = b1 − 1 + ε1  (1 + ε 1 )(1 + ε 2 ) 

И сп ол ь з уя гр аницы дл я a иb, з аданны енер авенством (8), п ол учаем  ε 1 e ≤ α M  1 − + 1 (1 + ε 1 )(1 + ε 2 ) 1 + ε 1 

 .  

У читы вая гр аницы дл я ε1 и ε2, оп р едел я емы е нер авенствами (10), и п р едп ол агая , что εМ < 1, мы п ол учаем п осл е некотор ы х п р еобр аз ований оценку e ≤ αMεM

1 1− εM

 1   + 2  . 1− εM 

Рассмотр им эл емент аij матр ицы А, над котор ой п р оизводится ш аг гауссова искл ю чения п о стол бцам с вы бор ом гл авны х эл ементов неп оср едственно вдол ь диагонал и. Ал гор итм искл ю чения п о стол бцам вз я т в качестве п р имер а, изл агаемы е ниже методы и р ез ул ь таты сох р аня ю т сил у такжедл я искл ю чения п о стр окам. П одр аз умевается , что эл емент aij(k ) каждой из р едуцир ованны х матр иц A(k), гдеA(1)≡A, х р анится в одной итой жея чей ке п амя ти. Н аk-м ш аге, гдеk<min(i,j), мы дел им k-ю стр оку нагл авны й эл емент (k ) akk(k ) из ап оминаем вел ичину u kj ≡ akj( k +1) = a kj( k ) / a kk на месте, где бы л з ап исан эл емент a kj(k ) . О п ер ация , вы п ол ня емая надэл ементом aij(k ) на k-м ш аге, п р и исп ол ь з ованииар иф метикисп л аваю щ ей з ап я той з ап исы вается в сл едую щ ем виде: aij( k +1) = aij( k ) − lik u kj + eij( k ) ,

(11)

где lik = aik(k ) п р и i ≥ k. Рез ул ь таты , п ол ученны е вы ш е, п оз вол я ю т оценить ош ибку eij(k ) , воз никш ую ввы числ ения х сп л аваю щ ей з ап я той .

17

О п р едел им дл я

этого вел ичины aij( k ) ≤ α ij

α ij = max k aij( k ) , так что

(12)

п р и k ≤ min(i, j). В частности, дл я k = 1 эти оценки сп р аведл ивы дл я эл ементов исх одной матр ицы A ≡ A(1). О ценка (12) оп р едел я ет гр аницы тол ь ко дл я эл ементовматр ицы L, но недл я эл ементовU. Ф актически, есл и i ≥ j = k, то lik = aik(k ) в сил у (4') из начение |lik| огр аничено вел ичиной αik. С др угой стор оны , есл и k = i < j, то u kj = akj( k ) / lkk , ип оэтому п р оизведение|lkkukj| огр аничено вел ичиной αkj, однако дл я вел ичины ukj, котор ая может бы ть вел ика, гр аницу п ол учить неудается . Е сл инекотор ы й эл емент матр ицы A р авен нул ю , ип оз иция , в котор ой он р асп ол ожен, не п одвер гается з ап ол нению в п р оцессе искл ю чения , то соответствую щ ие эл ементы матр ицы L ил и U, р асп ол оженны е в той же п оз иции, будут в точностир авны нул ю . Бол ее того, надэтим эл ементом не п р оизводится никаких ар иф метических оп ер аций , и соответственно не воз никаю т п огр еш ности, оп р едел я емы еур авнением (11). М ы будем отл ичать этот сл учай от др угого сл учая , когда какой -л ибо эл емент матр иц L ил иU становится р авны м нул ю в р ез ул ь тате сл учай ного вз аимного уничтожения обр аз ую щ их его сл агаемы х , вэтом сл учаеп огр еш ность п р исутствует, так как в соответствую щ ей п оз иции п р оисх одил о з ап ол нение. Такой эл емент матр ицы будет р ассматр ивать ся как ненул евой . С л учай ное вз аимное уничтожение п р оисх одит р едко (з а искл ю чением сп ециф ических сл учаев), и вр я д л и стоит п ы тать ся я вно учиты вать его. Таким обр аз ом, ненул евы м считается эл емент, отл ичны й от нул я л ибо р авны й нул ю в р ез ул ь тате вз аимного уничтожения , в то вр емя как нул евы м считается тот эл емент, котор ы й с самого начал а бы л р авен нул ю и котор ы й не п одвер гал ся дей ствию з ап ол нения . Заметим, что есл их отя бы одно из з начений lik ил иukj р авно нул ю , то ур авнение (11) не оп р едел я ет никакого изменения эл емента aij(k ) , и, таким обр аз ом, eij( k ) = 0 . (13) У р авнение (11) вы р ажает точное соотнош ение между вы числ енны ми вел ичинами, оно не отр ажает вл ия ния общ ей ош ибки, доп ущ енной п р и вы числ ении aij( k +1) . Д ей ствител ь но, дл я того чтобы оценить общ ую ош ибку, необх одимо бы л о бы учесть ош ибки, доп ущ енны е п р ивы числ ениивел ичин aij(k ) , lik и ukj. О ш ибка eij(k ) , дл я котор ой вы ш е бы л и установл ены гр аницы , я вл я ется нечем ины м, как р аз ность ю между вы числ енны м з начением aij( k +1) и тем з начением aij( k +1) , котор ое бы л о бы п ол учено, есл ибы над вел ичинами aij(k ) , lik иukj вы п ол ня л ись точны еар иф метическиеоп ер ации.

18

В ажное свой ство р аз р еженного искл ю чения оп исы вается соотнош ением (13), котор ое указ ы вает на то, что мал ое числ о оп ер аций , п р оизводимое над кажды м эл ементом, п р иводит к не стол ь уж бол ь ш ому накоп л ению ош ибки. И менно это свой ство дел ает воз можны м р еш ениеочень бол ь ш их р аз р еженны х систем п р я мы ми методами без чр ез мер ного р оста ош ибок окр угл ения . Д л я того чтобы осущ ествить систематический анал из указ анногосвой ства, оп р едел им матр ицу с цел очисл енны миэл ементамиnij: m

nij = ∑ nij( k ) ,

(14)

k =1

где nij( k ) = 1 , есл ииlik, иukj отл ичны от нул я ; nij( k ) = 0 , вп р отивном сл учае; m = min(i, j). Кажды й р аз , когда на k-м ш аге п р оизведение likukj вы числ я ется из атем вы читается из эл емента, р асп ол оженного в п оз иции(i, j), к этому эл ементу п р ибавл я ется ош ибка eij(k ) . Е сл и j > i, то (i, j)-й эл емент изменя тся п осл едний р аз на i – 1-м ш аге, а на i-м ш аге этот эл емент дел ится на диагонал ь ны й эл емент lii из ап оминается вкачествез начения uij. Т аким обр аз ом, оп ер ации, вы п ол ненны енадэл ементом, дл я котор ого j > i, даю т сл едую щ ий р ез ул ь тат:

((a

ij

) )

− l i1u1 j + eij(1) − l i 2 u 2 j + eij( 2) − Κ − l i ,i −1u i −1, j + eij( i −1) / l ii (1 + ε ) = u ij ,

(15)

где множител ь (1 + ε) введен дл я того, чтобы учесть , согл асно соотнош ению (5), ош ибку, воз никаю щ ую п р и вы п ол нениидел ения на lii. У р авнение (15) можноп ер еп исать ввиде i −1

i

k =1

k =1

aij + ∑ eij( k ) = ∑ lik u kj − lii u ij

ε , 1+ ε

(16)

где в частном сл учае i = 1 суммир ование в л евой части оп ускается . О п р едел им матр ицу ош ибок E сэл ементамиeij сл едую щ им обр аз ом: i −1

eij = ∑ eij( k ) + lii u ij k =1

ε , 1+ ε

(17)

где j > i. Е сл и эл емент uij я вл я ется ненул евы м, то числ о вы читаемы х чл енов в ур авнении(15) р авно в точностиnij – 1 (так как lii ≠ 0 ип оэтому в ф ор мул е (14) nij( i ) = 1 ). С умма в ф ор мул е (17) ф актическисодер жит nij – 1 сл агаемы х . Е сл ижеэл емент uij р авен нул ю , то з ап ол нениенеп р оисх одит иnij( k ) = 0 п р иk < i; кр ометого, nij( i ) = 0 всил у uij = 0; таким обр аз ом, nij = 0. Рассмотр ение сл учая j ≤ i п р оводится анал огично. О п ер ации, вы п ол ненны енадэл ементом aij, п р иводя т к сл едую щ ему р ез ул ь тату: aij − li1u1 j + eij(1) − li 2 u 2 j + eij( 2 ) − Κ − l i , j −1u j −1, j + eij( j −1) = lij . (18)

19

У р авнение (18) вы р ажает тот ф акт, что в качестве з начения lij п р инимается р ез ул ь тат вы п ол нения п осл едовател ь ностиоп ер аций тип а (11). Д л я j ≤ i оп р едел им j −1

eij = ∑ eij( k ) .

(19)

k =1

Е сл иэл емент lij ненул евой , то в сил у того, что ujj = 1 ≠ 0 и nij( j ) = 1 в (14), сумма в (19) содер жит nij – 1 чл енов. Е сл иже эл емент lij р авен нул ю , то в р ассматр иваемой п оз ицииз ап ол нения неп р оисх одит, так что nij = 0 иeij = 0. Н аконец, п одставл я я (17) в(16) и(19) в(18), можноз ап исать LU=A+E.

(20)

Рассмотр им невя з ку r = Ax – b дл я р еш ения x системы (1), вы числ енного с исп ол ь з ованием ар иф метикис п л аваю щ ей з ап я той . И з ур авнений (20), (*) и(**) п ол учаем r = - Ex + Lδ ω + δ b. В з я в1-нор му ил и4-нор му, имеем оценку ||r|| ≤ ||E|| ||x|| + ||L|| ||δ ω || + ||δ b||. П ол ожим ω Mi = max k ω i( k ) , так что ω i( k ) ≤ ω Mi ;1 ≤ i ≤ n;1 ≤ k ≤ n.

В частности, дл я k = i п ол учаем ω i(i ) = xi , так что |xi| ≤ ω Mi. П усть также ω M р авно наибол ь ш ему из чисел ω Mi, т.е. ω i( k ) ≤ ω M ; i = 1,2,..., n; k ≥ i.

(20')

И з (20') п ол учаем сл едую щ иегр аницы дл я нор м вектор аx: x 1 ≤ nω M , x

∞

≤ ωM .

М ожно дать др угую интер п р етацию вектор а невя з киr. П усть ~x – точное р еш ениесистемы (1), тогда A~x = b и r = A(x − ~ x ).

20

С л едовател ь но, x−~ x = A −1r ≤ A −1 r ,

и есл и доступ на оценка дл я нор мы ||А-1||, то можно най ти гр аницу нор мы п огр еш ностир еш ения x − ~x .

2.6 Числен н а я уст о йчиво ст ь и вы бо р гла вн ы х элемен т о в И ссл едуем теп ер ь наибол ее р асп р остр аненны е стр атегии вы бор а гл авного эл емента с точки з р ения числ енной устой чивости. Ак т ивная по дмат рицанаk-м ш агевкл ю чает в себя всеэл ементы aij(k ) , дл я котор ы х i ≥ k, j ≥ k. Э л ементы активной п одматр ицы будем наз ы вать ак т ивными элемент ами. Д л я изл ожения нам п отр ебую тся сл едую щ ие четы р е п одмножестваэл ементовактивной п одматр ицы : Spc – п одмножество, состоя щ ее из тех ненул евы х эл ементов активной п одматр ицы , ср еди котор ы х осущ ествл я ется п оиск. Э то п одмножество оп р едел я ется с цел ь ю сокр ащ ения объема п оиска п р и вы бор е гл авного эл емента, что п р иводит к умень ш ению тр удоемкостивы бор а; Sst – п одмножество эл ементов из Spc, удовл етвор я ю щ их некотор ому усл овию устой чивости; Ssp – п одмножество эл ементов из Spc, удовл етвор я ю щ их некотор ому кр итер ию сох р анения р аз р еженности; Spiv = Sst 1 Ssp – множество, из котор ого вы бир ается гл авны й эл емент. Э л ементы этого множество удовл етвор я ю т как тр ебования м сох р анения р аз р еженности, так иусл овия м устой чивости. О п р едел ения множествSst иSsp необя з аны бы ть нез ависимы ми. И ногдаSst оп р едел я ется как п одмножество Ssp, ил и наобор от. Г л авны й эл емент вы бир ается из множества Spiv. Е сл иэто множество содер жит бол ее одного эл емента, вновь п р инимаю тся во вниманиесообр ажения р аз р еженности, ина их основеп р оизводится окончател ь ны й вы бор . Т аким обр аз ом, тр удоемкость п онижается настол ь ко, наскол ь ко это воз можно, з а счет ул учш ения р аз р еженности, в то вр емя как усл овия устой чивости п о-п р ежнему удовл етвор я ю тся . Е сл ина некотор ом этап е оказ ы вается , что множество Spiv п усто, то тр ебования р аз р еженности осл абл я ю тся , и множество Ssp п ер еоп р едел я ется . В ы бр анны й кр итер ий устой чивости не дол жен бы ть сл иш ком жестким стем, чтобы множество Sst бы л о достаточно ш ир оким. Н а п р актике я вное оп р едел ение указ анны х четы р ех множеств обы чно не п р оизводится , так как оказ ы вается воз можны м исп ол ь з ование уп р ощ енны х п р оцедур . П р ипо лно м выбо ре главно го элементамножество Spc наk-м ш агесостоит из всех ненул евы х эл ементов активной п одматр ицы . Н енул евой эл емент, имею щ ий наибол ь ш ую абсол ю тную вел ичину, скажем aij(k ) , вы бир ается в качестве k-го гл авного эл емента и п ер емещ ается в п оз ицию (k, k) п утем п ер естановкиi-й иk-й стр ок и j-го иk-го стол бцов. М ножество Sst состоит из

21

единственного эл емента a , и множество Ssp обя з ател ь но дол жно содер жать этот эл емент. В сл учае п ол ного вы бор а гл авного эл емента р ост эл ементовматр ицогр аничен сл едую щ им обр аз ом (k ) ij

(

aij( k −1) ≤ k 1 / 2 2131 / 2 Κ k 1 /( k −1)

)

1/ 2

a 0 < 2k (ln k + 2 ) / 4 a 0 ,

где a0 = max|aij|. И стинная вер х ня я гр аница намного мень ш е. У каз анная стр атегия гар антир ует тесны е гр аницы дл я вел ичин aij в (12), но не я вл я ется удовл етвор ител ь ной с точкиз р ения сох р анения р аз р еженности, так как не дает никакой свободы дл я уп р авл ения степ ень ю з ап ол нения . П ол ны й вы бор гл авного эл емента р екомендуется п р именя ть л иш ь дл я п л отны х матр иц небол ь ш ого р аз мер а, когда гл авной цел ь ю я вл я ется достижение наил учш ей числ енной устой чивости. Ч астичный выбо р главно го элемент а з акл ю чается в оты скании наибол ь ш его п о модул ю эл емента в каком-л ибо стол бце (ил и стр оке) активной п одматр ицы с п осл едую щ им вы п ол нением соответствую щ их п ер естановок. Л иния вы бор агл авного эл емента(п одл инией п одр аз умевается стр ока ил и стол бец) оп р едел я ется из сообр ажений сох р анения р аз р еженности. Таким обр аз ом, множество Spc содер жит все активны е ненул евы еэл ементы , так как дл я оты скания л иниивы бор агл авного эл емента нужно п р оизвести п р осмотр всей активной п одматр ицы . М ножество Ssp содер жит в точности все ненул евы е эл ементы л инии вы бор а гл авного эл емента. М ножество Sst в этом сл учае я вл я ется п одмножеством Ssp: оно содер жит наибол ь ш ие п о модул ю эл ементы из Ssp. М ножество Spiv совп адает с Sst. И з ур авнения (11) (п р енебр егая вел ичиной eij(k ) ) можно вы вести сл едую щ ую оценку, сп р аведл ивую , есл и исп ол ь з уется частичны й вы бор гл авногоэл емента: aij( k +1) ≤ 2 max aij( k ) . i, j

Э таоценкагар антир ует, что накаждом ш агеэл ементы могут увел ичить ся не бол ее чем в два р аз а, и, таким обр аз ом, в итоге увел ичение п р оизой дет не бол ее чем в 2ν р аз , где ν = max(nij) – 1 – максимал ь ное числ о оп ер аций , вы п ол ненны х над кажды м отдел ь но вз я ты м эл ементом. О днако дей ствител ь ны й р ост эл ементов оказ ы вается , как п р авил о, гор аз до бол ее медл енны м, и есл итр ебуется п ол учить бол ее точны е гр аницы ош ибок, то необх одимо осущ ествл я ть контр ол ь вел ичины эл ементов матр иц ил и исп ол ь з овать х ор ош ий сп особ оценкивел ичины эл ементов. Частичны й вы бор гл авного эл емента п оз вол я ет исп ол ь з овать некотор ы е п р еимущ ествар аз р еженного сл учая , однако воз можностиэтой сх емы все же сл иш ком огр аничены . Без сущ ественного ух удш ения р ез ул ь татов удается п ол учить бол ее гибкую сх ему, есл и исп ол ь з овать страт егию по ро го во го выбо ра главно го элемента. В этой стр атегии все ненул евы е эл ементы активной п одматр ицы вкл ю чаю тся в множество Spc. В ы бир ается п ар аметр доп устимостиu, л ежащ ий в п ол уинтер вал е 0 < u ≤ 1, иSst оп р едел я ется как

22

множество всех эл ементов a сл едую щ их усл овий :

(k ) ij

из Spc, удовл етвор я ю щ их

одному

из

aij( k ) ≥ u max a (pjk ) ,

(21а)

aij( k ) ≥ u max aiq( k ) .

(21б)

k ≤ p≤n

k ≤q ≤n

М ножество Ssp оп р едел я ется нез ависимо, обы чно на основе какого-л ибо вар ианта кр итер ия М ар ковица. О кончател ь ны й вы бор гл авного эл емента п р оизводится из множества Spiv = Sst 1 Ssp, п р ичем оп я ть п р ивл екаю тся сообр ажения сох р анения р аз р еженности. Затем вы бр анны й эл емент п ер емещ ается в п оз ицию (k, k) п р ип омощ ип ер естановок. Е сл имножество Spiv оказ ы вается п усты м, то Sst дол жно бы ть р асш ир ено п оср едством умень ш ения з начения u. Н а п р актике, однако, р аботу этой п р оцедур ы ор ганизую т др угим сп особом. С начал а вы бир ается эл емент из Spc, наил учш ий с точки з р ения сох р анения р аз р еженности. Затем п р овер я ется , вы п ол ня ю тся л и усл овия (21) дл я этого эл емента. Е сл и усл овия (21) удовл етвор я ю тся , то вы бр анны й эл емент п р инимается вкачествегл авного. В п р отивном сл учае вы бир ается новы й эл емент исх одя из сообр ажений сох р анения р аз р еженности. О днако п осл едня я ситуация встр ечается ср авнител ь но р едко идоп ол нител ь ны й п оиск не вносит бол ь ш ого вкл ада в общ иез атр аты п р иусл овии, что вы бр ано р аз умноез начениеu. Значениеu=1 отвечает стр атегии частичного вы бор а гл авного эл емента. С читается , что конкр етны й вы бор u не я вл я ется очень кр итичны м, иобы чно р екомендуется вы бир ать з начение u = 0.25. Значение u = 0.1 п оз вол я ет п ол учить х ор ош ее сох р анение как р аз р еженности, так иустой чивости, однако мал ы е з начения , нап р имер u=0.01, можно исп ол ь з овать в сл учае небол ь ш их з начений вел ичины ν = max(nij) – 1, встр ечаю щ их ся в з адачах л иней ного п р огр аммир ования . eij(k ) в ур авнении (11) и п р едп ол агая П р енебр егая вел ичиной сп р аведл ивость усл овий (21), п ол учаем оценку

(

)

aij( k +1) ≤ 1 + u −1 max aij( k ) , i, j

котор ая гар антир ует, что р ост эл ементов матр иц на каждом ш аге огр аничен множител ем (1 + u-1), иобщ ее увел ичение п р оисх одит не бол ее чем в (1 + u1 ν ) р аз . Д ей ствител ь ны й р ост эл ементов обы чно п р оисх одит намного медл еннее. П ор оговы й вы бор гл авного эл ементая вл я ется весь мап оп ул я р ной стр атегией иисп ол ь з уется вбол ь ш инствестандар тны х п р огр амм. Д ве др угие стр атегии вы бор а гл авного эл емента бы л и п р едл ожены Зл атевы м. Э тистр атегииз авися т от п ар аметр аустой чивости u, вы бир аемого в п р едел ах 0
23

Spc состоит из ненул евы х эл ементов p стр ок активной п одматр ицы . В ы бор указ анны х p стр ок осущ ествл я ется из сообр ажений ул учш ения р аз р еженности, нап р имер , это могут бы ть p стр ок, имею щ их наимень ш ее кол ичество ненул евы х эл ементов на k-м ш аге искл ю чения . У сл овия устой чивости, исп ол ь з уемы е дл я того, чтобы оп р едел ить , какие эл ементы из Spc п р инадл ежат множеству Sst, те же, что ив стр атегиип ор огового вы бор а гл авного эл емента п о стр окам, и оп р едел я ю тся нер авенством (21б). М ножество Ssp оп р едел я ется как п одмножество Sst на основе сл едую щ его кр итер ия , обесп ечиваю щ его л окал ь ную оп тимизацию р аз р еженности: считается , что эл емент aij(k ) из Sst п р инадл ежит Ssp, есл иμij ≡ (ri – 1)(cj – 1) = μ, гдеμ=mini,j(μij), ri – числ о активны х ненул евы х эл ементов в i-й стр окена k-м ш аге искл ю чения , аcj – числ о активны х ненул евы х эл ементов в j-м стол бце на k-м ш аге искл ю чения . Д р угими сл овами, множество Ssp содер жит все ненул евы е эл ементы из Sst, дл я котор ы х п р оизведение числ а всех остал ь ны х ненул евы х эл ементов в той же стр оке на числ о всех остал ь ны х активны х ненул евы х эл ементов в том же стол бце минимал ь но (п ер ед начал ом вы п ол нения k-го ш ага). В этом сл учаемножествоSpiv совп адает сSsp. С т рат егия З лат ева з акл ю чается в вы бор е в качестве гл авного л ю бого эл емента из Spiv. Улучшенная страт егия З лат ева исп ол ь з ует в качестве гл авного эл емент из Spiv, имею щ ий наибол ь ш ее абсол ю тное з начение. О бы чно обе стр атегии даю т п р имер но одинаковую точность , однако ул учш енная стр атегия п оз вол я ет п ол учить л учш ие р ез ул ь таты в некотор ы х тр удны х сл учая х , так как устр аня ю тся «п л ох ие» п осл едовател ь ностигл авны х эл ементов, доп ускаемы еп ер вой стр атегией .

3. Теор и я гр аф ов для р азр еж енны х м атр и ц Е сл и свой ства матр ицы A неизвестны , воз можно, имеет смы сл п оп ы тать ся до начал а искл ю чения п ер еуп ор я дочить ее к бл очной нижней тр еугол ь ной ф ор ме. Л иней ная система с бл очной нижней тр еугол ь ной матр ицей бл очногоп ор я дкаN имеет вид  A11 A  21  Μ   AN 1

A22 Ο

  x1   b1    x  b   2= 2,   Μ  Μ     ANN   x N  bN 

где эл ементами я вл я ю тся матр ицы , кажды й квадр атны й

п ор я дка ni, и

N

ni = n . ∑ i =1

диагонал ь ны й

(22)

бл ок Aii –

С истему (22) можно р еш ать как

п осл едовател ь ность N мень ш их з адач. Задача i имеет п ор я док ni иматр ицу коэф ф ициентов Aii, i=1,2,… , N. П р и этом з ап ол нение будет п р оисх одить тол ь ко в диагонал ь ны х бл оках , даже есл ивы бор гл авны х эл ементов вы з вал несимметр ичны е п ер естановкистр ок истол бцов каждого бл ока. П р оцедур а такова:

24

(1) Реш ить п ер вую п одсистему, дл я котор ой А11 я вл я ется матр ицей коэф ф ициентов, относител ь но п ер вы х n1 неизвестны х . В ы числ ить вектор x1 п ор я дкаn1. (2) В ы честь п р оизведение Aj1x1 из j-й п р авой частидл я j = 2, … , N. Будет п ол учена бл очная нижня я тр еугол ь ная матр ица п ор я дка N – 1, ип р оцедур а п овтор я ется , п оканебудет вы числ ено п ол ноер еш ение. С л едует сдел ать п р едп ол ожение о невы р ожденностидиагонал ь ны х бл оков в системе(22). М атр ицаимеет по лную трансверсаль, есл ивсееедиагонал ь ны еэл ементы не р авны нул ю . Т рансверсаль есть в точности множество ненул евы х диагонал ь ны х эл ементов. В ся кую невы р ожденную матр ицу A п оср едством несимметр ичны х п ер естановок с п одх одя щ ими матр ицами P и Q можно п ер еуп ор я дочить так, чтобы PAQ имел а п ол ную тр ансвер сал ь . О бр атное невер но. Когда матр ица A з аданной л иней ной системы (1) имеет п ол ную тр ансвер сал ь , бл очную нижню ю тр еугол ь ную ф ор му (22) можно п ол учить п утем симметр ичны х п ер естановок вида PAPT. Е сл и сущ ествует бл очная ф ор ма, то A наз ы ваю т разло ж имо й мат рицей. Н екотор ы е матр ицы не могут бы ть п р иведены к (нетр ивиал ь ной ) бл очной нижней тр еугол ь ной ф ор ме. Э то п очти всегда так дл я систем, п ол ученны х дискр етизацией диф ф ер енциал ь ны х ур авнений с частны мип р оизводны ми. В др угих сл учая х р аз л ожимость матр ицы может бы ть известнаиз ееп остр оения . Е сл и A содер жит нул и на гл авной диагонал и, то необх одимо п ол учить п ол ную тр ансвер сал ь , п р ежде чем п ы тать ся п ер еуп ор я дочить матр ицу к бл очной ф ор ме. П ол учение п ол ной тр ансвер сал и тр ебует несимметр ичны х п ер естановок. М атр ицу, доп ускаю щ ую несимметр ичное п ер еуп ор я дочение к ф ор ме с п ол ной тр ансвер сал ь ю , а з атем симметр ичное п ер еуп ор я дочение к бл очной нижней тр еугол ь ной ф ор ме, будем наз ы вать дво як о разло ж имо й. Теор ия гр аф ов игр ает важную р ол ь в анал изе р аз р еженны х несимметр ичны х матр иц. С о вся кой несимметр ичной матр ицей , имею щ ей п ол ную тр ансвер сал ь , можно свя з ать ор иентир ованны й гр аф , ил и ор гр аф . О р гр аф инвар иантен относител ь но симметр ичны х п ер естановок стр ок и стол бцов матр ицы , меня ется л иш ь его п омечивание. О р гр аф может бы ть р аз бит на сил ь ны е комп оненты , соответствую щ ие диагонал ь ны м бл окам бл очной нижней тр еугол ь ной ф ор мы (22) данной матр ицы . М атр ица р аз л ожима тогда и тол ь ко тогда, когда ее ор гр аф может бы ть р аз бит на сил ь ны е комп оненты . О бе з адачи – п р иведение р аз р еженной матр ицы и р аз биение ор гр аф а – эквивал ентны , идл я обеих исп ол ь з ую тся одниите же ал гор итмы . Е сл и матр ица не имеет п ол ной тр ансвер сал и, то с ней можно ассоциир овать двудол ь ны й гр аф . Д вудол ь ны й гр аф инвар иантен относител ь но несимметр ичны х п ер естановок матр ицы , и п ол учение тр ансвер сал иэквивал ентно оты сканию п ар осочетаний вдвудол ь ном гр аф е. П р иведем нескол ь ко оп р едел ений , котор ы е нам п отр ебую тся в дал ь ней ш ем.

25

Г раф G = (V, E) состоит из множества V вер ш ин u, v, ω , … и множестваE р ебер , гдеребро м наз ы вается п ар а(u, v) вер ш ин из V. Г р аф G = (V, E) наз ы вается о риент иро ванным графо м ил и о рграфо м, когдап ар ы его вер ш ин, п р едставл я ю щ иер ебр а, уп ор я дочены . П о луст епенью захо давер ш ины v наз ы вается числ ор ебер , з ах одя щ их вv. П о луст епень исхо да– это числ ор ебер , исх одя щ их из v. М атрицадо стиж имо стей R ор гр аф а– это бул еваматр ица, оп р едел я емая сл едую щ им обр аз ом: rij = 1, есл иvj достижима из vi в ор гр аф е, и rij = 0 в п р отивном сл учае. О р гр аф наз ы ваю т слабо связным, есл и свя з ен соответствую щ ий неор иентир ованны й гр аф , п ол учаемы й удал ением ор иентациир ебер . Е сл иимеется ор иентир ованное р ебр о (u → v), то говор я т, что вер ш ина v смеж насu. Е сл иW – п одмножество вер ш ин G, то смеж но е мно ж ество дл я W, обоз начаемое чер ез Adj(W), – это множество вер ш ин, не п р инадл ежащ их W, но смежны х свер ш инамииз W. П усть даны G = (V, E) иWδV, тогда Adj(W) = {v ∈ V − W ∃u ∈ W : ∃(u → v) ∈ E}.

3.1 С ильн ы е ко мпо н ен т ы о ргра ф а Рассмотр им сл або свя з ны й ор гр аф G = (V, E). О р гр аф G наз ы ваю т сильно связным, есл идл я л ю бой п ар ы вер ш ин v,ω 0V сущ ествует п уть из v вω ип уть из ω в v, т.е. v иω вз аимно достижимы . П оскол ь ку п уть из v в ω вместесп утем из ω в v составл я ю т цикл , то сил ь ны й свя з ны й ор гр аф можно оп р едел ить и как ор гр аф , в котор ом дл я вся кой п ар ы вер ш ин сущ ествует цикл , содер жащ ий обе вер ш ины . М атр ица достижимостей сил ь но свя з ного ор гр аф а состоит из одних единиц. В общ ем сл учае ор гр аф G может не бы ть сил ь но свя з ны м. С ильно связно й к о мпо нент о й ил и сильно й к о мпо ненто й наз ы вается G частичны й гр аф в G, я вл я ю щ ий ся сил ь но свя з ны м и не доп ускаю щ ий р асш ир ения без п отер и этого свой ства. Частичны й гр аф содер жит все р ебр а G вида (v, ω ), такие что обе вер ш ины v, ω п р инадл ежат ему. И з оп р едел ения сил ь ной комп оненты вы текает сущ ествование цикл а, котор ому п р инадл ежат л ю бы е две з аданны е вер ш ины комп оненты . И з него вы текает также, что л ю бой цикл в G дол жен бы ть цел иком составл ен из вер ш ин данной сил ь ной комп оненты , л ибо, наобор от, цел иком составл ен из вер ш ин G, ей не п р инадл ежащ их . В самом дел е, есл ибы сущ ествовал цикл , содер жащ ий вер ш ину v сил ь ной комп оненты и вер ш ину ω , не п р инадл ежащ ую ей , то мы могл и бы добавл ением ω р асш ир ить сил ь ную комп оненту без п отер исил ь ной свя з ности, что п р отивор ечит оп р едел ению . Э то свой ство исп ол ь з уется дл я вы дел ения сил ь ны х комп онент: вначал е в G нах одя т цикл , а з атем наскол ь ко воз можно р асш ир я ю т его, иссл едуя др угие цикл ы . С л або свя з ны й ор гр аф G = (V, E) можно р аз бить насил ь ны екомп оненты C1, C2,… , Cs снеп ер есекаю щ имися множествамивер ш ин. Е сл иG сам сил ь но свя з ан, то s=1, исил ь ная комп онента тол ь ко одна. В п р отивном сл учае G доп ускает р аз биениеиs>1. Ребр о (v → ω ) я вл я ется выхо до м ил ионо исх одит из сил ь ной комп оненты C=(Vc,Ec), есл иv0Vc, аω ⌠Vc. Ребр о(v → ω ) есть вхо д

26

(ил ижеоно з ах одит в C), есл и v⌠Vc, аω 0Vc. Т ак как сил ь ная комп онента– это частичны й гр аф , то вх оды ивы х оды не п р инадл ежат никакой сил ь ной комп оненте. Е сл и G доп ускает р аз биение, то дол жна сущ ествовать х отя бы одна сил ь ная комп онента, не имею щ ая вы х одов. Д ей ствител ь но, есл ибы каждая комп онента имел а вы х од, то мы смогл и бы п р осл едить п уть от одной комп оненты к др угой , з атем к тр еть ей ит.д., п ока, наконец, не достигл ибы одной из комп онент, где уже бы л и п р ежде. Ц икл , п ол ученны й таким обр аз ом, п р отивор ечит оп р едел ению сил ь ны х комп онент. В общ ем сл учае может сущ ествовать нескол ь ко комп онент без вы х одов. Будем говор ить , что всесил ь ны екомп оненты без вы х одовп р инадл ежат ур овню 1. П р одол жая р ассуждать п одобны м обр аз ом, мы можем з акл ю чить , что ср едиоставш их ся сил ь ны х комп онент G дол жна сущ ествовать х отя бы одна такая , что каждое исх одя щ ие из нее р ебр о з ах одит в некотор ую комп оненту ур овня 1. В ообщ е говор я , таких комп онент может бы ть нескол ь ко, и мы будем говор ить , что все онип р инадл ежат ур овню 2. С р едикомп онент G, не вх одя щ их ни в ур овень 1, ни в ур овень 2, дол жна бы ть х отя бы одна, из котор ой все вы х оды ведут в ур овни1 и2. П о кр ай ней мер е, один из этих вы х одов дол жен з ах одить в ур овень 2, иначе комп онента п р инадл ежал а бы ур овню 2, ап о наш ему п р едп ол ожению , это нетак. Н аз ванная комп онентаи, есл и най дутся , все др угие с теми же свой ствами обр аз ую т ур овень 3. Заметим, что у комп онент ур овня 3 могут отсутствовать вы х оды , ведущ ие в ур овень 1. Е сл и п р одол жить оп исанную п р оцедур у, то будет п ол учена ст рук т урауро внейсвязно ст и, где: L1 = {Ci | Ci неимеет вы х одов}, Ll = {Ci | есл и(u → v) – вы х одиз Ci иv0Cj, тоCj0Ll', гдеl' < l}, l = 2, 3, … , m. О п р едел ение п одр аз умевает, что л ю бая сил ь ная комп онента ур овня l > 1 дол жнаиметь , п о мень ш ей мер е, один вы х од, ведущ ий в ур овень l – 1. Числ о m наз ы вается длино й разбиения. С тр уктур а ур овней свя з ности ор гр аф а единственна. Будем говор ить , что вер ш ина v гр аф а G нах одится в ур овне l ил и что У р овень (v)=l, есл и v п р инадл ежит сил ь ной комп оненте ур овня l. Е сл и(v → ω ) – р ебр о ор гр аф а, то У р овень (v) = У р овень (ω ) тогда итол ь ко тогда, когда v и ω п р инадл ежат одной и той же сил ь ной комп оненте, в п р отивном сл учае, У р овень (ω ) < У р овень (v). С ил ь ная комп онента ур овня l может бы ть достигнутатол ь ко р ебр ами, исх одя щ имииз ур овней l + 1, … , m, однако может сл учить ся , что сил ь ная комп онентанеимеет вх одов, дажеесл и ееур овень l < m. Д р угую стр уктур у ур овней свя з ности можно оп р едел ить , п омещ ая в ур овень 1 все комп оненты , не имею щ ие вх одов, и п р одол жая вы ш еоп исанны й п р оцесссз аменой сл ова«вы х од» насл ово «вх од». Г овор я т, что двестр уктур ы ур овней я вл я ю тся двой ственны ми. О р гр аф наз ы вается ацик лическ им, есл и он не имеет цикл ов: есл и п уть начинается в п р оизвол ь ной вер ш ине v, он никогда в v не вер нется . Э то з начит, что каждая вер ш ина ацикл ического ор гр аф а п р едставл я ет собой сил ь ную комп оненту. П оэтому числ о сил ь ны х комп онент ацикл ического

27

ор гр аф а р авно числ у его вер ш ин, х отя бы одна из вер ш ин имеет нул евую п ол устеп ень исх ода и, п о кр ай ней мер е, у одной вер ш ины п ол устеп ень з ах одар авнанул ю . Раз биение п р оизвол ь ного ор гр аф а на сил ь ны е комп оненты удобно изобр ажать п оср едством соответствую щ его ф актор гр аф а ил и конденсации, вер ш инамикотор ого я вл я ю тся сил ь ны екомп оненты . Ко нденсация о рграфа– это ацикл ический ор гр аф , котор ы й , как ився кий ацикл ический ор гр аф , имеет х отя бы одну вер ш ину с нул евой п ол устеп ень ю исх ода, т.е. х отя бы одну сил ь ную комп оненту без вы х одов. П усть теп ер ь G – ор гр аф , ассоциир ованны й с несимметр ичной матр ицей A. Раз обь ем G на сил ь ны е комп оненты ип остр оим стр уктур у ур овней , как оп исано вы ш е. П усть вер ш ины G уп ор я дочены , иуп ор я дочение совместимо с р аз биением на комп оненты и монотонно относител ь но ур овней , т.е. все вер ш ины каждой комп оненты нумер ую тся п осл едовател ь ны мичисл амиивсе комп оненты каждого ур овня l, l = 1, 2, … , m – 1, нумер ую тся р ань ш е л ю бой комп оненты ур овня l' > l. Т огда соответствую щ ая симметр ично п ер еуп ор я доченная матр ица будет бл очной нижней тр еугол ь ной . Каждой сил ь ной комп онентесni вер ш инамиотвечает квадр атны й диагонал ь ны й бл ок п ор я дка ni, внедиагонал ь ны е бл окисоответствую т свя з я м между сил ь ны ми комп онентами.

3.2 Исследо ва н ие ст ра т егий для н есиммет ричн ы х ра зреж ен н ы х ма т риц 3.2.1 По иск в глубин у н а о ргра ф е П оиск в гл убину – это п р оцедур а обх ода вер ш ин и р ебер гр аф а: начинаю т с п р оизвол ь ной вер ш ины s1 и п ы таю тся п о воз можности п р идер живать ся п осл едовател ь ностивер ш ина– р ебр о – вер ш ина– р ебр о … , есл и в текущ ей вер ш ине бол ь ш е нет неиссл едованны х р ебер , то воз вр ащ аю тся к п р еды дущ ей вер ш ине. Рассмотр им стр уктур ы , п ол учаемы е п р ивы п ол нениип оискавгл убину наор гр аф е, гдеф иксир овано нап р авл ение, в котор ом можно иссл едовать каждое р ебр о. П р едп ол ожим, что вся кая вер ш ина содер жит п етл ю . П усть v – текущ ая вер ш ина. М ы вош л ив v л ибо вп ер вы е (итогда v – п осл едня я п осещ енная вер ш ина), л ибо п овтор но п р и воз вр ащ ении. П усть иссл едуется р ебр о (v → ω ), п р ичем ω не п осещ ал ась п р ежде. Т огда ω становится текущ ей вер ш иной , а р ебр о (v → ω ) квал иф ицир уется как др евесное. Е сл исох р аня ть тол ь ко др евесны е р ебр а и п р енебр егать всеми остал ь ны ми, то будет п ол учено дер ево с кор нем в начал ь ной вер ш ине s1. П оскол ь ку р ебр а ор иентир ованы , то п р одол жение п оиска может оказ ать ся невоз можны м ещ е до того, как п осещ ены все вер ш ины . Т ак з аведомо п р оизой дет, есл и, нап р имер , s1 п р инадл ежит сил ь ной комп оненте C, не имею щ ей вы х ода: ииссл едование р ебер , ивоз вр ащ ение будут всегдап р иводить к вер ш инам из C, идер ево скор нем s1 будет точны м остовом C.

28

В бол ее общ ем сл учае п р и п р оизвол ь ном вы бор е s1 будет п ол учено дер ево с кор нем s1, остовное л иш ь дл я некотор ы х сил ь ны х комп онент гр аф а. Тогда п оиск воз обновл я ется из новой начал ь ной вер ш ины s2, котор ая п ока что не п осещ ал ась и, сл едовател ь но, не п р инадл ежит никакой из сил ь ны х комп онент, натя нуты х на п ер вое дер ево. С нова п р енебр егая вся ким недр евесны м р ебр ом, п остр оим втор оедер ево скор нем в s2, остовноедл я новой гр уп п ы сил ь ны х комп онент. П р оцедур ап р одол жается , п ока не будут п осещ ены все вер ш ины . Рез ул ь татом будет семей ство несвя з ны х дер евь ев, наз ы ваемое о сто вным лесо м, котор ое содер жит все вер ш ины ор гр аф а ир ебр а, квал иф ицир ованны е как др евесны е. Кр оме того, п р ип оискенумер ую тся уз л ы в том п ор я дке, вкаком онип осещ аю тся . Будем обоз начать чер ез Н омер (v) номер , п р ип исанны й вер ш ине v в х оде п оиска. В тех нол огии р аз р еженны х матр иц это уп ор я дочение и соответствие между дер евь я ми л еса и сил ь ны ми комп онентами исп ол ь з ую тся ал гор итмами, п р иводя щ имиматр ицу к бл очной нижней тр еугол ь ной ф ор ме. И ссл едуем бол ее детал ь но свя з ь между дер евь я миинатя нуты мина них сил ь ны микомп онентами. П усть s – начал ь ная вер ш ина, T – дер ево с кор нем s, п остр оенноеп оср едством п оискавгл убину. П окажем, что T можнор аз бить нанесвя з анны еп оддер евь я , каждоеиз котор ы х сл ужит остовом р овно одной сил ь ной комп оненты . П усть C = (Vc, Ec) – одна из сил ь ны х комп онент, натя нуты х на T, и п усть Tc – наимень ш ее п оддер ево T, содер жащ ее все вер ш ины C. П усть v0Vc – кор ень Tc. Л егко п оказ ать , что дер еву Tc п р инадл ежит тол ь ко вер ш ины из C. Д ей ствител ь но, п р едп ол ожим, что ω ⌠Vc – вер ш ина Tc. В ер ш ина ω не я вл я ется кор нем Tc, не может она бы ть и конечной вер ш иной , так как п о п р едп ол ожению Tc – наимень ш ееп оддер ево, содер жащ ее все вер ш ины C. Т огда v – п р едок дл я ω , и ω дол жна иметь п отомка(скажем, x) вC. В Tc имеется п уть из v вx, содер жащ ий ω , п оскол ь ку C – сил ь ная комп онента, то в C сущ ествует п уть из x в v. О бап утиобр аз ую т цикл , котор ому п р инадл ежит ω , но тогда ω дол жна бы ть вер ш иной C воп р екинаш ему п р едп ол ожению . Таким обр аз ом, T можно р аз бить на несвя з ны е п оддер евь я , каждое из котор ы х остовноер овно дл я одной сил ь ной комп оненты . Кор ень п оддер ева– это п ер вая вер ш ина соответствую щ ей комп оненты , п осещ аемая в х оде п оиска. О н наз ы вается к о рнем сильно й к о мпо нент ы. В частности, начал ь ная вер ш ина s я вл я ется кор нем той сил ь ной комп оненты , котор ой п р инадл ежит. С л едовател ь но, з адача оты скания сил ь ны х комп онент ор гр аф а сводится к з адаче оты скания кор ней п оддер евь ев. Будем говор ить , что п оддер ево относится к ур овню l, есл исоответствую щ ая комп онентанах одится в ур овне l стр уктур ы ур овней свя з ностиданногоор гр аф а. И ссл едуем соотнош ения между недр евесны мир ебр ами, с одной стор оны , и дер евь я мил еса и сил ь ны ми комп онентами ор гр аф а – с др угой . Э то будет сдел ано сучетом сл едую щ их сущ ественны х свой ствп оискавгл убину. П усть Т – одно из дер евь ев л еса, v – п р оизвол ь ная вер ш ина T, Tv – п оддер ево с кор нем v, содер жащ ееv ивсех ееп отомков в T. Т огдаv – п ер вая вер ш инаTv, п осещ аемая п р ип оиске, п оэтому онаимеет наимень ш ий номер в Tv: есл иω –

29

п отомок v, то Н омер (v)<Н омер (ω ). Кр оме того, все вер ш ины Tv будут п осещ ены до воз вр ащ ения чер ез v. В частности, есл и v – кор ень сил ь ной комп оненты , то номер v мень ш е номер а л ю бой др угой вер ш ины этой комп оненты , и все вер ш ины п осл едней будут п осещ ены , п р ежде чем п окинуть еевоз вр ащ ением чер ез v. Рассмотр им теп ер ь некотор ы й ш аг п оиска. П усть v – текущ ая вер ш ина, (v → ω ) – р ебр о, нея вл я ю щ ееся др евесны м. Э то оз начает, что ω п осещ ал ась до того, как v стал а текущ ей вер ш иной . С л едовател ь но, в этот момент оп р едел ены и Н омер (v), и Н омер (ω ). Кр оме того, есл и v относится к некотор ому ур овню l, то, ур овень l' вер ш ины ω дол жен удовл етвор я ть усл овию l' ≤ l, з нак р авенства достигается тол ь ко, есл иv иω п р инадл ежат одной итой же сил ь ной комп оненте. Е сл иобнар ужено недр евесноер ебр о (v → ω ), то сущ ествую т сл едую щ иевоз можности: (1) ω – п р едок дл я v. В этом сл учаеН омер (ω ) < Н омер (v), ар ебр о (v → ω ) наз ы вается о брат ным. П оскол ь ку уже сущ ествует п уть из ω в v, обр аз ованны й др евесны ми р ебр ами, то р ол ь обр атного р ебр а состоит в з амы каниицикл а. Т аким обр аз ом, v иее п р едкивп л оть до (ивкл ю чая ) ω п р инадл ежат одной итой жесил ь ной комп оненте. (2) ω – п отомок v. В этом сл учае Н омер (ω ) > Н омер (v), а р ебр о (v → ω ) наз ы вается лишним древесным ребро м. Л иш нее др евесное р ебр о соединя ет две вер ш ины , уже свя з анны е п утем из др евесны х р ебер . С л едовател ь но, оно не п омогает п оиску сил ь ны х комп онент, иесл инаш ацел ь состоит именно в этом, им можноп р енебр ечь . (3) ω – ни п отомок, ни п р едок дл я v. Ребр о (v → ω ) наз ы вается по перечным. Рассмотр им п оддер евоTv скор нем v, содер жащ еевсеп отомство v. В х одеп оиска, п осл еп р их одав v, п осещ аю тся инумер ую тся всевер ш ины Tv итол ь ко они, п окаTv небудет п окинуто воз вр ащ ением чер ез v. В ер ш инаω не п р инадл ежит Tv, но номер ей бы л п р исвоен р ань ш е, чем v стал а текущ ей вер ш иной . Э то з начит, что ω п ол учил а номер ещ е до того, как мы вп ер вы е вош л и в v, сл едовател ь но, Н омер (ω )<Н омер (v). В ер ш ины v и ω могут п р инадл ежать одной ил и р аз ны м сил ь ны м комп онентам. В п ер вом сл учае У р овень (ω ) = У р овень (v), во втор ом – У р овень (ω ) < У р овень (v). С тр уктур а, составл енная из остовного л еса идобавочны х р ебер , котор ы е могут бы ть обр атны ми, л иш ними др евесны ми и п оп ер ечны ми, наз ы вается дж унглями. Е сл и п оиск в гл убину п р оводится на ацикл ическом ор гр аф е, где каждая вер ш ина я вл я ется сил ь ной комп онентой , то п ол учится бол ее п р остая стр уктур а. Каждая вер ш ина остовного л еса – кор ень своей собственной сил ь ной комп оненты . Н ет ни обр атны х , ни активны х п оп ер ечны х р ебер (ак т ивным наз ы вается п оп ер ечное р ебр о, концы котор ого п р инадл ежат одной и той же сил ь ной комп оненте). В се р ебр а будут л ибо др евесны ми, л ибо стер ил ь ны мип оп ер ечны ми(ст ерильным наз ы вается п оп ер ечноер ебр о, концы котор огоп р инадл ежат р аз ны м сил ь ны м комп онентам).

30

3.2.2 По иск в ш ирин у н а о ргра ф е и ст рукт уры уро вн ей о риен т иро ва н н о й смеж н о ст и Рассмотр им кл асс р аз биений сл або свя з ного ор гр аф а G = (V, E), котор ы е могут бы ть п остр оены п оср едством п оиска в ш ир ину. П о дст рук т ура уро вней о риент иро ванно й смеж но сти L0, L1, … , Lm п ол учается , есл и L0δV – з аданное п одмножество вер ш ин G, а кажды й из остал ь ны х ур овней я вл я ется смежны м множеством дл я объединения п р еды дущ их ур овней :  i −1



 j =0



Li = Adj  Υ L j  , i = 1, 2, … , m. Числ о m наз ы вается длино й п одстр уктур ы ур овней . Ш ир инаоп р едел я ется как максимал ь ное числ о вер ш ин в п р оизвол ь ном ур овне. L0 – к о рень п одстр уктур ы . Е сл иL0 состоит из единственной вер ш ины u, т.е. L0 = {u}, то будем говор ить , что вер ш ина u – кор ень п одстр уктур ы . М ножество вер ш ин п одстр уктур ы m

Vs = Υ Li i =0

содер жит все вер ш ины L0 ите вер ш ины , котор ы е из них достижимы . В Vs, воз можно, вх одя т не все вер ш ины G. В этом сл учае оставш ееся п одмножество V–Vs может бы ть р аз бито анал огичны м обр аз ом, итак дал ее, п ока не будет п ол учена стр уктур а ур овней ор иентир ованной смежности, ох ваты ваю щ ая все вер ш ины G. Н умер ация ур овней в каждой п одстр уктур е своя . В ер ш ины п р и п оиске гр уп п ир ую тся п о ур овня м, а ор иентир ованны е р ебр аквал иф ицир ую тся как др евесны ел ибо как п оп ер ечны е. П р едп ол ожим, что п оиск начинается с некотор ой (п р оизвол ь но вы бр анной ) начал ь ной вер ш ины s. Тогда ур овень L0 состоит из единственной вер ш ины s, ибудет п ол учена п одстр уктур а ур овней с кор нем в s. П усть на некотор ом ш аге п оиска уже оп оз наны все вер ш ины ур овня Li. В се вер ш ины из Li и п р еды дущ их ур овней п омечены как п осещ енны е. Д ал ее дл я некотор ого v0Li мы иссл едуем р ебр а, ведущ ие из v к др угим вер ш инам. Е сл инай дено р ебр о (v → ω ), п р ичем вер ш ина ω ещ е не п осещ ал ась , то это р ебр о др евесное, а ω п р инадл ежит ур овню Li+1. Е сл и най дено р ебр о (v → x) и x – п осещ енная вер ш ина, то это р ебр о п оп ер ечное. П оскол ь ку п осещ енны е вер ш ины имею тся л иш ь в ур овня х Lj, j ≤ i +1, п оп ер ечное р ебр о, исх одя щ ее из вер ш ины ур овня Li, может веститол ь ко в вер ш ину ур овня Lj, j ≤ i +1. В бол ее общ ем сл учае, когда уже п остр оены некотор ы е др угие п одстр уктур ы , п оп ер ечное р ебр о может веститакже ив л ю бую вер ш ину этих п одстр уктур . Д р евесное р ебр о может соединя ть л иш ь вер ш ину ур овня Li и вер ш ину ур овня Li+1, есл и j > i + 1, то вер ш ина ур овня Li ивер ш ина ур овня Lj не могут бы ть соединены . Г р аф Gs =(Vs, Es), где Es – множество др евесны х р ебер , п р едставл я ет собой дер ево с кор нем s, остовное дл я п одстр уктур ы . Е сл ип о з авер ш енииочер едного дер ева п р одол жать п оиск, начиная с новой ,

31

не п осещ авш ей ся до сих п ор вер ш ины , итак до тех п ор , п ока не будут исчер п аны все вер ш ины G, то, в конечном счете, будут п ол учены джунгл ииостовной л ес. Д л я п одстр уктур ы ур овней скор нем вs имеет место сл едую щ еесвой ство: есл иv0Li, то р асстоя ние в G от s до v (т.е. дл ина кр атчай ш его п утииз s в v) р авно i. Кр оме того, в остовном дер еве сущ ествует р овно один кр атчай ш ий п уть дл ины i, он составл ен из др евесны х р ебер . 3.2.3 От ы ска н ие ма ксима льн о го мн о ж ест ва пут ей с ра зличн ы ми верш ин а ми в а циклическо м о ргра ф е Рассмотр им з адачу, котор ая свя з ана с п р иведением р аз р еженной матр ицы общ его вида к бл очной нижней тр еугол ь ной ф ор ме п оср едством несимметр ичны х п ер естановок. Заданы ацикл ический ор гр аф G = (V, E) и двеего вер ш ины s, t0V, най тимаксимал ь ноемножество п утей из s в t таких , что ниодна вер ш ина, кр оме s иt, не п р инадл ежит бол ее чем одному п ути. Будем говор ить , что множество мак симально в смы сл е некотор ого свой ства, есл и дл я его эл ементов это свой ство вы п ол нено, и оно (множество) не вкл ю чается стр огим обр аз ом ни в какое др угое множество эл ементов, имею щ их данное свой ство. С др угой стор оны , наибо льшим будем наз ы вать множество снаибол ь ш им числ ом эл ементов. Д л я р еш ения обсуждаемой з адачи исп ол ь з уется п оиск в гл убину. Е сл и п оиск начинается с вер ш ины s исущ ествует х отя бы один п уть из s в t, то t п р инадл ежит дер еву с кор нем в s. П оэтому достаточно иссл едовать тол ь ко это дер ево. Ал гор итм п ол ь з уется стеком, где х р анится п осл едовател ь ность вер ш ин от s до текущ ей вер ш ины . Каждое р ебр о иссл едуется тол ь ко один р аз , и л ибо оно становится часть ю констр уир уемого п ути, л ибо не сущ ествует п утииз s в t, содер жащ его это р ебр о. Рассматр иваю тся тол ь ко р ебр а, ведущ ие к неп осещ авш имся вер ш инам, п отому что мы ищ ем п ути, у котор ы х кр оме концов s и t нет общ их вер ш ин. Т ак как воз можно, что ал гор итму п р идется иссл едовать нескол ь ко р ебер , ведущ их к t, п р инимается согл аш ение о том, что t не дол жна становить ся п осещ енной вер ш иной . Е сл и х од п оиска п р иведет к вер ш ине t, она оп ускается в стек, котор ы й в этом сл учае содер жит п ол ны й п уть из s в t. В север ш ины п однимаю тся из стекаи п ечатаю тся , з атем встек сноваоп ускается s, иначинается п оиск нового п ути. Ал гор итм з аканчивает р аботу, когда s п однимается из стека п осл е того, как бы л и иссл едованы все вы х оды из s. П усть Vv – множество п осещ енны х вер ш ин, Ee – множество иссл едованны х р ебер . П усть гр аф п р едставл ен своей стр уктур ой смежности. Т огда ал гор итм можно оп исать сл едую щ им обр аз ом: Ш аг 0 (И нициал изация ). П ол ожить Vv ← ι, Ee ← ι. Ш аг 1 (Н ачал о п ути). О п устить s встек. Ш аг 2 (П осещ ениевер ш ины ). П ол ожить v ← вер ш инанавер х у стека. Ш аг 3 (И ссл едованиер ебр а). Н ай тивсп искесмежностивер ш ины v р ебр о (v→ ω )⌠Ee, гдеω ⌠Vv. Тогда:

32

(3а) Е сл итакоер ебр о наш л ось и ω ≠ t, п ол ожить Vv ← Vv ″ {ω }, Ee← Ee″(v→ ω ), оп устить ω в стек и п ер ей ти к ш агу 2 дл я п р одол жения п оиска. (3б) Е сл итакое р ебр о наш л ось иω = t, п ол ожить Ee ← Ee ″ (v → ω ), оп устить ω встек ип ер ей тик ш агу 5 дл я сбор кип ути. (3в) Е сл и v не имеет неиссл едованны х вы х одов, ведущ их к неп осещ авш имся вер ш инам, п ер ей тик ш агу 4 дл я воз вр ащ ения . Ш аг 4 (В оз вр ащ ение). П одня ть стек на одну п оз ицию . Е сл истек п уст, то остановка. В п р отивном сл учаеп ер ей тик ш агу 2. Ш аг 5 (Ф ор мир ование п ути). П одня ть все содер жимое стека, нап ечатать п уть , аз атем п ер ей тик ш агу 1, чтобы начать новы й п уть . Ал гор итм тр ебует п амя тиивр емени O(|V|, |E|). 3.2.4 Алго рит м Хо лла Е сл иу з аданной n × n матр ицы A вседиагонал ь ны еэл ементы нер авны нул ю , то ей можно соп оставить ор гр аф . О днако есл ина гл авной диагонал и имею тся нул и, то вначал е п ер еставл я ю тся стр оки и стол бы с тем, чтобы п ол учить ненул евую диагонал ь . Н ай денная этим п утем п осл едовател ь ность ненул евы х эл ементов наз ы вается т рансверсалью . У невы р ожденной матр ицы A п ол ная тр ансвер сал ь всегда сущ ествует. О днако, п ол ную тр ансвер сал ь может иметь и вы р ожденная матр ица. Н аз овем струк т урно выро ж денно й матр ицу п ор я дка n, котор ую нел ь з я п ер еуп ор я дочить так, чтобы п ол учил ась п ол ная тр ансвер сал ь . Е сл и максимал ь ная воз можная тр ансвер сал ь имеет дл ину k < n, то k – это струк т урный ранг, а n – k — ст рук т урныйдефек т матр ицы . М аксимал ь ную тр ансвер сал ь матр ицы A можно най ти п оср едством ал гор итма Х ол л а. О п иш ем вар иант с п ер естановкамистр ок, котор ы й удобен дл я р аз р еженны х матр иц, х р анимы х в стр очном ф ор мате. Ал гор итм состоит из n ш агов. Ц ел ь k-го ш ага – п оместить ненул евой эл емент в k-ю п оз ицию диагонал и. П о з авер ш енииk ш агов в п ер вы х k п оз иция х гл авной диагонал и стоя т ненул евы е эл ементы . Теп ер ь на ш аге k + 1 имею тся сл едую щ ие воз можности: (а) Э л емент ak+1, k+1 ≠ 0, вэтом сл учаеш аг k + 1 з акончен. (б) С ущ ествует ненул евой эл емент, стр очны й и стол бцовы й индексы котор ого нах одя тся в п р едел ах от k + 1 до n. В таком сл учае п ер естановкой стр ок и/ил и стол бцов этот эл емент можно п ер евести в (k + 1)-ю диагонал ь ную п оз ицию . Квадр атная п одматр ица, р асп ол оженная на п ер есечении стр ок и стол бцов с номер ами 1, … , k, не меня ется п р и этих п ер естановках , и ненул евы е эл ементы в п ер вы х k п оз иция х диагонал и останутся насвоих местах . (в) Квадр атная п одматр ица, стоя щ ая на п ер есечении стр ок и стол бцов с номер ами k + 1, … , n, – нул евая . М ы можем все же надея ть ся оты скать комбинацию стр очны х п ер естановок, п омещ аю щ ую ненул евой эл емент в(k + 1)-ю диагонал ь ную п оз ицию . Чтобы най ти тр ебуемы е п ер естановки, п р осл едим вматр ицеувеличиваю щ ий пут ь. О н начинается сп оз иции(k + 1, k

33

+ 1), идет вдол ь стр оки k+1 до ненул евого эл емента, стоя щ его, скажем, встол бцеl (х отя бы один такой эл емент дол жен бы ть , иначестр окаk + 1 цел иком состоит из нул ей , и A – вы р ожденная матр ица), з атем вдол ь стол бца l до п оз иции(l, l), дал ее к внедиагонал ь ному ненул евому эл ементу стр окиl, р асп ол оженному, скажем, в стол бце m, ит.д. Д р угимисл ова, п уть п оп ер еменно п р ох одит чер ез диагонал ь ны й и внедиагонал ь ны й ненул евой эл ементы . П уть неможет дважды идтивдол ь какой -л ибо стр окиил истол бца из аканчивается наненул евом эл ементеп одматр ицы , обр аз ованной стр оками 1, … , k и стол бцами k + 1, … , n. В п амя ти комп ь ю тер а п уть может р егистр ир овать ся з ап ись ю номер ов диагонал ь ны х п оз иций в том п ор я дке, в каком они п осещ ал ись , т.е. k + 1, l, m, … . П оскол ь ку некотор ы е диагонал ь ны е п оз иции могл и бы ть п осещ ены , а вп осл едствии удал ены из п ути, нужно з авестиисп исок п осещ авш их ся п оз иций , чтобы не вой тив них снова. Рассмотр им соответствую щ ий п р имер . Чтобы п остр оить нужны й п уть , мы начинаем с п оз иции (k + 1, k + 1) и ищ ем в стр оке k + 1 ненул евой эл емент. Д л я невы р ожденной матр ицы A такой дол жен най тись , п отому что в п р отивном сл учае стр ока k + 1 цел иком состоя л а бы из нул ей . Е сл и ненул евой эл емент стоит в стол бце l, то мы п ер ех одим к стр оке l иищ ем в ней ненул евой эл емент в стол бах k+1, … , n. Е сл и такой имеется , то п уть з акончен. Е сл инет, то мы ищ ем в п ер вы х k п оз иция х стр окиl ненул евой эл емент, котор ы й бы стоя л в стол бце, р анее не п осещ авш емся , скажем, в стол бце m. Д ал ее мы п ер ех одим к стр оке m и п овтор я ем вы ш еоп исанны е оп ер ации, п ока п уть не будет з авер ш ен. Е сл ив некотор ой стр оке не удается най ти внедиагонал ь ны й ненул евой эл емент в неп осещ авш емся стол бце, то этастр окаудал я ется из п ути(но неиз сп искап осещ авш их ся п оз иций ), имы воз вр ащ аемся к п р еды дущ ей стр оке. Е сл и на некотор ом ш аге п осл е п осещ ения r п оз иций в п р едел ах от 1 до k наш п уть становится п усты м (т.е. мы вер нул ись к начал ь ному п ункту), это оз начает, что A вы р ождена: дей ствител ь но, мы наш л иr+1 стр ок (r п осещ авш их ся стр ок п л ю с стр ока k + 1), имею щ их ненул евы еэл ементы тол ь ко вr стол бцах . Как тол ь ко искомы й п уть п остр оен (скажем, k + 1, l1, l2, … , lr, гдеlr > k), мы п ер еставл я ем r + 1 стр ок и два стол бца, чтобы вы вести п осл едний най денны й ненул евой эл емент в п оз ицию (k + 1, k + 1). Н ужны такие п ер естановкистр ок: стр ока k + 1 становится стр окой l1, стр ока l1 становится стр окой l2, … , стр окаlr-1 становится стр окой k + 1. П оскол ь ку стр оки вы бир ал ись так, чтобы ненул евой эл емент стр оки li стоя л в п оз иции li+1, то п р и з амене стр оки li стр окой li+1 этот ненул евой эл емент п оп адает в диагонал ь ную п оз ицию (li+1, li+1). С л едовател ь но, п осл е стр очны х п ер естановок эл ементы в п ер вы х k п оз иция х диагонал иостанутся ненул евы ми. Кр оме того, п осл едний ненул евой эл емент п ути будет п ер еведен в п оз ицию (k +1, lr). П ер естановка стол бцов k + 1 иlr п ер емещ ает его в п оз ицию (k + 1, k + 1), чем (k+1)-й ш аг з авер ш ается . Е сл иlr = k + 1, то п ер естановкастол бцовненужна.

34

О тносител ь но эф ф ективности этого ал гор итма з аметим, что на каждом ш агекаждая стр окап р осматр ивается самоебол ь ш оедважды : п ер вы й р аз п р ип оиске ненул евого эл емента, стоя щ его п р авее п оз ицииk, втор ой р аз п р инеобх одимостинай тиненул евой эл емент в неп осещ авш емся стол бце с номер ом от 1 до k. П оэтому есл ив матр ице z ненул евы х эл ементов, то на ш аге k вы п ол ня ется O(z) оп ер аций , а в ал гор итме в цел ом O(nz) оп ер аций . Э та оценка достигается на сп ециал ь но сконстр уир ованны х п р имер ах , но на п р актикечисл ооп ер аций обы чноя вл я ется мал ы м кр атны м z. 3.2.5 Алго рит м Хо пкро ф т а – К а рпа Ал гор итм Х оп кр оф та – Кар п а нах одит максимал ь ную тр ансвер сал ь р аз р еженной матр ицы . О сновная идея та же, что и в ал гор итме Х ол л а: п р осл еживаю тся увел ичиваю щ ие п ути, и от ш ага к ш агу ул учш аю тся наз начения . О днако п р оводится тщ ател ь ны й анал из увел ичиваю щ их п утей , и их свой стваисп ол ь з ую тся , чтобы р аз бить п осл едовател ь ность наз начений на мал ое числ о ф аз . В нутр и каждой ф аз ы одновр еменно нах одя т много кор отких увел ичиваю щ их п утей , все они имею т одинаковую , п р ичем минимал ь ную дл ину, исих п омощ ь ю ул учш ается текущ ееназ начение. Э тим сп особом п овы ш ается эф ф ективность ал гор итма. Рассмотр им неор иентир ованны й гр аф G = (V, E) ип одмножества M φ E его р ебер . П одмножество M наз ы вается паро со чет анием ил иназначением, есл и никакая вер ш ина G не инцидентна бол ее чем одному р ебр у из M. П ар осочетание с наибол ь ш им кар динал ь ны м числ ом m=|M| наз ы вается наибо льшим паро со чет анием. В ер ш ина, не инцидентная никакому р ебр у из M, наз ы вается сво бо дно й. П уть в гр аф е G, не имею щ ий п овтор я ю щ их ся вер ш ин, наз ы вается увеличиваю щ им пут ем п ар осочетания M, есл иоба его конца – свободны е вер ш ины , а р ебр а п оп ер еменно п р инадл ежат E – M иM. У вел ичиваю щ ие п ути сл ужат дл я п овы ш ения кар динал ь ного числ а п ар осочетания . Е сл и известен увел ичиваю щ ий п уть п ар осочетания M, то можно п ол учить новое п ар осочетание M' с числ ом р ебер , на единицу бол ь ш им, чем у M (т.е. |M'| = |M| + 1). Д л я этого нужно вз я ть всер ебр ап ути, неп р инадл ежащ иеисх одному п ар осочетанию M, идобавить всер ебр аM, не вош едш ие в увел ичиваю щ ий п уть . Э то свой ство имеет место дл я л ю бого увел ичиваю щ его п ути, какова бы ни бы л а его дл ина. В особенности нас будут интер есовать кр атчай ш ие увел ичиваю щ ие п ути, т.е. п ути, имею щ ие наимень ш ее кар динал ь ное числ о ср еди всех увел ичиваю щ их п утей п ар осочетания M. Чтобы бол ее точно сф ор мул ир овать сказ анное, нап омним сп ер ва некотор ы е обоз начения , исп ол ь з уемы е в теор ии множеств. Рассмотр им два множества: S и T. Зап ись S – T обоз начает множество эл ементовS, неп р инадл ежащ их T. Т аким обр аз ом, S – T = =S– (S 1 T). Зап ись SρT обоз начает симметр ичную р аз ность множеств S и T. Э л емент п р инадл ежит SρT, есл и он нах одится л ибо в S, л ибо в T, но не в S 1 T. С л едовател ь но, SρT = S ″ T – S 1 T. П усть теп ер ь P обоз начает множество р ебер увел ичиваю щ его п ути п ар осочетания M в гр аф е G. Т огда MρP также п ар осочетание, п р ичем

35

|MρP|=|M|+1. Н ай дем наибол ь ш ее п ар осочетание в гр аф е G = (V, E). О тп р авл я я сь от п устого п ар осочетания M0 = ι, мы будем вы числ я ть п осл едовател ь ность п ар осочетаний M0, M1, M2, … с воз р астаю щ ими кар динал ь ны ми числ ами, п ока не будет достигнуто наибол ь ш ее п ар осочетание. Каждое п ар осочетание Mi+1 п ол учается из п р еды дущ его п ар осочетания Mi п оср едством п остр оения увел ичиваю щ его п утиPi. И менно, Mi+1 = MiρPi, i = 0, 1, 2, … . Е сл и G – ассоциир ованны й с р аз р еженной матр ицей двудол ь ны й гр аф , то это в точности та п р оцедур а, на котор ой основан ал гор итм Х ол л а. Д л я матр ицы п ор я дка n с числ ом ненул евы х эл ементовz этот ал гор итм тр ебует O(nz) оп ер аций . В отл ичие от ал гор итма Х ол л а, ал гор итм Х оп кр оф та – Кар п а исп ол ь з ует тол ь ко кр атчай ш ие увел ичиваю щ ие п ути. Е сл и Pi – кр атчай ш ий увел ичиваю щ ий п уть п ар осочетания Mi и Mi+1 = MiρPi, i = 0, 1, 2, … , то имею т место сл едую щ иеутвер ждения : (а) |Pi+1| ≥ |Pi|, т.е. кр атчай ш ий увел ичиваю щ ий п уть дл я Mi+1 не может иметь мень ш ер ебер , чем кр атчай ш ий увел ичиваю щ ий п уть дл я Mi. (б) Д л я всех j иk таких , что |Pj| = |Pk|, п ути Pj иPk не имею т общ их вер ш ин. (в) Д л я всех j иk таких , что j < k и|Pj| = |Pk|, Pk я вл я ется кр атчай ш им увел ичиваю щ им п утем п ар осочетания Mj. (г) Е сл и m – кар динал ь ное числ о наибол ь ш его п ар осочетания , то кол ичество р аз л ичны х цел ы х чисел в п осл едовател ь ности|P0|, |P1|, |P2|, … не может п р евы ш ать 2m1/2 + 2. Кр ометого, есл иm – кар динал ь ноечисл о наибол ь ш его п ар осочетания , аM – п р оизвол ь ноеп ар осочетание, дл я котор ого |M| < m, то сп р аведл иво и (д) С ущ ествует увел ичиваю щ ий п уть дл ины , не п р евы ш аю щ ей 2|M|/(m |M|) +1. В сил у этих свой ств вы числ ение п осл едовател ь ности п ар осочетаний р аз бивается не бол ее чем на 2m1/2 + 2 ф аз . В се увел ичиваю щ ие п ути, р аз ы скиваемы е внутр и ф аз ы , имею т р аз л ичны е вер ш ины и одинаковую дл ину. Кр оме того, все эти п ути – кр атчай ш ие увел ичиваю щ ие дл я того п ар осочетания , с котор ы м начинается данная ф аз а. И так, вместо того чтобы вы числ я ть всю п осл едовател ь ность п ар осочетаний , Х оп кр оф т и Кар п п р едл агаю т сл едую щ ий ал гор итм: Ш аг 0 (И нициал изация ). П ол ожить M← ι. Ш аг 1 (П оиск п утей ). Н ай ти максимал ь ное множество {P1, P2, … , Pt} кр атчай ш их увел ичиваю щ их п утей п ар осочетания M, не имею щ их общ их вер ш ин. Е сл итаких п утей нет, то остановка. Ш аг 2 (У вел ичение п ар осочетания ). П ол ожить M ← MρP1ρP2ρ … ρPt и п ер ей тик ш агу 1. П окажем, как исп ол ь з овать этот ал гор итм дл я р аз р еженны х матр иц. П усть A – квадр атная р аз р еженная матр ицап ор я дкаn. П р оцедур аоты скания тр ансвер сал исостоит всл едую щ ем: (1) П остр оить ассоциир ованны й сA двудол ь ны й гр аф G = (V, E). Г р аф G неор иентир ованны й иимеет два множества вер ш ин R иC, п о n вер ш ин в

36

каждом. В ер ш ины R наз ы ваю тся ю но шами исоответствую т стр окам A. В ер ш ины C наз ы ваю тся девушк ами и соответствую т стол бцам A. В G имеется р ебр о(ri, cj), есл иaij ≠ 0. (2) П усть M – п ар осочетание в G. В начал е M = ι, но в х оде р аботы ал гор итмаM становится неп усты м. Т еп ер ь п р иф иксир ованном G итекущ ем M мы п р ип исы ваем ор иентацию р ебр ам G: каждоер ебр о из M нап р авл ено от ю нош ик девуш ке, а каждое из оставш их ся р ебер G – от девуш кик ю нош е. П усть G = (V , E ) – п ол ученны й этим сп особом ор иентир ованны й гр аф . И менно такой сп особ п остр оения G мотивир уется сл едую щ им его свой ством: р ебр а л ю бого ор иентир ованного п ути в G п оп ер еменно п р инадл ежат E – M и M. П оэтому есл и в G най ден п уть , свя з ы ваю щ ий свободную девуш ку со свободны м ю нош ей (имеется в виду свобода п о отнош ению к M), тоэтот п уть необх одимо увел ичиваю щ ий . (3) П усть L0 – множество свободны х девуш ек. Т огда нужно п остр оить п одстр уктур у ур овней ор иентир ованной смежностис кор нем в L0, п ол ь з уя сь п оиском в ш ир ину. Н ет необх одимости стр оить всю п одстр уктур у. Д остаточно сох р аня ть р ебр а, идущ иеот каждого ур овня Li к ур овню Li+1. П р и этом нужны тол ь ко ур овни L0, L1, … , Lp, где p = min{i | Li 1 {свободны е ю нош и}≠ ι}. П остр оенная п одстр уктур а п р едставл я ет собой ацикл ический ор гр аф с девуш ками в четны х ур овня х и ю нош ами – в нечетны х . Кажды й п уть от свободной девуш кик свободному ю нош е – это кр атчай ш ий увел ичиваю щ ий п уть дл я M, п р ичем его дл инар авнаp. Чтобы най тимаксимал ь ноемножество п утей ср аз л ичны мивер ш инами, обр ащ ается ор иентация каждого р ебр а, ина п одстр уктур е, отп р авл я я сь от свободны х ю нош ей ур овня Lp, вы п ол ня ется п оиск в гл убину. Заметим, что есл ибы ор иентация р ебер не обр ащ ал ась , а п оиск начинал ся от свободны х девуш ек ур овня L0, то п р иш л ось бы иссл едовать много р ебер , ведущ их к несвободны м ю нош ам ур овня Lp, что п отр ебовал о бы з начител ь но бол ь ш ей вы числ ител ь ной р аботы . Н аконец, есл и {P1, P2, … , Pt} – най денное множество п утей , то можно увел ичить текущ ее п ар осочетание M иновое п ар осочетание имеет кар динал ь ное числ о |M| + t. Е сл ир аз р еженная матр ица п ор я дка n имеет z ненул евы х эл ементов, то ал гор итм, стр оя щ ий внутр и ф аз ы максимал ь ное множество п утей , тр ебует п амя ти и вр емени O(n, z). П оскол ь ку кар динал ь ное числ о наибол ь ш его п ар осочетания не п р евы ш ает n, то ф аз будет не бол ь ш е чем 2n1/2 + 2. С л едовател ь но, весь ал гор итм вы числ ения наибол ь ш его п ар осочетания тр ебует вр еменине бол ее O(n3/2, zn1/2) ип амя тине бол ее O(n, z). Е сл и z = O(n), что часто вы п ол ня ется дл я р аз р еженны х матр иц, то эти оценки п р евр ащ аю тся вO(n3/2) дл я вр еменииO(n) дл я п амя ти. 3.2.6 Алго рит м С а рдж ен т а – Уэст ерберга Н есимметр ичная р аз р еженная матр ица, имею щ ая п ол ную тр ансвер сал ь (т.е. диагонал ь без нул ей ) может бы ть симметр ично п ер еуп ор я дочена к бл очной нижней тр еугол ь ной ф ор ме, есл и известны сил ь ны е комп оненты

37

соответствую щ его ор гр аф а. С ар джент и У эстер бер г п р едл ожил и п р остой ал гор итм оты скания сил ь ны х комп онент п р оизвол ь ного ор гр аф а. Ал гор итм основан на п р оцедур е п оиска в гл убину, п оскол ь ку в нем п р осл еживается п уть п р и сох р анении наскол ь ко это воз можно п осл едовател ь ностивер ш ина – р ебр о – вер ш ина – р ебр о… П уть начинается из п р оизвол ь но вз я той вер ш ины ип р одол жается до тех п ор , п ока не будут обнар ужены л ибоцикл , л ибовер ш инабез вы х ода. Ц икл оп оз нается бл агодар я тому, что п уть вх одит в вер ш ину, п осещ авш ую ся п р ежде. В се вер ш ины цикл а п р инадл ежат одной и той же сил ь ной комп оненте. В сл учае обнар ужения цикл а п р именя ется п р оцедур а, наз ы ваемая стя гиванием вер ш ин: все вер ш ины цикл а стя гиваю тся в единую составную вер ш ину, все р ебр а цикл а игнор ир ую тся , а р ебр а, соединя ю щ ие вер ш ины цикл а с п р очими вер ш инами гр аф а, р ассматр иваю тся теп ер ь как соединя ю щ ие составную вер ш ину с этимип р очимивер ш инами. С оставная вер ш ина становится п осл едней вер ш иной текущ его п ути, и в модиф ицир ованном гр аф еп оиск воз обновл я ется сэтого места. Е сл инай дена вер ш ина, ил исоставная вер ш ина, не имею щ ая вы х ода, то эта вер ш ина ил и составная вер ш ина я вл я ется сил ь ной комп онентой ур овня 1. В ер ш ина ил и все вер ш ины , обр аз ую щ ие составную , удал я ю тся из гр аф а вместе со всемиинцидентны миим р ебр ами. П оиск з атем воз обновл я ется в оставш емся п одгр аф е, п р ичем отп р авл я ю тся от п осл едней вер ш ины текущ его п утил ибо от новой начал ь ной вер ш ины , есл ип уть исчер п ан. Т ак п р одол жается до тех п ор , п ока не будут п осещ ены все вер ш ины и иссл едованы всер ебр аисх одного гр аф а. В этом ал гор итме каждое р ебр о гр аф а иссл едуется тол ь ко один р аз . О днако, необх одимы часты е п ер естр ой ки гр аф а, что составл я ет сер ь ез ную доп ол нител ь ную р аботу. С тя гивание вер ш ин п р и обнар ужении очер едного цикл аэквивал ентно ф ор мир ованию нового ф актор гр аф а, аудал ениесил ь ной комп оненты – вы дел ению частичного гр аф а. П р их одится вести з ап иси, указ ы ваю щ ие, из каких вер ш ин состоит каждая составная вер ш ина икакой составной вер ш ине п р инадл ежит каждая вер ш ина исх одного гр аф а. Н еудачная р еал изация может п овл ечь O(|V|2) п ер еп омечиваний вер ш ин (V – множество вер ш ин гр аф аG = (V, E)). 3.2.7 Алго рит м Т а рьян а П р ип оискевгл убину наор гр аф еG = (V, E) ф ор мир уется остовной л ес, состоя щ ий из одного ил и нескол ь ких дер евь ев. В ер ш ины каждой сил ь ной комп оненты C ор гр аф а оп р едел я ю т п оддер ево некотор ого дер ева из л еса. П оддер ево содер жит все вер ш ины C итол ь ко вер ш ины С , его кор ень – это п ер вая вер ш ина C, п осещ аемая в х оде п оиска. Т аким обр аз ом, з адача оты скания сил ь ны х комп онент сводится к оты сканию кор ней п оддер евь ев в остовном л есу, п ор ождаемом п оиском вгл убину. Ал гор итм Т ар ь я на сконстр уир ован таким обр аз ом, чтобы воз вр ащ ение чер ез кор ень комп оненты C в др угую комп оненту бол ее вы сокого ур овня бы л о невоз можно до тех п ор , п ока все вер ш ины C не будут п осещ ены и

38

оп оз наны как эл ементы C. Э то оз начает, в частности, что есл и v – текущ ая вер ш ина п оиска инай дено р ебр о (v → ω ), где ω нумер ована, но не п р ип исана какой -л ибо комп оненте, то v иω п р инадл ежат одной итой же комп оненте. Д оказ ател ь ство несл ожно: п усть У р овень (ω ) = l, так как ω ещ е не п р ип исана, то текущ ая вер ш ина v дол жна нах одить ся в ур овне l' ≤ l. О днако, п оскол ь ку (v → ω ) – р ебр о гр аф а G, то l' ≥ l. С л едовател ь но, l' = l, что воз можно, л иш ь , есл иv иω относя тся к одной комп оненте. В ал гор итме Т ар ь я на п р оводится п оиск, и каждой вер ш ине v соп оставл я ется метка. П осл едня я состоит из двух чисел , наз ы ваемы х Н омер (v) и С вя з ка(v). Н омер (v) оп р едел я ется в х оде п оиска п р остой нумер ацией вер ш ин от 1 до n = |V| соответственно п ор я дку, в каком они п осещ аю тся . Д л я п р оизвол ь ной вер ш ины v, не я вл я ю щ ей ся кор нем сил ь ной комп оненты , С вя з ка(v) – это номер некотор ой вер ш ины ω из той же, что и дл я v, сил ь ной комп оненты . О днако, ω нумер ована р ань ш е, чем v, т.е. С вя з ка(v) = Н омер (ω ) < Н омер (v). Д л я кор ня r л ю бой сил ь ной комп оненты мы п ол агаем С вя з ка(r) = Н омер (r). Э то свой ство исп ол ь з уется дл я оп оз нания кор ней сил ь ны х комп онент: есл ичисл о С вя з ка(v) п р авил ь но вы числ ено, то v тогда и тол ь ко тогда будет кор нем сил ь ной комп оненты , когда С вя з ка(v)=Н омер (v). В х оде п оиска вы числ ения , свя з анны е с п р изнаком С вя з ка, п р оизводя тся насл едую щ их ш агах : Ш аг 1 (И нициал изация ). Е сл и вер ш ина v п осещ ается вп ер вы е, то п ол ожить С вя з ка(v) = Н омер (v). Ш аг 2 (М одиф икация ). Е сл иv – текущ ая вер ш ина инай дено р ебр о (v → ω ), где ω нумер ована р ань ш е, чем v, но ещ е не п р ип исана какой -л ибо комп оненте, топ ол ожить С вя з ка(v) = min[С вя з ка(v), С вя з ка(ω )]. Ш аг 3 (В оз вр ащ ение). Е сл и(v → ω ) – др евесное р ебр о, п р ичем v и ω п р инадл ежат одной комп оненте и п р оисх одит воз вр ащ ение из ω в v, то п ол ожить С вя з ка(v) = min[С вя з ка(v), С вя з ка(ω )]. Н а ш аге 1 п р изнаку С вя з ка п р исваивается максимал ь ное воз можное дл я данной вер ш ины з начение. Н аш аге2 С вя з ка(v) п ер еоп р едел я ется намень ш ее з начение, есл и най дена свя з ь v с некотор ой п одх одя щ ей вер ш иной ω . В сл едствие тр ебования Н омер (ω ) < Н омер (v) з десь учиты ваю тся тол ь ко обр атны е ип оп ер ечны е р ебр а. Кр оме того, п оскол ь ку ω нумер ована, но ещ е не п р ип исана какой -л ибо комп оненте, то v иω дол жны бы ть в одной итой же комп оненте. Э то устр аня ет стер ил ь ны е п оп ер ечны е р ебр а, т.е. п оп ер ечны е р ебр а (v → ω ), у котор ы х v и ω относя тся к р аз ны м комп онентам. Д ал ее, С вя з ка(ω ) – это номер некотор ой вер ш ины из той же сил ь ной комп оненты , какой п р инадл ежат v и ω . Э тот номер , воз можно, мень ш е, чем у ω . С тр атегия ш ага 2 состоит в том, чтобы п ер еоп р едел я ть п р изнак С вя з ка(v) на наимень ш ий из известны х п ока номер ов вер ш ин в данной комп оненте. Н аш аге 3 минимал ь ноез начениеп р изнака С вя з ка сп ускается вдол ь п ути п р ивоз вр ащ ении. С тр атегия этого ш агата же, что у ш ага 2: мы з наем, что v свя з анасω , аω свя з анасx = С вя з ка(ω ), п оэтому v свя з анасx. Е сл иномер x мень ш е, чем текущ ее з начение числ а С вя з ка(v), то п осл еднее

39

п ер еоп р едел я ется . Ал гор итм будет р аботать п р авил ь но и п ри осл абеваниитр ебования о том, чтобы v иω п р инадл ежал иодной комп оненте. Д ей ствител ь но, есл и(v → ω ) – др евесноер ебр о, а v иω относя тся к р аз ны м комп онентам, то ω – кор ень своей комп оненты . П оскол ь ку имеет место воз вр ащ ение, то С вя з ка(ω ) = Н омер (ω ) > Н омер (v). Т ак как С вя з ка(v) ≤ Н омер (v), то з начениеп р изнака С вя з ка(v) в данном сл учае ш агом 3 небудет изменено. П окажем, что п р изнак С вя з ка вы числ я ется вер но. П усть v – некотор ая вер ш ина, относя щ ая ся к сил ь ной комп оненте C, и п усть Tv – п оддер ево с кор нем v, содер жащ ее п отомство v в C. Е сл иv не я вл я ется кор нем C, то Tv дол жно иметь вы х одвэту комп оненту, т.е. дол жно сущ ествовать р ебр о (ω → x), гдеω 0 Tv, x 0 C, п р ичем это р ебр о недр евесное. С л едовател ь но, x дол жна бы ть нумер ована р ань ш е, чем ω . Бол ее того, x дол жна бы ть нумер ована р ань ш е, чем v, чтобы р ебр о (ω → x) могл о бы ть вы х одом из Tv, п оэтому Н омер (x) < Н омер (v). Ребр о (ω → x) бы л о най дено в х оде п оиска, так что С вя з ка(ω ) ≤ Н омер (x). П оз же, п р ивоз вр ащ ении, это з начениебы л о сп ущ ено к v, откуда С вя з ка(v) ≤ Н омер (x) < Н омер (v). Э то как р аз тот тест, котор ы й оп р едел я ет, что v не я вл я ется кор нем C. Заметим, что п ол ученны й р ез ул ь тат будет сп р аведл ивнез ависимо от того, п ол агаем мы С вя з ка(ω ) = Н омер (x) ил и С вя з ка(ω ) = С вя з ка(x) в момент обнар ужения р ебр а (ω → x). Е сл иv – кор ень сил ь ной комп оненты , тоTv неимеет вы х ода, иС вя з ка(v)=Н омер (v). Ал гор итм Т ар ь я на п о сущ еству совп адает с ал гор итмом С ар джента – У эстер бер га. Г л авное отл ичие з акл ю чается в том, что вместо п оня тия «стя гивание вер ш ин», исп ол ь з овавш егося С ар джентом и У эстер бер гом, в ал гор итме Т ар ь я на вводится п р изнак С вя з ка, п оз вол я ю щ ий х р анить составны е вер ш ины в стеке. Д ей ствител ь но, есл и С вя з ка(v) = ω , то все вер ш ины , нах одя щ иеся в стеке между (также п омещ енны ми туда) вер ш инамиω иv, обр аз ую т составную вер ш ину. П р иведем р аз вер нутую ф ор мул ир овку ал гор итма Т ар ь я на. П ол ны й ал гор итм п р едставл я ет собой комбинацию п оиска в гл убину и оп исанной вы ш е п р оцедур ы вы числ ения п р изнака С вя з ка. И сп ол ь з ую тся два стека, мы будем п р идер живать ся тер минол огииТар ь я на иназ ы вать их соответственно «стеком» и«мар ш р утом». М ар ш р ут содер жит сп исок вер ш ин, обр аз ую щ их п уть от начал ь ной вер ш ины к текущ ей . Каждая новая вер ш ина, най денная п р и п оиске, оп ускается в мар ш р ут. Кажды й р аз , когда вы п ол ня ется воз вр ащ ение, соответствую щ ая вер ш инап однимается свер х амар ш р ута. С тек содер жит сп исок вер ш ин, п р инадл ежащ их частично сф ор мир ованны м сил ь ны м комп онентам. Каждая новая вер ш ина, най денная п р и п оиске, оп ускается в стек. В ер ш ины не удал я ю тся из стека индивидуал ь но. Когда сил ь ная комп онента в вер х ней части стека сф ор мир ованап ол ность ю , онаудал я ется вся . Ал гор итм исп ол ь з ует также массивы Н омер иС вя з ка, бул евский массив дл я п р овер ки з а ф иксир ованное вр емя , нах одится л и вер ш ина в стеке, и п р едставл ения множества Vv п осещ енны х вер ш ин и множества Ee иссл едованны х р ебер . Точная ф ор мул ир овкаал гор итматакова:

40

Ш аг 0 (И нициал изация ). П ол ожить Ee ← ι, Vv ← ι, i ← 0. Ш аг 1 (В ы бор начал ь ной вер ш ины ). В ы бр ать п р оизвол ь ную вер ш ину v ⌠ Vv. Е сл итакой нет, то – остановка. Ш аг 2 (П осещ ение вер ш ины ). О п устить v в стек имар ш р ут. П ол ожить Vv← Vv″{v}, i ← i +1, Н омер (v) ← i, С вя з ка(v) ← i. Ш аг 3 (И ссл едованиер ебр а). Н ай тивсп искесмежностивер ш ины v р ебр о (v→ ω )⌠Ee. В оз можны сл едую щ иесл учаи: (3а) Н ай дено р ебр о (v → ω ), п р ичем ω ⌠ Vv, т.е. (v → ω ) – др евесное р ебр о. П ол ожить Ee ← Ee ″ (v → ω ), v ← ω ип ер ей тик ш агу 2. (3б) Н ай дено р ебр о(v → ω ), п р ичем ω 0 Vv. П ол ожить Ee ← Ee ″ (v → ω ) и п ер ей тик ш агу 4 дл я п ер есчетап р изнакаС вя з ка(v). (3в) В ер ш ина v не имеет неиссл едованны х вы х одов и С вя з ка(v) < Н омер (v). П ер ей тик ш агу 5 дл я воз вр ащ ения . (3г) В ер ш ина v не имеет неиссл едованны х вы х одов и С вя з ка(v) = Н омер (v). П ер ей тик ш агу 6 дл я сбор кисил ь ной комп оненты . Ш аг 4 (П ер есчет п р изнака С вя з ка). Е сл и Н омер (ω ) < Н омер (v) и ω нах одится в стеке, то п ол ожить С вя з ка(v) ← min [С вя з ка(v), С вя з ка(ω )] и п ер ей тик ш агу 3. В п р отивном сл учае, ср аз у п ер ей тик ш агу 3. Ш аг 5 (В оз вр ащ ение). П одня ть v из мар ш р ута. П ол ожить : u ← вер ш ина навер х емар ш р ута, С вя з ка(u) ← min [С вя з ка(u), С вя з ка(v)], v ← u. П ер ей тик ш агу 3. Ш аг 6 (Ф ор мир ование сил ь ной комп оненты ). П одня ть v ивсе вер ш ины надv из стекаип оместить их в текущ ую сил ь ную комп оненту. П одня ть v из мар ш р ута. Е сл и мар ш р ут п устой , п ер ей ти к ш агу 1. В п р отивном сл учае п ол ожить v← вер ш инанавер х емар ш р утаип ер ей тик ш агу 3. Э тот ал гор итм тр ебует п амя тиивр емениO (|V|, |E|). 3.2.8 С т ра т егия М а рко вица С тр атегия М ар ковица з акл ю чается в том, чтобы на каждом ш аге бр ать в качестве гл авного ненул евой эл емент, дл я котор ого минимал ь но п р оизведение числ а остал ь ны х ненул евы х эл ементов той же стр окиичисл а остал ь ны х ненул евы х эл ементовтогожестол бцаактивной п одматр ицы . Н ижеизл оженны е стр атегиип р именимы к л ю бой матр ице A, но есл иA бол ь ш ая и известно, что она р аз л ожима, то п очти навер ное имеет смы сл вначал е п р ивести ее к бл очной нижней тр еугол ь ной ф ор ме, а уже з атем исп ол ь з овать этиметоды дл я каждогобл окап оотдел ь ности. Ал гор итм М ар ковица л окал ен в том смы сл е, что минимизир ует на каждом ш агез ап ол нениеичисл о оп ер аций , несчитая сь своз можность ю , что др угая п осл едовател ь ность п р еды дущ их гл авны х эл ементов могл а бы п ор одить ещ е мень ш ее общ ее з ап ол нение ип отр ебовать мень ш его общ его числ аоп ер аций . Рассмотр им сл едую щ ую кар тину гауссова искл ю чения . В начал е k-го ш агамы п р инимаем з агл авны й эл емент a kk(k ) инор мир уем стр оку k активной п одматр ицы дел ением всех ее эл ементов на a kk(k ) . В ектор ы r и c имею т

41

р аз мер ность n – k. Рассмотр им матр ицу crT, это квадр атная матр ица п ор я дка n – k ир анга 1. K-й ш аг гауссово искл ю чения состоит в вы читании crT из п одматр ицы , р асп ол оженной встр оках истол бцах k +1, … , n. В ектор c становится k-м п одстол бцом L, а вектор (1, rT) – k-й стр окой U. П усть n(v) обоз начает числ о ненул евы х эл ементов вектор а v. С тр атегию М ар ковица можно теп ер ь п ер еф ор мул ир овать сл едую щ им обр аз ом: вы бр ать в активной п одматр ице и п ер евести в п оз ицию (k, k) п оср едством соответствую щ их п ер естановок стр ок и стол бцов тот ненул евой эл емент, дл я котор ого п р оизведение n(c)n(r) минимал ь но. Так как n(c)n(r) – это числ о ненул евы х эл ементов матр ицы crT, то становится п оня тно, в каком смы сл е стр атегия М ар ковицап ы тается л окал ь но умень ш ить з ап ол нение. С л едует сдел ать тр и з амечания . М ожно р ассудить , что п р оизведение n(c)n(r) минимал ь но, когда минимал ен кажды й из сомножител ей , так что бы л о бы достаточно вы бр ать на р ол ь гл авного эл емент, стоя щ ий в стр оке и стол бцеснаимень ш им числ ом ненул евы х эл ементов. Т акой эл емент, однако, может оказ ать ся нул ем и, сл едовател ь но, неп р игодны м в качестве гл авного. В дей ствител ь ности, во многих сл учая х все ш ансы з а то, что такой эл емент будет нул евы м как р аз п отому, что он нах одится в стр оке и стол бце с наибол ь ш им числ ом нул ей . С итуация становится ещ е х уже, когда в р асчет п р инимаю т сообр ажения числ енной устой чивости, так как теп ер ь отвер гаю тся не тол ь ко нул и, но и сл иш ком мал ы е ненул евы е эл ементы . О днако, все же вер но то, что п р иемл емы й ненул евой эл емент, минимизир ую щ ий п р оизведение n(c)n(r), часто соответствует мал ы м n(c) и n(r). У чтем, что n(c) и n(r) – это в точности числ о внедиагонал ь ны х ненул евы х эл ементов соответственно в k-м стол бце L иk-й стр оке U. Э то п р оя сня ет то обстоя тел ь ство, что стр атегия М ар ковицап о сущ еству п ы тается сох р анить р аз р еженность L иU. П усть C – множество п оз иций ненул евы х эл ементов в матр ице crT, D – анал огичное множество дл я п одматр ицы , р асп ол оженной в A(k) в стр оках и стол бцах k + 1, … , n. О бы чно C1D ≠ ι, п оэтому множество F эл ементов з ап ол нения , внесенного в A(k+1) на k-м ш аге, вы р ажается ф ор мул ой : F = C – C1D. В тор ое наш е з амечание относится к тому, что стр атегия М ар ковица минимизир ует |C| = n(c)n(r), но не |F|. О днако минимизация |C| имеет тенденцию умень ш ать и |F|. С др угой стор оны , числ о |C| = n(c)n(r) р авно числ у умножений ичисл у сл ожений (есл из асчиты вать сл ожения с нул я ми), вы п ол ня емы х на k-м ш аге. С л едовател ь но, метод М ар ковица л окал ь но минимизир ует числ о умножений исл ожений . Числ о дел ений з а ш аг р авно n(r), это числ оочень мал о. Н аш е тр еть е з амечание касается воп р оса устой чивости. С тр атегия М ар ковицасамап о себенегар антир ует числ енной устой чивости. Тип ичны м я вл я ется сл едую щ ее п р авил о, сочетаю щ ее стр атегию М ар ковица с одним из кр итер иев устой чивости: на каждом ш аге ср едивсех ненул евы х эл ементов активной п одматр ицы , удовл етвор я ю щ их п р иня тому кр итер ию устой чивости, вы бр ать в качестве гл авного тот, дл я котор ого минимал ь но

42

п р оизведение n(c)n(r). С тандар тны й кр итер ий устой чивости – это отбор п о бар ь ер у. Spc содер жит всененул евы еэл ементы активной п одматр ицы , Sst – теэл ементы из Spc, котор ы еп одчиня ю тся п р иня тому кр итер ию устой чивости. Ssp – это п одмножествоSst, вы дел я емоеусл овием М ар ковица. В общ ем сл учае Ssp может содер жать нескол ь ко ненул евы х эл ементов. Н аконец, гл авны й эл емент – это л ю бой эл емент из Spiv ≡ Ssp. О днаиз сил ь ны х стор он стр атегииМ ар ковица– еесимметр ия . Э то оз начает, что (есл ине учиты вать вл ия ние кр итер ия устой чивостиинеодноз начности вы бор а) дл я обеих матр иц A иAT п ол учается одно ито же уп ор я дочение. С тоимость ал гор итмаМ ар ковицасущ ественно з ависит от р аз мер амножества Sst накаждом ш аге, п оскол ь ку п р оизведениеn(c)n(r) дол жно вы числ я ть ся дл я л ю бого эл ементаиз Sst. Д л я р еал изации методы М ар ковица тр ебуется два цел ы х массива, в котор ы е п оначал у з ап исы вается числ о ненул евы х внедиагонал ь ны х эл ементов соответственно каждой стр окиикаждого стол бца А. Э тимассивы п ер еоп р едел я ю тся от ш ага к ш агу с учетом искл ю чаемы х эл ементов и з ап ол нения . 3.2.9 С т ра т егия Д а ф ф а Д аф ф п р едл ожил бол ее деш евую стр атегию , наз ы ваемую ri в cj, ил и минимал ь ная стр ока в минимал ь ном стол бце. Э та стр атегия не имеет симметр ии. Ф ор мул ир уется она так: на каждом ш аге вы бир ается стол бец с наимень ш им числ ом ненул евы х эл ементов. Затем ср еди ненул евы х эл ементов этого стол бца, удовл етвор я ю щ их п р иня тому кр итер ию устой чивости, вы бир ается тот, что стоит в стр оке с наимень ш им числ ом ненул евы х эл ементов. Здесь Spc содер жит всененул евы е6 эл ементы активной п одматр ицы , Ssp – ненул евы е эл ементы стол бца с наимень ш им числ ом ненул евы х эл ементов, Sst – это п одмножество Spc, вы дел я емое кр итер ием устой чивости, и Spiv ≡ Ssp. Н аконец, гл авны й эл емент вы бир ается из Spiv исх одя из сообр ажений р аз р еженности. В некотор ы х сл учая х эта стр атегия р аботает гор аз до х уже, чем стр атегия М ар ковица. Ц еной некотор ой доп ол нител ь ной р аботы ее можно симметр изовать . Н а каждом ш аге вы п ол ня ется п р едп исаниестр атегииri вcj, аз атем нез ависимо – п р едп исание стр атегииck в rl (т.е. вы бир ается стр ока с наимень ш им числ ом ненул евы х эл ементов, скажем, стр ока l, вы бир аю тся ненул евы е эл ементы стр оки l, п одчиня ю щ иеся кр итер ию устой чивости, вы бир ается ненул евой эл емент, стоя щ ий в стол бце(скажем, k) снаимень ш им числ ом ненул евы х эл ементов). Н аконец, из двух най денны х гл авны х эл ементов бер ется тот, дл я котор ого п р оизведениеn(c)n(r) мень ш е. 3.2.10 С т ра т егия З ла т ева В р еал изациир аз ны х вар иантов стр атегииМ ар ковица бол ь ш ая часть р аботы (т.е. вр емени) и доп ол нител ь ной п амя ти ух одит на п р осмотр , п ер еуп ор я дочение исл ежение з а стр окамиистол бцами. П оэтому п р иведем стр атегию , вкотор ой п одобная р аботаминимал ь на.

43

У п ор я дочиваем стол бцы матр ицы А п о воз р астанию числ а ненул евы х эл ементов. Н а k-м ш аге гауссова искл ю чения вы бир аем в качестве гл авного эл емент k-го стол бца, удовл етвор я ю щ ий усл овию устой чивости и п р инадл ежащ ий стр оке с минимал ь ны м числ ом ненул евы х эл ементов. Т ак как мы р ассчиты ваем, что в стол бце мал о ненул евы х эл ементов, то можно п р овер я ть их все ине з аботить ся об уп ор я дочениистр ок. П р иискл ю чении п р оизводя тся тол ь ко п ер естановки стр ок. М етоды , основанны е на этой стр атегии, имею т недостатки: з ап ол нение часто будет бол ь ш им, вер оя тная п р ичина в том, что стол бцы , п оначал у содер жавш ие мал о ненул евы х эл ементов, бы стр о з ап ол ня ю тся , но, тем не менее, исп ол ь з ую тся как ведущ ие. П оэтому такая стр атегия дол жнап р именя ть ся остор ожно и/ил идл я сп ециал ь ны х кл ассовматр иц.

С писо к реко мен дуемо й лит ера т уры : 1. П иссанецкиС . Т ех нол огия р аз р еженны х матр иц / С . П иссанецки. – М . : М ир , 1988. 2. Д жор дж А. Числ енны е методы р еш ения бол ь ш их р аз р еженны х систем ур авнений / А. Д жор дж, Д . Л ю . – М . : М ир , 1984. 3. Э стер бю О . П р я мы е методы дл я р аз р еженны х матр иц / О . Э стер бю , З. Зл атев. – М . : М ир , 1987. 4. Т ь ю ар сон Р. Раз р еженны ематр ицы / Р. Т ь ю ар сон. – М . : М ир , 1977. 5. М етоды р еш ения систем ср аз р еженны миматр ицами. С п особы х р анения и п р едставл ения р аз р еженны х матр иц, оп ер ации над ними: метод. указ ания дл я студентов 3 кур са дневн. ивечер н. одт-ний ф ак. П М М / сост. И .А. Бл атов, Т .Н . Г л уш акова, М .Е . Э ксар евская . – В ор онеж : В ор онеж. гос. ун-т, 2002. – 33 с. – (№ 156)

Автор ы : Э ксар евская М ар инаЕ вгень евна, Г л уш аковаТ ать я наН икол аевна Редактор : Тих омир оваО л ь гаАл ександр овна