Матрицы. Системы линейных алгебраических уравнений (СЛАУ)

Нулевой – вектор, все компоненты которого равны нулю и обозначается в тексте программы как: a=[0;0;0]; a= zeros(3,1);

Транспонированный - вектор at= a’;

Матрица единичная E=[1 0 0;0 1 0;0 0 1]; E=eye(3);

Транспонированная – матрица, в которой строки заменены на соответствующие столбцы  AT=A’;

Равенство матриц  т.е. a_ij= b_ij где i=1,2,3,…,n j=1,2,3,…,m

Норма (длина) вектора  nor=sqrt(sum(a.^2)); nor=norm(a);

Норма матрицы (Эвклидова) Nor_A=sqrt(sum(A.^2)); Nor_A=norm(A,’fro’);

Складывать или вычитать можно только вектора с одинаковой размерностью  c=a+b;

Складывать или вычитать можно только матрицы с одинаковой размерностью  C=A+B;

Умножение вектора на константу.  c=λ*b;

Умножение матрицы на константу  C= λ *B;

Скалярное произведение векторов Это значение суммы произведений соответствующих компонент двух векторов.  z=a’ * b;

Угол между векторами. Косинус угла  r=a’*b/(norm(a)*norm(b))

Умножение матриц  Количество столбцов матрицы  должно равняться количеству строк матрицы  Элемент  вычисляется как скалярное произведение i-й строки матрицы  и j-го столбца матрицы  C=A*B;

Обратной матрицей называется такая квадратная матрица при умножении которой на исходную как справа так и слева получается единичная матрица  AO=inv(A);

Обращение матрицы  методом Гаусса-Жордана заключается в построении расширенной матрицы  и преобразовании расширенной матрицы так, чтобы на месте исходной получилась единичная матрица, тогда на месте единичной получится обратная матрица:  

Метод Гаусса-Жордана состоит из четырёх этапов

1) Строим расширенную матрицу дописав к исходной квадратной матрице единичную матрицу того же размера  и задаём номер ведущей строки k=1. E=eye(n); C=[A,E];

2) Делим элементы k-й строки начиная с k-ого на  

 j = k,k+1,k+2,…,2·n т.е.  =1.

3) Преобразуем все i-е строки кроме k-й, i=1,2,3,…,n i≠k так, чтобы элементы c_ik=0. Для этого из каждого элемента i-й строки начиная с k-ого вычитаем соответствующий элемент k-й строки, умноженный на элемент c_ik, т.е.

4) Проверяем условие k<n, если оно справедливо, то k=k+1 и выполняем алгоритм с пункта 2, иначе выводим полученную обратную матрицу, расположенную на месте единичной.

Система линейных алгебраических уравнений (СЛАУ). В общем виде СЛАУ можно записать в следующем виде  

Совокупность коэффициентов , i =1,2,3,…,n; j=1,2,3,….,m системы можно представить в виде матрицы:  

Совокупность неизвестных  в виде вектора  Совокупность неизвестных  в виде вектора

Используя выше приведенные определения, запишем СЛАУ в матричном виде:  Решить СЛАУ значить найти такие значения вектора x, подстановка которого в систему, обращает каждое уравнение этой системы в тождество

Классификация СЛАУ. СЛАУ называется: Переобусловленной, если n>m. Недообусловленой, если n<m. Нормальной, если n=m. Однородной, если вектор . Неоднородной, если вектор . Если система, имеет хотя бы одно решение, она называется совместной. Система, не имеющая решений, называется несовместной. Совместная система, имеющая единственное решение, называется определенной, а имеющая бесчисленное множество решений, называется неопределенной. Очевидно, что однородная система всегда совместна, так как имеет хотя бы одно решение , которое называется тривиальным.

Все методы решения СЛАУ можно разделить на две группы: точные и итерационные.

Точные методы позволяют получить решение путем выполнения определённого и точного количества арифметических операций. При этом погрешность решения определяется лишь точностью представления исходных данных и точностью вычислительных операций.
Итерационные методы дают некоторую последовательность приближений к решению. Пределом этой последовательности является решение системы уравнений. Решение, возможно, определить лишь с некоторой, как правило, заданной степенью точности e. Количество итераций для достижения требуемой точности решения определяется величиной e, выбором начального приближения и видом системы уравнений.

Точные методы: Метод обратной матрицы  x=inv(A)*b x=A\b

Метод Гаусса. Метод Гаусса включает два этапа:

Первый этап (прямой ход) заключается в последовательном исключении неизвестных из системы уравнений и состоит из n–1 шага. На первом шаге с помощью первого уравнения исключается x₁ из всех последующих уравнений начиная со второго, на втором шаге с помощью второго уравнения исключается x₂ из последующих уравнений начиная с третьего и т.д. Последним исключается x_n-1 из последнего n-го уравнения так, что последнее уравнение будет содержать только одно неизвестное x_n. Такое последовательное исключение неизвестных равносильно приведению матрицы коэффициентов к треугольному виду. Строка, с помощью которой исключаются неизвестные, называется ведущей строкой, а диагональный элемент в этой строке – ведущим элементом.

