Численные методы. Решения систем линейных алгебраических уравнений: Учебно-методическое пособие

М И Н И СТ Е РСТ В О О БРА ЗО В А Н И Я РО ССИ Й СК О Й Ф Е Д Е РА Ц И И В О РО Н Е Ж СК И Й ГО СУ Д А РСТ В Е Н Н Ы Й У Н И В Е РСИ Т Е Т

ЧИ СЛЕ Н Н Ы Е М Е Т О Д Ы РЕ Ш Е Н И Я СИ СТ Е М

ЛИ Н Е Й Н Ы Х А ЛГЕ БРА И ЧЕ СК И Х У РА В Н Е Н И Й

У чебн о -методическо е пособие по специальн о сти «математика» (010100)

В О РО Н Е Ж 2004

2

У твер ж ден о н аучн о -мето дическим со в ето м пр о то ко л№ 8 о т 1мар та2004 го да.

математическо го

ф акультета

Со став ительТ р о ф имо в В .П .

У чебн о -мето дическо е по со бие по дго то в лен о н а каф едр е математическо го мо делир о в ан ия математическо го ф акультета В о р о н еж ско го го судар ствен н о го ун ив ер ситета. Реко мен дуется для студен то в 4 и 5 кур со в дн ев н о го и в ечер н его о тделен ий математическо го ф акультета, о бучаю щ их ся по специальн о сти «математика» (010100).

3

Н асто я щ ее учебн о -мето дическо е по со бие пр едн аз н ачен о для в ыпо лн ен ия лабо р атор н о й р або ты «Числен н ые мето ды р еш ен ия систем лин ейн ых алгебр аических ур ав н ен ий» по кур су «М ето ды в ычислен ий» студен тами IV-V кур со в дн ев н о го и в ечер н его о тделен ий математическо го ф акультета. Раз р або тка мо ж етбыть испо льз о в ан а для само сто я тельн о й р або ты студен то в и по дго то в ки к экз амен у. Литер атур а 1. Бах в ало в Н .С. Числен н ые мето ды: У чеб. по со бие для студен то в ф из .-мат. специальн о стей в уз о в / Н .С.Бах в ало в , Н .П .Ж идко в , Г.М .К о белько в . – 2 из д. М .: Ф из матлит: Лаб. Баз о в ых Зн ан ий; СП б.: Н ев . Д иалект, 2001. – 630 с. 2. Бах в ало в Н .С. Числен н ые мето ды в з адачах и упр аж н ен ия х : У чеб. по со бие / Н .С.Бах в ало в , А .В .Лапин , Е .В .Чиж о н ко в ; П о д р ед. В .А .Садо в н ичего . – М .: В ысш ая ш ко ла, 2000. – 190 с. 3. Ф аддеев Д .К . В ычислительн ые мето ды лин ейн о й алгебр ы: У чеб. П о со бие для студен то в в уз о в / Д .К .Ф аддеев , В .Н .Ф аддеев а. 3 из д., стер . – СП б.: Лан ь, 2002. – 733 с. 4. В о ев о дин В .В . М атр ицы и в ычислен ия / В .В .В о ев о дин , Ю .А .К уз н ецо в . – М .: Н аука, 1984. – 320 с. 5. В о ев о дин В .В . В ычислительн ые о сн о в ы лин ейн о й алгебр ы. – М .: Н аука, 1977. – 304 с. 6. П лис А .И . Лабо р ато р н ый пр актикум по в ысш ей математике: У чеб. по со бие для в туз о в / А .И .П лис, Н .А .Слив ин а. – 2-е из д., пер ер аб. и до п. – М .: В ысш ая ш ко ла, 1994. – 416 с. О бо з н ачен ия R - мн о ж ество в ещ ествен н ых чисел; N – мн о ж еств о н атур альн ых чисел;

R m - m - мер н о е лин ейн о е пр о стр ан ство н ад по лем в ещ ествен н ых чиселR. 1. П о ст ан о в казад ач и П устьз адан асистемалин ейн ых алгебр аических ур ав н ен ий

Ax = b с кв адр атн о й н ев ыр о ж ден н о й матр ицей

(1)

A = {aij }i , j=1,K,m ( a ij ∈ R, i, j = 1,K , m ),

∆ = det A ≠ 0 , x, b ∈ R m , x = ( x1 , K , xm )T , b = (b1 ,K , bm ) T . В екто р xˆ н аз ыв ается р еш ен и ем си ст ем ы (1), если Axˆ ≡ b .

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

∆ = det A матр ицы A = {aij }i , j=1,K,m .

4

3) Н ах о ж ден ие о бр атн о й матр ицы

(

−1

)

−1

A−1

для

н ев ыр о ж ден н о й

матр ицы A A A = AA = I . Зам еч ан и е 1. В сю дув да ль н е йш е м м ы буде м ра ссм а т рива т ь т о ль ко случа й н е в ы ро ж де н н о й м а т рицы A , det A ≠ 0 . О бщий случа й т ре буе т спе циа ль н ы х по дхо до в к по н ят ию ре ш е н ия. О т м е т им , чт о при числе н н ы х ра сче т а х гра н ь м е ж ду det A ≠ 0 и det A = 0 до ст а т о чн о усло в н а . Ф о р мальн о е р еш ен ие системы (1) сущ ествует и мо ж ет быть н айден о по из в естн ым ф о р мулам К р амер а:

xˆ = A−1b,

) xi = ∆i ∆, i − 1,K, m,

где

∆ = det A,

a11 a21 K a1,i −1 b1 a1,i +1 K a1m a21 a22 Ka2,i −1 b2 a2,i +1 Ka2m , i = 1, K, m. ∆i = M M MMM M M M MMM M am1 am2 Kam,i −1 bm am,i +1 Kamm

R m н аибо лее часто испо льз ую тся следую щ ие в екто р н ые н о р мы:

В

x e = (x12 + x22 + K + x m2 ) 2 - ев клидо в а н о р ма; 1

x

н о р ма;

∞

x 1 = x1 + x 2 + K + xm - l1 -

= max xi - l∞ - н о р ма. 1≤i ≤m m

В н и м ан и е! В про ст ра н ст в е R в се н о рм ы экв ив а ле н т н ы и схо дим о ст ь в лю бо й изн их в ле че т схо дим о ст ь в о ст а ль н ы х н о рм а х. Н о р мы матр ицы A , со гласо в ан н ые с со о тветствую щ ими н о р мами в екто р о в  Ax  m  : A = max λi AAT , з десь  A = sup R в , в ычисля ю тся по ф о р мулам  e i x ≠0 x  

(

чер ез

(

( )

λi AAT

λi AA

T

)

о бо з н ачен ы со бствен н ые з н ачен ия

матр ицы

)

AAT , число m

н аз ыв ается син гуляр н ым число м матр ицы

A;

A 1 = max ∑ a ij ; 1≤ j ≤ m i =1

m

A ∞ = max ∑ aij . 1≤i ≤m j =1

A

Реш ен ие xˆ системы (1) н епр ер ыв н о з ав исито тв х о дн ых дан н ых : матр ицы и в екто р апр ав о й части b . Д ейств ительн о , р ассмо тр им в о з мущ ен н ую систему

( A + Ε)x = b + ε .

(2)

5

Е сли в о з мущ ен ие

−1 Ε удо в летв о р я етусло в ию Ε < 1 A , то система (2)

имеетедин ств ен н о е р еш ен ие

(

−1 ~ x = ( A + Ε ) (b + ε ) = I + A −1Ε

)

−1

A −1 (b + ε ) .

В в едем о тн о сительн ые в еличин ы в о з мущ ен ий в екто р о в xˆ, b ∈ R и матр иц m

A : R m → R m и A −1 : R m → R m : −1 −1 ( A + Ε ) − A xˆ − ~ x ε Ε δxˆ = , δb = , δA = , δA−1 = . xˆ b A A−1 −1 −1 В о спо льз о в ав ш исьто ж дество м ( A + Ε) − A = −( A + Ε) ΕA , имеем −1

−1

−1 −1 −1 xˆ − x~ = A−1b − ( A + Ε) (b + ε ) = ( A + Ε) ΕA−1b − ( A + Ε) ε =

= ( A + Ε) (Εxˆ − ε ). −1

О тсю да для лю бых со гласо в ан н ых н о р м, испо льз уя о цен ки b ≤ A ⋅ xˆ ,

( A + Ε )−1

≤ A−1

(1 − Ε ⋅ A ), по лучаем: −1

δA ≤ −1

xˆ − x~ ≤ δxˆ = xˆ

Ε ⋅ A−1

1 − Ε ⋅ A−1

A−1 ⋅ Ε + A−1 1 − Ε ⋅ A−1

или

ε xˆ

Ε A = , Ε 1 − A ⋅ A−1 A A ⋅ A−1

A ⋅ A−1

≤

1 − A ⋅ A−1

 Ε ε    + Ε  A b  A

δA ⋅ condA , 1 − δ A ⋅ condA

(3)

condA (δA + δb). 1 − δA ⋅ condA

( 4)

δA−1 ≤ δxˆ ≤

2

6

В

н ер ав ен ствах (3)-(4) число

condA = A ⋅ A −1

н аз ыв ается ч и сло м

о б у сло в лен н о ст и м ат р и цы A в р ассматр ив аемо й н о р ме. И з н ер ав ен ства (4) в ытекает, что δxˆ → 0 пр и δA → 0 и δb → 0 . П о лучен н ые ф о р мулы (3), (4) даю т ко личествен н ые о цен ки в о з мущ ен ия о бр атн о й матр ицы и р еш ен ия системы (1) пр и из мен ен ии матр ицы и в екто р а пр ав о й части системы. И з н их следует, что в о кр естн о сти лю бо й н ев ыр о ж ден н о й матр ицы о бр атн ая матр ица и р еш ен ие системы (1) я в ля ю тся н епр ер ыв н ыми ф ун кция ми в х о дн ых дан н ых . И з о чев идн о го н ер ав ен ства AA ≤ A ⋅ A следует, что condA ≥ 1 . Т аким о бр аз о м, хо р о ш о о б у сло в лен ы матр ицы с малым число м о бусло в лен н о сти, пр и это м о тн о сительн ая по гр еш н о стьр еш ен ия системы (1) мала. Зам еч ан и е 2. Для а прио рн о й о це н ки числа о бусло в ле н н о ст и condA т ре буе т ся н а йт и о бра т н ую м а т рицу к за да н н о й м а т рице A - эт о сло ж н а я в ы числит е ль н а яза да ча . Зам еч ан и е 3. Ан а лиз по гре ш н о ст и о кругле н ия при ре ш е н ии сист е м ы (1) по зв о ляе т (с по м о щь ю до ст а т о чн о гро м о здких в ы кла до к) по лучит ь сле дую щие о це н ки для δA и δb : −1

−1

