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

Дріс №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 суреттерді араыз).