Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Метод Холесского. ⇐ ПредыдущаяСтр 4 из 4
Исключительно эффективную реализацию метода LU-факторизации можно получить, если ограничиться классом линейных систем с симметрической положительно определенной матрицей A, т. е. Такую реализацию называют методом Холесского, либо методом квадратного корня. Будем полагать, что решаемая система имеет симметрическую положительно определенную матрицу A. В этом случае матрица A представляется в виде Здесь – нижняя треугольная матрица. Такое разложение существует и единственно для положительно определенных симметрических матриц. Система преобразуется к виду . Вектор ищется путем последовательного решения двух систем с треугольными матрицами: ; . Для получения расчетных соотношений элементов матрицы рассмотрим произвольный элемент матрицы A: Суммирование здесь выполняется только до j, т. к. j≤ i. Выделим член при значении k=j: . Теперь Эти соотношения позволяют вычислить по столбцам элементы матрицы . Эффективность такого метода достигается на этапе разложения матрицы, т. к. необходимо вычислить в этом случае только матрицу . Арифметические затраты в методе Холесского составляют длинных операций и n операций извлечения квадратного корня. Существует другой вариант разложения симметрической положительно определенной матрицы, в котором удается избежать операций извлечения квадратного корня. В этом варианте вводится новая матрица по правилу , причем – матрица, вычисленная ранее по схеме Холесского, – диагональная матрица с элементами матрицы . Матрица существует и является нижней треугольной с единичной диагональю. В этом случае , где . Расчетные соотношения для элементов матриц и можно получить, как и прежде, привлекая правило перемножения матриц , из которого следует, что т. к. матрица имеет единичную диагональ. Такой алгоритм потребует вдвое большего числа перемножений, чем схема Холесского. Однако, если ввести замену переменных , то расчетные соотношения примут вид Здесь сначала вычисляют вспомогательные величины , а затем их используют для определения искомых величин и . Количество умножений при такой организации алгоритма составляет приблизительно и не содержит операции извлечения квадратного корня.
|