WWW.MASH.DOBROTA.BIZ
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - онлайн публикации
 

«Леонид Книжнерман1 17 марта 2009 г. Отдел математического моделирования Центральной геофизической экспедиции, mmd Соавторы некоторых результатов: Владимир Друскин и Энн ...»

Оценки погрешности методов Ланцоша и Арнольди в

точной и машинной арифметике

Леонид Книжнерман1

17 марта 2009 г .

Отдел математического моделирования Центральной геофизической экспедиции, mmd@cge.ru. Соавторы некоторых результатов:

Владимир Друскин и Энн Гринбаум .

Глава 1

Введение

1.1 Семейство крыловских методов

Подпространство Крылова:

Km (A, ) = span{A0, A1,..., Am1}, (1)

A — матрица размера n n и — n-мерный вектор.

Степенной базис:

(A0, A1,..., Am1). (2) Введение 3

Ортогонализация — средство борьбы с вычислительной неустойчивостью при работе со степенным базисом (2) и средство получения априорных оценок погрешности. Варианты:

1. Ортогонализация по Граму–Шмидту базиса (2). Соответствующие методы в случаях эрмитовой и неэрмитовой матрицы A называются соответственно методами Ланцоша и Арнольди. Наш случай .

2. Все другие случаи. Построение квазиортогонального базиса, биортогональной или квазибиортогональной пары базисов .

Введение 4

1.2 Метод Арнольди Процесс Арнольди в H с A и ( = 1) — процесс ортогонализации по Граму–Шмидту степенного базиса подпространства Крылова K(A, ) = span{A0, A1,...}. (3)

Первые m шагов процесса Арнольди:

AQ = Q H + h m+1,m qm+1em, (4) T Q = (q1,..., qm ) — набор первых m ортонормированных векторов Арнольди, верхняя хессенбергова m m-матрица H = (h i j ) содержит коэффициенты рекурсии .



Если (i, si ) — собственные пары H (i = 1,..., m), то (i, Qsi ) — пары Ритца для A на Km (A, ) = span{A0,..., Am1}, т. е .

AQsi i Qsi Km (A, ), i = 1,..., m. (5) Числа Ритца не обязаны лежать в спектре S оператора A; они находятся в поле значений (множестве значений отношения Рэлея) .

Замыкание поля значений будем обозначать K .

Введение 5 [K91a], [K92a, § 4], [K96, § 2, 3], [K99, § 5] — оценки погрешности метода спектрального разложения Арнольди (МСРА). Если функция f аналитична в окрестности S и окрестности Sp(H ) — спектра H, то МСРА в качестве приближения к u = f (A) (6) выдает вектор u m Q f (H )e1. (7)

МСРА точен для многочленов степени m 1:

f C[t], f (A) = Q f (H )e1, deg f m 1. (8) Если f аналитична на всем компакте K, то ее можно разложить там в ряд Фабера и благодаря (8) свести оценку погрешности МСРА к

–  –  –

1.3 Метод Ланцоша Метод Ланцоша [Lanczos50]: A = A. H — вещественная симметричная трехдиагональная, K — отрезок вещественной оси; ряд Фабера функции f на K — сдвинутый ряд Чебышева. Общая оцен

–  –  –

[DK89]; она позволила оценить ошибку вычисления собственного значения методом Ланцоша в [DK92b, DK91a, K95b] .