δA = O (m2 − t ) = O(mε M ), δb = O (m2 − t ) = O (mε M ), где t - ра зрядн о ст ь ЭВ М , ε M - м а ш инно е эп с ило н.

И з ф о рм улы (4) сле дуе т о це н ка о т н о сит е ль н о й по гре ш н о ст и ре ш е н ия сист е м ы :

δxˆ = O (m ⋅ ε M ⋅ condA). П р и м ер 1. П устьматр ица A имеетв ид: 1  0 A=M  0 0 

a 1 M 0 0

K K O K K

0 0 M 1 0

0  0 M  a 1 

Н етр удн о в ычислитьр еш ен ие системы (1) с матр ицей

A:

xˆm = bm , xˆm−1 = bm−1 − abm , xˆm−2 = bm−2 − a ⋅ (bm−1 − abm ),K. О тсю да следует, что если bm з адан о с по гр еш н о стью ε , то по гр еш н о сть в в ычислен ии xˆ1 будет р ав н а (−1)

m−1 m−1

a ε . П р и m = 40, a = 7 эта по гр еш н о сть

7 32

будет в еличин о й по р я дка 10 и мы р искуем н е иметь в р еш ен ии системы н и о дн о го в ер н о го з н ака. В о з н икш ая ситуация мо ж етбыть пр едсказ ан а с по мо щ ью тако й х ар актер истики матр ицы A , как число о бусло в лен н о сти. В ычислив о бр атн ую матр ицу

A−1 , по лучим cond ∞ A = A ∞ ⋅ A

−1 ∞

am −1 = (1 + a ) . a −1

Д ля в ыбр ан н ых пар аметр о в cond ∞ A ≈ 8,5 ⋅ 10 и, следо в ательн о , матр ица 33

A пло х о о бусло в лен а. И з это го пр имер а мо ж н о из в лечь ещ е о дн о следств ие, со сто я щ ее в то м, что бо льш о е число о бусло в лен н о сти матр ицы н ельз я о бя з ательн о св я з ыв ать с близ о стью к в ыр о ж ден н о сти или н аличию мало го со бствен н о го з н ачен ия . М о ж н о пр о н о р мир о в атьматр ицу A , р аз делив ее н а a . Т о гдамы по лучим матр ицу

 a −1 1  −1  0 a B = a −1 A =  M M   0 0  0  0 М атр ица

K 0 0  K 0 0 O M M ,  −1 1 K a  K 0 a−1 

cond∞ B = cond∞ A.

B - пло х о о бусло в лен а, н о ее со бствен н ые з н ачен ия о тн ю дь н е

малы. Числен н ые мето ды р еш ен ия систем лин ейн ых алгебр аических ур ав н ен ий делятся н а дв е бо льш ие гр уппы: пр ям ы е и и т ер аци о н н ы е мето ды. П р я мые мето ды по з в о ляю тн айти р еш ен ие системы (1) з ако н ечн о е число ш аго в . 2. П р ям ы е м ет о д ы . М ет о д Гау сса Зн ачительн ая часть н аибо лее из в естн ых пр я мых мето до в р еш ен ия системы (1) св о дится к по следо в ательн о му р еш ен ию о дн о й или н еско льких систем

Gx = y

(5)

с матр ицами G «пр о сто го » в ида (диаго н альн ыми, «по чти» диаго н альн ыми, тр еуго льн ыми, «по чти» тр еуго льн ыми). 2.1. К ласси ч еск ая схем ам етод аГау сса. LU –р азло жен и е м ат р и цы К лассическая сх ема мето да Гаусса о сн о в ан а н а св еден ии системы (1) к экв ив ален тн о й системе (5) с в ер х н ей тр еуго льн о й матр ицей G :

Ax = b

⇔ Gx = y

(G = {g }, ij

g ij = 0,

j < i ).

8

П о лучен ие тако й системы - по стр о ен ие матр ицы G и в екто р а пр ав о й части y н аз ыв ается пр ям ы м хо д о м мето да Гаусса. Реш ен ие н о в о й н ы м хо д о м мето даГаусса. системы Gx = y н аз ыв ается о б р ат П р ям о й хо д м ет о д а Гау сса. П усть н ев ыр о ж ден н ая матр ица н ен улев ые глав н ые мин о р ы в сех по р я дко в о т1 до m-1:

1,K, r  A  ≠ 0, K r 1 , ,  

r = 1,2,K, m − 1.

A имеет

(6 )

Рассмо тр им матр ицы и в екто р ы

Ak = N k Ak −1, b ( k ) = N k b ( k −1) ,

b( 0 ) = b,

A0 = A,

(7 )

k = 1,K m − 1,

где н иж н я я тр еуго льн ая матр ица N k стр о ится по

k - то му сто лбцу матр ицы

Ak −1 и имеетв ид: 1  0 M  Nk =  0 0  M 0  Зам еч ан и е

4.

Н иж н ие

0 K 0 1 K 0 M O M 0 L 1 0 K nk(k+1) ,k M MMM M (k ) 0 K nmk

т ре уго ль н ы е

0 K 0  0 K 0 M MMM M   0 K 0. 1 K 0  M O M 0 K 1

м а т рицы

Nk

(8)

(k = 1,K, m − 1)

о т лича ю т сяо т е дин ичн о й м а т рицы лиш ь по ддиа го н а ль н ы м и эле м е н т а м и в ст о лбце , det N k = 1 . П ри эт о м

N k−1

1  0 M  = 0  0 M  0

0 K

0

1 K

0

M O

M

0 L

1

0 K − nk( k+)1,k M MMM

M

0 K

(k) − nmk

0 K 0  0 K 0 M MMM M   0 K 0 .  1 K 0 M O M  0 K 1

k -о м

9 −1

О че в идн о , чт о det N k = 1, k = 1, K, m − 1. −1

−1

−1

Ле гко по лучит ь и про изв е де н ие м а т риц N1 N 2 K N k (k = 1,K, m − 1) . Для е го н а хо ж де н ия н е н уж н о про изв о дит ь пра кт иче ски н ика ких в ы числе н ий. Н е н уле в ы е эле м е н т ы про изв е де н ия ра спо ла га ю т ся в пе рв ы х k ст о лбца х и −1

−1 −1 со в па да ю т с эле м е н т а м и м а т рицN1 , N 2 , K, N k . И м е е м

0 0  1  (1) 1 0  − n21  − n(1) − n( 2) 1 31 32  M M  M N1−1N 2−1 KNk−1 =  − nk(11) − nk( 22) − nk(33)  (1)  − nk +1,1 − nk( 2+)1,2 − nk(3+)1,3  M M M   − n(1) − n( 2) − n(3) m1 m2 m3 

0

0

0

0

0 0 O M K 1 K − nk( k+1) ,k MMM M (k ) K − nmk

0 K 0  0 K 0 0 K 0  M MMM M  . 0 K 0  1 K 0 M O M  0 K 1

Ан а ло гичн о в ы числяе т сяи про изв е де н ие м а т риц N1 N 2 K N k (k = 1, K, m − 1) . О бо з н ачим элемен ты матр ицы

Ak чер ез aij(k ) . Д ля каж до го k = 1,K, m − 1

элемен ты матр ицы N k в ыбер ем так, что бы

aij( k ) = 0,

если i > j, j ≤ k ,

aii( k ) ≠ 0, если i ≤ k . Н а пер в о м ш аге пр я мо го х о да мето да Гаусса k = 1 имеем (по усло в ию (6)

a11 = a11( 0 ) ≠ 0 ):

 1  (1)  n21  n(1) 31 N1 =   M  n(1)  m(−11),1 n  m1

0 1 0 M 0 0

0 0 1 M 0 0

L L L O L L

0 0 0 M 1 0

0  0 0 , M 0  1

(1) i1

n

ai(10) = − ( 0) , i = 2,K, m, a11

10 (0 ) ( 0) (0 )  a11 a12 a13  (1) (1) a22 a23  0  0 (1) (1) a32 a33 A1 =  M M  M  (1) (1)  0 am−1,2 am−1,3  0 am(12) am(13) 

(1) ij

a

L

a1(,0m)−1

L

a2(1,m) −1

L

a3(1,m) −1

O

M

a1(m0)   a2(1m)  a3(1m)  , M   am(1−)1,m  (1)  amm 

L am(1−)1,m−1 L am(1,)m−1

 b1(0)   (1)   b2   b(1)  (1) b =  3 ,  M   (1)   bm−1   b(1)   m 

ai(10) ( 0) ai(10) ( 0) ( 0) (1) = − ( 0) a1 j + aij , bi = − ( 0) b1 + bi(0) , i, j = 2,K, m. a11 a11

Н ав то р о м ш аге k = 2 имеем ( a22 ≠ 0 по усло в ию (6) ): (1)

0 1  1 0  0 n( 2) 32 N2 =  M M  0 n( 2) m−1, 2   0 n( 2) m, 2 

0 0 1 M 0 0

L L L O L L

(0 ) ( 0) ( 0)  a11 a12 a13  (1) (1)  0 a22 a23 ( 2)  0 0 a33 A2 =   M M M  0 am( 2−)1,3  0  0 0 am( 2,)3 

( 2) ij

a

0 0 0 M 1 0 L

0  0 0 , M 0  1

( 2) i2

n

a1(,0m)−1

L a2(1,m) −1 L a3(,2m) −1 O M L am( 2−)1,m−1 L am( 2,m) −1

ai(21) = − (1) , i = 3,K, m, a22

a1(,0m)   (1) a2,m  a3( 2,m)  , M   am(2−)1,m  ( 2)  amm 

b( 2 )

 b1( 0)   (1)   b2   b( 2)  =  3 ,  M   ( 2)   bm−1   b( 2)   m 

ai(21) (1) ai(21) (1) (1) ( 2) = − (1) a2 j + aij , bi = − (1) b2 + bi(1) , i, j = 3,K, m. a22 a22

У сло в ие (6) по з в о ляетпр о до лж итьэто тпр о цесс до k = m − 1 :

11

1  0 0 N m−1 =  M 0  0 

0 0 L 1 0 L

0

0 1 L M M O

0 M

0  0 0 , M 0  1

0

0 0 L 1 0 0 L nm( m,m−−21)

(0 ) (0 )  a11 a12  (1)  0 a22  0 0 Am−1 =  M  M  0  0  0 0  am( m,m−−21) ( m−1) amm = − ( m−2) am−2,m−2

(0 ) a13 (1) a23 ( 2) a33 M

0 0 a

( m−2 ) m−1,m

( m−2) m,m−1

n

am( m,m−−21) = − ( m−2) , am−1,m−1

L a1(,0m)−1 a1(,0m)   (1) (1) L a2,m−1 a2,m  L a3( 2,m) −1 a3(,2m)  , O M M   L am( m−1−,2m)−1 am( m−1−,2m)  (m−1)  L amm 0  +a

( m−2 ) mm

( m−1) m

, b

