§9. Көп қадамды градиентті əдістер

Біз осы уақытқа дейін бір қадамды итерациялық градиентті əдістерді

қарастырдық. Енді бір қадамы жай градиентті əдістің s қадамына пара-пар

итера-циялық əдістерді қалайша алуға болатынын қарастырайық.

9.1. Көп қадамды жылдам түсу əдісі

0

  , , ,  итерациялық параметрлер, ал x теңдеулер жүйесінің

Айталық,

1 2 n

бастапқы жуық шешуі болсын.

Егер

ì k

ï

x =x

ï0

ï

ï

x x a F Ax

ï = + ( - )

íï1 0 0 0 (9.1)

ï

ï

ï

ï

ï ' = = + -

x x x a F Ax

ïî s s -1 s -1 ( s -1 )

десек, онда қателік векторлар былайша жазылады:

ì

ûûû a a

ï = + = -( )

ï 1 0 0 0 0 0

ï

ï

ûûû a a

ï = + = -( )

ï 2 1 1 1 1 1 (9.2)

í

ï

ï

ï

ï

ï ' = = + = - .

y y y a Ay (E a A )y

ï s s -1 s -1 s -1 s -1 s -1

î

Осыдан

y ' = E -aA E -aA E -a A y =

( 0 )( 1 ) ( s -1 ) 0

= E -C A +C A2 ++C As y =y +C r ++C As -1r , (9.3)

( 1 2 s ) 0 k 1 k s k

мұнда r =F -Axk жəне

k

k k 1 s 1 . (9.4)

x x C r  C A r   1 k  s k

біздің мақсатымыз параметрлерін қателер функциясы f x ' өзінің

C C , ,C ,  ( )

1 2 s

ең аз мəніне ие болатындай етіп табу. Яғни,

k s -1

H x ' =H x -C r --C A r =

( ) ( 1 k s k )

k s k s -1

= Ax -C Ar --C A r ,x -C r --C A r -

( 1 k s k 1 k s k )

k s -1

-2 F , x -C r --C A r

( 1 k s k )

C C , ,C , 

функционалынан бойынша туынды алып, нөлге теңестірсек, онда

1 2 s

2

H x ____

( ' )

( 0, i1, s теңсіздігін дəлелдеу онша қиын емес)

2

 Ci

210

----------------------- Page 211-----------------------

2 s

ì

ï 

r , Ar C + r , A r C + + r , A r C = r , r

( ) ( ) ( ) ( )

ï k k 1 k k 2 k k s k k

ï

ï

ï 2 3 s +1



ïr , A r C + r , A r C + + r , A r C =(r , Ar )

( ) ( ) ( )

ï k k 1 k k 2 k k s k k

ï

ï

ï 2 s



r , Ar C + r , A r C + + r , A r C = r , r (9.5)

í( ) ( ) ( ) ( )

ï k k 1 k k 2 k k s k k

ï

ï

ï           

ï

ï

ï s + s +1 ++ 2s-1 = s-1

r , A r C r , A r C r , A r C r , A r

ï( ) ( ) ( ) ( )

ï k k 1 k k 2 k k s k k

ïî

C C , ,C , 

теңдеулер жүйесін аламыз. Осы теңдеулерді шешу арқылы пара-

1 2 s

k1

метрлерін табамыз да, (9.4) формула бойынша келесі жуық шешім - x век-

торын табамыз.

Мысалы, s 2 болғанда (9.5) теңдеулер жүйесінің шешуі

3 2

r , r A r , r - r , Ar r , A r

( )( ) ( )( )

k k k k k k k k

C1 = 2 ,

3 2

(r , Ar )r , A r - r , A r

k k (k k ) (k k )

2

2 2

r , A r - r , A r r , r

( ) ( )( )

k k k k k k

C2 = 2 (9.6)

3 2

(r , Ar )r , A r - r , A r

k k (k k ) (k k )

болғандықтан

k +1 k

x =x -C r -C Ar .

1 k 2 k

Ал кез келген s үшін бұл итерациялық процесте мына алгоритмді пайда-

ланған тиімді:

s

x 1 =x 0 + a y , (9.7)

å j j

j =1

мұндағы

y =r ,

1 0

y ,r r ,r

( i i- ) (i- i- )

r =r -a Ay , a = 1 = 1 1 ,

i i-1 i i i

(y ,Ay ) (y ,Ay )

i i i i

r , r r , Ay

( ) ( )

y r b y , b i i i i .

= + = =- (9.8)

i+1 i i i i

(r , r ) (y , Ay )

i- i- i i

1 1

i 1, 2, ,s 1

( =  - )

(9.7), (9.8) формулаларын табу жолдарын келесі оқулықтан қарауға болады:

Д. К. Фаддеев, В. Н. Фаддеева “Вычислительная методы линейной алгебры”

475, 504 беттер.

Жəне бұл итерациялық процесс үшін

211

----------------------- Page 212-----------------------

2sk

k æçM -m ö÷

f x £ f x

( ) ç ÷ ( )

ç ÷ 0

èM +m ø

теңсіздігі орындалады).