Поведению процесса Ланцоша в условиях машинной арифметики посвящены работы К. Пэйджа [Paige71, Page76, Page80], которые, однако, не содержали оценок погрешности метода. Оценка погрешности МСРЛ была дана [DK87c, DK91a]. В [DK87c], [DK91a] был также обоснован так называемый феномен Ланцоша [CullumWilloughby — свойство процесса Ланцоша рано или поздно вырабатывать приближения к собственным значениям. В [K95b] были улучшены результаты, касающиеся феномена Ланцоша .

Введение 7

1.4 Структура

Часть 1. Методы Ланцоша и спектрального разложения Ланцоша в точной арифметике: неадаптивные1 оценки (гл .



2-3) .

Часть 2. Методы Ланцоша и спектрального разложения Ланцоша в машинной арифметике (гл .

4-6) .

Часть 3. Методы Арнольди и спектрального разложения Арнольди: неадаптивные оценки (гл .

7-9) .

Часть 4. Методы Ланцоша, Арнольди, спектрального разложения Ланцоша и спектрального разложения Арнольди: адаптивные оценки (гл .

10-11) .

–  –  –

Сравнивая (8) и (6), видим, что оценка погрешности МСРЛ в два раза превышает оценку погрешности МОРЧ На практике, однако, МСРЛ обычно выигрывает благодаря адаптации к спектру .

МСРЛ в точной арифметике 11

2.4 Приложение к решению задачи Коши для параболического уравнения

–  –  –

s N равно отношению времени t 0 к шагу метода расщепления

0. Для приближенного же решения последней задачи можно применить МСРЛ к функции f () = s (одночлену) .

Двухциклическая схема расщепления [Marchuk88, § 13]: 0 C I .

–  –  –

Метод Ланцоша в точной арифметике

3.1 Введение Аппроксимационные оценки для собственного значения, не зависящие от его номера в спектре (в отличие от оценок Пэйджа и Саада) .

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

–  –  –

Метод спектрального разложения Ланцоша в машинной арифметике

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

Различные способы переортогонализации: [ParlettScott89, Parlett83, Simon84a, Simon84b, Sobyanin85, Sobyanin87]. Опираясь на результаты Пэйджа, мы доказали аналог теоремы 2 для случая простого процесса Ланцоша .

МСРЛ в машинной арифметике 19

4.2 Начальные сведения о простом процессе Ланцоша

–  –  –

Феномен Ланцоша и расположение чисел Ритца

5.1 Введение Попытка объяснить феномен Ланцоша: [CullumWilloughby80]. Мы доказали феномен Ланцоша в двух формулировках, по мере возможности перенося на случай машинной арифметики результаты главы 3. Применение теоремы 9 к шапочкообразной функции, имеющей максимум в нужном собственном значении A и быстро убывающей по мере удаления от него. Усилены некоторые результаты [Greenbaum89] о расположении чисел Ритца .

Феномен Ланцоша и расположение чисел Ритца 22

–  –  –

6.3 Возможные приложения

• Вычисление f (A), : в [KDQK94] величина exp(t A), есть давление на стенке скважины в момент времени t 0; часто встречающаяся в геофизике задача вычисления поля точечного источника в самом источнике .

• Решение некорректных задач с помощью вариационной регуляризации





• Феномен Ланцоша: исправление порядка оценки по r .

Глава 7 Метод спектрального разложения Арнольди: общие оценки

7.1 Введение В данной главе приводятся оценки погрешности МСРА в терминах сходимости ряда Фабера на поле значений K. В докладе мы касаемся только точной арифметики. Так как в методе Арнольди поддерживается ортогональность, то рассмотрение для машинной арифметики здесь несоизмеримо проще, чем в теории метода Ланцоша .

–  –  –

ЗАМЕЧАНИЕ. Недавний результат Б. Бекерманна позволяет удалить степенной множитель .

Глава 8

Оценки погрешности метода Арнольди:

случай нормальной матрицы

8.1 Введение Изучается сходимость в методе Арнольди крайних собственных значений и соответствующих собственных векторов, а также исследуется МСРА при ослабленном ограничении на функцию f : ей разрешается иметь особенности между крайними собственными значениями A. Дискретность части спектра A, не относимой к краю, несущественна .

В этой главе — случай нормальной матрицы A .

Метод Арнольди: случай нормальной матрицы 32

8.2 Аппроксимация крайних собственных пар нормальной матрицы s собственных значений 1,..., s не принадлежат выпуклой оболочке K остальных собственных значений s+1,..., n. Обозначения и т. п. будут относиться к этому новому K. ti = (i ), i R и i 0 .

Положим i = |ti |m m c1, где константа c1 1 зависит от формы K, и i = i /i .

–  –  –

ЗАМЕЧАНИЕ. Теорема 15 является аналогом для нормальных операторов теорем Каниэля и Саада .

ЗАМЕЧАНИЕ. Приложение: сходимость корней многочленов, ортогональных на единичной окружности, к изолированным точкам носителя меры. Теорема из книги Б. Саймона .

–  –  –

из [DK89]. Родственна [SluisVorst87] .

Глава 9

Оценки погрешности метода Арнольди:

случай крайних изолированных собственных значений

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

–  –  –

9.3 Вычисление матричной функции Теорема 18 Пусть функция f аналитична внутри некоторого контура R (R 1) и окрестностей точек 1,..., s. Тогда метод Арнольди, примененный к A и, за достаточное большое число шагов m выработает корректно определенную аппроксиманту u m к

–  –  –

ЗАМЕЧАНИЕ. Обе теоремы данной главы обобщают более ранние результаты для нормального случая в той степени, в какой этой возможно в данной ситуации (теорема о невязке, учитывающая отделенность, в ненормальном случае неприменима, вот почему собственные значения, вообще говоря, не сходятся быстрее соответствующих собственных векторов) .

Глава 10 Об адаптации методов Ланцоша и Арнольди к спектру, или почему два этих метода так мощны

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

Спектр оператора является его релевантной характеристикой (в отличие от спектра ненормальной матрицы) .

Адаптация методов Ланцоша и Арнольди к спектру 40

10.2 Решение систем линейных уравнений — общий случай

–  –  –

log |z| log capl E + o(1) при z ; 3) предельные значения g на границе D множества D неотрицательны .

Вычисляем A1 посредством МСРА. Обозначим соответственно через rm и rm невязки МСРА and GMRES на m-ом шаге .

A G

–  –  –

ЗАМЕЧАНИЕ. Адаптивный характер (2) следует из монотонности функции Грина. Если E = K, то g(0) g K (0), что и выражает преимущество (2) над неадаптивной оценкой .

ЗАМЕЧАНИЕ. К использованию множества E вынуждают формулировки из теории потенциала. Смысл использования E таков:

теорема о максимуме модуля не оставляет надежды выделить 0 с помощью многочлена, умеренного на S, если S отделяет 0 от бесконечности .

