Студопедия


Авиадвигателестроения Административное право Административное право Беларусии Алгебра Архитектура Безопасность жизнедеятельности Введение в профессию «психолог» Введение в экономику культуры Высшая математика Геология Геоморфология Гидрология и гидрометрии Гидросистемы и гидромашины История Украины Культурология Культурология Логика Маркетинг Машиностроение Медицинская психология Менеджмент Металлы и сварка Методы и средства измерений электрических величин Мировая экономика Начертательная геометрия Основы экономической теории Охрана труда Пожарная тактика Процессы и структуры мышления Профессиональная психология Психология Психология менеджмента Современные фундаментальные и прикладные исследования в приборостроении Социальная психология Социально-философская проблематика Социология Статистика Теоретические основы информатики Теория автоматического регулирования Теория вероятности Транспортное право Туроператор Уголовное право Уголовный процесс Управление современным производством Физика Физические явления Философия Холодильные установки Экология Экономика История экономики Основы экономики Экономика предприятия Экономическая история Экономическая теория Экономический анализ Развитие экономики ЕС Чрезвычайные ситуации ВКонтакте Одноклассники Мой Мир Фейсбук LiveJournal Instagram

LU-факторизация алгоритмом Краута




Схема Халецкого (LU-факторизация)

Одним из лучших методов решения систем линейных алгебраических уравнений общего вида является метод, основанный на разложении исходной матрицы на произведение треугольных, или метод -факторизации. Алгоритмы этого метода близки к алгоритмам метода Гаусса, хотя вычисления могут производиться в различной последовательности. Главным преимуществом метода -факторизации в сравнении с методом Гаусса является возможность более быстрого получения решений для различных векторов свободных членов, а также для транспонированной системы уравнений.

По числу операций, необходимых для решения конкретной системы, методы Гаусса и -факторизации практически неразличимы. Однако из всех операций решения в методе -разложения почти половина приходится на этап факторизации и следующая половина - на собственно решение двух треугольных систем. В силу этого факта при необходимости решения системы, отличающейся лишь вектором свободных членов, получаем экономию на операциях разложения. Аналогично, когда необходимо решать транспонированную систему после исходной, можно воспользоваться предыдущей факторизацией и лишь сменить порядок решения треугольных систем в силу операции транспонирования.

В методе решения систем линейных уравнений, основанном на факторизации, предполагается, что исходная система (6.12)

может быть представлена в виде

, (6.13)

т.е.

. (6.14)

Причем для определенности полагается, что матрица является нижнетреугольной, а – верхнетреугольной, причем с единичной диагональю.

Забегая несколько вперед, сразу отметим, что определитель треугольной матрицы равен произведению диагональных элементов, а определитель произведения матриц равен произведению их определителей. Откуда следует, что определитель матрицы равен произведению диагональных элементов нижнетреугольной матрицы :

. (6.15)

Ограничившись для наглядности порядком , запишем - и -матрицы

Схема Халецкого. Предполагая возможным разложение (6.14), вводя вспомогательный вектор

(6.16)

и подставив данное выражение в уравнение (6.13), получим

­- (6.17)

две треугольные системы, эквивалентные исходной системе. Поскольку обе системы (6.16) и (6.17) треугольные, их решения достаточно тривиальны, причем в начале решаем систему (6.17) и находим вектор , а затем из (6.16) окончательно находим .

Распишем подробнее алгоритм решения. Записывая систему (6.17) в виде

Для первых компонент вектора можем записать

,

,

.

Обобщая последовательность этих операций, называемых прямой подстановкой или прямым ходом, можем записать

; , (6.18)




при .

Для того чтобы соотношение (6.18) имело смысл, не должны равняться нулю.

Теперь решим систему (6.16) в координатной форме:

,

,

,

,

.

Начиная с последней формулы, запишем выражения для нескольких компонент вектора решений :

,

,

.

Обобщая эту последовательность действий, называемую обратной подстановкой или обратным ходом, запишем

