Модификация АВ-алгоритма и их применение к решению систем нелинейных алгебраических уравнений тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

ЛЕНИНГРАДСКИЙ ОРДЕНА ЛЕНИНА И ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ' ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

СИМОНОВА Вера Николаевна

УДК 518:512:83

МОДИФИКАЦИИ АВ-АЛГОРИТМА И ИХ ПРИМЕНЕНИЕ К РЕШЕНИГ) СИСТЕМ НЕЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

01.01.07 - вычислительная математика

АВТ0РЕ1ЕРАТ

г

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

ЛЕНИНГРАД 1990

Работа выполнена в Ленинградском отделении Математического института имени В.А.Стеклова All СССР

Научный руководитель - доктор физико-математических

наук, профессор КУБЛАНОВСКАЯ В.Н.

Официальные оппоненты: доктор физико-математических наук, профессор ДАУГАВЕТ U.K. кандидат физико-математических наук, доцент XA3AI10B В.Б.

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

Защита состоится " " lO/C f/ЛIS90 г. в час. на заседании специализированного совета Д 063.57.30 по защите диссертаций на соискание ученой степени доктора физико-математических наук при Ленинградском ордена Ленина и ордена Трудового Красного Знамени государственном университете по адресу: 198904, Ленинград, Старый Петергоф, Библиотечная пл., д.2, математико-механический факультет Ленинградского университета.

С диссертацией можно ознакомиться в библиотеке им.М.Горького Ленинградского университета (Ленинград, Университетская наб., 7/9).

Автореферат разослан " f^f " г.

Учзный секретарь специализированного совета Д 063.57.30

кандидат технических наук, доцент Ю.А.Сушков

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

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

Цель работы состоит в разработке эффективных алгоритмов численного решения названных задач. Первая часть посвящена исследованию и разработке новых алгоритмов решения спектральных задач для произвольных (регулярных и сингулярных) пучков матриц, как линейных так и полиномиальных.

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

Научная новизна. В диссертации получил дальнейшее развитие известный Л В-алгоритм, предложенный для решения проблемы собственных значений регулярного линейного пучка матриц. Исследование свойств _4,В-шага'для линейного пучка матриц общего вида способствовало созданию модификаций ДВ-алгоритма для решения более широкого круга спектральных задач.

Предлагаемые модификации позволяют ускорять сходимости процесса, уменьшать размеры пучка за счет выделения нулевых (бесконечных) собственных значений регулярного линейного пучка матриц. Расширение Л В -алгоритма для сингулярных цучков позволяет вычислять все минимальные индексы цучка, выделять его регулярный блок.

Для решения СНАУ от двух переменных разработан новый

метод, основанный на связи указанных систем с решением некоторых спектральных задач. Метод не требует знания начальных приближений и сводит решение СНАУ к вычислению собственных значений некоторых полиномиальных пучков матриц.

Все результаты являются новым! и научно обоснованы.

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

Апробация работы. Результаты диссертации докладывались на Всесоюзной конференции "Численные методы линейной алгебры", Новосибирск (Шушенское), 1980 г.; на Всесоюзной конференции "Актуальные проблемы вычислительной и прикладной математики", Новосибирск, 1987 г.; на Второй Всесоюзной конференции "Современные проблемы численного анализа", г.Тбилиси, 1989 г.; на конференциях профессорско-преподавательского состава ЛКИ "Прикладная математика и вычислительные системы в судостроении", Ленинград, 1989, 1990 гг.

Публикации. Результаты диссертации изложены в работах [I - 5].

Структура и объем работы. Диссертация состоит из введения и двух глав. Объем диссертации 125 стр., включая 6 стр. списка литературы из 61 наименований.

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

Во Введении раскрываются предмет и цель работы, сформулированы основные результаты.

Первая глава диссертации состоит из шести параграфов и посвящена некоторым модификациям Д В-алгоритма для решения спектральных задач пучков матриц.

В параграфе 1.1 приводятся некоторые известные сведения о пучках матриц.

Параграф 1.2 посвящен свойствам ЛВ -шага.