b( m−1)

 b1(0)   (1)   b2   b(2)  =  3 ,  M   ( m−2)   bm−1   b(m−1)   m 

am( m,m−−21) (m−2) = − ( m−2) bm−1 + bm( m−2) . am−1,m−1

За m − 1 ш аго в пр я мо го х о да мето да Гаусса мы по стр о им в ер х н ю ю тр еуго льн ую матр ицу

Am−1 = N m−1 N m−2 K N 2 N1 A. О тсю да н ах о дим пр едстав лен ие матр ицы в ер х н ей тр еуго льн ых матр иц:

A в в иде пр о из в еден ия н иж н ей и

A = (N 1−1 N 2−1 K N m−1−1 )Am −1 = LU ,

где

L = N1−1 N 2−1 K N m−1−1

-

н иж н я я

тр еуго льн ая

(9)

матр ица с един ичн ыми

U = Am −1 - в ер х н я я тр еуго льн ая матр ица, det U = det A . Ф о р мулу (9) пр ин я то н аз ыв атьLU –р азло жен и ем м атри цы A .

диаго н альн ыми элемен тами, det L = 1,

Т аким о бр аз о м, пр и в ыпо лн ен ии усло в ия (6) мы в р ез ультате пр я мо го х о да мето да Гаусса по лучаем экв ив ален тн ую (1) систему лин ейн ых ур ав н ен ий с в ер х н ей тр еуго льн о й матр ицей:

Ux = y ,

(10)

12

где

U = Am −1 и y = b

( m −1)

. О б р ат н ы й хо д м етод а Гау сса. Т епер ь мы мо ж ем в ычислить р еш ен ие

xˆ = ( xˆ1 , xˆ2 ,K, xˆm )T системы (10) с в ер х н ей тр еуго льн о й матр ицей. В силу экв ив ален тн о сти систем (10) и (1) xˆ будет и р еш ен ием системы (1). П усть U = {uij }i , j =1,K,m и y = ( y1 ,K, ym )T .

xˆ н ах о дя тся в о бр атн о м по р я дке по ф о р мулам: ym  ˆ x = , m  umm  m (11)  yi − ∑ uij ⋅ xˆ j  j =i +1 i = m − 1, m − 2,K,1. ,  xˆi = u ii 

К о о р дин аты р еш ен ия

В ычислен ие р еш ен ия системы (1) по ф о р мулам (11) я в ляется о б р ат ным хо д о м м ет о д аГау сса. Зам еч ан и е 5. И зло ж е н н ы й а лго рит м ре ш е н ия сист е м ы (1) н а зы ва ю т кла с с иче с ко й с хе м о й м ет о да Г а у с с а . Эт а схе м а прим е н им а в случа е , ко гда в ы по лн е н о усло вие (6). Для ре а лиза ции а лго рит м а по т ре буе т ся прим е рн о

 2m 3  O   а риф м е т иче ских о пе ра ций. 3   В н и м ан и е! Если изв е ст н о LU – ра зло ж е н ие м а т рицы A , т о ре ш е н ие сист е м ы (1) сво дит ся к по сле до ва т е ль н о м у ре ш е н ию дв ух сист е м с т ре уго ль н ы м и м а т рица м и: Lz = b , Ux = z. П о лучен н о е в ф о р муле (9) LU – р аз ло ж ен ие матр ицы A по з в о ляет в ычислить о пр еделительматр ицы Т ак как

A ин айти о бр атн ую матр ицу A−1 .

det A = det(LU ) = det L ⋅ det U = u11u22 Kumm ,

U = Am−1 ,

то (1) ( m −1) det A = det Am−1 = a11a22 Kamm .

Д ля по стр о ен ия о бр атн о й матр ицы

(12)

A−1 н уж н о р еш итьматр ичн о е ур ав н ен ие

A⋅ X = I.

(13)

13

= {xˆij }, (i , j = 1,K, m ) - р еш ен ие ур ав н ен ия (13) и дает A−1 . (k ) = ( xˆ1k ,K , xˆmk )T матр ицы Xˆ я в ляется О чев идн о , что k -ый сто лбец Xˆ (k ) р еш ен ием системы лин ейн ых ур ав н ен ий A ⋅ x = e , где в екто р пр ав о й части (k ) T системы e = ( 0,K,0,1,0, K,0) , k = 1,K, m. П р и это м для р еш ен ия М атр ицаXˆ

k

системы (13) LU – р аз ло ж ен ие матр ицы A стр о ится то лько о дин р аз . В ли ян и е о ш и б о к о кр у глен и я н а в ы ч и сли т ельн ы й пр о цесс. П усть

~ ~

~

~ ~

~

в ыпо лн ен о усло в ие (6) и N 1 , N 2 ,K, N m −1 и A1 , A2 , K , Am −1 - р еальн о в ычислен н ые матр ицы пр я мо го х о дамето даГаусса. П о ло ж им

(N~

−1 1

О бо з н ачим чер ез чер ез

µij

)

~ ~ ~ N 2−1 K N m−1−1 ⋅ Am−1 = A + Μ.

(14)

элемен ты матр ицы экв ив ален тн о го в о з мущ ен ия

Μ,

~ a~ij( k ) элемен ты матр ицы Ak . И мею тместо о цен ки

где

i = 1, 0, ~ j ≥ i, µij ≤ 1,5 ⋅ (i − 1) p −t +1α , 1,5 ⋅ ( j − 1) p −t +1α , j < i,  p - о сн о в ан ие системы счислен ия , t - р аз р я дн о стьЭ В М α = max αk , αk = max a~ij( k ) . 0≤k ≤m−1

(15) ,

i> k , j≥ k

В усло в ия х и о бо з н ачен ия х (14) в ыпо лн я ется н ер ав ен ств о

~ 6 2 −t+1 Μ сф ≤ m p α, 4

(16) 1 2

 2   . A = a A A ∑ ij з десьчер ез р ицы : сф  сф о бо з н ачен асф ер ическая н о р мамат  i , j=1  m

Зам еч ан и е 6. О це н ки (15), (16) по луче н ы бе з ка ких-либо пре дпо ло ж е н ий о т н о сит е ль н о в е личин ы гла в н ы х м ин о ро в м а т рицы A , кро м е , ко н е чн о , в ы по лн е н ия усло в ия о суще ст в им о ст и прям о го хо да м е т о да Г а усса . Т а ким о бра зо м , суще ст в е н н ы м усло вие м н е уст о йчив о ст и про це сса вы числе н ий яв ляе т ся

~

зн а чит е ль н ы й ро ст эле м е н т о в про м е ж ут о чн ы х м а т риц Ak .

14

Если прин ципиа ль н о н е м е н ят ь о бщую схе м у в ы числе н ий, то е дин ст в е н н о й в о зм о ж н о ст ь ю в ка ко й-т о м е ре ре гулиро в а т ь ро ст эле м е н т о в

~

м а т риц Ak яв ляе т ся испо ль зо ва н ие пе ре ст а н о во к при ре а лиза ции прям о го хо да м е т о да Г а усса . 2.2. М ет о д Гау ссас в ы б о р о м в ед у щ его (глав н о го ) элем ен т а AП усть пр о из в о льн ая н ев ыр о ж ден н ая матр ица. по следо в ательн о сти (7) р ассмо тр им по следо в ательн о стьматр иц

(

)

Aˆk = Nˆ k Pkik Aˆk −1Rkjk ,

Aˆ0 = A,

k = 1,K, m − 1,

В место

(17)

ik , jk ≥ k. Д ля лю бо го k в (17)

где Pkik , Rkjk - матр ицы пер естан о в о к, пр ичем

(k, k ) матр иц Pki Aˆk −1 Rkj

в ыбер ем матр ицы пер естан о в о к так, что бы в по з иция х

k

k

н ах о дились н ен улев ые элемен ты и каж дая из матр иц Nˆ k стр о ится со гласн о (8) по

k -о му сто лбцу матр ицы Pki Aˆk −1 Rkj . k

k

О писан н ый алго р итм (17) н аз ыв аю тм етод о м Гау ссас в ы б о р о м в ед у щ его (глав н о го ) элем ен т а.

(k, k ) м а т рицы Pki Aˆk −1 Rkj ст о ит т о т ж е эле м е н т , ˆ . П о эт о м у для ко т о ры й н а хо дит ся в по зиции (ik , jk ) м а т рицы A k −1 В н и м ан и е! В по зиции

о суще ст в им о ст и

k

про це сса

(16)

пе ре ст а н о в ки Pkik , Rkjk , ин де ксы (ik ,

k

н е о бхо дим о

в ы бира т ь

т а кие

jk ) ко т о ры х о пре де ляю т по зицию н е н уле в о го

