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

A x = b,

A m {Ab}

{Ab} A

m = 2

a11x1 + a12x2 = b1 a21x1 + a22x2 = b2

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 ∈ Rm A m × m

,

k^Ak

kAk > 0 A 6= 0 kAk = 0 ⇔ A = 0

m × m

k^Ak

kAkα

kxkα kAkβ kxkα = kxkβ

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∆Ak/kAk δ(x) 6 cond(,

cond(A) = kA−¹k kAk

k∆Ak → 0

cond(A) = kA−¹k kAk

t t

O(2−^t)

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

cond(A) = kA−¹k kAk

cond(A) ≥ 1 A A−¹ = E ⇒ 1 = kEk = kA A−¹k > kAk 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)

16i6m

cond(A) = kAk2 kA−¹k2

cond(A)

A = A∗ > 0

i = 1,...,m

Rm

,

.

b

.

ε_i

λ_l

A−1

A−1

ε “

δ

A x = b,

x

aij

a_ij = 0 i > j (i < j)

U

UT U−1

U^TU = 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−σkvke 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

l11y1 = b₁,

l21y1+ l22y2 = b₂,

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

lm−1,1y1+ lm−1,2y2+ ...+ ...+ lm−1,m−1ym−1 = bm−1,

lm1y1+ lm2y2+ ...+ ...+ lm,m₋1ym₋1+ lmmym = b_m.

y1 = b1/l11

y_i

Ux = y

u11x1+ u12x2+ u13x3+ ...+ ...+ u1mxm = y1, u21x2+ u23x3+ ...+ ...+ u2mxm = y2,

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

um−1,m−1xm−1+ ummxm = ym−1

ummxm = ym.

xm = ym/umm

.

Q R QR

A

QRx = b,

Rx = Q^Tb.

m × m

,

A_m

.

lmm umm

A_m

LDU

U

U1 U2

U1U2−1 = D = E ⇒ U1 = U2

D1−1L−1 1L2D2 = E L−1 1L2 = D1D2−1

L1 L2 L−1 1L2 = E ⇒ L1 = L2

D1 = D2

 a11 a12 ... ... ... ... a1m 

a21 a22 ... ... ... ... a2m A... ... ... ... ... ... ...

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

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

 a_m1 a_m2 ... ... ... ... a_mm

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

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

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

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

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

 0 am⁽¹⁾2 ... ... ... ... ...amm⁽¹⁾

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

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

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

 0 _{0 0 ... 1} −a_m1 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) = LkDkLk−1Dk−1 ...L1D1A =

− − ,m

 1 ... a11,k 1 a11,k ... a11,m 1 a¹11,m ^

 ... ... ... k(...k 11),k ... k(k⁽k,m...^k1⁾¹⁾,m1¹ (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_mL_m−1D_m−1 ...L₁D₁A =

− − 1,m

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

0 ... 1 a ⁻ ... a ⁻ a ⁻¹⁾

^ 1 ... a11,k 1 a(kk11,k11),k ... a(kk(k,m11k,m1)1),m111 m(ak(mk111 ^{}^

− − − − ,m

⁼0 ... 0 1 ... a a^(k) − k,m

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

0 ... 0 0 ... 1 a ⁻¹⁾

− ,m

0 ... 0 0 ... 0 1

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

A = LU.

U

cond(U) = cond(L⁻¹A) = cond(D_mL_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)

Li Di

“

a11x1 + a12x2 + ... + a1mxm = b1 a21x1 + a22x2 + ... + a2mxm = b2

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

am1x1 + am2x2 + ... + ammxm = bm

U

x_k

A

ai,n+1 = bi

k 1 m − 1

i k + 1 m + 1

r := aik/akk

j k + 1 m + 1

aij := aij − r akj

j

i

k

xn := an,n+1/an,n

k n − 1 1

xk := ak,n+1 − P akjxj!/akk

n

j=k+1

k

Ux = y

cond(A)

Ux = y U

A

k x_k

|aln|(k) = 6max6 |aij|(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

a25 a35 a45 a55

a15 

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

A12 = Q12A

12 ^ a1111 cosϕ1212 −514131a2121 sinϕ1212 ·524232 · · a1515 cosϕ1212 − a2525 sinϕ12  a sinϕ + a cosϕ · · · a cosϕ + a sinϕ12

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

ϕ12 A12

a11 sinϕ12 + a21 cosϕ12 = 0.

A₁

Q3 Q4

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

A m × m

A_m−1 = Q_m−1 · ... · Q₁ · A = Qe · A,

e

Q Am−1

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

QR A

v =

m A

v1 = (a11,a21,...,am1)T

P₁ m × m

a(1)12mm ^

a(1)

_mm· 

·

a(1)

m − 1 v₂

,

Am−1

Q

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

A = QR Q

R

Ax = b

Rx = Q^Tb

cond(A) = cond(R)

A Q_ij i

j

b(1)ik = bik cosϕij − ajk sinϕij

k = 1,...,m.

(1)

bjk = bik sinϕij + ajk cosϕij

Q A_m−1 = R

QR

A

QR

i k

i

i

R = A_m−1 A = Q R

i

Am−1

Am−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^∗)⁻¹ = L⁻¹ U^∗.

U (L^∗)⁻¹ = L⁻¹ U^∗ = D ⇒ U = D L^∗ ⇒ A = L D L^∗.

,

D = diag(

A

L

k > i

i = 1

a1j = aj1 = l11d11lj1,

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) ... = Snr(0).

S

S

kSk 6 1

kr(n)k → 0 n → ∞

S S

n → ∞ |µk| < 1 ,

.

kr(n)k = kG−1JnG r(0)k 6 kG−1k kJnk kGk 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 1max6k6m |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

kSk → 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 aii =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(x1) = F(x1,x2(n),...,xm(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(_kn+1)

.

.

.

X^k−¹ aikx(in+1) + akkxk(n+1) + X^m aikxni = bk.

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

A0 = (x01,x02)

gradF(x⁰) A0A1

A0A1

(x11,x12) A₁

A0A1

A = A∗ > 0

n

,

n

,

.

.

.

,

x(n+1)

,

i

0 < ω < 1 1 < ω < 2

ω = 1

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

c

v(n)

.

Rm

µ_i S

1 > |µ₁| > |µ₂| > |µ₃| > ... > |µ_m|,

µ_i

, .

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

,

.

, .

,

n

.

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

,

kv⁽ⁿ⁾k 6 ε1,

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

?

,

S = E − τA

0 < τ < 0.4

α β

α β

α β

n = 2

m × m

A∗ A

A

A∗

aji

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

Rm

Rm

Rm

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

16i,j6m

E

S(A) = √trAA_∗

.

|β/α| <