Решение задачи об оптимальной интерполяции с помощью дискретного преобразования Фурье (ДПФ)

Предложенная мне тема ВлРешение задачи об оптимальной интерполяции с помощью дискретного преобразования Фурье (ДПФ)В» написана на основе книги В. Н. Малоземова и С. М. Машарского ВлОсновы дискретного гармонического анализаВ». Дискретный гармонический анализ тАУ это математическая дисциплина, результаты которой активно используются в цифровой обработке сигналов. По ходу изучения книги возникли новые задачи, две из которых приведены в разделе ВлРешения задачВ». В данной работе также сравнивается ДПФ с непрерывным преобразованием Фурье. В приложениях в случае классического преобразования приходится приближенно заменят интегралы некоторыми суммами. При этом основная трудность связана с необходимостью оценки погрешности на каждом из последующих этапов. ДПФ тем выгоднее и отличаются, что здесь с самого начала вместо интегралов имеем дело с суммами. При этом основные цели использования ДПФ также достигаются.

Рассматриваются различные преобразования - периодических векторов, среди которых центральную роль играет ДПФ. Задача об оптимальной интерполяции является приложением ДПФ.

Отдельные задачи в рамках дипломной работы мне решить не удалось. Они не вошли в дипломную работу.

Основная работа свелась к изложению основных фактов с подробными доказательствами. В начале дипломной работы имеется раздел ВлВспомогательный материалВ», в котором кратко изложены факты, необходимые для чтения основного текста. Эти факты хорошо известны и касаются тех понятий и терминов, которые встречаются в теории чисел, в теории линейных комплексных пространств и в линейной алгебре. Все эти понятия используются для получения более важных результатов в последующих параграфах.

Далее вводится пространство - периодических векторов Ваи устанавливается тот факт, что - линейное комплексное пространство.

Над элементами этого пространства определяются прямое и обратное ДПФ.

Решены задачи, составлена и апробирована программа, которая реализует оптимальную интерполяцию. Также составлены программы, которые вычисляют свертку двух периодических векторов и ДПФ.

При решении задачи оптимальной интерполяции сначала переходим к новым переменным с помощью ДПФ. Далее полеченную задачу решаем методом множителей Лагранжа. И, наконец, переходим к исходным переменным с помощью формулы обращения.

Вз 1. Вспомогательный материал

В данной работе используются следующие обозначения:

Z, R, C тАУ множества целых, действительных и комплексных чисел соответственно;

m : n тАУ множество последовательных целых чисел {m, m+1, тАж , n}.

1.Корни из единицы. Допустим тАУ натуральное число, . Введём комплексное число

Ва(1)

По формуле Муавра при натуральном k получаем

Ва(2)

В частности, ВаЧисло Ваназывается корнем тАУ й степени из единицы.

Формула (2) верна при k=0. Покажем, что она верна и при целых отрицательных степенях . Действительно,

Значит, получили, что формула (2) справедлива при всех

Отметим, что Ваи Вапри натуральном . Из (2) и свойств тригонометрических функций следует также, что при всех целых Ваи

Применяя формулу Эйлера, имеем

2.Комплексное унитарное пространство. Будем говорить, что в комплексном линейном пространстве определено скалярное умножение, если всякой паре векторов a, b поставлено в соответствие число, обозначаемое символом (a, b) и называемое скалярным произведением векторов a и b. Причём (a, b) будет, вообще говоря, комплексным числом.

При этом должны выполнятся аксиомы:

1., где черта обозначает, как обычно, переход к сопряжённому комплексному числу;

4.Если а ≠ 0, то скалярный квадрат вектора а строго положителен, т.е.

(а. а) > 0, а если (а, а) = 0, то а = 0.

Комплексное линейное пространство называется унитарным пространством, если в нём задано скалярное умножение.

Векторы а и b называются ортогональными, если их скалярное произведение равно нулю

(а, b) = 0.

Система векторов называется ортогональной системой, если все векторы этой системы попарно ортогональны.

Назовём вектор b нормированным, если его скалярный квадрат равен единице

(b, b) = 1.

При этом, если Ва- ортонормированная база и векторы а, b

имеют в этом базе записи

а = , , то .

Также имеем равенство

Ва(3)

