Обратная подстановка (вещественный вариант): различия между версиями
[непроверенная версия] | [непроверенная версия] |
Frolov (обсуждение | вклад) |
Frolov (обсуждение | вклад) |
||
Строка 44: | Строка 44: | ||
в режиме накопления или без него, плюс деления результатов этих вычислений на диагональные элементы матрицы. | в режиме накопления или без него, плюс деления результатов этих вычислений на диагональные элементы матрицы. | ||
+ | |||
+ | === Описание схемы реализации последовательного алгоритма === | ||
+ | |||
+ | Чтобы понять последовательность исполнения, перепишем формулы метода так: | ||
+ | |||
+ | 1. <math>x_{n} = y_{n}/u_{nn}</math> | ||
+ | |||
+ | Далее для всех <math>i</math> от <math>n-1</math> до <math>1</math> по убыванию выполняются | ||
+ | |||
+ | 2. <math>x_{i} = \left (y_{i} - \sum_{j = i+1}^{n} u_{ij} x_{j} \right ) / u_{ii}</math> | ||
+ | |||
+ | Особо отметим, что вычисления сумм вида <math>y_{i} - \sum_{j = i+1}^{n} u_{ij} x_{j}</math> производят в режиме накопления вычитанием из <math>y_{i}</math> произведений <math>u_{ij} x_{j}</math> для <math>j</math> от <math>n</math> до <math>i + 1</math>, '''c убыванием''' <math>j</math>. Другие порядки выполнения суммирования приводят к резкому ухудшению параллельных свойств алгоритма, хотя, к сожалению, остаются кое-где в литературе и пакетах программ. |
Версия 10:42, 11 сентября 2014
Содержание
1 Описание свойств и структуры алгоритма
1.1 Словесное описание алгоритма
Обратный ход метода Гаусса - решение СЛАУ Ux = y с правой треугольной матрицей U. Матрица U - одна из составляющих матрицы A и получается либо из LU-разложения последней каким-либо из многочисленных способов (например, простое разложение Гаусса, разложение Гаусса с выбором ведущего элемента, компактная схема Гаусса, разложение Холецкого и др.), либо из других разложений. В силу треугольности U решение СЛАУ является одной из модификаций общего метода подстановки и записывается простыми формулами.
1.2 Математическое описание
Исходные данные: правая треугольная матрица U (элементы u_{ij}), вектор правой части y (элементы y_{i}).
Вычисляемые данные: вектор решения x (элементы x_{i}).
Формулы метода:
- \begin{align} x_{n} & = y_{n}/u_{nn} \\ x_{i} & = \left (y_{i} - \sum_{j = i+1}^{n} u_{ij} x_{j} \right ) / u_{ii}, \quad i \in [1, n - 1]. \end{align}
Существует также блочная версия метода, однако в данном описании разобран только точечный метод.
1.3 Вычислительное ядро алгоритма
Вычислительное ядро обратного хода метода Гаусса можно составить из множественных (всего их n) вычислений скалярных произведений строк матрицы U на уже вычисленную часть вектора x:
- \sum_{j = i+1}^{n} u_{ij} x_{j}
в режиме накопления или без него, в зависимости от требований задачи, с их последующим вычитанием из компоненты вектора y и деления на диагональный элемент матрицы U. В отечественных реализациях, даже в последовательных, упомянутый способ представления не используется. Дело в том, что даже в этих реализациях метода вычисление сумм типа
- y_{i} - \sum_{j = i+1}^{n} u_{ij} x_{j}
в которых и встречаются скалярные произведения, ведутся не в порядке «вычислили скалярное произведение, а потом вычли его из элемента», а путём вычитания из элемента покомпонентных произведений, являющихся частями скалярных произведений. Поэтому следует считать вычислительным ядром метода не вычисления скалярных произведений, а вычисления выражений
- y_{i} - \sum_{j = i+1}^{n} u_{ij} x_{j}
в режиме накопления или без него, в зависимости от требований задачи, плюс деления результатов этих вычислений на диагональные элементы матрицы.
1.4 Макроструктура алгоритма
Как уже записано в описании ядра алгоритма, основную часть метода составляют множественные (всего n-1) вычисления сумм
- y_{i} - \sum_{j = i+1}^{n} u_{ij} x_{j}
в режиме накопления или без него, плюс деления результатов этих вычислений на диагональные элементы матрицы.
1.5 Описание схемы реализации последовательного алгоритма
Чтобы понять последовательность исполнения, перепишем формулы метода так:
1. x_{n} = y_{n}/u_{nn}
Далее для всех i от n-1 до 1 по убыванию выполняются
2. x_{i} = \left (y_{i} - \sum_{j = i+1}^{n} u_{ij} x_{j} \right ) / u_{ii}
Особо отметим, что вычисления сумм вида y_{i} - \sum_{j = i+1}^{n} u_{ij} x_{j} производят в режиме накопления вычитанием из y_{i} произведений u_{ij} x_{j} для j от n до i + 1, c убыванием j. Другие порядки выполнения суммирования приводят к резкому ухудшению параллельных свойств алгоритма, хотя, к сожалению, остаются кое-где в литературе и пакетах программ.