Metody numeryczne

Układy równa´n liniowych, cz˛e´s´c II

Janusz Szwabi´nski

[e-mail]

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.1/50

Układy równa´n liniowych, cz˛e´s´c II

1. Iteracyjne poprawianie rozwi ˛aza´n
2. Metody iteracyjne rozwi ˛azywania układów równa´n

•

Uwagi wst˛epne

•

Metoda Jacobiego

•

Metoda Gaussa-Seidla

•

Analiza bł˛edów zaokr ˛agle´n

•

Metoda Czebyszewa

•

Nakłady oblicze´n i warunki ich przerwania

3. Układy równa´n z macierzami rzadkimi

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.2/50

Iteracyjne poprawianie rozwi ˛aza´n

Rozwi ˛azanie układu równa´n

A

x = b

dowoln ˛a metod ˛a dokładn ˛a obarczone jest pewnym bł˛edem:

r = b − Ax

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.3/50

Przykład





0, 99 0, 70

0, 70 0, 50





x =





0, 54

0, 36





⇒ ˜x =





0, 80

−0, 36





Arytmetyka zmiennopozycyjna o dwóch miejscach dziesi˛etnych
w mantysie, z zaokr ˛agleniami:

r(˜

x) =





0, 54

0, 36





−





0, 99 0, 70

0, 70 0, 50









0, 80

−0, 36





=





0

0





Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.4/50

Ale dla x

1

= (0, 02; 0, 74)

T

mamy równie˙z

r(x

1

) =





0, 54

0, 36





−





0, 99 0, 70

0, 70 0, 50









0, 02

0, 74





=





0, 54 − 0, 02 − 0, 52
0, 38 − 0, 01 − 0, 37





=





0

0





mimo ˙ze x

1

nie jest rozwi ˛azaniem równania:

k˜x − x

1

k

∞

= 1, 1

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.5/50

Arytmetyka z wi˛eksz ˛a liczb ˛a miejsc dziesi˛etnych w mantysie:

r(˜

x) =





0, 54

0, 36





−





0, 99 0, 70

0, 70 0, 50









0, 80

−0, 36





=





0

0





r(x

1

) =





0, 54

0, 36





−





0, 99 0, 70

0, 70 0, 50









0, 02

0, 74





=





0, 0022

−0, 004





⇒ wektory reszt licz z mo˙zliwie du˙z ˛a dokładno´sci ˛a

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.6/50

•

dla znalezionego metod ˛a dokładn ˛a x oblicz r

•

wyznacz poprawk˛e δx tak ˛a, ˙ze

x + δx = ˜

x, ˜

x − rozwi ˛azanie dokładne

r = b − Ax = A˜x − Ax = A(˜x − x) = Aδx

Je˙zeli dysponujemy rozkładem LU macierzy A, potrzebujemy:

•

n

2

mno˙ze´n

•

n

2

− n dodawa´n

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.7/50

Bł˛edy zaokr ˛agle´n:

⇒ zamiast δx znale´zli´smy poprawk˛e δx + δ(δx)

⇒ “musimy” liczy´c dalej

Algorytm:

1. rozwi ˛a˙z Ax

(1)

= b

stosuj ˛ac rozkład LU macierzy A

2. oblicz r

(1)

= b − Ax

(1)

(w podwójnej precyzji)

3. przerwij obliczenia, je´sli kr

(1)

k

∞

≤ kAx

(1)

k

∞

u

(lub

kr

(1)

k

∞

≤ kbk

∞

u

). Je˙zeli nie , to . . .

4. oblicz δx

(1)

i wyznacz x

(2)

= x

(1)

+ δx

(1)

5. oblicz r

(2)

= b − Ax

(2)

i przejd´z do punktu 3

⇒ wektor reszt rozwi ˛azania rz˛edu ukbk

∞

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.8/50

Metody iteracyjne

•

wybierz dowolny wektor startowy x

(0)

•

stopniowo ulepszaj ten wektor a˙z do uzyskania dostatecznie
dokładnego rozwi ˛azania interesuj ˛acego Ci˛e układu równa´n

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.9/50

