Дж. Деммель - Вычислительная линейная алгебра, страница 91

Поэтому многие привлекательные оценки погрешностей и свойства монотонной сходимости, справедливые для описанного в разд. 7.3 алгоритма Ланцоша, теперь не имеют места. Тем не менее, существуют эффективные алгоритмы и их реализации. Полезные сведения по этому поводу можно найти в [154, 171, 212, 216, 217, 233] и книге [213]. Наиболее современные программы описаны в [171, 233]; они помещены в НЕТЬ|В/зса1араск/геабше.аграск. Мас1аЬ-команда е18а (от «зрагзе е18епна1цез» вЂ” собственные значения разреженной матрицы) использует эти программы. Вторая возможность заключается в том, чтобы использовать несил«мешричный алгоритм Ланцоо«а.

Этот алгоритм пытается привести А к несимметричной трехдиагонельной форме посредством неортогонального подобия. Надежда здесь на то, что вычислить собственные значения для (разреженной!) несимметричной трехлиагональной матрицы проще, чем для хессенберговой матрицы, вычисляемой алгоритмом Арнольди. К сожалению, преобразования подобия могут быть весьма плохо обусловлены, вследствие чего собственные значения исходной матрицы и полученной из нее трехдиагональной матрицы могут сильно различаться. В действительности, подходящее подобие даже не всегда можно найти из-за явления, называемого «обрывом» [42, 134, 135, 199]. В [16, 18, 55, 56, 64, 108, 202, 265, 266] предлагаются различные способы исправления ситуации обрыва с помощью процесса, называемого «заглядыванием вперед», дается их анализ и описываются их реализации.

Наконец, к решению разреженной несимметричной проблемы собственных значений можно применить методы итерирования подпространства (алгоритм 4.3) [19], Дэвидсона [216] или Якоби — Дэвидсона [230]. 7.8. Литература и смежные вопросы к главе 7 Помимо публикаций, упоминавшихся в разд. 7.6 и 7.7, отметим еще наличие ряда хороших обзоров по алгоритмам для разреженных задач на собственные значения [см. [17, 51, 125, 163, 197, 213, 262]).

Параллельные реализации алгоритмов обсуждаются в [76]. В разд. 6.2 говорилось о существовании сетевого помощника для выбора между многочисленными итерационными методами решения системы Ах = Ь. Аналогичный проект разрабатывается в настоящее время для задач на собственные значения. Он будет описан в будущем издании этой книги.

