Элементы теории алгоритмов - 201 стр.

UptoLike

ВУЗ: 

ЯрГУ | Ярославль

Составители: 

Рубрика: 

§2
D
1
D
m
D =(A, −b)
A
t
−b
t
· λ =
⎛
⎜
⎜
⎝
0
...
0
1
⎞
⎟
⎟
⎠
,
A
t
b
t
· λ =
⎛
⎜
⎜
⎝
0
...
0
−1
⎞
⎟
⎟
⎠
.
λ
1
λ
m
A
t
b
t
· y =
0
−1
.
A = ||a
ij
|| m × n b =[b
1
,...,b
m
]
m
C =max
1≤i≤m
1≤j≤n
|a
ij
|,D=max
1≤i≤m
|b
i
|,C
1
=(mC)
m+1
.
x =(x
1
,...,x
n
)
Ax = b j =1,...,x
n
|x
j
|≤m!C
m−1
D.
[x
j
1
,...,x
j
m
]=B
−1
b.
B = ||b
ts
|| B
−1
=1/det(B) ·||B
st
||
B
st
m − 1 B
|B
st
|≤(m −1)! ·C
m−1
.
det(B) ≥ 1
x
j
t
=1/det(B) ·
m
Σ
s=1
B
st
· b
s
|x
j
t
|≤1/det(B) ·
m
Σ
s=1
|B
st
|·|b
s
|≤
m · (m − 1)! ·C
m−1
· D = m! ·C
m−1
· D.

Страницы