Федоренко Р.П. Введение в вычислительную физику (Федоренко Р.П. Введение в вычислительную физику.djvu), страница 9
Описание файла
DJVU-файл из архива "Федоренко Р.П. Введение в вычислительную физику.djvu", который расположен в категории "". Всё это находится в предмете "компьютерный практикум по специальности" из 11 семестр (3 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр DJVU-файла онлайн
Распознанный текст из DJVU-файла, 9 - страница
Кроме того, функция и должна принимать заданные значения (для простоты, и = 0) на границе области. В такой постановке решение следовало бы искать в классе 1К дважды непрерывно-дифференцируеммх функций. Однако в этом слиппсом узком пространстве решение задачи не всегда существует. решения, называемые склассическими» (т.е.
имеющие непрерывные те производные, которые входят в уравнение, и удовлетворяющие уравнению в прямом смысле слова), существуют при ограничениях на правую часть, слишком стеснительных для практики и часто не вююлняющихся. Приемлемым оказалось следующее расширение И~, при котором сама задача трансформировалась в вариационную: найти функцию и(х, у), непрерывную и имеющую кусочно-непрерывные первые производные, из условия ш1п ~ ~ (и~ + и~' — 2~и) с(х а1у. и()еи При численном решении задачи Пуассона возникает задача моделирования, аппроксимации указанного выше функционалъного пространства 1К. На ней мы и продемонстрируем важную в вычислительных.
методах технику интерполяции конечными элементами. Построим сначала триангуляцию области О, т.е. покроем ее сетью треугольников„каждые два из которых либо совсем не пересекаются, либо имеют только одну общую вершину, либо — общую сторону. Можно говорить, что б покрыта сеткой точек, каждая из которых находится только в вершине упоминавшихся выше треугольников (рис. 5). Построение триангуляции — не такая уж простая задача, особенно при большом числе узлов сетки. Выполнение Рис. 5 этой работы вручную иногда становит- ся просто непосильным: ведь в современных расчетах число узлов достигает тысяч, десятков тысяч. А если иметь в виду «триангуляцию» трехмерной области (покрытие ее сетью тетраэдров), работа становится почти невыполнимой.
Поэтому процесс триангуляции нужно алгоритмизировать. Один из популярных алгоритмов состоит в следующем. Задается. (вручную) грубая триангуляция области, включающая сравнительно небольшое число треугольников. Кахщый треуголъник разбивает- нате»полянка «тнхиий йз1 ся на четыре: к имевшимся ранее вершинам треугольников добавляются точки на серединах сторон начальных треугольников.
Этот процесс повторяется, и после нескольких таких «циялов» получается достаточно густая сетка, область триангулнрована достаточно мелкими треугольниками. Заметим, что некоторые треугольники могут быть и криволинейными, но конечная триангуляция состоит только из обычных треугольников. Это, конечно, приводит к триангуляции не исходной области т, а некоторой ее аппроксимации.
На рис, 5 показан процесс построения триангуляции (линии, возникающие на разных его этапах, имеют разные обозначения), Рассмотрим один нз треугольников и сеточную функцию, определенную в его вершинах, занумерованных индексами (1, 2, 3). Сеточная функция — это три числа и„и, и . Теперь решим задачу «интерполяции» такой функции, т.е. построим функцию, определенную внутри треугольника.
Построим в нем интерполяционный базис из трех функций р,(х, у), рг(х, у), рз(х, у), линейных по х и у, равных единице в «своей» вершине треугольника и нулю в остальных двух. Тогда интерполяция внутри треугольника выполняется по очевидной формуле з и(х, у) = х ~из рз(х, у).
(13) Пусть (и«)'„~„, — сеточная функция, определенная во всех узлах триангуляции. Используя в каждом треугольнике интерполяцию (13), получаем в б функцию и(х, у). Она, очевидно, непрерывна и имеет кусочно-непрерывные (а точнее, кусочно-постоянные) нервые производные. Каждый треугольник, оснащенный своим базисом, называют конечным элементом. Технически оказывается удобнее задавать конечные элементы в виде стандартного треугольника в плоскости параметров Д, т1) с вершинами в точках (О, 0), (1, 0), (О, 1), оснащенного стандартным базисом нз функций Фз(ч' т1) 1 «т)' Фг(«' т)) «' Фз(ь т1) т1 Для конкретного треугольника с вершинами (х,, у,), (хг, уг), (х, уз) легко построить линейное отображение его в стандартный треугольник: а, + апх+ азгУ т1 = иг+ игзх+ аггУ и обратное к нему.
Легко вычисляются, например, производные интерполированной функции: — = — — + — л=(и — и ) а +(и — и ) а а« а« аВ а« а ах аЕ ах а« ах г з н з з ги 1ч.и ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ 44 Они используютси при решении задач Пуассона. Интегрирование по элементарному треугольнику сводится к интегрированию по стандартному треугольнику (в плоскости (Т„4))) с последующим умножением на определитель преобразования (постоянный в силу линейности отображения). Таким образом, конечные элементы позволили построить некоторое подпространство из того пространства И~ (непрерывных функций с кусочно-непрерывными производными), в котором имеется решение задачи.
Этот аппарат оказался очень удобным для решения задач в областях ие слишком простых форм, Он составляет основу одного из самых гибких алгоритмов решения задач математической физики — метода конечных элементов (МКЭ). Обобщения метода конечных элементов связаны с решением не таких уж простых задач. В некоторых задачах (для бигармонического уравнения, например) естественным пространством 1т', которое следует аппроксимировать для приближенного решения, является пространство непрерывных функций с непрерывными первыми и кусочно-непрерывными вторыми производными.
Процедура гладкого восполнения внутри отдельною треугольника должна быть такой, чтобы совпадали не только проинтерполироваиные в двух соседних треугольниках функции на общей границе, но и их первые произВодные. В некоторых задачах (гидродинамика несжимаемой жидкости) желательно построить аппарат интерполяции вектор-функции с нулевой дивергенцией, и т.п. Построение таких «элементов» ценится в науке настолько, что им присваивают имена их конструкторов (элемент Оргириса и т.д.). Необходимо подчеркнуть, что работа с конечными элементами требует решения ряда достаточно сложных алгоритмических проблем.
Многие вещи, о которых так легко было юворить, ссылаясь на геометрическую картинку (см. рис. 5), не так-то просто реализовать в ЭВМ. В самом деле, пусть задана последовательность координат всех точек сетки (х„, у„)'„", (не следует забывать, что Ф могут быть порядка 1Оз, 104, а иногда !04). Зта информация полностью определяет сетку. Но попробуйте решить такую задачу.
Составьте группы по три точки, образующие все элементы триангуляции. Не сомневаюсь, что каждый справится с этой работой, но каков будет объем вычислений? Поэтому работать с такой «минимальной» информацией практически невозможно. В процессе формирования триангуляции необходимо формировать и дополнительную, избыточную информацию, позволяющую быстро решать те задачи, которые возникают при реализации метода конечных элементов. Например, можно сформировать последовательность троек чисел (т, „; т „; т „) номеров точек сетки, образующих вершины т-го элемента.
Допустим, такая информационная таблица уже есть. Попробуйте с ее помощью решить следующую за- интзшоляция «гнкний дачу. Пусть задан номер л одной из точек сетки. Найдите номера й элементов, одной нз вершин которых является .точка (х„, у„); в некоторых случаях желательно, чтобы эти номера были расположены в порядке следования элементов при обходе и-го узла по часовой, например, стрелке. Нетрудно понять, что если такая задача относится к числу «массовых» (решаемых многократно) при реализации метода конечных элементов, имеет смысл решить ее один раз и запасти в памяти ЭВМ соответствующую таблицу, Пусть и эта информация уже есть, Попробуйте решить такую задачу.
Дана точка (х, у) в области б, даны значения (и«) функции в узлах сетки. Вычислите и(х, у). Иными словами, нужно найти номер того элемента, внутрь которого попала точка (х, у), и воспользоваться формулой интерполяции (13). Но как найти этот номер, не перебирая всех элементов? Здесь очень полезной может оказаться информация, возникающая (и сохраняемая в памяти ЭВМ) в том процессе генерирования триангуляции, который был описан выше. Просматривают все треугольники первичной, «ручной» триангуляции (а их немного) и определяют, в каком нз ннх находится точка (х, у), затем просматривают только четыре треугольника следующего уровня триангуляции, и т.д.