1611689564-c292adb9a0ffac330f3ca30cdb684bd6 (826864), страница 9
Текст из файла (страница 9)
Ïîýòîìó, ïåðåãðóïïèðîâàâ ñëàãàåìûå, ìûìîæåì ïðîäîëæèòü ðàâåíñòâî (43) ñëåäóþùèì îáðàçîìAn = A(n1 , n2 ) =ãäå(1)A(n1 , k2 ) =12NpX2 −1A(1) (n1 , k2 )e−iπnk2N,(44)k2 =−p2 +1pX1 −1¡n1 k1¢±fk2 +p2 k1 e−iπ p1 .k1 =−p1 +1Âû÷èñëåíèå îäíîãî âûðàæåíèÿ A(1) (n1 , k2 ) òðåáóåò îò íàñ O(p1 ) àðèôìåòè÷åñêèõ îïåðàöèé ñ ÷èñëàìè ñ ïëàâàþùåé çàïÿòîé. Ïîñêîëüêó ñàìèõýòèõ âûðàæåíèé 2p1 · 2p2 øòóê, òî äëÿ âû÷èñëåíèÿ èõ âñåõ ïîòðåáóåòñÿO(p21 p2 ) îïåðàöèé.
Ïîñëå òîãî êàê âñå âûðàæåíèÿ A(1) (n1 , k2 ) íàéäåíû,äëÿ âû÷èñëåíèÿ îäíîãî âûðàæåíèÿ A(n1 , n2 ) òðåáóåòñÿ O(p2 ) îïåðàöèé.Ñàìèõ æå âûðàæåíèé A(n1 , n2 ) èìååòñÿ 2p1 · 2p2 øòóê. Çíà÷èò, äëÿ íàõîæäåíèÿ èõ âñåõ ïîòðåáóåòñÿ O(p1 p22 ) îïåðàöèé.Îêîí÷àòåëüíî ïîëó÷àåì, ÷òî äëÿ íàõîæäåíèÿ ïðÿìîãî äèñêðåòíîãîïðåîáðàçîâàíèÿ Ôóðüå ïî ôîðìóëàì (44) òðåáóåòñÿ O(p21 p2 ) + O(p1 p22 )îïåðàöèé.  ÷àñòíîñòè, åñëè ñîìíîæèòåëè p1 è p2 √ïðèáëèçèòåëüíî ðàâíû ìåæäó ñîáîé (à çíà÷èò, ïðèáëèçèòåëüíî ðàâíû N ), òî îáùåå ÷èñëîîïåðàöèé ñîñòàâèò O(N 3/2 ).57Âîò ìû è ïðîñëåäèëè, êàê çà ñ÷åò ðàöèîíàëüíîé îðãàíèçàöèè âû÷èñëåíèé óìåíüøèòü êîëè÷åñòâî îïåðàöèé ñ O(N 2 ) â ôîðìóëàõ (41) äîO(N 3/2 ) â ôîðìóëàõ (44). Âìåñòå ñ òåì ëåãêî ïîíÿòü, ÷òî ôîðìóëû (44)íå ÿâëÿþòñÿ ïðåäåëüíî ýêîíîìè÷íûìè: ïðè âû÷èñëåíèè êîýôôèöèåíòîâ A(1) (n1 , k2 ), â ñâîþ î÷åðåäü, ìîæíî âûäåëÿòü íåêîòîðûå âûðàæåíèÿA(2) ïîäîáíî îïèñàííîìó âûøå âûäåëåíèþ âûðàæåíèé A(1) (n1 , k2 ) èçA(n1 , n2 ); èç A(2) ìîæíî ïîäîáíûì îáðàçîì âûäåëÿòü âûðàæåíèÿ A(3)è ò.
ä. Óñëîæíåííûå òàêèì îáðàçîì âû÷èñëèòåëüíûå ôîðìóëû ïîçâîëÿþò äîâåñòè ÷èñëî îïåðàöèé íåîáõîäèìûõ äëÿ âû÷èñëåíèÿ äèñêðåòíîãîïðåîáðàçîâàíèÿ Ôóðüå äî O(N log2 N ).  ýòîì è ñîñòîèò áûñòðîå ïðåîáðàçîâàíèå Ôóðüå.Áîëåå äåòàëüíîå èçëîæåíèå áûñòðîãî ïðåîáðàçîâàíèÿ Ôóðüå ÷èòàòåëü ìîæåò íàéòè â êíèãå Í. Ñ. Áàõâàëîâà, Í. Ï. Æèäêîâà è Ã. Ì. Êîáåëüêîâà ¾×èñëåííûå ìåòîäû¿. Î äðóãèõ áûñòðûõ àëãîðèòìàõ (íàïðèìåð, îá àëãîðèòìàõ áûñòðîãî óìíîæåíèÿ ÷èñåë) ìîæíî ïðî÷èòàòü âîâòîðîì òîìå êíèãè Ä. Êíóòòà ¾Èñêóññòâî ïðîãðàììèðîâàíèÿ äëÿ ÝÂÌ¿.Âåðíåìñÿ ê ïðèìåðó ñæàòèÿ öèôðîâîé ôîòîãðàôèè, èçîáðàæåííîéíà ìîíèòîðå ñ ðàçðåøåíèåì 1200×1024 ïèêñåëåé.
 ýòîì ñëó÷àå êàæäàÿèç 1024 ñòðîê èìååò äëèíó N = 1200, è íàõîæäåíèå ïðåîáðàçîâàíèÿ Ôóðüå îò íåå ïî ôîðìóëàì (40) òðåáóåò C · 12002 îïåðàöèé, à ïî ôîðìóëàìáûñòðîãî ïðåîáðàçîâàíèÿ Ôóðüå òîëüêî C · 1200 · log2 1200 îïåðàöèé,÷òî ïðèìåðíî â 120 ðàç ìåíüøå. È ýòî ïðè êàæäîì îòêðûòèè èëè ñîõðàíåíèè *.jpg ôàéëà! Íå óäèâèòåëüíî, ÷òî ïðîèçâîäèòåëè ïðîãðàììíîãîîáåñïå÷åíèÿ ñ ãîòîâíîñòüþ èäóò íà óñëîæíåíèå âû÷èñëèòåëüíûõ àëãîðèòìîâ, îáåñïå÷èâàþùèõ òàêîé ðîñò ñêîðîñòè îáðàáîòêè èíôîðìàöèè.58Ïðåäìåòíûé óêàçàòåëüÔîðìà êîìïëåêñíàÿ èíòåãðàëà Ôóðüå18Ôîðìóëà îáðàùåíèÿ 19 Ïóàññîíà 43 Ôóðüå, èíòåãðàëüíàÿ 6Ôîðìóëû îáðàùåíèÿ 19Ôóíêöèÿ áûñòðî óáûâàþùàÿ 26 êóñî÷íî-ãëàäêàÿ 7 îòñ÷åòîâ 45 ôèíèòíàÿ 27Âåñ ìóëüòèèíäåêñà 26Äëèíà ìóëüòèèíäåêñà 26Èíòåãðàë Äèðèõëå 11 Ëàïëàñà 16 Ïóàññîíà äëÿ óðàâíåíèÿ òåïëîïðîâîäíîñòè 51 Ôóðüå 6Êîñèíóñ-ïðåîáðàçîâàíèå Ôóðüå 6 , îáðàòíîå 13 , ïðÿìîå 13Ëåììà ÐèìàíàËåáåãà äëÿ áåñêîíå÷íîãî ïðîìåæóòêà 6Ìåòîä îïåðàòîðíûé 51Ìóëüòèèíäåêñ 26Ïðàâèëî èçìåíåíèÿ ìàñøòàáà 35Ïðåîáðàçîâàíèå Ôóðüå áûñòðî óáûâàþùåé ôóíêöèè, îáðàòíîå 31 , ïðÿìîå 30 áûñòðîå 58 äèñêðåòíîå, îáðàòíîå 53 äèñêðåòíîå, ïðÿìîå 53 îáðàòíîå 18 ïðÿìîå 18Ðàâåíñòâî Ïàðñåâàëÿ 37Ñâåðòêà áûñòðî óáûâàþùèõ ôóíêöèé39Ñèíóñ-ïðåîáðàçîâàíèå Ôóðüå 6 , îáðàòíîå 13 , ïðÿìîå 13Ñóììà ìóëüòèèíäåêñîâ 26Òåîðåìà ÊîòåëüíèêîâàØåííîíà 45 î ïðåäñòàâèìîñòè ôóíêöèè â òî÷êåñâîèì èíòåãðàëîì Ôóðüå 7 î ñäâèãå 34 Ôóáèíè 8Òýòà-ôîðìóëà 45Óçåë ñåòêè 52Óðàâíåíèå òåïëîïðîâîäíîñòè 4859Îòâåòû è óêàçàíèÿ7.
