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

Введение

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

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

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

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

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

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

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

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

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/

еще рефераты
Еще работы по математике