9.2. Көп қадамды минимал ауытқу əдісі

Берілген Ax =F жүйесін минимал ауытқу əдісімен шешу үшін кейде мына

итерациялық əдіс қолданылады:

x k +1 =x k +t F -Ax k +b A F -Ax k . (9.9)

k ( ) k ( )

Осы теңдікті А матрицасына көбейтіп, теңдіктің екі жағын да F-тен алсақ,

онда

2

r + =r -t Ar +b A r

k 1 k k k k k

теңдігін аламыз. Мұнда r =F -Axk .

k

  , ( , r )r

Енді парамертлерін функционалының минимумынан

k k k 1 k 1

анықтаймыз.

r r ,  r r , 

k 1 k 1 k 1 k 1

Яғни 0 , 0 десек, онда мына теңдеулер жүйесін

k k

аламыз:

2

Ar , Ar t + Ar , A r b = r , Ar ,

( k k ) k ( k k ) k (k k )

2 2 2 2

Ar , A r t + A r , A r b = r , A r .

( ) ( ) ( )

k k k k k k k k

Осы теңдеулер жүйесінен

2 2 2 2

(r , Ar ) A r , A r - Ar , A r r , A r

k k ( k k ) ( k k )(k k )

tk = ,

C

2 2

(Ar , Ar )(r , A r )-(r , Ar )(Ar , A r )

bk = k k k k k k k k , (9.10)

C

2

2 2 2

мұнда C = Ar , Ar A r , A r - Ar , A r .

( k k )( k k ) ( k k )

Жалпы жағдайда бұл итерациялық əдіс

s

k +1 k i-1 k

ûûû = + t ( - )ûûû = 

å ik

i=1

___

түрінде жазылады жəне итерациялық параметрлер - t (i =1, s) (r , r ) функ-

ki k + k +

1 1

ционалының минимумынан анықталады. Мұнда

s

i

r =r + t A r .

k +1 k å ik k

i=1

212

----------------------- Page 213-----------------------

Яғни

s

æ ___ ö

i j i ç ÷

å(A r , A r )t =(A r ,r ), i =1,s ÷ (9.11)

ç

k k kj k k ç ÷

j =1 è ø

___

теңдеулер жүйесінен t (i =1, s) параметрлерін табамыз.

ki

Кейде теңдеулер жүйесін шешу үшін

k k 1

x x r  Ar   ' (9.12)

k k k k

( , r )r

екі қадамды итерациялық əдіс қолданады. Мұнда функционалының

k1 k1

  ,

минимум беретін k k мына өрнектерге тең:

r Ar A Ar A Ar - Ar A Ar r A Ar

(k , k )( ' k , ' k ) ( k , ' k )(k , ' k )

a =

k ,

C

r A Ar Ar Ar - r Ar A Ar Ar

(k , ' k )( k , k ) (k , k )( ' k , k )

b =

k ,

C

2

C = Ar Ar A Ar A Ar - Ar A Ar

( k , k )( ' k , ' k ) ( k , ' k )