Пупков K.A., Егупов Н.Д. Высокоточные системы самонаведения (2011) (1152001), страница 35
Текст из файла (страница 35)
порядок которых равен и = 2Р ()» = 1), Для решения зада и используются алгоритм Винограда-Штрассена для умножения (2 и 2)-матриц. Ключевые зависимости — регулярные преобразования вида (134): 11",ц' 1 11;, —. 0675из+0875нз+ 2г12 = — 1,75нз + 2ит (операций умножения/сложения/вычитания!. ЗЛО.6.3.
!2вьстрвгй аабраднвза алаоритлв улзноженил матрац парадна и =-4р(34 > 1). При построении алгоритма умножения двух матриц (и = 4д, гз — натуральное число) используется метод Винограда (133) для каждой из семи формул зависимостей (2.10.6.2). Справедливы определявшие их вь!ражения ! 1 1,1 р »з «»» » 2 р . ж 42 »з»з Р»1 3.
=-3 .3 3 „4 4 .4 3 „3 3,3 !6»з»» ° » "3 ° 1, 1 = 1, 2, ..., гн; ги ю и/2, »»»»»2 (з»тз, ! + *.1и з1( ~М !» + М» »1) в в Особенность алгоритме (2.10.6.21-(2.229) состоит з том, что в нем огушествлена одновременная 3!Инимнзация мультиплнкативной, аддитикной и обшей сложностеЙ относительно традипиониого алгоритма. Что касается мультнпликативнои, адднтивной и Обизей сложности, то В (133) покзааио слелующее: Выигрыш по мультипликативной сложности го«тавляет 12.5'Дз при любых значениях и; пронзит мииимизапни зд,тзг1ивно1! и об!пей сложностей зависит от величины и; для адднтивной ложности он равен 1д» при н = 26; составляет 9.633 прн и = 10» и !22'У». Ири н 10'„достигает максимального значения 12,5Ф» при и д 1О', Выигрыш по обпшй вьггислитсльной сложности составляет '623 при о =- 15: равен 11'М, нри о - 102 и 12,36»х при п = 10', нютигзст згаксимзльно1о зна!ения 12,5 ей при и > 104.
По сравнению » оыстрым алго1кчтзюм 1!иногрздз алгоритм характеризуется умень:1кн1ной Обшей Вычнслитглы!ОЙ слОжпостью прн Всех значениях н. 111ззосительно быстрых алгоритмов Штрзссена, Винограда-(!)Трассена. 1='лфныовой-Кзнитон!!вой Вынгрьш! по обшей вычислитетьиой с:южюютн наблюдается соответственно при н < 103. п < 600, и .: 10!. учитывая отмеченные преныуи!Сстпз, 3 также простоту и регулярность Вычислений, онтиы»тг1ьное соотношение между мультипликзтивиой и аддитивной сложностями. можно заключить, что его приме. кение в методах, основа которых — аппарат матричных операторов, ПОЗВОЛИТ ПОСТ!ЮИТЬ ВЕСЬМЗ ЗффЗ»КТИВНЫЕ ЗЛГОРИТМ14 ИССЛЕДОВЗНИЯ И синтеза широкого класса сложных САУ.
Включаюших нестанионзрные и нелинейные злементы. ззг'2 2 »з = Д (о21-1 4ь-3 + Ь44-1 зз- ! ) (Ь43-здз-1 + тн-! 4ь-1)* Ь"=1 з»»/2 3 (п2з-1ль-2 + Ь4ьдз-1) (Ьвь-22з-1 + о2»-! 4ь)» Ьм1 ззтз Л'.» ("1»,зь ! + Взь,т) (Зза 1а + азль)* 3 т т 3 )~ (азль-1 + азво) (32Ь-1„Г + З»2Ь)» зз/2 Е (з4ез 1+ Ьвь,зз)(Ьи-злз+ а~д ), ю/2 Х, ( ьвь-2 + аазьл ) (аазь- 13 + а ла) Ь 1 из/2 1 ч 2 »рз = 2 !'з.зь-! ' Ззздз Фж1 з»з/2 3 % П2»-1,4Ь-2 ' Оа»-1,4Ь ь=! »з»Г2 4 ч 3 3 Зз = г аздь-1 а!.ЯЬ Ь=1 »»»72 3 ч» ! 1 »р» ~„агдь-1 ' а!да Ь=1 зч72 Е Ьм,- 1дз-1 ° Ьвь-3,22- и 4зз1 ьз/2 ~: Ьвьдз-1 Ьва-222-1. Ь=1 ззз/2 )' азт„ 32„ ! , (2.232) Ь=1 ззз/2 3 3 ааь,з ' Я2Ь-1„1' В=1 зь/2 Я Ь44,22 Ь4Ь-2.22, ьм з»»/2 Х: в а азь,1 ' ззь-13 ею 1 Зависимости, определяющие коэффициенты а«ь, .... зэь и азь, „....
аа«о имеют вид ь;~, =- анде «+ «»»ьдь, зь =- Ьзь «зз — Ьзь — «лз — «, ! $ ь«ь = з«ь ам-«дь-« ° аьз = зьлэ — зьэ (2 ан; = аз»-«,и.-««тэ«ль-«зьу "" Ьзаау Ьзь-«ду з»ь аз»- «ль з«ь аго = аьу — Ьзаду-«, $ $ где 1, у, к ж 1,2.... „гп; п«ш и/2. Для вычисления элементов матрицы С справедливы формулы: 3 3 «3 сз — «дз«- «Р«з + р»з» сз«- «л» 1»з +' 1«» 3 т, 3 $ сзьз, « =1„— ро, «ц«да=(;,+р,, (2 «,у = 1,2,..., гп; т = п/2 «4 7 «4 3 $ $ '«1 = Ро+ РО 13 = '»з + Ры 'И = Уц т ро (2.235) 1, у' = 1, 2, ..., оц тп = п/2 В (133) показано, что мультипликатнвная, аддитивная и общая операционная сложности алгоритма соответственно составляют: Иы =- !4'ьг' + 11"„',' = 0,4375 пз + 1,75 ««~ (операций умножения), И;, = И пц+ И:«$«+ 1).г1+ 14.« = 1,3125 пз + 7,25 п~ — 7 и (операции сложения/вычитания), И'$ = Иы+)Р = =- 1,75пз+9пз- 7п (операций умножения/сложения).
Приведем вывод, сделанный в (133): »...алгоритм (2.230)-(2.235) по сравнению с алгоритмом (2,10.6.2)-(2.229) имеет минимизированную мультиплнкативную с»тожность при и = 10 в 1,4 раза, при и =!0т— в 1.9 раза. при и л 10' — в 2 раза. В этом алгоритме достигнута одновременная минимизация нультиплнкативной, аддитивной и общей сложностей в отличие от алгоритма Винограда.
При этом выигрыш по мультипликативной сложности при «» = 13 составляет 1 %, прн и = 10$ составляет !2.42 % н дости«вет максимального значения 12,6% при п > 10«. По адднтивиой сложности выигрыш 1% наблюдается прн п —. 28; составляет 12.2«х прн и: 10' и достигает максимума 12.5'х при и = 10'. Выигрыш по общей сложности имеет место прн и > 25 и достигает максимума 12,5'й при и — 10'. По отношению к быстрым алгоритмам Штрассеиа и Ви«щграда-Штрассена минимизация муль. типликатнвной сложности алгоритма (2.230)-(2,235) достигается при и с 45.
Кроме того, рассматриваемый здесь алгоритм обладает умень. щенной адднтивной (при»«,=. 10«) и общей (при и < 965) сложно- стями. По сравнению с быстрым алгоритчои Елфимовой-Ка««нтоновой предложенный алгоритм обладает уа«еньщ«и«нымн аддитивной и общей «ложностямн при рав««ой мульти««лнкативной сложности», 2.!0.6.4. Алаориагмы длл базовой опера«(ии (У = С+ 2 .4«7)« илеа«очиь«х меа«одоа линейной алаебры. Для болыпниства численных методов лннейиоЙ алгебры н многих зада~ вычислительной ма.
тематики разработаны их клеточные аналоги )133), свойства которых обеспечивают возможность быстрого решения задач произвольных размеров на различных вычислительных системах и создания эффективного программного обеспечения для таких систем.
Указанные клеточные дна~о~и требуют для своеЙ реал«изациг« ~олько два типа оп~раций: базовую операцию вида () = ( ' + ',~ Л«В« »«т »»з р' =Б!г «=«ь=« »те Р'у =Е 2 м«ь~« е ч 'с е с с ««Э гц р»з 2 Л з»-«ль-«зь-Щ-«' ««ь « (где А, В, С', (у — ~в~др~~~~е матрицы ра~~~ра г, 4 — перез«енный индекс суммирования) и нестандартную операцию, которые составляют малый процент общего числа операций алгоритма н могут быть произвольными алгоритмами линейной алгебры.
Весьма важным является положение (133); «...рассмотренные выше гибридные алгоритмы (2.230)-(2,235) и (2.10,6,2)-(2.229) могут быть использованы для ускорения вычисления клеточной операции (2.237) за счет преобразования их структуры информационных связей с привлечением свойств коммутативности и ассоциативности операции сложения. В этом случае быстрый регулярный процесс вычисления указанной операции иа основе алгоритма (2.10.6.2)-(2.229) осуществляется путем преобразования выражений (2.236) и (2.237) следующим образом: 2 1Щ Щ 'м = аы — п2»-1,2»-1* Щ (б а2» 1,2»-1 а2»,2»- $ ' (1) 2(1) Ц2$-12» 41» 2(1) (1) «в(1) «/4 Ы« =Ей«»-$3,-1 4»-3271 »==! »$71 4.
~2$-1,4»-3 о2в-вл»-1' » — 1 Р, =~'(=, — „-, '--»' ), 1 1(п $(1» (Ц! «74 4(1) т ЗЩ Зй) = Е. 31.2»-1'3$3» »»в1 2 „в . 211$2И),2Щ ) Р,,=, (-„ Мв « 1» 21.» 21-!.»* »Р» ~ «2»-1 ''«» 2$" 3, ».(1) ьЩ ~»7 "2»-1.21 32»-1.27-1' 6 б(11 3(1) 3»1 = 2»37 а») 7 Ф (1) 4»1 = ($2»,27 (»2»-1,27.
3 6(1) (1) 3»7 = '»7 О2».27.-! 1',7',й = 1,2...,,7772;1 = 1,2, ...,4.«. В конце процесса только один раз выполняются вычисления. 1 $4 2 1 4 3 3 6 «о=Р;;+4 «;,=«ы+Р;; «;,=Р(7+Р(, (2.240) $,7' = 1, 2, ..., 7172; 2 3 $(2»-1„27'-1 = с2$-1,27-1 + Рву + Р»7 1 3 $«2» $,27 — сы-(,27 + «Ц + «»1» (2.241) $«2»37-$ = с2122-1 + «17 Р»7 $(2»л, =с21.27+«ы+Р17 2 3 Вывод, приведенный в (133), формулируется так: «Общая вычислительная сложность алгоритма (2.238)-(2.241) составляет И;4~ = И"31 + 1У« = ~ (1,7573 + 272) + 72 (операций умножения/сложения).
Эффективность рассмотренного алгоритма состоит в минимизации его аддитнвиой сложности по сравнению со сложностью вычисления операции (2.237) с помощью алгоритма (2.!О.6.2)-(2.229). Прн этом выигрыш составляет б = (4+ 1) гт операций сложения. что прн ограниченном размере клетки является существенным ускорением вычнс»тення операции (2.237)* Аналогичным способом воспользуемся прн построении быстр(н"о алгоритма для вычисления клеточной операции (2.237) иа основе гибридного алв орнтма (2.230)-(2.233). Выражения (2.23О)-(2.232) принимают анд,' ЬЩ 3(1) ЗЩ) 6 «( 6(1) 6Щ 6(1)) ~17 7 ' »7 «'- ° Ц» 7 1 1 = Е (31.2»-1+32»3)(32»-13+ 3 л») ви) 2(1) 6(1) 6Щ 20) »ж1 «,Ч 2Щ . 'с в й) Ь(1), ъ»Ь(й, аЩ ,Е (О21-14»-3 + 4»-127-11 ( 4»-327-1 +»»2$-!4»-1)» »»»» $ » 74 1),Е., (о2в-1,4»-2+ 4».27-11( 4»-237 $ + 11«в-),4»)' »»» 1 »74 =Х.( л»-1+» )( — .+ ., ) 4Щ ЗЩ 7Щ 7(1) 3(1) » 1 К (313»- +32»3)( 2$-1.
+авл ) 6Щ )Щ ЗЩ 6(б Ц() »74 6Щ 4Щ Щ (1) 4Щ = Е (3$,~-1 + й4».27) (й4»-тд«+ 3(л») »в» $ 7(1) Щ 6(й ЗЩ Щ = Х: (оъл»-2+ 32»,) (32»-1, + ож4»)* »ж1 » 74 В!1) (1) (О = Х. »*4Ь.22 ' (»«Ь-2Д а ! »/4 6(!) ч 4(1) 4(0 ээ = Л а»,24-1 ' а).эь Ь1 »,Ч тий ч (!) , (1) !Э = ~ «КЗ1.4Ь-2 ' О21.4Ь ь»1 (1) (1) оз«ль-1 + паьзь 1О) (1) а«ь о24-!дь-1 (1) (1) 2»-1,2Ь-! О21ДЬ-1' (1) 2(0 О21-1.2Ь ага 2 2 ! 4 3 В В 17 =Ру+Ру 21 =10+Р ° «»у Р12+Р«з' (2.245) 1,7' = 1,2,...,г/2, = С21-)дз-1+ Ры + РЗ!З 3 = с2»-)ду + 1»' + 20 2 т = о)сд)-1+ 112 — Р, ° = сэ» 2; + (,, + )э;„, 4, ) = 1, 2, ..., г/2. Мультнцликативная, аддитивная и общая вычислительная сложности алгоритма (2.242)-(2.247) соответственно определяются формулами «133) (4»з(~4~) + (4'з!'а) = 4 «0.4357 гз + 1,75 гэ) (опеРаций УмножениЯ), И„(!)-22) —.««1.3125 '-1,75 ')+ + ~ «1.75 г2 — 7г) + б 2 гз — (б — 1) 3,5 гз + 2,75 г2 = С «1,3125 гз + 5,5 гз — 7г) — 0,75 г- (операций сложения), И'ц+ 14', = С «1.75 гз + 2 гз) + гэ (операций ук)ножения/сложения).
Общий вывод в (!33) сформулирован так: «...рассмотренные выме гибридные алгоритмы (2 10,6 2)-(2.229) и (2,230)-(2.235) имеют где 4,.) = 1, 2, ..., г!г2; й = 1,2, ..., г/4; 1 = 1, 2, ..., С. Для вычисления матриц 7ч (( = 1,2,3) и .0 используются соотно- шения практическую ценность н расщнряют семейство алгоритмов умножения матриц Наименьшая операционная сложность и регулярность вычислений этих а!!горитк)ов. а также построщп!ых на нх ощ)о!к быстрых алгоритмон (2.238)-(2.241) и (2,242)-(2.247) для базовой операции клеточных методов линейной алгебры создают все предпосылки для нх эффективной реализации на различнык 1ьзраллельиых вычислительных систеэьэх и проц!»ссорных массивах с систоличсской ор!анизацией вычислений».
Как неоднократно указывалось выще, в сфере рещения проблемы создания систем самонаведения задачи. рассматриваемые в кинге, составляют солар канне лищь одного сегчентз, С!Иц!ификой этого сегмента является то. что в вычис,н»тельном эксперименте используется математическая модель системы высокой степени адекватности реальному контуру. и, таким образом, порядок системы дифференпиальиых уравнений — дещггкн уравнений, элементами контура являются нели'нейные и существенно нестационариые звенья. Методы, являющиеся теоретической осиовпи реализации вычислительного эксперимента, относятся к классу численно-аналитических. т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
