Хакимзянов Чубаров Воронина печатные лекции часть 1 (973557), страница 5
Текст из файла (страница 5)
, N ), которое называется расчетной сеткой. Очевидно, чтосеточную функцию uj = u(xj , yj ) можно рассматривать как вектор(u1 , u2 , . . . , uN ) конечномерного пространства размерности N .Расчетная сетка является дискретным представлением области решения. Методам построения сеток для двумерных и трехмерных областей посвящено огромное количество научных статей, число которых стремительно растет и в настоящее время, поскольку нерешенныхпроблем здесь еще очень много [9, 10, 35, 37].
Широко применяютсяструктурированные (регулярные) сетки с четырехугольными ячейкамина плоскости (см. рис. 4, а) и шестигранными в пространстве. Регулярная сетка представляет собой упорядоченный по «сеточным направлениям» набор узлов. Широкое распространение на практике получилии неструктурированные (нерегулярные) сетки, особенностью которыхявляется произвольное расположение узлов сетки в области решения(см. рис. 4, б), произвольное в том смысле, что отсутствуют выраженные21yxаyxбРис.
4. Расчетные сетки: а — регулярная (структурированная);б — неструктурированнаясеточные направления и число ячеек, содержащих каждый конкретныйузел, может меняться от узла к узлу. Используются также гибридныесетки, объединяющие регулярные сетки в одних подобластях областирешения с нерегулярными в других. «Хорошая» сетка должна учитывать особенности решения, сгущаясь в окрестности этих особенностей,а при решении нестационарных задач являться еще и подвижной, адаптирующейся к подвижным особенностям решения [33, 34].Отметим, что в последнее время появились оригинальные вычислительные алгоритмы, для выполнения которых сетка не требуется. Ониполучили название бессеточных методов.Существует множество методов перехода от непрерывного представления математической модели к ее дискретному представлению: метод22конечных разностей, метод конечных объемов, метод конечных элементов, спектральные методы и др.
[11, 17, 23, 24, 30, 31, 32].Метод конечных разностей основан на замене производных, входящих в исходные уравнения, их дискретными (разностными) аналогамина структурированных сетках. Например, при дискретизации уравнения (1.8) методом конечных разностей на равномерной по времени сетке tj = jτ (j = 0, . . . , N ) с количеством узлов (N + 1) и шагом τ = T /Nполучается разностное уравнениеsj+1 − 2sj + sj−1= −ksj ,j = 1, . . . , N − 1(2.1)τ2относительно сеточной функции sj , являющейся на временно́м промежутке [0, T ] приближением для решения s(t) уравнения (1.8).В методе конечных объемов используется интегральная формулировка законов сохранения (1.4), которая записывается для совокупностиконтрольных объемов (обычно для ячеек как структурированных, таки неструктурированных сеток). Дискретный аналог законов сохраненияполучают путем вычисления всех входящих в формулировку интегралов по каким-либо квадратурным формулам.В методе конечных элементов искомое приближенное решение раскладывается по конечной системе финитных кусочно-полиномиальныхбазисных функций и требуется, чтобы невязка решения была ортогональна всем базисным функциям.
Таким образом, решение исходнойзадачи сводится к системе алгебраических уравнений (САУ), линейных (СЛАУ) или нелинейных (СНАУ) , относительно коэффициентовразложения. Построение базисных функций тесно связано с выбраннойрасчетной сеткой, вернее с ее ячейками, которые в этом методе называются конечными элементами. В качестве конечных элементов выступают отрезки в одномерной области, треугольники или четырехугольники в двумерной, тетраэдры или призмы в трехмерной.
Метод конечныхэлементов получил широкое распространение при выводе дискретныхмоделей в механике деформируемого твердого тела.Спектральные методы предполагают использование взаимно ортогональных базисных функций, не являющихся финитными. Искомоерешение раскладывается в ряд по этим функциям, и конечный отрезокэтого ряда подставляется в исходные уравнения.
В результате происходит полная алгебраизация исходной задачи, ее отображение в САУ дляопределения коэффициентов разложения. Для областей простой формы спектральный метод дает высокую точность даже при сравнительнонебольшом числе базисных функций.m23Заменив математическую модель дискретной, мы должны быть уверены в том, что при увеличении числа узлов (числа базисных функций)решение дискретной задачи приближается в некотором смысле к решению исходной задачи.
Близость этих решений во многом (но не полностью) определяется способом аппроксимации, «близостью» математической модели и аппроксимирующей ее дискретной модели. Строгиедоказательства аппроксимируемости непрерывной задачи ее дискретным представлением существуют лишь для ограниченного числа задач,линейных или квазилинейных.
Для большинства нелинейных задач таких теорем нет, и нет даже надежды, что они будут получены в обозримом будущем. Вследствие этого необходим очень тщательный и строгийконтроль свойств разрабатываемого алгоритма всеми доступными способами.Заметим, что некоторые задачи изначально формулируются в дискретной форме, например, в виде САУ относительно неизвестных величин (см.
§ 5 главы 2). Для таких задач этап перехода к дискретноймодели не нужен, поэтому после формулировки математической модели и ее исследования сразу приступают к разработке вычислительногоалгоритма.2.2. Точность алгоритма. После дискретизации исходной задачинадо построить вычислительный алгоритм, т. е. указать последовательность арифметических и логических действий, выполняемых на ЭВМи дающих за конечное число операций (шагов) решение дискретной задачи. Полученное решение принимается за приближенное решение исходной математической задачи.Как правило, для одной и той же дискретной модели можно предложить множество вычислительных алгоритмов.
И это обстоятельство неможет не настораживать, ибо довольно очевидно, что среди большогоразнообразия алгоритмов не все одинаковы по своим качествам. Естьалгоритмы «хорошие» и «плохие», и нужно уметь отличать одни от других, причем делать это, не тратя времени и труда на программированиеи расчеты, а заранее, априори. А для этого нужно сформулировать критерии для оценки качества вычислительных алгоритмов.Основное требование, предъявляемое к вычислительному алгоритму, это требование точности. Оно означает, что вычислительный алгоритм должен давать приближенное решение построенной или выбранной математической модели с заданной точностью ε > 0 за конечноечисло действий Q(ε). Алгоритм должен быть реализуемым, т. е.
давать24решение дискретной задачи за допустимое машинное время. Для почти всех алгоритмов время решения задачи возрастает при повышенииточности, т. е. при уменьшении ε.Решение дискретной задачи не совпадает с решением исходной, оноявляется приближенным решением, решением с погрешностью. Можновыделить две основные причины возникновения погрешности численного решения. Во-первых, при замене исходной задачи дискретной возникает погрешность дискретизации (аппроксимации). Например, заменяяв уравнении (1.8) производную s̈ разностной производной, фигурирующей в левой части разностного уравнения (2.1), мы допускаем погрешность дискретизации, имеющую при τ → 0 порядок τ 2 .
Второй видпогрешности — ошибки округления — связан с конечной разрядностьючисел, представляемых в ЭВМ. Ошибки округления могут существенноповлиять на точность приближенного решения и даже на саму возможность его вычисления на ЭВМ.2.3. Устойчивость алгоритма. При каждом вычислении на ЭВМпоявляются ошибки округления. В зависимости от алгоритма эти ошибки могут в процессе вычислений неограниченно нарастать, либо не накапливаться.
В первом случае алгоритм называют неустойчивым, вовтором — устойчивым. Например, если в некотором алгоритме вычисляются члены геометрической прогрессии bn+1 = bn q (n = 1, 2, . . . ) сознаменателем q > 1 и при вычислении первого члена была допущенаошибка δ, т. е. вместо b1 было получено значение b1 = b1 + δ, то этаошибка скажется и при вычислении bn+1 : вместо истинного значениямы получим значение bn+1 = b1 q n = bn+1 + δ · q n , отличающееся отbn+1 накопленной погрешностью δ · q n , которая быстро возрастает приn → ∞.Другой пример.
С точки зрения теоретической математики конструктивность теоремы о существовании и единственности решения СЛАУ,основанной на правиле Крамера, неоспорима. Однако алгоритм, основанный на формулах Крамера, не обладает устойчивостью при егоиспользовании для вычислений на ЭВМ. Кроме того, для него не выполняется требование получения решения за разумное количество операций (для вычисления определителей требуется порядка N ! действий,где N — число неизвестных). Поэтому для поиска решения СЛАУ наЭВМ применяются другие — устойчивые алгоритмы, основанные наметодах исключения и итерационных методах. Известны и иные алгоритмы, эффективные с теоретической точки зрения, но неприемлемыес точки зрения машинной арифметики.252.4.
Экономичность алгоритма. Естественно добиваться, чтобычисло действий Q(ε) (и тем самым машинное время решения задачи)было минимально. Для любой задачи можно предложить много алгоритмов. При их использовании одинаковая точность ε может достигаться за разное число действий. Предположим, что решение дискретной задачи является вектором (u1 , u2 , . . . , uN ) конечномерного пространстваразмерности N .
Если число арифметических действий для нахождения одной компоненты решения «слабо» зависит или вообще не зависитот общего числа неизвестных, то алгоритм называется экономичным.Таким образом, экономичный алгоритм требует выполнения числа действий, пропорционального размерности N конечномерного пространства, которому принадлежит решение дискретной задачи. Следовательно, алгоритм Крамера не относится к классу экономичных (требуетсяпорядка N ! действий), как и метод исключения Гаусса в общем случае(≈ N 3 действий), а вот знакомый вам метод прогонки является экономичным (число действий пропорционально N ).2.5.
Параллелизуемость алгоритма. Желательно, чтобы вычислительный алгоритм наряду с упомянутыми характеристиками, такими, как точность, устойчивость, экономичность, обладал и свойствомпараллелизуемости, т. е. позволял распараллеливать себя. Возможностьсегментации сложного вычислительно процесса на значительное числопростых и относительно независимых процессов, время от времени обменивающихся между собой входными и выходными данными, открывает путь к конструированию компьютерных программ параллельногосчета [5]. Разумеется, при этом возникают дополнительные проблемы,связанные с большими потоками информации между процессами.Если сложный алгоритм удается представить в виде ряда хорошоизученных и надежных алгоритмов решения простых задач, то такиеэлементарные алгоритмы называются вычислительными модулями,а сама процедура выделения модулей — модульным анализом алгоритма [15]. Проведя модульный анализ алгоритма, мы получаем возможность рассматривать сложный алгоритм как последовательное выполнение относительно простых вычислительных модулей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
