Реферат: Ряды Фурье. Численные методы расчета коэффициентов

--PAGE_BREAK--
V

-550

2500

-3300

-2950

-3850



<img width=«16» height=«15» src=«ref-1_826142619-89.coolpic» v:shapes="_x0000_i1126">

-3500

-1350

-3300

<img width=«15» height=«19» src=«ref-1_826142708-89.coolpic» v:shapes="_x0000_i1127">

2400

6350





Теперь по формулам (12):

<img width=«376» height=«168» src=«ref-1_826142797-2527.coolpic» v:shapes="_x0000_i1128"> <img width=«81» height=«168» src=«ref-1_826145324-742.coolpic» v:shapes="_x0000_i1129">

Таким образом,

<img width=«572» height=«21» src=«ref-1_826146066-792.coolpic» v:shapes="_x0000_i1130"><img width=«12» height=«23» src=«ref-1_826129781-73.coolpic» v:shapes="_x0000_i1131"><img width=«12» height=«23» src=«ref-1_826129781-73.coolpic» v:shapes="_x0000_i1132">

Объединим члены, содержащие косинус и синус одного и того же угла:

<img width=«497» height=«24» src=«ref-1_826147004-775.coolpic» v:shapes="_x0000_i1133">

Мы видим, что наиболее сильное влияние здесь оказывает вторая гармоника.

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

Сначала рассмотрим функцию <img width=«36» height=«21» src=«ref-1_826147779-126.coolpic» v:shapes="_x0000_i1134">, которую в промежутке <img width=«43» height=«23» src=«ref-1_826147905-156.coolpic» v:shapes="_x0000_i1135"> задается формулой

<img width=«232» height=«41» src=«ref-1_826148061-461.coolpic» v:shapes="_x0000_i1136">,

А для остальных значений x определяется по закону периодичности

<img width=«117» height=«21» src=«ref-1_826148522-232.coolpic» v:shapes="_x0000_i1137">.

Вычислим табличку:



x



<img width=«17» height=«41» src=«ref-1_826148754-119.coolpic» v:shapes="_x0000_i1138">

<img width=«17» height=«41» src=«ref-1_826148873-116.coolpic» v:shapes="_x0000_i1139">

<img width=«17» height=«41» src=«ref-1_826148989-117.coolpic» v:shapes="_x0000_i1140">

<img width=«27» height=«41» src=«ref-1_826149106-139.coolpic» v:shapes="_x0000_i1141">

<img width=«25» height=«41» src=«ref-1_826149245-136.coolpic» v:shapes="_x0000_i1142">

<img width=«15» height=«15» src=«ref-1_826149381-89.coolpic» v:shapes="_x0000_i1143">

<img width=«27» height=«41» src=«ref-1_826149470-140.coolpic» v:shapes="_x0000_i1144">

<img width=«27» height=«41» src=«ref-1_826149610-139.coolpic» v:shapes="_x0000_i1145">

<img width=«25» height=«41» src=«ref-1_826149749-137.coolpic» v:shapes="_x0000_i1146">

<img width=«25» height=«41» src=«ref-1_826149886-135.coolpic» v:shapes="_x0000_i1147">

<img width=«31» height=«41» src=«ref-1_826150021-150.coolpic» v:shapes="_x0000_i1148">

2<img width=«15» height=«15» src=«ref-1_826149381-89.coolpic» v:shapes="_x0000_i1149">

y



0.400

0.582

0.589

0.465

0.255



-0.255

-0.465

-0.589

-0.582

-0.400





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

<img width=«127» height=«21» src=«ref-1_826150260-237.coolpic» v:shapes="_x0000_i1150">

По схеме Рунге по этим значениям yнайдем:

b1=0.608; b2=0.076; b3=0.022;

все числа <img width=«16» height=«24» src=«ref-1_826150497-94.coolpic» v:shapes="_x0000_i1151">, а с ними и все коэффициенты <img width=«19» height=«24» src=«ref-1_826150591-97.coolpic» v:shapes="_x0000_i1152"> оказываются нулями.

В то же время формулы (10) непосредственно дают (с помощью трехкратного интегрирования по частям):

<img width=«318» height=«48» src=«ref-1_826150688-706.coolpic» v:shapes="_x0000_i1153">,

Так что

