6s F

c
ZVONIMIR        BOHTE
ANALIZA     ZAOKROŽITVENIH NAPAK     PRI     REŠEVANJU     PASOVNI   FI SI.STEMOV     LINEARNIH     ENAČB     PO GAUSSOVI     METODI
DISERTACIJA

m
LJUBLJANA, 1971

• !

1092 r/
3
^^
%*.&****>
Wilkinson (1961) je izdelal podrobno analizo za-okrožitvenih napak pri reševanju sistemov linearnih enačb po Gaussovi metodi za aritmetiko s premično vejico.
V tem delu sem obravnaval kot poseben primer pasovne sisteme linearnih enačb in dobil za Gaussovo metodo z delnim pivotiranjem izboljšane ocene za zaokrožitvene napake. Posebej sem obravnaval pivotno rast in dobil novo oceno za maksimalni pivot.
Ob tej priložnosti čutim prijetno dolžnost zahvaliti se svojemu učitelju, profesorju dr. I. Vidavu za vso matematično vzgojo, docentu dr. A. Suhadolcu/ ki je vedno z zanimanjem spremljal moje delo in dr. J. H. Wilkinsonu, ki me je s svojimi deli navdušil za numerično linearno algebro in posebej za analizo zaokrožitvenih napak. Prvoimenovana sta tudi skrbno prebrala rokopis in mi dala vrsto dragocenih nasvetov. Veliko zahvalo sem dolžan tudi študentki A. Pavličevi za trud pri tipkanju tega dela.
Z. B.
Lj ubij ana, j anuar 1971
- 3 -
KAZALO
I. UVOD                                                                                                     str.
1. Osnovne predpostavke in pomožne ocene ............       4
2. Gaussova metoda za reševanje sistemov linearnih e-načb .............................................       8
3. Analiza zaokrožitvenih napak pri Gaussovi metodi z delnim pivotiranj em ..............................     i 0
II. PASOVNE MATRIKE
4. Pasovni sistem linearnih enačb ...................     20
5. Struktura matrike PA .............................     22
6. Struktura matrik L in U ..........................     31
7. Analiza zaokrozitvenih napak .....................     33
3. Ocene norm nastopajočih matrik ...................     40
9. Končne ocene .....................................     55
10. Diagonalno dominantne pasovne matrike ............     57
11. Povzetek rezultatov ..............................     61
III. PIVOTNA RAST
12. Znane ocene ......................................     62
13. Pomožni izrek ....................................     66
14. Ocena za R pri pasovni matriki ...................     71
LITERATURA ..........................................     76
I. U V O D
1 - Osnovne predpostavke in pomožne ocene
Pri analizi zaokrožitvenih napak je potrebno upoštevati način izvajanja aritmetičnih operacij in navadno narediti še nekaj dodatnih predpostavk, ki omogočajo poenostavitev sicer kompliciranih ocen.
Vzemimo, da imamo opravka z računalnikom, ki računa s števili v b-narnem sistemu. Ta števila naj bodo zapisana v obliki s premično vejico (floating point) s t b-narnimi ciframi. Obseg dopustnih števil naj bo tako velik, da pri obravnavanih računih nikdar ne pride do prekoračitve tega obsega.
Množica Števil P, ki se dajo eksaktno upodobiti v računalniku, je definirana takole:
P = { fl(x) , fl(x) = ± m.-be }
kjer imenujemo m mantiso in e eksponent Števila fl{x) pri številski osnovi b. Pri tem naj veljajo naslednje omejitve;
(i)     b-1 < m < 1
Mantisa je vedno tako normalizirana, da je manjša od 1 in ni manjša od b
(ii)    -M  < e < M_
Eksponent je celo število, ki je po absolutni vrednosti sicer omejeno, a ta omejitev za analizo zaokrožitvenih napak ni bistvena.
{iii)   m = 0,d-d^...d  =
= d1b-1   +  d2b"2  +   ...   +  dtb-t
Za upodobitev mantise je na razpolago t b-narnih mest. Cifre d. so cela števila med 0 in b-1, le d  je najmanj 1. Izjema je število 0, ki ima mantiso 0. Za znak števila vzemimo, da je poskrbljeno posebej.
Množica P je torej končna množica racionalnih Števil, ki ležijo na dovolj velikem intervalu, in ki so med dvema zaporednima potencama osnove b razporejena ekvidistantno. Vsako
število iz množice P ima natanko t b-narnih cifer, od katerih prva ni nič, položaj vejice pa določa eksponent e. Zato pravimo, da so to števila s premično vejico. Števila s premično vejico se pri avtomatičnem računanju pretežno uporabljajo pri simboličnih jezikih (ALGOL, FORTRAN in pd.).
Vsa druga števila, ki ne spadajo v množico P, je treba aproksimirati s števili iz množice P. Vzemimo/ da pri tem upoštevamo pravilo pravega zaokroŽanja, to je, da k vsakemu realnemu številu x poiščemo kot aproksimacijo v množici P k x najbližje Število. Če označimo to število s f1 (x), potem velja (Bohte (1970))
fl(x) = x(l+L),                        |e| < |.b-t
če le lezi [xj na intervalu med absolutno najmanjšim (razen 0) in absolutno največjim številom iz množice P. Torej se dajo števila v tej obliki aproksimirati z majhno relativno napako. Število
a = ^.b"fc                                               (1.1)
bomo imenovali osnovna zaokrožitvena napaka.
Nadalje privzemimo, da je aritmetična enota računalnika tako zgrajena, da omogoča izvajanje osnovnih štirih a-ritmetičnih operacij s števili iz množice P tako, da je rezultat spet število iz te množice. Ker eksaktni rezultat take operacije v splošnem ni število iz množice P, pride pri tem do zaokrožitvene napake. Vzemimo, da dobimo vedno tak rezultat, kot bi ga dobili, če bi eksaktni rezultat zaokrožili na t mest.
Naj bosta x  in y dve Števili iz množice P in naj * pomeni enega od štirih aritmetičnih operatorjev +, -, •, /. Izračunani rezultat imenujmo fl{x*y). Predpostavljamo torej, da pri vseh dopustnih aritmetičnih operacijah velja zveza
fl{x*y) = (x*y) <l+e) ,  |e| <a                           (1.2)
To prav gotovo velja za vse računalnike, ki imajo akumulator z dvojno dolžino {Wilkinson (1963)).
Analiza zaokrožitvenih napak vodi često do bolj ali manj kompliciranih izrazov, ki vsebujejo osnovno zaokro-
- 6 -
žitveno napako a. 2a boljšo preglednost ocen se izplača te izraze poenostaviti, čeprav gre poenostavitev delno na račun rahlega poslabšanja ocene.
Za strogo upoštevanje členov drugega velikostnega reda bomo privzeli dve predpostavki, ki naj bosta v nadaljnjem vedno izpolnjeni:
(i)    a < 9.10"3                                                        (1.3)
Za osnovno zaokrožitveno napako a bomo vedno predpo-
stavili, da ni večja od 9*10  . To je zelo majhna omejitev,
_a saj je navadno pri avtomatičnem računanju a reda 10  ali
-5 vsaj 10  . Ta predpostavka je izpolnjena celo v primeru
-3 b = 10, t = 3/ ko je a po {1.1} enak 5-10  , to je takrat,
ko računamo s trimestnimi dekadičnimi števili s premično vejico in pravim zaokroŽanjem.
(iL)    na < 0*1                                                            (1.4)
Kjerkoli bo celo število n pomenilo dimenzijo računskega postopka, to je Število zaporednih operacij istega tipa, bomo predpostavili veljavnost omejitve (1.4). To tudi ni huda omejitev, kot se pokaže v tistih primerih, kjer bomo to
oceno izkoristili. Na primer, pri največjem dopustnem a =
-3 = 9*10  , bodo naše ocene veljavne pri vsakem n, ki je manj-
-5 ši od 12. Pri a reda 10  pa je največji dopustni n že reda
4
10 , kar zadošča za vse praktične potrebe.
Pri nadaljnjih analizah bomo uporabljali še naslednje
pomožne ocene, ki sledijo iz binomskega izreka in ocen (1.3)
in L1.4) (Bohte (1970)) :
(iii)     (1 - a)-1 < 1 +,l*01a                           (1.5)
(iv)      (1 + a)n  < 1 + l'06na                         {1.6)
(v)       (1 - a)"n < 1 + l*12na                         (1.7)
(vi)      (1 + a) (1 - a)~n < 1 + l*12(n+l)a          (1.8)
Kot zgled za uporabo enačbe (1.2) in omenjenih ocen si oglejmo analizo zaokrožitvonih napak pri izračunu ska-larnega produkta dveh vektorjev. Podobne izraze bomo pozneje večkrat srečali.
- 7 -
Naj bosta x in y dana vektorja:
K     =   Cx1,.../xn),    y  s (yl/...,yn)
in naj bo
s  = fl(xTy) = fl( L x y )
i=l
Računanje skalarnega produkta s  poteka takole:
Pi = fl(x±yi) ,   i=l,...,n                                         (1.9)
sl = »1
si+1 = fl(si + Pi+1) /   i=l,...,n-l                        (1.10)
Če upoštevamo zaokroŽitvene napake, moremo na osnovi zveze (1.2) enačbi (1.9) in (1.10) zapisati takole:
pi = (xiYi} {1 + ei) '   !Li'  = a
si+i = (si + Pi+i)C1 + n±î  *       [n±!    < a
Če te enačbe povežemo skupaj, dobimo rezultat
sn = xlYl(l + Cl) + -.. + xnyn(l + Çnî kjer je
1 + Çj = (1 + e1) (1 + r^) ... (l + nn_:)
k=l,2,...,n—1
Za števila 1 + Ç. veljajo očitno ocene
(1 - a)n < 1 + z1   <   (1 + a)n
(1 - a)n"k+1 < 1 + çk+1 < (1 + a)n-k+1 k=l,2, . . .,n-l
Če upoštevamo poenostavitev (1.6), dobimo za Števila  [ç. j naslednje ocene:
ç, I < 1*06 na                                                                   (1.11)
•1 i =
Uk+1l < 1*06 (n-k+l}a ,  k=l,...,n-l                     (1.12)
Rezultat analize zaokrožitvenih napak moremo v tem primeru izraziti takole:
Izračunani skalami produkt dveh vektorjev je enak eksaktnemu skalarnemu produktu vektorja x z nekoliko spremenjenim vektorjem y:
kjer je
T     T fl(x y) = x z
z±  = yi(l + çi) ,  i=l,... ,n
in veljajo za relativne spremembe v komponentah ocene (1.11) in (1.12) .
Relativne napake v izračunanem skalarnem produktu brez dodatnih predpostavk ni mogoče oceniti, saj je ta lahko poljubno velika.
2. Gaussova metoda za reševanje sistemov linearnih enačb
Na kratko si oglejmo Gaussovo metodo za reševanje sistemov linearnih enačb in sicer osnovno varianto in varianto z delnim pivotiranjem. Čeprav je metoda dobro znana, je le potrebno vsaj glede označb nekaj pojasnil.
Dani sistem linearnih enačb zapišemo v obliki
Ax = b                                                  . (2.1)
kjer je A dana nesingularna kvadratna matrika reda n, b dani vektor desnih strani, x pa iskani vektor.
Pri Gaussovi eliminacij ski metodi tvorimo postopoma ekvivalentne sisteme
ACr)x = b(r) ,  r=l,2,...,n                             (2.2)
kjer je A   = A in b   = b, tako, da je končna matrika A
zgornja trikotna matrika.
(r) Matrika Av   je že zgornja trikotna matrika v prvih
r vrsticah in v prvih r-1 stolpcih. V desnem spodnjem vogalu imamo še kvadratno matriko reda n-r+1. Na r-tem koraku eliminacije želimo eliminirati neznanko x  iz zadnjih n-r enačb, to je, doseči v r-tem stolpcu pod diagonalo same ničle. Matriko A     dobimo torej iz matrike A   tako, da
- 9 -
množimo r-to vrstico s primerno izbranim faktorjem m.  in jo odštejemo od i-te vrstice za i=r+l,...,n. Očitno je treba vzeti
mir = air)/arr) '   i=r+l,...,n       (2.3) in novi elementi so enaki
(r+l)    (r)       (r) aik   ¦ aik  - rairark  ' l'kwr+1.....n C2-4)
Pri tej eliminaciji se desne strani enačb transformiraju na
podoben način:
,{r+l)    (r)       (r)   4=av>J.i     „   fo tn
b^    - bi  - ^irbr   , i=r+l,...,n   (2.5)
Rešitev sistema x dobimo nato zelo enostavno iz zgornjega trikotnega sistema
Ux = y                                             (2.6)
kjer je U = Atn' in y = bfn' , po formulah
n x  = (y  -  I  u..x. )/u. . ,  i=n,n-l,...,1   (2.7) ¦ X     X  k=i+l  lk *   1X
Elemente zgornje trikotne matriko A   smo označili z
Uik = aik = 4*     •     kž i                         (2.8)
Če definiramo spodnjo trikotno matriko L takole:
i±i - 1 ,   i=l,...,n                                       (2 9j
i.. = m.. , i > k
ik   lk
potem se izkaže, da velja (gl. npr. Bohte (1970))
A = L-U ,   b = Ly                                             (2.10)
(r) če so le vsi a   različni od nič. Matriko A smo torej raz-rr
cepili na produkt spodnje in zgornje trikotne matrike.
(r) Število a^  imenujemo pivot na r-tem koraku eliminacije. Opisani računski postopek odpove, brž ko je kak pivot enak nič. Pri nesingularni matriki A se da deljenju z nič izogniti s pivotiranjem, to je s posebnim načinom izbire pivota na vsakem koraku eliminacije. Izkaže se tudi, da je pi-votiranje potrebno zaradi zaokrožitvenih napak, ki so sicer lahko poljubno velike.
- 10 -
Na kratko si oglejmo le delno pivotiranje. Pri tem načinu izbire pivotov si na vsakem koraku eliminacije izberemo za pivot absolutno največji element v prvem stolpcu preostale kvadratne matrike. Pri tem moramo po potrebi zamenjati dve enačbi v sistemu, to je zamenjati dve vrstici v preostali matriki in ustrezna elementa v vektorju desnih strani.
Naj velja na r-tem koraku eliminacije
|aCr)|= max |a.(r)|
Tedaj zamenjamo v sistemu (2.2) r-to in s-to enačbo ter izvedemo eliminacijo. Pri nesingularni matriki A so tako izbrani pivoti vedno različni od nič.
Pri delnem pivotiranju seveda ne veljata enačbi (2.10)/ pač pa velja (gl. npr. Bohte (1970))
PA = L*U ,  Ly = Pb
kjer je P primerna permutacijska matrika, ki je
P = In-1,(n-1)'*** Il,l' Če na r-tem koraku zamenjamo vrstici z indeksoma r in r'¦ (r' > r). Matrike I., so elementarne permutacijske matrike. Pri tem so vsi elementi spodnje trikotne matrike L absolutno omejeni z 1. Rešitev x dobimo kot prej iz zgornjega trikotnega sistema (2.6).
3. Analiza zaokroŽitvenih napak pri Gaussovi metodi z delnim pivotiranjem
Oglejmo si nekoliko podrobneje analizo zaokroŽitvenih napak pri Gaussovi metodi z delnim pivotiranjem v splošnem primeru, da bomo laze navezali ustrezno analizo za primer pasovnih matrik.
Wilkinson (1963) je dokazal, da je izračunana rešitev x sistema linearnih enačb (2.1) pri tej metodi enaka eksakt-ni rešitvi nekega perturbiranega sistema
(A + &A)x  =  h
- Il -
in podal oceno za normo perturbacijske matrike SA.
Analizirajmo najprej razcep matrike A na produkt dveh trikotnih matrik.
Teoretični formuli (2.3) in (2.4) se z upoštevanjem zaokrozitvenih napak prevedeta v formuli:
KK  - fl(a{r)/aCr)) = (afr)/a(r))(l + iL)      (3.1) ir      ir ' rr      ir ' rr       1
i=r+l,...,n
a(r+l) . ... , (r)     (rh
aik   - fl(aik  " mirark > =
= <«tk -miraik)(1 + L21)C1 + e3>      (3-2) i,k=r+l,...,n
kjer velja
Eij < a ,   1-1,2,3                                           (3.3)
Če upoštevamo definicijo matrik L in U, moremo enačbo (3.1) zapisati v obliki
0 = afr) - m. a(r) + e.(r) = ir    ir rr    ir
= a.(r) - l.   u  + efr}                                    (3.4)
ir    ir rr   ir
kjer je
ejri =  Llafr)                                                               (3.5)
ir    1 ir
Enačbo (3.2) pa zapišimo takole:
(r+1)   „(r)       (r) .  (r) a..    = a.. ' - m. a  ' + e.,  = ik      ik    ir rk    lk
= aff} - t.   u .  + e!^                                    (3.6)
ik    ir rk    ik
kjer je
BW . j2.aCr+l) _ t                                           (3.7)
ik   i+e3 x^      ir r^ 2
(r) Oglejmo si sedaj, kako se spreminja element a.. , ko
r teče od 1 do n-1. Ločiti moramo dva primera.
(i)     k > i   (zgornji trikotnik)
Element v zgornjem trikotniku se spreminja po formuli (3.6) , dokler r ne doseže vrednosti i-1, nakar ostane pri vseh nadaljnjih korakih nespremenjen. Torej velja enačba (3.6) za r = l,2,...,i-l. Če vse te enačbe seštejemo in upoštevamo, da
-12-
je A = A   in a:, ' = u., , dobimo
ali
kjer je
i-1
aik - uik + E/irurk - eik r=l
aik + eik » Virurk                                               C3-8)
r=l
(ii)  k < i    (spodnji trikotnik)
Element v spodnjem trikotniku se tudi spreminja po formuli (3.6) za r = l,2,...,k-l, nakar ga uporabimo v formuli (3.4), potem pa ga zamenjamo s številom 0. Pri nadaljnjih korakih se ne spreminja več.
Torej smemo podobno kot prej sešteti enačbe (3.6) za
r = l,...,k-l in še enačbo (3.4) za r = k. Tako dobimo
¦j.
aik  +  eik  = J/irurk                                         C3-10)
kjer  je
•i*->.X't*                                          (3-nl
Enačbi (3.8) in (3.10) moremo zapisati v matrični obliki
A + E = L-U                                                                   (3.12)
kjer so elementi matrike E definirani s formulama (3.9) in (3.11) .
Izračunani trikotni matriki L in U sta torej taki, da predstavljata eksaktni razcep neke perturbirane matrike A + E.
Če hočemo dobiti ocene za elemente matrike E, moramo
narediti nekaj predpostavk, kajti potrebujemo ocene za šte-
,,                      (r)
vila m.  in a., .
ir    ik
Najprej je očitno, da je m.  lahko poljubno veliko število, če izvajamo eliminacijo brez pivotiranja, saj je pivot na kakem koraku lahko enak nič. Tedaj je tudi matrika E lahko poljubno velika.
Zato vzemimo, da izvajamo eliminacijo z delnim pivoti-ranjem in zaradi enostavnejšega zapisa vzemimo, da ima prvot-
- 13 -
na matrika A že  tako permutirane vrstice, da velja pri naravnem vrstnem redu eliminacij ocena
|*lrl 5 1                                                              (3.13)
(r) Glede velikosti elementov a.,  pa zaenkrat predpostavimo le to, da so omejeni in naj velja
g =  max [a|f* j                                                  (3.14)
i,k,r
O ocenah za število g bomo govorili v zadnjem poglavju.
Pri teh dveh predpostavkah moremo dobiti za elemente
perturbacijske matrike dokaj ugodne ocene.
(r) Najprej ocenimo števila e., . Iz (3.3) in (3.7) sledi
|t(j)| <  a  |a(rH),   |   j )a(r)|a 1 ik ' = 1-a  lk   '   'ir1 ' rk '
Če upoštevamo še predpostavki (3.13) in (3.14), dobimo od tod 1*^1 š (a/^ - a) + a)g ,    r <  i,k       (3.15) Iz (3.5) pa sledi
Oceno (3.15) lahko poenostavimo, če upoštevamo oceni (1.3) in (1.5) . Tedaj je
[ef? I  < 2*01 ag                                          (3.16)
ki očitno velja tudi v primeru k = r.
Končno dobimo za elemente matrike E iz (3.9) in (3.11) oceni :
|eik j  < 2'01(i-l)ga ,  k > i
jeik ]  < 2*01 kga   ,  k < i
Brez posebnih težav dobimo od tod naslednje ocene za norme matrike E:
1 1 = - "*  3" 2
E \\m  <   2*01 ga | (n-1) (n+2)
E 1|, < 2-01 ga %  n(n-l)
H E [| B < 2*01 gat |n2 (n2-l) ) 1/2
Tu pomenijo
- 14 -
[| A [L   = max     L   |a..  [ 1        k     i=l     aK
n Il A ||m  = max    E   |a     | i    k=l     1R 0         n       n              _
[| A ll| -  L  E |a  ]2 L  1*1 k=l  1K
Naslednji del računa je transformacija desnih strani ali rešitev spodnjega trikotnega sistema
Ly = b
Formule za rešitev tega sistema so: i-1
yi = bi "  2 nikyk '   i=1''"*,n                                      (3.17)
k=l
(r ) Števila b   v formulah (2.5) so namreč ravno delne vsote v
enačbi (3.17) in b^]   = v.<
V resnici seveda izračunamo število
i-1 y. = fl^ - l   mikyk)                                                           (3.18)
Podobno kot pri skalarnem produktu, ki smo ga obravnavali v 1. razdelku, dobimo z upoštevanjem zaokrožitvenih napak zvezo
Vi = V1 + tl) - V^ikykU + çk)                         (3.19)
kjer je
i + ç± = (i + n^i d + n2) -•• d + ni„1) i + çk = (i + ek)(i + nk> ... (i + ni„1)
in veljajo ocene
|ek|  < a ,   |nj I  < a                                    (3.20)
Faktorji (1 + z, ) nastanejo pri množenju, faktorji (1 +n.) pa pri seštevanju.
Enačbo (3,19) zapišimo rajši v obliki
bi - *i» + 5i> + J, Vk(1 + V -¦,ViA(1 + V
x=l
- 15 -
kjer velja
i + q - a + Ci)"1 =
= U + h^-)"*XÓ + n2)_1--.(i + ni-i)"1  (3.21)
i + çk » a + ck) d + q)-1 -
= (1 + ek) (i + n1)~1 ... d + ^k-i^"1
Izračunani vektor y je torej eksaktna rešitev sistema
(L + <SL)y = b                                               (3.22)
kjer je perturbacijska matrika & L tudi spodnja trikotna matrika in velja
"ik = »iA -   *¦ i k                        <3-231
Za števila L. dobimo iz (3.21) in C3.20) ocene:
(1 + a)-(i-:L> < 1 + |  < (1 - a)"11"15 (1 - a) (1 + a)~{k~l)   <   1 +  Çk < (1 + a) (1 - a)"(k"1J
ki jih moremo poenostaviti s pomočjo ocen (1.7) in (1.8) v ocene
1^1 < l*12(i-l)a
|Ck! < 1*12 ka Ker je |L.. 1 <   1 / dobimo iz (3.23) ocene:
j(Silik( < ri2 ka ,    i > k Od tod dobimo hitro ocene za norme matrike ÓL: IISLJ^ < 1-12 a J(n-l) (n+3)
U SI. | k < 1*12 a | (Drl) (n+2)
!|6L|!E < 1*12 a(^ n (n-1) (n2 + 5n - 2) ) 1/2      (3.24)
Zadnji del reševanja prvotnega sistema je reševanje zgornjega trikotnega sistema
- 16 -
Ux = y
Formule (2.7) nara pri upoštevanju zaokrožitvenih napak dajo za komponente rešitve naslednje vrednosti:
"i-«<uri - kJ+1 »iA'/»iii *
" (Vid+q) - , E    Vk^^1111^^»!!    (3-25>
k=i+l
kjer  je
i + ç.  =  (i + ni+1)(i +. ni+2)   ...   d + nn)
i + çk =  U + eki d + nk)   ...   U + nn)
Faktorji {1 + n.) nastanejo pri seštevanju, faktorji (1 + L.) pa pri množenju ali deljenju. Pri tem veljajo ocene
lEjl ž a '   hjl %  a
Enačbo (3.25) moremo zapisati v obliki
likV
1  k=i
kjer je
1 + çk = (l+çk) (l+çi)~1 =
= (l+ek) (H-ni+1)_1 ... (1+nk_1)"1
Izračunana rešitev x je torej eksaktna rešitev sistema
(U + 6U)x = y                                                   (3.26)
kjer je perturbacij ska matrika SU tudi zgornja trikotna matrika in velja
5uik = uiA '   k ž i
Števila u., , ki so enaka a.. , moremo oceniti s številom g (3.14) :
Kkä s*
Za Števila Ç. pa veljajo ocene
(l+a)-(n-i+l) < 1 + q < (i-a)-(n-i+1)
(1-a) (l+a)"Ck"i_1) < 1 + Ç. < (1+a) (1-a)~(k~i_1)
- 17 -
Te ocene moremo poenostaviti z uporabo pomožnih ocen (1.7) in (1.8) takole:
\tt\   <   1*12 a(n-i+l) |Çkl < 1*12 a(k-i)
Od tod direktno sledijo ocene za elemente matrike 5U:
jžui;LJ < 1*12 (n-i+l)ga
|6uik| < l'12(k-i)ga , k > i
Brez težav dobimo od tod ocene za norme matrike SU:
H <SU [L < 1*12 ga -|(n2 - n + 2)
Il SD !]„ < 1*12 ga | a (,n+l)
|| SU |!E <  1*12 ga(îin(n+l)2(n+2));L/2     (3.27)
Sedaj moremo združiti analize posameznih korakov v končni rezultat.
Iz (3.12), (3.22) in (3.26) sledi, da je izračunana rešitev x eksaktna rešitev sistema
(L + 6L) (U + 5U)X = b ali sistema
(A  +  6A)x  =  b kjer  je perturbacijska matrika SA enaka
<5A  =  E  +  SL*U   +  L-SU  +  SL-SU Za katerokoli  normo velja potem ocena
|1SA||<   IIE||+||ĆL||   HUH  +l|ty   1I6U||+ ]|6l!|   |] 6U ||
Ocene   za || EJ]     ,  |j SLI]       in || SUJI       pri  p  =   1,°° ,E  2c  poznamo. Norme matrik  L   in  U  pa  ni   težko  oceniti   s  predpostavkama L3.13)    in    (3.14):
- 18 -
II L 51 < n !!ML<n H L I!E < ( |n(n+l))1/2
II» Ha. 5 gn
Il " IL < gn
||0 |!E m  g( |n(n+l))1/2
S elementarnim računom, primerno poenostavitvijo in upoštevanjem predpostavke (1.4) dobimo od tod naslednje ocene:
SI Sa(^ < 0'86(n3 + 2n2)ga
|| 5aL < l*16(n3 + 2n2)ga
|[ 5A|E < 0'46{n3 + 5n2)ga
Vse tri ocene imajo skupno obliko
|| 5A|^ < f (n)ga , p = 1,»,E                                     (3.29)
kjer je f(n) polinom tretje stopnje v n z vodilnim koeficientom reda 1. Ta koeficient je najmanjši pri p = E. Z bolj natančnim ocenjevanjem elementov ]6a.. ) bi lahko ta koeficient rahlo izboljšali. Pri p = E pride ta koeficient spet najmanjši in sicer 0*36, kar pa ne da bistveno boljše ocene.
Z oceno (3.28) primerljive ocene dobimo v Wilkinson (1963), Isaacson and Keller (1966) in Forsythe and Moler (1967).
Omeniti velja, da se da koeficient f (n) v oceni (3.29) v splošnem bistveno izboljšati le, če računamo skalarne produkte v vseh formulah, kjer nastopajo, z akumulacijo v dvojni
dolžini. Wilkinson (1965) je pokazal, da je tedaj f (n) pri-
P bližno enak n. Na žalost pa je tako računanje lahko izvedljivo le pri majhnem številu računalnikov.
Oceno (3.29) moremo uporabiti za apriorno oceno napake v rešitvi po formuli (Wilkinson (1965))
-   19   -
il Hl IM!
iJA"1!!     |[6a!1 i - IIa"1!!   ||sa||
kjer je na levi relativna sprememba v rešitvi sistema, če matriko spremenimo za 6A. Ta ocena velja, ce je
-1
!IA i! !!fiA|| < i
-ii
Uporabna je seveda le, če znamo oceniti  |JA j] , kar pa navadno ne gre brez dodatnega računanja.
Splošno oceno (3.29) moremo v nekaterih posebnih primerih matrik izboljšati.