3.Вычеты. Пусть и ВатАУ натуральное число. Существует единственное целое число , такое, что

Ва(4)

Оно называется целой частью дроби Ваи обозначается

Разность Ваназывается вычетом Вапо модулю Ваи обозначается .

Нетрудно показать, что

. (5)

Действительно, умножим неравенства (4) на Ваи вычтем .

Получим , что равносильно (5).

4.Функции комплексного переменного. На плоскостях комплексных переменных z и w рассмотрим соответственно множества Ваи .

Если указан закон f, по котором каждому значению Васопоставляется единственное значение , то говорят, что на множестве Е определена однозначная функция комплексного переменного z и пишут w=f(z).

Функции определяются как суммы степенных рядов:

, , . (6)

Из этих равенств непосредственно можно получить следующие формулы Эйлера:

, , . (7)

5.Матрицы. Прямоугольная таблица чисел, записанная в виде

Ва(8)

называется матрицей.

Коротко матрицу обозначают так: , ;

где Ва- элемент данной матрицы, который находится в i-й строке и j-м столбце матрицы А.

Некоторые свойства матриц:

1. сумма С = А + В двух матриц А и В одного размера mn тАУ это матрица

С = (с), где с = a + b для всех i, j;

сумма матриц разных размеров не определяется.

2.Произведение С = λА матрицы А и элемента λС тАУ это матрица того же размера, что и А, причём при всех i, j.

3.Произведение С = АВ матрицы А размера mn и матрицы В размера np тАУ это матрица С размера mp такая, что

Произведение матриц в общем случае некоммутативно, т.е АВ≠ВА.

Транспонированная матрица Ва(по отношению к матрице А) тАУ такая матрица, что .

Совокупность элементов Ваквадратной матрицы Ваназывается главной диагональю матрицы.

Матрица, у которой элементы, стоящие на главной диагонали, равны единице, а все остальные элементы равны 0, называется единичной матрицей и обозначается буквой Е.

Напомним, что

АЕ = А и ЕА = А.

Матрица называется ортогональной, если строки образуют ортогональную систему векторов и норма каждой строки равна единице.

Квадратная матрица называется симметрической, если

6.Определители. Всякое расположение чисел 1, 2, тАж, n в некотором определённом порядке называется перестановкой из n чисел.

Говорят, что в данной перестановке числа i и j составляют инверсию, если i>j, но i стоит в этой перестановке раньше j.

Перестановку называют чётной, если её символы составляют чётное число инверсий, и нечётной тАУ в противоположном случае.

Всякое взаимно однозначное отображение А множества первых n натуральных чисел на себя называется подстановкой n-й степени, причём, очевидно, всякая подстановка А может быть записана при помощи двух перестановок, подписанных одна под другой.

Подстановка А будет чётной, если общее число инверсий в двух строках любой её записи чётно, и нечётной тАУ в противоположном случае.

Определителем n-го порядка называется алгебраическая сумма n! членов, составленная следующим образом: членами служат всевозможные произведения n элементов матрицы, взятых по одному в каждой строке и в каждом столбце, причём член берётся со знаком плюс, если его индексы составляют чётную подстановку и со знаком минус в противоположном случае.

Для определителя квадратной матрицы А используется обозначение |A| или detA.

Свойства определителя:

1.определитель транспонированной матрицы равен определителю исходной, т.е.

det(AT) = detA;

2.если все элементы строки умножить на , то определитель умножится на ;

3. если каждый элемент некоторой строки определителя представлен в виде суммы двух слагаемых, то определитель можно представить в виде суммы двух определителей, у которых все строки, кроме данной прежние, а в данной строке в первом определителе стоят первые, а во втором тАУ вторые слагаемые;

3тАЩ. аналогичные свойства для столбцов;

4. если две какиетАУлибо строки (столбца) матрицы поменять местами, то определитель матрицы умножиться на (-1);

5. определитель с двумя одинаковыми строками (столбцами) равен 0;

6. определитель не изменится, если к какойтАУлибо его строке (столбцу) прибавить другую строку (столбец), умноженную на .

Алгебраическое дополнение Вак элементу квадратной матрицы определяется равенством

где Ва(минор) тАУ определитель матрицы, полученной удалением из А тАУ й строки и тАУ го столбца.