Uwagi wst˛epne

Definicja Promieniem spektralnym ρ(A) macierzy A
nazywamy liczb˛e

ρ(A) = max

i

=1,...,n

|λ

i

|,

przy czym λ

i

s ˛a tutaj warto´sciami własnymi macierzy A.

Zachodzi

|λ

i

| ≤ kAk

p

⇒ ρ(A) ≤ kAk

p

, p = 1, 2, ∞, E

Lemat Dla ka˙zdej liczby dodatniej  > 0 istnieje taka
indukowana norma k.k

p

macierzy A, ˙ze

kAk

p

≤ ρ(A) + 

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.10/50

Twierdzenie Dla ka˙zdego rzeczywistego wektora x ci ˛ag
wektorów Ax, A

2

x

, . . . jest zbie˙zny do zera wtedy i tylko wtedy,

gdy ρ(A) < 1.

Dla dowolnego wektora x

(0)

definiujemy ci ˛ag

x

(i+1)

= Mx

(i)

+ w, i = 0, 1, . . . ,

M

- pewna macierz kwadratowa, w - wektor

Twierdzenie Powy˙zszy ci ˛ag przy dowolnym wektorze x

(0)

jest

zbie˙zny do jedynego punktu granicznego wtedy i tylko wtedy,
gdy

ρ(M) < 1

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.11/50

Lemat Je˙zeli norma macierzy kwadratowej M spełnia warunek

kMk

p

< 1,

to macierz I + M jest nieosobliwa.

⇒ ρ(M) < 1 → x = Mx + w ma rozwi ˛azanie jednoznaczne

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.12/50

Metody iteracyjne - sposób konstrukcji:
dla układu Ax = b dobierz macierz M tak, aby:

•

ρ(M) < 1

, tzn. poni˙zszy ci ˛ag był zbie˙zny:

x

(i+1)

= Mx

(i)

+ w, i = 0, 1 . . .

•

spełniony był warunek zgodno´sci

˜

x = M˜

x + w, ˜

x

- dokładne rozwi ˛azanie

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.13/50

Teoretycznie wystarczy

•

wzi ˛a´c dowoln ˛a macierz M tak ˛a, ˙ze ρ(M) < 1

•

wyliczy´c w ze wzoru

w = (I − M)A

−1

b

jednak wymagałoby to wyliczenia macierzy A

−1

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.14/50

w = Nb

(N - pewna macierz kwadratowa)

Z warunku zgodno´sci

˜

x = M˜

x + w ⇒ (A

−1

− N − MA

−1

)b = 0 ⇒ M = I − NA

St ˛ad

x

(i+1)

= (I − NA)x

(i)

+ Nb

⇒ rozwi ˛azanie istnieje, je˙zeli tylko

ρ(I − NA) < 1

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.15/50

Jak testowa´c efektywno´s´c?

•

ilo´s´c niezb˛ednych działa´n

•

potrzebna pami˛e´c

•

szybko´s´c zmian wektora bł˛edu (do zera!)

e

(i)

= x

(i)

− ˜x

Uwaga!

•

osi ˛agni˛ecie zadowalaj ˛acej dokładno´sci w rozs ˛adnym czasie
nie zawsze bywa mo˙zliwe

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.16/50

Przykład

M

=













1
2

1

1
2

1

1
2

...
... 1

1
2













, w =
















−

1
2

−

1
2

...

−

1
2

1
2
















⇒ ˜x =
















1

1

...

1

1
















ρ(M) =

1
2

⇒ dla dowolnego x

(0)

metoda iteracyjna jest zbie˙zna,

a mimo to dla x

(0)

= 0

:

ke

(0)

k

∞

= 1, ke

(1)

k

∞

= 3/2, ke

(2)

k

∞

= 9/4, . . .

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.17/50

Bł˛edy zaokr ˛agle´n

⇒ w skrajnym mo˙zemy otrzyma´c

x

(i+1)

= x

