Решение СЛАУ прямыми методами

Размещено на http://www.allbest.ru/

Министерство образования науки и культуры Украины

Одесский национальный политехнический университет

Отчет по лабораторной работе

Дисциплина «Численные методы»

Тема «Решение СЛАУ прямыми методами»

Проверила:

Гришина В.А.

Выполнила ст. гр. ВС-121

Мостовая С.

Одесса 2014



1. Задание лабораторной работы

Составить программу LU - разложения матриц с помощью компактной схемы метода Гаусса. Используя полученное LU - разложения матрицы, вычислить определитель исходной матрицы и найти обратную матрицу. Используя программу, выполнить LU - разложение матрицы, соответствующей варианту, выполнить проверку полученного результата. Вычислить определитель заданной матрицы и найти обратную матрицу. Выполнить проверку правильности нахождения обратной матрицы. Сделать выводы.

Вариант № 6

0,63 0,57 -0,83

1,24 0,87 -0,54

1,32 -0,44 0,63

2. Теоретическое описание используемых методов

· LU-разложение

LU-разложение -- представление матрицы в виде произведения двух матриц, , где -- нижняя треугольная матрица, а -- верхняя треугольная матрица. LU-разложение еще называют LU-факторизацией.

LU-разложение используется для решения систем линейных уравнений, обращения матриц и вычисления определителя.

Этот метод является одной из разновидностей метода Гаусса.

· Решение систем линейных уравнений

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

Если известно LU-разложение матрицы , , исходная система может быть записана как

Эта система может быть решена в два шага. На первом шаге решается система

Поскольку -- нижняя треугольная матрица, эта система решается непосредственно прямой подстановкой. На втором шаге решается система

Поскольку -- верхняя треугольная матрица, эта система решается непосредственно обратной подстановкой.

· Обращение матриц

Обращение матрицы эквивалентно решению линейной системы ,

где -- неизвестная матрица, -- единичная матрица. Решение этой системы является обратной матрицей .

Систему можно решить описанным выше методом LU-разложения.

· Вычисление определителя матрицы

Имея LU-разложение матрицы , , можно непосредственно вычислить её определитель,

,

где -- размер матрицы , и -- диагональные элементы матриц и .

· Вывод формулы

В силу назначения LU-разложения нас будет интересовать только случай, когда матрица A невырожденная.

Поскольку и в первой строке матрицы L, и в первом столбце матрицы U, все элементы, кроме, возможно, первого, равны нулю, имеем .

Если , то или . В первом случае целиком состоит из нулей первая строка матрицы L, во втором -- первый столбец матрицы U. Следовательно, L или U вырождена, а значит, вырождена A, что противоречит предположению. Таким образом, если , то невырожденная матрица A не имеет LU-разложения. Пусть , тогда и . Поскольку L и U определены с точностью до умножения U на константу и деления L на ту же константу, мы можем потребовать, чтобы . При этом .

Разделим матрицу A на клетки:

,

где имеют размерность соответственно (N-1)Ч1, 1Ч(N-1), (N-1)Ч(N-1). Аналогично разделим на клетки матрицы L и U:

Уравнениепринимает вид

Решая систему уравнений относительно , получаем:

Окончательно имеем:

Итак, мы свели LU-разложение матрицы NЧN к LU-разложению матрицы (N-1)Ч(N-1).

Выражение называется дополнением Шура элемента в матрице A.

Заметим, что -- не скаляр, а матрица (N-1)Ч(N-1).

· Алгоритм

Один из алгоритмов для вычисления LU-разложения приведён ниже.Будем использовать следующие обозначения для элементов матриц , , ; причём диагональные элементы матрицы : , . Тогда, если известно LU-разложение матрицы, её определитель можно вычислить по формуле

= произведению элементов на диагонали матрицы U.

Найти матрицы и можно следующим образом (выполнять шаги следует строго по порядку, так как следующие элементы находятся с использованием предыдущих):

1.

2.

Для

1.

2. 

3.

В итоге мы получим матрицы -- и . В программной реализации данного метода (компактная схема Гаусса) для представления матриц и можно обойтись всего одним массивом, в котором совмещаются матрицы и . Например, так (для матрицы размером ):

4. Текст программы с соответствующими комментариями

using System;

using System.IO;

namespace LU