ЗАМЕЧАНИЕ. Последовательность значений m, реализующих нижний предел в (2), может быть произвольно редкой .

Адаптация методов Ланцоша и Арнольди к спектру 42

–  –  –

ЗАМЕЧАНИЕ. В отличие от (2) оценка (3) гарантирует хорошее поведение FOM для последовательности значений m, имеющей положительную нижнюю натуральную плотность ( 0.5) .

Адаптация методов Ланцоша и Арнольди к спектру 43

10.4 Оценка погрешности МСРЛ/МСРА

Критический уровень функции Грина :

–  –  –

ЗАМЕЧАНИЕ. Если E = K, то (5) экспоненциально сильнее, чем неадаптивная (в терминах K ) оценка .

ЗАМЕЧАНИЕ. Адаптация МСРЛ при вычислении матричной экспоненты рассмотрена в [DGK97] .

Адаптация методов Ланцоша и Арнольди к спектру 44

10.5 Вычисление собственной пары — общий случай Изолированное собственное значения 0. Пусть = A, G — замыкание линейного подпространства span, A, A2,.... Ограничение B = A|G G G. Здесь будем связывать спектр S, множество E и функцию g с оператором B (не A). Предположим, что 0 E .

Теорема 22 Метод Арнольди, примененный к оператору A и вектору, на m-ом шаге выработает приближенную собственную пару

–  –  –

меняет обобщенных изолиний [94, § 4.9] функции Грина. Поэтому здесь нет необходимости совместно рассматривать несколько собственных значений .

ЗАМЕЧАНИЕ. Нижние пределы в (6) предоставляются одной (возможно, редкой) последовательностью значений m .

Адаптация методов Ланцоша и Арнольди к спектру 45

–  –  –

Квадратура Гаусса–Арнольди для функции (z I A)1, и Паде-подобная рациональная аппроксимация функций марковского типа

11.1 Введение Квадратурa Гаусса–Арнольди (частный случай): f (z) f m (z), где

–  –  –

Оценку погрешности квадратуры Гаусса–Арнольди в терминах спектра дать нельзя. Эрмитов оператор B и подобный ему с помощью непрерывно обратимого оператор A; Sp A = Sp B = [ 1, 1] .

Квадратура Гаусса–Арнольди 49

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

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

Литература [1] Абрамовиц М., Стиган И. М. (ред.), Справочник по специальным функциям, М., Наука, 1979 .

[2] Бабенко К. И., Основы численного анализа, М., Наука, 1986 .

[3], Бахвалов Н. С., Жидков Н. П., Кобельков Г. М., Численные методы, М., Лаборатория Базовых Знаний, 2002 .

[4] Бейтмен Г., Эрдейи А., Высшие трансцендентные функции, М., Наука, l974, т. 2 .

[5] Воеводин В. В. Ошибки округления и устойчивость в прямых методах линейной алгебры. М.: Изд-во МГУ, 1969 .

Квадратура Гаусса–Арнольди 51

[6] Воеводин В. В., Кузнецов Ю. А., Матрицы и вычисления, М., Наука, 1984 .

[7] Гантмахер Ф. Р. Теория матриц. М.: Наука, 1988 .

[8] Годунов С. К., Рябенький В. С., Разностные схемы, М., Наука, 1973 .

[9] А. А. Гончар. “О сходимости аппроксимаций Паде для некоторых классов мероморфных функций”. Матем. сб., 97(139):607–629, 1975 .

[10] А. А. Гончар, С. П. Суетин. Об аппроксимациях Паде мероморфных функций марковского типа. Современные проблемы математики, (5), 2004 .

[11] Демидович Б. П., Марон И. А. Основы вычислительной математики. М.: Наука, 1970 .

[12] Дзядык В. К. Введение в теорию равномерного приближения функций полиномами. М.: Наука, 1977 .

Квадратура Гаусса–Арнольди 52 [13] Друскин В. Л., Книжнерман Л. А., Спектральный дифференциально-разностный метод численного решения трехмерных нестационарных задач злектроразведки, Изв .

АН СССР, Физ. Земли, 1988, № 8, c. 63–74 .

[DK87c] Друскин В. Л., Книжнерман Л. А., Использование операторных рядов по ортогональным многочленам при вычислении функций от самосопряженных операторов и обоснование феномена Ланцоша, Деп. в ВИНИТИ 02.03.1987, № 1535-В87, 47 с .

[DK89] Друскин В. Л., Книжнерман Л. А. Два полиномиальных метода вычисления функций от симметричных матриц// Ж. вычисл. матем. и матем. физ. 1989. Т. 29. № 12. C. 1763–1775 .

[DK91a] Друскин В. Л., Книжнерман Л. А. Оценки ошибок в простом процессе Ланцоша при вычислении функций от симметричных матриц и собственных значений// Ж. вычисл. матем .

и матем. физ. 1991. Т. 31. № 7. С. 970–983 .

Квадратура Гаусса–Арнольди 53 [14] Икрамов Х. Д., Разреженные матрицы, Итоги науки и техн., Матем. анализ, М., ВИНИТИ, 1982, т. 20, с. 179–260 .

[15] Х. Д. Икрамов. Несимметричная проблема собственных значений. Наука, М., 1991 .