Второй этап (обратный ход) заключается в последовательном вычислении искомых неизвестных и состоит из n шагов. Решая последнее уравнение, находим неизвестное xn. Далее используя это значение из предыдущего уравнения вычисляем неизвестное xn-1 и т.д. Последним найдем неизвестное x1 из первого уравнения.

Матрица, содержащая помимо. коэффициентов при неизвестных столбец свободных членов  , называется расширенной

1) Строим расширенную матрицу  размерностью n на n+1, приписав, справа к матрице  вектор  т.е. c_i,j=a_i,j, c_i,n+1=b_i, где i=1,2,3,…,n j=1,2,3,…,n  Задаем номер ведущей строки k = 1

2) Преобразуем все строки, расположенные ниже k-ой так, чтобы элементы c_ik=0, для этого вычисляем множитель b=-с_i,k/c_k,k и каждую i-ую строку заменяем суммой i–ой и k-ой умноженной на b, т.е. c_i,j=c_i,j+b*c_k,j где i = k+1,k+2,k+3,….,n и j = k,k+1,k+2,…,n+1

3) Проверяем k = n-1 если нет, то выбираем новую ведущую строку k=k+1 и переходим на пункт 2, иначе выполняем пункт 4.

4) Обратный ход. Из последнего n-ого уравнения определяем последнее n-ое неизвестное. x_n=c_n,n+1/c_n,n Последовательно, из предыдущих уравнений начиная с i=n-1, вычисляем соответствующие неизвестные x_i. Последним, определяется первое неизвестное из первого уравнения

Для уменьшения погрешности вычислений используют модификации метода Гаусса, которые определяются выбора«ведущего» элемента. В модификации с частичным выбором на каждом k-м шаге прямого хода в качестве «ведущего» выбирается наибольший по модулю элемент из неприведённой части k-го столбца матрицы, т.е.  Строка, содержащая этот элемент, переставляется с k-й строкой расширенной матрицы

При полном выборе в качестве «ведущего» элемента выбирается максимальный по модулю элемент из всей неприведённой части матрицы коэффициентов системы:  Для этого осуществляется необходимая перестановка как строк, так и столбцов в расширенной матрице коэффициентов. При этом следует помнить, что перестановка столбцов равносильна переименованию неизвестных.

Обусловленность систем линейных алгебраических уравнений. Если система плохо обусловлена, то это значит, что погрешности коэффициентов матрицы и свободных членов или погрешность округления при расчетах могут сильно исказить решение.

Исходную систему уравнений  с учетом погрешности в векторе  запишем как  или  и тогда , отсюда можно выразить ошибку . Абсолютную погрешность определим, как норму ошибки  или . Определим относительную погрешность  . Определим  

Из исходной системы  получим  далее определим  и подставим в определение относительной погрешности, получим

Вводим понятие числа обусловленности:  и тогда .

Метод простых итераций. Алгоритм метода состоит из трёх этапов.

Первый этап. Приведение СЛАУ к итерационному виду, для этого разрешим каждое уравнение относительно соответствующего неизвестного:  Тогда итерационную формулу запишем в виде:  где вектор  – приведенный столбец свободных членов,  – приведенная матрица коэффициентов

Второй этап. Проверяем условие сходимости  если условие не выполняется, то преобразуем исходную систему и выполняем 1-й этап.

Третий этап. Осуществляем уточнение решения по полученной итерационной формуле  За начальное приближение принимается  Условием окончания итерационного процесса является выполнение условия  где величина ε определяет точность получаемого решения, а  – смежные приближения к решению.

Программа решения СЛАУ. Простые итерации.

function DATA

global A b eps n;

eps=0.4;

n=3;

A=[4 1 1; 2 5.5 1; 2 1 4];

b=[6;8.5;7];

end

 

function [ x ] = fun_SLAU_Prost_Iterac(A,b,n,eps)

for i=1:n

for j=1:n

   if i==j

       C(i,j)=0;

   else

       C(i,j)=A(i,j)/A(i,i);

   end %if

end %for j

end %for i

for i=1:n

d(i)=b(i)/A(i,i);

end % for i

d=d';

 if norm(C, 'fro')<=1

x0=d;

for i=1:100

    x1=d-C*x0;

    if norm(x1-x0)<=eps

        i

        x=x1;

        break;

    else

        x0=x1;

    end %if

end %for i

 else

disp('||C||>1');

x=zeros(n);

 end %if

 end % function

 

function GLAV_SLAU_Prost_Iterac

global A b eps n x;

DATA;

[ x ] = fun_SLAU_Prost_Iterac(A,b,n,eps);

REPORT;

end

 

function REPORT

global A b eps n x;

disp('Arguments SLAU_Prost_Iterac');

disp('matrix A');

A

disp('Column b');

b

disp(['eps = ' num2str(eps,'%10.5f') ]);

disp('Results SLAU_Prost_Iterac');

disp('Column of variables');

x

disp('Ax-b');

A*x-b

end