автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Решение уравнения Теплицева типа и применение в задачах дифракции

PV6 о*

1 i * ' Чл • *

ИНСТИТУТ проблем /ЛЯЮ.ИШ'Ш! и ABÏCМЛХКЗЛШН НШОНАЛЬНОЯ АКАДЕМ! ШК АРШШ

На прззаз рукописи

АГЕКЯН ГЛГЕК BOK52EESÎ4

РЕШЕНИЕ УРАВНЕНИЯ ШШЩЕВА ТЕПА И ПРЖЕНЕКК

в задачах дарлкцли

CS.IO.ie - ЦрИЙЭЕвНИЭ BbI4SÎC5JE!T8JtbEOS TOEDECÏ,

иатематшэского кодзляроваккя и математических катодов в научт?« исогэдованиях

Автореферат

дассорггацин на ссясканиэ ученой стопмга кандидата физико-математических наук

Ереван - 1983

Работа БЫПСШ1ЭНЗ я Институте математики Национальной Акздамия Наук Армении.

Научный руководитель - член корр. HAK Армении,

доктор физике -математических на.ук, профессор А.Б.НЕРСЕОЯН

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

зав.отделом Э.М.Погосш

- кан£.технических наук. с.н.с. G.Б.Аллахвордян

Вздущэя органккация - государственный интанерпый

университет Армении

■Защита состоится "ЗС" СЛ^Т- 1093 г. в " " часов ка засодэиш сгоцкэлизирозаннога совэтэ К 0Ub.2I.0I па щвкцгадэнив .степени кандидата фжяясо-илтзкатгивских наук в института проездам иформатики и автоматизации HAH Армении по адресу: И7Ь044, г.Ероьан, уд.И.Сзвака 1.

О диссертацией моншо ознзкоюггьоя в библиотеке ИПйкА HAH РА и институте математаки Ш-11 РА.

Автореферат разослан "¿4" oJi'iye. 1883 г.

у' Ученыа секретарь / стацкализировакного совята, я<\чтор Ф;1з«ко-иатемапяоскшс

г J.VK, профессор

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Во многих теоретических вопросах и задачах Ерясгадяого характера особую роль играят теклщэвые матраца 1.^»г .а,... ,п). В г."-гугности, такиэ матрица встрэчавтся в тоорли приближения рациональными функциями (ашрокрамадая Пада), в тоорк! орггогсиадькмх многочлэнов, в теории вероятностей и статистике, а так:® при чиалэнном решэнии задач приклэднсг влэотрздазамики* акустзппг, обработай кзобргнаниг и т.д.1,2

Дш . рбшэакя таких вадзч занно иметь аффэктивяыа катода офллдакл .т-иатриц. Известно, что любая; униБэрсзльныа татод сйрзкэшя <п*г») - .'¿атр5Щ трзбуот шпслквния о(п3) аддитивных и .•»•дьтйллакаткзшх сюрацж* <п->о), а дай т - кзтрзц - о(п3) (п->»).

В ряда .сдучагз алзьаптзш! матрица т язлгатся спэрзтсрн, н чгстпоети, большой интзрэс прэдстаагязт с&юод-тпшцзшэ матршн» Дгтя газтораг шзшэтн й1<к>. ±1,... ,*<«-!)? саж шегой <1*1) кэтркцаии.

Особу» раяь ягряпт матрица на.гого чзпжцэва ранга "^"З^Я» ¿и-*»®.....«» к«», гдз

к ■ ' ж Т1 .СяЭ СеЭ ... — .

- -¿\ -л ' ....."-1

Пройлэкы» связанные с ровзвизя а.ахзбра:ггос1гп: слотам с т<"Т°; т^-нэтргщэки в гослзднга два досятагзткя заходятся в цантрз

1 1£энавдзр У., Сзгй Г. Тешнцзвь'о форам и их щвкотэпеэ. - Н.: -ИД,

1 Г. 5 к ,

и 11эхацдгта И.О. ГзшвэпЕнэ и тегшщэвкв кзтрш?* и форгш. - М.:

внимания многих учаных3'"*.

Цель работы состоит в разработка быстрых и устойчивы: алгоритмов численного решения определенных задач теории дифракции, Основные задачи, решаемые в работе:

- обобщение алгоритма работа3 на случая т*-. матриц (в том числе и для блочных);

