Численные методы линейной алгебры

Содержание

Введение

1. Метод Гаусса

2. Модификации метода Гаусса

3. Метод прогонки

4. Вычисление определителей

5. Вычисление обратных матриц

6. Итерационные методы

Заключение

Список литературы

Введение

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

В общем случае система линейных алгебраических уравнений имеет вид

(1)

В матричной форме система (1) представляется как

A X = B (2)

где

Чтобы такая система уравнений имела единственное решение, входящие в нее n уравнений должны быть линейно независимыми. Необходимым и достаточным условием этого является неравенство нулю определителя данной системы, т.е. det A ¹ 0. Алгоритмы решения систем уравнений такого типа делятся на прямые и итерационные.

1. Метод Гаусса

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

При использовании метода Гаусса задача решается в два этапа:

1) прямой ход;

2) обратный ход.

Прямой ход заключается в преобразовании системы к треугольному виду.

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

Прямой ход метода Гаусса. Для получения расчетных формул прямого хода преобразуем исходную систему (1), заменив элементы b_i () на a_i,n+1. В результате система (1) будет иметь следующий вид

Прямой ход выполняется за (n-1) шагов, причем на каждом шаге из уравнений с номерами k + 1, k + 2, …, n исключается неизвестное x_k.

На первом шаге сначала первое уравнение делится на a₁₁ ¹ 0. Получим

(3)

где

Затем из каждого оставшегося уравнения вида

 ()

вычитается полученное уравнение (3), умноженное на коэффициент a_i1. В итоге, после выполнения первого шага прямого хода система уравнений примет следующий вид

(4)

где

На втором шаге указанные выше действия повторяются над (n - 1) уравнениями системы (4), всеми кроме первого, с целью исключения переменной x₂, где

В итоге получим

где

Повторяя шаги прямого хода (n - 1) раз, окончательно получим систему уравнений треугольного вида

(5)

где

При программной реализации прямого хода используется расширенная матрица коэффициентов A¢

,

для которой элементы имеют следующий смысл

1)  - начальные значения;

2)  - промежуточные значения;

3)  - конечные значения.

Для определения элементов  матрицы A¢ на некотором k-ом шаге

()

используются следующие расчетные формулы

Обратный ход метода Гаусса. После приведения исходной системы уравнений (1) к треугольному виду (5) вычисляются значения корней по следующим формулам

Таким образом, расчетные формулы обратного хода имеют вид

Вычислительная сложность метода Гаусса оценивается как O(n³), причем для реализации прямого хода требуется около  арифметических операций, а для обратного – около n² операций.