Алгоритм нахождения спектра больших матриц - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Производная. Алгоритм нахождения производной 1 200.31kb.
Лабораторная работа 1 Методы решения задач линейной алгебры 1 31.76kb.
Решение экономических задач с помощью матриц. Изучить свойства некоторых... 1 146.2kb.
Пример: Алгоритм метода пжи (полные жардановые исключения) 1 19.1kb.
Шифрование методом скремблеров 1 52.54kb.
Изучить блочные алгоритмы шифрования: алгоритм перестановки, алгоритм... 1 83.13kb.
Вопросы к экзамену по курсу «Алгебра и геометрия» 1 19.74kb.
Алгоритм нахождения массовой доли растворенного вещества 1 79.5kb.
Экзаменнацоинные вопросы по математике для студентов 1 курса факультета... 1 28.14kb.
Термины и определения Алгоритм 1 40.32kb.
Программа курса модуль I. Линейная алгебра Тема Матрицы и действия... 3 269.26kb.
Программа аттестационного испытания по дисциплине «математика для... 1 49.34kb.
Направления изучения представлений о справедливости 1 202.17kb.

Алгоритм нахождения спектра больших матриц - страница №1/1

АЛГОРИТМ НАХОЖДЕНИЯ СПЕКТРА БОЛЬШИХ МАТРИЦ

М.Л. Бахмутский

Российский государственный геологоразведочный университет, Москва, Россия
Предложен алгоритм нахождения собственных значений и собственных векторов больших, порядка десятков тысяч строк и столбцов, симметричных заполненных матриц. Рассматривается спектральная задача: , где (1)

А – симметричная заполненная матрица размерности N*N.

N ≈10000÷150000. Не теряя общности, полагаем . Сформируем ортогональную матрицу:, где элементы (2)

(3)

Умножение матрицы на вектор размерности N означает вейвлет – преобразование на основе вейвлетов Хаара. Сформируем последовательность из k матриц.



Матрица является блочно-диагональной матрицей с ненулевыми диагональными блоками и нулевыми внедиагональными блоками. Рассмотрим матрицу . Умножив уравнение ( 1) на матрицу W, получим задачу:



(4)

Таким образом, к матрице A и собственному вектору x было применено вейвлет-пакетное разложение [1]. В результате получаем блочную матрицу блочной размерности и с блоками размерностью . Выделим диагональную часть , т.е. представим эту матрицу как:



, где , (4a)

В силу свойств, вейвлет –пакетов матрица описывает наиболее регулярную часть исходной матрицы , а матрица B – матрица поправок различной гладкости. Рассмотрим спектральную задачу:



(5)

Эта задача распадается на k независимых спектральных задач размерностью .



(6)

Задачи (6) решаются при помощи хорошо работающих традиционных алгоритмов[2], причем, для компьютеров с параллельной архитектурой, каждая из задач(6) решается одновременно и независимо друг от друга.

Матрица собственных векторов задачи (5) имеет вид:

(7)

Подматрицы являются ортогональными матрицами, столбцами которых являются собственные вектора задач (6). Собственные вектора задачи (5) образуют базис в пространстве собственных векторов задачи (4) и имеют по ненулевых компонент. Воспользуемся этим фактом, представлением (4a) и построим теорию возмущений для задачи (4) по аналогии с теорией возмущения Бриллюена-Вигнера [3]. Перепишем (4) для n-го собственного вектора в виде: Полагая, что при разложим по векторам базиса u.



(8)

И подставим в (4). В результате получим уравнения:



, (9)

Эту систему уравнений решаем методом последовательных приближений. В первом приближении имеем:





(10)

Процесс последовательных приближений быстро сходится при любой матрице B, т.к. искомое собственное значение находится и в знаменателе. Легко видеть из (4a) и (7), что скалярное произведение Для нахождения собственного значения исходной задачи используется метод Ньютона вычисления корня функции F(λ). Т.е. ищется корень уравнения F(λ)=0, где начальное приближение к есть



,

Вычислив , используя (10), находим собственный вектор . Константа с в (10) находится из условия нормировки. Найдя собственные вектора задачи (4), находим собственные вектора исходной задачи, проделав обратное вейвлет преобразование .

Литература

1.Э.Столниц,Т.ДеРоуз,Д.Салезин, Вейвлеты в компьютерной графике,Москва-Ижевск,2002г.



2.Уилкинсон,Райнш, Справочник алгоритмов на языке Алгол. Линейная алгебра ,М., «Машиностроение»,1976г.

3.Ф.М.Морс,Г.Фешбах, Методы теоретической физики,т.2,М.,Наука,1963




Дети — наше утешение в старости, и помогают быстрее ее достичь. Лайонел Кауфман
ещё >>