Построение информативного базиса на основе приливного оператора Лопласа и колебательных систем тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

"российская академия наук

СИБИРСКОЕ ОТДЕЛЕНИЕ

вычислительный центр

на правах рукописи УДК 518.5 512.83

Кощеева Ирина Владимировна

Посщюе>шс инфорясятвтго Оазиса m осно&е приливного оперсвща Лапмса и колебательных сиаяея

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

АВТОРЕФЕРАТ

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

Новосибирск-1992

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

доцент С.И.Кузнецов

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

дшшл специализированного совета К 002.10.01 по присуавденив учёной степени кандидата ваук в Вычислительном центре СО РАН по адресу :

630090, Новосибирск-30, пр.академика Лаврентьева,6.

С диссертационной работой шхно ознакомиться в читальном зале Вычислительного центра Шовосибирск-90, пр. академика Лаврентьева,6).

Автореферат разослан <2* 1992г.

профессор А.Ф.Воеводин

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

доцент С.Б.Сорокин

Ведущая организация: ЛЕТА 0ШЙ г. Дубна

Защита состоится "/£" илЛ 1992Г. в ч.^ии. на засе-

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

Е. И. Кузнецов

/

, 1. Общая характеристика работа.

.Актуальность тела.

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

1 )класс решений разностных аналогов модифицированных приливных операторов Лапласа и г)класс свободных колебаний систем с п степенями свобода. Цель работ. Создание и обоснование эффективных алгоритмов для построения информативных базисов. Научная новизна:

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

- Проведено алгебраическое обоснование постановки граничных условий при редукции задачи на сфере к задаче на полусфере для матриц Хафа.

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

- Получен алгоритм восстановления якобиевой матрицы по узлам и весам ортогональности многочленов.

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

сданы в ГОСФАП.

Ащюбсщия работ. Основные результаты диссертации докладывались на семинарах ВЦ СО РАН и ИГ СО РАН, на Школе молодый учЗннх ВЦ СО РАЙ (Новосибирск, 1990), нз Всесоюзной конференции "Актуальные проблемы вычислительной и прикладной математики" (Новосибирск Л990), на Всесоюзной конференции молодых учёных в ТМД (Москва,1930).

Публииащш- По теме диссертации опубликовано 7 рзбот.

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

г.Содержание работы.

Во введении дап краткий обзор спектральных подходов к построению информативного базиса.

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

В §1 рассматривается циклическая матрица якобиевого типа:

р1а1 с2Ь2а2

°П-1Ьп-1аП-1

п п

с условиями о1ап> О, ск+1ак>0, к=1 (1 )п-1 '^Е,0!^^

®к

и последовательности

Ф0=о, ф1=1, а1фг=(Х-Ь1)ф1,

(р0=1, ф1=0, аг<р3=(Х-ьг)фг^

«к^^Л- к=3(1)п,

являющиеся лотейно независимыми .

Собственные числа матрицы в есть корни многочлена РП(Х),

'V 2'

а системы многочленов ^ ( к=1(1)п) есть системы Штурма. Пусть

Фп^)=0, ¿=1(1)п-1, (1)

VI 0у=о,¿=1<1)п-1, (2)

Далее, с помощью ряда неравенств, сформулированных в леммах 1,2 устанавливаются следующие важные неравенства о возможном взаимном расположении корней и

V ^ < < ИЛИ

^ С ^ < <^,.1=1(1^-2,

и неравенства, свяогпзавдие корни Х^.ц.^ и г^:

либо ^^¡И'

либо ' ¿=1 (1 )й-2.

Следующая теорема является основной для этой главк.

Теореяа 1. Пусть выполнена условия (1) и (г).

Для того, чтобы матрица в имела кратное собственное число

^.Г^М-И £=1(1)п-1, необходимо и достаточно

выполнение условий: 1) ц^ =

