Скачать .pdf

Книга: Вычислительные методы линейной алгебры






A x = b,

A m {Ab }


{Ab } A m

{Ab } A

m = 2

a 11x 1 + a 12x 2 = b 1 a 21x 1 + a 22x 2 = b 2

5x 1 + 7x 2 = 12,

7x 1 + 10x 2 = 17,

x 1 = 1 x 2 = 1 F

t = 2 β = 10 t

F β F

x 1 = 2. 4 x 2 = 0 12 16. 8

0 0. 2 1. 4 −1

F x 1 = 2. 4 x 2 = 0

F



x R m A m × m

,

kA k

kA k > 0 A 6= 0 kA k = 0 ⇔ A = 0

m × m

kA k

kA kα

kx kα kA kβ kx kα = kx kβ

E

E

Ax = b

A

b

A A + ∆A

x

.

, .

(A + ∆A )−1 A1 = A1 A (A + ∆A )−1 A1 (A + ∆A ) (A + ∆A )−1 = = A1 (A − (A + ∆A )) (A + ∆A )−1 = −A1 A (A + ∆A )−1 .

δ (x ) 6 cond(A )k∆A k/ kA k δ (x ) 6 cond(,

cond(A ) = kA1 k kA k

k∆A k → 0

cond(A ) = kA1 k kA k

t t

O (2−t )

O (2t/ 2) O (2−t/ 2)

cond(A ) = kA1 k kA k

cond(A ) ≥ 1 A A1 = E ⇒ 1 = kE k = kA A1 k > kA k kA1 k = cond(A ) cond(c A ) = cond(A ) c cond(A B ) 6 cond(A ) cond(B ) cond(A1 ) = cond(A )

max dii

cond( D D = diag(dii )

16i 6m

cond(A ) = kA k2 kA1 k2

cond(A )

A = A> 0

i = 1,...,m

R m

,

.

b

.

εi

λl

A−1

A −1

ε

δ

A x = b,

x


a ij

aij = 0 i > j (i < j )

U

U T U −1

U T U = UU T = E

|det(U )| = 1 1 = det(E ) = det(UU T ) =

det(U ) det(U T ) = det2 (U )

1

Pij

i j

i j P 24 5 × 5

0 0 0 1 0

 0

A

0

A

i

j

A

24  1 0 0 0 0 

P =0 0 1 0 0

0 1 0 0 0

Pij

Qij (ϕ )

i j

Q 24 (ϕ ) 5 × 5

24 1 0 0 0 0 

 0 cosϕ 0 −sinϕ 0

Q (ϕ ) =0 0 1 0 0

0 sinϕ 0 cosϕ 0

0 0 0 0 1

Qij

P m

v 1 > 0,

e = (1, 0,..., 0)T

v 1 < 0.

,

u = vσ kv ke P

.

u 1 u

P

y = αu + βs

Aij aij = 0 i > j + 1(i < j − 1)

,

α = 1. 2. 3

x 1 + 0. 99 x 2 = 1. 99,

0. 99 x 1 + 0. 98x 2 = 1. 97,

x 1 = 1 x 2 = 1

x 1 = 3 x 2 = −1. 0203

A = L U

L U

L Ux = b.

, .

LU

Ly = b

l 11y 1 = b 1 ,

l 21y 1+ l 22y 2 = b 2 ,

... ... ... ... ... ... ...,

l m −1, 1y 1+ l m −1, 2y 2+ ... + ... + l m −1,m −1y m −1 = b m −1,

l m 1y 1+ l m 2y 2+ ... + ... + l m,m 1y m 1+ l mm y m = bm .

y 1 = b 1/l 11

yi

Ux = y

u 11x 1+ u 12x 2+ u 13x 3+ ... + ... + u 1m x m = y 1, u 21x 2+ u 23x 3+ ... + ... + u 2m x m = y 2,

... ... ... ...,

u m −1,m −1x m −1+ u mm x m = y m −1

u mm x m = y m .

x m = y m /u mm

.

Q R QR

A

QRx = b,

Rx = Q T b.

m × m

,

Am

.

l mm u mm

Am

LDU

U

l ii = 1 u ii = 1 D

A = LU

A = LDU

uii = 1

lii = 1

A = L 1D 1U 1 A = L 2D 2U 2

L 1D 1U 1 = L 2D 2U 2

U 1U 2−1 = D 1−1L −1 1L 2D 2

U 1U 2−1

D 1−1L −1 1L 2D 2

U 1 U 2

U 1U 2−1 = D = E U 1 = U 2

D 1−1L −1 1L 2D 2 = E L −1 1L 2 = D 1D 2−1

L 1 L 2 L −1 1L 2 = E L 1 = L 2

D 1 = D 2

 a 11 a 12 ... ... ... ... a 1m 

a 21 a 22 ... ... ... ... a 2m A... ... ... ... ... ... ...

... ... ... ... ... ... ...

=  a m −1, 1 a m −1, 2 ... ... ... ... a m −1,m 

am 1 am 2 ... ... ... ... amm

  1 a (1) 1222 ... ... ... ... a 1(1) 2mm  

0 a (1) ... ... ... ... a (1)

A (1) = L 1 D 1 A =... ... ... ... ... ... ... ,

... ... ... ... ... ... ...

 0 a (1)m −1, 2 ... ... ... ... a (1)m 1,m 

 0 a m (1) 2 ... ... ... ... ...a mm (1)

1/a 11 0 0 ... 0 1 0 0 ... 0

D 1 =  0 1 0 ... 0  L 1 k = 1 −a 21 1 0 A... (k 0 .

... ... ... ... ... ... ... ... ... ...

 0 0 0 ... 1 am 1 0 0 ... 1

k − −1)

1

 ...

0

A (k 1) = L D ...L D A =  0

a (1)12

...

1

0

...

...

0

1

...

...

a (kk −−11),k

a (k −1)

...

...

...

...

...

...

...

...

k a (1)1m 1,m 

... a (k 1)

a (k 1)

 ... 0

...

0

...

0

...

a (mk k −1)

... ...

... ... 

... a (mmk 1)

A (k −1)

Dk

k −1 k −1 1 1   k (kkk +11),k k (k,mk +11) 

0 0 0 a ... ... a ,m

Dk = diag(1,

Lk

... ... ... ... ... ...

0 ... 1 0 ... 0

k   1 ... ... k (mk (kk +11)1),k ... ... 0 

L =.

0 ... a 1 ... 0

... ... ... ... ... ...

0 ... a 0 ... 1

A (k ) = L k D k L k −1D k −1 ...L 1D 1A =

− − ,m

 1 ... a 11,k 1 a 11,k ... a 11,m 1 a 1 11,m  

 ... ... ... k (... k 11),k ... k (k ( k,m ...k 1)1) ,m 11 (k ... k

0 ... 1 a ... a a −1)

− − −  0 ... 0 0 m (k ) 1,m 1 m 

= 0 ... 0 1 ... a a (k ) − k,m

 ... ... ... ... ... ... ...

0 ... 0 0 ... a a (k )

− − −1,m

m −1

U

U = Dm Lm −1Dm −1 ...L 1 D 1 A =

− − 1,m

... ... ... ... ... ... ...

0 ... 1 a ... a a 1)

  1 ... a 11,k 1 a (kk 11,k 11),k ... a (kk (k,m 11k,m 1)1),m 111 m (a k (mk 111  

− − − − ,m

= 0 ... 0 1 ... a a (k ) k,m

... ... ... ... ... ... ...

0 ... 0 0 ... 1 a 1)

,m

0 ... 0 0 ... 0 1

L1 = Dm Lm −1Dm −1 ...L 1 D 1 A L1

A = LU.

U

cond(U) = cond(L 1 A ) = cond(Dm Lm −1Dm −1 ...L 1 D 1 A ) 6

cond(cond(Li ) cond(A )

=1

m

cond(Li ) > 1

cond(U ) D

i , |a (iii )| < 1

cond(

 |aii , |a (iii )| > 1

cond(Di ) cond(U )

cond(A )

L i D i

a 11x 1 + a 12x 2 + ... + a 1m x m = b 1 a 21x 1 + a 22x 2 + ... + a 2m x m = b 2

..............................

a m 1x 1 + a m 2x 2 + ... + a mm x m = b m

U

xk

A

a i,n +1 = b i

k 1 m − 1

i k + 1 m + 1

r := a ik /a kk

j k + 1 m + 1

a ij := a ij r a kj

j

i

k

x n := a n,n +1/a n,n

k n − 1 1

x k := a k,n +1 − P a kj x j !/a kk

n

j =k +1

k

Ux = y

cond(A )

Ux = y U

A

k xk

|a ln |(k ) = 6max6 |a ij |(k ) k l k n

k i,j m

k n

x

x (1)

kr (1)k 6 ε x (1)

ε

A

A = QR,

Q R

A

a 25 a 35 a 45 a 55

a 15 

12 12  cosϕ 1212 −sinϕ 1212 0 0 0  sinϕ cosϕ 0 0 0

Q (ϕ ) =0 0 1 0 0

0 0 0 1 0

0 0 0 0 1

A 12 = Q 12A

12   a 1111 cosϕ 1212 −514131a 2121 sinϕ 1212 ·524232 · · a 1515 cosϕ 1212 − a 2525 sinϕ 12  a sinϕ + a cosϕ · · · a cosϕ + a sinϕ 12

A =a a · · · a a · · · a a · · ·

ϕ 12 A 12

a 11 sinϕ 12 + a 21 cosϕ 12 = 0.

A 1

Q 3 Q 4

A 4 = Q 4 · Q 3 · Q 2 · Q 1 A

A m × m

Am 1 = Qm 1 · ... · Q 1 · A = Q e · A,

e

Q A m −1

A = QR Q = Q e−1 R = Am −1

QR A

v =

m A

v 1 = (a 11,a 21,...,a m 1)T

P 1 m × m

a (1)12mm 

a (1)

mm · 

·

a (1)

m − 1 v 2

,

A m −1

Q

Pi T i = 1,...,m − 1 Q

A = QR Q

R

Ax = b

Rx = Q T b

cond(A ) = cond(R )

A Qij i

j

b (1)ik = b ik cosϕ ij a jk sinϕ ij

k = 1,...,m.

(1)

b jk = b ik sinϕ ij + a jk cosϕ ij

Q Am −1 = R

QR

A

QR

i k

i

i

R = Am 1 A = Q R

i

A m −1

A m −1

QR

Qij

O (2m 3 )

QR

Pi m × m

A = A

A = L U.

A = L U = A = U L L U = U L U (L ) 1 = L 1 U .

U (L ) 1 = L 1 U = D U = D L A = L D L .

,

D = diag(

A

L

k > i

i = 1

a 1j = a j 1 = l 11d 11l j 1,

LU

LU

QR A

l

QR

x (0) x

A x = b

“ “ x (n )

kx (n ) − x k

O (m 2 )

B

b, n = 1, 2,...

x (n )

x n → ∞

x (n )

τn = τ

τn n = 1, 2,... B

B −1

x (n )

ε

n = n (ε )

.

ε

τn n = 1, 2,...

r (n ) n

τn = τ

r (n ) = Sr (n −1) = S Sr (n −2) ... = S n r (0).

S

S

kS k 6 1

kr (n )k → 0 n → ∞

S S

n → ∞ |µ k | < 1 ,

.

kr (n )k = kG −1J n G r (0)k 6 kG −1k kJ n k kG k kr (0)k → 0 n → ∞.

S

ε

n → ∞

B = E

S = E τA

S max|µk | τ max|µk | k k

τ A = A> 0 A 0 < γ 1 6 λk 6 γ 2 k =

λk S

µk = 1 − τλk

0 < τ < 2 2 |µk | = |1−τλk | < 1

0 < τ < 2 2 τ = τ

|µ ∗| = 0<τ< min2 2 1max6k 6m |1 − τλ k |

τ

γ 1 < λ < γ 2 gλ (τ ) = 1−τλ

τ = τ ∗ |gλ (τ ∗)| 6 |gλ (τ )| γ 1 < λ < γ 2 0 < τ <

2 2 0 < τ < 1 2

|gγ 2 (τ )| 6 |gγ 1 (τ )| τ > 1 1 |gγ 1 (τ )| 6 |gγ 2 (τ )|

1 2 6 τ 6 1 1 τ 0

|gγ 2 (τ 0 )| = |gγ 1 (τ 0 )|, τ 0

cond(A )

1

kS k → 1 ζ → ∞

aii =6 0 i = 1,...,m

(n +1)

B = diag(a 11 ,...,amm )

= b x (n +1) = (E B −1A )x (n ) + B −1b, A

,

.

x (0)

n := 0

x (1)

Ax = b ε

n

N

n > N

A Ax = b a ii =6 0

(n + 1)

i

+ ...

= b 1

+ ...

+ a 2m x m (n )

= b 2

...................................................

.

m = 2 (x 1 ,x 2 )

,

I

,

II

x (0)

n := 0

i 1 m

n := n + 1

Ax = b

x

A = A> 0

.

Φ(x ) = (Ax b,Ax b ) x Rm

x

F (x ) = F (x 1 ,x 2 ,...,xm ).

F (x )

x 1

ϕ 1(x 1) = F (x 1,x 2(n ),...,x m (n )),

x (1 n +1)

.

x 2

.

(n + 1)

A = A> 0

C = 0

a 1

A 1 (x (1)1 ,x (1)2 )

C

Ax = b

Ax = b A = A > 0

k

k k n + 1

x (k n +1)

.

.

.

Xk 1 a ik x (in +1) + a kk x k (n +1) + Xm a ik x ni = b k .

i =1 i =k +1

A = A> 0

F (x ) x

grad x (n +1)

x (n +1) = x (n ) − α n gradF (x (n )), αn

x (n +1)

gradF (xn ) αn := αn / 2

x (n +1)

αn

αn N

x (n +1)

ε ε

,

,

αn |ϕ (αn )|

ϕ (α n ) = F (x (n +1)) = F (x (n ) − α n gradF (x (n ))).

αn A = A> 0

grad

.

αn

Ax = b A = A > 0

A 0 = (x 01,x 02)

gradF (x 0 ) A 0A 1

A 0A 1

(x 11,x 12) A 1

A 0A 1

A = A> 0

n

,

n

,

.

.

.

,

x (n +1)

,

i

0 < ω < 1 1 < ω < 2

ω = 1

x (n ) = Sx (n −1) + c,

c

ε

kr (n )k = kx (n ) − x k 6 ε

kr (n )k = kx (n ) −x k

x (n ) x

v (n )

.

R m

µi S

1 > |µ 1 | > |µ 2 | > |µ 3 | > ... > |µm |,

µi

, .

kw (n )k = O ( |µ 1|n )

,

.

, .

,

n

.

kx (n ) − x (n −1)k µ 1

,

kv (n ) k 6 ε 1,

α β x (k +1) = S x (k ) + c

?

,

S = E τA

0 < τ < 0. 4

α β

α β

α β

n = 2

m × m

AA

A

A

a ji

AA A1

b =6 0

A m

λ ϕ 6= 0

A

m det (A λE ) = 0.

A

ρ (A ) = max|λi |

i

A

trA

A

A

A

A

ajj ej = (0,..., 0, 1 , 0,..., 0) j |{z}

λ k λ j A λ k =6 λ j

λk ϕk k = 1,...,m

R m

R m

R m

Aψk k = 1,...,m

(ϕkj ) = 0, k =6 j.

A

A B

P B =

P1 AP

P B = PAP A B

, .

grad

α gradF y

F (x )

x

F (x ) = c

F (x ) = c x 0 =

.

max |a ij |

16i,j 6m

E

S (A ) = √trAA

.

|β/α | <