Определитель можно разложить по любой строке и любому столбцу.

Разложение по iтАУй строке имеет вид:

7.Обратная матрица. Матрица А, у которой detA≠0, называется невырожденной.

Обратная матрица В = А-1 (по отношению к матрице А) тАУ такая матрица, что АВ = ВА = Е.

Обратная матрица существует в том и только в том случае, когда матрица А невырожденная.

В этом случае

, (9)

где тАУ алгебраические дополнения к элементам .

Если матрица А тАУ ортогональная и симметрическая, то

А-1 = А.

8.Конечные разности. Конечные разности вектора Ваопределяются рекуррентно :

Вместо Вапишут обычно .

Конечную разность Вапорядка Ваможно непосредственно выразить через значения вектора .

Справедлива формула

. (10)

Вз 2. Пространство N тАУ периодических комплекснозначных векторов

Зафиксируем натуральное число N. Определяем пространство следующим образом

Введём в Вадве операции тАУ операция сложения двух векторов и операция умножения вектора на комплексное число:

В результате получим линейное комплексное пространство.

Введём символ , у которого, когда Ваделится на , и при остальных ВаОчевидно, что

Лемма 1. Для Васправедливо следующее равенство

Ва(1)

Доказательство. Так как в обеих частях (1) стоят NтАУпериодические векторы, проверим равенство при Поскольку при Вавыполняются неравенства

то Вапри ВаОтсюда имеем

Таким образом, лемма доказана.

Формула (1) даёт аналитическое представление вектора х по его значениям на основном периоде

Рассмотрим следующую систему сдвигов вектора

Ва(2)

Покажем, что эта система линейно независима на Z. Действительно, пусть

Вапри

Как отмечалось, левая часть этого равенства равна Ватак что Вапри всех

Поэтому согласно лемме 1 любой вектор х разлагается по линейно независимой системе (2). Таким образом, показали, что система (2) является базисом пространства . При этом размерность пространства Варавна N, т.е.

Следующее вспомогательное утверждение будем часто использовать в дальнейшем.

Лемма 2. Для любого вектора Вапри всех Васправедливо равенство

Ва(3)

Доказательство. Пусть Вагде Ва- целая часть дроби, а - остаток от деления Вана . Воспользуемся Вапериодичностью вектора Ваи тем, что ВаТогда получим

Что и требовалось доказать.

Следствие. В условиях леммы 2 справедливо равенство

Ва(4)

Действительно,

Следствие доказано.

Определим в Васкалярное произведение и норму

Как и в комплексном унитарном пространстве, в Вадва вектора x, y называются ортогональными, если ВаВектор называется нормированным, если ||x||=1.

Лемма 3. При всех Васправедливо равенство

Ва(5)

Доказательство. Зафиксируем k и введём вектор ВаПосле чего, учитывая чётность Ваи формулу (1), запишем

Что и требовалось доказать.

Следствие. Система векторов (2) является ортонормированной, т. е. образует ортонормированный базис в пространстве

Наряду с вектором Вабудем рассматривать векторы , . Эти

векторы определяются следующим образом, а именно получаем векторы со значениями

Васоответственно.

Отметим также, что

Введём понятия чётности и нечётности вектора.

Вектор Ваназывается чётным, если Ваи нечётным, если Вапри всех .

Вектор Ваназывается вещественным, если , и чисто мнимым, если

Вз 3. ДПФ. Основные свойства

Возьмём корень Вастепени из единицы

Лемма 1. Имеет место равенство

, Ва(1)

Доказательство. Заметим, что в левой части (1) стоит ВатАУ периодическая функция.

На самом деле,

Вапри

тАУпериодическим является и ВаПоэтому достаточно проверить равенство (1) при .

При Ваоно тривиально. Пусть ВаИз формулы для суммы членов геометрической прогрессии имеем

Вапри

Положив , получим

Вапри .

Равенство доказано.

1.Непрерывное преобразование Фурье и формула обращения.

Функция , заданная на всей числовой прямой и определяемая формулой

, (2)

называется преобразованием Фурье исходной функции .

Формула, выражающая Вачерез её преобразование Фурье и имеющая вид

, (3)