[K91a] Книжнерман Л. А. Вычисление функций от несимметричных матриц с помощью метода Арнольди// Ж. вычисл. матем .

и матем. физ. 1991. Т. 31. N 1. С. 5–16 .

[K92a] Книжнерман Л. А. Оценки погрешности метода Арнольди:

случай нормальной матрицы // Ж. вычисл. матем. и матем. физ .

1992. Т. 32. N 9. С. 1347–1360 .

[K95b] Книжнерман Л. А. Качество аппроксимаций к хорошо отделенному собственному значению и расположение чисел Ритца в простом процессе Ланцоша// Ж. вычисл. матем. и матем. физ. 1995. Т. 35. N 10. С. 1459–1475 .

Квадратура Гаусса–Арнольди 54 [K96b] Книжнерман Л. А. Простой процесс Ланцоша: оценки погрешности гауссовой квадратурной формулы и их приложения// Ж. вычисл. матем. и матем. физ. 1996. Т. 36. N 11. С. 5–19 .

[K07] Книжнерман Л. А., Квадратура Гаусса–Арнольди для (z I A)1, и Паде-подобная рациональная аппроксимация функций марковского типа, Матем. сборник, ?

[K08a] Книжнерман Л. А. Квадратура Гаусса-ЏАрнольди для функции (z I A)1, и Паде-подобная рациональная аппроксимация функций марковского типа // Матем. сб. 2008. Т. 199 .

№ 2. С. 27–48 .

[16] Х.Д. Икрамов, Несимметричная проблема собственных значений, Неука, М., 1991 .

[17] Крейн С. Г. О классах корректности для некоторых граничных задач// Докл. АН СССР. 1957. Т. 114. N 6. С. 1162–1165 .

[18] Ланкастер П. Теория матриц. М.: Наука, 1978 .

Квадратура Гаусса–Арнольди 55 [19] Лебедев В. И. Об итерационных методах решения операторных уравнений со спектром, лежащим на нескольких отрезках// Ж. вычисл. матем. и матем. физ. 1969. Т. 9. № 6. С. 1247– 1252 .

[20] Лебедев В. И. Явные разностные схемы с переменными шагами по времени для решения жестких систем уравнений, М., Отдел вычисл. матем. АН СССР, 1987, препринт № 177, 39 с .

[21] С. Ленг. Алгебра. Мир, М., 1968 .

[22] Локуциевский В. О., Локуциевский О. В., Применение чебышевских параметров для численного решения некоторых зволюционных задач, М., Ин-т прикл. матем. АН СССР, 1984, препринт № 99б, 30 с .

[23] Марчук Г. И., Методы вычислительной математики, М., Наука, 1980 .

[Marchuk88] Марчук Г. И., Методы расщепления, М., Наука, 1988 .

Квадратура Гаусса–Арнольди 56 [24] Марчук Г. И., Агошков В. И., Введение в проекционноразностные схемы, М., Наука, 1981 .

[25] Никишин Е. М., Сорокин В. М., Рациональные аппроксимации и ортогональность, М., Наука, 1988ю [Parlett83] Парлетт Б., Симметричная проблема собственных значений, М., Мир, 1983 .

[26] Пашковский С., Вычислительные применения многочленов и рядов Чебышева, М., Наука, 1983 .

[27] У. Рудин, Функциональный анализ, Мир, М„ 1975 .

[28] Рябенький В. С., Введение в вычислительную математику, М., Наука, 1994 .

[29] Е. А. Рахманов. “Об асимптотике отношения ортогональных многочленов”. Матем. сб., 103(145):607–629, 1977 .

[30] Е. А. Рахманов. “Об асимптотике отношения ортогональных многочленов. II”. Матем. сб., 118(160):104–117, 1982 .

Квадратура Гаусса–Арнольди 57 [31] Е. А. Рахманов. “О сходимости диагональных аппроксимаций Паде”. Матем. сб., 104(146):271–291, 1977 .

[32] Самарский А. А. Теория разностных схем, М., Наука, 1977 .

[Sobyanin85] Собянин А. В. Анализ ошибок округления и устойчивость в методах типа Ланцоша: Препринт № 87. М.: ОВМ АН СССР, 1985. 15 с .

[Sobyanin87] Собянин А. В. Решение проблемы собственных значений для симметричных матриц большого порядка // Вычисл .

процессы и системы. М., 1987. № 5. С. 174–179 .

[33] Суетин П. К., Классические ортогональные многочлены, М., Наука, 1979 .

[Suetin84] Суетин П. К. Ряды по многочленам Фабера. М.: Наука, 1984 .

[34] С. П. Суетин. “Аппроксимации Паде и эффективное аналитическое продолжение степенных рядов”. УМН, 57:1:45–142, 2002 .

Квадратура Гаусса–Арнольди 58 [35] С. П. Суетин. “О равномерной сходимости диагональных аппроксимаций Паде для гиперэллиптических функций”. Матем. сб., 191(9):81–114, 2000 .

[36] С. П. Суетин. “Сходимость чебышевских непрерывных дробей для эллиптических функций”. Матем. сб., 194(12):63–92, 2003 .