(0)

⇒ numeryczne rozwi ˛azanie iteracyjne nie zawsze mo˙zliwe

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.18/50

Metoda Jacobiego

Rozwa˙zmy układ

A

x = b

A

= L + D + U

L

-

macierz poddiagonalna

D

-

macierz diagonalna

U

-

macierz naddiagonalna

Przykład







1 2 3

4 5 6

7 8 9







=







0 0 0

4 0 0

7 8 0







+







1 0 0

0 5 0

0 0 9







+







0 2 3

0 0 6

0 0 0







Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.19/50

x

(i+1)

= (I − NA)x

(i)

+ Nb

Niech

N

= D

−1

Wówczas

M

J

= I − NA = I − D

−1

A

= I − D

−1

(L + D + U) = −D

−1

(L + U)

Wzór Jacobiego

D

x

(i+1)

= −(L + U)x

(i)

+ b, i = 0, 1, 2, . . .

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.20/50

Główna przek ˛atna zawiera zera

⇒ metoda nie jest niezawodna

⇒ zmie´n kolejno´s´c równa´n w układzie Ax = b

W tym celu

1. spo´sród kolumn z elementem zerowym na diagonali

wybierz t˛e z najwi˛eksz ˛a liczb ˛a zer;

2. w kolumnie tej wybierz element o najwi˛ekszym module;

tak przestaw wiersze, aby znalazł si˛e on na głównej
przek ˛atnej; pomi´n ten wiersz w dalszych rozwa˙zaniach;
powró´c do punktu 1

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.21/50

Przykład










0 0 1 2

2 1 0 2

7 3 0 1

0 5 0 0










⇒










7 3 0 1

2 1 0 2

0 0 1 2

0 5 0 0










⇒










7 3 0 1

0 5 0 0

0 0 1 2

2 1 0 2










Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.22/50

Uwaga:

•

zamiana wierszy gwarantuje istnienie macierzy D

−1

•

spełnienie warunku zbie˙zno´sci

ρ(−D

−1

(L + U)) < 1

nie jest gwarantowane!

Metoda na pewno zbie˙zna, je´sli macierz A jest

•

silnie diagonalnie dominuj ˛aca

•

silnie diagonalnie dominuj ˛aca kolumnowo

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.23/50

Metoda Gaussa–Seidla

A

= L + D + U

N

= (D + L)

−1

⇒ M

GS

= −(D + L)

−1

U

St ˛ad

D

x

(i+1)

= −Lx

(i+1)

− Ux

(i)

+ b, i = 0, 1, 2, . . .

•

przy obliczaniu x

(i+1)
1

po prawej stronie nie wyst ˛api ˙zadna

współrz˛edna wektora x

(i+1)

•

przy obliczaniu x

(i+1)
2

prawa strona równo´sci b˛edzie

zale˙zała tylko od x

(i+1)
1

itd.

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.24/50

Metoda nie jest niezawodna

⇒ w razie konieczno´sci przestaw wiersze
Warunek zbie˙zno´sci

ρ(M

GS

) = ρ(−(D + L)

−1

U

) < 1

gwarantowany, je´sli macierz A jest:

•

symetryczna, dodatnio okre´slona;

•

silnie diagonalnie dominuj ˛aca;

•

silnie diagonalnie dominuj ˛aca kolumnowo

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.25/50

Analiza bł˛edów zaokr ˛agle´n

Niech

δ

(i)

- bł ˛ad zaokr ˛agle´n w iteracji i

⇒ w ka˙zdej iteracji zamiast Mx

(i)

+ w

obliczamy

M

x

(i)

+ w + δ

(i)

St ˛ad

x

(i+1)

= M

i

+1

x

(0)

+M

i

w+. . .+w+δ

(i)

+Mδ

(i−1)

+. . .+M

i

δ

(0)

Ł ˛aczny bł ˛ad zaokr ˛agle´n wynosi

˜

x

(i+1)

− x

(i+1)

= δ

(i)

+ Mδ

(i−1)

+ . . . + M

i

