Реферат Курсовая Конспект
LU-факторизация. - раздел Философия, Численные методы линейной алгебры Как Было Показано Выше, Основные Вычислительные Затраты В Методе Гаусса Связа...
|
Как было показано выше, основные вычислительные затраты в методе Гаусса связаны с приведением матрицы системы ЛАУ к треугольному виду (вычислительная сложность прямого хода метода Гаусса на порядок превосходит вычислительные затраты на обратный ход). В связи с этим во многих задачах оказывается целесообразным оптимизировать метод Гаусса с целью сохранения данных, полученных на этапе прямого хода. Данная модификация метода Гаусса получила название -факторизация. Само название указывает на то, что суть данного метода состоит в разложении матрицы на два сомножителя и – соответственно нижнюю и верхнюю треугольные матрицы.
Основной теоретический результат, касающийся существования и единственности представления матрицы вида заключается в следующем
Теорема. Если , то существует матрица перестановок такая, что имеет место разложение
, (2.8)
где – нижняя треугольная матрица с отличными от нуля диагональными элементами, – верхняя треугольная матрица с единичной главной диагональю.
Согласно приведенной теореме -факторизация может использоваться для произвольной невырожденной матрицы.
Алгоритм вычисления матриц и во многом повторяет прямой ход метода Гаусса. В частности, из равенства (2.7) следует
. (2.9)
Умножим равенство (2.9) на произведение матриц , в результате имеем:
.
Из полученного равенства следует
. (2.10)
Относительно элементарных треугольных матриц известно, что обратные им матрицы также являются элементарными треугольными, причем существует простая связь между элементами матриц и :
. (2.11)
Также как и в методе Гаусса при использовании алгоритма -факторизации на этапе формирования матриц согласно формуле (2.4) может оказаться , что приводит к потере корректности алгоритма. Подобные ситуации могут быть исключены с помощью описанной выше стратегии выбора ведущего элемента путем перестановки строк (столбцов) матрицы.
Вычислительная сложность алгоритма -факторизации , т.е. по порядку величины не превосходит вычислительные затраты в методе Гаусса.
Алгоритм разложения полезен в тех случаях, когда требуется решить несколько систем ЛАУ с одной и той же матрицей и разными правыми частями. После того как разложение матрицы получено, задача решения системы линейных алгебраических уравнений сводится к последовательному решению двух систем с матрицами треугольного вида: . Таким образом, однократное выполнение разложения позволяет на порядок сократить вычислительные затраты при серийных расчетах (многократных решениях систем ЛАУ с одинаковой матрицей).
– Конец работы –
Эта тема принадлежит разделу:
В М Волков... Численные методы линейной алгебры...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: LU-факторизация.
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов