- •§ 3. Методы решения систем линейных и нелинейных уравнений
- •§3. Методы решения систем линейных и нелинейных уравнений
- •3.1. Метод исключения гаусса для систем линейных уравнений
- •3.2. Метод главных элементов
- •3.3. Решение систем нелинейных уравнений методом ньютона
- •3.4. Решение систем линейных уравнений методом квадратного корня
- •3.5. Решение систем линейных уравнений методом итераций
- •3.6. Решение систем линейных уравнений методом зейделя
- •§4. Алгебра матриц
- •4.1. Вычисление собственныхвекторов и собственных значений матриц по методу крылова
3.4. Решение систем линейных уравнений методом квадратного корня
Метод квадратного корняоснован на представлении матрицыА, составленной из коэффициентов системы в форме произведения треугольных матриц, что позволят свести решение заданной системы к последовательному решению двух систем с треугольными матрицами.
Метод квадратного корня применяется для решения системы линейных уравнений, коэффициенты которой образуют эрмитову симметрическую матрицу (эрмитова матрица совпадает с комплексно-сопряженной транспонированнойA*=A).
Представим матрицу Ав видеА=S*D S, гдеS - верхняя треугольная матрица с положительными элементами на главной диагонали;S*- транспонированная к матрицеS;D- диагональная матрица, на диагонали которой находятся числа (+1) или (— 1).
Если матрицы SиD найдены, то заданная системаAХ= = F может быть решена следующим путем:
AX = S* D S X = (S* D) S X = B Y = F, (1.28)
где S*D = Весть нижняя треугольная матрица и Y = S X- вспомогательный вектор.
Таким образом, решение системы АX = Fравносильно решению двух треугольных систем ВY = Fи SX =Y.
Пусть S = (sik) при i > k и sik № 0, sii > 0; S* = (); D = =(dik), d =1; i № k. Тогда из сравнения матриц АиS*DSполучим
.
Ограничение в сумме получается из учета того факта, что в матрице Sниже главной диагонали элементы обращаются в нуль. Последнее равенство можно переписать несколько иначе, приняв для определенностиk= min(k,l):
;
,
откуда окончательно получим формулы для вычисления элементов матриц SиD:
(1.29)
Единственным условием возможности определения sikявляетсяskk № 0. Для построения матриц полагаемk = 1 и последовательно вычисляемвсе элементы первой строкиsпо формуле (1.29); затем полагаемk= 2- и определяем элементы второй строки и т.д. Когдаk=n, тогда найдены все элементыматрицS иD,а следовательно иS*. Затем последовательно выполняем вычисления (1.28):
S*Z = F; D Y = Z; S X = Y
обычным ходом по формулам
(1.30)
при i = 2, 3, ..., n.
Попутно заметим, что определитель матрицы А можно вычислить из выражения
. (1.31)
Этот метод экономичен, требует n3/3 арифметических действий и при большихn(n> 50) вдвое быстрее метода Гаусса. Если за основу процедуры принять алгоритм П5.6 Дьяконова [1987], то тогда метод квадратного корня может быть реализован c помощью следующей процедуры:
procedure KVK (M, N : integer;
aa: array of real; bb : array of real;
var C: array of real);
type mas1=array [0..4] of real;
mas=array [0..4] of mas1;
var a : mas; j, k, i : integer; s, c1 : real;
begin
i := 0;
for j := 1 to m do
for k := 1 to n do
begin Inc (i); a[j,k] := aa [i]; end;
for j := 1 to N do
begin
for k := j to N do
begin
s := 0.0;
for i := 1 to M do s := s + a[i,j] * a[i,k];
c[k] := s;
end;
c1 := 0.0;
for i := 1 to M do с1 := c1 + a[i,j]*Bb[i];
for i := j to N do a[i,j] := c[i];
c[J] := c1;
end;
a[1,1] := sqrt (a[1,1]);
for j := 2 to N do a[1,j] := a[j,1] / a[1,1];
for i := 2 to n do
begin
s := 0.0;
for k := 1 to i-1 dо s := s + a[k,i]*a[k,i];
a[i,i] := sqrt (a[i,i] - S);
for j := i+1 to N do
begin
s := 0.0;
for k := 1 to i-1 do
S := S + A[K,I]*A[K,J];
A[I,J] := (A[J,I] - S) / A[I,I];
end;
end;
c[1] := c[1] / a[1,1];
for i := 2 to N do
begin s := 0.0;
for k := 1 to i-1do
s := s + a[k,i] * c[k];
c[i] := (c[i] - s) / a[i,i];
end;
c[n] := c[n] / a[n,n];
for i := n-1 downto 1 do
begin s := 0.0;
for k := i+1 to N do s := s + a[i,k] * c[k];
c[i] := (c[i] - s) / a[i,i];
end;
еnd.
Формальные параметры процедуры.Входные: m, N(типinteger) -mуравнений иnнеизвестных определяют размер матрицыА.Для этой процедурыобязательно выполнение m > n, т.е. количествоуравнений должно быть больше количества неизвестных (система переопределена), предельныйразрешенный случай m = n; а - матрица, составленнаяиз коэффициентов при неизвестных;В - массив, составленный из столбца свободных членов.Выходные:С - массив, в котором содержится решение системы.
Для проверки правильности работы процедуры решалась система 4´4 линейных уравнений методом квадратных корней с точностью 0.0001:
0.68X1 + 0.05X2 + 0.11X3 + 0.08X4 = 2.15 ;
0.05X1 + 0.13X2 + 0.27X3 + 0.80X4 = 0.44 ;
0.11X1 + 0.27X2 + 0.28X3 + 0.06X4 = 0.83 ;
0.08X1 + 0.80X2 + 0.06X3 + 0.12X4 = 1.16 ,
решение которой, полученное методом квадратных корней, будет следующим
Х 1 = 2.97; Х2 = 1.11; Х3 = 0.74; Х4 = -0.07.