δ

(0)

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.26/50

Je´sli algorytm iteracyjny jest zbie˙zny i indeks iteracji jest
dostatecznie du˙zy, mo˙zemy przyj ˛a´c

1
2

k˜xk < kx

(j)

k < 2k˜xk

St ˛ad (dla ˜x 6= 0)

k˜

x

(i+1)

− x

(i+1)

k

kx

(i+1)

k

≤

2

k˜

x

k

(kδ

(i)

k + kMk · kδ

(i−1)

k + . . . + kMk

i

· kδ

(0)

k)

≤

2κ

k˜

x

k

(1 + kMk + . . . + kMk

i

)

kδ

(j)

k < κ, j = 0, 1, 2, . . . , i

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.27/50

Je´sli kMk < 1, to

k˜x

(i+1)

− x

(i+1)

k

kx

(i+1)

k

<

1

1 − kMk

2κ

k˜xk

Je´sli macierz układu jest silnie diagonalnie dominuj ˛aca:

k˜x

(i+1)

− x

(i+1)

k

∞

kx

(i+1)

k

∞

≤

1

1 − kM

GS

k

∞

12α

1 − α

α = O(2n

2

)kDk

∞

kD

−1

k

∞

⇒ dokładniej ni˙z w eliminacji Gaussa, je´sli

kDk

∞

kD

−1

k

∞

 K

∞

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.28/50

Metoda Czebyszewa

Niech

A

- macierz symetryczna i dodatnio okre´slona

Chcemy wybra´c macierz N tak, aby spełniony był warunek

ρ(I − NA) < 1

tzn. aby zbie˙zno´s´c rodziny iteracyjnej

x

(i+1)

= (I − NA)x

(i)

+ Nb

do rozwi ˛azania układu Ax = b była gwarantowana

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.29/50

Załó˙zmy, ˙ze N

s

jest wielomianem macierzowym W (A) stopnia

(s − 1)

⇒ M

s

jest wielomianem stopnia s postaci

P

s

(t) = 1 − W (t)t (dla t = A)

A

jest symetryczna i ma rzeczywiste, dodatnie warto´sci własne

a

1

, . . . , a

n

⇒ warto´sci własne macierzy M

s

spełniaj ˛a warunek

m

i

= P

s

(a

i

), i = 1, . . . , n

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.30/50

Niech

α ≤ a

1

< . . . < a

n

≤ β

Je´sli zachodzi

|P

s

(t)| < 1, t ∈ hα, βi

to

ρ(M

s

) < 1

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.31/50

Szukamy wielomianu W (t) stopnia (s − 1) takiego, aby
wyra˙zenie

max

t

∈hα,βi

|1 − W (t)t|

było najmniejsze z mo˙zliwych

⇒

P

s

(t) =

T

s



2t−(β−α)

β

−α



T

s



−

β

+α

β

−α



T

s

(x) = cos(s arccos x)

(T

s

- wielomian Czebyszewa)

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.32/50

Przykład s = 1:

P

1

(t) =

2

β + α

t, M

1

= I −

2

β + α

A

, N

1

=

2

β + α

I

,

oraz

ρ(M

1

) ≤

β − α
β + α

< 1

⇒ mo˙zemy obliczy´c macierze M

s

i N

s

, ale . . .

⇒ metoda nieekonomiczna (wyznaczanie kolejnych pot˛eg

macierzy)

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.33/50

Oznaczmy przez y

(1)

, . . . , y

(s)

wektory x

(i+1)

, które otrzymamy

stosuj ˛ac wielomiany stopnia 1, 2, . . . , s (k = 1, 2, . . . , s − 1):

y

(0)

= x

(0)

, y

(1)

= x

(i)

−

2

β + α

(Ax

(i)

− b)

y

(k+1)

= y

(k)

+ω

k

ω

k

−1

(y

(k)

−y

(k−1)

)−

2

β + α

(1+ω

k

ω

k

−1

)−(Ay

(k)

−b)

ω

0

=

β − α
β + α

, ω

k