[37] Тихонов А. Н., Арсенин В. Я. Методы решения некорректных задач. М.: Наука, 1979 .

[38] В.А.Треногин, Фунуциональный анализ, Наука, М„ 1980 .

[39] Уилкинсон Дж. Х., Райнш К. Справочник алгоритмов на языке Алгол. М.: Машиностроение, 1976 .

[40] Фаддеев Д. К., Фаддеева В. Н., Вычислительные методы линейной алгебры, СПб, Лань, 2002 .

[41] Хорн Р., Джонсон Ч. Матричный анализ. М.: Мир, 1989 .

[42] N.I.Akhiezer, I.M.Glazman, Theory of linear operators in Hilbert space, Dover, N.Y., 1993 .

Квадратура Гаусса–Арнольди 59 [43] A. Ambroladze. “On exceptional sets of asymptotic relations for general orthogonal polynomials”. J. of Approximation Theory, 82:257–273, 1995 .

[44] A. Ambroladze, H. Wallin. “Convergence rates of Pade and Padetype approximants”. J. of Approximation Theory, 86:310–319, 1996 .

[45] Arnoldi W. Е. The principle of minimized iterations in the solution of the matrix eigenvalue problem // Quart. Аррl. Math. 1951. V. 9 .

№ 1. Р. 17–29 .

[46] D. N. Bailey. “A Fortran-90 based multiprecision system” .

Technical report, RNR Technical Report RNR-94-013, June 6, 1994 .

[47] Brown P. A theoretical comparison of the Arnoldi and GMRES algorithms // SIAM J. Sci. Stat. Comp. 1991. V. 20. P. 58–78 .

[48] P.N.Brown, Y.Saad, Hybrid Krylov methods for nonlinear systems of equations, SIAM J. Sci. Statist. Comput. 11: 450–481 (1990) .

Квадратура Гаусса–Арнольди 60 [CalvettiKimReichel05] D. Calvetti, S.-M. Kim, L. Reichel .

“Quadrature rules based on Arnoldi process”. SIAM J. Matrix Anal. Appl., 26:765–781, 2005 .

[49] Concus P., Golub G. H., O‘Leary D. P., A generalized conjugate gradient method for numerical solution of elliptic partial differential equations, in: J. R. Bunch and D. J. Rose, Eds., Sparse Matrix Computations, New York, Academic Press, 1976 .

[50] J.Cullum, A.Greenbaum, Residual relationships within three pairs of iterative algorithms for solving Ax = b, SIAM J. Matrix Anal .

Appl. 17: 223–247 (1996) .

[CullumWilloughby80] Cullum J., Willoughby R. А. The Lanczos phenomenon — an interpretation based upon conjugate gradient optimization// Linear Algebra and Applic. 1980. V. 29. Р. 63-90 .

[51] Daniel J. W., Gragg W. В., Kaufman L., Stewart G. W .

Reorthogonalization and stable algorithms for updating the GramSchmidt QR factorization // Math. Comput. 1976. V. 30. Р. 772–795 .

Квадратура Гаусса–Арнольди 61 [52] T.A.Driscoll, K.-C.Toh, L.N.Trefethen, From potential theory to matrix iterations in six steps, SIAM Review, 40 (1998) 547–578 .

[DGK97] Druskin V., Greenbaum A., Knizhnerman L. Using nonorthogonal Lanczos vectors in the computation of matrix functions // SIAM J. Sci. Comp. 1998. V. 19. P. 38–54 .

[DK92a] Druskin V., Knizhnerman L., The Lanczos optimization of a splitting-up method to solve homogeneous evolutionary equations, J. Comput. Appl. Math., 1992, v. 42, pp. 221-231 .

[DK92b] Druskin V., Knizhnerman L. Evaluation for Krylov subspace approximation to internal eigenvalues of large symmetric matrices and bounded self-adjoint operators with continuous spectrum: Res .

note. Ridgefield: Schlumberger-Doll Res., Sept. 2, 1992. 20 p .

[53] Druskin V., Knizhnerman L., ?, North Carolina ?

[DK95b] Druskin V., Knizhnerman L. Krylov subspace approximation of eigenpairs and matrix functions in exact and computer Квадратура Гаусса–Арнольди 62 arithmetic, Numer. Linear Algebra with Appl., 1995, v. 2, № 3, pp .

205–217 .

[54] Elman Н. С., Saad Y., Saylor Р. Е. А hybrid Chebyshev Krylov subspace a1gorithm for solving nonsymmetric systems of linear equations// SIAM J. Sci. and Statist. Comput. 1986. V. 7. № 3. Р .

840–855 .

[FreundHochbruck93] R. W. Freund, M. Hochbruck. Applications and Computation of Orthogonal Polynomials, W. Gautschi, ed., chapter “Application of anti-Gauss quadrature rules in linear algebra”, pages 377–380. Kluwer, Dordrecht, The Netherlands, 1993 .

[55] D. Gaier. Lectures on complex approximation. Birkhauser–Verlag, Basel, 1980 .

[56] E.Gallopulos, Y.Saad, Efficient solution of parabolic equations by

Krylov approximation method, SIAM J. Sci. Statist. Comput. 13:

