Fedorenko-RP-Vvedenie-v-vychislitelnuyu-fiziku (810773), страница 9
Текст из файла (страница 9)
и()еи При численном решении задачи Пуассона возникает задача моделирования, аппроксимации указанного выше функционалъного пространства 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). Но как найти этот номер, не перебирая всех элементов? Здесь очень полезной может оказаться информация, возникающая (и сохраняемая в памяти ЭВМ) в том процессе генерирования триангуляции, который был описан выше. Просматривают все треугольники первичной, «ручной» триангуляции (а их немного) и определяют, в каком нз ннх находится точка (х, у), затем просматривают только четыре треугольника следующего уровня триангуляции, и т.д.
Но чтобы это можно было сделать, надо вырабатывать и сохранять соответствующую инфармацию (в виде некоторых таблиц), Задача вычисления и(х, у) является, как нетрудно понять, одной из типичных, наиболее массовых задач при содержательном истолковании решения, полученного методом конечных элементов в виде таблицы (и«) значений функции в узлах сетки.
Ведь нас интересует, что происходит в той или иной точке именно исходного геометрического пространства (х, у). Выше были приведены характерные геометрические задачи, которые легко решаются, если мы имеем перед собой чертеж триангуляции, на котором около каждого узла указан его номер в, а в каждом треугольнике — его номер т. Алгоритмизация, т.е. перевод этих «интуитивно» очевидных способов решения на чисто цифровой способ задания и обработки информации, — увлекательное и часто очень непростое занятие, особенно если строятся не просто принципиально верные алгоритмы, а, например, оптимальные по числу операций.
Реализация метода конечных элементов, не содержащая на первый взгляд серьезных трудностей, в действительности требует решения большого числа вспомогательных задач (некоторые из них были указаны выше). Кроме того, метод конечных элементов требует и достаточно больших объемов оперативной памяти ЭВМ. Этим в известной мере объясняется тот факт, что развитие и широкое внедрение в расчетную практику метода конечных элементов произошло в США, хотя основополагающие теоретические работы в этой области принадлежат чешскому математику М.
Зламалу. основы вычислительной мьтемлтики Некоторые сведения о полиномах Чебышева. Как зто принято в теории аппрокзимацин, будем рассматривать стандартный интервал изменения независимого переменного ( — 1, 1]. Полиномом Чебышева, или полнномом наименее уклоняющимся от нуля, степени р называют полипом, реализующий шгп (шах ]Т (!)]). -гага! Здесь пйп берется по всем полиномам степени р, нормированным условием: козффициент при ГР равен единице.