Квазирешетки в прикладных задачах обработки цифровой информации
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
е использованных источников содержатся литературные источников, которые были применены в процессе изучения и разработки алгоритма, в составе которых присутствуют как и литературные издания, научные статьи так и ссылки на интернет источники.
В заключении подведены итоги разработки и проведена оценка успешности разработанного алгоритма.
В приложении содержится листинг расчетных программ.
1. РЕШЕТКИ И ИХ СВОЙСТВА
1.1Основы теории сеточных методов
Возьмем ограниченную область D из Rn с границей ?D. Где Rn евклидово пространство n-мерных вещественных векторов. Разобьем пространство Rn на элементарные ячейки {x?(x1, x2,…,xn): kihi0. Величина hi по переменной xi, называется шагом сетки. Если hi=const, то сетка по xi называется равномерной. Величина hi называется шагом сетки. Пусть - объединение элементарных ячеек (включая их границы). Положим, что , а граница области . Тогда множество вершин ячеек принадлежащих так же обозначим символом и назовем его сеткой области , а вершины - узлами сетки. Внутренними узлами сетки, будем называть вершины ячеек принадлежащие области D. В таком случае граничные узлы составляют множество и обозначаются .
В узлах сеток , , можно определить некоторые функции. Функции, область определения которых является сетка, назовем сеточными функциями и обозначим их как ,,… Тогда значения сеточной функции в узлах , где , или т. е. .
На рисунке 1. и 2 представлены некоторые варианты сеток
Рисунок 1. 1 - Функция одной переменной Ф, заданная на структурированной сетке {xk}
Рисунок 1. 2 - Функция двух переменных Ф, заданная на структурированной сетке {xk}
Расчетные сетки используют при численном решении дифференциальных и интегральных уравнений.
Качество построения расчетной сетки в значительной степени определяет успех (неудачу) численного решения уравнения.
Задача построения расчетной сетки заключается в нахождении отображения которое переводит узлы сетки из физической области в вычислительную. Такое отображение должно удовлетворять нескольким условиям:
?отображение должно быть однозначным;
?узлы сетки должны сгущаться в области предполагаемой появление больших градиентов;
?линии должны быть гладкими для обеспечения области непрерывных производных.
Процедуру построения расчетной сетки можно рассматривать как построение взаимно-однозначного отображения области определения функции (физической области) на некоторую расчетную область, имеющую более простую форму.
Множество сеточных функций , определенных на , обозначим . На этом множестве можно ввести скалярное произведение и норму, превратив тем самым в конечномерное гильбертово пространство сеточных функций. Примером такого пространства является пространство , состоящее из вещественных сеточных функций определенных на . Скалярное произведение и норму в можно задать в виде:
,
,
где суммирование осуществляется по индексам, соответствующим узлам сетки . Однако можно превратить и в конечномерное банахово пространство, если ввести на норму, которая не порождается скалярным произведением. Примером банахова пространства является пространство с нормой .
Аналогично тому, как это сделано для случая , вводятся соответствующие пространства сеточных функций на и .
Пусть Ф есть линейное множество функций , определенных на. Считаем, что эти функции обладают определенной степенью гладкости и имеет смысл рассматривать их значения в узлах сетки . Тогда каждой функции можно поставить в соответствие сеточную функцию, которую обозначим по следующему правилу: значение в узле равно . Указанное соответствие задает линейный оператор , область определения которого есть , а область значений принадлежит . Этот оператор назовем оператором проектирования функций на сетку . Таким образом, имеем: , . Заметим, что оператор проектирования можно вводить различными способами. Так, другим оператором проектирования будет оператор, который каждой функции ставит в соответствие сеточную функцию , значения которой в узле есть
среднее значение в этом узле. Легко заметить, что оператор отличается от введенного ранее оператора : область его определения может быть значительно расширена и может включать функции , для которых .
Если предположить, что функции достаточно гладкие, то, применяя простейшие квадратурные формулы, несложно показать, что при . Нормы , , для которых имеем при , называют согласованными. Использование именно согласованных норм нередко оказывается важным моментом при исследовании различных вопросов теории конечно-разностных методов.
Подобно тому, как это сделано выше, можно осуществить проектирование функций (определенных на ) на и , ввести соответствующие операторы проектирования.
Пусть, далее, А - линейный оператор, заданный на функциях . Тогда функцию также можно спроектировать на сетку , положив . Если на определена функция (где а есть линейный оператор - оператор граничного условия), то также можно осуществить проектирование на , получая при этом сеточную функцию , определенную на [1].
Отмеченные выше проектирования функций на соответствующие сетки широко используются при построении конечно-разностных аналогов уравнений ( в D; на ?D и др.). Методы построения, а также вопросы аппроксимации, счетной устойчивости и сходимости приближенных решений задачи к решению точ?/p>