1236–1264 (1992) .

Квадратура Гаусса–Арнольди 63 [57] Gear С. W., Saad Y. Iterative solution of linear equations in ODE codes // SIАМ J. Sci. and Statist. Comput. 1983. V. 4. № 4. Р. 583– 601 .

[58] G. H. Golub, Ch. Van Loan. Matrix Computations. The John Hopkins Univ. Press, Baltimore and London, 1989 .



[59] Golub G. H., Meurant G. Matrices, moments and quadrature:

Manuscript SCCM-93-07. Sept. 30. Stanford: Stanford Univ., 1993 .

[60] Golub G. H., Strakos Z. Estimates in quadratic formulas:

Manuscript SCCM-93-08. Sept. 27. Stanford: Stanford Univ., 1993 .

[Greenbaum89] Greenbaum A. Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences// Linear Algebra and Applic .

1989. V. 113. P. 7–63 .

[Greenbaum97] A. Greenbaum, Iterative methods for solving linear systems, SIAM, Philadelphia, 1997 .

[DGK99] Greenbaum A., Druskin V. L., Knizhnerman L. A. On solving indefinite symmetric linear systems by means of the Lanczos Квадратура Гаусса–Арнольди 64 method. Ж. вычисл. матем. и матем. физ. 1999. Т. 39. № 3. C .

371–377 .

[61] Hanke M. Superlinear convergence rates for the Lanczos method applied to elliptic operators. // Numer. Math. 1997. V. 77. P. 487– 499 .

[62] M. He. “The Faber polynomials for circular arcs”. Proceedings of Symposia in Applied Mathematics, 48:301–304, 1994 .

[Higham08] Higham N. J. Functions of matrices. Theory and computation. Philadelphia: SIAM, 2008 .

[63] D.Ho, F.Chatelin, M.Bennami, Arnoldi — Tchebychev procedure for large scale nonsymmetric matrices, Math. Mod. and Numer .

Anal. 24: 53–65 (1990) .

[64] M.Hochbruck, C.Lubich, On Krylov subspace approximations to the matrix exponential operator, SIAM J. Numer. Anal. 34 (1997) 1911–1925 .

Квадратура Гаусса–Арнольди 65 [65] Hochbruck M., Lubich C. Exponential integrators for quantumclassical molecular dynamics // BIT. 1999. V. 39. P. 620–645 .

[66] M. Hochbruck, C. Lubich, H. Selhofer. “Exponential integrators for large systems of differential equations”. SIAM J. Sci. Comp., 19:1552–1574, 1998 .

[67] R.A.Horn, Ch.R.Johnson, Topics in matrix analysis, Cambridge Univ. Press, Cambridge, London, N.Y., New Rochelle, 1991 .

[68] Householder А. S. The theory of matrices in numerical analysis. N .

Y.: Blaisdell ? Рubl. Со., 1964 .

[69] Kaniel S., Estimates for some computational techniques in linear algebra, Math. Comp., 1966, v. 20, p. 369–378 .

[KDQK94] Knizhnerman L., Druskin V., Quing-Huo Liu, Kuchuk F.J .

Spectral Lanczos decomposition method for solving single-phase fluid flow in porous media// Numer. Methods for Partial Different .

Equations. 1994. N 10. P. 569–580 .

Квадратура Гаусса–Арнольди 66 [K95] L. Knizhnerman. “On adaptation of the Lanczos method to the spectrum”. Technical report, Schlumberger-Doll Research, Res .

Note # EMG-001-95-12, May 12, 1995 .

[K96] L. Knizhnerman. “On adaptation of the Arnoldi method to the spectrum”. Technical report, Schlumberger-Doll Research, Report #EMG-001-96-03, February 12, 1996 .

[K97] L. Knizhnerman, On adaptation of the Lanczos and Arnoldi methods to the spectrum, Mylovy, 1997?

[K99] L. Knizhnerman. “Error bounds for the Arnoldi method: a set of extreme eigenpairs”. Linear Algebra and Appl., 296:191–211, 1999 .

[K02] L. Knizhnerman. “Adaptation of the Lanczos and Arnoldi methods to the spectrum, or why the two Krylov subspace methods are powerful”. Чебышевский сборник, 3(2):141–164, 2002 .

Квадратура Гаусса–Арнольди 67 [K06] L. Knizhnerman, The quality of the Gauss–Arnoldi quadrature for (z I A)1, and application to Pade-like approximation, SIAM-GAMM-2006 ?

[70] П. Ланкастер. Теория матриц. Наука, М., 1978 .

[Lanczos50] Lanczos С. An iteration method for the solution of the eigenvalue problem of linear differential and integral operators// J. Res. Nat. Bur. Standards. 1950. Sect. В. V. 45. Р. 225–280 .

[Markov] A. A. Markov. “Deux demonstrations de la convergence de certain fractions continue”. Acta Math., 19:93–104, 1895 .

[Meurent06] G. Meurant, The Lanczos and Congugate Gradient algorithms: From theory to finite precision computations, SIAM, Philadelphia, 2006 .

[71] Mоlег С., Van Loan С., Nineteen dubious ways to compute the exponential of а matrix, SIAM Rev., 1978, v. 20, № 4, p. 801–836 .

