|
1. Описание вычислительной проблемы
К вычислительным задачам линейной алгебры относят задачи решения систем линейных алгебраических уравнений (СЛАУ) , вычисления обратных матриц , вычисления определителей , задачи вычисления собственных чисел и собственных векторов матриц. Эти задачи имеют очень важное теоретическое и прикладное значение. Трудности решения указанных задач, как правило, связаны с большой размерностью матриц. Чаще всего вычислительные задачи линейной алгебры решают точными и итерационными методами:
Метод называется точным, если в предположении отсутствия ошибок округлений, получается точное решение за конечное число шагов.
Метод называется итерационным, если решение получается в виде предела элементов некоторой последовательности.
В точных методах матрицу исходной системы уравнений эквивалентными преобразованиями приводят к более простой матрице или раскладывают на произведение более простых матриц. Большинство точных методов относятся к так называемым методам исключения. В этих методах, последовательно исключая неизвестные, исходную систему приводят к системе с треугольной или диагональной матрицей. Очевидно, что последние легко разрешимы.
В общем случае СЛАУ имеет вид:
Такие системы разделяются по своим качественным характеристикам на:
Однородные – все свободные члены равны нулю.
Неоднородные – хотя бы один свободный член не равен нулю.
Квадратные – количество переменных равно количеству уравнений.
Прямоугольные – количество переменных не равно количеству уравнений.
Недоопределённые – количество переменных меньше количества уравнений.
Переопределённые – количество переменных больше количества уравнений.
Решением же СЛАУ является нахождение значения количества переменных таких, что при подстановке этих переменных на свои места в систему все уравнения превращаются в тождества. Отсюда следуют, что СЛАУ также можно разделить ещё на несколько категорий:
Совместные имеют хотя бы одно решение.
Несовместные не имеют решений.
Определённые имеют одно решение.
Неопределённые имеют множество решений.
Самым сложным является реализация решения неопределённых СЛАУ, так как результат решения может зависеть от многих факторов:
Способ реализации алгоритма.
Конкретная реализация арифметических и логических операций на вычислительной машине.
Используемое программное обеспечение.
2. Описание изучаемого метода
Метода Гаусса для решения СЛАУ представляет собой метод последовательного исключения переменных, суть которого сводится к приведению расширенной матрицы к верхнетреугольному виду. Причём главная диагональ матрицы А расширенной матрицы Ab заполнена единицами. Такая матрица легко поддаётся нахождению решения СЛАУ, что и происходит на обратном ходе метода.
Как уже было сказано выше, метод Гаусса разделяется на прямой и обратный ход.
На прямом ходе метода Гаусса матрица приводится к верхнетреугольному виду. Получается это в ходе следующего алгоритма:
Проходимся по каждой строке расширенной матрицы
Запоминаем значение элемента на главной диагонали:
(1).
Делим всю строку на это значение:
(2).
Проходимся по строкам ниже текущей.
Проходимся по всем столбцам, чьи номера больше номера текущей строки.
Запоминаем значение (3).
Вычисляем значения каждого элемента расширенной матрицы по формуле:
(4).
Когда матрица приведена к верхнетреугольному виду решением СЛАУ будет считаться проход в обратном порядке в следующем цикле:
Проходимся по каждой строке в обратном порядке.
Проходимся по каждому столбцу в обратном порядке.
Вычисляем значения переменных Xпо формуле:
(5).
В итоге получаем значения всех переменных X.
Данный метод отлично подходит для вычисления матриц малого размера и прост в реализации на вычислительных машинах. Однако, при матрицах большой размерности недостатки его более очевидны. Например, большая ошибка округления при очень большом количестве операций . К тому же метода не подходит для решения СЛАУ с матрицами, в которых существуют нулевые элементы на главной диагонали.
Do'stlaringiz bilan baham: |