7.9. Вопросы к главе 7 403 7.9. Вопросы к главе 7 Вопрос Т.1 (легкий). Проверить, что алгоритм Арнольди (алгоритм 6.9) или алгоритм Ланцоша (алгоритм 6АО), примененные к матрице А и начальному вектору о, порождают ту же матрицу Хессенберга Нь (или трехдиагональную матрицу Та), что и те же алгоритмы, примененные к матрице („>тАц и начальному вектору Я о. Вопрос Т.2 (средней трудности). Пусть Лг — простое собственное значение матрицы А, а д1 ортогонален соответствующему собственному вектору. Доказать, что в точной арифметике собственные значения трехдиагональных матриц Тю вычисляемых алгоритмом Ланцоша, не могут сходиться к Лг в том смысле, что наибольшая из вычисленных матриц Ть не может иметь собственного значения Л,.

С помощью примера 3 х 3 показать, что собственное значение некоторой промежуточной матрицы Ть может «случайно» оказаться равно Ль Вопрос Т.З (средней трудности). Проверить, что симметричная трехдиагональная матрица Ть, вычисляемая алгоритмом Ланцоша, не может иметь (в точности) кратных собственных значений. Показать, что если у матрицы А есть кратное собственное значение, то алгоритм Ланцоша, примененный к А, должен завершиться досрочно. Список литературы [1] В.. А8агчча1, Р. Спягачвоп, апс1 М.

ЕпЬа!г, Ехр1о!С!п8 6шсг!опа1 ряга11е!!вш о1 РОчч'ЕВ2 йо дея!хп ЫЯЬ рег1оггпапсе пшпегдса1 а18ог!СЬшя. 1ВМ .7. Веа йеие1ортеп1, 38;563 — 576, 1994. [2) Ь. АЫ1огв. Сотр1ех Апа1уясв. МсСгаъч-Н!11, Хезч г'ог!с, 1966. [3*!] А. АЬо, Л. Норсго1с, апс1 Л. У!1тап. Т!зе Рея!до апй Апа!увсв о/ Сотригет А1дотзс!стз. Адд!яоп-Жев1еу, Неад!п8, МА, 1974. [4) С.

А1еЕе1д апд Л. НегхЬег8ег. 1пстойис1ъоп !о Еп!етиа1 Сотри!а!1опз. Асас1егшс Ргевв, Хесч ''г'ог1с, 1983. [5] Р. Н. АшеяШу апд 1. Б. Пп!1. "чессог!хас!оп о1 а пш1с!ргосеяяог пш1с1- 1гопСа! соде. 1псег.паг1опа1 моитпа! о/ Яиретсотри!ет Арраса!1опв, 3:41— 59, 1989. [6] Р. В.. АшеяФоу. Расгодгагюп о1 !аг8е ппвупппеФг!с ярагве гпасг!сев Ъавед оп а пш!сНгопса1 арргоасЬ ш а шпИргосеяяог епгдгопшеп1. ТесЬшса1 В.ерогй ТН/РА/91/2, СЕВРАСБ, Топ1опяе, г'гапсе, РеЬгпагу 1991. РЬ.В.

сЬея!в. [7) А. Апда апд Н. Раг1с. гввс р1апе госас!опя сч!сЬ с1упаппс вса1!п8. ЯУАМ м'. Ма!т1х Апа1. Арр1., 15:162 — 174, 1994. [8) А. Апда апс1 Н. Раг1с. Яе11 вса1!п8 1аяс госас!опв 1ог яс!К 1еавс яс!пагея ргоЫешя. Езпеат А1деута Арр1., 234:137 — 162, 1996. [9) А. Апс1егяоп, Р. Сп11ег, П. РаИегвоп, апс1 сЬе ХОчч' Теаш. А саяе Гог пегъог!св о1 счог!сяФа1!опв: ХОМИЧ. 1ЕЕЕ М1сто, 15(1):54 — 64, РеЬгпагу 1995. [10] Е. Апс1егяоп, 2. Ви', С. В!ясЬо1, Л. 1)ешше1, 3. Ооп8агга, Л. Пп Сгох, А. СгеепЬашп, Я.

Нашшаг!!п8, А. МсКеппеу, Б. ОяггопсЬоч, апс1 Р. Богепяеп. ЕАРАСК Уветв' Сигйе (2пй ейз!гоп). Я1АМ, РЬВаде1- рЬ!а, РА, 1995. [11) АХЯ1/1ЕЕЕ, Хек Ъог1с. ТЕЕЕ Я1апйатй/от В!пату Р(оа!1пд Рози! Ат!йте!1с, БЫ 754-1985 ед!С!оп, 1985. [12] АХБ1/1ЕЕЕ, Хек УогЬ. 1ЕЕЕ Я!апйатй /от Вайт 1пйерепйеп! Р1оа!!пд Ро1пг Ат!азтеНс, ЯЫ 854-1987 ед!с!оп, 1987. [13] Р. АгЪепх апд С. Со1пЬ.

Оп 1Ье ареопага! десошров!С!оп о1 Негш!С!ап гпасдсев пюд!6ес1 Ъу гочч гап1с регспгЬас!опв сч!ФЬ арр1!сас!опв. Я7АМ м'. Ма!гъх Апа1. Арр1., 9:40 — 58, 1988. [14] М. Агю11, Л. Репнпе1, апс1 1. Б. Пп!1. Бо1ч!п8 врагве 1шеаг вувсешя зч!сЬ ярагве Ьас1сзчагс1 еггог. ЯАМ м'. Ма!т!х Апа1. Арр1., 10:165 — 190, 1989. ~ Работы, помеченные звездочкой имеют русский перевод, ем.

е. 421. — Гсрмм. ред. Список литературы 405 [15] О. Ахе1явоп. ЕСетаС!че Яо1ийоп МеСЬос1з. СаспЪСЫце Рп!чегв!Су Ргеяя, СашЪСЫЯе, 11К, 1994. [16] 2. ВаЬ Еггог апа1уяя оЕ СЬе Ьапсяов а18ог!СЬш Еог СЬе попвупипеСпс е!Яепча1ие ргоЫегп. МаСЬ. Сотр., 62:209 — 226, 1994. [17] с . Ва!. Рго8геяв ш СЬе пшпепса1 яо1иНоп оЕ СЬе попвупипеСпс е!Яепча1ие ргоЫеш. Х Митет. йтаеаг А1деЬга Арр1., 2:219 — 234, 1995. [18) Е. ВаЪ Р. Рау, апс1 О. г'е. АВ1 Е: Ап ас1арС!че Ыос1с Ьапсгоя шеСЬос! Еог поп-Непп!С!ап е!Яепча1ие ргоЪ1ешя МаСЬешаС!ся РерС.

НерогС 95-04, Рп!четв!Су оЕ КепСис1су, Мау 1995. ЯиЬпиССед Со ЯХАМ Х Ма!тих Апа1. Арр1. [19] Е. Вал апс1 С. ССс. ЯСесчагС. ЯНН1Т: А РогСгап виЬгоиСше Со са1си1аСе СЬе с1ош!папС !пчапапС яиЬярасе оЕ а попвупипеСпс шаСпх. СошриСег Яс1- епсе РерС. НерогС ТН 2908, 11пдчегв!Су оЕ Магу1апс1, Арп1 1992. АчЫ1- аЫе ав риЬ/герогСя Еог герогСя апс! риЪ/ягг!С Еог рго8гашя ч!а апопугпоия ЕСр Егосп СЬа1ев.св.шпс1.ес1и. [20) Р. Н.

Ва!1еу. Ми1С1ргес1яоп Сгапв1аС!оп апс1 ехесиС1оп оЕ РогСгап ргоЯгапся. АСМ Тгапз. Ма!!с. Яо/!шаге, 19:288 — 319, 1993. [21] Р. Н. Вы1еу. А РогСгап-90 Ъявес1 ши1С!ргес!в!оп вувСеш. АСМ Тгаиз. Мадс. Яо/С шаге, 21:379 — 387, 1995. [22] Р. Н. ВЫ1еу, К. 1 ее, апс1 Н. Р. Я!шоп. Рв!пд ЯСгаяяеп'я а!8ог!СЬш Со ассе!егаСе СЬе яо1иС1оп оЕ 1!пеаг яувСешя Х Яиретсотристд, 4:97 — 371, 1991. [23] Л. Вагпея апс1 Р. НиС. А ЫегагсЫса1 0(п1о8 и) Еогсе са1си1асюп а18опСЬш.

Ес/а!иге, 324:446-449, 1986. [24] ЕЬ ВаггеСС, М. Весту, Т. СЬап, Л. Репипе1, Л. РопаСо, 3. Ропкагга, с/. Е!]ЫюиС, с'. Рояо, С. Нош!пе, апс! Н. чап с!ег ч'огяС. Тепср!аСез /от 6се Яо1ийоп о/ йсиеат Яузсегаз: ВиЕЫту В!осИз /ог Вета!иве МеСЕсос!з. Я1АМ, РЫ1ас1е1рЫа, РА, 1994. А1яо ача!1аЪ1е е1есСгошса11у аС ЬССр://чсшчс.пеС1!Ъ.огд/Сешр1аСея.

