Реферат: Решение задачи об оптимальной интерполяции с помощью дискретного преобразования Фурье (ДПФ)
Введение
Предложенная мне тема «Решениезадачи об оптимальной интерполяции с помощью дискретного преобразования Фурье(ДПФ)» написана на основе книги В. Н. Малоземова и С. М. Машарского «Основы дискретногогармонического анализа». Дискретный гармонический анализ – это математическаядисциплина, результаты которой активно используются в цифровой обработкесигналов. По ходу изучения книги возникли новые задачи, две из которыхприведены в разделе «Решения задач». В данной работе также сравнивается ДПФ снепрерывным преобразованием Фурье. В приложениях в случае классическогопреобразования приходится приближенно заменят интегралы некоторыми суммами. Приэтом основная трудность связана с необходимостью оценки погрешности на каждомиз последующих этапов. ДПФ тем выгоднее и отличаются, что здесь с самого началавместо интегралов имеем дело с суммами. При этом основные цели использованияДПФ также достигаются.
Рассматриваются различныепреобразования /> — периодических векторов, средикоторых центральную роль играет ДПФ. Задача об оптимальной интерполяцииявляется приложением ДПФ.
Отдельные задачи в рамкахдипломной работы мне решить не удалось. Они не вошли в дипломную работу.
Основная работа свелась кизложению основных фактов с подробными доказательствами. В начале дипломнойработы имеется раздел «Вспомогательный материал», в котором кратко изложеныфакты, необходимые для чтения основного текста. Эти факты хорошо известны икасаются тех понятий и терминов, которые встречаются в теории чисел, в теориилинейных комплексных пространств и в линейной алгебре. Все эти понятияиспользуются для получения более важных результатов в последующих параграфах.
Далее вводится пространство /> — периодическихвекторов /> иустанавливается тот факт, что /> — линейное комплексноепространство.
Над элементами этого пространстваопределяются прямое и обратное ДПФ.
Решены задачи, составлена иапробирована программа, которая реализует оптимальную интерполяцию. Такжесоставлены программы, которые вычисляют свертку двух периодических векторов иДПФ.
При решении задачи оптимальнойинтерполяции сначала переходим к новым переменным с помощью ДПФ. Далееполеченную задачу решаем методом множителей Лагранжа. И, наконец, переходим кисходным переменным с помощью формулы обращения.
2
§ 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) будет, вообще говоря, комплекснымчислом.
3
При этом должны выполнятсяаксиомы:
1./>, где черта обозначает, как обычно,переход к сопряжённому комплексному числу;
2./>
3./>
4.Если а ≠ 0, то скалярныйквадрат вектора а строго положителен, т.е.
(а. а) > 0, а если (а, а) = 0,то а = 0.
Комплексное линейное пространствоназывается унитарным пространством, если в нём задано скалярное умножение.
Векторы а и b называютсяортогональными, если их скалярное произведение равно нулю
(а, b) = 0.
Система векторов называетсяортогональной системой, если все векторы этой системы попарно ортогональны.
Назовём вектор b нормированным, еслиего скалярный квадрат равен единице
(b, b) = 1.
При этом, если /> - ортонормированнаябаза и векторы а, b
имеют в этом базе записи
а = />, /> />, то />./>
Также имеем равенство
/> (3)
3.Вычеты. Пусть/>и /> – натуральное число.Существует единственное целое число />, такое, что
/> (4)
Оно называется целой частью дроби/> иобозначается />
Разность /> называется вычетом /> по модулю /> и обозначается/>.
4
Нетрудно показать, что
/>/>/>. (5)
Действительно, умножимнеравенства (4) на /> и вычтем />.
Получим />, что равносильно (5).
4.Функции комплексногопеременного. На плоскостях комплексных переменных z и w рассмотримсоответственно множества /> и />.
Если указан закон f, по которомкаждому значению /> сопоставляется единственноезначение />,то говорят, что на множестве Е определена однозначная функция комплексногопеременного z и пишут w=f(z).
Функции />/>определяются как суммы степенныхрядов:
/>, />, />. (6)
Из этих равенств непосредственноможно получить следующие формулы Эйлера:
/>, />, />. (7)
5.Матрицы. Прямоугольная таблицачисел, записанная в виде
/> (8)
называется матрицей.
Коротко матрицу обозначают так: />, />;
где /> - элемент данной матрицы, которыйнаходится в i-й строке и j-м столбце матрицы А.
5
Некоторые свойства матриц:
1. сумма С = А + В двух матриц Аи В одного размера m/>n – это матрица
С = (с/>), где с/>= a/>+ b/>для всех i, j;
сумма матриц разных размеров неопределяется.
2.Произведение С = λАматрицы А и элемента λ/>С – это матрица того же размера, чтои А, причём />привсех i, j.
3.Произведение С = АВ матрицы Аразмера m/>nи матрицы В размера n/>p – это матрица С размера m/>p такая, что
/>
Произведение матриц в общемслучае некоммутативно, т.е АВ≠ВА.
Транспонированная матрица /> (по отношениюк матрице А) – такая матрица, что />.
Совокупность элементов /> квадратнойматрицы /> называетсяглавной диагональю матрицы.
Матрица, у которой элементы, стоящиена главной диагонали, равны единице, а все остальные элементы равны 0, называетсяединичной матрицей и обозначается буквой Е.
Напомним, что
АЕ = А и ЕА = А.
Матрица называется ортогональной,если строки образуют ортогональную систему векторов и норма каждой строки равнаединице.
Квадратная матрица называетсясимметрической, если
/>.
6.Определители. Всякоерасположение чисел 1, 2, …, n в некотором определённом порядке называетсяперестановкой из n чисел.
Говорят, что в даннойперестановке числа i и j составляют инверсию, если i>j, но i стоит в этой перестановкераньше j.
Перестановку называют чётной, еслиеё символы составляют чётное число инверсий, и нечётной – в противоположномслучае.
Всякое взаимно однозначноеотображение А множества первых n натуральных чисел на себя называетсяподстановкой n-й степени, причём, очевидно, всякая подстановка А может бытьзаписана при помощи двух перестановок, подписанных одна под другой.
6
Подстановка А будет чётной, еслиобщее число инверсий в двух строках любой её записи чётно, и нечётной – впротивоположном случае.
Определителем n-го порядканазывается алгебраическая сумма n! членов, составленная следующим образом:членами служат всевозможные произведения n элементов матрицы, взятых по одномув каждой строке и в каждом столбце, причём член берётся со знаком плюс, еслиего индексы составляют чётную подстановку и со знаком минус в противоположномслучае.
Для определителя квадратнойматрицы А используется обозначение |A| или detA.
Свойства определителя:
1.определитель транспонированнойматрицы равен определителю исходной, т.е.
det(AT) = detA;
2.если все элементы строкиумножить на />,то определитель умножится на />;
3. если каждый элемент некоторойстроки определителя представлен в виде суммы двух слагаемых, то определительможно представить в виде суммы двух определителей, у которых все строки, кромеданной прежние, а в данной строке в первом определителе стоят первые, а вовтором – вторые слагаемые;
3’.аналогичные свойства для столбцов;
4. если две какие–либо строки(столбца) матрицы поменять местами, то определитель матрицы умножиться на (-1);
5. определитель с двумяодинаковыми строками (столбцами) равен 0;
6. определитель не изменится, еслик какой–либо его строке (столбцу) прибавить другую строку (столбец), умноженнуюна />.
Алгебраическое дополнение /> к элементуквадратной матрицы />определяется равенством
/>,
где /> (минор) – определитель матрицы, полученнойудалением из А />– й строки и />– го столбца.
7
Определитель можно разложить полюбой строке и любому столбцу.
Разложение по i–й строке имеетвид:
/>.
7.Обратная матрица. Матрица А, укоторой detA≠0, называется невырожденной.
Обратная матрица В = А-1 (поотношению к матрице А) – такая матрица, что АВ = ВА = Е.
Обратная матрица существует в томи только в том случае, когда матрица А невырожденная.
В этом случае
/>, (9)
где />– алгебраические дополнения кэлементам />.
Если матрица А – ортогональная исимметрическая, то
А-1 = А.
8.Конечные разности. Конечныеразности вектора />/> определяются рекуррентно :
/>
Вместо /> пишут обычно />.
Конечную разность /> порядка /> можно непосредственновыразить через значения вектора />.
Справедлива формула
/>. (10)
8
§ 2. Пространство N –периодических комплекснозначных векторов
Зафиксируем натуральное число N.Определяем пространство следующим образом
/>.
Введём в /> две операции – операция сложениядвух векторов и операция умножения вектора на комплексное число:
/> /> />
/> /> />
В результате получим линейноекомплексное пространство.
Введём символ />, у которого/>, когда /> делится на />, и />при остальных /> Очевидно, что />
Лемма 1. Для /> справедливо следующееравенство
/> (1)
Доказательство. Так как в обеихчастях (1) стоят N–периодические векторы, проверим равенство при />Поскольку при /> выполняютсянеравенства
/>
то /> при /> Отсюда имеем
/>
Таким образом, лемма доказана.
Формула (1) даёт аналитическоепредставление вектора х по его значениям на основном периоде />
9
Рассмотрим следующую системусдвигов вектора />
/> (2)
Покажем, что эта система линейнонезависима на Z. Действительно, пусть
/> при />
Как отмечалось, левая часть этогоравенства равна /> так что /> при всех />
Поэтому согласно лемме 1 любойвектор х разлагается по линейно независимой системе (2). Таким образом, показали,что система (2) является базисом пространства />. При этом размерностьпространства /> равна N, т.е. />
Следующее вспомогательноеутверждение будем часто использовать в дальнейшем.
/>
Лемма 2. Для любого вектора /> при всех /> справедливоравенство
/> (3)
Доказательство. Пусть /> где /> - целая частьдроби/>, а /> — остаток отделения /> на/>.Воспользуемся /> периодичностью вектора /> и тем, что /> Тогда получим
/>/>
Что и требовалось доказать.
10
Следствие. В условиях леммы 2справедливо равенство
/> (4)
Действительно,
/>
Следствие доказано.
Определим в /> скалярное произведениеи норму
/>
Как и в комплексном унитарномпространстве, в /> два вектора x, y называютсяортогональными, если /> Вектор называется нормированным, если||x||=1.
Лемма 3. При всех /> справедливо равенство
/> (5)
/>
Доказательство. Зафиксируем k ивведём вектор /> После чего, учитывая чётность /> и формулу (1),запишем
/>
Что и требовалось доказать.
Следствие. Система векторов (2)является ортонормированной, т. е. образует ортонормированный базис впространстве />
11
Наряду с вектором /> будем рассматриватьвекторы />, />. Эти
векторы определяются следующимобразом, а именно получаем векторы со значениями
/> соответственно.
Отметим также, что />
Введём понятия чётности инечётности вектора.
Вектор /> называется чётным, если /> и нечётным, если/> при всех />.
Вектор /> называется вещественным, если />, и чистомнимым, если />
12
§ 3. ДПФ. Основные свойства
Возьмём корень /> степени из единицы />
Лемма 1. Имеет место равенство
/>, />/> (1)
Доказательство. Заметим, что влевой части (1) стоит /> – периодическая функция.
На самом деле,
/> при />
/>–периодическим является и /> Поэтомудостаточно проверить равенство (1) при />.
При /> оно тривиально. Пусть /> Из формулы длясуммы членов геометрической прогрессии имеем
/> при />
Положив />, получим
/> при />.
Равенство доказано.
1.Непрерывное преобразованиеФурье и формула обращения.
Функция />, заданная на всей числовой прямойи определяемая формулой
/>, (2)
называется преобразованием Фурьеисходной функции />.
13
Формула, выражающая /> через еёпреобразование Фурье и имеющая вид
/>, (3)
называется формулой обращения длянепрерывного преобразования Фурье.
Следует обратить внимание насходство между формулами (1) и (2).
Вторая из них отличается отпервой лишь знаком в показателе и множителем /> перед интегралом.
2.Дискретное преобразование Фурье(ДПФ). Определение.
ДПФ – это отображение
/>,
сопоставляющее вектору /> вектор /> со значениями
/> (4)
Вектор X называется спектром Фурьевектора x или просто спектром, а величины X(k) – компонентами спектра илиспектральными составляющими соответствующего вектора.
Теорема 1. Имеет место формулаобращения
/> (5)
Доказательство. Из формул (1), (4)и из формулы (1) предыдущего параграфа имеем
/>
Теорема доказана.
14
Формулу (5) можно записатькомпактно так: />
Введём обозначение />. Тогда формула (5) дляДПФ примет вид
/> (6)
Из равенства (6) видно, чтовектор /> разлагаетсяпо системе векторов
/> (7)
Коэффициентами в этом разложенииявляются компоненты спектра.
Лемма 2. Для любого целого kимеем />.
Доказательство. Действительно,
/>
Лемма доказана.
Лемма 3. Система векторов (7)ортогональна. При этом /> при всех />
Доказательство. Имеем при />
/>
Отсюда очевидным образом следуеттребуемое.
15
Лемма 4. Система /> линейно независима.
Доказательство. Чтобы показатьлинейную независимость данной системы, надо проверить равенство
/>
тогда и только тогда, когда />
Возьмём скалярное произведение ипокажем справедливость данного равенства:
/>
Т.к. векторы ортогональные, то
/> при />
Нетрудно видеть, что />. Так как />, то />
Лемма доказана.
Установлено, что система (7)образует ортогональный базис в пространстве />Этот базис называетсяэкспоненциальным.
Возьмём вектор />
Тогда
/> - разложение вектора /> в базисе (7).
Умножив обе части данногоразложения на />, получим />
Учитывая тот факт, что />, приходим кравенству
/> (9)
Таким образом, формула (9)определяет коэффициенты Фурье вектора />
16
Рассмотрим матрицу, элементамикоторой является компоненты векторов />:
/>, />
Это матрица ДПФ. Очевидно, у этойматрицы строки ортогональны.
Введем некоторые свойства даннойматрицы и получим матрицу обратного преобразования.
Лемма 5. Матрица /> будет ортогональной.
Доказательство. Для того чтобыдоказать факт надо показать:
1.строки данной матрицы образуютортогональную систему векторов;
2.норма каждой строки равнаединице.
Покажем сначала первое, т.е.
/>
Далее
/>
Лемма доказана.
17
Лемма 6. Матрица /> являетсясимметрической.
Доказательство. Чтобы доказатьданную лемму, покажем справедливость равенства />
Итак,
/>,
/>
Лемма доказана.
Раз матрица /> - ортогональная исимметрическая, то />
Тогда /> т.к.
/>
Итак, /> — матрица обратного преобразованияФурье.
В дальнейшем нам понадобитсяследующее утверждение.
Лемма 7. Если имеемдействительное евклидовое пространство, то
/>. (10)
В случае комплексногопространства имеем
/>. (11)
Доказательство.
Пусть /> - матрица преобразования Фурье.
Тогда
/>.
18
Рассмотрим скалярное произведение
/>/> — левая часть нашего
равенства.
Учитывая, что
/>
рассмотрим
/> - правая часть
нашего равенства.
Правая часть равенства совпала слевой частью, значит, (11) — верное равенство.
Лемма доказана.
Далее рассмотрим свойства ДПФ.
Теорема 2. Пусть />Тогда
/> (12)
Доказательство. Учитывая формулу(12) и тот факт, что матрица /> является симметрической иортогональной, получим
/>
/>
Что и требовалось доказать.
Следствие. В условиях теоремы 2справедливо равенство
/> (13)
Формула (13) называетсяравенством Парсеваля, а формула (12) – обобщённым равенством Парсеваля.
19
§ 4. Задача восстановлениякоординат
Ставится задача следующимобразом. Пусть /> где /> и
/>
Также считается известными и />
Требуется узнать, можно ли найти /> при условии, что/>
В приводимой ниже теоремепоказывается, что при некотором предположении координаты вектора /> полностьювосстанавливаются.
Теорема. Если спектр /> вектора /> равен нулю нанекотором множестве />, то
/> (1)
Доказательство. По формулеобращения для ДПФ, учитывая условию теоремы, приходим к следующему равенству
/> (2)
Зафиксируем /> и пусть /> Продолжив /> периодически спериодом /> на/>, получимвектор />, принадлежащий/> Вычислимего ДПФ:
/>
Применяя формулу обращения, приходимк равенству
/>
20
Подставив это выражение в (2), придёмк (1). Действительно,
/>
Теорема доказана.
Упростим формулу для h. Очевидно,что
/>
Так как
/>.
Аналогичным образом получаем
/>./>
При /> имеем
/>
Итак, получаем
/> (3)
21
В простейшем случае, когда /> формула (3)принимает вид
/> (4)
Проверим это. При всех /> имеем
/>
что равносильно требуемому.
В случае /> нашу теорему можнопереформулировать так: если на основном периоде /> половина значений спектра /> с индексами /> равна нулю, товектор /> восстанавливаетсяпо половине своих
компонентов /> с помощью формулы
/>
где h имеет вид (4).
22
§5.Интерполяционная задача.
Рассмотрим следующуюинтерполяционную задачу
/> (1)
В этой задаче требуется построитьвектор />, которыйв узлах /> принимаетзаданные значения />. Также известно, что старшиекоэффициенты Фурье равны нулю.
Решение данной интерполяционнойзадачи сформулируем в виде теоремы.
Теорема. Решением задачи (1)является вектор
/> (2)
Доказательство. Однороднаясистема
/>
согласно формуле (1) изпредыдущего параграфа имеет только нулевое решение. Таким образом, задача (1)однозначно разрешима при любых комплексных /> Рассмотрим решение /> этой задачи. Аргумент /> представим ввиде /> Всилу определения /> и формулы (1) предыдущегопараграфа, получим
/>
Теорема доказана.
23
§ 6. Свёртка векторов/>
Свёрткой векторов /> называется вектор /> с компонентами
/> (1)
Теорема 1 (о свёртке). Пусть /> Тогда
/> (2)
где справа стоит покомпонентноепроизведение спектров§, которое определяется следующим образом
/>
Доказательство.
По формуле (2) из § 2 имеем
/>
/>
/>
что соответствует (2). Чтотребовалось доказать.
Из теоремы 1 как следствие можнополучить следующий результат.
Следствие. Справедливо равенство
/> (3)
Сформулируем свойства свёртки ввиде теоремы.
Теорема 2. Свёртка коммутативна иассоциативна.
Доказательство. Коммутативность />, непосредственноследует из (3). Проверим ассоциативность. Возьмём три вектора /> и обозначим через /> их спектры.
24
Учитывая (2) и (3), получаем
/>
/>
Теорема доказана.
Преобразование /> называется линейным, еслидля любых /> илюбых />, имеетместо равенство
/>
В качестве примера линейногопреобразования рассмотрим оператор сдвига />, сопоставляющий вектору /> вектор /> с координатами/>
Преобразование /> называется стационарным,если />
для всех />
Из определения получаем
/>,
где /> — тождественный оператор.
Теорема 3. Преобразование /> будет линейными стационарным тогда и только тогда, когда найдётся вектор />, такой, что
/> при всех /> (4)
Доказательство.
Необходимость. Учитывая, что /> перепишемформулу (1) из § 2 в виде
/>
Так как оператор /> линейный и стационарный,то получим
/>
25
Допустив, что />, приходим к равенству
/>
Достаточность. Линейностьсверточного оператора очевидна. Остается проверить стационарность. В силукоммутативности свертки
/>
Далее запишем
/>
Что и требовалось доказать.
Рассмотрим операцию взятияконечной разности /> порядка:
/>
Сначала покажем, что /> где
/>
Согласно (1) из § 2 имеем
/>
что и требовалось установить.
26
§ 7. Решение задачи оптимальнойинтерполяции
Допустим, что /> — натуральное число.Рассмотрим следующую экстремальную задачу:
/> (1)
В этой задаче требуется построитьвозможно более гладкий вектор, принимающий в узлах /> заданные значения /> а гладкость данноговектора характеризуется квадратом нормы конечной разности r – го порядка. Чащевсего рассматривается случай, когда r=2.
Проведём замену переменных
/>
После чего перепишем задачу (1) вкомпонентах /> Этотпроцесс начнём с целевой функции. Как было показано в последнем примерепредыдущего параграфа /> где /> определяется соответственноформулой (5) того же параграфа. Далее используя равенство Парсеваля и формулуиз теоремы о свёртке, получаем
/>
/>
Отметим только, что здесь
/>/>
Введём обозначение
/>
27
Тогда /> и
/> (2)
Теперь обратимся к ограничениям.Имеем
/>
Таким образом, ограничения задачи(1) принимают вид
/>
Последняя формула представляетсобой разложение вектора /> по экспоненциальному базису. Онаравносильна тому, что
/> (3)
где /> На основании (2) и (3) приходим кэквивалентной постановке задачи (1):
/>
/> (4)
Последняя задача, т.е. задача (4)распадается на m независимых подзадач, соответствующих разным />
/>
/> (5)
28
Поскольку />, то при /> приходим к задаче
/>
/>
Решение этой задачи имеет вид
/> (6)
Заметим только, что минимальноерешение целевой функции равно нулю.
Допустим теперь, что />
В этом случае мы данную задачурешаем методом множителей Лагранжа.
Строим функцию Лагранжа:
/>.
Итак,
/>
/> (7)
Чтобы найти /> воспользуемсяограничениями
/>.
Из этого выражения находим />:
/>
Подставив /> в (7), получим решениезадачи (4) при />
/>
29
Введём обозначение
/>
Тогда окончательное решениезапишется в виде
/> (8)
Формулы (6) и (8) определяют /> на всёмосновном периоде /> По формуле обращения находимединственное решение задачи (1):
/> (9)
При этом минимальное значениецелевой функции задачи (1) складывается из минимальных значений целевых функцийзадач (5) при />, так, что
/>.
Преобразуем (9) к более удобномудля вычислений виду. Индексы /> представим в виде /> и />
Согласно (6) и (8) запишем
/>
/>
Таким образом, приходим кследующей схеме решения задачи (1):
1. в первую очередь, формируемдва массива констант, зависящих только от m, n и r:
одномерный
/>
30
и (по столбцам) составляемдвумерный
/>
2. вычисляем /> при />
3. после этого вводим двумерныймассив В со столбцами
/>
4. и наконец, применяя обратноеДПФ порядка m ко всем n-1 строкам матрицы В, получаем решение задачи (1):
/>
31
Решения задач
Задача 1. Докажите, что
/>
Доказательство. По определениюсравнения
/>
Используя свойства сравнений, получим
/>
Или в одну строку
/>
т.е. 12 есть остаток от данногоделения.
Задача 2. Пусть /> и даны два вектора
/>
Требуется найти />
Решение. Согласно формуле длявычисления свертки, имеем
/>
32
Задача 3. Докажите, что
/>
Доказательство. Докажем данноеравенство методом математической индукции.
При n=1 имеем верное равенство
/>
Пусть n=k
/>
Тогда
/>
/>
Равенство доказано.
Задача 4. (Китайская теорема обостатках). Предположим, что />, причём сомножители /> - попарновзаимно простые и отличные от единицы числа. Докажите, что система уравнений /> или
/> (1)
имеет единственное решение намножестве /> прилюбых /> Найдитеэто решение.
Доказательство.
Пусть числа /> определены без условийи />
33
Тогда число /> - является решением
системы (1).
Действительно, так как
/>
то
/>,
так как все слагаемые в правойчасти делятся на />.
Известно, что
/>.
Последнее сравнение умножим на />:
/> (2)
Тогда /> - решение сравнения /> Аналогичноможно показать, что /> -
решение всех остальных сравненийсистемы (1). Таким образом, /> - решение системы (1).
Докажем теперь единственностьэтого решения.
Пусть /> - какое-нибудь другое решениеданной системы, т.е. имеем
/> (3)
Сравнение (2) перепишем в виде />Вычитая изсравнения (2) сравнение (3), приходим к />
Таким образом, доказалиединственность решения системы (1).
34
Задача 5. Докажите, что при /> и натуральных /> справедливоравенство
/>
Доказательство. По определениювычета имеем
/>
Итак, />
Задача 6. Пусть /> - взаимно простые инатуральные числа, т.е. />
Положим /> Докажите, что множества /> равны, т.е.состоят из одних и тех же элементов.
Доказательство. Общий элементмножества /> представляетсяв виде:
/>
а множества /> - в виде:
/>
Так как функции /> периодические спериодом /> и/> пробегает/>, то ихзначения совпадают, т.е. множества /> равны.
35
Задача 7. Докажите, что
/>
Доказательство. (Методматематической индукции).
При /> имеем верное равенство. Пустьверно и при />
Перейдём к случаю, когда />
/>/> (верно).
Задача 8. Докажите, что конечнаяразность /> порядкаот алгебраического полинома /> степени равна тождественно нулю.
Доказательство. Как известно, еслифункция /> имеет/> непрерывныхпроизводных на некотором промежутке и /> любые различные точки этогопромежутка, то существует точка
/>
Отсюда следует, что /> если
/>алгебраический полином, у которого/>
А производная /> порядка, как известно, отполинома степени /> равно нулю.
36
Задача 9. Докажите, что сигнал /> являетсячётным тогда и только тогда, когда
/>
Доказательство.
Необходимость. Пусть /> - чётныйсигнал, т.е. выполняется равенство
/> Тогда учитывая периодичность ичётность данного сигнала, имеем:
/>
Достаточность. Допустим имеем: /> Покажем, что />
Действительно,
/>
Задача 10.Приведём пример навычисление ДПФ. Пусть /> и
/>
Покажем, что />
По определению ДПФ
/>
Поскольку /> то /> так что
/>
37
Остаётся учесть, что в случае, когда/> неделится на />(вчастности, при нечётных />), справедливо равенство
/>
38
Программы
Листинг программы для вычисленияДПФ
uses crt;
const
N=3;
var
j, k:integer;
xm, X_r,X_i:array[0..N-1] of real;
begin clrscr;
for k:=0 to N-1 do
readln(xm[k]);
for j:=0 to N-1 dobegin
X_r[j]:=0; X_i[j]:=0;
end;
for j:=0 to N-1 do
for k:=0 to N-1 dobegin
X_r[j]:=X_r[j]+cos(2*pi*j*k/N)*xm[k];
X_i[j]:=X_i[j]+sin(2*pi*j*k/N)*xm[k];
end;
for j:=0 to N-1 dobegin
if X_i[j]<0 then
writeln(X_r[j]:6:2, '+i*', — X_i[j]:5:2)
elsewriteln(X_r[j]:6:2, ' — i*', X_i[j]:5:2)
end;
readkey;
end.
39
Листинг программы для вычислениясвёртки
uses crt;
const N=3;
var
x, v:array[0..N-1] ofreal;
y:array[1-N..N-1] ofreal;
j, k:integer;
begin clrscr;
for k:=0 to N-1 do
readln(x[k]); writeln;
for k:=0 to N-1 do
{for j:=0 to N-1 do}
readln(y[k]); writeln;
{for j:=0 to N-1 do}
for k:=1 to N-1 do
y[-k]:=y[N-k];
{------------------------------------}
for k:=1-N to N-1 dowriteln(y[k]:4:1); writeln;
{----------------------------------}
for j:=0 to N-1 do
v[j]:=0;
for j:=0 to N-1 do
for k:=0 to N-1 do
v[j]:=v[j]+x[k]*y[j-k];
for j:=0 to N-1 do
writeln(v[j]:4:1);
readkey;
end.
40
Листинг программы для вычисленияодномерного массива />
uses crt;
const nb=12; n=3; m=4;
var
l, s:array[1..m-1] ofreal;
D_r, D_i, SR, SI:array[1..n-1,1..m-1] of real;
p, q, t:integer;
{-----------------------------------}
begin clrscr;
for p:=1 to m-1 do
s[p]:=0;
for p:=1 to m-1 do
for q:=0 to n-1 do
s[p]:=s[p]+1/(16*exp(4*ln(sin((pi*(p+m*q))/nb))));
for p:=1 to m-1 do
l[p]:=n/s[p];
for p:=1 to m-1 do
writeln(l[p]:4:1);writeln;
{----------------------------}
for t:=1 to n-1 do
for p:=1 to m-1 dobegin
SR[t, p]:=0; SI[t,p]:=0; end;
for t:=1 to n-1 do
for p:=1 to m-1 do
for q:=0 to n-1 do
SR[t, p]:=SR[t,p]+cos((2*pi*q*t)/n)/(16*exp(4*ln(sin((pi*(p+m*q))/nb))));
SI[t, p]:=SI[t,p]+sin((2*pi*q*t)/n)/(16*exp(4*ln(sin((pi*(p+m*q))/nb))));
for t:=1 to n-1 do
for p:=1 to m-1 do
D_r[t, p]:=SR[t,p]*cos((2*pi*q*t)/nb)-SI[t, p]*sin((2*pi*q*t)/nb);
D_i[t, p]:=SR[t,p]*sin((2*pi*q*t)/nb)+SI[t, p]*cos((2*pi*q*t)/nb);
for t:=1 to n-1 dobegin writeln;
for p:=1 to m-1 do
write(D_r[t, p]:5:1);
end;
readkey;
end.
41
Листинг программы для решениязадачи оптимальной интерполяции
uses crt;
const
m=4; n=3; nb=12;
var
j, p, q, t,lm:integer;
zm, l, s, zv_r,zv_i:array[1..m-1] of real;
Z_r, Z_i:array[0..m-1]of real;
D_r, D_i, SR,SI:array[1..n-1, 1..m-1] of real;
B_r, B_i:array[1..n-1,0..m-1] of real;
xr_i, xr_r, x_i,x_r:array[0..nb-1] of real;
{---------------------------------------------}
begin clrscr;
for p:=1 to m-1 do
s[p]:=0;
for p:=1 to m-1 do
for q:=0 to n-1 do
s[p]:=s[p]+1/(16*exp(4*ln(sin((pi*(p+m*q))/nb))));
for p:=1 to m-1 do
l[p]:=n/s[p];
writeln('lambda p');
for p:=1 to m-1 do
writeln(l[p]:4:1);writeln;
{-----------------------------------------------}
for j:=1 to m-1 do
readln(zm[j]);
Z_r[0]:=0; Z_i[0]:=0;
for j:=1 to m-1 do
Z_r[0]:=Z_r[0]+zm[j];
for p:=1 to m-1 dobegin
Z_r[p]:=0; Z_i[p]:=0;
end;
for p:=1 to m-1 do
for j:=1 to m-1 dobegin
Z_r[p]:=Z_r[p]+cos(2*pi*p*j/m)*zm[j];
Z_i[p]:=Z_i[p]+sin(2*pi*p*j/m)*zm[j];
end;
writeln('Z(p)');
for p:=1 to m-1 do
writeln(Z_r[p]:6:2, '', Z_i[p]:6:2); writeln;
{-------------------------------------------------}
for p:=1 to m-1 dobegin
zv_r[p]:=l[p]*Z_r[p];
zv_i[p]:=l[p]*Z_i[p];
end;
42
writeln('Z s volnoy');
for p:=1 to m-1 do
writeln(zv_r[p]:6:2, '', zv_i[p]:6:2); writeln;
{---------------------------------------------------}
for t:=1 to n-1 do
for p:=1 to m-1 dobegin
SR[t, p]:=0; SI[t,p]:=0; end;
for t:=1 to n-1 do
for p:=1 to m-1 do
for q:=0 to n-1 do
SR[t, p]:=SR[t,p]+cos((2*pi*q*t)/n)/(16*exp(4*ln(sin((pi*(p+m*q))/nb))));
SI[t, p]:=SI[t,p]+sin((2*pi*q*t)/n)/(16*exp(4*ln(sin((pi*(p+m*q))/nb))));
for t:=1 to n-1 do
for p:=1 to m-1 do
D_r[t, p]:=SR[t,p]*cos((2*pi*q*t)/nb)-SI[t, p]*sin((2*pi*q*t)/nb);
D_i[t, p]:=SR[t,p]*sin((2*pi*q*t)/nb)+SI[t, p]*cos((2*pi*q*t)/nb);
writeln;writeln('Matriza D');
for t:=1 to n-1 dobegin writeln;
for p:=1 to m-1 do
write(D_r[t, p]:5:1);
end;
writeln;
for t:=1 to n-1 dobegin writeln;
for p:=1 to m-1 do
write(D_i[t, p]:5:1);
end;
{-----------------------------------------------}
for t:=1 to n-1 do
for p:=1 to m-1 dobegin
B_r[t,p]:=zv_r[p]*D_r[t, p];
B_i[t,p]:=zv_i[p]*D_i[t, p];
end;
for t:=1 to n-1 dobegin
B_r[t, 0]:=Z_r[0];
B_i[t, 0]:=Z_r[0];
end;
writeln;writeln('Matriza B');
for t:=1 to n-1 dobegin writeln;
for p:=0 to m-1 do
write(B_r[t, p]:5:1);writeln;
end;
writeln;
for t:=1 to n-1 dobegin writeln;
for p:=0 to m-1 do
write(B_i[t, p]:5:1);writeln;
end;
{-----------------------------------------------}
for t:=1 to n-1 do
43
for lm:=0 to m-1 dobegin
x_r[t+lm*n]:=0;
x_i[t+lm*n]:=0;
end;
for t:=1 to n-1 do
for lm:=0 to m-1 do
for p:=0 to m-1 dobegin
x_r[t+lm*n]:=x_r[t+lm*n]+B_r[t,p]*cos(2*pi*p*lm/m);
x_i[t+lm*n]:=x_i[t+lm*n]+B_i[t,p]*sin(2*pi*p*lm/m);
xr_r[t+lm*n]:=x_r[t+lm*n]/m;
xr_i[t+lm*n]:=x_i[t+lm*n]/m;
end;
writeln; writeln('Rex*', ' ', 'Im x*');
for j:=0 to nb-1 do
writeln(xr_r[j]:4:1, '', xr_i[j]:4:1);
readkey;
end.
44
Списоклитературы
В.Н.Малоземов, С.М.Машарский.Основы дискретного гармонического анализа. – СПб:, НИИММ, 2003 г.
А.Н. Колмогоров, С. В. Фомин.Элементы теории функции и функционального анализа. – М:, Наука, 1976 г.
А. Г. Курош. Курс высшей алгебры.– М:, Наука, 1971 г.
В. С. Шипачев. Высшая математика.– М:, Высшая школа, 2003 г.
Г. А. Магомедов, М. М.Сиражудинов, Р. К. Рагимханов. Теория функций комплексного анализа. –Махачкала:, ИПЦ ДГУ, 2003 г.
Для подготовки данной работы былииспользованы материалы с сайта referat.ru/