<img width=«116» height=«41» src=«ref-1_826151394-283.coolpic» v:shapes="_x0000_i1154">; <img width=«127» height=«41» src=«ref-1_826151677-302.coolpic» v:shapes="_x0000_i1155">; <img width=«125» height=«41» src=«ref-1_826151979-298.coolpic» v:shapes="_x0000_i1156">.

Совпадение превосходное!

3) Однако далеко не всегда получается столь точный результат. В виде второго примера мы возьмем функцию с периодом <img width=«24» height=«19» src=«ref-1_826119362-106.coolpic» v:shapes="_x0000_i1157">, которая в промежутке <img width=«43» height=«23» src=«ref-1_826147905-156.coolpic» v:shapes="_x0000_i1158"> определяется так:

<img width=«152» height=«41» src=«ref-1_826152539-332.coolpic» v:shapes="_x0000_i1159">.

Пользуясь тождеством:

<img width=«127» height=«21» src=«ref-1_826150260-237.coolpic» v:shapes="_x0000_i1160">,

составим таблицу:



x



<img width=«17» height=«41» src=«ref-1_826148754-119.coolpic» v:shapes="_x0000_i1161">

<img width=«17» height=«41» src=«ref-1_826148873-116.coolpic» v:shapes="_x0000_i1162">

<img width=«17» height=«41» src=«ref-1_826148989-117.coolpic» v:shapes="_x0000_i1163">

<img width=«27» height=«41» src=«ref-1_826149106-139.coolpic» v:shapes="_x0000_i1164">

<img width=«25» height=«41» src=«ref-1_826149245-136.coolpic» v:shapes="_x0000_i1165">

<img width=«15» height=«15» src=«ref-1_826149381-89.coolpic» v:shapes="_x0000_i1166">

<img width=«27» height=«41» src=«ref-1_826149470-140.coolpic» v:shapes="_x0000_i1167">

<img width=«27» height=«41» src=«ref-1_826149610-139.coolpic» v:shapes="_x0000_i1168">

<img width=«25» height=«41» src=«ref-1_826149749-137.coolpic» v:shapes="_x0000_i1169">

<img width=«25» height=«41» src=«ref-1_826149886-135.coolpic» v:shapes="_x0000_i1170">

<img width=«31» height=«41» src=«ref-1_826150021-150.coolpic» v:shapes="_x0000_i1171">

2<img width=«15» height=«15» src=«ref-1_826149381-89.coolpic» v:shapes="_x0000_i1172">

y

1

0,694

0,444

0,250

0,111

0,028



0,028

0,111

0,250

0,444

0,694

1

Тогда по схеме Рунге

<img width=«296» height=«24» src=«ref-1_826154614-451.coolpic» v:shapes="_x0000_i1173">

числа же <img width=«16» height=«24» src=«ref-1_826155065-91.coolpic» v:shapes="_x0000_i1174"> и коэффициенты <img width=«20» height=«24» src=«ref-1_826155156-104.coolpic» v:shapes="_x0000_i1175">  — на этот раз нули. Точные значения коэффициентов будут:

<img width=«296» height=«101» src=«ref-1_826155260-1181.coolpic» v:shapes="_x0000_i1176">

в частности,

<img width=«109» height=«41» src=«ref-1_826156441-265.coolpic» v:shapes="_x0000_i1177">; <img width=«111» height=«41» src=«ref-1_826156706-264.coolpic» v:shapes="_x0000_i1178">; <img width=«117» height=«41» src=«ref-1_826156970-285.coolpic» v:shapes="_x0000_i1179">.

Таким образом, если для первых двух коэффициентов относительная погрешность не превосходит 1,5-2 %, то для последующих она достигнет10% и даже 20%! Ясно, что для повышения этой точности нужно брать больше ординат.

3.1.1.3. Схема для двадцати четырех ординат.

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

<img width=«103» height=«25» src=«ref-1_826157255-198.coolpic» v:shapes="_x0000_i1180">,

отвечающие значениям аргумента:

<img width=«128» height=«41» src=«ref-1_826157453-354.coolpic» v:shapes="_x0000_i1181">,

или

<img width=«151» height=«24» src=«ref-1_826157807-290.coolpic» v:shapes="_x0000_i1182">.

На этот раз все множители, на которые при приближенном вычислении коэффициентов Фурье приходится умножать ординаты, сведутся к таким:

