Численные методы решения СЛАУ

Методы решения СЛАУ

Общий вид СЛАУ

[pic 1]

Чтобы система имела единственное решение определим количество переменных равным количеству уравнений (n):[pic 2]

[pic 3]

 [pic 4]

- матрица системы, обозначим за А

[pic 5]

- искомый вектор Х

[pic 6]

- вектор свободных членов В

Теперь можем представить систему в таком виде: [pic 7]

Метод обратной матрицы

Алгоритм:

[pic 8]

Временная сложность алгоритма: [pic 9]

Определение функции в MATLAB:

function [X] = invmatrix(A, B)

%invmatrix решает СЛАУ методом обратной матрицы

%А-матрица системы,

%B-вектор свободных корэффициентов

X = A^-1 * B;

end

Метод Крамера

Алгоритм:

Найдем определитель матрицы коэффициентов А

[pic 10]

Пусть матрица [pic 11]- матрица, у которой все столбцы, кроме n-ого - соответственные столбцы матрицы А, а n-ый столбец будет заменен на столбец свободных членов.

Например, [pic 12], ее определитель [pic 13]. Тогда

[pic 14]. В общем виде [pic 15].

Временная сложность алгоритма: [pic 16]

Определение функции в MATLAB:

function [X] = Kramer(A, B)

%Kramer решает СЛАУ методом Крамера,

%А-матрица системы,

%B-вектор свободных корэффициентов

%X = A^-1 * B;

n=length(B);

d = det(A);

X = zeros(n, 1);

for i = 1:n

    A1 = A;

    A1(:, i) = B;

    num = det(A1);

    X(i) = num/det(A);

end

end

Метод Гаусса-Жордана

Алгоритм:

Составим расширенную матрицу

 [pic 17]

Далее мы выполняем арифметические операции так, чтобы левая часть расширенной матрицы стала единичной. Тогда полученные значения на месте правой части расширенной матрицы - искомое решение СЛАУ.

Вычислительная сложность: [pic 18]

Определение функции в MATLAB:

function [X] = Gauss(A, B)

%Gauss решает СЛАУ методом Гаусса-Жордана,

%А-матрица системы,

%B-вектор свободных корэффициентов

n = length(B);

A1 = zeros(n, n+1);

A1(:, 1:n) = A;

A1(:, n+1) = B;

for i = 1:n

    m = A1(i, i);

    if m == 0

       for j=i+1:n

           if A1(j, i) ~= 0

               A1(i, :) = A1(i, :)+ A1(j,:);

               m = A1(i, i);

               break;

           end

       end

    end

    if m == 0, return; end 

    A1(i, :) = A1(i, :)/m;

    for j = 1:n

        if i~=j

            m = A1(j, i);

            for k = 1:n+1

                A1(j, k) = A1(j,k)-m*A1(i, k);

            end

        end

    end   

end

X = A1(:, n+1);

Метод разложения Холецкого

Алгоритм:

Пусть А - симметричная положительно определенная квадратная матрица. Тогда ее можно представить в виде произведения некоторой нижней треугольной матрицы L на ее транспонированную матрицу. [pic 19]

Исходное уравнение [pic 20] приобретает вид [pic 21]. Выполним замену [pic 22]. Тогда исходное матричное уравнение будет преобразовано в систему из двух матричных уравнений:

[pic 23] , откуда [pic 24]