à) f (x) = 2πR−1 +∞(1 + cos πy)(1 − y 2 )−1 cos xy dy ; á) f (x) = 2π −1R +∞sin πy(1 − y ) sin xy dy. 8. à) f (x) = 2π −1 0 y −1 sin y cos xy dy ;0R +∞R +∞á) f (x) = 2π −1 0 y −1 (1 − cos y) sin xy dy. 9. à) f (x) = 2π −1 0 y −2 (yR+∞sin y + cos y − 1) cos xy dy ; á) f (x) = 2π −2 0 y −2 (sin y − y cos y) sin xy dy.R10. à) f (x) = −2π −1 0+∞ y −2 (y sin(2y/3) + 3(cos(2y/3) − 1)) cos xy dy ;R +∞á) f (x) = 2π −2 0 (2y − 3 sin(2y/3)) sin xy dy. 11.
f (y) = e−y , y ≥ 0.R12. f (y) = e−y , y ≥ 0. 13. f (y) = (2/π) 0+∞ (1+x2 )−1 sin xy dx; ýòîò èíòåãðàë íå áåðåòñÿ â ýëåìåíòàðíûõ ôóíêöèÿõ, íî åãî ìîæíî ïðåîáðàçîâàòüR +∞ê âèäó f (y) = [e−y Ei (y) − ey Ei (−y)]/π , ãäå Ei (y) = − −y e−x /x dx.14. Íåò ðåøåíèé. 15. f (y) = 2π −1 y(1+y 2 )−1 , y ≥ 0.
16. f (y) = (sin πy)(1−2y 2 )−1 . 17. f (y) = (y sin πy)(1 − y 2 )−1 . 18. f (y) = 2−1 π −1/2 ye−y /4 , y ≥ 0.−1 −1−1−1−1−119. 2π y sin ay . 20. π (1 − y) sin a(1 − y) + π (1 + y) sin a(1 + y).221. (2π)−1/2 e−y /4 . 22. 21/2 π −1/2 cos(y 2 /2 − π/4). 23. 21/2 π −1/2 cos(π/4 −2y 2 /2). 24. 2π −1 y −1 (1−cos ay). 25. 2π −1 ye−y /2 . 26. π −1 ln |(1+y)/(1−y)|.R +∞Óêàçàíèå. Èñïîëüçóéòå èíòåãðàëû Ôðóëëàíè 0 x−1 [f (ax)−f (bx)] dx =f (0)ln (b/a), ãäå ïðåäïîëàãàåòñÿ, ÷òî a > 0, b > 0, ôóíêöèÿ f íåïðåðûâR +∞íà ïðè x ≥ 0 è èíòåãðàë A x−1 f (x) dx ñõîäèòñÿ õîòÿ áû äëÿ îäíîãîA.
30. F− [eiax f (x)](y) = F− [f ](y + a). 31. F− [f (x − a)](y) = eiax F− [f ](y).R +∞2 −10∨∨32. Ôîðìóëà íå èçìåíÿåòñÿ. 33. F− [f (x) sin ax](y) = [f (y + a)− f∨∨(y − a)]/(2i). 36. fb(y) =f (y) = 21/2 π −1/2 y −1 sin y . 37. fb(y) = − f (y) =∨i21/2 π −1/2 y −2 (y cos y − sin y). 38. fb(y) =f (y) = 21/2 π −1/2 y −2 (cos y −∨1 + y sin y). 39. fb(y) =f (y) = 21/2 π −1/2 y −3 (2y cos y + (y 2 − 2) sin y).∨40. fb(y)= f (y)=e−(y∨22ch ay . 41.
fb(y)=− f (y)=−ie−(y +a )/2 sh ay .∨∨242. fb(y) =f (−y) = e−(y+a) /2 . 43. fb(y) = − f (y) = −i81/2 π −1/2 ay(y 2 +∨∨a2 )−2 . 44. fb(y) =f (y) = 81/2 π −1/2 y 2 (y 2 + 1)−2 . 45. fb(y) = − f (y) =2+a2 )/2∨i81/2 π −1/2 y(1−3y 2 )(y 2 +1)−3 . 46. fb(y) =f (−y) = 21/2 π −1/2 (1−y)−1 sin πy .∨∨47. fb(y) =f (y) = 21/2 π −1/2 y(1 − y 2 )−1 sin πy . 48. fb(y) = − f (y) =∨−i21/2 π −1/2 (1 − y 2 )−1 sin πy . 49. fb(y) =f (−y) = i(2π)−1/2 (1 − y)−1 (1 +∨∨e−iπy ). 50. fb(y) =f (y) = 21/2 π −1/2 y −1 (sin 2y − sin y). 51. fb(y) =f (y) =∨2−1/2 π 1/2 e−|y| . 52. fb(y) = − f (y) = −i2−1/2 π 1/2 y 3 e−|y| . 65.
xH(x).66. (x+1)H(x+1). 67. (2−|x|)H(2−|x|). 68. x3 H(x)/3. 69. (1−cos x)H(x).6070. (x2 −4 sin2 (x/2))H(x). 71. (3x2 +6 cos x−6)H(x). 72. (sh x−sin x)H(x)/2.273. (1 + |x|)e−|x| . 74. −4−1 a−1/2 xe−ax /2 . 81. πa−1 (ea/2 + e−a/2 R)(ea/2 −te−a/2 )−1 = πa−1 cth a/2. 82. u(t, x) = [f (x−at)+f (x+at)]/2+2−1 0 [g(x−R+∞az) + g(x + az)] dz . 83. f (x, y) = π −1 −∞ y[(x − z)2 + y 2 ]−1 g(z) dz. Óêàçàíèå. Óáåäèòåñü, ÷òî ïðÿìîå ïðåîáðàçîâàíèå Ôóðüå fb(z, y) ôóíêöèè fïî ïåðåìåííîé x èìååò âèä gb(z)e−y|z| .61ÎãëàâëåíèåÏðåäèñëîâèå .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1. Èíòåãðàë Ôóðüå êàê ïðåäåëüíàÿ ôîðìà ðÿäà Ôóðüå . . . . . . . . . 2. Òåîðåìà î ïðåäñòàâèìîñòè ôóíêöèè â òî÷êå ñâîèì èíòåãðàëîìÔóðüå . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3. Ðàçëîæåíèå íà ïîëóïðÿìîé. Ïðÿìîå è îáðàòíîå ñèíóñ- èêîñèíóñ-ïðåîáðàçîâàíèå Ôóðüå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4. Ïðèìåðû âû÷èñëåíèÿ ñèíóñ- è êîñèíóñ-ïðåîáðàçîâàíèÿÔóðüå è ïðåäñòàâëåíèÿ ôóíêöèè åå èíòåãðàëîì Ôóðüå . . . .
. . . 5. Êîìïëåêñíàÿ ôîðìà èíòåãðàëà Ôóðüå. ÏðåîáðàçîâàíèåÔóðüå. Ôîðìóëà îáðàùåíèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6. Ïðèìåð âû÷èñëåíèÿ ïðåîáðàçîâàíèÿ Ôóðüå . . . . . . . . . . . . . . . . . . 7. Áûñòðî óáûâàþùèå ôóíêöèè. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . 8. Ïðåîáðàçîâàíèå Ôóðüå áûñòðî óáûâàþùèõ ôóíêöèé . . . . . . . . 9. Ðàâåíñòâî Ïàðñåâàëÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10. Ñâåðòêà áûñòðî óáûâàþùèõ ôóíêöèé . . . . . . . . . . . . . . . . . . . . . . 11. Ôîðìóëà Ïóàññîíà . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12. Òåîðåìà Êîòåëüíèêîâà Øåííîíà . . . . . . . . . . . . . . . . . . . . . . . . . 13. Ïðèìåíåíèå ïðåîáðàçîâàíèÿ Ôóðüå ê ðåøåíèþ óðàâíåíèÿòåïëîïðîâîäíîñòè . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14. Íà÷àëüíûå ñâåäåíèÿ î äèñêðåòíîì ïðåîáðàçîâàíèè Ôóðüå . 15. Ïåðâûå ñâåäåíèÿ î áûñòðîì ïðåîáðàçîâàíèè Ôóðüå . . . . . . . .Ïðåäìåòíûé óêàçàòåëü . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . .Îòâåòû è óêàçàíèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .62346121517202630373943454852565960Îòâåòû è óêàçàíèÿ7. à) f (x) = 2πR−1 +∞(1 + cos πy)(1 − y 2 )−1 cos xy dy ; á) f (x) = 2π −1R +∞sin πy(1 − y ) sin xy dy. 8. à) f (x) = 2π −1 0 y −1 sin y cos xy dy ;0R +∞R +∞á) f (x) = 2π −1 0 y −1 (1 − cos y) sin xy dy. 9. à) f (x) = 2π −1 0 y −2 (yR+∞sin y + cos y − 1) cos xy dy ; á) f (x) = 2π −2 0 y −2 (sin y − y cos y) sin xy dy.R10. à) f (x) = −2π −1 0+∞ y −2 (y sin(2y/3) + 3(cos(2y/3) − 1)) cos xy dy ;R +∞á) f (x) = 2π −2 0 (2y − 3 sin(2y/3)) sin xy dy. 11.
f (y) = e−y , y ≥ 0.R12. f (y) = e−y , y ≥ 0. 13. f (y) = (2/π) 0+∞ (1+x2 )−1 sin xy dx; ýòîò èíòåãðàë íå áåðåòñÿ â ýëåìåíòàðíûõ ôóíêöèÿõ, íî åãî ìîæíî ïðåîáðàçîâàòüR +∞ê âèäó f (y) = [e−y Ei (y) − ey Ei (−y)]/π , ãäå Ei (y) = − −y e−x /x dx.14. Íåò ðåøåíèé. 15. f (y) = 2π −1 y(1+y 2 )−1 , y ≥ 0.
16. f (y) = (sin πy)(1−2y 2 )−1 . 17. f (y) = (y sin πy)(1 − y 2 )−1 . 18. f (y) = 2−1 π −1/2 ye−y /4 , y ≥ 0.−1 −1−1−1−1−119. 2π y sin ay . 20. π (1 − y) sin a(1 − y) + π (1 + y) sin a(1 + y).221. (2π)−1/2 e−y /4 . 22. 21/2 π −1/2 cos(y 2 /2 − π/4). 23. 21/2 π −1/2 cos(π/4 −2y 2 /2). 24. 2π −1 y −1 (1−cos ay). 25. 2π −1 ye−y /2 . 26. π −1 ln |(1+y)/(1−y)|.R +∞Óêàçàíèå. Èñïîëüçóéòå èíòåãðàëû Ôðóëëàíè 0 x−1 [f (ax)−f (bx)] dx =f (0)ln (b/a), ãäå ïðåäïîëàãàåòñÿ, ÷òî a > 0, b > 0, ôóíêöèÿ f íåïðåðûâR +∞íà ïðè x ≥ 0 è èíòåãðàë A x−1 f (x) dx ñõîäèòñÿ õîòÿ áû äëÿ îäíîãîA. 30. F− [eiax f (x)](y) = F− [f ](y + a). 31.
F− [f (x − a)](y) = eiax F− [f ](y).R +∞2 −10∨∨32. Ôîðìóëà íå èçìåíÿåòñÿ. 33. F− [f (x) sin ax](y) = [f (y + a)− f∨∨(y − a)]/(2i). 36. fb(y) =f (y) = 21/2 π −1/2 y −1 sin y . 37. fb(y) = − f (y) =∨i21/2 π −1/2 y −2 (y cos y − sin y). 38. fb(y) =f (y) = 21/2 π −1/2 y −2 (cos y −∨1 + y sin y). 39. fb(y) =f (y) = 21/2 π −1/2 y −3 (2y cos y + (y 2 − 2) sin y).∨40. fb(y)= f (y)=e−(y∨22ch ay . 41.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