<img width=«252» height=«24» src=«ref-1_826158097-430.coolpic» v:shapes="_x0000_i1183">

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



ординаты

<img width=«19» height=«24» src=«ref-1_826135904-97.coolpic» v:shapes="_x0000_i1184">

<img width=«17» height=«23» src=«ref-1_826136001-97.coolpic» v:shapes="_x0000_i1185">

<img width=«20» height=«23» src=«ref-1_826136098-97.coolpic» v:shapes="_x0000_i1186">

<img width=«19» height=«24» src=«ref-1_826136195-98.coolpic» v:shapes="_x0000_i1187">

<img width=«20» height=«23» src=«ref-1_826136293-98.coolpic» v:shapes="_x0000_i1188">

<img width=«19» height=«24» src=«ref-1_826136391-97.coolpic» v:shapes="_x0000_i1189">

<img width=«19» height=«24» src=«ref-1_826136488-98.coolpic» v:shapes="_x0000_i1190">

<img width=«20» height=«24» src=«ref-1_826136990-97.coolpic» v:shapes="_x0000_i1191">

<img width=«19» height=«24» src=«ref-1_826136891-99.coolpic» v:shapes="_x0000_i1192">

<img width=«19» height=«24» src=«ref-1_826136793-98.coolpic» v:shapes="_x0000_i1193">

<img width=«23» height=«24» src=«ref-1_826136689-104.coolpic» v:shapes="_x0000_i1194">

<img width=«23» height=«23» src=«ref-1_826136586-103.coolpic» v:shapes="_x0000_i1195">

<img width=«23» height=«23» src=«ref-1_826159710-104.coolpic» v:shapes="_x0000_i1196">



<img width=«24» height=«24» src=«ref-1_826159814-106.coolpic» v:shapes="_x0000_i1197">

<img width=«24» height=«23» src=«ref-1_826159920-106.coolpic» v:shapes="_x0000_i1198">

<img width=«24» height=«23» src=«ref-1_826160026-106.coolpic» v:shapes="_x0000_i1199">

<img width=«24» height=«24» src=«ref-1_826160132-107.coolpic» v:shapes="_x0000_i1200">

<img width=«23» height=«24» src=«ref-1_826160239-104.coolpic» v:shapes="_x0000_i1201">

<img width=«23» height=«24» src=«ref-1_826160343-105.coolpic» v:shapes="_x0000_i1202">

<img width=«23» height=«24» src=«ref-1_826160448-104.coolpic» v:shapes="_x0000_i1203">

<img width=«23» height=«24» src=«ref-1_826160552-105.coolpic» v:shapes="_x0000_i1204">

<img width=«23» height=«24» src=«ref-1_826160657-103.coolpic» v:shapes="_x0000_i1205">

<img width=«23» height=«23» src=«ref-1_826160760-105.coolpic» v:shapes="_x0000_i1206">

<img width=«23» height=«24» src=«ref-1_826160865-103.coolpic» v:shapes="_x0000_i1207">



Суммы

<img width=«19» height=«24» src=«ref-1_826137087-98.coolpic» v:shapes="_x0000_i1208">

<img width=«16» height=«23» src=«ref-1_826137185-96.coolpic» v:shapes="_x0000_i1209">

<img width=«19» height=«23» src=«ref-1_826137281-98.coolpic» v:shapes="_x0000_i1210">

<img width=«17» height=«24» src=«ref-1_826137379-97.coolpic» v:shapes="_x0000_i1211">

<img width=«19» height=«23» src=«ref-1_826137476-98.coolpic» v:shapes="_x0000_i1212">

<img width=«17» height=«24» src=«ref-1_826137574-96.coolpic» v:shapes="_x0000_i1213">

<img width=«19» height=«24» src=«ref-1_826137670-98.coolpic» v:shapes="_x0000_i1214">

<img width=«19» height=«24» src=«ref-1_826161649-97.coolpic» v:shapes="_x0000_i1215">

<img width=«17» height=«24» src=«ref-1_826161746-97.coolpic» v:shapes="_x0000_i1216">

<img width=«19» height=«24» src=«ref-1_826161843-98.coolpic» v:shapes="_x0000_i1217">

<img width=«23» height=«24» src=«ref-1_826161941-104.coolpic» v:shapes="_x0000_i1218">

