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

A x = b,

A m {Ab }

{Ab } A

m = 2

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

5x ₁ + 7x ₂ = 12,

7x ₁ + 10x ₂ = 17,

x ₁ = 1 x ₂ = 1 F

t = 2 β = 10 t

F β F

x ₁ = 2. 4 x ₂ = 0 12 16. 8

0 0. 2 1. 4 −1

F x ₁ = 2. 4 x ₂ = 0

F

x ∈ R m A m × m

,

k^A k

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

m × m

k^A k

kA kα

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

E

E

Ax = b

∆A

b

A A + ∆A

x ∗

.

, .

(A + ∆A )−¹ − A −¹ = A −¹ A (A + ∆A )−¹ − A −¹ (A + ∆A ) (A + ∆A )−¹ = = A −¹ (A − (A + ∆A )) (A + ∆A )−¹ = −A −¹ ∆A (A + ∆A )−¹ .

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

cond(A ) = kA −¹ k kA k

k∆A k → 0

cond(A ) = kA −¹ k kA k

t t

O (2−^t )

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

cond(A ) = kA −¹ k kA k

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

max d_ii

cond( D D = diag(d_ii )

16i 6m

cond(A ) = kA k2 kA −¹ k2

cond(A )

A = A ∗ > 0

i = 1,...,m

R m

,

.

b

.

ε_i

λ_l

A−1

A −1

ε “

δ

A x = b,

x

a ij

a_ij = 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 ) = det² (U )

1

P_ij

i j

i j P ₂₄ 5 × 5

0 0 0 1 0

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

P =0 0 1 0 0

0 1 0 0 0

P_ij

Q_ij (ϕ )

i j

Q ₂₄ (ϕ ) 5 × 5

₂₄ 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

Q_ij

P m

v ₁ > 0,

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

v ₁ < 0.

,

u = v −σ kv ke P

.

u ₁ u

P

y = αu + βs

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

“

“

,

α = 1. 2. 3

x ₁ + 0. 99 x ₂ = 1. 99,

0. 99 x ₁ + 0. 98x ₂ = 1. 97,

x ₁ = 1 x ₂ = 1

x ₁ = 3 x ₂ = −1. 0203

L Ux = b.

, .

LU

Ly = b

l 11y 1 = b ₁ ,

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

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

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 = b_m .

y 1 = b 1/l 11

y_i

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

,

A_m

.

l mm u mm

A_m

LDU

U

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 

 a_{m 1} a_{m 2} ... ... ... ... a_mm

^  1 a ⁽¹⁾ 1222 ... ... ... ... a 1⁽¹⁾ 2mm ^ 

0 a ⁽¹⁾ ... ... ... ... a ⁽¹⁾

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

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

^ 0 a (1)_m −1, ₂ ... ... ... ... a (1)_{m −} 1,m ^

 0 a m ⁽¹⁾ 2 ... ... ... ... ...a mm ⁽¹⁾

1/a ₁₁ 0 0 ... 0 1 0 0 ... 0

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

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

 0 _{0 0 ... 1} −a_{m 1} 0 0 ... 1

k − −¹⁾

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

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

