Вычислительные методы линейной алгебры (стр. 3 из 5)

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