<img width=«21» height=«23» src=«ref-1_826162045-103.coolpic» v:shapes="_x0000_i1219">

<img width=«23» height=«23» src=«ref-1_826162148-103.coolpic» v:shapes="_x0000_i1220">

разности



<img width=«16» height=«23» src=«ref-1_826137768-93.coolpic» v:shapes="_x0000_i1221">

<img width=«17» height=«23» src=«ref-1_826137861-95.coolpic» v:shapes="_x0000_i1222">

<img width=«17» height=«24» src=«ref-1_826137956-94.coolpic» v:shapes="_x0000_i1223">

<img width=«17» height=«23» src=«ref-1_826138050-95.coolpic» v:shapes="_x0000_i1224">

<img width=«17» height=«24» src=«ref-1_826138145-94.coolpic» v:shapes="_x0000_i1225">

<img width=«17» height=«24» src=«ref-1_826162722-95.coolpic» v:shapes="_x0000_i1226">

<img width=«17» height=«24» src=«ref-1_826162817-94.coolpic» v:shapes="_x0000_i1227">

<img width=«17» height=«24» src=«ref-1_826162911-94.coolpic» v:shapes="_x0000_i1228">

<img width=«17» height=«24» src=«ref-1_826163005-94.coolpic» v:shapes="_x0000_i1229">

<img width=«21» height=«24» src=«ref-1_826163099-100.coolpic» v:shapes="_x0000_i1230">

<img width=«20» height=«23» src=«ref-1_826163199-100.coolpic» v:shapes="_x0000_i1231">


    продолжение
--PAGE_BREAK--


Суммы

<img width=«19» height=«24» src=«ref-1_826137087-98.coolpic» v:shapes="_x0000_i1232">

<img width=«16» height=«23» src=«ref-1_826137185-96.coolpic» v:shapes="_x0000_i1233">

<img width=«19» height=«23» src=«ref-1_826137281-98.coolpic» v:shapes="_x0000_i1234">

<img width=«17» height=«24» src=«ref-1_826137379-97.coolpic» v:shapes="_x0000_i1235">

<img width=«19» height=«23» src=«ref-1_826137476-98.coolpic» v:shapes="_x0000_i1236">

<img width=«17» height=«24» src=«ref-1_826137574-96.coolpic» v:shapes="_x0000_i1237">

<img width=«19» height=«24» src=«ref-1_826137670-98.coolpic» v:shapes="_x0000_i1238">

<img width=«23» height=«23» src=«ref-1_826162148-103.coolpic» v:shapes="_x0000_i1239">

<img width=«21» height=«23» src=«ref-1_826162045-103.coolpic» v:shapes="_x0000_i1240">

<img width=«23» height=«24» src=«ref-1_826161941-104.coolpic» v:shapes="_x0000_i1241">

<img width=«19» height=«24» src=«ref-1_826161843-98.coolpic» v:shapes="_x0000_i1242">

<img width=«17» height=«24» src=«ref-1_826161746-97.coolpic» v:shapes="_x0000_i1243">

<img width=«19» height=«24» src=«ref-1_826161649-97.coolpic» v:shapes="_x0000_i1244">



Суммы

<img width=«20» height=«24» src=«ref-1_826164582-100.coolpic» v:shapes="_x0000_i1245">

<img width=«19» height=«23» src=«ref-1_826164682-97.coolpic» v:shapes="_x0000_i1246">

<img width=«20» height=«23» src=«ref-1_826164779-100.coolpic» v:shapes="_x0000_i1247">

<img width=«20» height=«24» src=«ref-1_826164879-99.coolpic» v:shapes="_x0000_i1248">

<img width=«20» height=«23» src=«ref-1_826164978-100.coolpic» v:shapes="_x0000_i1249">

<img width=«20» height=«24» src=«ref-1_826165078-100.coolpic» v:shapes="_x0000_i1250">

<img width=«20» height=«24» src=«ref-1_826165178-100.coolpic» v:shapes="_x0000_i1251">

разности

<img width=«19» height=«24» src=«ref-1_826165278-97.coolpic» v:shapes="_x0000_i1252">

<img width=«17» height=«23» src=«ref-1_826165375-96.coolpic» v:shapes="_x0000_i1253">

<img width=«19» height=«23» src=«ref-1_826165471-98.coolpic» v:shapes="_x0000_i1254">