- векторизация (распараллеливание) обобщенного алгоритма (в частности, и алгоритма3);

- оцэнка сложности и объема необходимой памяти параллельных и последовательных вариантов разработанного алгоритма;

- апробация алгоритмов на широком классе тестовых уравнений;

- рекомендации к использованию в задачах дифракции.

Метода исследования. Теоретической основой работы являотсг обобщение подхода работы3 на основе понятия блочно-ортогоналыюгс разложения. Алгоритмы принадлежат к рекуррентному типу к строятся на основа квадратурны? формул.

Научная новизна и практическая ценность. Для т-матриц (в ton числа и блочных) получен новый. быстрый алгоритм обращения. Предложена новая схема распараллеливания алгоритма. Разработанные в работе метода, алгоритмы и программы могут бить использованы при научных исследованиях:

^ Воеводин В.В. , Тыртьшников Е.Е. Вычисления с тешшцэвыми 'матрицами. - В кн.: Вычислительные процессы и.системы. Вып. I. -М.: Наука, iss3, стр. 124-267.

4

Heinig О., Rost X. Algebraic Methods for Toeplitz-llke Matrices 2nd Operators. - Mathematical Research, band IS, Academic - Verlag,

Berlin, 1084.

t;

Cybenko G. Fast Toeplitz Orthogonaliaation using inner products, SI AM. i. SCI. STAT. COMPUT. Vol. 8, N 5, 1087, 734-740.

- В -

ab Для резонга линейных интегральных уравнений Фредгольма с эчти разностными ядрами.

б). Дяя рэгзния задач дифракции на бесконечном идеально роводязри цилиндре?

Предлагзэхиа алгоритм кожет Сыть реализован на современных вогопроцзссорных вычислительных системах.

Нз защиту выносятся слздуй:диэ поло:хеяия:

1 . Теоретическая разработка новых быстрых параллельных ягоритмов дая обращения т* - блочных матриц и решение кз этой з.чоЕв интегральных уравнений, возникающие, в частности, в теории фракции.

а. Новые алгоритм дяя ппстроения псевдообратноя нзадратнся зтрицм кстодом окагмлэния.

3. Численный эксперимент, содаркзщка результата решепга зетовых уравнения..

4, Сравнительный анализ результатов эксперимента с юультаташ вычисления по стандартным программам.

з. Рекомендации по применения разработанных злгоритяав при itraiffii! задач дифракции.

Апробация работа. Основные результаты диссертации доло:ганы нз минарэ отдала дифференциальных и интегральных уравнений Института ¡тематики HAH ■ Армении, в институте проблем информатики и ¡томатиззции HAH Армении.

Цубликации. Основные результата -опубликованы в шести работах.

Структура и объем диссертации. Диссертационная р?ботз. состоит ! введения и трех глав (всего десять параграфов).

Библиография содержит 41 наименовааиэ. Общий объем :ссвртации - 84 страницы.

Хенль X., Мзуя А., Ееетпфгль К. Теория дифракции, - М.: Мир,

- в -

/

СОДЕРЖАНИЕ РАБОТЫ

Глава I посапузяа рззрзс'откз алгоритмов дет обраяэния блочно-ортогонального разлошаия котркц '.''.злого тешсюэзого ранга и векторизации (распараллеливанию) этих алгоритмов.

В § I главы I рассматривается блочная матрица а са - пйхпи полного ранга, удовлетворяющая слэдупшому условию' '. '

к

,СвЭ Са

"и»4 "1-1^+1 ""I. " '

з=1

... - ^ ♦ К "Г <°

где х^23, - (1x1) матрицы, 1=1,2.....ш-1. j-i.fi.....п-1,

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

(1=1.2.....п), (чА -блочные (т1х1) столбцы)

блочно-ортогональная, т.е.

нулевая мзтрща, если . невырожденная матрица, если

то,скажем, что дано блочно-ортогональное разложение матрицы а.

Если к» а имеют такие же свойства и ак=о, то скажем, что дано обрзщэние блочно-ортогонзльного разлошния.

Доказаны.две'основные лэмми, относящеюся к взаимосвязи матриц

а, кио.

В § 2 главы I на основании вышеупомянутых лемм построен экономичный алгоритм джя обращения блачно-ортогонального разложения душ матриц, удовлетворявши!» условию (1).

