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

UptoLike

ВУЗ: 

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

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

Рубрика: 

3 Векторно-ориентированные алгоритмы LU-разложения
Для k = 1 до n − 1
Для i = k + 1 до n
l
ik
= a
ik
/a
kk
Для j = k + 1 до n
a
ij
= a
ij
− l
ik
a
kj
Для k = 1 до n − 1
Для s = k + 1 до n
l
sk
= a
sk
/a
kk
Для j = k + 1 до n
Для i = k + 1 до n
a
ij
= a
ij
− l
ik
a
kj
Рис. 3.1. Строчно ориентированная
схема
¯
LU-разложения
Рис. 3.2. Столбцово ориентированная
схема
¯
LU-разложения
Определение 3.1. Триадой называют операцию вида a + αb, где a и
b суть векторы, а α — скаляр
1
.
Определение триады появилось в связи с ис польз о в а нием векторных ком-
пьютеров
2
, требующих, чтобы векторы располага лись в последовательно
адресуемых ячейках памяти. Для алгоритма на рис. 3.1 удобно предполо-
жить, что A хранится по строкам. Соответственно этому, схема на рис. 3.1
названа строчно ориентированной. В ней посредством триад осуществля-
ется модификация (т. е. обновление) строк м а трицы A; на это приходится
основная часть работы в LU-разложении.
Реальные задачи, как правило, требуют выбора главного элемента, и это
еще сильнее уменьша ет скорость. При использовании одной из стратегий
частичного выбора мы должны на первом шаге просмотреть первый стол-
бец в поисках максимального по модулю элемента. Эта стратегия, соответ-
ственно, называется выбором главного элемента по столбцу, и она приво-
дит к перес тановке строк
3
. Как только положение максимального элемента
определено, соответств ующую строку можно переставить с первой (точнее,
текущей ве дущей) строкой или изменить порядок индексации строк. Второй
вариант называют неявной перестановкой строк. Как именно реализуется
стратегия выбора главного элемента, зависит от вашего варианта задания.
Однако во всех вариантах лабораторных работ физическая, т.е. явная пере-
ста новка строк (или столбцов) запрещена и должна быть заменена измене-
нием порядка нумерации строк (или столбцов), т. е. неявной перестановкой.
Это требование соответствует ре а льным пакетам вычислительной линейной
алгебры. т.е. так в реальности всегда и делают. В схеме на рис. 3 .1 возможны
все три стратегии выбора главного элемента (см. подразд. 2.2).
1
В зарубежной литературе триаду называют также saxpy, что обозначает операцию y := ax + y и
заменяет фразу: Single precision (с обычной точностью) ax Plus y.
2
По поводу триады и векторных компьютеров см. подразд. 3.2 и 3.3.
3
Подробнее о стратегиях выбора главного элемента см. подразд. 2.2.
54

Страницы