<img width=«19» height=«24» src=«ref-1_826165569-98.coolpic» v:shapes="_x0000_i1255">

<img width=«19» height=«23» src=«ref-1_826165667-98.coolpic» v:shapes="_x0000_i1256">

<img width=«19» height=«24» src=«ref-1_826165765-96.coolpic» v:shapes="_x0000_i1257">





Суммы

<img width=«16» height=«23» src=«ref-1_826137768-93.coolpic» v:shapes="_x0000_i1258">

<img width=«17» height=«23» src=«ref-1_826137861-95.coolpic» v:shapes="_x0000_i1259">

<img width=«17» height=«24» src=«ref-1_826137956-94.coolpic» v:shapes="_x0000_i1260">

<img width=«17» height=«23» src=«ref-1_826138050-95.coolpic» v:shapes="_x0000_i1261">

<img width=«17» height=«24» src=«ref-1_826138145-94.coolpic» v:shapes="_x0000_i1262">

<img width=«17» height=«24» src=«ref-1_826162722-95.coolpic» v:shapes="_x0000_i1263">

<img width=«20» height=«23» src=«ref-1_826163199-100.coolpic» v:shapes="_x0000_i1264">

<img width=«21» height=«24» src=«ref-1_826163099-100.coolpic» v:shapes="_x0000_i1265">

<img width=«17» height=«24» src=«ref-1_826163005-94.coolpic» v:shapes="_x0000_i1266">

<img width=«17» height=«24» src=«ref-1_826162911-94.coolpic» v:shapes="_x0000_i1267">

<img width=«17» height=«24» src=«ref-1_826162817-94.coolpic» v:shapes="_x0000_i1268">



Суммы

<img width=«13» height=«23» src=«ref-1_826166909-91.coolpic» v:shapes="_x0000_i1269">

<img width=«16» height=«23» src=«ref-1_826167000-91.coolpic» v:shapes="_x0000_i1270">

<img width=«15» height=«24» src=«ref-1_826167091-90.coolpic» v:shapes="_x0000_i1271">

<img width=«16» height=«23» src=«ref-1_826167181-92.coolpic» v:shapes="_x0000_i1272">

<img width=«15» height=«24» src=«ref-1_826167273-91.coolpic» v:shapes="_x0000_i1273">

<img width=«15» height=«24» src=«ref-1_826167364-91.coolpic» v:shapes="_x0000_i1274">

разности

<img width=«16» height=«23» src=«ref-1_826139014-92.coolpic» v:shapes="_x0000_i1275">

<img width=«17» height=«23» src=«ref-1_826139106-91.coolpic» v:shapes="_x0000_i1276">

<img width=«16» height=«24» src=«ref-1_826139197-92.coolpic» v:shapes="_x0000_i1277">

<img width=«17» height=«23» src=«ref-1_826167730-92.coolpic» v:shapes="_x0000_i1278">

<img width=«17» height=«24» src=«ref-1_826167822-91.coolpic» v:shapes="_x0000_i1279">





Суммы

<img width=«20» height=«24» src=«ref-1_826164582-100.coolpic» v:shapes="_x0000_i1280">

<img width=«19» height=«23» src=«ref-1_826164682-97.coolpic» v:shapes="_x0000_i1281">

<img width=«20» height=«23» src=«ref-1_826164779-100.coolpic» v:shapes="_x0000_i1282">

<img width=«20» height=«24» src=«ref-1_826164879-99.coolpic» v:shapes="_x0000_i1283">

<img width=«20» height=«24» src=«ref-1_826165178-100.coolpic» v:shapes="_x0000_i1284">

<img width=«20» height=«24» src=«ref-1_826165078-100.coolpic» v:shapes="_x0000_i1285">

<img width=«20» height=«23» src=«ref-1_826164978-100.coolpic» v:shapes="_x0000_i1286">



Суммы

<img width=«17» height=«24» src=«ref-1_826168609-100.coolpic» v:shapes="_x0000_i1287">

<img width=«16» height=«23» src=«ref-1_826168709-98.coolpic» v:shapes="_x0000_i1288">

<img width=«19» height=«23» src=«ref-1_826168807-102.coolpic» v:shapes="_x0000_i1289">

<img width=«17» height=«24» src=«ref-1_826168909-100.coolpic» v:shapes="_x0000_i1290">