¦
¦

- 20 -
II. PASOVNE  MATRIKE
V praksi pogosto nastopajo matrike, ki imajo od nič različne elemente zbrane vzdolž glavne diagonale in ob njej, vsi drugi elementi pa so enaki nič. S takimi matrikami imamo največkrat opraviti pri numeričnem reševanju diferencialnih enačb.
V tem poglavju bomo izdelali podrobno analizo zaokro-žitvenih napak pri reševanju pasovnega sistema linearnih enačb po Gaussovi metodi z delnim pivotiranjem. Izkaže se, da se da splošna ocena (3.29) v tem posebnem primeru bistveno izboljšati.
4. Pasovni sistem linearnih enačb
Matriko A imenujemo pasovno matriko s širino pasu 2p+l, če velja
aik = 0 ,  |i-kj > p                                     (4.1)
in če je
n > 2p+l                                                             (4.2)
Tako matriko imenujemo včasih tudi (2p+l)-diagonalna matrika. Za elemente a., pri |i-kj <  p bomo predpostavljali, da so v splošnem od nič različni. Če je pri dani pasovni matriki kak tak element enak nič, tega v naši analizi ne bomo upoštevali.
Omejitev (4.2) ni bistvena, saj v praksi obravnavamo matriko A kot pasovno le, če je n >> 2p+l. Če upoštevamo posebno strukturo pasovnih matrik, se največji red, ki ga dopušča spomin računalnika pri polni matriki, znatno poveča.
Naj bo sedaj A nesingularna pasovna matrika,   ki ustreza pogojema (4.1) in (4.2).
Pri reševanju pasovnega sistema enačb
Ax = b                                                                 (4.3)
z Gaussovo metodo bi kot v splošnem primeru brez kakršnegakoli
- 21 -
pivotiranja lahko dobili rešitev s poljubno veliko napako. Delno pivotiranje se izkaze za zelo primerno. Ne samo, da moremo pri takem reševanju pasovnega sistema enačb skoraj v vsej splosnosti upoštevati pasovno strukturo matrike in s tem varčevati s spominom v računalniku, ampak moremo s podrobno analizo napak tudi pokazati/ da je ta strategija s stališča . natančnosti računanja popolnoma zadovoljiva.
Pri delnem pivotiranju zamenjujemo med eliminacijami vrstice matrike s ciljem, da dobimo pri tekoči matriki na ustreznem mostu na diagonali absolutno največji element od vseh, ki so pod njim. Zaradi tega pridejo na r-tem koraku eliminacije za zamenjavo z r-to vrstico v poštev le vrstice r+1, r+2, ... , r+p, saj so v vseh naslednjih vrsticah v r-tem stolpcu same ničle.
Vzemimo, da smo na r-tera koraku eliminacije zamenjali r-to vrstico z r'-to. Tej zamenjavi ustreza elementarna permutaci j ska matrika I   ,.
Če označimo s P permutacijsko matriko
P = Xn-1, (n-1) ' **• Xl,V                                {4"4)
potem ima matrika PA, kot smo omenili v prejšnjem poglavju, lastnost, da nam da pri Gaussovi eliminaciji brez pivotiranja razcep
PA = L-U
pri čemer so vsi elementi spodnje trikotne matrike L absolutno ornej eni z 1.
V (4.4) velja pogoj
r < r' < min (r+p, n)                                             (4.5)
Matrika PA, ki ima iste vrstice kot matrika A, le da so primerno permutirane med seboj, v splošnem ni več (2p+l)-diagonalna, pač pa ima v svoj i strukturi vseeno posebnosti, ki izvirajo iz pasovne strukture matrike A in ki se dajo izkoristiti pri podrobni analizi napak.
Dokazali bomo, da je izračunana rešitev x sistema (4.3) eksaktna rešitev sistema
(PA + 5A)x = Pb                                                     (4.6)
- 22 -
in podali ocene za tri norme matrike SA.
Iz (4.6) in dejstva, da je P ortogonalna matrika, sledi, da je x  tudi eksaktna rešitev sistema
T
(A + P 6A)x = b
pri čemer očitno velja
j[PT5A|[p  =  ||«A|Je   ,      p   =   1,-,E saj   je  P  permutacij ska matrika.
5. Struktura matrike PA
Najprej si podrobno oglejmo strukturo matrike PA, kajti analiza napak je enostavnejša, če si mislimo, da je prvotna matrika tako permutirana, da v toku eliminacij ni potrebno narediti nobene zamenjave vrstic.
Naj bo sedaj A poljubna (2p+l)-diagonalna matrika, P pa poljubna permutacijska matrika oblike (4.4), pri čemer veljajo pogoji (4.5). Vseh možnih takih matrik je p!(p+l)  p.
Če je P = I, ali, kar je isto, če je r' = r, r=l,.,n-], potem je PA = A, torej je PA (2p+l)-diagonalna matrika. Primer matrike, ki ima to lastnost, je diagonalno dominantna pasovna matrika. Ta primer bomo obravnavali posebej.
Pri katerikoli drugi dopustni permutaciji P pride vsaj en element, ki leži znotraj (2p+l)-diagonalnega pasu, izven njega in zato matrika PA ni več (2p+l)-diagonalna. Zanima nas predvsem, kako ležijo ničle v matriki PA, če smatramo vse elemente znotraj pasu za različne od nič..
Matrika P (4.4), ki je produkt elementarnih permutacij-
skih matrik I   , , je permutacijska matrika. Ima natanko n r, r
enoj k, vsi drugi elementi pa so enaki nič. Te enojke ležijo ta ko, da je v vsaki vrstici in v vsakem stolpcu natanko ena e-nojka. Položaj enoj k fiksirajmo z zapisom. IJaj bo v i-1i vrsti ci cnojka v s.-tem stolpcu:
piSi= 1 '  Pik * ° '  k ** si
- 23 -
Tedaj matriko P na kratko označimo s P        . Števila slf.
S j t•••tS^
..,sn so neka permutacij a' Števil 1,2,...,n.
Matrika PA ima potemtakem permutirane vse vrstice matrike A in sicer je i-ta vrstica matrike PA enaka s.-ti vrstici matrike A.
Zanima nas pa tudi obratna zveza. Na katero mesto v matriki PA pride i-ta vrstica matrike A ?
Očitno je zaradi (4.4)
-1                         -1                         T
P  = P                      = P       i
Si t » . • /Sjj      Si f . •• f Sjj
Transponirana matrika permutacijske matrike je tudi permuta-cijska matrika in naj velja
P       T = P.                                                              (5.1)
To pa pomeni, da velja
A = P.      . (PA)                                                      (5.2)
Torej i-ta vrstica matrike A preide v t,-to vrstico matrike
i
PA, kjer so števila t. definirana s (5.1). .
Lahko se je prepričati bodisi iz zveze (5.1), bodisi iz (5.2), da velja
t  = i ,  s  = i ,   i=l,2,...,n      (5.3)
si                      ti
Sedaj pa upoštevajmo pogoje (4.5) in jih prenesimo na števila s.in t.. Matriko P zapišimo v obliki
Si , — ,sn   n-1,(n-1)       1,1'
To pomeni, da dobimo matriko P tako, da v enotni matriki I po vrsti izvršujemo zamenjave vrstic (1,1'), {2,2'), ... , (n-1,
(n-1)'). Poglejmo, kaj se utegne zgoditi pri teh zamenjavah
(r,r'), r=l,...,n-l z s.-to vrstico matrike I.
Zaradi pogoja r' <  r+p ostane s.-ta vrstica na svojem mestu, dokler je r < s.-p. Od r = s.-p do r = s.-l se utegne zgoditi zamenjava (r,s.), tedaj pride s.-ta vrstica matrike I na r-to mesto in tam tudi.ostane do konca vseh zamenjav, saj vedno velja r' > r. V tem primeru velja i = r in i > s „.-p ali
si < i + p                                                                        (5.4)
- 24 -
Če se taka zamenjava ne zgodi, je nadalje možno, da je pri r = s. ustrezni r' = r, torej, da s.-ta vrstica ostane na svojem mestu. Tedaj je i = s. in ocena (5.4) tudi velja. Če pa se pri r = s. zgodi zamenjava (r,r'), r' > s., se v tem primeru s.-ta vrstica pomakne navzdol in velja kvečjemu i > s. in ocena (5.4) tudi velja.
Ugotovili smo torej, da pogoj (4.5) pomeni, da je
s  < i + p ,   i=l,...,n                                   (5.5)
Analogen pogoj za števila t. pa dobimo, če vstavimo namesto i v (5.5) t. in upoštevamo (5.3):
t. > i - p ,   i=l,...,n                                   (5.6)
Ta rezultat moremo z besedami tolmačiti takole: Nobena vrstica matrike A se v PA ne pomakne za več kot p mest navzgor.
Sedaj, ko dobro poznamo permutacijsko matriko P, lahko tudi podrobneje opišemo strukturo matrike PA, kjer je A (2p+l)-diagonalna matrika. Dogovorili smo se že, da bomo pod ničlami matrike A razumeli samo elemente izven pasu.
Dokažimo najprej nekaj pomožnih izrekov, ki jih bomo uporabili pri nadaljnji obravnavi.
Vse  ničle  matrike  Aj ki   ležijo  v  spodnjem  trikotniku (i > k)j ostanejo  v  spodnjem   trikotniku matrike  PA.   (TI)
Dokaz.   Matrika A ima v spodnjem trikotniku ničle na mestih
a,, = 0 ,  i=p+2,...,n ,  k=l,...,i-p-l
V i-ti vrstici je skrajna desna ničla v (i-p-l)-tem stolpcu. Ker je i-ta vrstica matrike A enaka t.-ti vrstici matrike PA, je ta skrajna desna ničla še vedno v spodnjem trikotniku, saj zaradi (5.6) velja
i - p - 1 < t. -1
v             =i
kar pomeni, da ostane levo od diagonale.
V spodnjem trikotniku matrike PA se torej ohrani vseh ^(n-p-1)(n-p) ničel iz spodnjega trikotnika matrike A.
Število teh ničel v vsakem stolpcu je enako kot pri matriki A (saj so le vrstice permutirane med seboj), v k-tem stolpcu jih je torej natanko
- 25 -
max ( O, n-p-k)
Izkaže se, da so za analizo napak bistvene le tiste ničle v spodnjem trikotniku matrike PA, ki izvirajo iz ničel v spodnjem trikotniku matrike A. Te ničle so skupaj na začetku vsake vrstice.
Definirajmo Števila u., ki naj povedo, koliko zaporednih ničel, šteto od prvega stolpca dalje, je v i-ti vrstici matrike PA. Naj torej velja za vsak i
(PA)ik = 0 ,  k=l,...,ui
(PA) ,. $  0 ,  k=u.+l
ik    '    i
Ker preide v i-to vrstico matrike PA s.-ta vrstica matrike A, očitno velja
u. = max (0, s.-p-l) ,  i=l,...,n                             (5.7)
Števila u. imajo lastnost, da je med njimi p+1 enakih nič, vsa druga pa so neka permutacija števil 1,2,...,n-p-l. Ker je zaradi (5.5)
s, - p < i
je od tod in iz (5.7) razvidno, da je
u. < i - 1 ,  i=l, . . . ,n
kar je le druga oblika trditve (TI).
Ničle v matriki PA, ki izvirajo iz zgornjega trikotnika matrike A, se lahko bolj premešajo z elementi, ki so različni od nič. Nekatere od teh ničel morejo preiti tudi v spodnji trikotnik matrike PA, a so desno od elementov, ki niso enaki nič, zato ne vplivajo na definicijo števil u., ki štejejo le začetne zaporedne ničle v vrstici.
Ničle iz zgornjega trikotnika matrike A se pri vsaki permutacij i vrstic razdelijo v matriki PA v dve skupini. Prva skupina se ohrani ves čas v toku Gaussove eliminacije in te moremo s pridom upoštevati pri analizi napak. Druga skupina pa se v toku eliminacij sčasoma izgubi in teh pri analizi ne bomo upoštevali. Z upoštevanjem teh ničel bi se analiza zao-krožitvenih napak nepotrebno skomplicirala. Za posamezne eie-
- 26 -
mente matrike <5A bi sicer lahko dobili rahlo ugodnejšo oceno, norme te matrike pa ne bi mogli na preprost način bolje oceniti
Prvo skupino ničel opišimo takole Naj bo v, število zaporednih ničel matrike PA v k-tem stolpcu, šteto od prve vrstice dalje. Torej, za vsak k naj bo
(PA)ik = 0 ,   i=l,...,vk
<PA)ik t  0 ,   i=vk+l
Kaj lahko povemo o številih vk ?
Pri  poljubni  dopustni permutaciji  vrstic matrike     A velja  ocena                                                                           (?2)
v, > max(0, k-2p-l)                                              (5.8)
Dokaz.   Naj bo i = t., to je, naj j-ta vrstica matrike A postane i-ta vrstica matrike PA.
Če je i = j, j = 1, ... , n, potem je PA = A in je očitno
vk = max(0, k-p-1) ,   k=l,...,n        (5.9)
saj je v k-tem stolpcu matrike A pri k=p+i,...,n natanko k-p-1 začetnih zaporednih ničel. Ker pa je pri poljubni dopustni permutaciji vrstic zaradi (5.6) i > j-p , j=l,...,n, se nobena vrstica matrike A ne pomakne za več kot p mest navzgor. To pa pomeni, da se število začetnih zaporednih ničel matrike v nobenem stolpcu ne more zmanjšati od prvotnih (5.9) za več kot p. Torej velja ocena (5.8) za poljubno dopustno permuta-cijo.
Mimogrede lahko omenimo, da tvorijo števila vk nepada-joče zaporedje:
VW1 > v.                                                                   (5.10)
k+1 =  k
To je posledica dejstva, da v nobeni vrstici od nič različni elementi niso prepleteni z ničlami. Ničle, ki so levo od elementov, ki so različni od nič, pa po (TI) ostanejo v spodnjem trikotniku.
2 drugimi besedami lahko trditev (T2) formuliramo takole: Od prvotnih =(n-p-l)(n-p) ničel v zgornjem trikotniku ma~ trike A, se v matriki PA ohrani najmanj x{n-2p-l)(n-2p) ničel,
- 27 -
ki so razporejene tako, da so nad vsako in desno od vsake same ničle.
Te ničle, ki so opisane s števili v., torej štete po stolpcih, moremo opisati tudi drugače.
Definirajmo Števila
z. = k - i ,  i=l,...,n
kjer je k najmanjši indeks, za katerega velja, da so vsi v., j > k najmanj enaki i. Torej
v, > i ,   j >  k
vk-l * i Z drugimi besedami: Elementi matrike PA v i-ti vrstici so pri-čenši z (i+z.)-tim elementom vsi enaki nič:
(PA)ik = 0 ,   k=i+zi,...,n
Dodatno definirajmo
z. = n - i + 1
i
če je (PA)in ?  0.
Pri tem je lahko (PA)., = 0 tudi pri k < i+z ,., toda nad temi ničlami so od 'nič različni elementi, ker je pri takem k v. < i. Torej so s števili z. popisane natanko ište ničle kot s števili v. .
Pri P = I imamo očitno
z. = min{p+l, n-i+1)
in ker se pri nobeni dopustni permutacij i nobena vrstica matrike A ne pomakne za več kot p mest navzgor, se tudi nobeno število z. ne more povečati za več kot p. Torej velja ocena
z. < 2p + 1 ,   i=l,...,n
Ničle druge skupine v matriki PA, ki izvirajo iz zgornjega trikotnika matrike A, so torej take ničle, nad katerimi je vsaj po en od nič različen element, to je tak element, ; ki je bil v matriki A znotraj pasu.
Ničle  druge  skupine  se   v   toku  eliminacij  izgubi jo.  (T3) Dokaz.   Naj bo prva ničla iz druge skupine v i-ti vrstici na k-tem mestu matrike PA. Tedaj je nad njo vsaj en od nič
- 28 -
različen element in naj bo (j,k)-ti tisti izmed njih, ki ima najmanjši prvi indeks. To pomeni, da je
vk=j-l,   j<i                                           (5.11)
Naj bo B = PA, tedaj je po predpostavki
b., = 0 ,  b.. Î  0 ik        jk
brk = ° '  r=1'""''^-1
(5.12)
Dokazali bomo, da se na j-tem koraku eliminacije, ko eliminirano j-to neznanko iz i-te enačbe, ničla b., pokvari, to je, postane od nič različno število, če ne upoštevamo e-ventualnih ničel iz notranjosti pasu ali ničel, ki nastanejo slučajno med računom na mestih, kjer so bili v začetku ali pozneje od nič različni elementi.
Iz formul (2.3) in (2.4) dobimo
b(^ b<j+l) = b(j> _ Vi_ b(j)
Dik     bik   b(j) Djk
Število b.L     se ohrani kot ničla na vseh prejšnjih korakih eliminacije zaradi (5.12), toda b.r    je v splošnem razli-
cen od nič, ker je različen od nič bit .* ki se tudi ohrani
^      (i) na vseh prejšnjih korakih, pa tudi   b.-:  je v splošnem od
* j nič različen element. Kajti, če je b., prva ničla iz druge
skupine v i-ti vrstici, potem je levo od te ničle min(2p+l,
k-1) od nič različnih elementov in zato je ustrezni
u. = max{0, k-2p-2) < v, = j - 1        (5.13)
1                                               —   .K
pri čemer smo upoštevali L5.8) in (5.11). Torej b.. ne more
¦*¦ J biti ničla iz spodnjega trikotnika matrike A in je zato od
H )
nič različen element. Število h:J.     torej lahko postane nič
i:
samo slučajno.
Z analognim sklepanjem ugotovimo, da se tudi vse nadaljnje ničle druge skupine v i-ti vrstici izgubijo na poznejših korakih, saj velja (5.10). Le v (5.13) namesto prvega enačaja velja znak <.
S tem je trditev (T3) dokazana.
Oglejmo si sedaj nekaj primerov.
- 29 -
(i) Če je r' = r, r=l,...,n , je P = I in matrika PA = A, torej (2p+l)-diagonalna matrika. Pri n = 11, p = 3 ima naslednjo obliko:
A  =
*	*	*	ft	0	0	0	0	0	0	0
*	¦k	*	ft	*	0	0	0	0	0	0
A	¦k	ft	A	¦A-	ft	0	0	0	0	0
*	*	E	É	W	*	É	Ô	0	0	0
0	*	ft	ft	*	k	ft	*	0	0	0
0	0	*	ft	*	*	*	ft	*	0	0
0	0	0	*	ft	*	*	*	ft	*	0
0	n	0	0	*	A	II	¦k	ft	*	*
0	0	0	C	0	¦k	*	-k	ft	ft	ft
0	0	0	0	0	0	*	k	*	*	*
0	0	0	0	0	0	0	*	*	*	*
=  A,
Tu smo z znakom * označili v splošnem od nič različen element, V tem primeru veljajo naslednje enačbe:
u = max (0, r-p-1)
v = max(0, r-p-l) , r=l,.
z  = min(p+l, n-r+1)
/n
(5.14)
(ii) Vzemimo sedaj primer z n = 11, p = 3 in naslednjimi vrednostmi:
u
v
1	1	1	1	0	0	4
2	5	5	5	1	0	7
3	4	4	7	0	0	6
4	6	6	3	2	0	6
5	5	2	2	0	1	5
6	9	9	4	5	1	6
7	9	3	8	0	1	5
8	9	7	10	3	1	4
9	10	10	6	e	3	3
10	10	8	9	4	5	2
11	11	11	11	7	5	1
- 30 -
Matrika PA ima sedaj naslednjo obliko:
*	*	*	*	0	0	0	0	0	0	0
0	*	*	*	*	*	ft	k	0	0	0
•	*	*	*	*	*	*	0	0	0	0
0	0	-k	*	*	A	k	*	ft	0	0
t;	*	¦k	*	*	0	0	0	0	0	0
0	0	0	0	0	-k	k	*	k	*	*
*	*	*	*	*	-k	0	0	0	0	0
0	0	0	*	¦k	*	*	¦k	X	*	0
C	0	0	0	0	0	*	X	*	*	¦k
0	0	0	0	*	*	A	•k	*	X	*
0	0	0	0	0	0	0	*	*	*	*
V spodnjem trikotniku so vse ničle iz spodnjega trikotnika matrike A in sicer so tako razporejene, da ležijo skupaj, pricenŠi s prvim stolpcem. Ničle iz zgornjega trikotnika matrike A pa se razdelijo v dve skupini. Prvo smo tudi označili z ničlami in jih opisujejo števila v  ali z . Tudi te ničle ležijo skupaj na začetku vsakega stolpca in na koncu vsake vrstice. Drugo skupino, ki se v toku računa izgubi, pa smo označili s prečrtano ničlo.
(iii) Oglejmo si še skrajni primer. Naj se v toku eliminacij izvršijo naslednje zamenjave (r,r'), r=l,...,n:
r' = r + p ,
Pri tem se izkaže, da veljajo naslednje formule:
r - 1 ,  r=l,...,n-p
0     ,  r=n-p+l,...,n
(5.15) max(0, r-2p-l) , r=l,...,n
min(2p+l/ n-r+1),  r=l,...,n 3 imamo naslednje vrednosti:

= A,
če je  r+p < n če je r+p > n
u =
r
ur *
v =
r
2r =
V primeru n = 11, p =
- 30 -
t.
u
1	4	4	10	0	0'	7
2	5	5	11	1	0	7
3	6	6	9	2	0	7
4	7	7	1	3	C	7
5	3	8	2	4	0	7
6	9	9	3	5	0	6
7	10	IO	4	6	0	5
3	11	11	5	7	1	4
9	9	' 3	6	C	2	3
10	IO	1	7	0	3	2
11	11	2	S	0	4	1
Matrika PA ima torej naslednjo obliko;
PA =
*	*	*	*	*	*	*	0	0	0	0
0	*	X	*	*	*	a	*	C	0	0
0	0	*	*	*	*	¦k	*	*	0	0
0	0	0	a	*	X	*	X	*	*	0
0	0	0	0	*	*	¦k	*	*	*	X
0	0	0	0	0	X	x	*	X	*	*
0	0	0	0	0	0	É	*	k	*	*
0	0	0	0	0	0	0	*	*	*	*
X	*	*	X	*	*	0	0	0	0	0
*	*	*	*	0	0	0	0	0	0	0
*	*	*	*	*	0	0	0	0	0	0
=  A.
(5.16)
V tem primeru imamo najmanj ničel iz prve skupine v zgornjem trikotniku in največ iz druge skupine.
Preden nadaljujemo z analizo reševanja pasovnega sistema enačb, strnimo dosedanje ugotovitve.
Naj bo A poljubna matrika, ki more nastati iz nesingu-larne (2p+l)-diagonalne matrike z dopustnimi permutacijami vrstic (4.4) pri pogoju (4.5) . Položaj ničel v matriki A, ki jih bomo upoštevali pri analizi, moremo opisati takole:
(i) spodnji trikotnik (i >   k)
a., = 0, k=l,...,u. , i=l,...,n
(ii) zgornji trikotnik (i <  k)
aik = °' i=1" ' ¦ 'vk ' k=1/
,ti
- 31 -
ali
a., = 0, k=i+z.,...,n , i=l,...,n
Pri tem veljajo naslednje enačbe ali ocene:
(i)  u. = max{0, s.-p-l) ,  i=l,...,n                     (5.17)
kjer so s. , i=l,...,n neka permutacija" števil l,...,n , pri čemer velja
m
si < i + p                                                                 (5.18)
ui < i - 1                                                                  (5.19)
(ii) v. > max(0, k~2p-l) ,  k=l,...,n                     (5.20)
(iii) z. <min(2p+l, n-i+1) ,  i=l,...,n       (5.21)
Matrika A ima torej v spodnjem trikotniku natanko ^(n-p-1) (n-p) ničel, ki so razporejene tako, da ležijo v vsaki vrstici skupaj na začetku in jih je v k-tem stolpcu natanko max(0, n-p-k).
V zgornjem trikotniku pa je najmanj 2(n-2P-1)(n-2p) ničel, ki so razporejene tako, da ležijo skupaj na začetku vsakega stolpca in skupaj na koncu vsake vrstice.
6. Struktura matrik L in U
Oglejmo si sedaj razcep matrike A na produkt spodnje trikotne matrike L z enojkami na diagonali in zgornje trikotne matrike U. Tudi matriki L in U imata posebno strukturo glede položaja ničel, ki izvira iz posebne strukture matrike A.
Vse  niâle  iz   spodnjega   trikotnika matrike  A se   ohranijo  v  matriki  L.                                                                (T4)
Dokaz.   Matrika L je bila v splošnem primeru definirana s formulami (2.9) in (2.3). Naj velja pri nekem i
m±j - 0 i     j=l/.•-,r ,  r < u±
Potem sledi iz formul (2.4), da je
- 32 -
*ll+1)   =  ajj1, j=l,...,r , k=j+l,...,n      (6.1) Ker pa je a^,J = a.. = O pri k < u. , sledi iz (6.1), da je
aik+1) = ° ' k=r+1" • ¦ 'n Tedaj pa je po formuli (2.3) tudi
m     = a(r+1)/aCr+1)   = 0 mi,r+i  ai,r+l/ar+l,r+l  °
Pri r = 0 je trditev trivialna, saj je m.. = ail/a11 = °» če jeu. > 0.
Torej pri vsakem i velja
^ik = ° '  k=1/---'ui                                    ¦    (6*2)
Vse  ničle   iz  zgornjega  trikotnika  matrike  A se   ohranijo  v matriki  U.                                                                    (T5)
Dokaz.   Matrika U je bila v splošnem primeru definirana kot A*n) z elementi (2.8).
Naj velja pri nekem k
ujk " »jk = ° ' j=1.....r ' r < Vk
Poten sledi iz formul (2.4) .
aCJ + D _ a(5)    i=1     -   i=i + i     n
d.,        —  <*..     /    J- * t   •   •  * iL       /  i—JTX/.../H
in ker je
a^' m  0 ,   i=l, . . . ,vk
aik+1) = ° '   i=i+1'""vk Torej je tudi pri j = r in i = j+1
ur+l,k = ar+l,k = °
Pri r = 0 je trditev trivialna, saj je u.. = aij_ = a . = 0, če je v, > 0.
Torej je
uik B ° '  i=1.....vk
je
- 33 -
ali
Uik = ° '  k=i+zi'---'n                               (6.3)
7. Analiza zaokrožitvenih napak
Najprej na kratko ponovimo glavne korake analize zaokrožitvenih napak pri reševanju sistema linearnih enačb v splošnem primeru (razdelek 3), nato pa upoštevajmo posebnosti obravnavanega pasovnega primera.
Izračunana rešitev x sistema enačb
Ax = b je eksaktna rešitev sistema
(A + <5A)x = b kjer je perturbacijska matrika podana z izrazom
ÓA = E + ÔL-U + L*5U + SL*<5U                     (7.1)
in veljajo eksaktno enačbe
A + E = L "U
(L + SL)y = b                                                 (7.2)
(U + 5U)x = y                                                 (7.3)
Za norme nastopajočih matrik smo dobili ocene:
I|E|lp   <   2-01   ga  |lE'Hp       •                                  (7.4)
llLJlp   <   1-12  a  UöL'Hp                                      (7.5)
IJUlIp   <   1-12 ga !Uu'Hp                                    (7.61
INip   <   IlL'Slp                                                          ¦   (7.7)
Ilullp < g llu'üp                                                        <7-s>
za p = 1,«/ E. Tu je a osnovna zaokrožitvena napaka, g maksimalni nastopajoči element, matrike E', <5L', ÔU', L' in U' pa so matrike s celoštevilčnimi elementi, ki dajo pri danem načinu ocenjevanja skupaj z ustreznim faktorjem na desni strani ocene za ustrezne elemente matrike na levi.
- 34 -
V splošnem primeru smo dobili za te elemente naslednje vrednosti:
= '  = i - 1 ,  k>i
¦ik
'  -
'ik
m   k
u>u = i - i
6V±k  - k 5uik = k " *
Su'  = n - i + 1
t'     =   1 ik
u
/  _
ik
= 1
k   <   i
k   <   i
k   >   i
k  <   i
k   >   i
Nedefinirani elementi so vsi enaki 0.
Preden na kratko ponovimo analizo posameznih korakov z upoštevanjem ničel, to je Števil u., v, in z,, dodatno de-finirajmo še števila
w., = max (u . /V, } ,  i,k=l, . . . ,n ik       i  k  '
(7.9)
a) Matrika E
Pri razcepu matrike A na produkt LU smo v splošnem primeru imeli formule (3.1) - {3.11} za r=l,...,n-l. Ponovimo samo naj pomembnej še :
mir = <*irWr)){1 + el>
(r)      (r) eir  = Llair  '
i=r+l, .. . ,n a (r+1)   , (r) _ _ _<*)
(7.10)
ik
. (r) 'ik
{L
ik
mirark' a+e2î)(l+e3i
L3   (r+1)       Cr) —-— a.,     - toaj&li     eo 1+e-  ik      ir rk 2
i,k=r+l,.. . ,n
k > i
e   - V E(r) ik - tix   eik  '
'ik
k
= E
eL> ,  k < i
r=l  ik
(r)
(7.11)
(7.12)
(7.13)
Ker smo po (3.16) vse e.v^' ocenili z istim številom 2*01 ga, potem pomeni število e', število od nič različnih
IK
- 35 -
s urlando v v vsotah (7.12) in (7.13).
Sedaj pa upoštevajmo, da pri trivialni operaciji, to je pri množenju z 0 ali pri prištetju števila 0, ne nastane
nobena zaokrožitvena napaka.
(r)
Napaka e  je nie, Če jo a.   = 0, ali, kar jo ifjto,
Če je m.  = l.     = 0. Ugotovili smo (T4), da je to pri danem i za r=l,...,u..
Napaka e_ pa je nič in hkrati z njo tudi e, takrat,
ko je nrodukt m. a ,  = t.   u , = 0. To pa je takrat, ko je
¦*  ¦       ir rk    ir rk        r  J     .   "
vsaj eden od obeh faktorjev enak nič. Prvi faktor je nič po (T4) za r=l,...,u., drugi pa po (T5) za r=l,...,v . Torej sta glede na definicijo (7.9) L~ in e_ enaka nič za r=l,...,w., .
z      J                                                   1K
Na tem mestu je razvidno, da bi bilo možno, da je sa-
(r) mo e- enak nič. Se je a.,  = 0, produkt Z.   u , pa ne. To so
3                                        ik                                   ir rk
ničle iz druge skupine, o katerih smo rekli, da jih ne bomo
(r) upoštevali. V tem primeru bi za ustrezni e.V.  iz (7.11) dobili oceno ga namesto 2*01 ga. 2 upoštevanjem takih ničel bi ne mogli bistveno izboljšati ocene  za normo matrike E. Namesto enačbe (7.10) imamo torej za vsak i:
Lir  = ° ' r=1" - * 'ui
efr} m  Fa.{r) ,  r=u.+l,... ,1-1 ir    1 ir  '    i
in namesto (7.11) za vsak i in k
ik   1+E   ik      ir rk  2 r=w.,+l,. . . ,min(i-l ,k-l)
Torej veljajo v našem primeru namesto (7.12) in (7.13)
formule:       i-1    , .
ejn. =    E    e.fJ ,  e'  = max (0, i-1-w. ) , k>i   (7.14)
'ik  r=w +1     ik     '   ik —^>-  -   -lk' ik
kr*          (r)    (k)
r=w.k+l     lk    lk