ˆ . эле м е н т а м а т рицы A k −1 Реализ уя пр о цесс (17), по лучим следую щ ее р аз ло ж ен ие матр ицы A н а мн о ж ители

)(

(

)

A = P1i1 Nˆ1−1 K Pm −1, jm−1 Nˆ m−1−1 ⋅ Aˆm−1Rm−1, jm−1 K R1 j1 . В р аз ло ж ен ии (18) матр ицы, сто я щ ие в ско бках тр еуго льн ыми.

( N r−−11

уж е н е я в ляю тся

( −1 ˆ −1 N Рассмо тр им матр ицы р ицы r −1 = Pkik K Prir N r −1 Prir K Pkik . О чев идн о мат −1 я в ляю тся матр ицами типа N k (см. (8)) и о тличаю тся о тматр иц Nˆ r−1 лиш ь

пер естан о в ко й по ддиаго н альн ых элемен то в в r − 1 -о м сто лбце. Рав ен ство (18) мо ж н о з аписатьв в иде

(

)

( ( ( A = N 1−1 K N m−1−1 ⋅ Aˆm −1 ,

где

(18)

15

(

) (

)

( A = Pm−1,im−1 K P1i1 ⋅ A ⋅ R1i1 K Rm−1,im−1 . Ср ав н ив ая н айден н о е пр едстав лен ие с (9), делаем в ыв о д, что пр о цесс (17)

( A , ко то р ая

о пр еделяет р аз ло ж ен ие н а тр еуго льн ые мн о ж ители матр ицы по лучается из матр ицы A путем пер естан о в о к ее стр о к и сто лбцо в . Т ак как пер естан о в ки н е в н о ся тдо по лн ительн ых о ш ибо к, то о цен ки (15), (16) пер ен о ся тся

( ˆ A и пр о цесс (17). Следо в ательн о , р о ст элемен то в матр иц A н а матр ицу k по лн о стью о пр еделяется стр атегией в ыбо р апер естан о в о к (в едущ их элемен то в ).

ˆ в по з иция х (i , j ) пр о цесса (17) н аз ыв аю тся Э лемен ты матр иц A k k k в ед у щ и м и (глав н ы м и ) элем ен т ам и мето даГаусса. Сущ еств ую ттр и н аибо лее р аспр о стр ан ен н ые ст р ат еги и в ы б о р а в ед у щ и х элем ен т ов : 1) В качестве в едущ его элемен та k -го ш ага в ыбир ается максимальн ый по ( k −1)

ˆ пр и усло в ия х i ≥ k , j = k ; если имеется мо дулю элемен т aˆij матр ицы A k −1 н еско лько максимальн ых по мо дулю элемен то в , то в едущ им в ыбир ается лю бо й из н их ; этастр атегия н аз ыв ается в ыбо р о м в едущ его элемен тапо столб цу . 2) В качестве в едущ его элемен та k -го ш ага в ыбир ается максимальн ый по ( k −1)

ˆ пр и усло в ия х i = k, j ≥ k ; если имеется мо дулю элемен т aˆij матр ицы A k −1 н еско лько максимальн ых по мо дулю элемен то в , то в едущ им в ыбир ается лю бо й из н их ; этастр атегия н аз ыв ается в ыбо р о м в едущ его элемен тапо ст р о ке. 3) В качестве в едущ его элемен та k -го ш ага в ыбир ается максимальн ый по ( k −1)

ˆ пр и усло в ия х i ≥ k , j ≥ k ; если имеется мо дулю элемен т aˆij матр ицы A k −1 н еско лько максимальн ых по мо дулю элемен то в , то в едущ им в ыбир ается лю бо й из н их ; этастр атегия н аз ыв ается в ыбо р о м в едущ его элемен тапо в сей м ат р и це. Зам еч ан и е 7. П рим е н е н ие ст ра т е гий в ы бо ра в е дущих эле м е н т о в по ст о лбцуи по в се й м а т рице о бе спе чива е т для эле м е н т о в м а т риц Nˆ k в ы по лн е н ие н е ра в е н ст в а nˆij ≤ 1 . Зам еч ан и е 8. С уще ст в ую т м а т рицы , для ко т о ры х прим е н е н ие ст ра т е гии в ы бо ра в е дуще го эле м е н т а по ст о лбцу в о бо зн а че н иях (14) прив о дит к (k )

в ы по лн е н ию со о т н о ш е н ия α k = 2 α0 для в се х k . У ка за н н ы й ро ст эле м е н т о в до ст ига е т ся н а м а т рица х спе циа ль н о го в ида . В пра кт иче ских в ы числе н иях о н о ка зы ва е т ся, ка к пра в ило , н е слиш ко м бо ль ш им . k

16

ст ра т е гии в ы бо ра К а ко ва бы н и бы ла м а т рица A , прим е н е н ие в е дуще го эле м е н т а по в се й м а т рице в о бо зн а че н иях (14) приво дит к в ы по лн е н ию при в се х k со о т н о ш е н ия

α k ≤ f (k ) ⋅ α 0 , где 1

1 1 1 2 f (k ) ≤ k 2 ⋅  213 2 4 3 Kk k −1  .   1

О т м е т им , чт о эт а о це н ка по -видим о м усиль н о за в ы ш е н а , т а к ка к до сих по р н е н а йде н о н и о дн о й м а т рицы , дляко т о ро й f ( k ) ≥ k . В н и м ан и е! Если м а т рица A им е е т пре о бла да ю щую гла в н ую диа го н а ль m

aii > ∑ aij ,

i = 1,K, m

j =1 j ≠i

и н е о суще ст в ляе т ся в ы бо р в е дущих эле м е н т о в , т о при ре а лиза ции прям о го хо да м е т о да Г а усса н е про исхо дит ро ст эле м е н т о в . 2.3. К о м пакт н ая схем ам етод аГау сса Е сли в ыпо лн ен о усло в ие (6), то для матр ицы A сущ еств ует р аз ло ж ен ие (9). О бо з н ачим чер ез

LU

lij и uij элемен ты матр иц L и U ,

со о тветствен н о . Д ля в сех i, j = 1,K, m имею тместо р ав ен ства

aij =

–

min(i , j )

∑l

ir

⋅ urj .

r =1

Э ти ур ав н ен ия о тн о сительн о lij и uij р екур р ен тн о р аз р еш имы, пр и это м

 u11 = a11,  a u1 j = a1 j , l j1 = j1 , j = 2,3,K, m, u11  i −1  uii = aii − ∑lir ⋅ uri , i = 2,3,K, m,  r=1 j−1  a ji − ∑l jr ⋅ uri  i −1 r=1  u = a − ∑l ⋅ u , l = , ji ij ij ir rj  uii r=1  i = 2,3,K, m, j = i + 1, i + 2,K, m. 

(19)

17

И з (19) по лучаем

1 l11 ⋅ u11 = A , 1

1 2 A 1 2  ,K, lmm ⋅ umm = l22 ⋅ u22 = 1 A  1

1 2 K m A  1 2 K m . 1 2 K m − 1 A  1 2 K m − 1 L и U в

Ф о р мулы (19), по з в о ляю щ ие н айти тр еуго льн ые матр ицы р аз ло ж ен ии (9), н аз ыв аю тся ко м пак т н о й схем о й м ет о д аГау сса.

2.4. М ет о д пр о го н ки П усть матр ица A я в ляется тр ех диаго н альн о й aij = 0, i − j > 1 . Глав н ую и

(

по бо чн ые

{αi },

диаго н али

матр ицы

A

о бо з н ачим

)

чер ез

{γ i },

i = 1, K, m ,

i = 2,K, m , {βi }, i = 1,K, m − 1 ; сто лбец св о бо дн ых член о в системы (1)

о бо з н ачим чер ез {φi }, i = 1,K, m . Т епер ьсистему (1) мо ж н о з аписатьв в иде

= φ1 , γ 1 x1 + β1 x2   (20) α i xi −1 + γ i xi + β i xi +1 = φi , i = 2,K, m − 1,  α x +γ x = φm.  m m−1 m m П о стр о им ф о р мулы LU – р аз ло ж ен ия матр ицы A системы (20):

A = LU ,

 γ1  α2  M  A= M  M 0  0

β1

0

γ2 M M

β2 K 0 0 M M M O M O M M M M M O 0 K α m−1 γ m−1 αm 0 K 0

M 0 0

K

0

0

0   0  M   M , M  β m−1   γm 

18

1   l2 L=M  0 0 

0 K 0 1 K 0 M O M 0 K 1 0 K lm

0  0 M ,  0 1 

 v1  0 U =M  0 0 

0   0  M .  wm −1  vm 

w1 K 0 v2 K 0 M O M 0 K vm−1 0 K 0

В это м случае ф о р мулы (19) пр ин имаю тв ид

v1 = γ 1,

w1 = β1,

l2 =

vi = γ i − li wi ,

wi = βi ,

li +1 =

α2

v1

αi +1

i = 2,3, K, m.

,

vi

,

А лго р итм р еш ен ия системы (20) пр ин я то з аписыв атьв в иде:

x k = ξ k xk +1 + ηk ,

k = 1, K, m − 1,

( 21)

где ко эф ф ициен ты ξ k , ηk в ычисля ю тся по р екур р ен тн ым ф о р мулам

β1 φ1  = − , = , ξ η 1  1 γ1 γ1  − βk φ − α kη k −1 ξ k = , ηk = k ,  γ k + α k ξ k −1 γ k + α k ξ k −1   k = 2,K, m − 1.

(22)

А лго р итм (21)-(22) р еш ен ия систем с тр ех диаго н альн о й матр ицей н аз ыв ается м ет о д о м пр о го н ки . Сн ачала по ф о р мулам (22) н ах о дя тся ко эф ф ициен ты ξ k , η k (k = 1,K , m − 1) . В ычислен ие в еличин ξ k ,η k н аз ыв ается пр ям о й пр о го н ко й . Т епер ь, р еш ая со в местн о по следн ее ур ав н ен ие системы (20) и ур ав н ен ие (21), о твечаю щ ее k = m − 1 , н айдем ко о р дин аты

xˆm , xˆm−1 р еш ен ия

xˆm−1 , по ф о р мулам (21) xˆk (k = m − 2, m − 3,K,1) .

системы, если то лько по лучен н ая системасо в местн а. Зн ая о пр еделим

о стальн ые

ко о р дин аты

р еш ен ия

В ычислен ие ко о р дин ат xˆk р еш ен ия системы (20) в о бр атн о м по р я дке н аз ыв ается

19

о б р ат н о й пр о го н ко й . Д ля р еализ ации алго р итма по тр ебуется пр имер н о O (m ) ар иф метических о пер аций. Зам еч ан и е 9. П уст ь м а т рица сист е м ы (20) им е е т пре о бла да ю щую гла в н ую диа го н а ль и в ы по лн е н ы усло в ия:

γ k ≥ αk + βk + δ , где δ > 0, α 1 = 0, β m = 0 . У сло в ия (23) га ра н т ирую т

xˆ сист е м ы

k = 1, K, m,

суще ст в о в а н ие

(23)

е дин ст в е н н о го

ре ш е н ия

(20) и по зво ляю т о суще ст в ит ь прям о й и о бра т н ы й хо ды про го н ки (ф о рм улы (21)-(22)). П ри эт о м

max xˆk ≤

0≤ k ≤ m

1 ⋅ max φ k . δ 0≤ k ≤ m

2.4. То ч н о ст ьр еш ен и я Т о чн о сть я в ляется в аж н ейш ей х ар актер истико й лю бо го числен н о го мето да, в то м числе и р аз ло ж ен ия матр ицы н а мн о ж ители. П усть н айден о LU – р аз ло ж ен ие матр ицы A . О бо з н ачим чер ез пр я мо го х о дамето даГаусса. Т о гда

~ ~ L , U р еальн о в ычислен н ые матр ицы

LU = A + Μ и экв ив ален тн о е в о з мущ ен ие Μ удо в летво р я ет н ер ав ен ств у (см. ф о р мулы (14),(15),(16))

Μ

сф

~ ≤ f ( m ) ⋅ p − t +1 A сф ,

где ф ун кция f (m ) з ав исит то лько о т р аз мер н о сти m матр ицы системы (1) и спо со бапо лучен ия р аз ло ж ен ия . Св я з ь то чн о сти р еш ен ия системы с то чн о стью р аз ло ж ен ия матр ицы н а ~ мн о ж ители го р аз до сло ж н ее. Реальн о в ычислен н о е р еш ен ие x системы (1) я в ляется то чн ым р еш ен ием в о з мущ ен н о й системы (2): это м

(A + Ε)~x = b + ε . П р и

≤ ϕ ( m ) ⋅ p − t +1 A сф , ε е ≤ ψ ( m ) ⋅ p − t +1 b е , ~ где ϕ ( m) +ψ ( m ) ≤ 2 ⋅ f (m ), если то лько в пр еделах таких в о з мущ ен ий матр ица A + Ε о стается н ев ыр о ж ден н о й. Ε

сф

Д ля о тн о сительн о й по гр еш н о сти р еш ен ия системы (1) в это м случае имеет место о цен ка

xˆ − ~ x ~ δxˆ = ≤ 2 f ( m) ⋅ cond cф A ⋅ p −t +1 . xˆ

20

3. И т ер аци о н н ы е м ет од ы И з ло ж ен н ые в ыш е пр я мые мето ды р еш ен ия системы (1) тео р етически пр ив о дя т к то чн о му р еш ен ию . Здесь мы о пиш ем итер ацио н н ые мето ды, с по мо щ ью ко то р ых в пр ин ципе мо ж ет быть по стр о ен о н е само р еш ен ие по следо в ательн о сть элемен то в

x ( n ) к н ему сх о дя щ

ая ся

(x

(n)

xˆ ,

а

→ xˆ пр и n → ∞ ) .

Н еко то р ый элемен т x , до стато чн о близ кий к пр еделу по следо в ательн о сти xˆ , пр ин имается з а пр иближ ен н о е р еш ен ие. Т аким о бр аз о м, итер ацио н н ые мето ды имею т н еко то р ую тео р етически н ео бх о димую о ш ибку (алго р и т м и ч еск у ю о ш и б ку мето да). Э то о бсто я тельство н е я в ляется их н едо статко м по ср ав н ен ию с пр я мыми мето дами. А лго р итмическая о ш ибка мо ж етбыть сделан а мен ьш е, чем по гр еш н о сть, в ыз в ан н ая о ш ибками о кр углен ия пр и р еализ ации пр я мо го мето да. О бщ им н едо статко м итер ацио н н ых мето до в я в ляется н аличие до по лн ительн ых усло в ий для сх о димо сти по следо в ательн о сти пр иближ ен н ых р еш ен ий. К о н ечн о , сх о димо сть итер ацио н н ых мето до в мо ж ет иметь место то лько тео р етически. П р и н аличии о ш ибо к о кр углен ия в ычислен н ые пр иближ ен ия будут о тличаться о т истин н ых . П о это му н ельз я гар ан тир о в ать, что в ычислен н ые пр иближ ен ия с до стато чн о бо льш ими н о мер ами леж ат в ско ль уго дн о мало й о кр естн о сти р еш ен ия xˆ . М о ж н о то лько утв ер ж дать, что о н и по падаю т в н еко то р ую о кр естн о сть р еш ен ия , р аз мер ы ко то р о й о пр еделяю тся то чн о стью в ычислен ий. П о сле то го как по лучен о пр иближ ен н о е р еш ен ие из этой о кр естн о сти, пр о до лж ен ие в ычислен ий н е по в ыш аетто чн о сти р ез ультата. (N )

3.1. П р и н ци псжи м аю щи х о т о б р ажен и й Бо льш ин ство итер ацио н н ых мето до в (и н е то лько для систем лин ейн ых ур ав н ен ий) мо ж ет быть по лучен о пр имен ен ием пр ин ципа н епо дв иж н о й то чки (сж имаю щ их о то бр аж ен ий). П р ив едем его ф о р мулир о в ку. П усть E - по лн о е лин ейн о е н о р мир о в ан н о е пр о стр ан ство и F - его о то бр аж ен ие в себя . F н аз ыв ается сжи м аю щ и м н а мн о ж естве X ⊆ E , если

сущ еств ует тако е число q ∈ [0,1) , что для лю бых н ер ав ен ств о

x′ и x ′′ из X в ыпо лн ен о

F ( x ′) − F ( x ′′) ≤ q x ′ − x ′′ . П р ед ло жен и е (пр и н ци псжи м ающи х о т о б р ажен и й ). П уст ь о гра н иче н н о е м н о ж е ст в о в E м н о ж е ст в е X . Т о гда ура в н е н ие

(X

X -за м кн ут о е

⊆ E ) и о т о бра ж е н ие F , сж им а ю ще е н а x = F (x )

( 24 )

21

X е дин ст в е н н о е ре ш е н ие xˆ . П ри эт о м при лю бо м в ы бо ре в е кт о ра

им е е т в

x ( 0) ∈ X

по сле до ва т е ль н о ст ь

x (n +1) = F ( x ( n ) ) схо дит сяпри n → ∞ к

( 25)

xˆ .

3.2. М ет о д пр о ст ы хи т ер аци й (по след о в ат ельн ы х пр и б ли жен и й ) Замен им систему (1) экв ив ален тн о й системо й, имею щ ий в ид (24):

x = Bx + c. П о стр о им по н ачальн о му пр иближ ен ию з адав аемый ф о р муло й (ср ав н ите с ф о р муло й (25))

x ( n +1) = Bx ( n ) + c,

( 26)

x ( 0) итер ацио н н ый пр о цесс, n = 0,1,K

( 27)

А лго р итм (27) н аз ыв ается мето до м пр о ст ой и т ер аци и или ст аци о н ар н ы м мето до м. У каж ем н аибо лее р аспр о стр ан ен н ые спо со бы пер ех о да о т системы (1) к экв ив ален тн о й системе в ида(26):

x = x − Ax + b, B = (I − A), c = b. B = (I − HA ), c = Hb , 2. x = x + H (b − Ax ), где H - н еко то р ая н ев ыр о ж ден н ая матр ица. −1 B = (I − τS −1 A ), c = τS −1b, 3. x = x + τS (b − Ax ), где τ - число в о й пар аметр , S - н ев ыр о ж ден н ая матр ица. 1.

Д ля тр етьего спо со ба пер ех о да о тисх о дн о й системы (1) к экв ив ален тн о й системе (26) алго р итм (27) пр ин я то з аписыв атьв в иде

x ( n +1) − x ( n ) S + Ax ( n ) = b. τ

( 28)

Ф о р мула (28) н аз ыв ается о б щи м н еяв н ы м м ет о д о м пр о ст ой и т ер аци и . Зн ачен ие пар аметр а τ в ыбир ается для каж до й ко н кр етн о й системы так, что бы ско р о стьсх о димо сти по следо в ательн о сти пр иближ ен ий Тео р ем а 1. Если ре ш е н ие

−1 xˆ = (I − B ) b

x ( n ) быламаксимальн о й.

B ≤ q < 1, т о сист е м а (26) им е е т е дин ст в е н н о е и м е т о дпро ст о й ит е ра ции (27) схо дит ся

lim x ( n ) = xˆ

n→ ∞

( 0)

при лю бо м в ы бо ре н а ча ль н о го приближ е н ия x со ско ро ст ь ю н е м е дле н н е е , че м сум м а ге о м е т риче ско й про гре ссии со зн а м е н а т е ле м q . П ри эт о м :

22

xˆ − x

(n )

qn ≤ x (1) − x ( 0) , 1− q

xˆ − x ( n ) ≤

q x ( n ) − x( n −1) . 1− q

В н и м ан и е! Для схо дим о ст и м е т о да про ст о й ит е ра ции до ст а т о чн о в ы по лн е н ияв лю бо й н о рм е усло в ия B < 1 . Тео р ем а 2. П уст ь м а т рица A сист е м ы (1) н е в ы ро ж де н а . Т о гда м е т о д про ст о й ит е ра ции (27) схо дит ся при лю бо м в ы бо ре н а ча ль н о го приближ е н ия

x ( 0) т о гда

(

и т о ль ко т о гда , ко гда спе кт ра ль н ы й ра диус λB м а т рицы

λk (B ) , где λk (B ) - со бст в е н н ы е числа м а т рицы е дин ицы λB = max k

B ).

B ме нь ш е

О цен им степен ьв лия н ия о ш ибки о кр углен ия н ав ычислительн ый пр о цесс. О бо з н ачим

~ x (n)

чер ез

р еальн о

в ычислен н о е з н ачен ие

пр иближ ен ия , а чер ез δ - в екто р по гр еш н о сти о кр углен ия н а В место ф о р мулы (27) по лучим: (n )

n -о го

n -о м ш аге.

x~( n+1) = Bx~(n) + δ ( n+1) , n = 0,1,2,K . ( n +1) = x~ ( n +1) − x ( n +1) н а (n + 1) -о м ш аге имеет В екто р суммар н о й о ш ибки ε

в ид:

(

)

ε ( n+1) = B~ x ( n) − B~ x ( n) + δ ( n+1) = B ~ x (n) − x (n) = Bε ( n) + δ (n+1) , n = 0,1,2,K . В усло в ия х тео р емы 1 имеем:

ε (n )

ε ( n+1) ≤ q ε ( n ) + δ (n ) , 0 < q < 1, n = 0,1,2,K. И з по лучен н о го н ер ав ен ства следует, что с р о сто м n суммар н ая о ш ибка ( j) в едет себя как в еличин а по р я дка δ = max max δ i , то есть т о ч н о ст ь 0≤ j ≤ n 1< i< m

р езу льт ат а со о т в ет ст в у етт о ч н о ст и в ы по лн ен и я ар и фм ет и ч ески х о пер аци й . Э то о бщ ее св о йство итер ацио н н ых мето до в я в ляется их в аж н ейш им пр еимущ еств о м пер ед др угими числен н ыми мето дами. Зам еч ан и е 10. Т е о ре м а 2 хо т я и да е т н е о бхо дим ы е и до ст а т о чн ы е усло вия схо дим о ст и м е т о да про ст ы х ит е ра ций, н о ча ст о е е пра кт иче ско е зн а че н ие н е в е лико . Ра ссм о т рим сист е м у (1) с м а т рице й A из прим е ра 1. В о спо ль зо в а в ш ись пе рв ы м спо со бо м пе ре хо да к сист е м е (26), до пуска ю ще й прим е н е н ие м е т о да про ст ы х ит е ра ций, по лучим эквив а ле н т н ую сист е м у x = Bx + c = ( I − A) x + c, в ко т о ро й м а т рица B им е е т в ид

23

0 − a  0 0 B = M M  0 0 0 0 

0   0  O M M .  K 0 − a K 0 0  K 0 K 0

В е сь спе кт р м а т рицы B св о дит ся к о дн о й т о чке λ = 0 . С т о чки зре н ия т е о ре м ы 2 эт о о че н ь хо ро ш ий случа й. О дн а ко в прим е ре 1 бы ло по ка за н о , чт о при до в о ль н о скро м н ы х ра зм е ра х м а т рицы A ( m = 40) при a = 7 м ы н а хо дим ре ш е н ие сист е м ы (1) с о гро м н о й по гре ш н о ст ь ю . В ы ясн им , чт о буде т про исхо дит ь , е сли для ре ш е н иясист е м ы испо ль зо в а т ь м е т о дпро ст ы х ит е ра ций. Б уде м счит а т ь , чт о по ф о рм уле (27) в ы числяю т ся н е прира ще н ия ρ

(n)

в е кт о ры

x(n ) , а

= x ( n ) − x ( n−1) :

ρ ( n +1) = Bρ ( n ) = B 2 ρ ( n −1) = K = B n ρ (1) . В ре а ль н ы х в ы числе н иях по лучим

ρ ( k +1) = (B k + ∆ k )ρ (1) ,

где

∆ k - м а т рица о ш ибо к н а k - о м ш а ге . k Н е т рудн о по дсчит а т ь , чт о B им е е т эле м е н т ы о т личн ы е о т н уля т о ль ко

k в по зициях (1, k + 1), (2, k + 2),K и ка ж ды й из эт их эле м е н т о в ра в е н (−a) и

B m = 0.

П ри k ≤ m − 1 им е е м

ρ ( k +1)

k ≤ B + ∆k ∞

( 1) ⋅ ρ ∞

∞

≈ a k ρ (1) ∞ .

О т сю да сле дуе т , чт о е сли a > 1 , н о н е н а ст о ль ко в е лико , чт о бы н а ст упило пе ре по лн е н ие , ко гда k ≈ m , т о схо дим о ст и ит е ра ций в се ра в н о н е буде т . В са м о м ( m+1)

= ∆ m ρ . П о эт о м у для в се х ρ де ле , по ско ль ку B = 0 , ∆ m ≠ 0 , т о по сле дую щих ит е ра ций по лучит ся а н а ло гичн а я сит уа ция, ко т о ра я, о че в идн о , по в т о рит ся ско ль ко уго дн о ра з. Та ким о бра зо м , усло вия т е о ре м ы в ы по лн е н ы , а ит е ра ции в ре а ль н ы х в ы числе н иях н е схо дят ся. Д ля уско р ен ия сх о димо сти итер ацио н н ый пр о цесс (27) до лж ен быть по стр о ен так, что бы н о р маматр ицы B была в о з мо ж н о мен ьш е. Е сли в о з в р атиться к спо со бам пер ех о да о тсистемы (1) к экв ив ален тн о й системе (26), это о з н ачает, m

(1)

24

что н уж н о в ыбир ать матр ицу

H или, со о тветствен н о ,

пар аметр

τ

и

−1

матр ицу S так, что бы н о р мы I − HA или I −τS A были в о з мо ж н о мен ьш е. −1

Е сли бы мы мо гли по ло ж ить H = A , то пр о цесс (пр и о тсутствии о ш ибо к о кр углен ия ) со ш елся бы з а о дн у итер ацию . И спо льз уя до по лн ительн ые св о йства −1

з адан н о й матр ицы A , мо ж н о в ыбир атьматр ицы H , пр иближ аю щ иеся к A . Зам еч ан и е 11. В прило ж е н иях до в о ль н о ча ст о в ст ре ча ю т ся сист е м ы с по ло ж ит е ль н о о пре де ле н н ы м и сим м е т ричн ы м и м а т рица м и. М ы н е прив о дим зде сь по дро бн о ст и прим е н е н ия ит е ра цио н н ы х м е т о до в для ре ш е н ия т а ких сист е м . И х изло ж е н ие м о ж н о н а йт и, н а прим е р, в [3]. О т м е т им т о ль ко , чт о для лю бо й по ло ж ит е ль н о о пре де ле н н о й сим м е т ричн о й м а т рицы

A (aij = a ji , ( Ax , x ) > 0, x ≠ 0 ) м о ж н о т а к по до бра т ь м а т рицу H , чт о бы

ит е ра цио н н ы й про це сс (27) схо дился. Де йст в ит е ль н о , т а к ка к со бст в е н н ы е числа м а т рицы A прин а дле ж а т н е ко т о ро м уин т е рв а лу (0; α ) , т о м о ж н о по ло ж ит ь

H =

2 2 ⋅ I , B = I − HA = I − A. α α

Н е т рудн о в иде т ь , чт о спе кт ра ль н ы й ра диус м а т рицы B м е н ь ш е е дин ицы

2   λk (B ) = 1 − ⋅ λk ( A), α 

 − 1 < λk (B ) < 1. 

О т м е т им , чт о случа й по ло ж ит е ль н о о пре де ле н н о й сим м е т ричн о й м а т рицы яв ляе т ся до ст а т о чн о о бщим , т а к ка к сист е м а (1) экв ив а ле н т н а сист е м е

AT Ax = AT b с по ло ж ит е ль н о о пре де ле н н о й сим м е т ричн о й м а т рицей. О дн а ко T м а т рица A A яв ляе т ся, во о бще го во ря, зн а чит е ль н о хуж е о бусло в ле н н о й, че м м а т рица A . П о эт о м у пра кт иче ско е зн а че н ие т а ко го пре о бра зо ва н ия сист е м ы н е в е лико . 3.3. Алго р и т м ы о сн о в н ы х (пр о ст ей ш и х) и т ер аци о н н ы х м ет од ов 1) М ет о д р елаксаци и (о слаб лен и я). А лго р итм мето да р елаксации з адается ф о р муло й

x ( n +1) = x ( n ) + τ (b − Ax ( n ) ), B = I − τ ⋅ A,

n = 0,1, K,

c = τb,

или (см. (28))

x ( n+1) − x ( n ) + Ax ( n ) = b n = 0,1,K, τ S = I , τ > 0.

25

М ето д р елаксации сх о дится для симметр ичн о й по ло ж ительн о о пр еделен н о й матр ицы A пр и 0 < τ < 2 A . 2) М ет о д Яко б и . А лго р итм мето даЯ ко би з адается ф о р муло й

x ( n+1) = x ( n ) + D −1 (b − Ax ( n ) ), n = 0,1,K, D = diag (a11 , a 22 ,K, amm ), aii ≠ 0, i = 1,K, m,

B = I − D −1 A,

c = D −1b,

или (см. (28))

D ⋅ (x ( n +1) − x ( n ) ) + Ax ( n ) = b n = 0,1, K, S = D , τ = 1. М ето д Я ко би сх о дится , если матр ица A имеетпр ео бладаю щ ую глав н ую

диаго н аль: m

aii > ∑ aij

i = 1,K, m .

j =1 j ≠i

A в в иде A = AL + D + AU ,

3) М ет о д Зей д еля. П р едстав им матр ицу

( 29)

где

 0   a 21 AL =  a 31   M a  m1

0

K

0

0

K

0

a32 M

K O

0 M

a m 2 K am ,m −1

0  0   0  a 21 0 , AL =  a 31   M  M a 0   m1

0

K

0

0

K

0

a32 M

K O

0 M

a m 2 K a m ,m −1

D = diag (a11, a 22 , K, a mm ), aii ≠ 0, i = 1, K, m. А лго р итм мето даЗейделя з аписыв ается в в иде (см. (29)):

( AL + D )x ( n +1) + AU x ( n ) = b, n = 0,1,K , −1 −1 B = − ( AL + D ) AU , c = ( AL + D ) b,

или (см. (28))

( AL + D )⋅ (x (n +1) − x ( n ) ) + Ax ( n ) S = AL + D ,

= b, τ = 1.

n = 0,1,K ,

0  0 0 ,  M 0 

26

М ето д Зейделя н ея в н ый, н о матр ица AL + D легко о бр атима. О тсю дапо лучаем в ычислительн ые ф о р мулы алго р итмамето даЗейделя:

x

( n +1) k

=

1 a kk

   − ∑ akj( n+1) − ∑ a kj( n ) + bk ,   j< k  j >k 

k = 1,K , m .

П о тео р еме 2 мето д Зейделя сх о дится то гда и то лько то гда, ко гда в се

со бствен н ые з н ачен ия матр ицы B = −( AL + D ) AU = I − ( AL + D ) A по мо дулю мен ьш е един ицы. Н етр удн о пр о в ер ить, что эти со бствен н ые з н ачен ия −1

−1

det ( AL + D + λAU ) = 0. М ето д Зейделя сх о дится , если матр ица A имеетпр ео бладаю щ ую глав н ую

я в ляю тся ко р н я ми ур ав н ен ия

диаго н аль. Е сли матр ица A симметр ичн ая и по ло ж ительн о о пр еделен н ая , то мето д Зейделя я в ляется сх о дя щ имся . Следо в ательн о , мето д Зейделя в сегда сх о дится для экв ив ален тн о й системы A Ax = A b. 4) М ет о д в ер хн ей р елаксаци и . В о бо з н ачен ия х (29) алго р итм мето да в ер х н ей р елаксации з адается ф о р муло й (см. (28)) T

T

x ( n+1) − x (n ) (D + ωAL ) + Ax ( n ) = b ω S = D + ωAL , τ = ω > 0, или (см. (27))

(

)

n = 0,1,K,

x (n +1) = I − (D + ωAL ) ⋅ ωA x (n ) + ω (D + AL ) b, n = 0,1, K, −1

−1

B = I − (D + ωAL ) ⋅ ωA = (D + ωAL ) ((1 − ω ) D − ωAU ), −1

−1

c = ω (D + AL ) b. −1

П р и ω = 1 о тсю дапо лучаем мето д Зейделя. Е сли матр ица A симметр ичн ая и по ло ж ительн о о пр еделен н ая , то мето д в ер х н ей р елаксации я в ляется сх о дя щ имся пр и 0 < ω < 2 . 4. И т ер аци о н н о е у т о ч н ен и е р еш ен и я (N )

П усть x - р еальн о в ычислен н о е (лю бым спо со бо м, н апр имер , мето до м Гаусса) р еш ен ие системы (1). Запиш ем то чн о е р еш ен ие xˆ системы (1) в в иде

xˆ = x ( N ) + ∆( N ) . П о дстав ив это в ыр аж ен ие в (1), по лучим

27

A∆( N ) = r ( N ) ,

(30)

r ( N ) = b − Ax ( N ) . В екто р r ( N ) н аз ыв ается н ев я з ко й. Т епер ь, р еш ая систему (N ) (30), н айдем по пр ав ку ∆ . Следую щ ее пр иближ ен ие к то чн о му р еш ен ию ~ ~ ( N +1) = x ( N ) + ∆( N ) , где ∆( N ) - р еальн о системы (1) по лучается как x

где

в ычислен н о е

р еш ен ие

системы

(30).

Затем

в ычисляем

н ев я з ку

r ( N +1) = b − Ax ( N +1) и в то р ую по пр ав ку к то чн о му р еш ен ию ∆( N +1) как р еш ен ие ( N +1) . В то р ым пр иближ ен ием к р еш ен ию будет системы (30) с пр ав о й частью r ~ ( N +2 ) = x ( N +1) + ∆( N +1) итак далее. в екто р x Будем считать, что числен н ый мето д р еш ен ия системы (30) и пр имен я емая маш ин н ая ар иф метика в ычислен ия н ев я з ки тако в ы, что р еальн ая по пр ав ка

~ ∆( N ) удо в летв о р я етусло в ию

~ ∆( N ) − ∆( N ) ∆

(N )

е

≤θ,

е

θ з аметн о мен ьш е един ицы. О сн о в н ая тр удн о сть в удо в летво р ен ии это го (N ) усло в ия св я з ан асо спо со бо м в ычислен ия н ев я з ки. Е сли x до статочн о близ ко к где

то чн о му р еш ен ию , то н ев я з ка мала и ее в ычислен ие пр ив о дит к бо льш им о тн о сительн ым о ш ибкам. К р о ме то го , мало сть н ев я з ки мо ж ет пр ив ести к з н ачительн о й по тер е то чн о сти пр и в ычислен ии по пр ав ки ∆ (в ычислен ия в близ и маш ин н о го н уля). П о это му о бычн о по ступаю тследую щ им о бр аз о м: 1) В ычисляю тн ев я з ку с удв о ен н о й то чн о стью . 2) Н о р мир ую тн ев я з ку. 3) Реш аю тсистему (30). 4) У мн о ж аю т в ычислен н ую по пр ав ку н а в еличин у о бр атн ую н о р мир ую щ ему мн о ж ителю . П р о цесс уто чн ен ия р еш ен ия тем эф ф ектив н ее, чем мен ьш е θ . О бычн о до стато чн о пр о в ести 2-3 итер ации, что бы до стичьн уж н о й то чн о сти. Зам еч ан и е 12. П ри по сле до в а т е ль н о м в ы по лн е н ии про це сса ут о чн е н ия ре ш е н ия 1)-4) н е т н ика ких о сн о в а н ий о ж ида т ь суще ст в е н н о го ум е н ь ш е н ия н о рм н е в язо к. Б о ле е т о го , н о рм ы н е в язо к н а н е ко т о ры х ш а га х м о гут да ж е н е ско ль ко ув е личит ь ся. Н е см о т ря н а эт о т о чн о ст ь по сле до в а т е ль н ы х приближ е н ий (N )

