Участник:Elijah/Нахождение собственных чисел квадратной матрицы методом QR разложения: различия между версиями
Elijah (обсуждение | вклад) |
Elijah (обсуждение | вклад) |
||
| Строка 31: | Строка 31: | ||
=== Схема реализации последовательного алгоритма === | === Схема реализации последовательного алгоритма === | ||
| − | // | + | |
| + | Последовательная реализация простейшего алгоритма сострит из некоторого числа итераций. <br> | ||
| + | |||
| + | На итерации <math> n </math>: | ||
| + | # Для матрицы <math> A_{n} </math> строится QR разложение любым доступным последовательным алгоритмом на матрицы <math> Q_{n} </math> и <math> R_{n} </math> <br> | ||
| + | # Матрицы <math> R_{n} </math> и <math> Q_{n} </math> перемножаются, таким образом получается матрица <math> A_{n+1} = R_{n} * Q_{n} </math> для следующей итерации <math> n + 1 </math> | ||
| + | |||
| + | По окончании каждой итерации проверятся, приведена ли матрица к диагональной форме. | ||
| + | |||
| + | # TO do about heisenberg form and algorithm with shift | ||
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
Версия 08:45, 16 сентября 2016
| Нахождение собственных чисел квадратной матрицы методом QR разложения | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]N * O(n^3)[/math] |
| Объём входных данных | [math]n^2[/math] |
| Объём выходных данных | [math]n[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]Unknown[/math] |
| Ширина ярусно-параллельной формы | [math]Unknown[/math] |
Основные авторы описания: И.В.Афанасьев, В.А.Шишватов
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
1 Свойства и структура алгоритма
//TODO
1.1 Общее описание алгоритма
//TODO
1.2 Математическое описание алгоритма
//TODO
1.3 Вычислительное ядро алгоритма
Для базового алгоритма вычислительное ядро состоит из операций двух типов:
1) поиска QR разложения с использованием метода Гивенса
2) матричного умножения полученных матриц
Данные операции производятся на каждой итерации до тех пор, пока матрица не примет диагональную форму (в вещественном случае)
1.4 Макроструктура алгоритма
//TODO
1.5 Схема реализации последовательного алгоритма
Последовательная реализация простейшего алгоритма сострит из некоторого числа итераций.
На итерации [math] n [/math]:
- Для матрицы [math] A_{n} [/math] строится QR разложение любым доступным последовательным алгоритмом на матрицы [math] Q_{n} [/math] и [math] R_{n} [/math]
- Матрицы [math] R_{n} [/math] и [math] Q_{n} [/math] перемножаются, таким образом получается матрица [math] A_{n+1} = R_{n} * Q_{n} [/math] для следующей итерации [math] n + 1 [/math]
По окончании каждой итерации проверятся, приведена ли матрица к диагональной форме.
- TO do about heisenberg form and algorithm with shift
1.6 Последовательная сложность алгоритма
//TODO
1.7 Информационный граф
//TODO
1.8 Ресурс параллелизма алгоритма
// TODO
1.9 Входные и выходные данные алгоритма
Входные данные: плотная квадратная матрица [math]A[/math] (элементы [math]a_{ij}[/math]).
Объём входных данных: [math]n^2[/math].
Выходные данные: n вещественных собственных чисел [math] | l_{i} | [/math] матрицы [math]A[/math]
Объём выходных данных: [math]n[/math].
1.10 Свойства алгоритма
// TODO