[25] Я. Вассегвоп. Сопчегдепсе оЕ СЬе вЫЕСес! с4Н а18ог!СЬш оп 3 Ьу 3 поппа1 шаСпсев. Ес/итег. МаСЛ., 58:341 — 352, 1990. [26] Р. Ь. Ваиег. Сепаш81сейяЕгадеп Ье! с1ег Ьбяипд 1!пеагег С1е!сЬип8ввуяСеше. Я. Апуеш. МаСЬ. МесЕс., 46:409 — 421, 1966. [27) Т. Вее1еп апс! Р. Чап Роогеп. Ап 1гпргочес1 а!дог!СЬш Еог СЬе согприСаСюп оЕ Кгопес1сег'в сапошса1 Еоггп оЕ а я!пди!аг репс11. йспеат А1уе5та Арр!., 105:9 — 65, 1988. [28] С. В!всЬоЕ. 1псгеспепса1 сопс1!С!оп еяс!шаС!оп. ЯЕАМ .7. Маггсх АааЬ Арр1., 11:312 — 322, 1990. [29] С. В!ясЬоЕ, А.

Саг1е, С. Сог1!вя, А. Сгсесчап1с, апс1 Р. Ноч1апс1. АР1РОВз Сепегас!пд с1ег!чаС!че сосЕея Егош Рогсгап ргоЯгяшя. Ясзеисфс Ргоугаттсид, 1:11 — 29, 1992. ЯоЕСсчаге ача!1аЫе аС ЬССр://шм сч.шея.ап!.аоч/ас!!Еог/. 406 Список литературы [30] С. В!зс1ю1 апс1 С. 1;Ли!псапа-Огс!. Сошрис!п8 гап1с-геъеаИп8 СЛН ГасСог|кайопв о1 с!епве тпасг4сев. Аг8оппе Ргерг4пс АХЬ-МСБ-Р559-0196, Аг8оппе Ха!Попа! ЬаЬогасогу, Аг8оппе, П, 1996. [31] А. В)огс1с.

