85459 (612492), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Дальнейшие коэффициенты по двадцати четырем ординатам получаются с все меньшей точностью.

Нужно обратить внимание на одну подробность. Для получения коэффициентов и

нужно отдельно вычислить те выражения, которые поставлены в квадратные скобки, а затем сложить их (для нахождения

) и вычесть (для нахождения

). Аналогичное замечание – относительно вычисления коэффициентов

и

.

3.1.2. Быстрое преобразование Фурье.

Тригонометрическая интерполяция. Дискретное преобразование.

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

Пусть f(x) – периодическая функция с периодом 1 – разложена в ряд Фурье

, (1)

причем

. (2)

Здесь i – мнимая единица.

Рассмотрим значение этой функции на сетке из точек , где l, N целые, N фиксировано, и обозначим

. Если

, где k целое, то

, где kl целое. Следовательно,

(3)

в узлах сетки. Поэтому если функция f(x) рассматривается в узлах сетки , то в соотношении (1) можно привести подобные члены

, (4)

где

. (5)

Лемма. При , определяемых (5), соотношение (4) остается в силе, если пределы суммирования [0, N-1] заменить на [m,N-1+m], где m – любое целое.

Если с самого начала была задана функция, определенная только на сетке, то на этой сетке ее можно также представить в форме (1). Действительно, такую функцию можно продолжить на всю прямую, доопределив ее между узлами сетки путем линейной интерполяции. Для непрерывной кусочно-дифференцируемой функции выполняется (2), поэтому в точках сетки после приведения подобных членов получим (4).

Определим скалярное произведение для функции на сетке следующим образом:

.

(Множитель введен для согласованности получаемых соотношений с непрерывным случаем: если f(x) и g(x) – непрерывные функции на отрезке [0,1], то вследствие интегрируемости f(x)g(x) по Риману

при ). Функции

при

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

.

При , суммируя геометрическую прогрессию, имеем

(при знаменатель отличен от 0). Поскольку

, то в итоге имеем

при

. (6)

Умножая (4) скалярно на , получим равенство

(7)

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

,

поэтому

при и фиксированном j.

Покажем, что соотношение

(8)

в общем случае не имеет места. Пусть . Из (4) получаем

, остальные

. Таким образом, правая часть (8) есть

. Она совпадает с f(x) в точках

, но, как правило, далека от нее вне этих точек.

Воспользовавшись утверждением леммы, перепишем (4) в виде

. (9)

Если f(x) – достаточно гладкая функция, то величины с ростом j убывают быстро, поэтому

при малых q. Кроме того, при гладкой f(x) величины

и

малы при больших q.

Напомним, что это приближенное равенство обращается в точное равенство в точках сетки. Способ аппроксимации

Носит название тригонометрической интерполяции. Соотношение (9) называют конечным или дискретным рядом Фурье, а коэффициенты - дискретными коэффициентами Фурье.

Игнорирование установленного нами факта о равенстве функций и

в узлах сетки при

часто являются источником получения неверных соотношений.

Существует соответствие между задачей приближения функций линейными комбинациями Чебышева и тригонометрическим многочленами. Пусть на отрезке [-1,1] функция f(x) приближается линейными комбинациями . Замена переменных x=cost сводит исходную задачу к задаче приближения функции f(cost) линейной комбинацией

.

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

.

Следовательно, задача наилучшего приближения f(x) в норме, соответствующей скалярному произведению , эквивалентна задаче приближения

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

. Точно так же существует соответствие в случае задач интерполяции и наилучшего приближения в равномерной метрике. Задача интерполирования функции многочленом по узлам

- нулям многочлена Чебышева

- после такой замены сводится к задаче интерполирования функции f(cost) при помощи тригонометрического многочлена

по узлам

, образующим равномерную сетку.

3.1.2.3. Быстрое преобразование Фурье.

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