Анализ взаимного расположения корней Л, ц и v, проведенный в §1, позволяет построить эффективный алгоритм нахождения как кратных, так и прости корней матрицы в, который описан в §2. Алгоритм представляет собой сочетание метода окаймления и метода Миллера (последний используется для решения эскалаторного уравнения).

В 53 приводятся некоторые сведения, касагациеся собственных векторов кососимметричных циклических матриц. В основном содержание данного параграфа носит справочный характер. Особое внимание уделено случаю чётного порядка матрицы, для которого существует алгоритм более простого вычисления собственных векторов. Здесь данный алгоритм сформулирован более ч8тко в части, касающейся вычисления действительной и мнимой части собственник векторов, соответствующих простым и кратным собственным числам.

В §4 рассматривается частный случай собственной проблемы для кососимметричной матрицы порядка n=2m:

f О 1 -11

-10 1 о

0-1 0 1 1 -1 О

Вторая глава посвящена проблеме информативного базиса в Rn на сфере. Одна кз целей построения Оазиса заключается в том, чтобы специальным выбором Оазиса сделать возможным использование сетки с крупным шагом. В данной главе проводится анализ свойства симметрии и антисимметрии относительно экватора матриц Хафа, что позволяет задачу на сфере свести к задаче на полусфере. Для построения базиса используется ряд новых алгоритмов, основанных на результатах гл. 1. Перше два раздела данной главн носят справочный характер и касаются приливного оператора Лапласа, остаточных уравнений и их разностных аналогов. В третьем параграфе анализируются матрицы Хафа. Пусть

Ъ,

2 а2

сМ-2 ЪК-2

с Ъ N-1 N-1

где

л1пО,

кИ /?

(Т2 -соо

°кг

зтЭ,

к-1/2

(Г2-соа е|1/2)я1пвк

Ьк=-

ГГО

,4% .

(12-еав )з1пг6к

1ТО 4х

аг(Гг сов^в^) - соа2в )г

" ск ~ ак~<1к'

