Вычислительные методы алгебры и оценивания. Семушин И.В. - 85 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

5.2 Выбор ведущего элемента
где ε — не которое наперед заданное положительное число. В лаборатор-
ном проекте № 4, описание которого дано ниже, надо взять ε = 10
−3
, если
используется тип real, или ε = 10
−5
, если используется тип extended.
Итак, среди элементов активной подматрицы A
(k)
в соответствии с крите-
рием (5.2) выбирается множество допустимых элементов, а затем среди них
отыскивается элемент, минимизирующий локальное заполнение на текущем
шаге. Для этого используются следующие две стратегии выбора оптималь-
ного ведущего элемента.
Стратегия I. Локальное заполнение на (k + 1)-м шаге метода Гаусса
будет минимальным, если в качестве главного (ведущего) выбрать элемент
a
(k)
st
на позиции s = α + k, t = β + k, где α и β определяются из формулы
g
(k+1)
αβ
= min
i,j
{e
T
i
G
k+1
e
j
} для всех
a
(k)
i+k,j+k
> ε.
Здесь G
k+1
= B
k
¯
B
T
k
B
k
, где B
k
— матрица, полученная из A
(k)
путем замены
ненулевых элементов единицами, а
¯
B
k
= M −B
k
(M — матрица, состоя щая
из единиц). Согласно стратегии I, в качестве главного берется тот из числа
допустимых элементов активной подматрицы A
(k)
, которому в ма т рице G
k+1
соответствует наименьший элемент.
Стратегия II. Локальное заполнение на k + 1-м шаге метода Гаус са
будет небольшим, если в качестве главного (ведущего) выбрать элемент a
(k)
st
,
на позиции s = α + k, t = β + k, где α и β определяются из формулы
g
(k+1)
αβ
= min
i,j
{e
T
i
ˆ
G
k+1
e
j
} для всех
a
(k)
i+k,j+k
> ε.
Здесь
ˆ
G
k+1
= (B
k
− I
n−k
)M(B
k
− I
n−k
), где матрицы M и B
k
имеют тот
же самый смысл, что и в стратегии I, а I
n−k
обозначает единичную матрицу
размера n−k. Хотя стратегия II не обеспечивает минимальное заполнение на
текущем шаге, она очень прост о реализуется на практике, и ее применение
приводит к сравнительно небольшому числу новых ненулевых элементов .
Использование упакованной формы хранения матрицы A и более слож-
ной процедуры выбора главного элемента требует значительного увеличения
затрат м а шинного време ни, поэтому перенос процедур и функций из лабора-
торного проекта № 1, осуществляющих решение системы линейных алгебра-
ических уравнений, не даст оптимальный по в ремени результат. Это связано
с тем, что поиск (i, j)-гo элемента матрицы A в упакованной форме требует
существе нных затрат машинного вре м ени. Следовательно, при написании
оптимальной по времени счета программы таких действий надо избегать.
85

Страницы