Оглавление
Рекурсия Левинсона
-
Рекурсия Левинсона
- Процедура для рекурсивного вычисления решения уравнения с матрицей Теплица
- Выполняется за Θ(n2) времени, что быстрее метода исключения Гаусса–Жордана
- Предложена Норманом Левинсоном в 1947 году, усовершенствована Джеймсом Дурбином в 1960 году
-
Сравнение с другими методами
- Рекурсия Левинсона быстрее, но более чувствительна к ошибкам округления
- Алгоритм Барейсса для матриц Теплица работает так же быстро, но использует O(n2) пробелов
- Алгоритм Барейсса численно стабилен, рекурсия Левинсона слабо стабильна
-
Новые алгоритмы
- Асимптотически быстрые алгоритмы могут решать за Θ(n логарифмов)
- Рекурсия Левинсона остается популярной из-за простоты и скорости для небольших n
-
Алгоритм Левинсона–Дурбина
- Работает в два этапа: установление прямых и обратных векторов, построение решения
- Прямые и обратные векторы определяются рекурсивно
- Решение строится рекурсивно, используя обратные векторы
-
Блочный алгоритм Левинсона
- Применяется для блочных теплицевых матриц
- Используется в алгоритмах обработки сигналов и циклостационарных сигналах
-
Дополнительные ресурсы
- Ссылки на статьи и книги по теме
- Ссылки на исследования и статьи по устойчивости методов решения систем уравнений Теплица