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