Яо1игтоп о1 Едиастопз ьп К", чо1шпе 1 оГ НапйЬоо|с о1 Фитпеттса1 Апа1увтв, сЬарСег Ьеззс Бс|иагев МеСЬос!в. Е!зеч!ег/ХогСЬ НоПапс1, Аптзсегс!аш> 1987. [32) А. В|ого|с. 1еазс вс!иагея шеСЬос|в. МаСЬетпаС1св 1ЭерагсшепС Нерогс, РПп1юр1пд 11п!четв!Су, 1991. [33] А. В|бгс1с. Фитеттса! МеС|ьос!з Лот йеавс Яциатез РтиМетпз. 81АМ, РЬ!1ас1е1рЬ!а, РА, 1996. [34) 1. Б. В1асЫогс|, Л.

СЬо|, А. С1еагу, Е. Р'Акечес!о, Л. |Лешше1, 1. ВЫПоп, Л. Роп8ыга, Б. НашшагИп8, С. Непгу, А. РеС!Сес, К. БСап1еу, В. %'аПсег, апс! Н. С. К!тЬа1еу. ЯсайАРАСК Уветз' Ситс|е. Бойтчаге, Епч1гоптпепсв, апс1 Тоо|в 4. 81АМ, РЫ!ас!е1рЫа, РА, 1997. [35] Л. В1ие. А рогСаЫе РОВТВАХ рго8гвхп Со Ппс! СЬе Еис1Ыеап погш оГ а чессог. АСМ 7!апв. Ма1Л. ЯоЛСтвате, 4:15 — 23, 1978. [36) Л. Н.

ВгыпЫе, Л. Е. Рззс1а1с, апс! А. Н. БсЬаСк. ТЬе сопвСгис|Иоп оЕ ргесопс!!С!олега Гог еП!рС1с ргоЪ|ешв Ъу виЬвсгиссиг!пд, 1. Масй. Соптр., 47:103 — 134, 1986. [37] Л. Н. ВгашЫе, Л. Е. Раяс1а|с, апс| А. Н. БсЬаск. Ап !СегаС|че шеСЬос| 1ог е1Ирс!с ргоЫешв оп ге8!опв рагВНопес1 1псо яиЪвСгиссигев. МаСЬ.

Сотар., 46:361 — 369, 1986. [38] Л. Н. ВгашЫе, Л. Е. Равс1а1с, апс1 А. Н. БсЬаск, ТЬе сопзсгисС!оп о1 ргесопс!!С!олега Гог еП!рС!с ргоЫегпв Ъу виЬвсгиссиНп8, П. МаСЬ. Соптр., 49:1-16, 1987. [39] Л, Н. ВгыпЫе, Л. Е. Рззс1а1с, злс1 А.

Н. БсЬаск. ТЬе сопвсгиссюп о1 ргесопс|!С!олега Гог еП1рС1с ргоЫегпв Ъу виЬвсгисСиг!пк, Н1. Масй. Сотар., 51:415-430, 1988. [40) Л. Н. ВгатпЫе, Л. Е. Равс1а1с, апс| А. Н. БсЬаск. ТЬе сопвсгисС!оп о1 ргесопс|!С!опегв 1ог еП!рС!с ргоЫешв Ьу виЪвсгиссиг1п8, ТЧ. Масй. Сотпр., 53:1-24, 1989. [41) К. Вгепап, Б. СыпрЬеП, апс! Ь. РеСко1сЬ Нитпет!са1 Яо1иСтоп оу 1пт2та1- Уа1ие РтоЫетпв тп .Отб'етепСта1-А1де|>тасс Ес|иаСтопз. ХогСЬ НоПалс1, Хек> Ъ'от|с, 1989.

[42) С. Втек!ля|о, М. Ней!чо Еа8Иа, апс! Н. Бас!о|с. Ачо!с!!п8 Ъгеа|сс!омал апс! пеах-Ьгеа!сс!очтп 1п Ьапсков Суре аког!СЬшв. 1>1итпет. А1доттс!ттпв, 1:261-284, 1991. [43] ЪУ. Вг!к8в. А Ми1Г!дтт>1 7ЪСотта1. 8!АМ> Р1п1ас1е1рЫа, РА, 1987. [44] Л. ВипсЬ апс| Ь. Каи6пап. Богпе вСаЪ|е шеСЬос!в 1ог са1си!аНпд 1пегНа апс1 яо!чшд вутшпеСНс 1шеаг вувСептв.