называется формулой обращения для непрерывного преобразования Фурье.

Следует обратить внимание на сходство между формулами (1) и (2).

Вторая из них отличается от первой лишь знаком в показателе и множителем Ваперед интегралом.

2.Дискретное преобразование Фурье (ДПФ). Определение.

ДПФ тАУ это отображение

сопоставляющее вектору Вавектор Васо значениями

Ва(4)

Вектор X называется спектром Фурье вектора x или просто спектром, а величины X(k) тАУ компонентами спектра или спектральными составляющими соответствующего вектора.

Теорема 1. Имеет место формула обращения

Ва(5)

Доказательство. Из формул (1), (4) и из формулы (1) предыдущего параграфа имеем

Теорема доказана.

Формулу (5) можно записать компактно так:

Введём обозначение . Тогда формула (5) для ДПФ примет вид

Ва(6)

Из равенства (6) видно, что вектор Варазлагается по системе векторов

Ва(7)

Коэффициентами в этом разложении являются компоненты спектра.

Лемма 2. Для любого целого k имеем .

Доказательство. Действительно,

Лемма доказана.

Лемма 3. Система векторов (7) ортогональна. При этом Вапри всех

Доказательство. Имеем при

Отсюда очевидным образом следует требуемое.

Лемма 4. Система Валинейно независима.

Доказательство. Чтобы показать линейную независимость данной системы, надо проверить равенство

тогда и только тогда, когда

Возьмём скалярное произведение и покажем справедливость данного равенства:

Т.к. векторы ортогональные, то

Вапри

Нетрудно видеть, что . Так как , то

Лемма доказана.

Установлено, что система (7) образует ортогональный базис в пространстве Этот базис называется экспоненциальным.

Возьмём вектор

Тогда

Ва- разложение вектора Вав базисе (7).

Умножив обе части данного разложения на , получим

Учитывая тот факт, что , приходим к равенству

Ва(9)

Таким образом, формула (9) определяет коэффициенты Фурье вектора

Рассмотрим матрицу, элементами которой является компоненты векторов :

Это матрица ДПФ. Очевидно, у этой матрицы строки ортогональны.

Введем некоторые свойства данной матрицы и получим матрицу обратного преобразования.

Лемма 5. Матрица Вабудет ортогональной.

Доказательство. Для того чтобы доказать факт надо показать:

1.строки данной матрицы образуют ортогональную систему векторов;

2.норма каждой строки равна единице.

Покажем сначала первое, т.е.

Лемма доказана.

Лемма 6. Матрица Ваявляется симметрической.

Доказательство. Чтобы доказать данную лемму, покажем справедливость равенства

Итак,

Лемма доказана.

Раз матрица Ва- ортогональная и симметрическая, то

Тогда Ват.к.

Итак, - матрица обратного преобразования Фурье.

В дальнейшем нам понадобится следующее утверждение.

Лемма 7. Если имеем действительное евклидовое пространство, то

. (10)

В случае комплексного пространства имеем

. (11)

Доказательство.

Пусть Ва- матрица преобразования Фурье.

Тогда

Рассмотрим скалярное произведение

- левая часть нашего

равенства.

Учитывая, что

рассмотрим

Ва- правая часть

нашего равенства.

Правая часть равенства совпала с левой частью, значит, (11) - верное равенство.

Лемма доказана.

Далее рассмотрим свойства ДПФ.

Теорема 2. Пусть Тогда

Ва(12)

Доказательство. Учитывая формулу (12) и тот факт, что матрица Ваявляется симметрической и ортогональной, получим

Что и требовалось доказать.

Следствие. В условиях теоремы 2 справедливо равенство

Ва(13)

Формула (13) называется равенством Парсеваля, а формула (12) тАУ обобщённым равенством Парсеваля.

Вз 4. Задача восстановления координат

Ставится задача следующим образом. Пусть Вагде Ваи

Также считается известными и

Требуется узнать, можно ли найти Вапри условии, что

В приводимой ниже теореме показывается, что при некотором предположении координаты вектора Ваполностью восстанавливаются.

Теорема. Если спектр Вавектора Варавен нулю на некотором множестве , то

Ва(1)

Доказательство. По формуле обращения для ДПФ, учитывая условию теоремы, приходим к следующему равенству

