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

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 − A −1 = A −1 A (A + ∆A )−1 − A −1 (A + ∆A ) (A + ∆A )−1 = = A −1 (A − (A + ∆A )) (A + ∆A )−1 = −A −1 ∆A (A + ∆A )−1.

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

cond(A ) = kA −1 k kA k

K∆A k → 0

Cond(A ) = kA −1 k kA k

T t

O (2−t )

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

Cond(A ) = kA −1 k kA k

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

Max dii

Cond( D D = diag(dii )

16i 6m

Cond(A ) = kA k2 kA −1 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 1D 1A =… … … … … … … ,

… … … … … … …

 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 1D 1A =

− − 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

L −1 = Dm Lm −1Dm −1 …L 1D 1A L −1

A = LU.

U

Cond(U) = cond(L −1A ) = cond(Dm Lm −1Dm −1 …L 1D 1A ) 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 1A

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 (1n +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

A ∗ A

A

A ∗

A ji

AA A −1

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

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

A

A B

P B =

P −1AP

P B = P ∗AP 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 ∗

.

|β/α | <


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