Приведение произведения отражений хаусхолдера к каноническому виду тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

АКАДЕМИЯ НАУК СССР

Сибирское отделение ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР

На правах рукописи БАБЕНКО Виктор Николаевич

УДК 519.61

ПНШдаИБ ПРОИЗВЕДЕНИЯ ОТРАЖЕНИЙ ХАУСХОЛ.ДЕРА К КАНОНИЧЕСКОМУ Б1ЩУ

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени к»шд!'д«?э фдаико-катека'гических наук

I

Новосибирск 1991

Работа выполнена в ИНСТИТУТЕ МАТЕМАТИКИ СО АН СССР Научный руководитель:

член-коореспондент АН СССР, профессор Годунов С.К.

Официальные оппоненты:

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

профессор. Ильин B.II.

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

Ведущая организация: Волгоградский политехнический институт

Защита состоится " ,) " ¡Л-г-О^О»i 1991 года на

заседании специализированного совета К 002. 10.01 в Вычислительном центре СО АН СССР по адресу: 630090, НоБОсибирск-ЗО, пр. Академика Лаврентьева, б.

С диссертацией можно познакомиться в читальном зале ГПНТБ СО АН СССР (пр. Академика Лаврентьева, б).

Автореферат разослан " jäi IS0I годи

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

К 002.10.ОI к.ф.-м.н.

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

Актуальность темы. В предлагаемой работе рассматривается вычислительная проблема приведения произведения отражений Хаусхолдера к каноническому вида.

При решении задач линейной алгебры во 'многих случаях исходная матрица ортогональными преобразованиями приводится к тому или иному каноническому виду. Применяемые преобразования -отражения Хаусхолдера и вращения Лкоби. Узким местом этих методов является трудность прогноза количества потребующихся ¿ращений, что приводит к неопределенности объема оперативной памяти j.riM /Dil/ для размещения вращений. К тому же вращений может быть так много, что возникает проблема их размещения в ОП. Чтобы избегать перечисленных проблем, можно воспользоваться приведением произведения отражений к каноническому виду, позволяющему отказаться от хранения преобразований вращения.

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

Цель работы. Цель» настоящей работы является разработка и исследование численных свойств алгоритмов, приводящих произведение отражений Хаусхолдера к каноническому виду.

Научная новизна. Выполненная диссертация является развитием и продолжением работы Куплена [l'J по приведению произведения отражений к каноническому виду. Новыми в ней являются алгоритмы повышения индекса и компенсации произведения отражений. Производится тщательный анализ разработанных алгоритмов. Предложена специальная функция, позволяющая обеспечить отсутствие чувствительности алгоритма повышения индекса к ошибкам вычислений. доказанные оценки точности выполнения алгоритмов повышения индекса и компенсации отражений позволили получить оценку точности выполнения алгоритма приведения произведения отражений к каноническому виду.

По алгоритмам повышения индекса и компенсации произведения отозткетР написана программа изменения индекса произведения отражений.

Практическая ценность. Применение программы изменения индекса произведения отражений совместно с процедурой отражения вектора обеспечивает приведение любого произведен;!.'; отражений к каноническому виду с гарантированно'" точностью. Это позволяет

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

Методы исследования. В диссертации используются методы численного анализа, заложенные в работах Д.Х.Уилкинсона, СЛ. Годунова и др.

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

Публикации. По теме диссертации опубликована одна работа

[I].

Структура и объем диссертации. Диссертация состоит из введения, двух глав, двух приложений и списка цитируемо^ литературы. Работа занимает 105 страниц машинописного текста, включая три таблицы. Список литературы содержит 18 наименованиГ: отечественных и зарубежных авторов.

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

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

Первая глава состоит из пяти параграфов.

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

Пусть б-/>,, - ортогональный базис вещественного ев-

клидового пространства . Отражение Хаусхолдера

называется элементарным ортогональным преобразованием индекса 1[1П.(Р]=^)) , если С р*£г$0. Произведение отражений 2 -Р^.. П) называется каноническим, если индексы отражений упорядочены отношениями:

Ы(р1)< ...¿ЫРг).

Лемма 1.1.2. Всякое ортогональное преобразование в имеет единственное представление в виде канонического произведения отражена?.

Цель второго п-зрагра^а - установление свойств произведений - 4 -

отражения, которые затем'будут положены в основание алгоритма приведения произведения отражений к каноническому виду.

Пусть векторы О. v, ё образуют отнормированный базис в плоскости П . Преобразование вида

w , „ ] „, S = I+ (aifyиш ¡m~f-/](aiS)

осуществляет поворот векторов, лежащих в плоскости f] , на угол У и называется вращением Гивенса плоскости /7 .

