Читать онлайн «Методы решения систем с разреженными матрицами. Способы хранения и представления разреженных матриц, операции над ними: Методические указания к спецкурсу»

В О РО НЕ Ж С К И Й Г О С У Д А Р С Т В Е ННЫ Й У НИ В Е Р С И Т Е Т Ф АК У Л Ь ТЕ Т ПМ М К а ф едр а в ы чи с ли т ельной м а т ем а т и ки М Е Т О Д Ы Р Е Ш Е НИ Я С И С Т Е М С Р А ЗР Е Ж Е ННЫ М И М А Т Р И ЦА М И С П О С О БЫ ХР А НЕ НИ Я И П Р Е Д С Т А В Л Е НИ Я РА ЗРЕ Ж Е ННЫ Х М А Т Р И Ц, О П Е Р А ЦИ И НА Д НИ М И М ет одическиеуказания к спецкур су для с т у дент ов 3 ку р с а днев ного и вечер него от делени й ф а ку льт ет а ПММ Сос т а ви т ели : И. А. Бла т ов Т. Н . Глу ша кова М. Е. Экс а р евс ка я В о ро не ж – 2002  -2- СО Д ЕРЖ А Н И Е § 1. В в е де ние … … … … … … … … … … … … … … … … … … … … … … … … … … . . 3 § 2. Способы хране нияи пре дстав л е нияразре ж е нных мат риц … … … . … … ... 3 § 3. О пе рации над разре ж е нными мат рицами … … … … … … … … … … ... … … . 9 § 4. М е т од Гаусса дл яразре ж е нныхмат риц … … … … … … … … … … … … … . 24 Л ит е рат ура … … … … … … … … … … … … … … … … … … … … … … … … … . 33  -3- § 1. В ведение С т ро гого о пре де л е ния разре ж е нной мат рицы не т , но е сть “не строгие ” о пре де л е ния, не ко т орые изко т орых мы зде сьп рив е де м. О п р е д е л е ни е 1. 1. Р азре ж е нная м ат ри ца ( РМ ) – эт о мат рица, у кот о ро й “ мно го” эл е ме нт ов рав но нул ю . О п р е д е л е н и е 1. 2. Р азре ж е нная м ат ри ца – эт о мат рица, дл я кот о ро й испо л ьзов ание ал горит мо в , учит ыв аю щ их нал ичие нул е й, по зв ол яе т добит ься эконо мии маш инно го в ре ме ни и памят и по срав не нию с т радиционными ме т о дами. РМ в о зникаю т п ри ре ш е нии многих прикл адных задач. Н азов е м не кот о рые изних: 1) дискре т изация урав не ний мат е мат иче ской ф изики – разно стные схе мы и ме т о д коне чных эл е ме нт о в ; 2) задачи л ине йно го про граммиро в ания (т е о рияопт имизации); 3) задачи т е ории эл е кт риче ских це пе й. О сновная задач а к урса – на у чи т ьс я с т р ои т ь эф ф ект и в ны е а лгор и т м ы р ешени я с и с т ем ли нейны х а лгебр а и чес ки х у р а в нени й (СЛАУ) AU = f ( A – РМ), т . е. п ы т а т ьс я оп т и м и зи р ова т ь п р оцес с р ешени я с т очки зр ени я за т р а т м а ши нной п а м я т и и в р ем ени . В озмож ности ре ш е ния эт о й задачи связаны с игнориров ание м нул е й мат рицы A за сче т т ого , чт о: 1) ариф ме т итиче ские оп е рации снул ями не произв одят ся; 2) нул и не обязат е л ьно хранит ьв маш инной памят и. § 2. С пособы хр анения ипр едст авл ения р азр еж енны х м ат р иц В се сп осо бы хране ния РМ закл ю чаю т ся в т о м, чт обы хранит ь т ол ько не нул е в ые эл е ме нт ы мат рицы ил и, мо ж е т быт ь, не бо л ьш ое ко л иче ств о нул е й в ме сте сними. 2. 1.