![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Метод квадратного корня
Данный метод используется для решения линейной системы
у которой матрица А симметрическая, т.е. АТ = А, aij = aji (i = j =1,..., n). Решение системы (16) осуществляется в два этапа. Прямой ход. Преобразование матрицы А и представление ее в виде произведения двух взаимно транспонированных треугольных матриц: А = S Т × S, (17) где
Перемножая SТ и S, и приравнивая матрице А, получим следующие формулы для определения sij:
После нахождения матрицы S систему (16) заменяем двумя ей эквивалентными системами с треугольными матрицами (17)
Обратный ход. Записываем системы (19) в развернутом виде:
Используя (20) и (21) последовательно находим
Метод квадратных корней дает большой выигрыш во времени по сравнению с рассмотренными ранее прямыми методами, так как, во-первых, существенно уменьшает число умножений и делений (почти в два раза), во-вторых, позволяет накапливать сумму произведений без записи промежуточных результатов. Числовой пример ручного счета можно посмотреть в учебнике: Копченова Н.В., Марен И.А. «Вычислительная математика в примерах и задачах», 1972. Машинная реализация метода предусматривает его следующую трактовку. Исходная матрица А системы (16) представляется в виде произведения трех матриц A = S Т × D × S, где D – диагональная матрица с элементами dii = ±1; S – верхняя треугольная (sik = 0, если i > k, причем sii > 0); S T – транспонированная нижняя треугольная. Требование выполнения условия sii > 0 необходимо для полной определенности разложения. Это и определяет необходимость введения диагональной матрицы D. Рассмотрим алгоритм разложения матрицы А с использованием матрицы D на примере матрицы второго порядка. Пусть А – действительная симметричная матрица
Будем искать S и D в виде
Тогда
Из условия равенства A = S ТD S, получим три уравнения Из первого уравнения находим d 11 = sign a 11; s 11 = Далее, если а 11 ¹ 0, то s 12 = а 12 / (s 11 d 11), и, наконец
т.е. d 22 = sign (a 22 Здесь и для общего случая матрицу S можно по аналогии с числами трактовать как корень квадратный из матрицы А, отсюда и название метода. Итак, если SТDS известно, то решение исходной системы
Нахождение элементов матрицы S (извлечение корня из А) осуществляется по рекуррентным формулам, избежав проблемы оперирования комплексными числами: dk = sign skk = skj = k = 1, 2,..., n; j = k +1, k +2,..., n. В этих формулах сначала полагаем k = 1 и последовательно вычисляем d 1 = sign (a 11); s 11 = и все элементы первой строки матрицы S (s 1 j, j > 1), затем полагаем k = 2, вычисляем s 22 и вторую строку матрицы s 1 j для j > 2 и т.д. Решение систем (23) ввиду треугольности матрицы S осуществляется по формулам, аналогичным обратному ходу метода Гаусса: Метод квадратного корня почти вдвое эффективнее метода Гаусса, т.к. полезно использует симметричность матрицы. Схема алгоритма метода квадратного корня представлена на рис. 2.3. Значение функции sign(x) равно +1 для всех х > 0 и –1 для всех x < 0. Алгоритм реализован в методическом пособии: А.К.Синицын и др. «Алгоритмы вычислительной математики». Проиллюстрируем метод квадратного корня, решая систему трех уравнений:
Нетрудно проверить, что матрица А есть произведение двух треугольных матриц (здесь dii = 1):
Исходную систему запишем в виде
Обозначим
Тогда для вектора
Зная
Рис. 2.3. Блок-схема метода квадратного корня
|