Циклды редукция алгоритмі.

Дәріс №13. Прима тізбектелген алгоритм

Мақсаты: параллельді каскадты қосу алгоритмі қарастыру

Сандық сараптамаларда рекурсияларды қолдану мысалдары өте көп: САТЖ Гаусстың шығару әдісімен және кез-келген итерациялық әдістермен шешу; кәдімгі дифференциалдық теңдеулерді интегралдаудың көптеген әдістері; дербес туындылардағы дифференциалдық теңдеулерді шешудің көптеген әдістері.

Өз мағынасында, рекурсия есептеу тізбегін береді және сондықтанда параллельдеу үшін белгілі бір мәселе болып табылады.

Бірінші ретті сызықтық рекурсияларды қарастырумен шектелейік:

 

мұндағы – берілген тұрақтылар. X0=a1=0 деп есептейік (егер ).қабылдасақ, бұған жеңіл қол жеткізуге болады). Бұл болжамдағы рекурсияның ақпараттық байланыстары (1), 1 суретте көрсетілген түрге ие болады.

 

1-сурет. Рескурсияның ақпараттық байланысының құрылымы (1): n=4.

Параллельді каскадты қосу алгоритмі.

деп есептейік. Бұл жағдайда (1) формула сандарды қосу алгоритмінің рекурентті жазбасы болып табылады.

n=8 жағдайы үшін параллельді каскадты қосу алгоритмінің ақпараттық байланыстар құрылымы 2 суретте көрсетілген.

Каскадты қосу алгорритмі x_nшамасымен қатар барлық аралық шамаларды алуға мүмкіндік береді. Егер тек қана x_n шамасының мәні керек болса, онда 2 суретте көрсетілген қосындыларды ғана орындаған жеткілікті. Бұл жағдайда алгоритм екі еселеу алгоритміне айналады (2 параграфты қараңыз).

ЯПФ каскадты қосу алгоритмінің биіктігі –ке тең, ал ЯПФ әрбір қабаттарының ені –ке тең екендігін байқау оңай. Алгоритм операциялардың жалпы санын тен x-ке дейін көбейтетіндігін атап өтейік (тағы да).

Циклды редукция алгоритмі.

1, 1,..., 1.деп есептейік.

Циклдық редукция алгоритмінің негізгі идеясы , рекурсия мүшелерінің арасында қатынас алынатындай етіп, рекурсияның сыбайлас мүшелерін біріктіру болып табылады. Мұның нәтижесінде, бастапқы рекурсияның әрбір екінші ,айнымалысын байланыстыратын, мүшелерінің саны жаңа сызықтық рекурсия пайда болады. Бұл жаңа рекурсияда тағы да сыбайлас мүшелерді біріктірейік – бастапқы рекурсияның әрбір төртінші x айнымалысын байланыстыратын, мүшелерінің саны рекурсияны аламыз, осылайша ары қарай. редукциясынан кейін -ті есептейтін формуланы аламыз.

Сипатталған сұлбаны нақтырақ қарастырамыз.

1 редукция. (1) көрініп тұрғандай .. Бұл амалды (1) қойып, бастапқы тізбектің салалас мүшелерінің арасындағы бірінші ретті сызықтық рекурсияны аламыз.

мұндағы = , = + .

2 редукция. Сондай сұлба бойынша алдыңғы рекурсиядан бастапқы рекурсияның әрбір төртінші мүшесінің арасындағы бірінші ретті келесі сызықтық рекурсияны аламыз.

 

мұндағы

.

k редукциясы. Сондай сұлба бойынша алдыңғы рекурсиядан бірінші ретті келесі сызықтық рекурсияны аламыз.

(2)

Егер (2) формуладағы индекстер[1,n] диапазонынан шығып кететін болса, онда (2) рекурсияның сәйкес компонентін нөлге тең ету қажет.

n редукциясы. Қарастырылған сұлба бойынша (n-1) рекурсиясынан аламыз.

Осылайша, циклдық редукция алгоритміне сәйкес, рекурсияны есептеу коэффициенттерін есептеуге келіп тіреледі. Бұл коэффициенттерді есептеу параллельдік каскадтық қосудың көмегімен жүргізіледі. (3,4 суреттерді қараңыз).