Fedorenko-RP-Vvedenie-v-vychislitelnuyu-fiziku (810773), страница 34
Текст из файла (страница 34)
После этого очередная серия простых итераций с т== 0.2лз эффективно гасит невязку. Причина именно такой структуры г разъясняется ниже. Итак, основная идея коррекции с помощью вспомогательной сетки состоит в том, что невязка из подпространства гладких сеточиык функций «перегоняется» в подпространство негладких сеточных функций, где эффективно работает метод простой итерации.
Вернемся к вопросу о том, как решать задачу на вспомогательной Н.сетке, ведь она немногим проще исходной. Ответ очевиден: для этого надо использовать свою 2Н-сепсу, для нее — 4Н-сетку, и т.д. до тех пор, пока число узлов иа очерщной вспомогательной сетке не станет совсем уж незначительным. Однако окупит ли эффект ускорения сходимости затраты на вспомогательные вычисления? Ответ на этот вопрос не очевиден, он требует проведения сложных и достаточно аккуратных оценок.
Такие оценки были проделаны и было доказано (сначала' для задачи Пуассона в прямоугольнике, затем для гораздо более общих и сложных эллиптических задач), что норма невязки убывает со скоростью, не зависящей от шага сетки, т.е. необходимое для ее уменьшения в е ' раз число арифметических операций есть СНз1п е ' (С не зависит от Ф). Это асимптотически рекордный результат. При достаточно большом Ф описанные выше (и в сущности все остальные известные сейчас) методы уступают многосеточному. Однако постоянная С в этой оценке вычисляется настолько грубо, что лучше считать ее неизвестной. Могло бы оказаться, что преимущество многосеточного метода по сравнению, например, с методом переменных направлений наступает при сюль больших Н, какие на практике ие используются.
Такие вопросы выясняются путем вычислительного эксперимента. Мнопэчисленные реализации многосеточного метода и результаты вычислений показали, что метод оказывается эффективным уже на тех сравнительно скромных сетках (Н порядка 50, 100), которые давно используются в практических расчегах. Приведем для иллюстрации табл.
11, в которой показаны результаты вычислительного эксперимента по решению некоторых уравнений многосеточным методом. Основная сетка имела 103 х 108 узлов„ первая вспомогательная (Н= Зл) — Збх36, вторая — 12х12. В табл, 11 показаны вид аппроксимируемого оператора, шаблон аппроксимации, и — число итераций, затрачиваемых на сглаживание иевязки, предшествующее обращению к вспомогательной задаче, и, наконец, средняя скорость убывания невязки с номером итерации 1. Прн этом 1 — это число итераций на основной сетке 108 х 103, включая время работы, затрачиваемое на решение вспомогательных 177 й 141 гвшвннв эллиптичгских злдлч мвгодом сеток задач (в единицах, равных времени на одну итерацию на основной сетке).
В дальнейшем многосеточный метод был усовершенствован. Усовершенствования касались таких деталей, как способ вычисления невязки Я на Н-сетке через невязку г на Ь-сетке, форма основных итераций, методы интерполяции с гг= на л-сетку, и некоторых других. Все эти технические усовершенствования сделали алгоритм одним из наиболее эффективных, выдерживающих конкуренцию даже с некоторыми узкоспециализированными, применимыми только к задаче Пуассона (уравнение с постоянными коэффициентами Ьи = г') в квадрате, Замечательным оказался тот факт, что и алгоритм метода, н теорема о независимости скорости сходнмости от шага сетки, выдержали обобщения прн усложнении задачи за счет переменности коэффициентов, произвольного вида области и т.п.
Однако наибольшая популярность и широта применения метода в настоящее время связаны с его приложением к такому мощному средству решения эллиптических задач, как метод конечных элементов. Основные идеи этого способа построения аппроксимирующей конечномерной задачи были изложены в з 3. Напомним, что характерной особенностью системы линейных алгебраических уравнений, аппроксимирующих, например, задачу Пуассона в достаточно произвольной области, являются высокий порядок системы (достнгающий в современных расчетах 1Π—: 10 ) и слабая заполненность матрицы.
(Эти черты присущи и системам метода конечных разностей в прямоугольной области.) Следующее свойство специфично для метода конечных элементов. Расположение ненулевых элементов в матрице системы не имеет такой простой и удобной структуры, с которой мы до сих пор имели дело, применяя метод сеток в простых областях. Это делает невозможным применение наиболее эффективных итерационных методов (переменных направлений, например). Пожалуй, единственный из знакомых нам методов, который в такой ситуации может быть использован, — это метод простой итерации с чебышевским ускорением.
Но его эффективность недостаточна для решения сложных задач, поэтому в методе конечных элементов обычно используются «ленточные» варианты метода исключения Гаусса, что всетаки является довольно дорогой операцией, часто вынуждающей ограничиваться расчетами на относительно грубых сетках. При описании основных идей метода конечных элементов специально было обращено внимание на процедуру автоматической триангуляции «произвольной» области, при которой возникает иерархическая структура вложенных друг в друга сеток. Она позволяет удобно реализовать алгоритм многосеточных итераций.
Комбинация техники метода конечных элементов с многосеточным итерационным алгоритмом привела к созданию мощных основы вычнслитвльноя млтемлтики 1?з средств вычислений, Надо отметить, что логическая структура метода заметно сложнее, чем структура методов, описанных выше. Это приводит к определенным трудностям в программной реализации. Поэтому в простых задачах обычно предпочитают более простые с точки зрения программирования методы, хотя они работают медленнее. Формирование задач на вспомогательных сетках. Рассмотрим две сетки — основную и первую вспомогательную, которую назовем грубой. В современной практике приходится строить грубую сетку, учитывая геометрию области, разрывы коэффициентов н т.п.
Все это приводит к тому, что грубая сетка не имеет такой простой связи с основной, как было описано выше. Например, грубая сетка может формироваться так: задается список номеров основной сетки йп т'-й узел грубой сетки совпадает с х,-м узлом основной. Имеется в виду сетка по переменной х. Аналогично, списком т, определяется сетка по у. Таким образом узел (1, у) грубой сетки совпадает с узлом (й„ту) основной. Числа йп естественно, возрастают, и все разности й;+, — й,- достаточно малы, в остальном они произвольны. Возможны и более сложные способы построения грубой сетки.
В таких ситуациях возникает вопрос: как строить аппроксимацию на грубой сетке? Он еще более обостряется, если коэффициенты уравнения достаточно сильно отличаются даже в близких узлах основной сетки, т.е. если решается уравнение с разрывными коэффициентами. Пусть на основной сетке получено приближение и с гладкой повязкой г Ьи-г' (здесь А — оператор на основной сетке, аппроксимирующий произвольный эллиптический, а не обязательно оператор Лапласа). Определим грубую сетку и оператор !, интерпаеирующий функцию, заданную на грубой сетке, на основную сетку. Попытаемся найти на грубой сетке такую функцию И', чтобы получить Ь(и — ЛР) †У. Очевидно, это невозможно, так как уравнений здесь столько, сколько внутренних узлов на основной сетке, а неизвестных И' столько, сколько внутренних узлов на грубой сетке (функция $% должна удовлетворять однородным краевым условиям исходной задачи, чтобм коррекция и — ЛР не портила краевые условия).
Однако это уравнение можно решить в «слабом», галеркинском, смысле: О = (А(и — Л ) — У, т) = (?" г — К'Л? И, ~), Ч1 илн в явной форме — в виде уравнения для Иг: Р$Г=Я, где Р=1'Ы, Я=1 г. 179 е г41 гешение эллиптических злдАч методом сеток Таким образом все определяется только конструкцией оператора интерполяции с грубой сетки на основную 1. Что представляет собой оператор 1*, сопряженный к оператору интерполяции? Он отображает функции, определенные на основной сетке, в функции, определенные на грубой сетке.