АЛГОРИТМ:

(

¡Initializations

Ч1 = pí ~ (p-nlxl )

Ь = CCr:> = dCr° = O. r=1.2_____к <r.b.CCr:,.dCr:)-<T.+2k(n-i)}lxl)

p= /î^^û. р-1.2.....к (ф. fi, . ni л)

Ч^; P-Pj_. q^"1. Xrju--CXCr:>. Х^]. Г,м=1.2.....к.

I MAZIJ LOCP»

j=2 to n

У=-СЧ1, Zqj^Js V=qm+kCn_1:)(j_i:

""■^kCn-ia'.j'-i For r=l to к

. ^r-^^W-akC n-15 —Cr-15n,J -1 к

.СгЭ

,M=i

END

к к •.оэ,, ^ V

'j ■ ^j-l + 4XY + fv + bU + I с Vr * I d Ur

г «1 г =1

к к

^ Г „СгЭ,

Pj = 2qPj + pXY + фЧ + /Ш + J Ф Vr + 1 ft' U.

г«1 r=l

Y - Cqj. qjl"1; Pj - Z^tqj- tp4J)

For r=l to к

V =CP., XCr3] J

cCr>= cCr)+ ^

d - d + qjYP^gfcc.^^j.^^^

,СгО СгЗ О** = Ф * PJ YVГ '

„С г 5 „СО

" " * ^ т+гкСп-13-Сг-1Эп» д

емо

Л = г + Я.1Р ^ , ^ и+кСп-О о

ь ж ь •■ аЛ'?!*, , . .

ш V ^ п+кСп-;.;

р - А « Ч' кСп-1Э . 4

л?

ч * ч *

р « р +

ег.'о.

„ . Г, Т г 4 т.т г т т т ,т

.. - ^ а, 1а1 ; а = Ц' а21- '

т т т ' Т т т

с 2э саз СЗЗ сзэ1 СкЭ СкЭ' 1

-1" 1 • п-1 ..... 1 ..... п-1..... 1 '~1п.....

" Га" 1 г»

т .,т

г~I п-1 *1 '"п-1 -----К1 .....Кп-1.....J !

В чалтаом случае, когда а есть блочно-тэшшцэвэя матрица,

а а1у Ч"Са1Гп- аг ,п-1.....ахгУ- столбец

ргемороа <п~1)1х1.

Кроне того, сдолани слэдувщиэ обозначения: Л'* = сх,уз; е,- единичная шприца <1x1), е- нулевая матрица <1x1), 20-;{вадратнгя матрица следующего вида

в . . . в Е

Ехе .... в

о

в . . О К. О

_ а -

¥=<11ад10, . . . ,0.1. . ( . .1 .0, . . . „01 ;

Сп-13к1 »1 Сп-1Эк1

вСТЬ (т+2к <п-1 ) )1х(т+2к (п-1 ) )1 МЭТрИШ, ГД9 \ {У- <п-1 )+1 +1,

п+Зк<гг-1 )-<2-1 )п) ■» ПрИ 1=1 .2. . . . ,га-1 ; 3=1,2.....к. СЧЗТ.ХТЬНЫЭ

элементы равны нулю, а г = з0 + ; ■¿~'1 = - ^ ^ Отметим, что в случае, когда а есть блотно-тешвшезая матрлца, в выражениях размеров матриц 2. V лада принять к=1. а на к=-о.

Слккность этого алгоритма <в смысла глазных члапов) равна бк+3Требуемая ПаМЯТЬ'О(п1) (.~.<й; п. т->ио).

В п.2 § 2 главы I рассматривается матрица а, удовлвтвсряго^гя условию (1), ь=2, в частном случае = -Ч^-и- Построен

аналогичный алгоритм для обращения блочно-ортогонэльного разложения

СО СЛО:КНОСТЬЮ 23т! э+32п2.1 3.

В § 3 главы I изучается задача распараллеливания алгоритма обращения блочно-ортогояалькага разложеняя для реогэ; ;ля алгебраических систем с матрице®, удовлетворяющей условия (1). '

В случае блочно-тешицэвоа матрица построен векторкзовзнзыз алгоритм с линейным ускоренная, при этом требуемая опэратиавзя память хетеет объем порядка о{п) (п->-»). в случае матрицы малого тегшщэвз ранга линейное ускорения достигается при наличии оперативной памяти порядка о(пг).

