Метод квадратного корня

Данный метод используется для решения линейной системы

, (16)

у которой матрица А симметрическая, т.е. А^Т = А, a_ij = a_ji (i = j =1,..., n).

Решение системы (16) осуществляется в два этапа.

Прямой ход. Преобразование матрицы А и представление ее в виде произведения двух взаимно транспонированных треугольных матриц:

А = S ^Т × S, (17)

где

Перемножая S^Т и S, и приравнивая матрице А, получим следующие формулы для определения s_ij:

(18)

После нахождения матрицы S систему (16) заменяем двумя ей эквивалентными системами с треугольными матрицами (17)

. (19)

Обратный ход. Записываем системы (19) в развернутом виде:

(20)

(21)

Используя (20) и (21) последовательно находим

(22)

(23)

Метод квадратных корней дает большой выигрыш во времени по сравнению с рассмотренными ранее прямыми методами, так как, во-первых, существенно уменьшает число умножений и делений (почти в два раза), во-вторых, позволяет накапливать сумму произведений без записи промежуточных результатов. Числовой пример ручного счета можно посмотреть в учебнике: Копченова Н.В., Марен И.А. «Вычислительная математика в примерах и задачах», 1972.

Машинная реализация метода предусматривает его следующую трактовку. Исходная матрица А системы (16) представляется в виде произведения трех матриц

A = S ^Т × D × S,

где D – диагональная матрица с элементами d_ii = ±1; S – верхняя треугольная (s_ik = 0, если i > k, причем s_ii > 0); S ^T – транспонированная нижняя треугольная.

Требование выполнения условия s_ii > 0 необходимо для полной определенности разложения. Это и определяет необходимость введения диагональной матрицы D.

Рассмотрим алгоритм разложения матрицы А с использованием матрицы D на примере матрицы второго порядка.

Пусть А – действительная симметричная матрица

.

Будем искать S и D в виде

, , где d_ii = ±1.

Тогда

.

Из условия равенства A = S ^ТD S, получим три уравнения

Из первого уравнения находим

d ₁₁ = sign a ₁₁; s ₁₁ = .

Далее, если а ₁₁ ¹ 0, то s ₁₂ = а ₁₂ / (s ₁₁ d ₁₁), и, наконец

,

т.е. d ₂₂ = sign (a ₂₂ ); s ₂₂ = .

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

Итак, если S^ТDS известно, то решение исходной системы сводится к последовательному решению систем:

. (23)

Нахождение элементов матрицы S (извлечение корня из А) осуществляется по рекуррентным формулам, избежав проблемы оперирования комплексными числами:

d_k = sign ;

s_kk = ; (24)

s_kj = ;

k = 1, 2,..., n; j = k +1, k +2,..., n.

В этих формулах сначала полагаем k = 1 и последовательно вычисляем

d ₁ = sign (a ₁₁); s ₁₁ =

и все элементы первой строки матрицы S (s _{1 j}, j > 1), затем полагаем k = 2, вычисляем s ₂₂ и вторую строку матрицы s _{1 j} для j > 2 и т.д.

Решение систем (23) ввиду треугольности матрицы S осуществляется по формулам, аналогичным обратному ходу метода Гаусса:

Метод квадратного корня почти вдвое эффективнее метода Гаусса, т.к. полезно использует симметричность матрицы.

Схема алгоритма метода квадратного корня представлена на рис. 2.3. Значение функции sign(x) равно +1 для всех х > 0 и –1 для всех x < 0.

Алгоритм реализован в методическом пособии: А.К.Синицын и др. «Алгоритмы вычислительной математики».

Проиллюстрируем метод квадратного корня, решая систему трех уравнений:

, .

Нетрудно проверить, что матрица А есть произведение двух треугольных матриц (здесь d_ii = 1):

.

Исходную систему запишем в виде

.

Обозначим

.

Тогда для вектора получим систему :

, откуда y ₁ = 3; y ₂ = 2; y ₃ = 1.

Зная , решаем систему :

, откуда х ₃ = 1; х ₂ = 1; х ₁ = 1.

Рис. 2.3. Блок-схема метода квадратного корня