разности

<img width=«15» height=«24» src=«ref-1_826169009-95.coolpic» v:shapes="_x0000_i1291">

<img width=«13» height=«23» src=«ref-1_826169104-92.coolpic» v:shapes="_x0000_i1292">

<img width=«15» height=«23» src=«ref-1_826169196-94.coolpic» v:shapes="_x0000_i1293">



разности

<img width=«16» height=«23» src=«ref-1_826139014-92.coolpic» v:shapes="_x0000_i1294">

<img width=«17» height=«23» src=«ref-1_826139106-91.coolpic» v:shapes="_x0000_i1295">

<img width=«16» height=«24» src=«ref-1_826139197-92.coolpic» v:shapes="_x0000_i1296">

<img width=«17» height=«24» src=«ref-1_826167822-91.coolpic» v:shapes="_x0000_i1297">

<img width=«17» height=«23» src=«ref-1_826167730-92.coolpic» v:shapes="_x0000_i1298">



суммы

<img width=«20» height=«23» src=«ref-1_826169748-100.coolpic» v:shapes="_x0000_i1299">

<img width=«21» height=«23» src=«ref-1_826169848-102.coolpic» v:shapes="_x0000_i1300">

<img width=«21» height=«24» src=«ref-1_826169950-101.coolpic» v:shapes="_x0000_i1301">

разности

<img width=«16» height=«23» src=«ref-1_826170051-96.coolpic» v:shapes="_x0000_i1302">

<img width=«19» height=«23» src=«ref-1_826170147-97.coolpic» v:shapes="_x0000_i1303">





Отметим, что с величинами q и r нет надобности проделывать сложения и вычитания.

Теперь через полученные указанным путем величины k, l, m, n, q и r коэффициентов Фурье выразятся следующим образом:

<img width=«523» height=«341» src=«ref-1_826170244-5607.coolpic» v:shapes="_x0000_i1304">

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

Нужно обратить внимание на одну подробность. Для получения коэффициентов <img width=«17» height=«23» src=«ref-1_826175851-96.coolpic» v:shapes="_x0000_i1305"> и <img width=«19» height=«24» src=«ref-1_826175947-97.coolpic» v:shapes="_x0000_i1306"> нужно отдельно вычислить те выражения, которые поставлены в квадратные скобки, а затем сложить их (для нахождения <img width=«17» height=«23» src=«ref-1_826175851-96.coolpic» v:shapes="_x0000_i1307">) и вычесть (для нахождения <img width=«19» height=«24» src=«ref-1_826175947-97.coolpic» v:shapes="_x0000_i1308">). Аналогичное замечание – относительно вычисления коэффициентов <img width=«16» height=«23» src=«ref-1_826176237-99.coolpic» v:shapes="_x0000_i1309"> и <img width=«17» height=«24» src=«ref-1_826176336-98.coolpic» v:shapes="_x0000_i1310">.

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

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

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

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

<img width=«164» height=«47» src=«ref-1_826176434-517.coolpic» v:shapes="_x0000_i1311">, (1)

причем

<img width=«76» height=«47» src=«ref-1_826176951-371.coolpic» v:shapes="_x0000_i1312">. (2)

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

Рассмотрим значение этой функции на сетке из точек <img width=«60» height=«32» src=«ref-1_826177322-185.coolpic» v:shapes="_x0000_i1313">, где l, N целые, N фиксировано, и обозначим <img width=«71» height=«24» src=«ref-1_826177507-172.coolpic» v:shapes="_x0000_i1314">. Если <img width=«87» height=«23» src=«ref-1_826177679-195.coolpic» v:shapes="_x0000_i1315">, где k целое, то <img width=«152» height=«24» src=«ref-1_826177874-278.coolpic» v:shapes="_x0000_i1316">, где kl целое. Следовательно,

<img width=«177» height=«23» src=«ref-1_826178152-343.coolpic» v:shapes="_x0000_i1317"> (3)

в узлах сетки. Поэтому если функция f(x) рассматривается в узлах сетки <img width=«16» height=«24» src=«ref-1_826178495-94.coolpic» v:shapes="_x0000_i1318">, то в соотношении (1) можно привести подобные члены

<img width=«172» height=«47» src=«ref-1_826178589-556.coolpic» v:shapes="_x0000_i1319">, (4)

