Пупков K.A., Егупов Н.Д. Высокоточные системы самонаведения (2011) (1152001), страница 34
Текст из файла (страница 34)
Реализация же второго зтапа состоит в расчете семи матричных произведений Я), Х2,..., Хт (2,219) с применением клеточного метода матричного умножения. Рис.2,26 иллюстрирует алгоритм расчета Х), где Х' и 1" — клеточные подматрицы — операнды порядка 4. г У)! ! Уа 1 - ! У(( У(:У' ':2' Ъ (8(2! -! Х(( В соответствии с алгоритмом„реализующим клеточный метод, можно указать следующие зтапы вычислений; е зтап вычисления матричных козффициентов л,ь и Гю.. (Х21-1,2Ь-(+ ХЬ.ЬЬ) " (Х21,2Ь-)+ Х21.2Ь) ° (Х2~-! 2Ь-1+ Х21-122)" (Х2..22-1- Х21-1. Ь-)) ~', = (А(2+ Ае+ л+2) Х;, = (А(+,„+ А(+ .(+2), 2 Х, = (А() + А(л+,), Л, = (Аье)„ — А; ), Х, =(Акт+; — Аее(ле ), Ь 22 Х 2~( Х!1,;: Х(12 ) ";" Х(( Х211 .' Х212,1 ".
*, Х21„, (12ь- )лз-1+ гзм22) 1 1 (уть- )л) 12ц22) ° (Утмт)-1 222-1.2)-1) ° 1 (УТЬ- 122- ! + У22-1,2)) (Утнт) - ! + УЬЬ-1.2~) ° (2.221) ° этап вычисления матриц «;!!,: «к ! Х И ! «4 = ) )Ф'зь !дз ! ьж! ью! ! с2 Э ! 3 ЧГО ~' '«Ь-!.2Э-!~ Ю! «Сц ) '«2кзЭРЭЗ (2,222) «4 = Х: ЖЛУзэ,зу 4)0 - Е ЯМ эм! эж! я~!у = ~' $$экэф. эж! где к,у, й = 1, 2, ..., р; ° этап вычислениэ мзтРнц Л!З." 22ь-!,22-! «кк«у + ~у ~ву'+ «тку' 22!-!,2 = «гы+ «4 ~2саз-! = Фу + Й)0 (2.223) 4!,2, =42 -9к, +~4+~)«з где 67'.й = 1.2, ...,р.
Приведенные фрагменты алгоритма позволяют рассчитать матричные п)зонзведення У2, Я,..., Е . Результатом третьего этапа СКА4 являются результирующие матрицы Сни имеющие порядок 2', Приведем формулы для проведения вычислений С,«+ — — Яз + Яз С«+, . - -Якз, + Я« (2224) 2 3 С„,„., = К„- Я„+ г,, + г,',. где «,,у = 1,...,4, В работе (136) приведены положения, позволяющие оценить вычис- лительную сложность расчетов, Значения мультипликативной н адаптивной сложностей клеточного аналога традиционного алгоритма, полученного на основе смешанного клеточного метода определяются формулэмн: В'ы = 711'к«г! - 7 0,109 з - 0,763 з (операций умнож ).
14. = 7(11- «ээ!+ И.!г!) + И.«зл! = (2,225) ~ 7(1.125 л- + 0,109 из — 0.437 г!2) + 4,5 из -. 0,763 нз . 9,316 не (операции сложения!. Аналогичным образом рассчитываются мультиплнкатнэная и адаптивная сложщютн клеточных аналогов других нзвестных алгоритмоэ мэтри щого умножения. значения которых приведены э табл. 2.2. Таблица 2.2. Д«ульгнплнкнтнэнэн н элднтнэнэн сложности клегочнмх энэ- ;югоэ кзэестных элгорнтмоэ КлетОчные аналоги эл!Орнт.
Г Вычнслнтельнэн сложность Он к!Нтрнчного умно)кения, (число опе экий) Му .! А шанного клеточного метода иэн, Ксы В' Традиционного алгоритма Алгоритм Винограда 0.763 н" 0,382 и" 0,763(=)н «2м / м 0,334н' Алгоритм 0)трэссенэ Алгоритм Елфнмоэой-Кэпн- тоноэой СКА4. основные положения которого изложены выше, минимизирует знзчещ!я мультиплнкэтнвной и адаптивной сложностей отмеченных злгоритмов матричного умножения на 25%. Увеличение глубины рекурсии (числа рекурсивных шагов) приводит к дальнейшему уменьшению вычислительной сложности приведенных клеточных зиалогов нэ каждом щзге рекурсии, 2. $0.6, Быстрые алгоритмы умцснкемня матриц.
2.$0.6.$. Общие полажеиил 1133). Результаты, полученные в работах Л. Л. Елфимовой, ориентированы на решение широкого спектра задач вычислительной линеЙноЙ алгебры: решение систем линеЙных алгебраических уравнений, обращение матриц. вычисление определителей н др. Одной из фундаментальных операций при построении соответствующих алгоритмов является матричное умиожснще. Эта оце. рация является ключевой и при решении задач исследования н синтеза систем автокщтического управления методом матричных операторов, В работе (133) приведен обэп, в котором рассмотрены неко!орые результаты решения указанные проблемы. Основное положение звучит так: ЛПоявлеине с~м~Йст~а алгоритмов умножения ~~~риц н нх клеточных аналогов обусловлено стремлением авторов решить задачу оптимизации вычислительной сложности наиболее эффективно.
Как известно, в традиционном (классическом) алгоритме две матрицы размера и х и можно перемножить, используя и операций умножения и (пз — пэ) операций сложения. Общая вычислительная сложность алгоритма составляет И;эм = 2пз - ~2 операций укн!Ожения/сложения. Поскольку умножение чисел — операция более трудоемкая, чем их сложение, возникает необходимость н уменьшении мультипликатнвиой сложности алгоритмов, В 1966г.
5.Мподгай (550, 551) разработал быстрый регулярный алгпритч умножения чатриц, мультипликатнвная сложность которого равна И'3» = 0,5о'+ п2 операций умножение, Однако минимизация мультиплнкативной сложности практически на 50'й обусловила увеличение более чем на 50% адаптивной сложности, 3 именно И;, = 1,5и' + 2»»2 — 2»» операций сложения. Таким обра.юм, общая вычислительная сложность алгоритма (550, 551) составляет И;„;„, = 2о'+ Зпз 2п операций уь»ножения»»сложения, В !969г. Ч,5(гаьзсп (542( предложил быстрый рекурсивный алгоритм, мультипликативная н аддитивнаи сложности которого соответственно равны И',ц»»"»иг»»2~~ операций учноже»»ня и И'„— -- 6(7ь'""" — 22'""-'") операций сложения, Для умножения (2 н 2)-матриц он использовал сечь опера»ий умножения и 18 операций сложения в отличие от традиционного алгоритма, требующего восемь операций умножения и четыре операции сложения. При»»спе»»ис этого алгоритма в ка»сстве базож»го для п»»строен»»я рекурсивного алгоритма умножения и н)-матриц (где и = 2".
й — натуральное число) даст следующее соотно»пенис для вычисления общего числа арифметических операций: И;ач =- И;„ь„(2" ) = 7"" ' - 6. 22» операций у»»поженив/сложа»»ия. Та»»»»»» образом, рекурсия является эффективныч способом построения быстрого алгоритма умножения матриц, поскольку приводит и умсньшени»О его чультнпликативной сложности отнОсительио иссодного традиционного алгоритма. о;шако при этом существенно уве.
лнчивастся аддити»»ная сложность. В 1971 г, 5. Моргай (550. 551) ц»сдложил алгоритм, которь»Й позволил т»ин»»чнзирпвать вялит»»аную ;ложность рекурсивного алгоритча. Для умножения (2 х 2)-матриц чу удалось использовать се»»ь умножений и 15 сложений вместо 18 сложений в алгоритме. Это дало возможность минимизировать общую вычислительную сложность данного рекурсивного алгоритча. определяемую соотношением И;...,,12") = 6 7» — 5 22ь операций )хнюження/сл»»жених.
В дальней»ис»» показатель степени чультиплиьатня»»ой сложности новых алгоритмов матричного умножения после.»овательио снижался. Так, в 1976 г. Ч. Уа. Рап получил чультиплиативную сложность загорит»»а. Равную О(от~из). В 1979г. (». Внй и соавторы работы (502] минимизировали ее до значения О(пзтт~). В 196)г. А.5сйоп(»аае (540! добился сложности, равной 0( 2322). В 1962».
().Соррсгзп»10» и 5.%(по~гай (511) предложили алгоритч, сложность которого составила О(»».'эз). Наименьшего значения чультиплнкативной сложности, равного»)(»»эл™), достиглн О. Соррегзгп1Ф и 5.%)пойга»( (5101 в 1990г. используя арифметические прогрес. сии. В 2001 г. Л.Д. Елфичова и К), В. Капнтонова (136) предложилн быстрый гибридный алгоритм, в котороч впервые достигнута одновременная минимизация ч)льтиплнкатнвной и адаптивной с~ожн~- стеЙ.
Да~ныЙ алгоритм в отличие от алгоритма Винограда харак. тсризустся ученьшсннычи чультипликатнвной, адаптивной н обшей сложностями, равными соответственно И'и =- 0.4375пз -. 1,75п2 опе- 2 б Р» = ~~ 3»»,. зь», Р," = ~~ пз; »д» ~ Ь2» ь=! »-л 3 % г 4 'с 3 т Рц =,р аз -кзь ' 2».2»-» ° Ро = 2, 3» 3»2. ь=» ь=! Рч = 4» а»ь ' а»З* Р»» = ~ а»а ' "мьз» ° Р»2 = 2 4»аь2$ ' аьз ° ь=» ь~» ью1 где 4,7', й = ! „2...., и»; и» = п»»2. Коэффициенты а'... а,'„и 33„,.... аа. определяются по формулам з»ь = аз»,22-» + аз»дь.
! з,ь = а2»-»ды- — аз»,22-», 3 2 а»ь = аз»-»,2Ь»'»Ь где»', 2, й = 1 „2,..., тп; пз = и/2. Далее используются промежуточные вычисления: Элементы матрицы С = Ан вычисляются с помощью соотношений 3 Сз»22 (ч +10 3 с2,2» = 1,~ +Рч 3 с2»-».22-» = Р, +Р,» т озс22» —— 1";, -Р,, где», ) = 1,2... нц и»: н72 раций умножения, И;, —. 1,3125н' - йиз 7н операций сложения и И'м„,, = !.75лз ь 9,75пе — Ун операций у»н»оже»»ия/сложснн»». Перечислнчые быст(»ые алгорит»»ы нъюют б»»л»~»»»ос тео()етнчсск»»е значсни»„', однако практически цсннычн являются алгоритмы ввиду простоты их реализации и наиченыпей труаос»»кости программирования. В н»»сто»»»»»е»» разделе изложены оспою»ыс ~»О»»ожеиня работы (133), в которой отражены результаты исследовании в направлении о~»тнчизации как мультипликатнвной, так н адднтнвной сложностей указанных выше алгоритмов. 2Л0.6.2, Бысп»ра»й ги!42идиый алаарии»лг умиазиеиид мап»ри»( парддиа п =- 20 ()» > 1) !1331, Задача состоит в построении алгоритма умножения матриц 4 = (о„) н В: (Ь„).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
