Основная идея мультисетки - это проекция. Я пытаюсь думать об этом следующим образом:
Предположим, я хочу определить PDE с большой точностью, поэтому я продолжаю дискретизировать область (скажем, используя метод конечных разностей) на очень тонкой сетке с большим количеством точек. В конце концов, я настроил свою систему уравнений и готов ее решить. Я пытаюсь использовать мой любимый итеративный решатель (Якоби, Гаусса Зейделя, сопряженный градиент и т. Д.). Я продолжаю ждать больше суток и понимаю, что мой компьютер все еще пытается вычислить ответ !!!
Причина, по которой эти итерационные методы не работают быстро, заключается в том, что (как правило), когда вы устанавливаете большую систему уравнений, как эта, сама матрица имеет собственные значения, чрезвычайно близкие к 1. Почему это имеет значение? Потому что скорость сходимости многих итерационных методов обратно пропорциональна наибольшему собственному значению (см. Ссылку Кристиана Класона на слайды из учебника по многосетке Бригга, часть 1, страница 27). Таким образом, чем ближе наибольшее собственное значение к 1, тем медленнее итерационный метод. (Примечание: это немного упрощает вещи, но это помогает мотивировать потребность в многосетке).
Очевидно, что всегда быстрее решить проблему, если есть меньше неизвестных (то есть на грубой сетке с меньшим количеством точек сетки). Но что более важно, решение (или приближенное решение) на более грубой сетке является хорошей отправной точкой для решения задачи на более тонкой сетке. Это ключевая идея большинства (если не всех) многосеточных методов. Почему это так? Интуитивно, это имеет смысл, но есть математически строгий способ оправдать это.
Давайте посмотрим на режимы Фурье ошибки в итеративном методе (для аргументов, скажем, jacobi или gauss seidel), примененном к исходной задаче тонкой сетки. Мы увидим, что в течение первых нескольких итераций большая часть высокочастотных (сильно колебательных) ошибок устраняется! Это здорово, но есть низкочастотная (менее колебательная) ошибка, которая все еще остается и не исчезает быстро. Фактически, это ошибка низкой частоты, которая мешает стандартному итеративному методу быстро сходиться.
Когда мы решаем проблему на более грубой сетке (скажем, с помощью итеративного метода, такого как jacobi или gauss-seidel), мы, по существу, способны устранять ошибки с более низкой частотой гораздо быстрее (т.е. за меньшее количество итераций), чем на тонкой сетке . Итак, если мы решим проблему грубой сетки, у нас будет решение, чьи ошибки на низких частотах были значительно уменьшены. Таким образом, это было бы полезно в качестве отправной точки для итерационного метода на более мелкой сетке.
Несмотря на то, что существуют разные многосеточные методы, большинство из них работают по разным причинам:
- Начните с проблемы с мелкой сеткой
- Проект на грубую сетку (также известный как ограничение )
- Приближенное решение на грубой сетке (с использованием другого решателя)
- Спроектируйте решение для грубой сетки на более мелкую сетку (также известную как продолжение )
- Используя проекцию из 4. в качестве начального предположения, решите проблему точной сетки итерационным методом.
Для меня самая сложная часть многосеточного метода - это проекции между сетками. Уроки Briggs, предложенные @ChristianClason, решают эту тему намного лучше, чем я.
Этот сайт, возможно, не является хорошим местом для подробного объяснения с помощью псевдокода (как указано в FAQ : «Если вы можете представить целую книгу, которая отвечает на ваш вопрос, вы спрашиваете слишком много»), так что вы можете захотеть начать с одной из классических книг по этой теме (перечисленных ниже) и вернуться к конкретным вопросам о конкретных деталях, с которыми у вас возникли проблемы.
Briggs, Multigrid Tutorial , SIAM, 2000 (Вы можете скачать слайды здесь и здесь ). Это случайный источник, дающий подробное введение в принципы многосеточных, в основном для эллиптических задач.
Brandt, Multigrid Techniques , пересмотренное издание, SIAM 2011 (или загрузите PDF ). Это отличное развитие многосеточной философии и многомасштабного моделирования, и у нее есть хорошие шансы на глубокое изменение вашего мышления о неявных решателях. Веб-сайт Ачи Брандта содержит еще много ссылок, в том числе его « Обзор научных расчетов в нескольких масштабах» за 2000 год .
Trottenberg, Oosterlee, и Schueller , Multigrid , Academic Press, 2001. Это более проработанные примеры, чем у Брандта, включая множество экспериментов и подробностей о конкретных методах, особенно в контексте динамики жидкости.
Hackbusch, Multigrid Methods and Applications , Springer, 1985. Это обеспечивает строгую теорию сходимости, включая «многосеточный тип второго рода» для интегральных операторов Фредгольма.
источник
Еще одна классика:
Примеры кодов можно найти на MGNet
источник