где

<img width=«95» height=«45» src=«ref-1_826179145-357.coolpic» v:shapes="_x0000_i1320">. (5)

Лемма. При <img width=«21» height=«25» src=«ref-1_826179502-108.coolpic» v:shapes="_x0000_i1321">, определяемых (5), соотношение (4) остается в силе, если пределы суммирования [0, N-1] заменить на [m,N-1+m], где m – любое целое.

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

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

<img width=«124» height=«45» src=«ref-1_826179610-507.coolpic» v:shapes="_x0000_i1322">.

(Множитель <img width=«29» height=«32» src=«ref-1_826180117-137.coolpic» v:shapes="_x0000_i1323"> введен для согласованности получаемых соотношений с непрерывным случаем: если f(x) и g(x) – непрерывные функции на отрезке [0,1], то вследствие интегрируемости f(x)g(x) по Риману

<img width=«151» height=«51» src=«ref-1_826180254-526.coolpic» v:shapes="_x0000_i1324">

при <img width=«53» height=«19» src=«ref-1_826180780-140.coolpic» v:shapes="_x0000_i1325">). Функции <img width=«137» height=«25» src=«ref-1_826180920-439.coolpic» v:shapes="_x0000_i1326"> при <img width=«68» height=«21» src=«ref-1_826181359-170.coolpic» v:shapes="_x0000_i1327"> образуют ортогональную систему относительно введенного таким образом скалярного произведения. Действительно,

<img width=«211» height=«45» src=«ref-1_826181529-756.coolpic» v:shapes="_x0000_i1328">.

При <img width=«39» height=«20» src=«ref-1_826182285-121.coolpic» v:shapes="_x0000_i1329">, суммируя геометрическую прогрессию, имеем

<img width=«232» height=«67» src=«ref-1_826182406-992.coolpic» v:shapes="_x0000_i1330">

(при <img width=«121» height=«21» src=«ref-1_826183398-230.coolpic» v:shapes="_x0000_i1331"> знаменатель отличен от 0). Поскольку <img width=«79» height=«25» src=«ref-1_826183628-295.coolpic» v:shapes="_x0000_i1332">, то в итоге имеем

<img width=«87» height=«27» src=«ref-1_826183923-330.coolpic» v:shapes="_x0000_i1333"> при <img width=«81» height=«21» src=«ref-1_826184253-184.coolpic» v:shapes="_x0000_i1334">. (6)

Умножая (4) скалярно на <img width=«20» height=«25» src=«ref-1_826184437-101.coolpic» v:shapes="_x0000_i1335">, получим равенство

<img width=«240» height=«45» src=«ref-1_826184538-775.coolpic» v:shapes="_x0000_i1336"> (7)

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

<img width=«140» height=«51» src=«ref-1_826185313-478.coolpic» v:shapes="_x0000_i1337">,

поэтому

<img width=«213» height=«51» src=«ref-1_826185791-578.coolpic» v:shapes="_x0000_i1338">

при <img width=«53» height=«19» src=«ref-1_826180780-140.coolpic» v:shapes="_x0000_i1339"> и фиксированном j.

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

<img width=«168» height=«47» src=«ref-1_826186509-546.coolpic» v:shapes="_x0000_i1340"> (8)

в общем случае не имеет места. Пусть <img width=«177» height=«24» src=«ref-1_826187055-321.coolpic» v:shapes="_x0000_i1341">. Из (4) получаем <img width=«124» height=«24» src=«ref-1_826187376-230.coolpic» v:shapes="_x0000_i1342">, остальные <img width=«47» height=«25» src=«ref-1_826187606-139.coolpic» v:shapes="_x0000_i1343">. Таким образом, правая часть (8) есть <img width=«164» height=«24» src=«ref-1_826187745-426.coolpic» v:shapes="_x0000_i1344">. Она совпадает с f(x) в точках <img width=«16» height=«24» src=«ref-1_826178495-94.coolpic» v:shapes="_x0000_i1345">, но, как правило, далека от нее вне этих точек.

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

<img width=«167» height=«41» src=«ref-1_826188265-544.coolpic» v:shapes="_x0000_i1346">. (9)