Лемма 1.2.2. Произведение отражений PQ= il'ppjlptjq*) есть вращение плоскости fl~Pl(pj(j) на угол f~

Лемма 1.2.3. ПустьР*Р~рр* и Q =/- (¡(j* - отражения Хаусхолдера и лектор . Определим векторы

p = ([-UU')p и f = (I-li2lVf , тогда

Qp^IifliJ-pp'hPQ.

Лемма 1.2.4. Пусть Р~ 1~рр* и (j(jf - отражения

Хаусхолдера и U - произвольное вращение плоскости

П-Ж0.

Определим векторы ' pi= Uo и (j*- Щ , тогда

ll-ppitl-'ff)

•Лемма 1.2.5. Пусть Р=1~рр* и - отражения

Хаусхолдера индекса I и р fq , тогда 3/ пара отражений P-1-pp* и Q=l~qq* таких, что

Р6*Р0,Ш-1<1л($).

Лемма 1.2.б- пусть векторы р и (j , определяющие отражения Р=1~рр*' и Q = l-gq* , удовлетворяют условию: ¡ip-QH ±£ HQH , тогда

UlP-Q/U 2£,

3. Если p=(j , то pQ=I .

В третьем параграфе формулируется задача приведения произведения отражений Хаусхолдера к каноническому виду и описываются средства ее решения.

¡¡усть е задано произведение отрл*ени''| г~Г)...Рп..„г,уг

требуется построить последовательность отражений Рь.,.,Рг. такую, что Pi,.,Pi и In * ¡П ИЧ

Постаблешая задача решается с помощью применения трех операций:

1) операция упорядочения,

2) операция повышения индекса,

3) операция компенсации произведения отражений, содержание которых раскрывается в следующих определениях.

Определение 1.3.1. Индексом произведения отражения Р~Р1.,,Р// будем называть и обозначать величину

1п(р']'*£Ш).

1*1

Определение 1.3.2. Если индексы отражени" Р и О связаны соотношением 1ц (Р) > 1/1Ш) , то замену отражения, описанную в лемме 1.2.3, при условии И~Р , будем называть операцией упорядочения произведения отражениеЦп.Ш)^ 1/1 (Р))-

Определение 1.3.3. Замену произведения отражений, описанную леммой 1.2.5, будем называть операцией повышения индекса произведения отражений Хаусхолдера.

Определение 1.3.4. Замену произведения отражений тождественным (см. лемму 1.2.6, пункты 2,3) будем называть операцией компенсации произведения отражений.

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

Лемма 1.4.1. Пусть Р*1~рр* и 0 = - преобразо-

вания отражения Хаусхолдера, причем Ы(Р)=1п10) =-1 и рФд , тогда векторы р и ^ , вычисленные по формулам:

р=Р(Щ^р) , Ц = ир , где

удовлетворяют соотношениям:

Лемма 1.4.2. Пусть Р =1~рр* и - отражения

Хаусхолдера, ^причем 1п(Р)=[п(Щ = I и , тогда векто-

ры р и ^ , вычисляемые по формулам:

- 6 -

Т)ц], , где

=л-А / - А ^ +¿*= ¿-з/х^-т/х,

удовлетвоояют соотношениям

Ь результате исследования показано, что операции упорядочения и повышения индекса произведения отражений не чувствительны к ошибкам округлений, о связи с этим устанавливается, что формулы леммы 1.4.2 нечувствительны к ошибкам вычислений, формулы ке леммы 1.4.1 приобретают чувствительность к ошибкам округлений, если > 0 , что накладывает ограничения

А

на область их применения.

Пятый параграф посвящен описанию алгоритма изменения индекса произведения отражений.

Алгоритм изменения индекса произведения отражений

Л

1. , если да, то Х- и идти на 4.

2. ¡¡р-ЦЦЬ^ЦЦ* , если да, то X - 2 Нр , и идти на 4.

Г I, если р*Ц>0 У "1.-1. если р*(] £ О,

3. Выполнить компенсацию отражений р и 0 и идти на 10.

4. щи ¿¡щи , если да, то выполнить ИЗ и идти на 9.

5. \р1\ -< ири , если да, то выполнить и идти на 8.

6. < 0 , если да, то выполнить /?"/ и идти на 8.

7. Выполнить алгоритм $2 •

8. р* и/(1 УМ)1'2.

'4

10. Конец.

9. ^ =

В памяти ЭВМ число X с плавающей точкой представлено парой чисел: мантиссой >П и целочисленным порядком К причем Х= $ Ш , у - основание системы счисления, У ¿ГП ¿1 . При выполнении алгоритмов /? / и использу-

ется специальная функция

если /( четно если К нечетно,

г функция

Ее применение с использованием повыгенноЯ точности вычислений позволяет обеспечить гарантированную точность выполнения алгоритмов /?/ и .

величины ¿] и § характеризуют близость векторов р и Ц , и их подбор должен быть есунестрлен так, чтобы обеспечивался контроль за порядком Хм - маиинны-.« результатом ен-числения X • Кроме того, 0 должна удовлетворять еде одном;.' требованию - погрешность компенсации должна быть равна или несколько провылать погрешность выполнения алгоритмов и К2 . »»бор Орл и ¿^ осуществляется из '»тих же' соображений. Значения б1, , 6 , С/> и зависят от размера разрядной сетки и устанавливаются го второй главе.

Алгоритм У?/ основан на реализации -ормул леммы 1.4.1. Алгоритм Ц/ 1р'(]Р:д; ± О)

1. х=р?+й! -р*<?ре-<?<-, /м.

2. ¿-^//^/--Д-/^.

3. Ур , / = 1*1.п.

4. Щ

5. г -- иг*р, И/ - ¿у - = ¿>.

6. Конец.

В основу алгоритма положены формулы леммы 1.4.2.

-Алгоритм [р^С/ Построение ортогонального базиса плоскости а-Шря)

г

3. -^у-- л д.

4. 5 "Ц^Г)«*, П.

л» Л»

Вычисление векторов р у.

6. р1-21/=-9г/</'а-

7. -- Т-рЩ/ * (¿в */зг)2]

- 3 -

' -8.

9. Конец.

Алгоритм /?3 использует результаты леммы 1.2.6 (пункт Л. Алгоритм Я5

I. ()£~0.

3. Конец.

Леммы 1.2.6 (пункт Г и Г.2.3 служат для построения алгоритма

Як .

Алгоритм Я к

1.

2. $1*0, 3. Конец.

Лемма 1.2.6 (пункт 2) указывает на возможность компенсации отражений с гарантированной точностью.

Вторая глава состоит из четырех параграфов и содержит тщательное численное исследование алгоритма приведения произведения отражений Хаусхолдера к каноническому виду.

Одно1? из основных численных характеристик ЭВМ является число . Оно определяется следующим образом. Пусть

X. - {тХм\Хм.> - множество машинных чисел-с плавающей точкой, больших единицы, тогда £1 = 1.

В первом параграфе исследуется точность алгоритма повышения индекса произведения отражения Я1 . Его результатом является точность численной реализации алгоритма на ЭВМ. Пусть имеем исходное произведение отражений Р(} . В результату выполнения алгоритма Я1 получим произведение отражений , причем лл„

Целью второго параграфа является получение оценок точности ¡лгоритмов Я2 , /?5 и Як . Устанавливается такое важное ¡войство алгоритма- Й2 , как обеспечение построения двумерно-'о ортогонального.базиса плоскости вращения с гарантированно« ■очиостыо, что позволило получить оценку точности его выполне-

- 9 - .

ния • ч , 7т

Наряд;/ с этим показано, что выбор в качестве ¿у и йр констант k9£t и Qi.SSi обеспечивает гыполненне алгоритмов R5 и ff^i с точностью, описываемой неравенствами:

ши-ûh wu<,

HPQU-PQUwu,.

В третьем параграфе устанавливается, что выбор: Ô-SC'Cf, обеспечивает гарантированную точность замен?; произведения отражений тотдественным:

Щ-РОИ

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

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

!!(ûLP-Pûli^j--mu HPûh'PÛlUàr^m^

Пусть для приведения произведения отра^ени*1 г к каноническому виду Р потребовалось выполнить: Ну операций упорядочения, fin операций повышения индекса и ИК операций компенсации произведения отранени". Тогда справедлива опенка точности:

три -м* ¡у о) + ¡и о* - /и.

Автор выражает глубокую благодарность члену-корреспонденту С.К.Годунову за научное руководство и постоянную поддержку, э такке В.И.Костину за полезные советы и замечания.

Основное содержание диссертации опубликовано е работе: I. Бабенко Б.К. Алгоритм изменения индекса произведения отражена» Хзусхолдера. Новосибирск, 1930, 5:J с. Рукопись представлена редакцией Сибирского мате.м. журнала. Доп. в ьИНШ

- 10 -

11.10.90, I5350-B90.

ЛИТЕРАТУРА

i'. CiippenlJ.fi. Ott updating tkûzrvftiâtA fyod&cU о/ Лои4е-

fiôécù/t. tzß,cticM. f/iiWJt, fícd/^rncuísi, Ш-Щ MSb.