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

Презентация:



Advertisements
Похожие презентации
ИСПОЛЬЗОВАНИЕ ЭКОНОМНЫХ МЕТОДОВ ВЫЧИСЛЕНИЯ ЧАСТИ СПЕКТРА БОЛЬШИХ РАЗРЕЖЕННЫХ МАТРИЦ В ЗАДАЧАХ ГАЗОВОЙ ДИНАМИКИ.
Advertisements

ИСПОЛЬЗОВАНИЕ ЭКОНОМНЫХ МЕТОДОВ ВЫЧИСЛЕНИЯ ЧАСТИ СПЕКТРА БОЛЬШИХ РАЗРЕЖЕННЫХ МАТРИЦ В ЗАДАЧАХ ГАЗОВОЙ ДИНАМИКИ Дипломная работа на тему Сабиров Г. Р. Группа.
Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования «ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»
Основы матричной алгебры СЛОЖЕНИЕ МАТРИЦ Операция сложения матриц определяется для двух матриц одинакового размера. Если А, В – это матрицы, то элементы.
Примеры обработки информации (Алгоритмы) Примеры обработки информации (Алгоритмы)
Фрагментация алгоритма умножения симметричной разреженной матрицы на вектор Студентка: Ткачёва А.А. ФПМИ 4курс Руководитель: Киреев С.Е
ЛЕКЦИЯ 11 Каждый элемент этой матрицы равен 0 или 1. Произведение дзух чисел можно получить, если суммировать элементы матрицы р следующем порядке:
Семинар 1 Уравнение Сильвестра. I. A, B - матрицы размера n x n, m x m соответственно, правая часть Y - матрица размера m x n. Неизвестной является матрица.
Обратная Матрица. Определение. Матрица называется о б р а т н о й к квадратной матрице, если Обратная матрица обозначается символом Примечание. Операция.
Матрицы Собственные числа и собственные векторы. Введение Целый ряд инженерных задач сводится к рассмотрению систем уравнений, имеющих единственное решение.
Нижегородский государственный университет им. Н.И.Лобачевского Факультет Вычислительной математики и кибернетики Применение технологии Cilk для решения.
ЛОГИЧЕСКИЕ ЭЛЕМЕНТЫ 33. Упрощённо можно представить работу компьютера как некоторого устройства, производящего обработку двоичных сигналов, соответствующих.
Проверка эквивалентности срединной и линейной осей многоугольника Дипломная работа студента 545 группы Подколзина Максима Валериевича Санкт-Петербургский.
§1 МАТРИЦЫ И ОПРЕДЕЛИТЕЛИ 1.1 Матрицы и их свойства Матрицей размера m n называется совокупность mn чисел, расположенных в виде таблицы из m строк и n.
Матрицы лекция 2. Определение Матрицей размера называется прямоугольная таблица из чисел, где,, состоящая из строк и столбцов.
1. МАТРИЦЫ И СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ 1.1. Матрицы. Действия с матрицами Определение 1.1. Таблица вида: (1.1) в которой все – заданные числа, называется.
Литература Апатенок Р.Ф., Маркина А.М., Попова Н.В., Хейнман В.Б. Элементы линейной алгебра и аналитической геометрии Ильин В.А., Позняк Э.Г. Линейная.
Выполнил студент : Санкт - Петербург 2012 Министерство образования Российской Федерации Санкт - Петербургский государственный архитектурно - строительный.
Распараллеливание построения среднеквадратических приближений сплайнами восьмого порядка аппроксимации Полуянов С.В.
Матрицы и операции над ними.. Матрицей называется множество чисел, образующих прямоугольную таблицу, которая содержит m строк и n столбцов.
Транксрипт:

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

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

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

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

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

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

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

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

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

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

Идеи

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

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

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

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

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

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