Ва(2)

Зафиксируем Ваи пусть ВаПродолжив Вапериодически с периодом Вана , получим вектор , принадлежащий ВаВычислим его ДПФ:

Применяя формулу обращения, приходим к равенству

Подставив это выражение в (2), придём к (1). Действительно,

Теорема доказана.

Упростим формулу для h. Очевидно, что

Так как

Аналогичным образом получаем

При Ваимеем

Итак, получаем

Ва(3)

В простейшем случае, когда Ваформула (3) принимает вид

Ва(4)

Проверим это. При всех Ваимеем

что равносильно требуемому.

В случае Ванашу теорему можно переформулировать так: если на основном периоде Ваполовина значений спектра Вас индексами Варавна нулю, то вектор Вавосстанавливается по половине своих

компонентов Вас помощью формулы

где h имеет вид (4).

Вз5.Интерполяционная задача.

Рассмотрим следующую интерполяционную задачу

Ва(1)

В этой задаче требуется построить вектор , который в узлах Вапринимает заданные значения . Также известно, что старшие коэффициенты Фурье равны нулю.

Решение данной интерполяционной задачи сформулируем в виде теоремы.

Теорема. Решением задачи (1) является вектор

Ва(2)

Доказательство. Однородная система

согласно формуле (1) из предыдущего параграфа имеет только нулевое решение. Таким образом, задача (1) однозначно разрешима при любых комплексных ВаРассмотрим решение Ваэтой задачи. Аргумент Вапредставим в виде ВаВ силу определения Ваи формулы (1) предыдущего параграфа, получим

Теорема доказана.

Вз 6. Свёртка векторов

Свёрткой векторов Ваназывается вектор Вас компонентами

Ва(1)

Теорема 1 (о свёртке). Пусть ВаТогда

Ва(2)

где справа стоит покомпонентное произведение спектровВз, которое определяется следующим образом

Доказательство.

По формуле (2) из Вз 2 имеем

что соответствует (2). Что требовалось доказать.

Из теоремы 1 как следствие можно получить следующий результат.

Следствие. Справедливо равенство

Ва(3)

Сформулируем свойства свёртки в виде теоремы.

Теорема 2. Свёртка коммутативна и ассоциативна.

Доказательство. Коммутативность , непосредственно следует из (3). Проверим ассоциативность. Возьмём три вектора Ваи обозначим через Ваих спектры.

Учитывая (2) и (3), получаем

Теорема доказана.

Преобразование Ваназывается линейным, если для любых Ваи любых , имеет место равенство

В качестве примера линейного преобразования рассмотрим оператор сдвига , сопоставляющий вектору Вавектор Вас координатами

Преобразование Ваназывается стационарным, если

для всех

Из определения получаем

где - тождественный оператор.

Теорема 3. Преобразование Вабудет линейным и стационарным тогда и только тогда, когда найдётся вектор , такой, что

Вапри всех Ва(4)

Доказательство.

Необходимость. Учитывая, что Ваперепишем формулу (1) из Вз 2 в виде

Так как оператор Валинейный и стационарный, то получим

Допустив, что , приходим к равенству

Достаточность. Линейность сверточного оператора очевидна. Остается проверить стационарность. В силу коммутативности свертки

Далее запишем

Что и требовалось доказать.

Рассмотрим операцию взятия конечной разности Вапорядка:

Сначала покажем, что Вагде

Согласно (1) из Вз 2 имеем

что и требовалось установить.

Вз 7. Решение задачи оптимальной интерполяции

Допустим, что - натуральное число. Рассмотрим следующую экстремальную задачу:

Ва(1)

В этой задаче требуется построить возможно более гладкий вектор, принимающий в узлах Вазаданные значения Ваа гладкость данного вектора характеризуется квадратом нормы конечной разности r тАУ го порядка. Чаще всего рассматривается случай, когда r=2.

Проведём замену переменных

После чего перепишем задачу (1) в компонентах ВаЭтот процесс начнём с целевой функции. Как было показано в последнем примере предыдущего параграфа Вагде Ваопределяется соответственно формулой (5) того же параграфа. Далее используя равенство Парсеваля и формулу из теоремы о свёртке, получаем