ВУЗ:
Составители:
5 Разреженные формы LU-разложения
Таким образом, разреженная матрица хранится в виде массива указателей
на списки, а каждый список содержит все ненулевые элементы одной строки.
Упакованную форму матрицы A примера 5.1 в этом случае можно схема-
тично изобразить следующим образом.
1 → 1 1.0 → 3 3.0 → 4 −2.0 → nil
2 → 1 1.0 → 5 5.0 → nil
3 → 3 7.0 → 4 2.0 → nil
4 → 2 −3.0 → 6 −1.0 → nil
5 → 1 1.0 → 4 3.0 → nil
6 → 5 2.0 → 6 2.0 → nil
5.2 Выбор ведущего элемента
Способы 1–4 упаковки матриц позволяют компактно хранить матрицу A
коэффициентов системы Ax = f. Однако при использо в а нии метода Гаусса
(или ему подобных) в результа т е модификации элементов матрицы A может
значительно возрасти число ненулевых элементов. С одной стороны, это тре-
бует дополнительной памяти для хранения новых ненулевых э лементов, а с
другой — приводит к возрастанию числа арифметических операций, что вле-
чет накопление ошибок округле ния. В связи с этим обстоятельством были
предложены стратегии выбора главного элемента, позволяющие минимизи-
ровать число новых ненулевых элементов на каждом шаге метода Гаусса.
Назовем локальным заполнением на (k + 1)-м шаге метода Гаусса число
элементов матрицы A, которые были нулевыми после k-го шага и ста ли
ненулевыми после (k + 1)-го шага метода Гаусса. Таким образом , задача за-
ключается в выборе в качестве главного элемента таког о элемента матрицы
A
(k)
, который минимизирует локальное заполнение матрицы A на (k + 1)-м
шаге (как и прежде, A
(k)
— активная подматрица матрицы A). При этом,
чем больш е множество элементов, среди которых выбирается главный, тем
меньше локальное заполнение. Но, с другой стороны, в качестве главного
можно брать только ненулевой элемент. Поэтому вводится понятие допусти-
мого эле мента.
Допустимым элем ентом на (k + 1)-м шаге метода Гаусса называется та-
кой элемент активной подмат рицы A
(k)
, который удовлетворяет неравенству
a
(k)
ij
> ε ,
84
Страницы
- « первая
- ‹ предыдущая
- …
- 82
- 83
- 84
- 85
- 86
- …
- следующая ›
- последняя »