- 36 -
t     _
"ik
¦ max(O, ^-w., } / k < i
(7.15)
(r)
Tri (7.15) je treba pojasniti, da so vsi e., , r < k enaki
(k) nič, če je e.V  = 0, kajti iz L., = 0 sledi, da je L.  = 0,
i/-                                                  IK                                                        1JT
r < k. Ocena (3.16) seveda ostane pri tem v veljavi, zato je [eik| < 2-01 ga e^
Za ilustracijo navedimo matrike E' za naše tri primere matrik, ki smo si jih ogledali v razdelku 5.
Iz (7.14) in (7.15) dobimo za te tri primere naslednje matrike:
h2
			0	0	0	0   0	0	0   0	G	0   0
			1	1	1	1   0	0   0   0		0	0   0
			1	2	2	2   1	0   0   0		0	0   0
			1	2	3	3   2	10   0		0	0   0
			0	1	2	3   3	2   10		0	0   0
E	r        m L		0	0	1	2   3	3   2   1		0	0   0
			0	0	0	1   2	3   3   2		1	0   0
			0	0	0	0   1	2   3   3		2	1   0
			0	0	0	0   0	1   2   3		3	2   1
			C	0	0	0   0	0   12		3	3   2
			L°	0	0	0   0	0   0   1		2	3   3 —
0   0	0   0	0   0		0	0	0   0	0			
0   0	0   0	0   0		0	0	0   0	0			
1   2	2   2	1 1		1	1	0   0	0			
0   0	1   1	1 1		i	1	0   0	0			
1   2	3   4	3   3		3	3	1   0	0			
0   0	0   0	0   0		0	0	0   0	0	e;		=
1   2	3   4	4   5		5	5	3   1	1			
0   0	0   1	2   3		4	4	4   2	2			
0   0	0   0	0   0		1	2	2   2	2			
0   0	0   0	1   2		3	4	5   4	4			
0   0	0   0	0   0		0	1	2   3	3			
3	0	0	0	C	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	C	0	0	0	0
0	0	0	0	0	0	0	0	0	0	G
0	0	0	0	0	0	0	0	C	0	0
0	0	0	0	0	0	0	0	0	0	G
1	2	3	4	5	6	7	7	6	5	4
I	2	3	4	5	6	7	7	7	6	5
1	2	3	4	5	6	7	7	7	7	e
b) Matriki L in 6L
Za matriko L smo že v (T4) ugotovili, kje ima ničle-, Za druge elemente pa velja
\tik\   < t'ik   ,     t^  - 1 ,  k^+1,.,.,1 , i >  k (7.16)
Pri analizi reševanja spodnjega trikotnega sistema bomo upoštevali ničle v matriki L.
V formuli (3.19) upoštevajmo (6.2). Tako dobimo, če sledimo splošni analizi (3.18) - (3.24):
-   37   -
i-1
kjer  je
Y,   = b, (1  +  ç4)   -       E        L<^n  +   ç„)
k=uL+i
i       ~i"~       "l"        ,,_^   , ,    "ik-^k^   '   ^ky
(7.17)
1 + çi - (1 + v**> •¦
i + çk = (i + ek) d + nfcî
d + nw)
d + nwJ
in veljajo ocene
Uvi  : a »  In.I  : a
*k' =
3' =
Enačbo (7.17) zapišimo v obliki
kjer je
bi * . S    LikYkU + Çk) k=Ui+l
l + Ci-  (l+^r1 =  (i+nUi+1)_1  ...   Cl+n^r1
i + çk =   (i+ck)(i+ç.)"x =   (i+ek)(i+nUi+1)_1...(i+nk-1î
Od  tod  sledi,   da   je  izračunani vektor y eksaktna  rešitev  sistema   (7.2),   pri  čemer veljajo ocene
61.A   <   1*12  a  61*     ,       &l'. .   =  i  -   1   - u. ii1   =                           li                   li                                i
(7.18)
St.. I   <   1*12  a  &t..    , ik '   =                      ik  '
&l'     = max(0,k-u.),k<i ik                                i
Matriki L' in <5L' sta v naših treh zgledih enaki
H-"
1							—	
1 1								
1 1 1								
111	1		'					
0   11	1	1						
0   0   1	1	1	1					<Lj  -
0   0   0	1	1	1	1				
0   0   0	0	1	1	1	1			
0   0   0	0	Q	1	1	1	1		
0   0   0	U	0	0	1	1	1	1	
0   0   0	0	0	0	0	1	1	1 1	
0							
1	1						
1	2	2					
1	2	3	3				
0	:	2	3	3			
0	0	1	2	3	3		
0	0	0	1	2	3	3	
0	0	0	0	1	2	3	3
0	0	0	0	0	I	2	3
0	0	0	0	0	0	1	2
0	0	0	0	0	0	0	1
2 3 3
- 38 -
H
H
1					y			
0   1								
1 1	1							
U   0	i	1						
1 1	:	i	1					
0   0	0	0	0	i				
1 1	1	1	1	i	1			
0   0	0	1	1	1	1	1		
0   0	0	0	0	0	1	1	1	
0   0	0	0	1	1	1	1	1	1
0   0	0	0	0	0	0	1	1	1 1
1								
0   1								
0   0	1							
0   0	0	1						
0   0	0	0	1					
0   0	0	0	0	1				
0   0	0	0	0	0	1			
0   0	0	0	0	0	0	1		
1 1	I	i	1	:	1	1	1	
1 1	1	1	1	:	1	1	1	1
1 1	1	1	:	i	1	1	1	1 1
	0									
	0	fi								
	1	2	2							
	0	0	1	1						
	1	2	3	4	4					
5L2  =	0	0	0	C	0	0				
	1	2	3	4	5	6	6			
	0	0	0	1	2	3	4	4		
	0	0	0	0	0	0	I	2	2	
	0	0	0	0	1	2	3	4	5	5
	0	0	0	U	C	G	0	1	2	3
	m									
	0									¦
	0	0								
	0	0	3							
	0	0	0	0						
	0	0	0	0	0					
6L3  =	0	0	0	0	0	0				
	0	0	0	0	0	0	0			
	0	0	0	0	0	0	0	0		
	:	2	3	4	5	6	7	8	8	
	i	2	3	4	5	6	7	8	9	9
	i	2	3	4	5	e	7	8	3	10
c) Matriki U in <5U
V (T5) smo ugotovili, kje ima matrika U ničle. Za druge elemente veljajo ocene:
!uik' =  g uik '       Uik = l '   k=i'---'i+zi~1    (7.19) ali     u', = 1 ,   i=v.+l,...,k
Pri analizi reševanja zgornjega trikotnega sistema bomo
upoštevali ničle matrike U, določenem (6.3).
Tako dobimo, če sledimo splošni analizi po formulah
(3.25) - (3.27):
i+Zi-1
x± -   (yi(l + çi)   -    _L^   Uikxk(1+Çk>> (1+ei)/uii     (7*20) kjer  je
k=i+l
i + ç    - (i + ni+1)
in veljajo ocene
{1   +   ^i+Zi-it1
1    +    Çk   =     {1    +    Lk)   (1    +   Tlk)
« + "W.i>
l€j|   <  a   ,
n.    < a
3 ¦   =
- 39 -
Enačbo (7.20) moremo zapisati v obliki
i+Zi-1
Vi =  E  uikxk^ + V
kjer je
i+Ck = (i+çk) (i+ç-T1 = ti+ek)(i+ni+1)"1...{i+i)k„x)":l
Izračunana rešitev x je torej eksaktna rešitev sistema (7.3), pri Čemer veljajo ocene
[Šu,4I < 1*12 ga Su'. ,       Su',. * 2.
11 =                                                     ii   i                                 {7#21)
Mu., j < 1*12 ga (Su'  ,   Su'  = k-i, i<k<i+z. 1  ik- =     *    lk      ik                                    i
Vsi drugi elementi so enaki nič.
Matriki U' in <5U ' sta v naših treh primerih enaki:
	1111	0	0 0 0	0 0	0		4 12 3	0 0	0	0	0	0 0
	111	i	0 0 0	0 0	0		4 1 2	3 0	0	0	0	0 0
	1  1	1	1 0 0	0 0	0		4 1	2 3	0	0	0	0 0
	1	1	110	0 0	0		4	1 2	3	0	0	0 0
		1	i i :	0 0	0	J		4 1	2	3	0	0 0
OJ -	i		ili	1 0	0	ÓU^ =		4	1	2	3	0 0
	¦		i i	1 1	0				4	1	2	3 0
			i	1 1 1 1 1	1 1 1 1					4	1 3	2 3 1  2 2 1 1
	—				_		-					
												
	1111	G	0 0 0	0 0	0		4 12 3	0 0	0	0	0	0 0
	111	1	111	0 0	0	'	7 12	3 4	5	6	0	0 0
	1  1	1	111	0 0	0		6 1	2 3	4	5	0	0 0
	1	1	1 1 1	1 0	0		6	1 2	3	4	5	0 0
		1	1 1 1	1 0	0			5 1	2	3	4	0 0
D2 «	¦		111 ' 1 1	1 1 1 1	1 1	6U; =		6	1 5	2 1	3 2	4 5 3 4
	•**		1	1 1 1 1 1	1 '1 1 1 -					4	1 3	2 3 1  2 2 1 1
- 40 -
U3 =
1  1 1
0 0 0 0 0 0
o 1 : : i i i i
	7   1	2	3	-1	5	6	D	0   0   0
	7	1	2	3	4	5	6	0   0   0
		7	1	2	3	4	5	6   0   0
			7	:	2	3	4	5   6   0
				7	1	2	3	4   5   6
ÖU3   -.					6	1	2	3   4   5
						5	1	2   3   4
.							4	1   2   3 3   1   2
								2   1 1
								
8. Ocene norm nastopajočih matrik
Poskusimo sedaj čimnatančneje oceniti vse tri norme petih nastopajočih matrik E', ÓL', c5U ', L' in U'. Začnimo pri enostavnejših računih.
a) Matrika L'
Od nič različni elementi matrike I/ so podani s (7.16), poleg tega pa vemo po (T4) in (TI), da je v spodnjem trikotniku matrike L' natanko ^(n-p-1)(n-p) ničel in sicer jih je v k-tem stolpcu natanko max(0,n-p-k).
Izračun vseh treh norm matrike L' je preprost. (i)
n                        n
|L'U. = max E i:v  - max E V     = 1   k i=l **   k i=k lK
= max ((n-k+1) - max(0,n-p-k)) = k
= max min(n-k+1,p+l) = p + 1
k
Zadnji enačaj velja, Če je n >  p, kar je vedno zaradi omejitve (4.2), ki je ne bomo več povdarjali. Iz (7.7) potem sledi, da velja
(u)  ||l'|
» =maX J/ik =naX t *   *îk = i k=l      i k=Uj.+ l
= max (i - u. ) < n

-   41   -
Iz   (7.7)   poten sledi
(iii)       IJl'Ill =   g      L Li| = |n<n+l)   - §(n-p~l) (n-p)   = E      i-l k=i  1JC      l                    l
= |(p+l)(2n-p)
Zato velja
IjL'ljg  <   t|(p*l) (2n-p))1/2
b)   Matrika U'
Od  nič  različni  elenenti matrike U'   so podani  s   (7.18)
n                               k
(i)            llu'll-   = max    E    u'     = max       E       u'     «
1         k     i=l     1K         k     i=v. +1   1Jt
k
= max   (k - v, )
k                  k
Ker velja   (5.20)   za  vsak k,   je
...
k  -  vk  <   2p +   1                                                      (8.1)
Zato  je
liü'Uj   <   2P +   1
in   iz   (7.8)   sledi
IJUlk   <  g(2p +  1)
n                        i+2i-l
(ii)          i|u'|L= max    Z     u'     = max    E"     u'     = max  z.
i     k=l                    i     k=i                      i
Iz (5.21) potem sledi
lIu'IL 5 2P + 1
in
IML< g(2p + 1)
«         n       n .       „         n     i+z.-1     _         n
{iii)      liu'j!2 -E      E   u'L =   e       T     u[k =   E    zi E      i=i  k=l    iic      1=1    k=i       1K      i=l     *
Iz  ocene   (5.21)   dobimo
7         n
Ilü'llp 4    E     min(2p+l,n-i+l)   =   (2p+l) (n-p) u '    i=l
-   42   -
Torej   velja  splošno
|lu[iE   <  g((2p+l) (n-p)}1/2
c)   Matrika   SU'
Od  nič  različni  elementi matrike   6U'   so podani  s   (7.21)
n                            k-1
(i)          IML   = max     E     ću'     = max(     E       tk-4J   +  Ž*J   =
1         k     i=l       1K        k     i=v,+l                   K
1                                 k
= max   {^(k-vk-l) (k-vk)   +  zfc)
k
.Če  upoštevamo  oceni   (8.1)   in   (5.21),   dobimo od  tod
\Wl\i  â   (P+1) (2P+1) Torej   je  zaradi   (7.6)
IJSUl^   <   1*12   ga   (p+l)'(2p+l)
n                        i+Zi-1
(ii)        !15tJ ' !L= raax     S    5u^k = max     E        &^lk =
i    k=l                   i    k=i
=» max   (z     +       E        (k-i))   ¦ i                k=i+l
= max  s ž. (2j   +  1)
i
Iz ocene (5.21) potem sledi
llffli'IL < cp+1) <2p+1>
in
SU]  < 1"12 ga (p+1)(2p+l)
(iii)  |16U'||2 =  E  E  «»iJ =
i=l k=l n      i+Zi-1     -=  E (zf +   E   (k-ip) = i=l     k=i+l
n 1 =  E e z   (z +1) C2Z.+1I                      (8.2)
*
Spet upoštevajmo oceno (5.21) in vsoto v (8.2) primerno razdelimo:
-.43 -
5   n-2p [[6U'[[; <  E  ±(2p+l) <2p+2)(4p+3) + L   i=l .
n     1 +   E    L(n-i+l) Cn-i+2)(2n-2i+3) =
i=n-2p+l b = |(P+D (2p+l) ((4p+3)n - p(6p+5) ) Od tod sledi :|SU[!E < 1*12 ga(|{p+l) (2p+l) ((4p+3)n - p(6p+5)))1/2
d) Matrika fiL'
Od nič različni elementi matrike SI/ so podani s [7.18)
(i)    |]6L'[|  = max  L $% =
k i=l n = max (  E  max {0 ,k-u . ) + k-u,-l) = k  i=k+l                     *      K
n = max ( E max(0,k-u.) - 1)      (8.3) k  i=k        *
Naj bo najprej k > n-p. Tedaj je
n max ( E max(0,k-u.) - 1) < max (k(n-k+l) - 1) = k>n-p i=k                                      ' k>n-p
= np - p2 + p - 1    (3.4)
2
Namreč funkcija -k + (n+l)k - 1  je nenaraščajoča za k > n-p,
saj je odvod -2k + n+1 manjši od -n + 2p+l, kar-je po predpostavki (4.2) nepozitivno število. 2ato je maksimum dosežen pri k ?= n-p+1.
Sedaj pa naj bo k < n-p. Haj prej ocenimo vsoto v oklepaju v (3.3):
n                                n                                k-1
E max(0,k-u.) =  E max(0,k-u.) -  E max(0,k-u.) i=k        x    i=l                     1    i=l
V prvi vsoti pišimo namesto u. izraz (5.17) in preuredimo su-macijo po indeksu j = s. (j pomeni indeks vrstice prvotne pasovne matrike, ki preide v i-to vrstico obravnavane matrike).
V drugi vsoti pa upoštevajmo oceno (5.19) . Tako dobimo
- 44 -
n                                  n
Z    max(O,k-u.) <  L max{O,k-max(O,j-p-1)) -
i=k       x   -  5-1
k-l - S max(0,k-i+l) = pk + 1
Toraj je                                   x~
n
max  "C ^ik š nax  P** = P(n~P) i k<n-p i=l      k<n-p
< pn - p2 + p - 1                                 (8.5)
Oceni (8.4) in (8.5) skupaj nam dasta
llfiL'1^ < pn - p2 + p - 1 Iz (7.5) potem sledi
IJÔLJIj < 1-12 a (pn - p2 + p - 1)
di)        HóL'll^ = max Z  &l[k =
1   JC— X
i-1 = max( L max(0,k-u.) + i-l-u.) = i  k=l                     1        *
i-1 = max(  L   (k-u.) + i-l-u.) = i  k=Ui+l    1        L
= max x(i-u.-l)(i-u,+2) <
i
Torej velja tudi
<  max  |(i-1) (i+2)   =  |(n-l) (n+2) i
SZt.ll    <   1*12  a  Ü-(n-l) (n+2)
11 oo =                                    z
\-\  k=l
n       i-1                 2                       p
=    L   (     E       (k-u.)z +   (i-u.-l}z)   =
i=l  k=Ui+l
=  \     E   (2i3+3i2-lli+6-2u3 + 3u2-rllu.) 6  i=l                                             lil
n
-    E iu. (i-u.+l)                          (8.6)
i=l
Če upoštevamo enačbo (5.17) in pišemo j = s., dobimo
- 45 -
n        n
E u. =  ;: max(0,j-p-1) = i(n-p-l) (n-p)                                 (0.7)
i=l  1   3=1
n   2    n                             2   1
E u; =  E max(Oo-p-l)^ = L(n-p-l) (n-p) (2h-2p-l)    (8.8)
L-1              j = l
p.                     n
E  u3   =  E max(0/j-p-l)3 = j(n-p-l)2{n-p)2           (8.9)
1=1              D=l
Prva vsota v (8.6) se da torej izračunati, drugo pa bomo ocenili z upoštevanjem enačbe (5.17) in ocene (5.18) pri j=s. :
n                                     n
E iu. (i-u.+l) = E i max(0, j-p-1) (i-max (0 , j-p-1) +1) = i=l   1   1     j=l
n                                                               n
=  E  i(j-p-l) (i-(j-p-l)+l) ž  E  2(j-p) (j-p-1) = j=P+2                                                       j=p+2
= 2(|(n-p-l)(n-p)(2n-2p-l) + \<n-p-l)(n-p))                          (8.10)
Če združimo (8.6) z izračuni (8.7) - (8.9) in z oceno (8.10), dobimo
Hol/JI2, < y|(4n3-6(p-2)n2+2(2p2-6p-7)n-(p3-4p2-7p-2))
Torej je
!ISlj|E< 1-12 a(y|<4n3-6(p-2)n2+2(2p2-6p-7)n-(p3-4p2-7p-2) )) 1/2
e) Matrika E'
Elementi matrike E' so bili definirani s formulama (7.14) in (7.15). Pri tem se spomnimo na definicijo (7.9).
n (i)                        |]E'H ,   =max     E    e'     =
1       . k     i=I     1K k                                              n
= max (   E    max (0 ,i-l-w.,J   +       E       max (0 ,k-w.. ) ) 1=1                                           i=k+l
Zaradi   ocene   (5.20)   velja
w..   = nax{u, ,v,J   >   max(u.,k-2p-l)                                (8.11)
-   46   -
Od  tod  poten  sledi
k ¦iE'!Ii   â max(   E    Itiax (Q,i-l-max (u . ,k-2p-l) )   + k     i=l                                 L
n +       E      max(0,k-max(u.,k-2p-l))   )                  (8.12)
i=k+l                             x
Najprej vzemimo, da je
n ^ 3p + 1                                                   (8.13)
in razdelimo množico 1 < k < n na tri dele: 1 < k < 2p+l, 2p+l < k < n-p ,  n-p < k < n  in poiščimo maksimum (8.12) na vsakem delu posebej.
Na prvi množici velja max(u.,k-2p-l) = u.  in zato ima-
mo, ker je u. > 0  in u. < i-1:
J    i =        i =
k                               n
max   ( E (i-l-u.) +  L. max(0,k-u.) ) = l<k<2p+l i=l     x         i=k+l        1
k =    max   ( E (i-l-u. - max(0,k-u.)) + l<k<2p+l i-1     1                           1
n + E max(0,k-u.) )                                                                            (8.14)
i=l                       1
V drugi vsoti upoštevajmo zvezo (5.17) in preuredimo sumacijo po indeksu j = s.:
n                                     n
E max(0,k-u.) = E max(0,k-max(0,j-p-1)) = i=l                       1   j=l
p+1      n =  E k +  E  max(0,k-j+p+l) j=l    j=p+2
Ker je na prvi množici zaradi (8.13)  k+p < n, dobimo
od tod                                                               , .
n                                                         k+p
E max(0,k-u.) = (p+l)k +  E  (k-j+p+1) -
i=l                      x                             j=P+2
= (p+l}k + ~  k(k-l)                            (8.15)
Prva vsota v (3.14) pa je enaka:
k                                                               k
Z   ((i-l-u ) - max(0,k-u. )) =  E min(i-l-u.,i-k-1) = i=l      1                             x           i-1        i
- 47 -
1=1
sa "
= E (i-k-i) - - I kCk+i) i=i
2p+
j je u. <  i-1 < k-1.
Zato velja na prvi množici
n                                          1                                          1
max    E eî. <  max   (- a  k(k+l) + (p+l)k + 5 k(k-l)) =
l<k<2p+l i=l  1K  l<k<2p+l
max  pk = p(2p+l)                                   (8.16)
l<k<2p+l
Na drugi in tretji množici je izraz k-2p-l pozitiven. Najprej izraz na desni v (8.12) prepišimo v obliko ¦
n                                          k
max   E g'     <   max  (  E (max(0,i-l-max(u.,k-2p-l)} -¦Kk<n 1=1  lK r: 2p+Kk<n  1=1                                    X
n - max(0,k-max(u.,k-2p-l))) +  L max(0,k-max(u.,k-2p-l)) )
i=1                                                 (8.17)
V drugi vsoti upoštevajmo (5.17) in preuredimo
sumacijo po indeksu j = s.:
¦
n
E max(0,k-max(u.,k-2p-l)) = i=l                               x
n =  E max(0,k-max(max(0,j-p-1),k-2p-l)) = j = l k-p                             n
E  (2p+l) +   E  inax(0,k-j+p+l)                              (8.18)
j=l                      j=k-p+l
Prvo vsoto v (8.17) pa razdelimo na dva dela. Prvi del
je enak
k-2p-l
E   (max(0,min(i-l-u., i-k+2p)) - max(0/min(k-u.,2p+l))) = i=l                                        x
k-2p-l .
E  -(2p+l) = - (2p+l)(k-2o-l)                                   (8.19)
i-l
ker je
u. < i-l < k~2p-2 torej
i-l-u. > i-k+2p+l
- 48 -
in
k-u. > 2p+2 Drugi del prve vsote v (8.17) pa je enak
E   (max(0,min(i-l-u.,i-k+2p)) -i=k-2p                                   1
- max(0,min(k-u.,2p+l))) =
k
E   (i-k-1) = - (p+1) (2p+l)                                         (6.20)
i=k-2p
ker so sedaj zaradi
in
u. < i-1 <  k-1
k-u. > 1
i =
vsi štirje izrazi i-l-u., i-k+2p, k-u. in 2p+l nenegativni in hkrati nastopita prvi in tretji ali drugi in četrti. Velja namreč
(i-l-u.) - (i-k+2p) = k-u.-2p-l
(k-uj_) - (2p+l) = k-ui-2p-l
Zato je izraz v zunanjem oklepaju v (8.20) enak
(i-l-u.) - (k-u.) = (i-k+2p) - (2p+l) = i-k-1
Prva vsota v (8.17) je torej na drugi in tretji množici enaka vsoti izrazov (8.19) in (8.20): .
-(2p+l) (k-2p-l) - (p+1) (2p+l) = -<2p+l) (k-p)   (8.21)
Iz (8.18) in (8.21) sledi, da velja na drugi množici
n max    E e'  <    max   ( (2p+l) (k-p) + 2p+l<k<n-p i=l       2p+l<k<n-p
k+p +    Z        max(0,k-j+p+l) - (2p+l) (k-p) ) =p(2p+l) j=k-p+l
(8.22)
- 49 -
Na tretji množici pa imamo
n                                          n
max   L e'v ~  raax     L   (k-j+p+1) = n-p<k<n i=l  x   n-p<k<n j=k-p+l
max   (p(2p+l) - 2(k-n+p+1)(k-n+p)) « p(2p+l) - 1 n_P<kän                                                                                        (8.23)
kajti izraz v oklepaju zavzame maksimum pri k = n-p+1.
Torej sledi iz (8.16), (8.22) in (8.23) pri pogoju (8.13) , da velja
IIe'IIj < P(2p+1)                                                 (8.24)
Ugotovimo še, da je ta ocena veljavna tudi v primeru
2p+l < n < 3p+l                                               (8.25)
Izkaže se, da velja tedaj stroga neenakost.
Množico k = l,...,n razdelimo na tri dele takole: 1 < k < n-p,  n-p < k < 2p+l,  2p+l < k < n.
Če upoštevamo (8.16), dobimo za prvo množico, ker je
n-p < 2p+l, oceno:
n max   E  e'v. <  max  pk = p (n-p) = l<k<n-p i=l  a   l<k<n-p
= p(2p+l) - p(3p+l - n) < p(2p+l)
Na drugi množici pa upoštevajmo (8.16) s korekturo v formuli (8.15), ker je sedaj n < k+p. Tako dobimo
n                                                     1
max     Z    e', <   max    (pk - ^ (k-rn-p+l) {k-n+p) )
n-p<k<2p+l i=l      ¦ n-p<k<2p+l =  p(2p+l) - |(3p+l-n) (3p+2-n) < p(2p+l)
saj je maximum dosežen pri k = 2p+l.
Na tretji množici pa velja kot v (8.23):
n
max   ]T e', <   max  (p(2p+l) - ^(k-n+p+D* 2p+Kk<n i=l       2p+Kk<n
(k-n+p)) = p(2p+l) - |(3p+2-n) (3p-i-3-n) < p(2p+l)
- 50 -
Sedaj je maksimum dosežen pri k = 2p+2. Torej pri pogoju (8.25) velja
IJE'lij < P(2p+1)
in zato velja ocena (8.24) splošno za vsak n > 2p+l. Iz ocene (3.24) in iz (7.4) potem sledi
jjE]^ <j 2*01 ga p(2p+l)
n (ii)   ||EM[Ä= max E eLk = i k=l i-1                                    n
= max ( E max(0,k-w., ) +  E max (0 ,i-l-w., ) ) i  k=l        lk   k=i                        lK
Iz definicije (7.9) in ocene (5.20) sledi, da velja za vsak i ocena
w., = max (u . ,v,) j» v. g max (0 ,k-2p-l)
Zato  imamo oceno
i-1
||E'[I     < max   (  E    max(0,k-max(0,k-2p-l) )   + ™ "     i       k=l n +       T    max(0,i-l-max(0,k-2p-l))    )          (8.26)
k=i
Vzemimo najprej, da velja
n > 4p + 1                                                                   (8.27)
V tem primeru razdelimo množico i = l,...,n na tri dele takole: 1 < i < 2p+l,  2p+l < i < n-2p,  n-2p < i < n.
Na prvem delu imamo
n                                        i-1    2p+l
max    E e|v <  rnax   (  E k +  V  (i-1) + l<i<2p+l k=l      l<i<2p+l  k=l    k=i
i+2p-l +    E    (i+2p-k) ) =  max   (2p+l) (i-1) = 2p{2p+l)
k=2p+l                               l^i<2p+l                                           /o 28)
Na drugem delu dobimo
n                                              2 p
max     E e!, <    max    (  E k + 2p+l<i<n-2p k=l       2p+l<i<n-2p  k=l
-   SI   -
i-I                         i+2p-l
+       E        (2p+l)   +       L        (i+2p-k)    )   -           max          (2p+l) (i-1)   =
k=2p+l                      k=i                                 2p+l<i<in-2p
=   {2p+l)n  -   4p2   -   4p  -   1                                                              (8.29)
¦
Na tretjem delu pa velja
n                                     2p     1-1
max   %    e' <         max  ( E k +  E   (2p+l) +
n-2p<i<n k=l      n-2p<i<n k=l   k=2p+l n + E (i+2p-kî ) =   max  ((2p+l)(i-l) -k=i                             n-2p<i<n
- |(i+2p-n)(i+2p-n-l)) = (2p+l)n - 2p2 - p - 1      (8.30)
kajti maksimum je dosežen pri i = n.
Ker je izraz (8.30) večji od izrazov (8.29) in (8.28), je zato pri pogoju (8.27)
!lE'Lš (2P+1)n - 2p2 - p - 1                                (8.31)
Prepričajmo se še, da je tudi pri pogoju
2p+l < n < 4p+l
ocena (8.31) veljavna. Sedaj pa razdelimo množico i = l,...,n na tri dele takole: 1 < i < n-2p,  n-2p < i < 2p+l,  2p+l < < i < n .. Brez težav dobimo iz (8.26) naslednje ocene. Na prvem delu je
n                                        i-1    2p+l
max    E e'     <  max   (  E k + E  (i-î) + l<i<n-2p k=l  1K   l<i<n-2p k=l    k=i
i+2p-l +  E   <i+2p-k) ) =  max    (2p+l) (i-1) = (2p+l) (n-2p-l) = k=2p+2                             l<i<n-2p
2                                                     2
= (2p+l)n - 4p  - 4p - 1 < (2p+l)n - 2p  - p - 1
Na drugem delu dobimo
n                                              i-1    2p+l
max     E é*  <    max    (  E k +  E  (i-1) + n-2p<i<2p+l k=l     " n-2p<i<2p+l  k=l     k=i
n +   E   (i+2p-k) ) =    max    ((2p+l) (i-i) -k=2p+2                             n-2p<i<2p+l
- 52 -
- ~(i+2p-n) (i+2p-n-U) = 2p(2p+l) - | (4p+l - n> (4p - n)
(3.32) Maksimum je namreč dosežen pri i = 2p+l. Izraz (8.32) ni večji od izraza (8.31), enak mu je lahko le pri n = 2p+l. Na tretjem delu pa velja
n                                     2p      i-1
max   T e'  <   max  (  E k +   E   (2p+l) + 2p+Ki<n k=l       2p+Ki<n  k=l     k=2p+l
n                                                                       1
+ L   (i+2p-k) ) =   max  ((2p+l)(i-1)-a(i+2p-n)(i+2p-n-l))=
k=i                           2p+l<i^n
2 = (2p+l)n - 2p  - p - 1
Tu je spet maksimum dosežen pri i = n. Torej velja ocena (3.31) za vsak n, > 2p+l.
Iz (8.31) torej sledi
IlEJl^  <   2-01   ga((2p+l)n   -   2p2   -  p  -   1)
(iii)           flE'11    «   E     Z   ell =
k=l   i=l n        k                                 „           n                             -
=    E     (  E    max{0,i-l-wik)^  +       t    max(0,k-wik)^   } k=l     i=l                                       i=k+l
Tu spet uporabimo oceno (8.11) in dobimo
9   n   k                                                     ?
IlE'lip <  E  { E max(Q,i-l-max(u ,k-2p-l))z +
*¦   k=l  i=l
n                                                  2
+  E max(0,k-max(u.,k-2p-l))  ) =
i=k+l                           x
n    k                         •                               ~
= E  ( E ( max(0,i-l-max(u.,k-2p-l))  -k=l  i=l                                   x
2 - max(0,k-max(u.,k-2p-l) )  ) +
n                                                 2
+ E max(0,k-max(u.,k-2p-l))  )       (8.33)
1=1
Vsoto na k = 1 do k = n razdelimo na tri dele: 1 < k <   2p+l, 2p+2 < k < n-p,  n-p+1 < k < n. Če je 2p+l < n < 3p+l, potem
- 53 -
ina srednja vsota zgornjo mejo manjšo od spodnje, kar pri seštevanju prav nie ne moti.
Pri prvi vsoti je k-2p-l < 0, max{u, ,k-2p-l) = u. in pri i < k je tudi u. < 1-1 < k. V vsoti od i = 1 do i = n pa uporabimo že večkrat uporabljen prijem: upoštevamo formulo L5.17) in preuredimo sumacijo po indeksu j = s.. Tako dobimo
2p+l n    ~        2p+l   k                      ^        „
E  E Bit <   E  (E ((i-i-u )d -  (k-u r) + k=i i=i 1K  k=i  i=i     1      x
n                                                   2
+ Z    max(0,k-max{0,j-p-1))  ) =
j = l 2p+l   k      „ = E   (E ((i-i)  - ^    + 2{k+l-i)u ) + k=l   i=l
p+1  »    k+p                      _
+    Z    kz +      Z    (k-j+p+ir ) j=l      j=p+2
Tu upoštevajmo še, da je u. < i-1. Tako dobimo
2p+l n    0        2p+l   k        ?        9
E  L e'J .  E   (E -(i-k-1)^ + (p+l)k^ + k=l i=l      k=l  1=1
2p+l + | k(k-l) (2k-l) ) =  E  pk  = 6                                        k=l
m  | p{p+l) (2p+l) (4p+3)                                    (S.3*)
Drugo vsoto od k=2p+2 do k=n-p v (8.33) najprej nekoliko predelajmo;
n-p   n  _   n-p     k E    E e'j <  E    (E c.„ + k=2p+2 i=l 1K '" k=2p+2   i=l
n                                                                           2
+  E max(0,k-max(max[U,j-p-1),k-2p-l) ) ) =
j-l
n-p  k-2p-l       k
= t      ( E  e  +  E  e  +
k=2p+2  i=l   iK   i=k-2p  iX k-p     ~    k+D                        -,
+ E (2p+l)  +   E"  (k-j+p+1) )   (3.34) j=l                       j=k-p+l
Tu pomeni
2 e, = max (0 ,min (i-l-u . ,i~k-H2p) ) jL J^                                                                                   r
2 - max (0,min(k-u.,2p+l))
- 54 -
Ko je i < k-2p-l, je u, < i-1 < k-2p-2 in zato je k-u. > 2p+2 in. i-k+2p < -1. Torej je
k-2p-l      k-2p-l
E  c   -   L  -(2p+l)^ = -(k-2p-l) (2p+l)^    (8.35) i=l   1K   i=l
Ko pa je k-2p < i < k, je i-l-u. > 0, i-k+2p > 0,
k-u. > k-i+1 > 1 in ker je
i =      =                         J    .
(i-l-u.) - (i-k+2p) = (k-u.) - (2p+l) je zato bodisi
bodisi
cik = (i-i-u^2  -   &-uL)2  = (i-1)2 - k2 + 2 (k-i+1)u±
c. = (i-k+2p)2 - (2p+l)2 = -(k-i+1) (i-k+4p+l)
'ik Ker pa je u. < i-1, je
(i-1)2 - k2 + 2(k-i+l)u. < -(k-i+1)2 Obenem pa velja tudi
-(k-i+1) (i-k+4p+l) < -(k-i+1)2 saj je
-(k-i+1)2 + (k-i+1)(i-k+4p+l) = 2(k-i+l)(i-k+2p) >  0
Zato moremo oceniti drugo vsoto takole:
k                          k
Z         cik <   L  -(k-i+1)2 m  -|(p+l) (2p+l) (4p+3)
i=k-2p    ¦ i=k-2p                                                                  (8t36)
Iz (8.34), (8.35) in (8.36) dobimo torej
n-p   n   -   n—p                                          -
E     E  e'J <   I    C-(k-2p-l)(2p+l)^ -k=2p+2 i=l  1K " k=2p+2
-  |(p+l) (2p+l) (4p+3) + (k-p) (2p+l)2 + |p(2p+l) (4p+l) ) =
n-p E   p(2p+l)^ = p(2p+l)z(n - 3p - 1)                            (8.37)
k=2p+2
Ocenimo še tretji del vsote v (8.33) in sicer vsoto od k = n-p+1 do k = n. Ta del obdelamo podobno kot prejšnji
- 55 -
del, le da sedaj upoštevamo, da je k+p > n in zato moramo v vsoti (S.34) zgornjo mejo k+p nadomestiti z n. Upoštevajoč prejšnji rezultat tako dobimo:
n    n    -      n                       _    k+p                    _
Z          Z    e[     <         Z        (p<2p+ir -   Z     (k-j+p+ir) =
k=n-p+l i=l      k=n-p+l                         j=n+l
= p2(2p+l)2 - ~  p(p+l)2(p+2) =
=     ^(47p3   +   44p2  +   7p  -   2)                                                         (8.38)
Če  seštejemo ocene   (8.3*),    (8.37)   in   (8.38),   dobimo l|E'jj2   <  p(2p+l)2n  -  ^(65p3   +  76p2  +   25p  +   2)           (8.39)
Torej  velja
|1E|IE   <   2*01   ga(p(2p+l)2n  - ^<65p3  +   76p2  +   25p  +   2) ) 1/2
9. Končne ocene
Zdaj lahko' izpeljemo končne ocene za norme perturbacij -ske matrike <SA.
Iz zveze (7.1) in ocen za norme nastopajočih matrik iz prejšnjega razdelka dobimo
HfiAi^ < Mj + !1 «LU x m\1 + |!l|[1   i«tfij1 +   iifiLj^   üfiüi^
in
^ HfiAJIj   <   2-01   p(2p+l)   +   l*12{2p+l) (pn-p2+p-l)   +
+     l*12{p+l)2(2p+l)   +   l*122(p+l) (2p+l) (pn-p2+p-l)a V  zadnjem  členu  upoštevajmo  pogoj    (1.4):
2
{pn-p +p-l)a  <  pna  <  o"l  p
Tako dobimo
•\ H 6A|]      <   1*12  p(2p+l) (n  +   0"12p  +   4*92} Če  to  oceno  še malo  polepšamo,   dobimo
|| 6A[| x   <   1*12   p(2p+l) (n+p+5)ga                                             (9.1)
- 56 -
Za  j[ÔAJ|  dobimo po podobni poti naslednje ocene:
PAL < iiEii^ +  U«ilLll«!L + i|L!!j«ĐlU+  U«tflÄll«ö|L
m ll5AIL Ž 2*01 ( (2p+l)n-2p2-p-l) + 0"56(2p+l) (n2+n-2) + +  l'12(2p+l) (p+l)n + | l'122(p+l) <2p+l) {n-1) (n+2) a
V zadnjem členu upoštevajmo pogoj (1.4) :
{n-l}a < na < 0*1 in tako dobimo
m !16A11* = f2p+1) (0*56n2 + (l"19p+3'76)n - (1 " SSp+0 ' 99) ) in od tod po primerni zaokrožitvi navzgor
il<5A'L < 0*56(2p+l)n(n+3p+6)ga                             (9.2)
Ta ocena je asimptotično za faktor n/2p slabša od ocene za jjóA'J..
Končno ocenimo še |j 6A]j . Pri tem moramo zaradi enostav-nej šega računa nekaj žrtvovati na strogosti ocene, toda le pri manj pomembnih členih. Znebiti se moramo namreč kompliciranih izrazov pod koreni.
Z elementarnim računom poenostavimo ocene za evklidske norme nastopajočih matrik takole:
ftfiJL < 2*01 ga(2p+l)/pn"                                       (9.3)
[]5L||  < o*56 an/2pn []|U]L < 0*65 ga(2p+l) /5pn
l]L|lE < /2pii |]U|!E < g/3pn"
Pri nekaterih od teh ocen smo predpostavili, da je n > 4. Iz ocene
||5A]!E < !tE!|E + !|6LJ]E |fu|!E + J!LJIE |J5U!1E + J!6L[!E («Ofl* sledi
— !I6A||  < 2*01(2p+l)/pn + 0"56/6pn2 + 0 * 65/TO(2p+l} pn +
y â     . Xj
+ 0*56-0*65/TÖ(2p+l)pn-na Ker je na < O'l, dobimo po elementarnih poenostavitvah
-.57 -
j|ÔA|| ¦< 1"33 pn(n+5p+3)ga                                       (9.4)
Tudi ta ocena je slabša od ocene za  |!SA]L.
Da se ocene ne dajo izboljšati, se moremo prepričati na primeru. Pri tem gre seveda le za preskus strogosti ocen za posamezne norme nastopajočih matrik.
Vzemimo matriko tipa A  iz razdelka 5 (5.16). Iz formul (5.15) in definicij matrik E', <SL' ,  L', 6U' in U' dobimo z direktnim računom, če vzamemo, da je
n > 4p + i
za vse norme teh matrik enake vrednosti kot so dobljene ocene,
razen pri evklidski normi matrike E', kjer dobimo naslednjo
vrednost:                _                   _                   %            i
i|Ej|l|  =  p(2p+l)   n  -  3J|(71pJ   +   96p^   +   43p  +   6)
Torej je ocena (8.39) kvečjemu malo pregroba, saj se v glavnem členu ujemata. V poenostavljeni oceni (9.3) se ta razlika nič ne pozna.
Končne ocene (9.1), (9.2) in (9.4) so torej kar se da natančno izračunane.
10. Diagonalno dominantne pasovne matrike
Še ugodnejše ocene za normo perturbacijske matrike dobimo, če je dana pasovna matrika diagonalno dominantna. Tudi take matrike v praksi niso redke.
Vzemimo sedaj, da je dana nesingularna matrika A takšna, da velja poleg
aik = ° '  I1"*' >  ?
še P°go^                           k-1                    k+p
|akk| >  Z     |aik! +  S  ja.jj ,   k=l,...,n i=k-p       i=k+l
Vsak diagonalni element je večji ali kvečjemu enak vsoti absolutnih vrednosti'izvendiagonalnih elementov v istem stolpcu.
- 58 -
Izkaže se, da v primeru, ko je matrika diagonalno dominantna, pri delnem pivotiranju ni potrebna nobena zamenjava vrstic. Diagonalna dominantnost se namreč ohranja., v toku Gaus-sove eliminacije (Wilkinson (1961)). Za tako matriko veljajo torej formule (5.14) {primer A }. Tedaj imamo
u = max(0,r-p-l)
v. = max{0,r-p-l)                                          (10.1)
z  = min (p+1 ,n-r-rl)
Pri oceni norm posameznih perturbacijskih matrik moremo torej izkoristiti splošne formule (7.4) - (7.8) in definicije matrik E', &L,' , 6W,   L' in U'. Pojdimo kar v istem vrstnem redu kot v razdelku 8.
a) Matrika L7
Iz (10.1) in definicije (7.16) sledi, da so od nič različni elementi matrike L' podani takole:
l'     =  1 , max(0,i-p-l) < k < i
Od tod dobimo
|[L'||  = p + 1                                                  (10.2)
b*i\m = P + 1
!'l'!!e = l(p + i} (2r " p)        U0*3I
b) Matrika U'
Iz (10.1) in definicije (7.19) sledi, da so od nič različni elementi matrike U' podani takole:
u^k = 1 ,  i < k < min(i-hp,n) Tudi tu dobimo brez težav isti rezultat kot prej.
Ilu'11  = p + 1                                                       (10.4)
ÜU'SL = p + 1
'¦U'^E = I{P + 1} (2n " p)                            (10.5)
- 59 -
e) Matrika SU'
Iz (10.1) in definicije (7.21) dobimo, da so od nič različni elementi matrike <SU ' takile:
Su'. = min(p+1,n-i+l)
Su', = k-i ,  i .< k <  min(i+p,n)
Od   tod  izračunamo
IjSU'l^   =  |(p+D <p+2)                                                (10.6)
liwiU w |(p+jl> <p+2)
IISU'I]2, = fUp+1) (p+2) (2(2p+3)n - p(3p+5))
E   12                                                                   (10.7)
d) Matrika $b'
Iz definicije (7.18) in iz (10.1) sledi, da so od nič različni elementi matrike Si/ podani takole:
St'. .   = min(i-l,p)
&t',   = max(0,k-max(0,i-p-l)),  k < i
Od tod izračunamo
Ifai/Jlj   =  |p(p+3)                                                  (10.8)
liöL'L  =  |p(P+3)
[|€L'f||  = ^{2(2p2+9p+l)n   -   (p+1) (3p2+llp-2))
(10.9)
e)    Matrika  E'
Iz   (10.1)   in definicije   (7.14)   sledi,   da  je matrika  E' podana  takole:
eî,    = max (0 ,min{i-l, i+p-k) )    ,     k   >   i
IK
e',    = max(0,min(k,k+p+l-i))    ,     k   <   i
Xr-n
saj je pri k >  1,   wik = vk in pri k < i, w^k = u^,
Od tod izračunamo .
|J.E'j|  = p(p+l)                                                             (10.10)
Il E'IL = P(p+li
ll;E*ll| = f(p+l) C2(2p+l)n - 3P(p+l))                    (10.11)
Zdaj pa izpeljimo še končne ocene za perturbacijsko matriko <SA. Pri tem borno uporabili poleg zveze (7.1) še ocene (7.4) - (7.8) .
Iz (10.2), (10.4), (10.6), (10.3) in (10.10) sledi:
P IlAJjj < 2*01 p(p+l) + 1*12 \  p(p+3) (p+1) +
+ 1*12 |(p+l)2(p+2) + 1*12  | p(p+D (p+2) (p+3)a
Tu upoštevajmo, da je
2pa < na < 0*1 in po elementarnih poenostavitvah dobimo oceno
IIjSÄjjj < 1*14(p+l) (p2+5p+l)ga Prav tako velja
[liSAJL < 1*14 (p+l) (p2+5p+l)ga
saj so ocene za posamezne matrike iste.
Ocenimo Še evklidsko normo. Najprej posamezne norme (10.3), (10.5), (10.7), (10.9) in (10.11) ocenimo tako, da si poenostavimo nadaljnji račun:
[IlML < /Tp+TTn"
"h,
|JU'[|E   <   /(p+l)n
|J6U'!!E   <   (p+2)vMp+Un/3
]|6L'||E   <   p/(p+l)n
1JE'[1E   <   (p+l)/2pn/3
Od  tod dobimo
— [j SAl!      <   2 "01 (p+l) /2pn/3  +   1*12   p(p+l)n  + ga  "      "b   —
+   l'12(p+2) /T73"(p+l)n  +   l*122p(p+2)/T73"(p-rl)na
Tu upoštevajmo,   da  je na   <   0*1.   Tako  dobimo po poenostavitvi                                                     j
j|<5AÜE  <   1*77(p+l)    (n  +   /n  +  p) ga
-gi-
ll . Povzetek rezultatov
Pri ocenjevanju norm perturbacijske matrike ÓA srno
prišli do naslednjih zaključkov (pri fiksiranih pogojih glede
aritmetike):
Pri splošni matriki so vse tri norme ocenjene s (3,29), 3 kjer je f (n) = 0{n ), pri splošni pasovni (2p+l)-diagonalni
P                         2
matriki je f, (n) = 0(p n), druga dva faktorja f (n) in f„(n)
pa sta reda 0(pn ). Pri diagonalno dominantni pasovni matriki
pa velja f 1 (n) = fÄ(n} =0(p3) in fL (n) = 0(p2n).
Iz tega moremo sklepati, da je Gaussova metoda z delnim pivotiranjem za pasovne matrike tudi s stališča analize napak zelo uspešna in posebno priporočljiva, če so te matrike diagonalno dominantne.
Za še boljšo potrditev tega sklepa pa si moramo ogledati podrobno še ocene za pivotno rast, to je ocene za število g.
-   62   -
III.      PIVOTWA     RAST
12.   Znane  ocene
V oceni (3.29) za normo perturbacijske matrike nastopa tudi faktor g, ki je bil definiran kot
(r)
a.
i, k, r
g = max i a..
ik i
Število g nam pove, kako veliki morejo postati elemen-
(r) ti matrik A   v toku Gaussove eliminacije.
Vpeljimo ustrezno relativno število:
R = g/max [ a±k| i/k
To število nam pove, za kakšen faktor morejo kvečjemu
(r)
narasti elementi posameznih matrik A   glede na absolutno
največji element prvotne matrike. Če R poznamo, je tedaj
g = R max I a., I i,k   lk
Pri ocenjevanju faktorja R bomo suponirali, da je matrika A nesingularna in tako normirana, da je
max la.,  = 1                                                (12.1)
I,*'  lkl
Tedaj je očitno g = R. študirali bomo torej, kako naraščajo elementi v toku eliminacij pri pogoju (12.1).
Če izvajamo eliminacije brez pivotiranja, se v splošnem lahko zgodi, da je R poljubno veliko Število. Torej brez dodatnih predpostavk ni mogoče dobiti nobene ocene za R. Obenem se spomnimo tudi, da je bila ocena (3.29) izpeljana pri pogoju, da so elementi spodnje trikotne matrike L absolutno omejeni z 1, torej pri pogoju, da izvajamo eliminacije npr. z delnim pivotiranjem.
- 63 -
Oglejmo si nekaj ocen za število R, ki jih je izpeljal Wilkinson (1961) .-
a) Pri delnem pivotiranju velja ocena
,n-l
R < 2
(12.2)
Iz formul (2.4)
m pogoja sledi
(r+1)    (r)       (r) i..    = a..  - m. a V lk      ik    ir rk
m.   < 1
1 ir ' =
\J*^\   < 2 max \*$ \
lk       i,k  lk
Torej velja tudi (r+1)
max | a i,k
ik
< 2 max ja.(J} I
=  i,k  lk
(12.3)
Na vsakem koraku eliminacije je kvečjemu možen porast elementov za faktor 2, torej velja
max laf?1 J < 2n_1 max la., I = 2n_1
. , ' ik ' =     . , ' ik1 i,k                                 i,k
(12.4)
Iz (12.3) in (12.4) takoj sledi veljavnost ocene (12.2), Enačaj je v tej oceni možen. Vzemimo primer take matrike pri n = 6.
A =
1	C	0	0	0	1
1	1	0	0	0	1
1	-1	1	0	0	1
1	-1	-1	1 J.	C	1
1	-1	-1	-1	1	1
1	-1	-1	-1	-1	1
(6) _
1	0	0	0	0	1
0	1	0	0	0	2
0	0	1	0	0	4
0	0	0	1	0	8
0	0	G	0	1	16
0	0	0	0	0	32
Toda to je zelo specialen primer. V praksi je znaten porast elementov zelo redek.
b) Če je A diagonalno dominantna matrika, je
R < 2
brez pivotiranja.
- 64 -
e) Če je A tridiagonalna matrika, velja ocena
R < 2                                                            (12.5)
pri delnem pivotiranju.
Oglejmo si dokaz za oceno (12.5), ker bomo v zadnjem razdelku ta rezultat posplošili na poljubne pasovne matrike.
Naj bo torej A tridiagonalna matrika:
aik = ° '  [i-fe| > A t   [aik[ < 1 Pri Gaussovi eliminaciji z delnim pivotiranjem prideta v poštev pri izbiri pivota vedno samo dva elementa. Oglejmo si
r-ti korak eliminacije in si ponazorimo samo tiste elemente
(r) matrike A   , ki so na tem koraku zanimivi:
rr        r,r+l ar+l,r    ar+l,r+l    ar+l,r+2
0         ar+2,r+l    ar+2,r+2
Elementi brez zgornjega indeksa so elementi prvotne matrike. Vzemimo nadalje, da veljajo ocene:
|a(r)[ < 2 ,   |a(r)  I < 1
1 rr 1 =      1 r,r+l- =                                 (12>6)
jaikl  < 1 ,   i > r+l, k > r
kar je pri r = 1 prav gotovo izpolnjeno.
Oglejmo si sedaj en korak eliminacije. Imamo dve
možnosti:
(i)     la(r) I > la ,.  1                                                  (12.7)
1 rr '   =   '   r+l,r
V tem primeru vrstic r in r+l ne zamenjamo in r-ta vrstica zgornje trikotne matrike U postane «      n  , (r)   (r)
Nova elementa (r+l)-te vrstice izračunamo po formulah:
(r+l)                             _ ar+l,r   (r)
r+l,r+l   ar+l,r+l     (r)    r,r+l
rr
- 65 -
r+l,r+2    r+l,r+2
Vsi drugi elementi ostanejo nespremenjeni. Če upoštevano (12.6) in (12.7), dobimo od tod naslednje ocene:

1 r+l,r+l! = ' r+1rr+l'   ] r,r+l' =
laril,r+2! = tar+l,r+2l = 1 ja.. ] < 1 ,  i > r+2,  k > r+l
(ii>    t^r'f < lar+l,ri                                                           (12*8)
V tem primeru najprej zamenjamo r-to in (r+l)-to vrstico  tako, da dobimo na ustreznih mestih situacijo:
a
r+
l,r  ar+l,r+l  ar+l,r+2
rr     r,r+l
ar+2,r+l  ar+2,r+2 Tako postane r-ta vrstica matrike U
0, ... , 0, ar+1^r, ar+1^r+1, arS-i,r+2' °' "¦ ' ° Nato izvedemo eliminacijo po formulah
„(r+l)       aa(r)       _^rr_
(r+l)             (r)        _     "rr
Lr+l,r+l "*    r,r+l        ar+1 fc r+l,r+l
a(r) (r+l)        .         rr
r+l,r+2            a             r+l,r+2

Vsi drugi elementi ostanejo nespremenjeni. Iz (12.6) in (12.8) potem sledi:
l«LLi«l L lar+l,r+2! S 1 |a,, i < 1 ,  i > r+2 ,  k > r+l
- 66 -
V obeh primerih imamo torej spet situacijo kot pred tem korakom z ocenami (12.6) pri r, ki je za 1 večji. Na osnovi indukcije torej sklepamo, da velja ocena (12.5).
Preden preidemo na izpeljavo ocene za R pri poljubni (2p+l)-diagonalni matriki, si pripravimo potrebne pripomočke.
13. Pomožni izrek
Pri danem naravnem številu p konstruirajmo pravokotno matriko B, ki ima p+1 vrstic in 2p stolpcev po pravilu:
bi,2p = * '  i=1'2'""P+1                                  (13.1)
bp+l,k = l   ' k=1'2"-"2p                                    (13.2)
bik=bi+l,k+l +bl,k+l                                         C13-3) za k=2p-l,...,l  in  i=l,2,...,p.
S temi predpisi je matrika B natanko določena. Ima naslednje lastnosti:
(i)     b., > 1 , i=l,...,p , k=l,...,2p-l       (13.4)
(ii)   blk > bik , k=l,...,2p , i»2,»..,p+I    (13.5)
(iii)   blk > b: k+1 , k=l,...,2p-l                                (13.6)
(iv)    max b.. = b,,                                                               (13.7)
i,k  lk   n
(v)     b.. = 22P"k - 2P-k+i_1 + 1 -lk
- (p-k-2)2p"k-X + <i-k-3)21_k~2      (13.8} za 1=2,3,...,p  in  k=l,2,...,i-l
b<v = 22P"k - 2p-k+i"1 - (P-k-2)2p-k_1   (13.9) za i=l,2,...,p  in k=i,i+l,...,p
bik = 22p_k - 2P"k+i"1 + 1                                  (13.10)
za i=2,3,...,p in k=p+l,...,p+i-l
- 67 -
.   = 22p"k                                                             (13.11)
za i=l,2,...,p  in k=p+i,...,2p
Dokaz.
(i) Ocena (13.4) sledi neposredno iz definicije elementov matrike B (13.1) - (13.3), saj je zaradi (13.3) b,, vedno
IK
vsota dveh pozitivnih celih števil.
(ii) Pri dokazovanju neenačbe (13.5) ločimo dva primera:
a)  k > p + i - 1                                                        (13.12)
Tedaj   sledi  iz   (13.3),  da  je
blk M bik :! b2,k+l    ' bl,k+l    ' bi+l,k+l + bl,k+l b2,k+l  ~ bi+l,k+l
b2p-k+l,2p       b2p-k+i,2p       L " 1       °
Pri pogoju   (13.12)   je namreč
2p-k+i<p+l
in zato smemo uporabiti definicijo (13.1). Torej pri pogoju (13.12) je
bik - bik
¦¦¦
b)  k < p + i - 1                                                        (13.12)
V tem primeru pa na osnovi (13.3) velja: blk " bik = b2,k+l " bi+l,k+l
bp-i+2,p+k-i+l " bp+l,p+k-i+l bp-i+2,p+k-i+l  l >   °
saj je sedaj
p+k-i+1 < 2p
in moremo uporabiti oceno (13.4) .
Pri pogoju (13.12) velja torej
b„ » b.,
Ik   ik
- 68 -
Neenačba (13.5) je torej dokazana.
(iii) Veljavnost neenačbe (13.6) sledi neposredno iz (13.3) in (13.4) ali (13.1) :
blk = b2,k+l + bl,k+l >  bl,k+l
(iv) Enostavno se je prepričati, da je maksimalni element matrike B ravno b.,. Iz (13.5) in (13.6) sledi
max b.. = max b . = b. . i,k  lk   k   1K   1X
(v) Nekoliko več računanja je pri izpeljavi eksplicitnih formul za elemente matrike B. Ločiti je treba štiri trikotne dele matrike B.
V vseh štirih primerih bomo uporabljali formulo, ki sledi iz aditivne lastnosti (13.3):
bik = bi+l,k+l + bl,k+l =
= bi+2,k+2 + b2,k+2 + 2bl,k+l
= bi+3,k+3 + b3,k+3 + 2b2,k+3 + 4bl,k+3 =
=bi+r/k+r +V 2Sbr-s,k+r                                 '  <13-i3)
s=0
V tej formuli bomo vzeli čimvečj i r, to se pravi, da bo bodisi i+r = p+1  in k+r < 2p, bodisi k+r = 2p in i+r < < p+1.
Oglejmo si sedaj elemente matrike B v Štirih trikotnikih,
a)      i=l,2,...,p ,  k=p+i,...,2p
V tem primeru je
k > p + i
V enačbi (13.13) smemo torej vzeti r = 2p-k, saj je i+r =
= 2p-k+i < p. Pri tem upoštevajmo definicijo (13.1). Tako do-
bimo                                          2p-k-l   fi
bik  =  b2p-k+i,2p +     sJrQ     2     b2p-k-s,2p
- 69 -
2p-k-l       2  v = 1 +   L         2s = 2^p K                                                (13.14)
s = 0
S tem je dokazana formula (13.11).
b)       i=2,3,...,p ,  k=p+l,...,p+i-l
V tem primeru je
p < k < p + i                                                                    (13.15)
V formuli (13.13) moremo sedaj vzeti r = p-i+1, saj je
k+r = p+k-i+1 < 2p+l. Pri tem upoštevajmo definicijo (13.2).
Tako dobimo
p_i s b.1=b,,  ,, .,,+ E 2 b  .  ,,  ,. . ,, = lk   p+1,p+k-i+l    n    p-i-s+1,p+k~i+l
s—u
p-i
- 1 + t     2S b  .  .,  .v . ..                                  (13.16)
s=0    p-i-s+l,p+k-i+l
Ker je sedaj na osnovi neenačbe (13.15)
(p+k-i+1) - (p-i-s+1) ¦ k+s > k > p
moremo v (13.16) uporabiti formulo (13.14) in zato je
= 2P-k+i-l p-i-s+1,p+k-i+1
Tako dobimo iz (13.16)
*
b.. = 1 + *Z    2s.2P"k+i-1 = 22P"k - 2p-k+i_1 + 1 (13.17)
S=0
S tem smo dokazali formulo (13.10).
c)       i=l,2,— ,p ,  k=i,i+l,— ,p
Sedaj je
i < k < p                                                                             (13.18)
Spet uporabimo formulo (13.13) z r = p-i+1, pri tem pa razdelimo vsoto na dva dela:
p-k-1
bik = X +  Sn  2 Vi-s+1,p+k-i+1 + s=0
p-i  s + s=p-k 2  Vi-s+1,p+k-i+1
- 70 -
Prva vsota je pri k = p enaka nič, kot je navadno pri tem zapisu. V prvi vsoti velja zaradi (13.18)
p+k-i+1 > p+1 > p in
(p+k-i+1) - (p-i-s+1) = k+s < p-1 < p
Zato moremo v prvi vsoti uporabiti formulo (13.17). V drugi vsoti pa velja
(p+k-i+1) - (p-i-s+1) = k+s > p
Zato moremo uporabiti formulo (13.14). Tako dobimo
b.v = 1 + PTX 2s(2P-k+i"1 - 2P-k_s+1 + 1) +
s=p-k = 22p-k _ 2p-k+i-l _ (p-k-2)2p-k-1                        (13.19)
S tem je dokazana formula (13.9).
Končno si oglejmo še zadnji trikotnik. d)      i=2,3,...,p  /  k=l,2,...,i-1 Sedaj pa je
k < i in spet uporabimo formulo (13.13) z r = p-i+1:
p-i
s=0
i   = 1 +  V  2  b ik     ."\         p-i-s+1, p+k-i+1
(13.20)
Ker sedaj velja
(p+k-i+1) - (p-i-s+1) = k+s g k > 0 in
p+k-i+1 < p+1 < p
moremo v (13.20) uporabiti formulo (13.19). Tako dobimo
-¦71 -
k   -i    r1  os /->P-k+:i-~l   -p-k-s-1   , . , , v -,i-k-2, biJc = 1 +  L  2 {2^       -2^       - (i-k-3)2     )
s=0 = 22p-k _ 2p-k+i-l + 1 m   (p_k_2)2P-k-l +
+ (i-k-3)21_k_2
Tako je dokazana tudi formula (13.8) in s tem ves pomožni izrek.
14. Ocena za R pri pasovni matriki
Izrek.   Če  je  A ne s ing ulama      (2p+l) -diagonalna matrika in  5e  izvajamo  na  njej  Gaussovo   eliminacijo  z   delnim pivotiranjem^   velja pri   eksaktni  aritmetiki
R < 22p~I - (p-l)2p-2                                                 (14.1)
Ocena  je   stroga,
Dokaz.   Izrek bomo dokazali z indukcijo. Na vsakem koraku pride v poštev za eliminacijo samo p+1 vrstic matrike. Vzemimo situacijo na r-tera koraku. Napišimo samo tiste elemente matrike A    (A   = A) , ki nastopijo pri izračunu ma-trike A(r+1):
arr       ar,r+l     '•* ar,r+2p-l       U ar+l,r    ar+l,r+l   """ ar+l,r+2p-l     u
a(r)      a(r)                           a(r)                                0
r+p-l,r   r+p-l,r+l "*'  r+p-l,r+2p-l
Cr)       (r)                               (r)                                   (r)
r+p,r     r+p,r+l   —  r+p,r+2p-l      r+p,r+2p
Pri tem so elementi zadnje vrstice še nespremenjeni elementi prvotne matrike.
ar+p,k " ar+p,k  '  k=r.....r+2p
- 72 -
Vzemimo, da veljajo ocene (r)
r+
t-i.r+k-ll = bik ' i=1'""P+1 ' ^=1/---/2p  (14.2)
lar+p,r+2p' =
kjer so b., elementi matrike B, ki je bila definirana v prejšnjem razdelku. Pri r = 1 je situacija taka, da tem pogojem prav gotovo ustreza, saj je b., > 1.
Ugotovili bomo, da dobimo po enem koraku eliminacije analogno situacijo z enakimi ocenami.
Pri delnem pivotiranju si ogledamo elemente v r-tem stolpcu na glavni diagonali in pod njo ter poiščemo tistega, ki ima največjo absolutno vrednost. Če je takih več, je vseeno, katerega vzamemo.
Naj bo v našem primeru pivot v (r+j)-ti vrstici, kjer je j neko število med 0 in p. Velja naj torej
lar+j,ri ^ iaril,rl  <  «^.....P                             C14'3)
Tedaj zamenjamo r-to vrstico z (r+j)-to in elementi zgornje trikotne matrike v r-ti vrstici so:
ur,r+k =arij,r+k •  k=0,l,...,2p                                 (14.4)
Nato izvedemo eliminacijo po formulah
a(r) (r+1)   =  (r)    _ r+i,r                                            , 4 5)
ar+i,r+k  ar+i,r+k   urr   r,r+k                             lH,:'
za i=l,2,...,p, i ^ j  in k=l,2,...,2p
in posebej
aCr) .(r+1)   _  (ri     rr                          .      _    ,, fi.
ar+j,r+k - ar,r+k  II^T Ur,r+k '  k-l'--*'2P   t14-6)
Če je j = 0, ta enačba ni potrebna. Vsi drugi elementi ostanejo nespremenjeni in velja torej tudi
ar+p+l,r+k = ar+p+l,r+k  '. k=1'""'2p+1
Ocenimo sedaj absolutne vrednosti novih elementov.
- 73  -
Najprej   dobimo  iz    (14.4)    in   (14.2)    pri  k=l,2,...,2p-l     oceno
lur,r+ki   L &j+1,k+l                                            U4'7>
in   iz   (14.5),    (14.2),    (14.3)   in   (14.7)
lar+i,r+kl   =   lar+i,r+k'   +   lur,r+kl   =
< b       + b
=  i+l,k+l    j+l,k+l
-
Sedaj pa uporabimo lastnosti (13.5) in (13.3) matrike D in dobimo
lar+i,r+k' = bi+l,k+l + bI,k+l = bik
Posebej pri k = 2p  pa imamo iz (14.5) za  i=l,2,...,p-l , če i ^ j in iz (13.1)
Iarii!r+2P1 ^ iur,r+2pi ž l  " htf2p in pri i = p, kajti, če je j ^  p, je ur/r+2p = 0:
|a(i+1L, ! = [a(f}  AO i < 1 - h    , 1 r+p,r+2p'   l r+p,r+2p' =     P/2p
Torej velja za i=l,2,...,p , i ^ j  in  k=l,2,...,2p ocena
.  I»LLL ,*«¦*-! I ±bik                                             (14-8»
torej analogna ocena kot (14.2) pri  r+1.
To oceno moramo potrditi Še pri i = j. Tedaj pa uporabimo (14.6) in dobimo za k=l,...,2p-l
iaL!r+kl ž !•LL*! * wr,r+ki š
ž bl,k+l + bj+l,k+l - bjk
Pri k = 2p pa imamo
Če je j < p. Če pa je j = p+1, je
'ar+p+l,r+2p' = 'ur,r+2pi = 1 : bp+l,2p
- 74 -
Torej velja ocena (14.8) za vse indekse i=l,...,p+l in
Po enem koraku eliminacije se torej situacija popolnoma ponovi.
Zato velja
R = max |af^ | < max b . = b i,k,r 1K  " i,k 1K   iJ"
Ker pa je iz (13.9)
bxl = 22P-1 - CP-D2P-2 je s tem izrek dokazan.
Pokazati moramo le Še, da je ocena stroga. Konstruirajmo matriko A reda n ¦ 2p+l s predpisom: — 1 /   i=l,... ,n = -1 ,  i-k=l,... ,p
a. . - * ,
n
ik
m
= 1
i=l,p+2,p+3,...,n
Vsi drugi elementi naj bodo enaki nič. Tako matriko lahko dobimo iz (2p+l)-diagonalne matrike, ki zadošča pogojem ja., | g 1 če najprej zamenjamo prvo in (p+l)-to vrstico.
Izkaže se, da elementi zadnjega stolpca matrik A nastajajo po istih pravilih kot smo tvorili elemente matrike B. Velja namreč
, r=2,...,n , i=r,...,r+p
(r)
in    i-r+l,n-r+l
Torej je v tem primeru
ann - bll Kot zgled vzemimo tako matriko pri p = 5, n = 11:
A =
1	0	0	0	0	0	0	0	0	0	1
-1	1	0	0	0	0	0	0	0	0	0
-1	-1	1	0	0	0	0	n	0	0	0
-1	-1	-1	1	0	0	0	0	0	0	0
-1	-1	-1	-1	1	0	G	0	0	0	0
-1	-1	-1	-1	-1	1	0	0	0	0	0
0	-1	-1	-1	-1	-1	I	0	0	0	1
0	0	-1	-1	-1	-1	-1	1	0	0	1
0	0	0	-1	-1	-1	-1	-1	1	0	1
0	0	0	0	-1	-1	-1	-1	-1	1	1
0	0	0	0	0	-1	-1	-1	-1	-1	1
V tem primeru je
tur."
- 75 -
0 0	0	0	0	0	a	0	0	i
1 0	0	0	0	0	0	0	0	1
1	0	0	0	0	0	0	0	2
	1	0	0	0	0	0	0	A
		1	0	0	0	0	0	8
			1	0	0	0	0	16
				1	0 1	0 0 1	C 0 0 1	32 63 124 244 480
Ustrezna matrika B pa je pri p = 5 enaka:
B =
480   244   124 63 32 16 8 4 2 1
464   236   120 61 31 16 8 4 2 1
432   220   112 57 29 15 8 4 2 1
369   188     96 49 25 13 7 4 2 1
245   125     64 33 17  9 5 3 2 1
1       1       11111111
Ugotovili smo torej, da je pri pasovnih matrikah tudi ocena za faktor g znatno boljša od splošne ocene (12.2). Ocena (14.1) je odvisna samo od p, kar je zelo ugodno, saj je pri pasovnih matrikah navadno n znatno večji od p.
Če strnemo vse ugotovitve zadnjih dveh poglavij, moremo trditi, da je Gaussova eliminacijska metoda z delnim pivotira-njem tudi s stališča analize napak zelo priporočljiva za pasovne sisteme linearnih enačb.                                     „
- 76 -  L
LITERATURA
nohte, Z», 1970, Analiza zaokrožitvenih napak pri nume-riČnih metodah linearne algebro, Elaborat za SIIK.
Forsythe, G. and Moler, C.B., 1967, Computer solution of linear algebraic systems. Prentice-Hall, Englewood Cliffs.
Isaacson, E. and Keller B.K., 1966, Analysis of numerical methods. John Wiley.
Wilkinson, J.H., 1961, Error analysis of direct methods of matrix inversion. J. Ass. Comp. Mach. 8, 281 - 330.
Wilkinson, J.H., 1963, Rounding errors in algebraic processes. Her'Majesty's Stationery Office, London.
Wilkinson, J.H., 1965, The algebraic eigenvalue problem. Clarendon Press, Oxford.