, к=1 (1 >N-1,

з - число разбиений вдоль крута широта, - число интервалов вдоль меридиана, причем точки полюсов -я и н-я в матрицу не входят. Размерность матрицы N-1 зависит того, является ли экваториальная, точка узлом сетки или нет. ;ли является, то гс^гги-г, иначе к=2п+1. зтрицу Й симметризуем, А = ОЙ, где А - симметричная матрица, Б - диагональная, О=Ша£{з1п0к}, к=1 (1 . ?жяо 3. Матрица А симметрична относительно второй диагонали, ¡мма 3 отражает свойства симметрии относительно экватора 1ффоренциального оператора, что позволяет свести задачу 1 сфере к двум задачам на полусфере с постановкой на гваторэ граничных условий Дирихле и Неймана (назовём это ¡дукцией основной задачи). Редукция же разностного оператора >зможиа на при каждой аппроксимации условий Дирихле и ¡ймана на экваторе. Выясню,!, при каких аппроксимациях

2

граничных условий редукция возможна. Рассмотрим случай N=211+2.

Матрицу а представим в блочном ввде, используя свойство симметрии:

Ап ^п 0 апеп VI ап+1е1 0 а1й-1е1 тАп

тАп "

а j я

о 1 1 • "о

, J» £ ,

тогда собственную проблему av » ADV можно записать следущим образом:

Anu + Vn+l^n W bn+1vn+1 + an+1vn+2 an+1VlHiei +TAnW

A.DnU

dn+1Xvn+1

X TDnW

где D =

Г °п 0 1 ■ и

SS Vi V = » vn+1

0 т°п. W

, T*V=JDnJ.

Тогда

(Ап - М>ГЮ - -а-п+1еп>

Ъп+1*п+1 + ап+1х/п+2 - (3)

( ^ - " .

Возможность редукции разностного оператора будет

определяться свойствами симметрии, уп+1+1с = (условие

Неймана) или антисимметрии, уп+1+1с = - (условие

Дирихле),что в векторном виде имеет выражение :

И = Ы — Л/. (4) в

Это накладывает определенные условия на

Лемма 4. Для того, чтобы выполнялись условия (4), необходимо и достаточно выполнение условий Ф о,

= о

соответственно.

Теперь рассмотрим случай 11=2пИ . Собственную проблему АУ - ХОУ можно предыдущему случаю:

записать аналогично

Я "хопи ■

,апуп е1 +тАп*.

или

'<Апи -ЛОп>и - - апч/п+1 еп ' -*ОпШ - - а^пеп .

Лежка 5. В случае N=211+1 матрица (дп-АОп) невыроаденна.

Лемма 6. Для того, чтобы выполнялись условия (4),необходимо и достаточно выполнение условия уп А О.

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

1 N = 2п+2. Для условия Дирихле Уп+1 =0, А^,

а для условия Неймана уп+2=уп, а^= ^+апеп-Меп*

2. N = гп+1. Для условия Дирихле уп+1=-уп, Ад- а^е®,

а для условия Неймана уп+1= уп, ^+апепеп

Итак, если разностная задача допускает редукцию, то решение собственной проблемы будет следующим:

собственные числа матрицы А есть объединение собственных чисел матриц А^д и А^ед, а собственные векторы - объединение собственных векторов матриц А^, продолженных на всю сферу со знаком минус, и собственных векторов А^, продолженных

положительно.

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

Пятый параграф посвящЭн аддитивной собственной проблеме, когда неизвестна диагональ симметричной якобиевой матрицы, но заданы собственные числа.

Пусть дп- известная симметричная вещественная трёхдиагональ-нзя матрица с нулевой диагональю,

В* - неизвестная диагональная матрица,

Л*- диагональная^ матрица известных собственных чи<

матрицы (А0+В), Ша^Х*.....Л*}

и* - фундаментальная матрица с условием

и*и*т= Е.

Задача состоит в определении матрицы в по извести матрицам А0 и Л? Решение этой задачи традиционно находится методом Ньютона-Рафсона

и<ВХВ-В)=Л*-Л,

где и(В)={ ^ ) ={4..} ,

В - новоб приближение матрицы в. В случае , считаем В*= В .

Рассмотрим

ел т зи т <зи

= (им)+ - и А - Л. — и7

- - Ч.-5 ЯЛ--}/ -г - и " <

<?Я{ 2

Сравнивая диагональные элементы, получим = и{что и

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

ГО

Лаяна 5.Справедливо представление

где

К =

Ш

ЭБ. " К и3 и.

О X"

1

1

IV

О

= <2{цд{и1;|, ... .и^},

причем и{ . - элементы матрицы и.

соотношения (5) можно использовать для анализа сходимости метода Ньютона и усовершенствования метода. Это можно сделать, например, следующим образом. В качестве очередного приближения Фундаментальной матрицы на некоторой итерации вместо и бер§м и + Ли, где п

Ш и^и.

При более детальном исследовании сходимости в методе Ньютона моэрто таким образом "подправлять" не всю фундаментальную матрицу, а лишь те собственные векторы, для которых наблюдается плохая сходимость. Бнли проведены некоторые начальные эксперименты, показавшие, что такой способ оказывается эффективным.

Третья глава посвящена взаимосвязи систем многочленов Штурма и колебательных систем с п степенями свободы. §1 содержит некоторые общеизвестные факты о простейшей колебательной системе, представляющей собой п сосредоточенных масс пр г=Ю)п, закрепленных в точках 1£, £=1(1)п+1, го=2п+.1-0 на невесомой упругой нити с натяжением о. Вводятся матричные объекты, связанные с этой системой. Это якобиевая матрица

г =

Ь1 ~а1 -а, Ь2

с элементами

а{ = т|т{ "4+1>

о 1

= Й.(-ГГТ +

-1/2

1=2(1 )п-1,

1

О 1

1 ®1 *о Ч а 1 1

последовательность ортогональных многочленов ук(М: а1у1 (А)=А.-Ь1,

акУк(Х)=(\-Ьк)Ук_1 (Х)-ак_1Ук_г(Х), к=2(1 )п

с соотношением ортогональности п

г?1°Л{Я£)у1(Х£) = • 1с,г=1(1)п,

п

где 1-1°1=1'

Значения многочленов ук(Л) в точках Х.^, з=1 (1 )п. соответствуют компонентам собственных векторов матрицы ¿, которые в свою очередь являются компонентами векторов амплитуд колебательной системы. Ортогональные многочлены ук(Л), к=о(1)п-1, образуют базис в пространстве многочленов порядка п. Пусть ук(\) представлен через свои коэффициенты:

<б)

и из коэффициентов а* составим верхнюю треугольную матрицу Б,

„о л

Б -

„п-1

ПУсть у - матрица, составленная из компонент ук(М у0(;ц >у1а1 )...уп_1 (V,)'

тогда у = V/ Б,

(7)

где

V/

Г 1 V, -1 .

. ХГ1

»г

матрица Вандермонда. Определим ганкелеву матрицу н :

N V ^ ъэ-*Ь V

П V

■VI •VI

VI \ ^а-г.

т.е.

Н = И1 С «,

,оп}.

где с=<Иае(о1,

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

разложении обратной матрицы Вандермонда Я? Т ,

(где для СЛ=1(1)п матрица ТЧ^} - нижняя, а

13

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

разложение н = (в Бт)-1, которое можно представить как

1 «V «V л №т Л(П

Н 1 = Р Т С 1 Т1 г.

Проведя треугольное разложение для Т С_1Тт= V О V", где у-верхняя треугольная единичная матрица, О - даю тональная матрица, получим соотношение

Б » I? V 01/2,

а элементы матрицы а{,ъг определяются через элементы Б следующим образом:

Второй алгоритм использует другое разложение н-1= и где

I. = 3, { =1 (1 )п - левая треугольная матрица,

определенная условиями гесли 1+3 > п+1. В этом алгоритме

ап-г^/ф

Ьп-£ = £=1(1>п'

а матрица 1_ = Й V где V - левая треугольная матрица.

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

Четвёртая глава посвящена описанию библиотеки программ, содержащей около 50 модулей и тестированию алгоритмов.

Список работ, опубликованных по тема диссертации.

1. Кощеева И.В., Кузнецов Ю.И. Восстановление тревдиагональной матрицы. ЖВМ и ВТ, 1987,N10, стр.1573-1578. 2 .Кощеева И.В. .Кузнецов Ю.И. Построение информативного базиса для типизации метеополей. Сборник ВЦ СО АН СССР "Гидродинамические- модели окружащей среды", Н-к, 1990. 2 .Кощеева И.В., Кузнецов Ю.И. Восстановление якобиевой матрицы. Информ. бкш. "Алгоритмы и программы", 50860000347, М., ВНИТЦ,1987,N5,стр.4

4 . Кощеева И.В..Кузнецов Ю.И. Метод наименьших квадратов для якобиевых матриц. Информ. бш. "Алгоритмы и программы", 50870000331, М.,ВНИТЦ,1987,N9,стр4.

5 . Кощеева И.В., Кузнецов Ю.И. Численные эксперименты с использованием информативногобазиса. Сборник ВЦ СО АН СССР, Системное моделирование экологических процессов", Н-к, 1991.

6 . Кощеева И.В. Некоторые особенности спектральных задач, связанных с разностным приливным операторы Лапласа. Препринт N950, 1992.

7. Кощеева И.В. .Кузнецов Ю.И. Построение информативного базиса. Тезисы докладов Всесоюзной конференции "Актуальные проблемы вычислительной математики". Новосибирск, 1990г.,стр.81