ИСПОЛЬЗОВАНИЕ ЭКОНОМНЫХ МЕТОДОВ ВЫЧИСЛЕНИЯ ЧАСТИ СПЕКТРА БОЛЬШИХ РАЗРЕЖЕННЫХ МАТРИЦ В ЗАДАЧАХ ГАЗОВОЙ ДИНАМИКИ Дипломная работа на тему Выполнил: студент. - презентация

1

2 ИСПОЛЬЗОВАНИЕ ЭКОНОМНЫХ МЕТОДОВ ВЫЧИСЛЕНИЯ ЧАСТИ СПЕКТРА БОЛЬШИХ РАЗРЕЖЕННЫХ МАТРИЦ В ЗАДАЧАХ ГАЗОВОЙ ДИНАМИКИ Дипломная работа на тему Выполнил: студент 506 группы Сабиров Г. Р. Научный руководитель: к. ф.-м. н. Козубская Т. К. Москва 2006 г.

3 План Обработка исходной матрицы A. Реализация матрично-векторных операций с использованием разреженности и специального вида матриц. Обработка исходной матрицы A. Реализация матрично-векторных операций с использованием разреженности и специального вида матриц. Построение проектора Q: Построение проектора Q: Q T AQ=H ; A (nxn), Q(kxn) => H(kxk), k H(kxk), k<

4 Компактное хранение и обработка матриц – формула доступа к элементам Исходная матрица имеет размер NxN; M ненулевых элементов

5 Недостатки: Неочевидные формулы работы с матрицами в компактном виде. Неочевидные формулы работы с матрицами в компактном виде. Трудоемкий последовательный доступ к конкретному элементу матрицы. Трудоемкий последовательный доступ к конкретному элементу матрицы.Преимущества: Занимаемая память меньше во много раз. Занимаемая память меньше во много раз. Быстрое умножение матрицы на вектор: порядок операций не О(N*N), а О(M) Быстрое умножение матрицы на вектор: порядок операций не О(N*N), а О(M) Компактное хранение и обработка матриц – недостатки и преимущества

6 Концепция Крыловского подпространства K=span(b 1,Ab 1,A 2 b 1,…, A k b 1 )

7 Извлечение информации о матрице А из матрично-векторных операций

8 Концепция Крыловского подпространства Q – ортогональная Q – ортогональная Q – хорошо обусловлена Q – хорошо обусловлена Q – легко обратима Q – легко обратима

9 Алгоритм Арнольди для (частичного) приведения к форме Хессенберга

10 Трехдиагонализация

11 Алгоритм Ланцоша для (частичного) приведения к симметричной трехдиагональной форме

12 Идеи

13 Концепция на пальцах

14 Построение проектора Q без использования самой матрицы А (i-й шаг)

15 Диагонализация

16 Неявный симметричный QR-шаг со сдвигом Уилкинсона

17 Симметричный QR-алгоритм Выполнить трехдиагонализацию по некоторому алгоритму. Получится матрица T. until q=n Для i=1:n-1 положить и равными нулю, если Найти наибольшее q и наименьшее p, такие, что если то диагональная, а неприводимая. if q < n Применить QR-шаг с каким-либо сдвигом к endend Этот алгоритм требует примерно флопов.

18 Пример спектра