{

class Program

{

static void Main(string[] args)

{

/*Чтение происходит из файла Матрица.txt, который находится в проекте.

на вход подается в первой строке порядок матрицы, а далее сама матрица через пробелы

в таком виде:

3 - порядок матрицы

0,63 0,57 -0,83

1,24 0,87 -0,54

1,32 -0,44 0,63*/

StreamReader sr = new StreamReader("Матрица.txt");

string poryadok = sr.ReadLine();

int n = Int32.Parse(poryadok);

string[] separ = { " ", "\r", "\n", "" };

string matrix = sr.ReadToEnd();

string[] M = matrix.Split(separ, StringSplitOptions.RemoveEmptyEntries);

double[,] K = new double[n, n];

int k = 0;

for (int i = 0; i < n; i++)

{

for (int j = 0; j < n; j++)

{

K[i, j] = Convert.ToDouble(M[k]);

k += 1;

}

}

Console.WriteLine("Дана матрица:");

Print_Matrix(K);//Выводим матрицу

Console.WriteLine();

LU_razl(K, n);//Выполняем LU-разложение.

Console.WriteLine();

Console.ReadKey();

}

static void Print_Matrix(double[,] A)

{

for (int i = 0; i < 3; i++)

{

for (int j = 0; j < 3; j++)

{

Console.Write(Math.Round(A[i, j], 2) + " || ");//вывод с 2-мя цифрами после запятой.

}

Console.WriteLine();

}

}

private static void LU_razl(double[,] A, int n)

{

double[,] U1 = new double[n, n];

double[,] L1 = new double[n, n];

double sum = 0;

double sum1 = 0;

for (int i = 0; i < n; i++)

{

U1[0, i] = A[0, i];

}

for (int i = 1; i < n; i++)

{

L1[i, 0] = A[i, 0] / U1[0, 0];

L1[i, i] = 1;

L1[0, 0] = 1;

}

for (int i = 1; i < n; i++)

{

for (int j = i; j < n; j++)

{

for (int k = 0; k <= i - 1; k++)

{

sum += L1[i, k] * U1[k, j];

U1[i, j] = A[i, j] - sum;

}

sum = 0;

}

for (int j = i + 1; j < n; j++)

{

for (int k = 0; k <= i - 1; k++)

{

sum1 += L1[j, k] * U1[k, i];

L1[j, i] = (A[j, i] - sum1) / U1[i, i];

}

sum1 = 0;

}

}

Console.WriteLine("Матрицa U после разложения:");

Print_Matrix(U1);

Console.WriteLine("Матрицa L после разложения:");

Print_Matrix(L1);

Console.WriteLine();

double d = Opredel(U1);//Считаем определитель

double[,] A1 = obratnaya_matrix(n, U1, L1);

Console.WriteLine("Проверим LU разложение:");

proisv(L1, U1);

Console.WriteLine();

Console.WriteLine("Проверим обратную матрицу ");

proisv(A, A1);

}

static void proisv(double[,] L, double[,] U)

{

//перемножаем матрицы.

double[,] R = new double[3, 3];

for (int i = 0; i < 3; i++)

{

for (int j = 0; j < 3; j++)

{

for (int k = 0; k < 3; k++)

{

R[i, j] += L[i, k] * U[k, j];

}

}

}

Console.WriteLine("Перемножим матрицы:");

Print_Matrix(R);//Перемножили-выводим

}

static double Opredel(double[,] U)

{

//Считаем определитель перемножением элементов главной диагонали матрицы U

double det = 1;

for (int i = 0; i < 3; i++)

{

det *= U[i, i];

}

Console.WriteLine("Определитель det(A) = {0}", det);

return det;

}

static double[,] obratnaya_matrix(int n, double[,] U, double[,] L)

{

double summ = 0;//Используем переменную для подсчета суммы по к из ф-лы.

double[,] E = new double[n, n];//Единичная матрица

for (int i = 0; i < n; i++)

{

E[i, i] = 1;

}

double[,] Y = new double[n, n];// Матрица для решения LY=E

double[,] X = new double[n, n];//Матрица для решения UX=Y

for (int i = 0; i < n; i++)

{

for (int j = 0; j < n; j++)

{

for (int k = 0; k <= j - 1; k++)

{

summ += L[j, k] * Y[k, i];

}

Y[j, i] = (E[j, i] - summ) / L[j, j];

summ = 0;

}

}

summ = 0;

for (int i = n - 1; i >= 0; i--)

{

for (int k = n - 1; k >= 0; k--)

{

for (int j = k + 1; j < n; j++)

{

summ += U[k, j] * X[j, i];

}

X[k, i] = (Y[k, i] - summ) / U[k, k];

summ = 0;

}

}

Console.WriteLine();

Console.WriteLine("Обратная матрица через UL :");

Print_Matrix(X);

return X;

}

}

}

5. Результаты расчетов

матрица разложение коэффициент уравнение

Дана матрица:

0,63 || 0,57 || -0,83 ||

1,24 || 0,87 || -0,54 ||

1,32 || -0,44 || 0,63 ||

Матрицa U после разложения:

0,63 || 0,57 || -0,83 ||

0 || -0,25 || 1,09 ||

0 || 0 || -4,73 ||

Матрицa L после разложения:

1 || 0 || 0 ||

1,97 || 1 || 0 ||

2,1 || 6,49 || 1 ||

Определитель det(A) = 0,750055

Обратная матрица через UL :

0,41 || 0,01 || 0,55 ||

-1,99 || 1,99 || -0,92 ||

-2,26 || 1,37 || -0,21 ||

Проверим LU разложение:

Перемножим матрицы:

0,63 || 0,57 || -0,83 ||

1,24 || 0,87 || -0,54 ||

1,32 || -0,44 || 0,63 ||

Проверим обратную матрицу:

Перемножим матрицы:

1 || 0 || 0 ||

0 || 1 || 0 ||

0 || 0 || 1 ||

Выводы

С помощью метода LU -разложения очень легко работать с матрицей дальше: решать уравнения, находить определитель или обратную матрицу, которая при нахождении в лоб имеет сложность n! . При использовании LU количество необходимых операций около n^3, что очень существенно экономит время и память. Правда, оно возможно только для невырожденных матриц.

Размещено на Allbest.ru

...