x ( N ) по в ы ш а е т ся. О писа н н ы й про це сс ут о чн е н ия связа н с уст ра н е н ие м в лиян ия о бусло в ле н н о ст и м а т рицы исхо дн о й сист е м ы н а по гре ш н о ст ь в ре ш е н ии.

28

В н и м ан и е! Бо ле е п о дро бно е изло ж е ние ра с с м о т ре нных и дру гих м е т о до в ре ш е ния с ис т е м лине йных у ра вне ний м о ж но на йт и в [3], [4] и на с а йт е : http://www.srcc.msu.su/num_anal (с м . ра зде л «Уче бно -м е т о диче с кие м а т е риа лы» ). Зад ан и е. Н айдите р еш ен ие системы лин ейн ых ур ав н ен ий с то чн о стью ε = 10 −6 мето дами Гаусса, пр о сто й итер ации и Зейделя. В ар и ан т ы зад ан и й Но м ер

1

2

3

4

6

М ат р и ца

27.70153 -1.85121 -0.18283 -3.82808 -1.80561 28.07253 -1.87601 -0.18528 -3.87935 -1.82980 28.44353 -1.90080 -0.18773 -3.93062 -1.85398 28.81453 -1.92559 -0.19017 -3.98189 -1.87816 29.55654 -1.97518 -0.19507 -4.08443 -1.92653

