1 Постановка задачи
Для
численного решения систем линейных
алгебраических уравнений с квадратными
матрицами методом ортогонализации
необходимо спроектиро вать и разработать
программное обеспечение, реализующее
функции ввода, вывода, расчет по
вычислительной схеме метода ортогонализации
и проведение численных экспериментов.
При оценке качества разработанного
алгоритма и программы использовать
критерий на основе величины нормы
относительной погрешности
.
2 Метод ортогонализации
В данном разделе приводятся основные сведения о методе ортогонали зации необходимые для разработки алгоритма и программного обеспечения.
Идея метода состоит в следующим. Пусть даны квадратная матрица A и вектор B. Надо найти такой x, чтобы Ax = b. Перенесём вектор B в левую часть уравнения и будем рассматривать (n+1)-мерные строки. Тогда решением будет вектор x' у которого (n+1)-ая координата равна -1 и все скалярные произведения на строки полученной матрицы равны 0. Отсюда следует, что нам нужно найти в (n+1)-мерном пространстве вектор ортогональный линейной оболочки из n векторов. Такой вектор всегда существует. Если у него (n+1)-ая координата не равна 0, то умножая этот вектор на скаляр получим вектор x'.
Пусть дана система линейных алгебраических уравнений
Ах = b (1)
где
А
=
(аij)
– неособенная размерности n
x
n
матрица,
и
-
векторы-столбцы.
Если присоединить столбец b к матрице A, то исходная система (1) запишется в виде
или
(2)
где ai = (ai1, ai2 , ..., ain , ai, n+1 ) - вектор-строки, ai, n+1 = - bi, i =1, 2, ..., n;
z = (x1, ..., xn, 1)T - вектор-столбец. Система векторов a1, a2, ..., an дополняется вектором an+1 = (0, 0, ..., 1). К полученной системе a1, a2, ..., an, an+1 применяется процесс ортогонализации, состоящий в построении ортонормированной системы s1, s2, ..., sn+1, и который реализуется по следующим рекуррентным формулам
(3)
где
-евклидова
норма вектора
.
Вектор
удовлетворяет уравнению (2), а за искомое
решение принимается вектор x
с компонентами:
.
(4)
Формулами (3) и (4) определяется векторная форма записи вычислительной схемы метода ортогонализации.
В координатной форме схема метода ортогонализации записывается следующим образом:
(5)
k
=2,
3, ..., n+1;
j
=
1, 2,..., n+1;
(6)
.
(7)
3 Алгоритм метода ортогонализации
В данном разделе приводятся описание алгоритм вычислений по формулам метода ортогонализации.
r1=a1; s1= r1/sqrt(r1, r2)
Для k =2 до n+1 выполнять
Для i=1 до k-1 выполнять
sp=(ak,si) вычисление скалярного произведения (ak,si)
Для p=1 до n+1 выполнять
si,p=sp*si,p
Конец по p
Конец по i
Вычисление компонент вектора rk
Для j =1 до n +1 выполнять
ss=0
Для i =1 до k -1 выполнять
ss=ss+si,j
Конец по i
rk,j=ak,j-ss
Конец по j
Формирование вектора sk
sp =( rk,rk) вычисление скалярного произведения
Для p=1 до n+1 выполнять
sk,p= rk,p/sp
Конец по p
Конец по k
Формирование и вывод решения
Для j=1 до n выполнять
xj=(rn+1,j/ rn+1,n+1)*(-1)
Конец по j