Является составной частью решения многих задач решения многих задач. Непосредственное осуществление этих преобразований по формулам (4), (7) требует арифметических операций. Рассмотрим вопрос о возможности сокращение этого числа. Для определенности речь пойдет о вычислении коэффициентов

по заданным значениям функции. Идея построения алгоритмов быстрого преобразования Фурье опирается то, что при составном N в слагаемых правой части (7) можно выделить группы, которые входят в выражения различных коэффициентов

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

Рассмотрим сначала случай . Представим q, j, лежащие в пределах

, в виде

, где

. Имеем цепочку соотношений

.

Из равенства

и предыдущего соотношения получим

,

где

.

Непосредственное вычисление всех требует

арифметических операций, а последующее вычисление

- еще

операций. Поэтому при

общее число операций составит

. Точно так же при

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

, для которого общее число операций не превосходит

, здесь С – постоянная, не зависящая от N. Выпишем соответствующие расчетные формулы для наиболее употребительного случая

. Представим числа q, l в виде

,

где . Величину

представим в виде

,

где s - целое, равное сумме всех слагаемых вида , которых

. Очевидно, что

, поэтому

После перегруппировки слагаемых имеем

Это соотношение можно записать в виде последовательности рекуррентных соотношений

где

Переход от каждой совокупности к совокупности

требует O(N) арифметических и логических операций; всего таких шагов r, поэтому общее число операций имеет порядок

.

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

используются значения

,

. В частности, при m=1 величина

принимает значения +1 или -1. Для вычисления значений

потребуются еще значения

при нечетных j, удовлетворяющих неравенству

. Их можно вычислить через уже вычисленные до этого величины, в частности, при помощи соотношений

где, в свою очередь,

при .

В ряде случаев удается еще уменьшить число операций. Один из таких случаев упоминался выше: дана вещественная функция , известная в точках

; требуется найти коэффициенты интерполяционного многочлена

.

Другой случай: при четном N заданы значения функции

в точках ; нужно определить коэффициенты

.

3.1.3. Расчет коэффициентов на ЭВМ.

Было запрограммировано два метода расчета коэффициентов на языке Паскаль:

по схеме Рунге;

метод трапеций.

3.1.3.1. Схема Рунге.

Расчет ведется для двенадцати орт. Для большего количества ординат алгоритм остается аналогичным с небольшими корректировками в основной части программы (необходимо заменить вычислительные формулы для коэффициентов). См. приложение 1.

3.1.3.2. Метод трапеций.

Метод трапеций был выбран по причине того, что схема Рунге основана на вычислении коэффициентов Фурье методом трапеций и является лишь результатом удачной манипуляции.. См. приложение 2.

3.1.3.3. Сравнение методов.

Если сравнивать две программы то необходимо заметить, что причиной того что мы отказались во второй программе от непосредственного применения схемы Рунге заключается в том, что она является довольно громоздкой и, несмотря на то, что схема Рунге требует меньшее количество вычислительных операций ( +2n), чем прямой метод трапеций (

), в то же время при вычислении на ЭВМ затрачивается большой объем памяти для хранения промежуточных данных (u,v,p,…).

Метод Рунге скорее удобен для вычисления вручную, но менее актуален в программировании.

Если говорить о нахождении более оптимального метода расчета коэффициентов Фурье на ЭВМ, то таким является вышеописанное быстрое преобразование Фурье. Он позволяет сократить количество операций до . В сравнении с вышеописанными методами он является более приемлемым. Способы его алгоритмизации были разработаны и подробно описаны в работе «Numerical recipes in C: The art of scientific computing»-Cambridge unv.,1992.

Сам алгоритм лишь упоминается в курсовой работе, потому что количество операций Б.П.Ф. сопоставимо со С.Р., только Б.П.Ф. является более гибким (в С.Р необходимо вводить n кратное 12-ти значений функции, а чтобы уменьшить погрешность необходимо вносить изменения в основную программу для увлечения количества исходных данных).

Характеристики

Список файлов курсовой работы