Analiza numeryczna Ćwiczenia nr 4

Słowa kluczowe:

normy macierzy, twierdzenie residualne, NP algorytmów rozwiązywania układów równań lin-iowych

kAxk

1. Niech ⊗ kAk := sup

: x 6= 0

= max kAxk.

kxk

kxk=1

Pokazać, że (⊗) oznacza normę w M (n, m, R). (Jest to norma indukowana) 2. Pokazać, że dla normy operatorowej (⊗) zachodzi: (a) kABk ≤ kAk · kBk,

(b) kAxk ≤ kAk · kxk,

(c) kIk = 1.

3. Wykaż, że

n

X

(a) kAk1 = max

|aij|,

j=1,...,n i=1

p

(b) kAk2 =

λmax(AT A),

n

X

(c) kAk∞ = max

|aij|.

i=1,...,n j=1

4. Wykazać, że

√

((1 + 2)2−t z1, z2 ∈ C

(a) f l(z1z2) = (z1z2)(1 + ε), gdzie |ε| ≤1

2−t

z1, z2 ∈ R

√

n

!

n

(

X

X

(n − i + 2 +

2)2−t

ai, bi ∈ C

(b) f l

aibi

=

aibi(1 + εi), gdzie |εi| ≤1

(n − i + 2)2−t

a

i=1

i=1

i, bi ∈ R

5. Zanalizować w fl algorytm (naturalny) obliczania iloczynu macierzy dwóch macierzy A · B oraz macierzy przez wektor A · x.

6. Udowodnić następujące twierdzenie Tw 1 Algorytm rozwiązywania układu równań Ax = b jest NP ⇔ ∃K > 0 ∃E : (A + E)˜

x = b ,

gdzie kEk ≤1 K2−tkAk , ˜

x - wynik uzyskany w algorytmie.

7. Udowodnić twierdzenie residualne Tw 2 Algorytm rozwiązywania układu równań jest N P ⇔ ∃K > 0 : ∀Ax = b obliczony w f l wektor rsidualny r = f l(A˜

x − b) : spełnia krk ≤ K2−tkAkk˜

xk .

8. Zbadać wpływ zaburzeń danych na rozwiązanie układu równań Ax = b, gdy: (a) zaburzamy tylko prawą stronę układu, (b) zaburzamy jedynie macierz układu.