Квазирешетки в прикладных задачах обработки цифровой информации

дипломная работа

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), имеющих ограниченные четвертые производные.

Делись добром ;)