2.71425 34.29314 1.68413 3.08101 3.17782 2.75060 34.75242 1.70669 3.12227 3.22038 2.78695 35.21171 1.72924 3.16353 3.26294 2.82330 35.67099 1.75180 3.20480 3.30550 2.89600 36.58956 1.79691 3.28733 3.39062

-0.85915 2.11113 24.80947 2.52143 2.32840 -0.87066 2.13941 25.14174 2.55520 2.35959 -0.88216 2.16768 25.47401 2.58897 2.39077 -0.89367 2.19596 25.80628 2.62274 2.42195 -0.91668 2.25250 26.47082 2.69027 2.48432

В ек т ор

0.99784 4.53818 3.07213 31.08655 -2.29968 1.01121 4.59896 3.11327 31.50288 -2.33048 1.02457 4.65974 3.15442 31.91922 -2.36128 1.03793 4.72052 3.19556 32.33556 -2.39208 1.06466 4.84208 3.27785 33.16823 -2.45368

-0.78454 -0.66302 3.91096 1.41026 34.34837 -0.79505 -0.67190 3.96334 1.42915 34.80840 -0.80556 -0.68078 4.01572 1.44804 35.26842 -0.81607 -0.68966 4.06810 1.46693 35.72844 -0.83708 -0.70742 4.17286 1.50470 36.64849

