2.1. Lu представление матрицы. Обращение матриц и вычисление определителя.
При приведении матрицы СЛАУ к треугольному виду (вычислительная сложность прямого хода метода Гаусса на порядок превосходит вычислительные затраты на обратный ход) целесообразно оптимизировать метод. Данная модификация метода Гаусса получила название - факторизация. Само название указывает на то, что суть данного метода состоит в разложении матрицы на два сомножителя и – соответственно нижнюю и верхнюю треугольные матрицы.
Основной теоретический результат, касающийся существования и единственности представления матрицы вида заключается в следующем
Теорема. Если , то существует матрица перестановок такая, что имеет место разложение (1), где – нижняя треугольная с отличными от нуля диагональными элементами, - верхняя треугольная с единичной главной диаг-ю.
=>-факторизация может использоваться для произвольной невырожденной матрицы.
Алгоритм вычисления матриц и во многом повторяет прямой ход метода Гаусса. В частности, из равенства следует
(2)
Умножим равенство (2) на произведение матриц , в результате имеем:
.
Из полученного равенства следует (3)
Относительно элементарных треугольных матриц известно, что обратные им матрицы также являются элементарными треугольными, причем:
Как и в методе Гаусса при использовании алгоритма - факторизации на этапе формирования матриц может оказаться => стратегии выбора ведущего элемента путем перестановки строк (столбцов) матрицы.
Вычислительная сложность алгоритма - факторизации , т.е. по порядку величины не превосходит вычислительные затраты в методе Гаусса.
Алгоритм разложения полезен в тех случаях, когда требуется решить несколько систем ЛАУ с одной и той же матрицей и разными правыми частями. После того как разложение матрицы получено, задача решения системы линейных алгебраических уравнений сводится к последовательному решению двух систем с матрицами треугольного вида: . Таким образом, однократное выполнение разложения позволяет на порядок сократить вычислительные затраты при серийных расчетах (многократных решениях систем ЛАУ с одинаковой матрицей).
LU-разложение используется для решения систем линейных уравнений и для обращения матриц. Этот метод является одной из разновидностей метода Гаусса.
- 1.1. Прямые методы решения систем линейных алгебраических уравнений. Метод Гаусса (вычислительная сложность, выбор ведущего элемента).
- 1.2. Понятие об одношаговых и многошаговых методах. Метод Эйлера решения задачи Коши для системы оду первого порядка.
- 2.1. Lu представление матрицы. Обращение матриц и вычисление определителя.
- 2.2. Локальная и глобальная ошибка одношагового метода решения задачи Коши. Задача для погрешности метода, устойчивость и сходимость.
- 3.1. Нормы векторов и матриц. Понятие согласованности и подчиненности матричных норм
- 3.2. Методы Рунге-Кутта. Схема метода четвертого порядка.
- Число обусловленности матрицы системы лау. Оценки вычислительной погрешности при решении систем лау
- Многошаговые методы. Явные и неявные методы. Метод Адамса
- 5.1. Понятие устойчивости численных методов для жестких систем. Метод Гира.
- 5.2. Итерационные методы решения систем лау. Метод простой итерации. Условия сходимости и критерий остановки итераций.
- 6.2. Разностная аппроксимация дифференциальных операторов. Сеточный шаблон. Явные и неявные схемы для нестационарных задач математической физики.
- 7.1. Прямые методы вычисления собственных значений. Преобразования подобия. Метод Данилевского.
- 7.2. Порядок аппроксимации разностной схемы. Оценка порядка аппроксимации разностной схемы с весами для нестационарного уравнения теплопроводности.
- 8.1. Оптимальное значение итерационного параметра. Метод минимальных невязок.
- 8.2. Основные понятия теории разностных схем. Пространство сеточных функций и сеточные нормы.
- 9.1. Итерационные методы решения проблемы собственных значений. Степенной метод.
- 9.2. Спектральный метод исследования устойчивости разностных схем для уравнений с постоянными коэффициентами.
- 10.1. Итерационные методы решения нелинейных уравнений. Метод Ньютона.
- 10.2. Устойчивость и сходимость разностных схем. Оценка погрешности разностного решения.
- 21.1. Спектр собственных значений разностного оператора второй производной.
- 21.2. Разностные аналоги формул Грина и теоремы вложения норм сеточных функций.