Если f(x) – достаточно гладкая функция, то величины <img width=«25» height=«29» src=«ref-1_826188809-128.coolpic» v:shapes="_x0000_i1347"> с ростом j убывают быстро, поэтому <img width=«53» height=«25» src=«ref-1_826188937-156.coolpic» v:shapes="_x0000_i1348"> при малых q. Кроме того, при гладкой f(x) величины <img width=«21» height=«25» src=«ref-1_826179502-108.coolpic» v:shapes="_x0000_i1349"> и <img width=«19» height=«25» src=«ref-1_826189201-100.coolpic» v:shapes="_x0000_i1350"> малы при больших q.

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

<img width=«188» height=«41» src=«ref-1_826189301-582.coolpic» v:shapes="_x0000_i1351">

Носит название тригонометрической интерполяции. Соотношение (9) называют конечным или дискретным рядом Фурье, а коэффициенты <img width=«21» height=«25» src=«ref-1_826179502-108.coolpic» v:shapes="_x0000_i1352">  — дискретными коэффициентами Фурье.

Игнорирование установленного нами факта о равенстве функций <img width=«81» height=«23» src=«ref-1_826189991-208.coolpic» v:shapes="_x0000_i1353"> и <img width=«83» height=«23» src=«ref-1_826190199-209.coolpic» v:shapes="_x0000_i1354"> в узлах сетки при <img width=«87» height=«23» src=«ref-1_826190408-195.coolpic» v:shapes="_x0000_i1355"> часто являются источником получения неверных соотношений.

Существует соответствие между задачей приближения функций линейными комбинациями Чебышева и тригонометрическим многочленами. Пусть на отрезке [-1,1] функция f(x) приближается линейными комбинациями <img width=«73» height=«47» src=«ref-1_826190603-365.coolpic» v:shapes="_x0000_i1356">. Замена переменных x=cost сводит исходную задачу к задаче приближения функции f(cost) линейной комбинацией <img width=«188» height=«47» src=«ref-1_826190968-645.coolpic» v:shapes="_x0000_i1357">.

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

<img width=«316» height=«51» src=«ref-1_826191613-868.coolpic» v:shapes="_x0000_i1358">.

Следовательно, задача наилучшего приближения f(x) в норме, соответствующей скалярному произведению <img width=«47» height=«23» src=«ref-1_826192481-146.coolpic» v:shapes="_x0000_i1359">, эквивалентна задаче приближения <img width=«60» height=«21» src=«ref-1_826192627-160.coolpic» v:shapes="_x0000_i1360"> в норме, соответствующей скалярному произведению <img width=«203» height=«51» src=«ref-1_826192787-569.coolpic» v:shapes="_x0000_i1361">. Точно так же существует соответствие в случае задач интерполяции и наилучшего приближения в равномерной метрике. Задача интерполирования функции многочленом по узлам <img width=«121» height=«41» src=«ref-1_826193356-308.coolpic» v:shapes="_x0000_i1362">  — нулям многочлена Чебышева <img width=«41» height=«24» src=«ref-1_826193664-141.coolpic» v:shapes="_x0000_i1363">- после такой замены сводится к задаче интерполирования функции f(cost) при помощи тригонометрического многочлена <img width=«87» height=«47» src=«ref-1_826193805-395.coolpic» v:shapes="_x0000_i1364"> по узлам <img width=«85» height=«41» src=«ref-1_826194200-246.coolpic» v:shapes="_x0000_i1365">, образующим равномерную сетку.

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

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

<img width=«187» height=«24» src=«ref-1_826194446-316.coolpic» v:shapes="_x0000_i1366">

Является составной частью решения многих задач решения многих задач. Непосредственное осуществление этих преобразований по формулам (4), (7) требует <img width=«49» height=«24» src=«ref-1_826194762-156.coolpic» v:shapes="_x0000_i1367"> арифметических операций. Рассмотрим вопрос о возможности сокращение этого числа. Для определенности речь пойдет о вычислении коэффициентов <img width=«21» height=«25» src=«ref-1_826179502-108.coolpic» v:shapes="_x0000_i1368"> по заданным значениям функции. Идея построения алгоритмов быстрого преобразования Фурье опирается то, что при составном N в слагаемых правой части (7) можно выделить группы, которые входят в выражения различных коэффициентов <img width=«21» height=«25» src=«ref-1_826179502-108.coolpic» v:shapes="_x0000_i1369">    продолжение
--PAGE_BREAK--