2.06829 0.11903 4.44773 -3.16207 0.84720 4.50730 -3.20442 0.85854 2.09599 0.12062 2.12369 0.12222 4.56687 -3.24677 0.86989 2.15139 0.12381 4.62644 -3.28912 0.88124 2.20679 0.12700 4.74557 -3.37381 0.90393

29

Но м ер

7

8

9

10

11

12

13

М ат р и ца

29.92754 -1.99997 -0.19752 4.13570 -1.95071 30.29854 -2.02477 -0.19997 -4.18696 -1.97489 30.66955 -2.04956 -0.20242 -4.23823 -1.99907 31.04055 -2.07435 -0.20487 -4.28950 -2.02325 17.26399 -1.15370 -0.11394 -2.38572 -1.12528 17.63499 -1.17850 -0.11639 -2.43698 -1.14947 18.00599 -1.20329 -0.11884 -2.48825 -1.17365

2.93236 37.04884 1.81946 3.32859 3.43318 2.96871 37.50812 1.84202 3.36985 3.47574 3.00506 37.96740 1.86458 3.41112 3.51830 3.04141 38.42669 1.88713 3.45238 3.56086 1.69156 21.37197 1.04958 1.92013 1.98046 1.72791 21.83126 1.07213 1.96139 2.02302 1.76426 22.29054 1.09469 2.00266 2.06558

-0.92819 2.28078 26.80309 2.72404 2.51551 -0.93970 2.30905 27.13536 2.75781 2.54669 -0.95120 2.33733 27.46763 2.79158 2.57787 -0.96271 2.36560 27.79990 2.82535 2.60906 -0.53544 1.31569 15.46162 1.57139 1.45109 -0.54694 1.34396 15.79389 1.60516 1.48228 -0.55845 1.37224 16.12616 1.63893 1.51346

В ек т ор

1.07803 4.90286 3.31899 33.58457 -2.48448 1.09139 4.96364 3.36014 34.00091 -2.51528 1.10475 5.02442 3.40128 34.41725 -2.54608 1.11812 5.08520 3.44243 34.83359 -2.57688 0.62187 2.82826 1.91459 19.37358 -1.43320 0.63523 2.88904 1.95574 19.78992 -1.46400 0.64860 2.94982 1.99688 20.20626 -1.49480

-0.84759 -0.71630 4.22524 1.52359 37.10851 -0.85809 -0.72518 4.27761 1.54248 37.56853 -0.86860 -0.73406 4.32999 1.56136 38.02856 -0.87911 -0.74293 4.38237 1.58025 38.48858 -0.48894 -0.41320 2.43737 0.87890 21.40640 -0.49945 -0.42208 2.48975 0.89778 21.86642 -0.50995 -0.43096 2.54213 0.91667 22.32644

2.23449 0.12859 -4.80514 -3.41616 0.91527 2.26219 0.13019 4.86471 -3.45851 0.92662 2.28989 0.13178 4.92428 -3.50086 0.93797 2.31759 0.13338 4.98384 -3.54321 0.94931 1.28899 0.07418 2.77189 -1.97065 0.52798 1.31669 0.07577 2.83146 -2.01300 0.53933 1.34439 0.07737 2.89103 -2.05534 0.55068

30

Н о м ер

14

15

16

17

18

19

20

М ат р и ца

18.37699 -1.22808 -0.12129 -2.53952 -1.19783 18.74800 -1.25288 -0.12374 -2.59079 -1.22201 19.11900 -1.27767 -0.12618 -2.64206 -1.24620 19.49000 -1.30246 -0.12863 -2.69333 -1.27038 19.86100 -1.32725 -0.13108 -2.74460 -1.29456 22.70536 -1.51733 -0.14985 -3.13766 -1.47996 23.44736 -1.56692 -0.15475 -3.24020 -1.52832

1.80061 22.74982 1.11724 2.04392 2.10814 1.83696 23.20911 1.13980 2.08518 2.15070 1.87332 23.66839 1.16235 2.12645 2.19326 1.90967 24.12767 1.18491 2.16771 2.23582 1.94602 24.58696 1.20746 2.20897 2.27838 2.22471 28.10813 1.38039 2.52533 2.60468 2.29742 29.02669 1.42550 2.60785 2.68980

-0.56996 1.40051 16.45843 1.67270 1.54464 -0.58146 1.42878 16.79070 1.70647 1.57583 -0.59297 1.45706 17.12297 1.74024 1.60701 -0.60447 1.48533 17.45524 1.77400 1.63820 -0.61598 1.51361 17.78751 1.80777 1.66938 -0.70420 1.73037 20.33491 2.06667 1.90846 -0.72721 1.78692 20.99945 2.13421 1.97083

В ект ор

0.66196 3.01060 2.03803 20.62259 -1.52559 0.67532 3.07138 2.07917 21.03893 -1.55639 0.68869 3.13216 2.12032 21.45527 -1.58719 0.70205 3.19294 2.16146 21.87161 -1.61799 0.71542 3.25372 2.20260 22.28794 -1.64879 0.81787 3.71969 2.51805 25.47987 -1.88492 0.84460 3.84125 2.60034 26.31254 -1.94652

-0.52046 -0.43984 2.59450 0.93556 22.78647 -0.53097 -0.44872 2.64688 0.95445 23.24649 -0.54147 -0.45760 2.69926 0.97333 23.70651 -0.55198 -0.46648 2.75164 0.99222 24.16653 -0.56249 -0.47536 2.80402 1.01111 24.62656 -0.64305 -0.54344 3.20559 1.15591 28.15340 -0.66406 -0.56120 3.31035 1.19369 29.07344

1.37209 0.07896 2.95059 -2.09769 0.56202 1.39979 0.08056 3.01016 -2.14004 0.57337 1.42749 0.08215 3.06973 -2.18239 0.58472 1.45519 0.08374 3.12930 -2.22474 0.59606 1.48289 0.08534 3.18887 -2.26709 0.60741 1.69526 0.09756 3.64555 -2.59177 0.69440 1.75066 0.10075 3.76469 -2.67646 0.71709

31

Н о м ер

21

22

23

24

25

26

27

М ат р и ца

23.81837 -1.59171 -0.15720 -3.29147 -1.55251 24.18937 -1.61651 -0.15965 -3.34274 -1.57669 24.56037 -1.64130 -0.16210 -3.39400 -1.60087 24.93137 -1.66609 -0.16455 -3.44527 -1.62505 25.30238 -1.69089 -0.16699 -3.49654 -1.64923 25.57444 -1.70907 -0.16879 -3.53414 -1.66697 25.94545 -1.73386 -0.17124 -3.58541 -1.69115

