Циклическое сокращение

Циклическая редукция — это численный метод решения больших линейных систем путем многократного разделения задачи. Каждый шаг удаляет четные или нечетные строки и столбцы матрицы и сохраняет аналогичную форму. Этап исключения относительно дорог, но разделение задачи позволяет проводить параллельные вычисления.

Применимость

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

Точность

Системы, которые изначально имеют хорошую численную стабильность, имеют тенденцию улучшаться с каждым шагом. Более того, до такой степени, что можно дать хорошее приближенное решение: ^[1] но поскольку должна быть сохранена специальная форма матрицы, поворот не может быть выполнен для повышения числовой точности.

Сравнение с многосеточным

Этот метод не является итеративным, он ищет точное решение линейной задачи, согласующееся с заданными граничными значениями, в отличие от аналогичного, но более дешевого в вычислительном отношении многосеточного метода , который распространяет оценки исправления ошибок вниз и учитывает разные параметры релаксации в разных масштабах, итеративный аспект, позволяющий лучше учитывать нелинейные функции.

Комбинация с быстрым преобразованием Фурье БПФ

Преобразование из пространственной области и переформулирование УЧП называется спектральным методом , анализ Фурье и циклическое сокращение объединены в алгоритме FACR. ^[2] что объясняется в «Численных рецептах» — см. 19.4 «Методы Фурье и циклического приведения для краевых задач». ^[3]

Примечания и ссылки

^ Уолтер Гандер и Джин Х. Голуб, Циклическая редукция - история и приложения , Материалы семинара по научным вычислениям, 10–12 марта 1997 г.
^ П. Н. Шварцтраубер, Метод циклической редукции, анализ Фурье и алгоритм FACR для дискретного решения уравнения Пуассона на прямоугольнике, Обзор SIAM Общества промышленной и прикладной математики, 19 стр. 490–501, 1977 г.
^ WH Press, SA Teukolsky, WT Vetterling, BP Flannery. Численные рецепты в «C»: искусство научных вычислений. Архивировано 6 августа 2013 г. в Wayback Machine , стр. 885. ISBN 0-521-43108-5 Издательство Кембриджского университета, 1988–1992 гг.

Эта математическому анализу, статья, посвященная незавершена . Вы можете помочь Википедии, расширив ее .

[1] Уолтер Гандер и Джин Х. Голуб, Циклическая редукция - история и приложения , Материалы семинара по научным вычислениям, 10–12 марта 1997 г.

[2] П. Н. Шварцтраубер, Метод циклической редукции, анализ Фурье и алгоритм FACR для дискретного решения уравнения Пуассона на прямоугольнике, Обзор SIAM Общества промышленной и прикладной математики, 19 стр. 490–501, 1977 г.

[3] WH Press, SA Teukolsky, WT Vetterling, BP Flannery. Численные рецепты в «C»: искусство научных вычислений. Архивировано 6 августа 2013 г. в Wayback Machine , стр. 885. ISBN 0-521-43108-5 Издательство Кембриджского университета, 1988–1992 гг.

[1]

[2]

[3]