Для линейного пучка матриц D(A)= А -ХВ размеров wxtt Дб-шагом называется переход от пучка D(A) = А - X В к пучку М(Х) = й--Х(3+, где матрицы (2- и являются блоками матрицы Л _ ("» , столбцы которой образуют ортонормиро-

La. J

ванный базис правого нуль-пространства вспомогательной матрицы (X = [ А ' ~ BJ . Реализация Л В-шага осуществляется о помощью правосторонних умножений матрицы (% на цепочку матриц плоских вращений Ту . обеспечивающих приведение- ее

еат-iL-oj,

где L - есть ттрица размеров ж-х р полного столбцового ранга (.р ю UUlil d) , 0 - нулевая матрица размеров m х ( 2 И- ~р ) i б - результирующая матрица переотановок порядка hi j Т = П Tjj - результирующая ортогональная матрица преобразования. Последние 2п~р столбцов матрицы Т образуют'искомую матрицу Q „j^f j » Qf, матрица размеров П-х Сi?H-J)). В зависимости от решаемой спектральной задачи поредок зануления элементов матрицы и выбор матрицы перестановок в может быть осуществлен по разному и чаща воаго обусловлен желанием улучшить численную стабильность процеооа и (или) сохранить определенную форму матриц пучка.

В параграфа 1.2 устанавливается связь между спектральными (скалярными и векторными) хаоактеристиками пучков D(X)

И М(А).

Модификации Л В-алгоритма для выделения нулевого (бесконечного) собственного значения регулярного линейного пучка матриц посвящен параграф 1.3. Предложенный алгоритм конечный и состоит из вычисления последовательности пучков I^(X)=Ak-A размеры которых не возрастают. Переход от D,,(\) к DM1 (X) состоит из двух шагов. На первом шаге осуществляется с определенным выбором зануления элементов матрицы Ctk , при котором матрица (3. имеет первые И-к-1 (tK»=tlw6 Ак , - порядок пучка 1)к (А) ) стол-Шов нулевыми. На втором ниге

осуществляется строго эквивалентное преобразование пучка МК(А) = 0 _ — АА(+К) и результате которого нулевые столбцы первой матрицы сохраняются, а соответствующие столбцы нгорой матрицы О,'*' преобразуются в столбцы единичной матрицы, так что прообразуемый пучок приводится к форме Шура.

Долее следует понижение размеров пучка, т.е. переход к пучку Вк4, (Л) . При этом, если матрица Ак+1 особенная, процесс повторяется.

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

3 плр^играфс 1.4 предлагается модификация ЛБ -алгоритма со сдвигом, которая позволяет ускорить сходимость алгоритма при ¡^числении вещественных собственних значений регулярного лшюйного пучка натрии простой структуры. Кодификация состоит Л построении двух последовательностей матриц { Ак } и [ Вк ] (матрица одной последовательности имеет треугольную форму, а матрица другой - почти треугольную форму) по следующем/ предписанию (алгоритм I) л

А,-А в,~в

А г = А,-4Д В,-В4

Кг В. •

Матрицы Д^ и Вк вычисляются по вспомогательным матрицам А к и р с помощью ЛВ-!"ага,лс определенным порядком ганулеиил ачементов матрицы (\ = [Дк : - Вж.]» после.цояпгельности сдвигов. Предлагается способ выбора сдвигов, позволявши получать асимптотически квадратичную сходп-шегь посл'.'дсРат&чыю к каждому собственному значению, начиная с локмеиьмего. Справедлива теорена.

ТЕОРЕМА. Пусть на некоторог- шчге алгоритма I получено

I а00 а'*'

ил Л V .- я (К

(и«) £>„

I ('Г ' 4-1

в условиях алгоритма I получим |-^п) ~ | < }1£> .

В параграфе рассмотрели еце дна варианта ЛВ -алгоритма со сдвигом. Один из них юзволяет избегать случайных сдкигов и вычислять собственные значения последовательно, начиная с наименьшого. Другой вариант Л В-алгоритма рассмотрен для пучка, обо матрицы которого имеют почти треугольную фопг.г/,,

В § 1.5 предлагается -алгоритм. Алгоритм

является модификацией ЛВ -алгоритма и предназначен для ьи-числения структуры кронекеровскоп формы линейного сингулярного пучка матриц: позволяет одновременно осуществлять подсчет правых и левых минимальных индексов полиномиальных решений, элементарных делителей нулевого и бесконечного собственных значений исходного пучка и выделять его регулярны!'! блок.

Алгоритм состоит из вычисления конечной последовательности- пучков Ц,(А) = Ак - А Вк ■ , размеры которых не возрастают. Переход от 0К (А) к I) *»< (А) состоит из трех шагов, На первом шаге осуществляется типичный ЛВ-маг, ?•<'« находится правое нуль-пространство 0, матрицы 01 *=* =[Ак: На втором таге на/, дится косинусо-синуснон раз-

ложение матрицы л _ Г 1 и осуществляется первое ло-

1<зН

нижение прообразуемого пучка. На третьем шаге выполняется строго эквивалентное преобразование пучка, которое позволяет осуществить второе понижение преобразуемого пучка и шгаслить новый пучок Д^(А).

В результате будет построен регулярный пучокГ^-А^Абц, все собственные значения которого и соответствующие т элементарные д<;лители совпадают с конечными, отличными от нуля собственным:! пна.лншми и им соответствующими элементарными делителями исходного пучка О (А) . Вычисление щги'кх и левых минимплыпк индексов и элементарных делителей, соогьптетмуших нулевому и бесконечному собственным значениям, осуществляется в процесса алгоритма,

В § 1.6 приводится модификация Л В-алгоритма (блочный вариант) для решения проблемы собственных значений полиномиального регулярного пучка матриц. Цредложен опособ линеаризации полиномиального регулярного пучка в блочной треугольно-хессенберговой форме, собственный значения которого совпадают с. собственными значениями исходного пучка.

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

В § 2.1 устанавливается связь решения системы нелинейных алгебраических уравнений от одной переменной с вычислением собственных значений некоторого линейного лучка матриц; в терминах спектральных задач формулируется условие разрешимости СНАУ и приводится алгоритм вычисления всех корней.

В § 2.2 устанавливается связь между решениями СНАУ от двух неизвестных и собственными значениями полиномиального пучка матриц, построенного по коэффициентам исходной системы.

Цгсть т

.....- 0. (I)

Исходная система ^-нелинейных алгебраических уравнений с двумя неизвестными А и ^ , с коэффициентами из поля комплексных чисел, И- и »И - наибольшая степень А и ^ соответственно входящих в (I). н нн т

Введем в рассмотрение векторы А(А , Л Л,т/

и М: —. Тогда можно записать в виде

РсА,^) =БдюА или 6сА)М,

+-- +С0 - пучок матриц С размеров й*(н+1)

А л » Л »

Сл А^ч... + С„ - пучок матриц Ск размеров Цх (*н + 1) так что уравнение можно записать в любой из

двух эквивалентных ему форм:

6(А)М-0 или Б(>ол = 0. (2)

ТЕОРЕМАI.Для совместности системы р(А./О — О необходимо, чтобы правое нуль-пространство пучка О(^) (пучка Р(А)) было не пустым множеством.

Теоретические предпосылки построения нового алгоритма решения СНАУ рассматриваются в § 2.3.

В качестве базиса правого нуль-пространства 0,(}1) пучка Ж/О возьмем объединение минимального базиса из правых полиномиальных решений пучка и базиса ин-

вариантных подпространств, соответствующих собственным значениям jU.fr регулярной части пучка 1)( Рассмотрим уравнение

[а+ср-ха_(/о]У =о, о)

где и 0. (матрицы, составленные из к первых и п-

последних строк матрицы (3 (Д).

Уравнение (3) можно записать в виде

[(З+^-АОД^ЗУ =0 при ^ = (4а)

°<(я[ду] =0 при (4в)

Здесь и построены из п первых и П по-

следних строк матрицы О, С/1Г) , столбцы которой образуют базис правого нуль-простраг :'тва постоянной матрицы

где (¿1) , матрицы, составленные из первых И-

и последних и- строк матрицы IV (^ , Ск -матрицы

6 - максимальная степень полиномиальных столбцов \Vijli').

Справедливы теоремы.

ТЕ0РЕЛА2.. Каждому решению (А , Д) уравнения (2) соответствует решение (А.Д ; У) уравнения (3) и наоборот, каждому решению (А, ^ ; У ) уравнения (3) соответствует решение (А, Д) уравнения (2).

ТЕОРНДА ЗДДля того, чтобы пара чисел .М*) Удовлетворяла системе (I), достаточно выполнения одного из условий; число является собственным значением пучка £) (¿1)

числе является собетьешшм значением пучка

2. Для того, чтобы одночлен бил общим делителем

систеш (I), достаточно, чтобы пучок ~

имел, по крайней мере, одно правое ..биномиальное решение.

ТЕОРйлА $ .1, Для того, чтобы пара чисел (А(») была решенном (I) достаточно, чтобы число било соб-

ственном значением пучка ДС/О , число Х^*' - било собственным значением пучка О'/Ч/^0 ) ~А£}_ • Здесь (3'."( и{4>) и и<'>\ матрицы, оформирован-

- * ' л /Л

ные из б" пс рг.ых и о последних строк матрицы ц () , столбцы которой образуют базис правого нуль-пространства постоянной матрицы

2. Для того, чтобы пара (\ = ЧЧ/1)> была одномерным

решением (I) достаточно, чтобы А ^ (/О был собственным значенном пучка

где IV4 (¿0 и р,) сформирована из блоков равных размеров матрицы IV («!)■= [ 1

1 ^ I Н™ (¿0 I '

В параграфа 2.4, на основании изложенных теоретических предпосылок, предлагается следующий алгоритм решения СНАУ от двух перемеыш.

1. Находится регулярная часть пучка 0(/1) и ьычиоляютоя все ее собственные аначения

2. Для 1:<одого фиксированного формируется пучок <4а) и находятся все его собственные значения А,> Ак, а также устонавлинаотся наличие правых полиномиальных решений (т.е. наличие общих делителей систеш вида (- )

Пары ¿ --И... р, |«И...11 является нульмерными решения-

ми СНАУ.

3. Находится минимальный базис }1) из правых полиномиальных решений пучка 1)(. Формируется пучок (4в).

4. фнкга 1-3 выполняются с пучком Ц (_/(•).

Цунктн 1-4 выполняются до тех пор, пока на некотором шаге будет выполняться одно из двух условий:

а) пу ч г,к у I) - АIV ^1 /I) является квадратным и пучок не имеет регулярного блока;

б) пучки и (¿1) на имеют регулярных блоков.

В результате выполнения алгоритма будут найдена все конечные нульмерные решения СНАУ, а тскле общш делители системы вида (£1-^) ( (А - А,) , построен линейный регулярный пучок Д(А ) -,(|В(А ), собственные значзния которого совпадав с ояпо!.'ерн!ми корнями исходно:! системы.

В качестве вспомогательного приводится алгоритм виделомя регулярной части лннзйного пучка вида А {$1) - А В

5 параграфе 2.5 дано краткое изложение известного метода исключения для решения СИЛУ и в гсфаграфа 2.3 лредлагаггея его модификация, которая базируется на связи метода исключения со спектральными задачами для полиномиальных пучков матриц.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

1. Для регулярного линейного пучка матриц предлсколи и теоретически обосноьаны следующие модификации ЛВ-алгоритма:

1) модификация, позволяющая выделять нулевое (бесконечное) собственное значение и вычислять ему соответствующие элементарные делители ;

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

2. Для сингулярного линейного пучка матриц общего вида предложен ЛВС5В-алгоритм, позволяющий вычислять одновременно левые и правые минимальные индекс;:, элементарно делители нулевого а бесконечного собственных значений, вы-

делять регулярный блок исходного сингулярного пучка.

3. Для полиномиального регулярного цучка предложен, блочный

Я В -алгоритм.

4. Для решения СНАУ ол дцух (одной) переменной предложен метод, основанный на связи указанных систем с решением некоторых спектральных задач для пучков матриц.

По всем предложенным алгоритмам составлены программы и проведены численные эксперименты на РС 1Ш. С программами можно ознакомиться в лаборатории алгоритмических методов ЛШ1 АН СССР. Диссертант выражает глубокую благодарность научному руководителю доктору физ.-мат. наук В.Н.Кублановской за постоянную помощь и внимание к работе.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ:

1. Кублановская В.Н., Симонова В.Н. О некоторых модификациях алгоритма ЛВ .. - Зал.науч.сеыин.ЛОМИ, 1981, Ш, с. 117-137.

2. Кублановская В.Н., Симонова В.Н. О новом алгоритме решения обобщенной проблемы собственных значений. - Актуальные продлены вычислительной и прикладной математики, М., 1983,

о.106-116.

3. Кублановская В.Н., Симонова В.Н. Об одном подходе к решению систем нелинейных алгебраических уравнений. Препринт ЛОМИ, Р-7-80, 42 о.

4. Симонова В.Н. Клеточный вариант и алгоритмов.

Тезисы докладов Всесоюзной конференции. Актуальные проблемы вычислительной и прикладной математики. М., 1987, 0.162. 6. Симонова В.Н. Алгоритм ЛВС$Р . - Труды ЯКИ. Прикладная математика и вычислительные системы в судостроении, Л., 1939, с.44-49.