Циклическое сокращение
Циклическая редукция — это численный метод решения больших линейных систем путем многократного разделения задачи. Каждый шаг исключает четные или нечетные строки и столбцы матрицы и сохраняет ее в аналогичной форме. Шаг исключения относительно затратен, но разделение задачи позволяет проводить параллельные вычисления.
Применимость
Метод применим только к матрицам, которые могут быть представлены как (блочная) матрица Теплица . Такие проблемы часто возникают в неявных решениях для уравнений в частных производных на решетке. Например, быстрые решатели для уравнения Пуассона выражают проблему как решение трехдиагональной матрицы, дискретизируя решение на регулярной сетке.
Точность
Системы, изначально имеющие хорошую численную устойчивость, стремятся улучшаться с каждым шагом. Более того, до точки, где может быть дано хорошее приближенное решение, [1] но поскольку специальная форма матрицы должна быть сохранена, поворот не может быть выполнен для улучшения числовой точности.
Сравнение с многосеткой
Метод не является итеративным, он ищет точное решение линейной задачи, согласующееся с заданными граничными значениями, в отличие от похожего, но более дешевого в вычислительном отношении многосеточного метода , который распространяет оценки коррекции ошибок вниз и допускает различные параметры релаксации в разных масштабах, причем итеративный аспект позволяет лучше учитывать нелинейные особенности.
Сочетание сбыстрое преобразование ФурьеБПФ
Преобразование из пространственной области и переформулирование уравнения в частных производных называется спектральным методом , анализ Фурье и циклическая редукция объединены в алгоритме FACR [2] , который объясняется в численных рецептах – см. 19.4 Методы Фурье и циклической редукции для граничных задач. [3]
Примечания и ссылки
- ↑ Уолтер Гандер и Джин Х. Голуб, Циклическая редукция – история и приложения, Труды семинара по научным вычислениям, 10–12 марта 1997 г.
- ^ П. Н. Шварцтраубер, Метод циклической редукции, анализ Фурье и алгоритм FACR для дискретного решения уравнения Пуассона на прямоугольнике, Обзор SIAM Общества промышленной и прикладной математики, 19 стр. 490–501, 1977 г.
- ^ WH Press, SA Teukolsky, WT Vetterling, BP Flannery Численные рецепты на языке «C»: искусство научных вычислений Архивировано 06.08.2013 в Wayback Machine, стр. 885 ISBN 0-521-43108-5 Cambridge University Press 1988–1992
 | Эта статья, связанная с математическим анализом , является заглушкой . Вы можете помочь Википедии, расширив ее. |