Квадратура Гаусса–Арнольди 68 [72] Navarra А. An application of the Arnoldi’s method to а geophysical fluid dynamics problem // J. Comput. Phys. 1987. V. 69. № 1. Р .

143–162 .

[73] O.Nevanlinna, Convergence of iterations for linear equations (lectures in mathematics Eth Zurich), Birkhauser, 1993 .

[74] Nour-Omid В., Clough R. W., Dynamic analysis of structure using Lanczos со-ordinates, Earthquake Engng and Structure Dynamics, 1984., v. 12, № 4, p. 565–577 .

[75] Nour-Omid В., Lanczos method for heat conduction analysis, Internat. J. Numer. Meth. Engng., 1987, v. 24, № 1, p. 251–262 .

[Paige71] Paige С. С. The computation of eigenvalues and eigenvectors of very large sparse matrices: Ph. D. Thesis. London: Univ. of London, 1971 .

[Page76] Paige С. С. Error analysis of the Lanczos algorithm for tridiagonalizing of а symmetric matrix // J. Inst. Math. Аррliс. 1976 .

V. 18. No. 3. Р. 341–349 .

Квадратура Гаусса–Арнольди 69 [Page80] Paige С. С. Accuracy and effectiveness of the Lanczos algorithm for the symmetric eigenproblem // Linear Algebra and Applic. 1980. V. 34. Р. 235–258 .

[76] Paige C. C., Parlett B. N., van der Vorst H. A. Approximate solution and eigenvalue bounds from Krylov subspaces // Center for Pure and Applied Mathematics, Univ. of California, Berkeley. Report PAM-579. February 23, 1993 .

[77] Paige С. С., Sonders М. А., Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Analys., 1975, v. 12, № 4, p. 617–629 .

[ParlettScott89] Parlett В. N., Scott D. S. The I.anczos algorithm with selective orthogonalization// Math. Comput. 1979. V. 33. No. 145 .

Р. 217–238 .

[Parlett80] Parlett В. N., А new look at the Lanczos algorithm for solving symmetric systems of linear equations, Linеаr Algebra and Applic., 1980, v. 29, p. 323–346 .

Квадратура Гаусса–Арнольди 70 [Parlett98] Parlett B. N. The symmetric eigenvalue problem .

Philadelphia: SIAM, 1998 .

[78] У. Рудин. Функциональный анализ. Мир, М., 1975 .

[79] Remis R. F., van der Berg P. M. A modified Lanczos algorithm for the computation of transient electromagnetic wavefields// IEEE Trans. on Microwave Theory and Techniques. V. 45. No. 12. P .

2139–2149 .

[80] Ruhe A. The two-sided Arnoldi algorithm for unsymmetric eigenvalue problems // Lect. Notes in Math. 1982. V. 973. P. 104– 120 .

[81] Saad Y., On the rates of convergence of the Lanczos and the blockLanczos methods, SIAM J. Numer. Anal., 1980, v. 17, p. 687–706 .

[82] Saad Y. Variations on Arnoldi’s method for computing eigenelements of large unsymmetric matrices // Liпеаг Algebra and Appl. 1980. V. 34. Р. 269–295 .

Квадратура Гаусса–Арнольди 71 [83] Saad Y. Krylov subspace method for solving large unsymmetric linear systems// Math. Comput. 1981. V. 37. № 155. Р. 105–126 .

[84] Yu. Saad, Iterative methods for sperse linear systems, SIAM, Philadelphia, 2003 .

[85] Y.Saad, Analysis of some Krylov subspace approximation to the matrix exponential operator, SIAM J. Numer. Anal. 29: 209–228 (1992) .

[86] Y.Saad, M.H.Schultz, GMRES: a generalized minimum residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci .

Stat. Comput. 7: 856–869 (1986) .

[87] H. S. Shapiro. The Schwarz function and its generalization to higher dimensions. University of Arkansas lecture notes in the mathematical sciences, A Wiley-interscience publication, John Wiley & Suns, Inc., 1992 .

Квадратура Гаусса–Арнольди 72 [Simon84a] Simon Н. D. The Lanczos algorithm with partial reorthogonalization// Math. Comput. 1984. V. 42. No. 165. Р .

115–142 .

[Simon84b] Simon Н. D. Analysis of the symmetric Lanczos algorithm with reorthogonalization methods // Linear Algebra and Applic .

1984. V. 61. Р. 101–131 .

[88] Simon Н. D., The Lanczos algorithm for solving linear systems, Ph .

D. Thesis, Berkeley, Univ. California, 1982 .

[SluisVorst87] Van der Sluis A., van der Vorst H. A. The convergence behavior of Ritz values in the presence of close eigenvalues// Linear Algebra Appl. 1987. V. 88–89. P. 651–694 .

[StahlTotik92] H. Stahl, V. Totik. General Orthogonal Polynomials .

In: “Encyclopedia of Math.”, Cambridge Univ. Press, Cambridge, 1992 .

[89] G.W.Stewart, J.Sun, Matrix perturbation theory, Academic Press, Boston et al., 1990 .