+1

=

1

2

β

+α

β

−α

− ω

k

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.34/50

Rozwi ˛azanie układu Ax = b (algorytm):

1. dla i = 0 kładziemy x

(−1)

= 0

oraz obliczamy

ω

0

=

β − α
β + α

, c =

2

β + α

, L = 2

β + α
β − α

2. dla k = 0 kładziemy x

(i)

= x

0

, oraz ω

i

−1

= 0

i ω

i

= ω

0

,

3. obliczamy

x

(i+1)

= x

(i)

+ ω

i

ω

i

−1

(x

(i)

− x

(i−1)

) − c(1 + ω

i

ω

i

−1

)

− (Ax

(i)

− b)

ω

i

+1

=

1

L − ω

i

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.35/50

4. zwi˛ekszamy k i i o jeden. Je´sli k < s to wracamy do kroku

3, je´sli k ≥ s, przyjmujemy x

0

= x

(i)

i wracamy do kroku 2

Twierdzenie Je˙zeli A jest macierz ˛a symetryczn ˛a dodatnio
okre´slon ˛a, której warto´sci własne le˙z ˛a w przedziale hα, βi
(0 < α < β), to dla dowolnego wektora pocz ˛atkowego x

(0)

ci ˛ag

x

(1)

, x

(2)

, . . . generowany przez algorytm Czebyszewa przy braku

bł˛edów zaokr ˛agle´n d ˛a˙zy do rozwi ˛azania równania Ax = b.

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.36/50

Dowód Przyjrzyjmy si˛e najpierw wektorom, dla których
nast˛epuje powrót do kroku 2:

x

((k+1)s)

= M

s

x

(ks)

+ N

s

b

Macierze M

s

i N

s

spełniaj ˛a warunek zgodno´sci, wi˛ec

˜

x = M

s

˜

x + N

s

b

Odejmuj ˛ac powy˙zsze równania stronami otrzymamy

e

((k+1)s)

= M

s

e

(ks)

gdzie e = x − ˜x

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.37/50

St ˛ad

e

(ks)

= M

k
s

e

(0)

Niech teraz i = ks + p dla 1 ≤ p ≤ s. Zachodzi

x

(i)

= M

p

x

(ks)

+ N

p

b

czyli

e

(i)

= M

p

e

(ks)

= M

p

M

k
s

e

(0)

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.38/50

Poniewa˙z

kM

p

k

2

≤ kM

1

k

2

≤

β − α
β + α

oraz

kM

s

k

2

≤ kM

1

k

2

≤

β − α
β + α

wi˛ec ke

(i)

k

2

→ 0

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.39/50

Własno´sci

•

im wi˛eksze s tym lepsza zbie˙zno´s´c

•

w idealnym przypadku najlepiej byłoby wzi ˛a´c s = ∞ (brak
od´swie˙zania)

•

ze wzgl˛edu na bł˛edy zaokr ˛agle´n bierze si˛e s du˙ze, ale
sko´nczone

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.40/50

Bł ˛ad (w ka˙zdej iteracji)

kδ

(i)

k

2

kx

(i)

k

2

≤ 



55 +

η



(8k + 16)



η

- precyzja, z jak ˛a obliczamy Ax

(i)

− b

k ≤ (n + 1)

√

n

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.41/50

Nakłady oblicze´n i warunki ich przerwania

•

około n

2

mno˙ze´n w ka˙zdej iteracji

•

liczba iteracji  n potrzebna do osi ˛agni˛ecia du˙zej
dokładno´sci

⇒ po około n iteracjach nakład oblicze´n porównywalny z

metodami dokładnymi

⇒ w przypadku ogólnym metoda nieefektywna

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.42/50

Przykład





1

3
4

3
4

1





x =





448

448





⇒ x =





256

256





•

eliminacja Gaussa: 6 mno˙ze´n

•

metoda Gaussa–Seidla: po 8 iteracjach (32 mno˙zenia)

kx

(8)

− ˜xk > 0, 1

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.43/50

