Составители:
85
рассмотренным на третьем шаге первой итерации. Затем переходят
к следующей m + 1-й итерации.
Рассматриваемый процесс построения матрицы R
q
является итера-
ционным и продолжается до тех пор, пока все элементы матрицы
[]
()
1
n
m
nL
−
+
C
не станут равными нулю на некоторой m-й итерации. Число
итераций данного процесса конечно. Размерность получаемой матрицы
R
q
, равная n + L
q
, где L
q
– число добавленных столбцов (строк), может
быть оценена неравенством
n + L
q
≤ n
2
+ n – 1.
Основная идея доказательства сходимости процесса заключается в
следующем.
Пусть число не равных нулю элементов
()
1
ij
c
матрицы
[]
()
1
n
C
равно L.
Тогда справедливо неравенство
2
1
Ln≤−
,
так как число элементов матрицы
[]
()
1
n
C
равно n
2
, а среди элементов
матрицы
[]
()
1
n
S
есть хотя бы один не равный нулю наименьший элемент.
Следовательно, в матрице
[]
()
1
n
C
будет хотя бы один нулевой элемент,
соответствующий этому наименьшему элементу матрицы
[]
()
1
n
S
.
Для каждого из вновь введенных в матрицу
[
]
(
)
m
m
nL
+
R
элементов
()
m
ik
r
,
()
, 1, 2, 3...,
m
kj
r
m
=
соответствующие элементы
() ()
11
и
mm
ik kj
cc
++
матри-
цы
[]
()
1
m
m
nL
+
+
C
всегда равны нулю, так как элементы
()()
11
,
mm
ik kj
ss
++
матри-
цы
[]
()
1
m
m
nL
+
+
S
равны наименьшему положительному числу в i-й строке и
k-м столбце, либо в k-й строке и j-м столбце матрицы
[]
()
1
m
m
nL
+
+
S
, что
обусловлено соответствующим построением матрицы
[]
()
m
m
nL
+
R
(хотя бы
Страницы
- « первая
- ‹ предыдущая
- …
- 83
- 84
- 85
- 86
- 87
- …
- следующая ›
- последняя »