D_k = diag(1,

L_k

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

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 ¹ 11,m ^ 

 ... ... ... k (... k 11),k ... k (k ⁽ k,m ...^k 1⁾¹⁾ ,m 1¹ (k ... k

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

− − − ₋  0 ... 0 0 m ^{(k )} 1,m ¹ m 

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

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

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

 − − −1,m

m −1

U

U = D_m L_m −1D_m −1 ...L ₁ D ₁ 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

L −¹ = D_m L_m −1D_m −1 ...L ₁ D ₁ A L −¹

A = LU.

U

cond(U) = cond(L ^{− 1} A ) = cond(D_m L_m −1D_m −1 ...L ₁ D ₁ A ) 6

cond(cond(L_i ) cond(A )

=1

m

cond(L_i ) > 1

cond(U ) D

 i , |a (iii )| < 1

cond(

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

cond(D_i ) 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

x_k

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 x_k

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

Q 3 Q 4

A ₄ = Q ₄ · Q ₃ · Q ₂ · Q ₁ A

A m × m

A_{m −} 1 = Q_{m −} 1 · ... · Q ₁ · A = Q e · A,

e

Q A m −1

A = QR Q = Q e−¹ R = A_m −1

QR A

v =

m A

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

P ₁ m × m

a (1)12mm ^ 

a (1)

_mm · 

·

a (1)

m − 1 v ₂

,

A m −1

Q

P_i ^T i = 1,...,m − 1 Q

A = QR Q

R

Ax = b

Rx = Q ^T b

cond(A ) = cond(R )

A Q_ij 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 A_m −1 = R

QR

A

QR

i k

i

i

R = A_{m −} 1 A = Q R

i

A m −1

A m −1

QR

Q_ij

O (2m ³ )

QR

P_i 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 ² )

B

b, n = 1, 2,...

x (n )

x ∗ ⁿ → ∞

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

ε

ⁿ → ∞

B = E

S = E − τA

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

τ A = A ∗ > 0 A 0 < γ ₁ 6 λ_k 6 γ ₂ k =

λ_k S

µ_k = 1 − τλ_k

0 < τ < 2/γ ₂ |µ_k | = |1−τλ_k | < 1

0 < τ < 2/γ ₂ τ = τ ∗

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

τ

γ ₁ < λ < γ ₂ g_λ (τ ) = 1−τλ

τ = τ ∗ |g_λ (τ ∗)| 6 |g_λ (τ )| γ ₁ < λ < γ ₂ 0 < τ <

2/γ ₂ 0 < τ < 1/γ ₂

|g_{γ 2} (τ )| 6 |g_{γ 1} (τ )| τ > 1/γ ₁ |g_{γ 1} (τ )| 6 |g_{γ 2} (τ )|

1/γ ₂ 6 τ 6 1/γ ₁ τ ₀

|g_{γ 2} (τ ₀ )| = |g_{γ 1} (τ ₀ )|, τ ₀

cond(A )

1

kS k → 1 ζ → ∞

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

(n +1)

B = diag(a ₁₁ ,...,a_mm )

= 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

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

.

m = 2 (x ₁ ,x ₂ )

,

I

,

II

x (0)

n := 0

i 1 m

n := n + 1

Ax = b

x ∗

A = A ∗ > 0

.

Φ(x ) = (Ax − b,Ax − b ) x ∈ R^m

x ∗

F (x ) = F (x ₁ ,x ₂ ,...,x_m ).

F (x )

x ₁

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

_x (₁ n +1)

.

x ₂

.

(n + 1)

A = A ∗ > 0

C = 0

a ₁

A ₁ (x (1)₁ ,x (1)₂ )

C

Ax = b

Ax = b A = A^∗ > 0

k

k k n + 1

_x (_k n +1)

.

.

.

X^k −¹ a ik x (in +1) + a kk x k (n +1) + X^m 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 (xⁿ ) α_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 ⁰ ) A 0A 1

A 0A 1

(x 11,x 12) A ₁

A 0A 1

A = A ∗ > 0

n

,

n

,

.

.

.

,

x (n +1)

,

i

0 < ω < 1 1 < ω < 2

ω = 1

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

c

v (n )

.

R m

µ_i S

1 > |µ ₁ | > |µ ₂ | > |µ ₃ | > ... > |µ_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 −¹

b =6 0

A m

λ ϕ 6= 0

A

m det (A − λE ) = 0.

A

ρ (A ) = max|λ_i |

i

A

trA

A

A

A

A

a_jj e_j = (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 −¹ AP

P B = P ∗AP A B

, .

grad

α gradF y

F (x )

x

F (x ) = c

F (x ) = c x ⁰ =

.

max |a ij |

16i,j 6m

E

S (A ) = √trAA _∗

.

|β/α | <