Эта страница переведена с помощью средств машинного перевода. Смотреть оригинал

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

Авторы
ИзданиеarXiv.org.
Год издания2010

 Мы рассматриваем численную устойчивость некоторых быстрых алгоритмов для решения систем линейных уравнений и линейных задач наименьших квадратов с малой структурой ранга смещения. Например, матрицами могут быть теплиц или ганкель. Рассматриваются алгоритмы, которые включают в себя поворот без разрушения структуры и описывают некоторые недавние результаты по устойчивости этих алгоритмов. Мы также сравниваем эти результаты с соответствующими результатами устойчивости для хорошо известных алгоритмов Шура / Барейса и Левинсона, а также для алгоритмов, основанных на полунормальных уравнениях.

 13 страниц. Старый технический отчет (CSL, ANU, сентябрь 1997 г., 13 стр.), Представленный для архивных целей. Для получения дополнительной информации см. Http: // wwwmaths.Ану.Edu.Au / ~ brent / pub / pub177.Html Опубликовано: «Быстрые надежные алгоритмы для матриц со структурой» (под ред. Али Сайеда и Томаса Кайлата), SIAM, Philadelphia, 1999, 103-116

Ссылка на публикацию
Брент Р. П.  Устойчивость быстрых алгоритмов для структурированных линейных систем. - : , 2010. // arXiv.org, 2010.
Библиография
1.Г. S. Аммар и У. B. Грэгг, Супербыстрое решение вещественных положительно определенных теплицевых систем, СИАМ Дж. Матричный анал. Appl. 9 (1988), 61--76.
2.E. ЧАС. Барейс, Численное решение линейных уравнений с тёплицевой и векторной теплицевыми матрицами, Числ. Математика. 13 (1969), 404-424.
3.? A. Bj? Orck, Анализ устойчивости метода полунормальных уравнений для линейных задач наименьших квадратов, Linear Alg. Appl. 88/89 (1987), 31-48.
4., Анализ ошибок алгоритмов наименьших квадратов, Численная линейная алгебра, Цифровая обработка сигналов и Параллельные алгоритмы (под редакцией Г. ЧАС. Голуб и П. Van Dooren), Springer-Verlag, 1991, 41--73.
5.A. W. Bojanczyk, R. П. Brent, P. Ван Дорден и Ф. Р. Де Хоог, Заметка о сокращении факторизации Холецкого, SIAM J. Sci. Stat. Вычисл. 8 (1987), 210-220.
6.A. W. Bojanczyk, R. П. Брент и Ф. Р. Де Хоог, QR-факторизация тёплицевых матриц, Числитель. Математика. 49 (1986), 81--94.
7., Анализ устойчивости общего решателя систем Теплица, Численные алгоритмы 10 (1995), 225-244.
8.A. W. Bojanczyk, R. П. Брент, Ф. Р. Де Хоог и Д. Р. Слайт, Об устойчивости алгоритмов фатеризации Терица и Барейса, SIAM J. Матричный анал. Appl. 16 (1995), 40--57.
9.A. W. Боянчик и А. O. Steinhardt, Анализ стабильности алгоритма Хозяин, основанный на снижении факторизации Холецкого, SIAM J. Sci. Статистик. Вычисл. 12 (1991), 1255-1265.
10.T. Борос, T. Кайлаф и В. Ольшевский, Быстрые алгоритмы для решения линейных систем Коши, препринт, 1995.
11.Р. П. Брент, Параллельные алгоритмы для теплицевых систем, Численная линейная алгебра, Цифровая обработка сигналов и параллельные алгоритмы (под ред. Г. ЧАС. Голуб и П. Van Dooren), Springer-Verlag, 1991, 75--92.
12., Численная устойчивость некоторых быстрых алгоритмов для структурированных матриц, Тр. Семинар по научным вычислениям 1997 (Гонконг, март 1997), SpringerVerlag, 1998, 41--48.
13.Р. П. Брент, Ф. Г. Густавсон и Д. Y. Y. Юн, Быстрое решение теплицевых систем уравнений и вычисление аппроксимаций Паде, Дж. Алгоритмы 1 (1980), 259-295.
14.J. Р. Грозд, Устойчивость методов решения тёплицевых систем уравнений, СИАМ Дж. Sci. Stat. Вычисл. 6 (1985), 349-364.
15., Слабая и сильная устойчивость алгоритмов в численной линейной алгебре, Линейная алгебра. Appl. 88/89 (1987), 49-66.
16., Матричные свойства алгоритмов Левинсона и Шура, J. Численная линейная алгебра с приложениями 1 (1992), 183-198.
17.J. П. Бург, Спектральный анализ максимальной энтропии, кандидатская диссертация, Стэнфордский университет, Стэнфорд, Калифорния, 1975.
18.T. F. Чан и П. С. Хансен, Упреждающий алгоритм Левинсона для индефинитных теплицевых систем, SIAM J. Матричный анал. Appl. 13 (1992), 490-506.
19., Упреждающий алгоритм Левинсона для общих систем Теплица, IEEE Trans. Сигнальный процесс. 40 (1992), 1079-1090.
20.S. Чандрасекаран и А. ЧАС. Сейед, Стабилизация обобщенного алгоритма Шура, СИАМ Дж. Матричный анал. Appl. 17 (1996), 950-983.
21., Быстрый стабильный решатель для несимметричных теплицевых и квазитеплицевых систем линейных уравнений, препринт, Ян. 1996 год. [Появляется в SIAM J. Матричный анал. Appl. 19 (1998), 107-139.]
22.J. Чун, алгоритмы быстрого массива для структурированных матриц, кандидатская диссертация, Стэнфордский университет, Стэнфорд, Калифорния, 1989.
23.J. Чун, Т. Кайлаф и Х. Лев-Ари, Быстрые параллельные алгоритмы для QR и треугольная факторизация, SIAM J. Sci. Stat. Вычисл. 8 (1987), 899-913.
24.Г. Кибенко, Численная устойчивость алгоритма Левинсона-Дурбина для систем уравнений Теплица, SIAM J. Sci. Stat. Вычисл. 1 (1980), 303-319.
25., Быстрая ортогонализация Теплица с использованием внутренних произведений, SIAM J. Sci. Stat. Вычисл. 8 (1987), 734-740.
26.J.-М. Делосме и я. С. F. Ипсен, Параллельное решение симметричных положительно определенных систем с гиперболическими вращениями, Линейная алгебра. 77 (1986), 75-111.
27.П. Делсарта, Y. V. Генин и Y. Г. Камп, Обобщение алгоритма Левинсона для эрмитовых матриц Теплица с любым профилем ранга, IEEE Trans. Акустика, речь и обработка сигналов ASSP - 33 (1985), 964--971.
28.J. Дурбин, Подгонка моделей временного ряда, Rev. Int. Stat. Inst. 28 (1959), 229-249.
29.Г. E. Форсайт и С. B. Молер, Компьютерное решение линейных алгебраических систем, Прентис-Холл, Нью-Джерси, 1967.
30.Р. W. Фрейнд и Х. Чжа, Формально биортогональные полиномы и альтернативный алгоритм Левинсона для общих систем Теплица, Линейная алгебра. 188/189 (1993), 255-303.
31., Упреждающий алгоритм для решения общих систем Ханкеля, Числитель. Математика. 64 (1993), 295-321.
32.Я. Гохберг (редактор), И. Методы Шура в теории операторов и обработки сигналов (Теория операторов: достижения и приложения, том 18), Birkh? Auser Verlag, Базель, 1986.
33.Я. Гохберг, Т. Кайлаф и В. Ольшевский, Гауссова элиминация с частичным поворотом для матриц со структурой смещений, Матем. Comp. 64 (1995), 1557-1576.
34.Я. Гохберг и я. Koltracht, смешанные, покомпонентные и структурированные номера условий, SIAM J. Матричный анал. Appl. 14 (1993), 688--704.
35.Я. Гохберг, И. Колтрахт и Д. Xiao, Условие и точность алгоритмов вычисления коэффициентов Шура тёплицевых матриц, SIAM J. Матричный анал. Appl. 15 (1994), 1290-1309.
36.Г. ЧАС. Голуб, Численные методы решения линейных задач наименьших квадратов, Числ. Математика. 7 (1965), 206-216.
37.Г. ЧАС. Голуб и Дж. ЧАС. Уилкинсон, Заметка об итерационном уточнении решения наименьших квадратов, Числитель. Математика. 9 (1966), 139-148.
38.Г. ЧАС. Голуб и C. Van Loan, Matrix Computations, третье издание, Johns Hopkins Press, Балтимор, Мэриленд, 1997.
39.N. Гулд, О росте в гауссовой элиминации с полным поворотом, SIAM J. Матричный анал. Appl. 12 (1991), 354-361.
40.Минг Гу, Стабильные и эффективные алгоритмы для структурированных систем линейных уравнений, Тех. Доклад LBL-37690, лаборатория Лоуренса Беркли, авг. 1995 год. [Появляется в SIAM J. Матричный анал. Appl. 19 (1998), 279-306.]
41., Новые быстрые алгоритмы для структурированных задач наименьших квадратов, Тех. Доклад ЛБЛ-37878, лаборатория Лоуренса Беркли, ноябрь 1995 год.
42.М. ЧАС. Гуткнехт, Стабильные повторения строк для таблицы Pad e и, в общем, сверхбыстрые упреждающие решатели для неэрмитовских систем Теплица, Linear Alg. Appl. 188/189 (1993), 351-421.
43.М. ЧАС. Гуткнехт и М. Хохбрюк, Упреждающие алгоритмы Левинсона и Шура для неэрмитовских теплицевых систем, IPS Research Report 93--11, ETH, Z? Urich, август 1993.
44.М. ЧАС. Гуткнехт и М. Хохбрюк, Устойчивость формул обращения для тёплицевых матриц, Отчет по исследованиям IPS 93- 13, ETH, Z? Urich, октябрь 1993.
45.П. С. Хансен и Х. Гесмар, Быстрое ортогональное разложение дефектных по индексу тёплицевых матриц, Численные алгоритмы 4 (1993), 151-166.
46.Г. Хейниг, Обращение обобщенных матриц Коши и другие классы структурированных матриц, Линейная алгебра для обработки сигналов, Объемы ИМА в математике и ее приложения, Том. 69, 1994, 95-114.
47.Г. Хейниг и К. Рост, Алгебраические методы для теплицево-подобных матриц и операторов, Теория операторов, т. 13, Birkhauser, Basel, 1984.
48.D. J. Хайрам и Н. J. Higham, Обратная ошибка и условие структурированных линейных систем, SIAM J. Матричный анал. Appl. 13 (1992), 162-175.
49.N. J. Higham, точность и стабильность численных алгоритмов, SIAM, Филадельфия, 1996.
50.D. Гильберт, Эйн Бейтраг, теоретические основы полиномов Лежандра, Acta Math. 18 (1894), 155-160.
51.М. Янковский и М. Возняковски, итерационное уточнение подразумевает численную устойчивость, БИТ 17 (1977), 303-311.
52.T. Kailath and J. Chun, Обобщенная структура смещения для blockToeplitz, Теплиц-блок и тёплицевы матрицы, SIAM J. Матричный анал. Appl. 15 (1994), 114-128.
53.T. Kailath, S. Y. Кунг и М. Морф, Смещение рангов матриц и линейных уравнений, Ж. Математика. Анальный. Appl. 68 (1979), 395-470.
54.T. Кайлаф и А. ЧАС. Sayed, Displacement structure: theory and applications, SIAM Review 37 (1995), 297--386.
55.T. Kailath, A. Виейра и М. Морф, Инверсы операторов Теплица, нововведения и ортогональные многочлены, Обзор СИАМ 20 (1978), 106-119.
56.A. N. Колмогоров, Интерполяция и экстраполяция стационарных случайных последовательностей, Изв. 5 (1941), 3-11 (на русском). Подведение итогов немецкого языка, там же, 11-14.
57.N. Левинсон, критерий погрешности Wiener RMS (Root-Mean-Square) при проектировании и прогнозировании фильтров, J. Математика. Phys. 25 (1947), 261-278.
58.F. T. Luk и S. Qiao, Быстрая, но неустойчивая ортогональная техника триангуляции для тёплицевых матриц, Линейная алгебра. 88/89 (1987), 495-506.
59.W. Миллер и К. Wrathall, Программное обеспечение для кругового анализа матричных алгоритмов, Academic Press, New York, 1980.
60.V. Ольшевский, Поворот на структурированные матрицы с приложениями, препринт, июль 1997.
61.С. С. Пейдж, Анализ ошибок метода решения матричных уравнений, Матем. Comp. 27 (1973), 355-359.
62.S. Qiao, Гибридный алгоритм быстрой ортонализации Теплица, Числитель. Математика. 53 (1988), 351-366.
63.A. ЧАС. Сайед, Структура смещения в обработке сигналов и математика, диссертация, Стэнфордский университет, Стэнфорд, Калифорния, 1992.
64.Я. Schur, «Uber Potenzreihen, die im Innern des Einheitskreises beschr? Ankt sind, J. Fur die Reine und Angewandte Mathematik 147 (1917), 205-232. Английский перевод в [? ], 31-59.
65.Г. W. Стюарт, Введение в вычисления матриц, Academic Press, Нью-Йорк, 1973.
66., Оценки возмущений для QR-факторизации матрицы, SIAM J. Число. Анальный. 14 (1977), 509-518.
67., Влияние погрешности округления на алгоритм сокращения даун-факторизации Холецкого, J. Inst. Математика. Appl. 23 (1979), 203-213.
68.М. Стюарт, Стабильный поворот для быстрой факторизации матриц типа Коши, препринт, Ян. 13, 1997.
69.М. Стюарт и П. Ван Дорен, Проблемы устойчивости в факторизации структурированных матриц, SIAM J. Матричный анал. Appl. 18 (1997), 104-118.
70.D. Р. Сладкие, численные методы для теплицевых матриц, кандидатская диссертация, Университет Аделаиды, 1982.
71., Быстрая ортогонализация Теплица, Числитель. Математика. 43 (1984), 1- 21.
72., Использование поворота для улучшения численной эффективности алгоритмов для матриц Теплица, SIAM J. Матричный анал. Appl. 14 (1993), 468-493.
73.D. Р. Свит и Р. П. Брент, Анализ ошибок быстрого метода частичного поворота для структурированных матриц, Труды SPIE, Volume 2563, Алгоритмы расширенной обработки сигналов SPIE, Беллингхэм, Вашингтон, 1995, 266-280.
74.Г. Сегео, Ортогональные многочлены, AMS Коллоквиум изд. XXIII, AMS, Провиденс, Род-Айленд, 1939 год.
75.W. F. Тренч, Алгоритм инверсии конечных тёплицевых матриц, Ж. SIAM (SIAM J. Appl. Математика.) 12 (1964), 515-522.
76.J. М. Варах, Оценки обратных ошибок для систем Теплица, препринт, Отдел компьютерных наук, Университет Британской Колумбии, Ванкувер, сентябрь 1992 год.
77.J. М. Вара, Продленная матрица, Линейная алгебра. 187 (1993), 269-278.
78.N. Винера, экстраполяция, интерполяция и сглаживание стационарных временных рядов, с инженерными приложениями, Technology Press и Wiley, Нью-Йорк, 1949 (изначально опубликован в 1941 г. как технический отчет).
79.J. ЧАС. Уилкинсон, Анализ ошибок прямых методов матричной инверсии, J. Assoc. Вычисл. Маха. 8 (1961), 281-330.
80.J. ЧАС. Уилкинсон, Округление ошибок в алгебраических процессах, Прентис-Холл, Энглвуд Клифс, Нью-Джерси, 1963.
81.J. ЧАС. Уилкинсон, Алгебраическая задача на собственные значения, Издательство Оксфордского университета, Лондон, 1965.

Эта публикация на других ресурсах

Портал arXiv.org

Другие публикации этой тематики
1.Редкое изъятие фазы одномерных сигналов методом Прони
Беинерт Р. , Плонка Д.
2.Структура многочленов в предопределенных алгоритмах BiCG и направление переключения предварительно обусловленных систем
Итох С. , Суджихара М.
3.Миграция Кирхгофа без фаз
Бардслеу П. , Фернандо Д. В.
4.Рекурсивные семейства итерационных отображений более высокого порядка
Джраçа М. М.
5.О наилучших приближенных решениях уравнения МатрицыAXB=C
Öздемир Х. , Сардуван М.
6.Теплиц и Теплиц-блок-Теплица и их корреляция с сизигиями многочленов
Кхалил Х. , Моурраин Б. , Скхатзман М.
7.Алгоритм описания множества решений любой тропической линейной системыAx=Bx
Лорензо Е.
8.Аналоги сопряженной матрицы для обобщенных инверсий и соответствующие правила Крамера
Куркхеи И.
9.Гауссовские многочлены и функции ограниченного разбиения с ограничениями
Фел Л. Д.
10.Новая вариация шляп угадайку игры
Ма Т. , Сун Х. , Уу Х. А.