Глава II посвяарнз решен® алгебраических систем и интегральных уравнения.

В § I главы II обобщен метод - окзямлеяия для построения псевдообратног матрицы. В случае симметричной изтркпы отот алгоритм имеет меньшую сложность, чем известный алгоритм Грзвиля.

В §§ 2-3 главы II для решения интегрального уравттення Врэдгольма второго рода с ядром к, для которого а к а к к . „ „

— - — - у «Са5<м (г:

«Я. дХ ¡Ч

- lo -

предлагается д^гфопгзкровать уравнение с помощью квадратурш формул bücükox. точности. В результате пэдучается систег алгебраических уравнений с блочной матрицей типа (i), решеш ¿".старой проводится по методу гл.1.

В глаш III разработанные алгоритмы примэнявтся для pecöm . классических задач дифракции.

Б § I в с.иуь;з& дифракции на бесконечно длинном идеалы проводящем цжашдре дая плотности поверхностных токов получают« кзтофзлыш© уравнения Фрэдгольма второго рода с разноствыми ядра; <т.о. и (г) о).

Б § 2 главы III приведены результата численного эксперимент; оиюсгаэгсся к рэшэнк* тегшщешх систем и интмраяшас' уравнен; ИауЧС^вКГ 1ШЮВ.

б | 3 гдзеы'ПГ разработан определенный подход для рэшеш уравнзяш Ванера-Хоп^ к приведены результата числзпнся зжсшршкэета. • , ,

В § 4 главы in гркввдэны результаты численного. резгеы тэсг опил интегральных ¿фЕьношзг с ядром разностного ткпа (г).

Ояновнш? равультати работы

з.» .Разработаны новые быстрш, ккзащгаэ сложность о(пг) (п->о аягориткы д;ш обращения тк- блочных катриц размере rsm и рошлнЕя на этак основа кпогрглъшг уравнений, возникающих, частноеги( в теора: дафракцли. ■ .'

а, Подучен навыа. алгоритм для построения псевдообратнс хшедпеткои матрицу пето док окаяошшя.

4. ■

а. Нредишишк© элгорапи порядка о(ь*) -(ь* ——> о, ь отрэвок равзошраоа дискретизации) реализованы для тестовь зргиаоаих я готовы к уштрзблзшш для решения <юотватстаушю хргоэдш» РЗДЗ <s.

I. Ъаедяюыа ьычислоша приведешь! в аде т£йлад к 'дезгргаа

которые подтверждают хороши числвпше, свойства ргзработапнкх алгоритмов.

Основные результаты диссертации опубликованы в слэдувгдих работах:

1. Агокян' Г.В., Нэрсесян А.Б. Построение псевдообратнса квадратной матрицы методом окавмлэния. Депонировано в Арм. ШЙНТЙ, М та - Ар ее, юяч, гг.

а. Агекяя Г.В., Нэрсесян А.Б. Блочно-ортогональнсе разложеякз натрии тешпедзва типа и быстрое решение некоторых интегральных уравнений. Депонировано в Арм. НЖГП', N - Ар <*'з. 1аеэ, аз.

з. Агвкян Г.В. Экономичный алгоритм решения янтвгральчого уравнения с почти разностным ядром. ДАН Арм.ССР, "Математик-::'*, тем «о, N г, *РОО, ьо-в4.

-I- Агекяя Г.В. Экономичный алгоритм решения задачи паьузкх-ких квадратов о матрицей малого тешицевего ранга. ДАН /рм.ОС.?, "Иггоэтотика", том ш. н *, 1йяо, г?~ао.

н. Атэкян Г.В. Об одном методе числиаясго росожгя шггагрального уравнения Винера ■-Хопфа. Изв. АН Армении, "Мчточатика", х'счп. м з, юа1, гва-271.

е. Агокян Г.В., Нэрсесян А.Б. Векторизованные алгортти! решения систем с матрицами тешгишза типа. ДАН Арконяя, "Вычислительная математика", том аз, м 1, юза, 17-гз.

Сдано в производство 15.03.1991г.

Буя. 60x84 поч. 0,75 листа Заказ ICO Тираж ICO

Цех "Ротапринт" Ереванского госуняверситета. Ереван, ул. Ал.Макухлна 'Ь I.