2.33377 29.48598 1.44805 2.64912 2.73236 2.37012 29.94526 1.47061 2.69038 2.77492 2.40647 30.40454 1.49316 2.73164 2.81748 2.44282 30.86383 1.51572 2.77291 2.86004 2.47917 31.32311 1.53827 2.81417 2.90260 2.50583 31.65992 1.55482 2.84443 2.93381 2.54218 32.11920 1.57737 2.88569 2.97637

-0.73872 1.81520 21.33172 2.16798 2.00201 -0.75022 1.84347 21.66399 2.20175 2.03319 -0.76173 1.87175 21.99626 2.23552 2.06438 -0.77324 1.90002 22.32853 2.26929 2.09556 -0.78474 1.92829 22.66080 2.30305 2.12675 -0.79318 1.94903 22.90446 2.32782 2.14961 -0.80469 1.97730 23.23673 2.36159 2.18080

В ект ор

0.85797 3.90203 2.64148 26.72888 -1.97732 0.87133 3.96281 2.68262 27.14522 -2.00812 0.88469 4.02359 2.72377 27.56155 -2.03892 0.89806 4.08437 2.76491 27.97789 -2.06972 0.91142 4.14514 2.80606 28.39423 -2.10052 0.92122 4.18972 2.83623 28.69954 -2.12310 0.93459 4.25050 2.87738 29.11588 -2.15390

-0.67457 -0.57008 3.36273 1.21258 29.53347 -0.68507 -0.57896 3.41511 1.23146 29.99349 -0.69558 -0.58784 3.46749 1.25035 30.45351 -0.70609 -0.59672 3.51987 1.26924 30.91354 -0.71660 -0.60560 3.57224 1.28813 31.37356 -0.72430 -0.61211 3.61066 1.30198 31.71091 -0.73481 -0.62099 3.66303 1.32086 32.17093

1.77836 0.10234 3.82426 -2.71881 0.72844 1.80606 0.10394 3.88382 -2.76116 0.73978 1.83376 0.10553 3.94339 -2.80351 0.75113 1.86146 0.10713 4.00296 -2.84586 0.76248 1.88916 0.10872 4.06253 -2.88821 0.77382 1.90947 0.10989 4.10621 -2.91927 0.78214 1.93717 0.11148 4.16578 -2.96162 0.79349

32

Н о м ер

28

29

30

31

32

33

34

М ат р и ца

26.31645 -1.75865 -0.17369 -3.63668 -1.71533 26.68745 -1.78345 -0.17614 -3.68795 1.73952 26.98425 -1.80328 -0.17809 -3.72896 -1.75886 27.35526 -1.82807 -0.18054 -3.78023 -1.78304 27.72626 -1.85287 -0.18299 -3.83150 -1.80723 28.09726 -1.87766 -0.18544 -3.88277 -1.83141 28.46826 -1.90245 -0.18789 -3.93404 -1.85559

2.57853 32.57848 1.59993 2.92696 3.01893 2.61489 33.03777 1.62248 2.96822 3.06149 2.64397 33.40519 1.64053 3.00123 3.09554 2.68032 33.86448 1.66308 3.04250 3.13810 2.71667 34.32376 1.68564 3.08376 3.18066 2.75302 34.78304 1.70819 3.12502 3.22322 2.78937 35.24233 1.73075 3.16629 3.26578

-0.81619 2.00558 23.56900 2.39536 2.21198 -0.82770 2.03385 23.90127 2.42913 2.24317 -0.83691 2.05647 24.16708 2.45614 2.26811 -0.84841 2.08474 24.49935 2.48991 2.29930 -0.85992 2.11302 24.83162 2.52368 2.33048 -0.87143 2.14129 25.16389 2.55745 2.36166 -0.88293 2.16957 25.49616 2.59122 2.39285

В ект ор

0.94795 4.31127 2.91852 29.53222 -2.18470 0.96131 4.37205 2.95966 29.94856 -2.21550 0.97200 4.42068 2.99258 30.28163 -2.24014 0.98537 4.48146 3.03372 30.69796 -2.27094 0.99873 4.54224 3.07487 31.11430 -2.30174 1.01210 4.60302 3.11601 31.53064 -2.33254 1.02546 4.66379 3.15716 31.94698 -2.36334

-0.74532 -0.62987 3.71541 1.33975 32.63095 -0.75582 -0.63875 3.76779 1.35864 33.09098 -0.76423 -0.64585 3.80970 1.37375 33.45900 -0.77474 -0.65473 3.86207 1.39264 33.91902 -0.78524 -0.66361 3.91445 1.41152 34.37904 -0.79575 -0.67249 3.96683 1.43041 34.83906 -0.80626 -0.68137 4.01921 1.44930 35.29909

1.96487 0.11308 4.22535 -3.00396 0.80484 1.99257 -04.2849 -1.11467 3.04631 0.81618 2.01473 0.11595 4.33257 -3.08019 0.82526 2.04243 0.11754 4.39214 -3.12254 0.83661 2.07013 0.11913 4.45170 -3.16489 0.84795 2.09783 0.12073 4.51127 -3.20724 0.85930 2.12553 0.12232 4.57084 -3.24959 0.87065

33

Н о м ер

35

36

37

38

39

40

41

М ат р и ца

27.45419 -1.83469 -0.18120 -3.79390 -1.78949 27.82519 -1.85948 -0.18365 -3.84517 -1.81367 28.19620 -1.88427 -0.18609 -3.89644 -1.83786 28.56720 -1.90906 -0.18854 -3.94771 -1.86204 28.93820 -1.93386 -0.19099 -3.99898 -1.88622 28.93820 -1.93386 -0.19099 -3.99898 -1.88622 29.68021 -1.98344 -0.19589 -4.10152 -1.93459

2.69001 33.98695 1.66910 3.05350 3.14945 2.72636 34.44623 1.69165 3.09476 3.19201 2.76272 34.90552 1.71421 3.13603 3.23457 2.79907 35.36480 1.73676 3.17729 3.27713 2.83542 35.82408 1.75932 3.21855 3.31969 2.83542 35.82408 1.75932 3.21855 3.31969 2.90812 36.74265 1.80443 3.30108 3.40481

-0.85148 2.09228 24.58796 2.49892 2.30761 -0.86299 2.12056 24.92023 2.53268 2.33880 -0.87449 2.14883 25.25250 2.56645 2.36998 -0.88600 2.17711 25.58477 2.60022 2.40116 -0.89751 2.20538 25.91704 2.63399 2.43235 -0.89751 2.20538 25.91704 2.63399 2.43235 -0.92052 2.26193 26.58158 2.70153 2.49472

В ект ор

0.98893 4.49766 3.04470 30.80899 -2.27915 1.00230 4.55844 3.08584 31.22533 -2.30995 1.01566 4.61922 3.12699 31.64166 -2.34075 1.02902 4.68000 3.16813 32.05800 -2.37155 1.04239 4.74078 3.20927 32.47434 -2.40235 1.04239 4.74078 3.20927 32.47434 -2.40235 1.06912 4.86234 3.29156 33.30701 -2.46395

-0.77754 -0.65710 3.87604 1.39767 34.04169 -0.78805 -0.66598 3.92842 1.41656 34.50171 -0.79855 -0.67486 3.98080 1.43545 34.96174 -0.80906 -0.68374 4.03318 1.45434 35.42176 -0.81957 -0.69262 4.08556 1.47322 35.88178 -0.81957 -0.69262 4.08556 1.47322 35.88178 -0.84058 -0.71038 4.19032 1.51100 36.80183

2.04982 0.11797 4.40802 -3.13384 0.83963 2.07752 0.11956 4.46759 -3.17618 0.85098 2.10522 0.12115 4.52716 -3.21853 0.86232 2.13292 0.12275 4.58672 -3.26088 0.87367 2.16062 0.12434 4.64629 -3.30323 0.88502 2.16062 0.12434 4.64629 -3.30323 0.88502 2.21602 0.12753 4.76543 -3.38793 0.90771

34

Н о м ер

42

43

44

45

46

47

48

М ат р и ца

30.05121 -2.00824 -0.19834 -4.15278 -1.95877 24.28830 -1.62312 -0.16030 -3.35641 -1.58314 28.24566 -1.88758 -0.18642 -3.90328 -1.84108 28.61667 -1.91237 -0.18887 -3.95455 -1.86526 28.98767 -1.93716 -0.19132 -4.00581 -1.88945 29.35867 -1.96196 -0.19377 -4.05708 -1.91363 29.72967 -1.98675 -0.19621 -4.10835 -1.93781

2.94447 37.20193 1.82698 3.34234 3.44737 2.37981 30.06774 1.47662 2.70138 2.78627 2.76756 34.96676 1.71721 3.14153 3.24024 2.80391 35.42604 1.73977 3.18279 3.28280 2.84027 35.88532 1.76232 3.22405 3.32536 2.87662 36.34460 1.78488 3.26532 3.36792 2.91297 36.80389 1.80744 3.30658 3.41048

-0.93203 2.29020 26.91385 2.73530 2.52590 -0.75329 1.85101 21.75259 2.21075 2.04151 -0.87603 2.15260 25.29680 2.57096 2.37414 -0.88753 2.18088 25.62907 2.60473 2.40532 -0.89904 2.20915 25.96134 2.63849 2.43651 -0.91055 2.23742 26.29361 2.67226 2.46769 -0.92205 2.26570 26.62588 2.70603 2.49887

В ект ор

1.08248 4.92312 3.33271 33.72335 -2.49475 0.87489 3.97901 2.69360 27.25624 -2.01633 1.01744 4.62733 3.13247 31.69717 -2.34486 1.03081 4.68811 3.17362 32.11351 -2.37566 1.04417 4.74889 3.21476 32.52985 -2.40646 1.05753 4.80966 3.25591 32.94619 -2.43726 1.07090 4.87044 3.29705 33.36253 -2.46805

-0.85109 -0.71926 4.24269 1.52989 37.26185 -0.68788 -0.58132 3.42908 1.23650 30.11616 -0.79995 -0.67604 3.98778 1.43797 35.02307 -0.81046 -0.68492 4.04016 1.45685 35.48310 -0.82097 -0.69380 4.09254 1.47574 35.94312 -0.83148 -0.70268 4.14492 1.49463 36.40314 -0.84198 -0.71156 4.19730 1.51352 36.86316

2.24372 0.12912 4.82500 -3.43028 0.91906 1.81344 0.10436 3.89971 -2.77246 0.74281 2.10891 0.12137 4.53510 -3.22418 0.86384 2.13661 0.12296 4.59467 -3.26653 0.87518 2.16431 0.12455 4.65423 -3.30888 0.88653 2.19202 0.12615 4.71380 -3.35123 0.89788 2.21972 0.12774 4.77337 -3.39358 0.90922

35

Со став ительТ р оф имов В алер ий П ав лов ич Редакто р Т их омир ов аО .А .