Testy stopu (∆ - ˙z ˛adana dokładno´s´c)

1. kx

(i+1)

− x

(i)

k < ∆

2.

1

kbk

kAx

(i+1)

− bk < ∆

Je˙zeli norma macierzy A jest mała, to reszta

kAx

(i+1)

− bk = kA(x

(i+1)

− ˜x)k ≤ kAk · kx

(i+1)

− ˜xk

mo˙ze by´c mała, mimo du˙zego odchylenia wektora x

(i+1)

od

rozwi ˛azania dokładnego ˜x

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.44/50

kx

(i+1)

−x

(i)

k = ke

(i+1)

−e

(i)

k = kMe

(i)

−e

(i)

k = k(M−I)e

(i)

k

⇒ mimo du˙zego bł˛edu e

(i)

, x

(i+1)

i x

(i)

mog ˛a si˛e mało ró˙zni´c,

gdy norma macierzy M − I jest mała

kI − Mk ≥ ρ(I − M) = 1 − ρ(M)

⇒ z sytuacj ˛a tak ˛a mamy do czynienia, gdy ρ(M) jest bliskie 1

(wolna zbie˙zno´s´c algorytmu)

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.45/50

Układy równa´n z macierzami rzadkimi

Definicja Macierz A układu Ax = b nazywamy macierz ˛a
rzadk ˛a, je˙zeli w ka˙zdym równaniu (a przynajmniej w wielu z
nich) liczba niewiadomych jest du˙zo mniejsza ni˙z liczba
wszystkich niewiadomych n.

⇒ rezerwowanie n

2

komórek pami˛eci dla macierzy układu jest

bardzo nieekonomiczne

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.46/50

Organizacja pami˛eci:

1. zapami˛etujemy kolumnami niezerowe elementy, np.: a

11

,

a

21

, a

12

, a

22

, a

32

, a

23

, a

33

, a

43

, a

34

, a

44

, oraz w oddzielnych

tablicach numery wierszy, tu: 1, 2, 1, 2, 3, 2, 3, 4, 3, 4, oraz
znaczniki kolumn (ł ˛acznie z nieistniej ˛ac ˛a (n + 1)–sz ˛a), tu:
1,3,6,9,11

2. jak powy˙zej, lecz zamiast zapami˛etywa´c numery wierszy,

zapami˛etujemy tylko pierwszy i ostatni w ka˙zdej kolumnie
oraz dodatkowo słowami bitowymi poło˙zenie niezerowych
elementów, np. dla kolumny a

12

, a

32

, a

43

, a

72

, a

83

nale˙zy

zapami˛eta´c liczby 1 i 8 oraz kod 011001, wskazuj ˛acy
elementy a

32

, a

43

, a

72

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.47/50

3. elementy macierzy zapisujemy w dowolnej kolejno´sci,

doł ˛aczaj ˛ac do nich informacje o poło˙zeniu s ˛asiednich
elementów w ich wierszach i kolumnach lub dodatkowe
informacje, np. poło˙zenie ostatniego elementu w kolumnie

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.48/50

Metody dokładne

•

brak skutecznych metod wyboru elementu podstawowego,
które gwarantowałyby niezawodno´s´c i stabilno´s´c, i nie
powodowały pojawienia si˛e du˙zej liczby nowych
niezerowych elementów. Wyj ˛atki:

•

macierze trójdiagonalne, diagonalnie dominuj ˛ace
kolumnowo

•

macierze wst˛egowe, diagonalnie dominuj ˛ace
kolumnowo

•

macierze wst˛egowe, symetryczne i dodatnio okre´slone

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.49/50

Metody iteracyjne

•

nakład oblicze´n du˙zo mniejszy ni˙z w przypadku ogólnym
⇒ mo˙zliwa du˙za liczba iteracji
⇒ mo˙zliwa zadowalaj ˛aca dokładno´s´c

•

nie trzeba zmienia´c poło˙zenia elementów macierzy A

Metody numeryczne I (C) 2004 Janusz Szwabi´nski – p.50/50