, (6.19)

при .

Число операций, требуемых для выполнения как прямой, так и обратной подстановок, равно примерно , а в сумме для решения вместе с разложением требуется примерно операций.

Изучение соотношений (6.16) и (6.17) показывает, что компоненты используются только для определения и позднее не требуются. Аналогично не нужны после вычисления . Следовательно, при такой системе расчетов векторы и могут быть размещены в одних и тех же ячейках памяти ЭВМ. Коэффициенты треугольных систем – матрицы и , если не хранить единичную диагональ матрицы , могут быть размещены на месте исходной матрицы коэффициентов . Следует также отметить эквивалентность обратных подстановок в схеме Халецкого и в методе Гаусса.

При изложении алгоритмов разложения для наглядности ограничимся порядком системы , что не повлияет на общность рассуждений.

Суть алгоритма Краута. Предполагая, что разложение существует, запишем произведение :

.

Сравнивая компоненты этого произведения с компонентами матрицы , видим, что первый столбец произведения равен первому столбцу матрицы , т.е. , при . Первая строка произведения может быть использована для определения первой строки матрицы . Действительно, т.к.

,

при , получаем

.

Поскольку во втором столбце элементы и известны, можем определить второй столбец матрицы :



,

где . Теперь, т.к. известны и , можно по второй строке произведения определить вторую строку матрицы :

,

при . Далее, чередуя строки и столбцы, можно аналогичным образом найти остальные элементы матриц и .

Чтобы получить общие соотношения, запишем произвольный элемент произведения :

,

где верхний предел суммы учитывает наличие нулевых элементов в матрицах и . Рассмотрим произвольный элемент на или под главной диагональю матрицы , для которого , и заменим индекс на . Учитывая при этом, что , получим

,

откуда

, (6.20)

при и . Аналогичным образом, рассматривая произвольный элемент над главной диагональю, для которого , и используя вместо , находим

,

откуда

, (6.21)

при и .

Эти соотношения для и есть алгоритм разложения на треугольные матрицы – алгоритм Краута. Заметим, что текущие элементы матриц и определяются текущим элементом матрицы и предыдущими элементами матриц и . Отсюда, т.к. нулевые элементы и единичную диагональ матрицы запоминать не нужно, в процессе вычислений матрицы и могут быть записаны на месте матрицы , причем расположена в нижнем треугольнике , а – соответственно в верхнем треугольнике матрицы .

Коротко алгоритм Краута как вариант чередования столбцов и строк можно представить следующей последовательностью действий:

1) положим и перейдем к пункту 3;

2) используя выражение (6.20), рассчитываем -ый столбец матрицы и, если , закончим процедуру разложения;

3) используя выражение (6.21), рассчитываем -ую строку матрицы ;

4) положим и перейдем к пункту 2.

Кроме варианта чередования столбцов и строк, на основе соотношений (6.20) и (6.21) возможны варианты последовательного обхода по строкам либо по столбцам.

Если последовательно обходить ()-произведение по строкам, то можно заметить, что, используя предыдущие соотношения (6.20) для при и (6.21) для при , можно беспрепятственно определить все элементы матриц и . Аналогично можно организовать алгоритм вычисления элементов матриц и , совершая обход по столбцам.

Преимущества этих вариантов алгоритма Краута проявляются при матрицах большого размера.

Известен также вариант алгоритма -факторизации, основанный на приведении исходной матрицы к верхней треугольной форме по Гауссу [1], однако по сравнению с алгоритмом Краута он требует более частого обращения к матрице .





Дата добавления: 2014-02-12; просмотров: 3263; Опубликованный материал нарушает авторские права? | Защита персональных данных | ЗАКАЗАТЬ РАБОТУ


Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Да какие ж вы математики, если запаролиться нормально не можете??? 8354 - | 7286 - или читать все...

Читайте также:

 

100.26.182.28 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.


Генерация страницы за: 0.006 сек.