Квазирешетки в прикладных задачах обработки цифровой информации
1.1 Основы теории сеточных методов
Возьмем ограниченную область D из Rn с границей ?D. Где Rn евклидово пространство n-мерных вещественных векторов. Разобьем пространство Rn на элементарные ячейки {x?(x1, x2,…,xn): kihi<xi<(ki+1)hi, i=1, 2, …, n}, где ki - целые числа, hi=const>0. Величина hi по переменной xi, называется шагом сетки. Если hi=const, то сетка по xi называется равномерной. Величина hi называется шагом сетки. Пусть - объединение элементарных ячеек (включая их границы). Положим, что , а граница области . Тогда множество вершин ячеек принадлежащих так же обозначим символом и назовем его сеткой области , а вершины - узлами сетки. Внутренними узлами сетки, будем называть вершины ячеек принадлежащие области D. В таком случае граничные узлы составляют множество и обозначаются .
В узлах сеток , , можно определить некоторые функции. Функции, область определения которых является сетка, назовем сеточными функциями и обозначим их как ,,… Тогда значения сеточной функции в узлах , где , или т. е. .
На рисунке 1. и 2 представлены некоторые варианты сеток
Рисунок 1. 1 - Функция одной переменной Ф, заданная на структурированной сетке {xk}
Рисунок 1. 2 - Функция двух переменных Ф, заданная на структурированной сетке {xk}
Расчетные сетки используют при численном решении дифференциальных и интегральных уравнений.
Качество построения расчетной сетки в значительной степени определяет успех (неудачу) численного решения уравнения.
Задача построения расчетной сетки заключается в нахождении отображения которое переводит узлы сетки из физической области в вычислительную. Такое отображение должно удовлетворять нескольким условиям:
? отображение должно быть однозначным;
? узлы сетки должны сгущаться в области предполагаемой появление больших градиентов;
? линии должны быть гладкими для обеспечения области непрерывных производных.
Процедуру построения расчетной сетки можно рассматривать как построение взаимно-однозначного отображения области определения функции (физической области) на некоторую расчетную область, имеющую более простую форму.
Множество сеточных функций , определенных на , обозначим . На этом множестве можно ввести скалярное произведение и норму, превратив тем самым в конечномерное гильбертово пространство сеточных функций. Примером такого пространства является пространство , состоящее из вещественных сеточных функций определенных на . Скалярное произведение и норму в можно задать в виде:
,
,
где суммирование осуществляется по индексам, соответствующим узлам сетки . Однако можно превратить и в конечномерное банахово пространство, если ввести на норму, которая не порождается скалярным произведением. Примером банахова пространства является пространство с нормой .
Аналогично тому, как это сделано для случая , вводятся соответствующие пространства сеточных функций на и .
Пусть Ф есть линейное множество функций , определенных на. Считаем, что эти функции обладают определенной степенью гладкости и имеет смысл рассматривать их значения в узлах сетки . Тогда каждой функции можно поставить в соответствие сеточную функцию, которую обозначим по следующему правилу: значение в узле равно . Указанное соответствие задает линейный оператор , область определения которого есть , а область значений принадлежит . Этот оператор назовем оператором проектирования функций на сетку . Таким образом, имеем: , . Заметим, что оператор проектирования можно вводить различными способами. Так, другим оператором проектирования будет оператор, который каждой функции ставит в соответствие сеточную функцию , значения которой в узле есть
- среднее значение в этом узле. Легко заметить, что оператор отличается от введенного ранее оператора : область его определения может быть значительно расширена и может включать функции , для которых .
Если предположить, что функции достаточно гладкие, то, применяя простейшие квадратурные формулы, несложно показать, что при . Нормы , , для которых имеем при , называют согласованными. Использование именно согласованных норм нередко оказывается важным моментом при исследовании различных вопросов теории конечно-разностных методов.
Подобно тому, как это сделано выше, можно осуществить проектирование функций (определенных на ) на и , ввести соответствующие операторы проектирования.
Пусть, далее, А -- линейный оператор, заданный на функциях . Тогда функцию также можно спроектировать на сетку , положив . Если на определена функция (где а есть линейный оператор - оператор граничного условия), то также можно осуществить проектирование на , получая при этом сеточную функцию , определенную на [1].
Отмеченные выше проектирования функций на соответствующие сетки широко используются при построении конечно-разностных аналогов уравнений ( в D; на ?D и др.). Методы построения, а также вопросы аппроксимации, счетной устойчивости и сходимости приближенных решений задачи к решению точной будут рассматриваться ниже.
Рассмотрим некоторую задачу математической физики в операторной форме:
в D,
на ?D, (1.1)
где А - линейный оператор, , . В данном случае Ф и F - гильбертовы пространства с областями определения элементов в и соответственно, а - линейный оператор граничного условия, , где G - гильбертово пространство функций с областью определения .
Наряду с уравнением (1.1) рассмотрим уравнение в конечномерном пространстве сеточных функций
в ,
на , (1.2)
где Ah - линейный оператор, зависящий от шага сетки h, , а - пространства сеточных функций. Здесь - множество внутренних узловых точек области D, a -- множество узловых точек, на которых аппроксимируется граничное условие задачи, - линейный оператор, , евклидово пространство сеточных векторов с областью определения .
Введем в сеточных пространствах , G, , соответственно нормы , . Пусть -- линейный оператор, который элементу ставит в соответствие элемент так, что . При таких условиях, задача (1.2) аппроксимирует задачу (1.1) с порядком n на решении ц, если существуют положительные константы , такие, что для всех выполняются неравенства
(1.3)
.
В тех случаях, когда решение ц задачи (1.1) обладает достаточной гладкостью, порядок аппроксимации удобно находить с помощью нормы, естественной для пространства непрерывных и дифференцируемых функций. С этой целью обычно пользуются разложением решения и других функций, участвующих в задаче, в ряды Тейлора.
В дальнейшем будем полагать, что редукция задачи (1.1) к задаче (1.2) осуществлена и, более того, граничное условие из (1.2) использовано для исключения значений решениями граничных точках области . В результате приходим к эквивалентной задаче
(1.4)
При этом значения решения в граничных точках найдутся из уравнения (1.2) после того, как будет построено решение уравнения (1.4). В некоторых случаях удобно пользоваться записью аппроксимационной задачи в форме (1.4), а в некоторых - в форме (1.2). Итак, в результате проведенной редукции и с учетом требуемой аппроксимации задача с непрерывным аргументом (1.1) приводится к задаче линейной алгебры (1.4), заключающейся в решении системы алгебраических уравнений.
В дальнейшем в основном будут использоваться гильбертовы пространства сеточных функций и соответствующая норма будет определяться (если не оговорено особо) соотношением . Однако необходимо отметить, что многие из вводимых понятий (аппроксимация и т. д.) можно перенести на случай банаховых.
Рассмотрим задачу:
в D, на ?D (1.5)
Положим, что областью определения D является множество {(х, у): 0 < x < 1, 0 < y < 1}, а f -- гладкая функция.
Квадрат покроем равномерной по х и по у сеткой с шагом h. Узлы области будем отмечать двумя индексами (k, l), где первый индекс k (0 ? k ? n) соответствует точкам деления по координате x, а второй индекс l (0 ? l ? n) -- по у. Рассмотрим следующие аппроксимации:
где , , , - разностные операторы, определенные как
,
где - разностный оператор Лапласа. Если расписать более подробно, то получим следующие выражения:
Тогда задача (1.5) может быть аппроксимирована следующей функцией:
в ,
на , (1.6)
где - множество узлов, принадлежащих границе. С учетом изложенного задача (1.6) может быть приведена к виду
в ,
на , (1.7)
где и - векторы с компонентами и и
В приведенных здесь схеме в качестве берется некоторое усреднение f(x, y), вычисленное по приведенной выше формуле. Это обстоятельство, вообще говоря, позволяет рассматривать разностные схемы при f(x, y), не обладающей предполагаемой в данном примере достаточной гладкостью. В последних случаях можно также получить соответствующие оценки ошибок аппроксимаций.
Введем в рассмотрение пространство решений . За область определения элементов из примем . Вектор принадлежит пространству Fh с областью определения . Разлагая решение по формуле Тейлора в окрестности точки и предполагая ограниченность производных по x и у вплоть до четвертого порядка, будем иметь
где - произвольная точка области
Аналогичное разложение будем иметь и для функции f(x, y). Введем в пространстве Fh норму
.
Аналогично вводится норма в пространстве Gh. В качестве возьмем вектор, компонентами которого являются значения функции в соответствующем узле сетки. Тогда, используя указанные выше разложения для и f получим
, (1.8)
где
.
Аппроксимация граничных условий в этом случае является точной.
Из последнего утверждения и оценки (1.8) следует, что задача (1.7) аппроксимирует задачу (1.5) со вторым порядком на решениях задачи (1.5), имеющих ограниченные четвертые производные.