Квадратура Гаусса–Арнольди 73 [90] H. Tal-Ezer, Spectral methods in time for hyperbolic equations, SIAM J. Numer. Anal., 1986, v. 23, № 1, pp. 11–26 .

[91] H. Tal-Ezer, Spectral methods in time for parabolic problems, SIAM J. Numer. Anal., 1989, v. 26, № 1, pp. 1–11 .

[Trefethen05] Trefethen L. N., Embree M. Spectra and pseudospectra:

the behavior of nonnormal matrices and operators. Princeton:

Princeton Univ. Press, 2005 .

[92] Van der Vorst Н. А., An iterative solution method for solving f (A)x = b using Krylov subspace information obtained for the symmetric positive definite matrix, J. Comput. Appl. Math., 1987, v. 18, № 2, p. 249–263 .

[93] Van der Vorst Н. А., Iterative Krylov methods for large linear systems, Cambridge Univ. Press, 2003, Cambridge, UK .

[94] J.L.Walsh, Interpolation and approximation by rational functions in the complex domain, AMS, Colloquium Publications, v. 20, Providence, R.I., 1969 .

Квадратура Гаусса–Арнольди 74 [95] Wilkinson G. Н. Rounding errors in algebraic process. N.

Y.:

Prentice-Hall, 1964 .






Похожие работы:

«Список литературы: 1.Свами М. Графы, сети и алгоритмы / М. Свами, К. Тхуласираман. – М.: Мир, 1984.– 455с. 2. Зайцев Д.А. Синтез моделей Петри телекоммуникационных протоколов / Д.А.Зайцев // Наукові праці ОНАЗ ім. О.С.Попова. – 2005. – №2. – С.36-42. 3.Клейнрок Л. Вычислительные системы с очередями / Клейнрок Л. – М.: Мир, 1979. –600 с. 4.Фрактальны...»

«МЕЖДУНАРОДНАЯ АКАДЕМИЯ ИНФОРМАТИЗАЦИИ (МАИ) РОССИЙСКАЯ АКАДЕМИЯ ЕСТЕСТВЕННЫХ НАУК (РАЕН) АКАДЕМИЯ ИНФОРМАЦИОЛОГИЧЕСКОЙ И ПРИКЛАДНОЙ УФОЛОГИИ (АИПУФО) МЕЖДУНАРОДНАЯ УФОЛОГИЧЕСКАЯ АССОЦИАЦИЯ (МУА) ИНСТИТУТ ПОСЛЕКОНТАКТНОЙ РЕАБИЛИТАЦИИ (ИПР) при информационной поддержке журнала "Философские науки", газет "Аргументы и факты" и "Ан...»

«Конференция "Ломоносов-2012", секция "Вычислительная математика и кибернетика" Подсекция "Компьютерная графика" Вторник, 10 апреля, 10:30-14:10, ауд. 523 Руководитель: Конушин Антон Сергеевич 1 Алехин Владимир Юрьевич Белгородский государственный Создание автоматизированных систем на основе технологии технологический ун-т им. В.Г. Шухов...»

«Российская Академия наук Центральный дом учёных 15.03.2017 НАУЧНЫЕ ОСНОВЫ ПРОГРАММ И ТЕХНОЛОГИИ ПРОГРАММИРОВАНИЯ СИСТЕМ Доклад доктора физ.мат . наук, проф. МФТИ, гнс ИСП РАН Лаврищевой Е.М. НАУЧНЫЕ ОСНОВЫ ПРОГРАММ И ТЕХНОЛОГИЙ: 1. ТЕОРИЯ ПРОГРАММ ДЛЯ ПЕРВЫХ ЭВМ 2. ТЕОРИЯ ТЕХНОЛОГИИ ПРОГРАММИРОВАНИЯ 3. ТЕОРИЯ ОБЪЕКТНО-КОМПОНЕНТНО...»

«НИИАР П-238 Научно-исследовательский институт атомных реакторов им. В. И.Ленина В.Л.Лебедев. Ю.Д.Фёдоров БУФЕРНАЯ РЕГИСТРИРУЮЩАЯ УСТАНОВКА НА ВХОДЕ УНИВЕРСАЛЬНОЙ ЦВМ Димитровград • 1974 Н И М Р П-238 В.Л.Лебедей, Ю.Д. Федор...»

«АКСИОМАТИЧЕСКАЯ МОДЕЛЬ ПРИЧИННО-СЛЕДСТВЕННЫХ СВЯЗЕЙ Белкин А.Э.1, Бирюков Д.Р.2 Email: Belkin645@scientifictext.ru 1Белкин Антон Эдуардович – бакалавр физико-математических наук; 2Бирюков Данила Русланович – бакалавр физико-математических наук, кафедра прикладной математики и информатики, Т...»

«37 ГЛАВА Развертывание и использование виртуализации Windows В ЭТОЙ ГЛАВЕ. • Стратегия виртуализации Microsoft • Интеграция технологии Hypervisor в среде Windows Server 2008 • Планирование внедрения технологии Hyper-V • Установка роли Microsoft Hype...»




 
2019 www.mash.dobrota.biz - «Бесплатная электронная библиотека - онлайн публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.