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² операций.

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

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

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

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

Идея этого метода состоит в следующем. На некотором k-м шаге прямого хода из уравнений исключается не следующая по номеру переменная x_k, а такая переменная, коэффициент при которой является наибольшим по абсолютной величине. Этим гарантируется отсутствие деления на нуль и сохранение устойчивости метода.

Если на k-м шаге в качестве главного элемента выбирается , то в матрице A должны быть переставлены местами строки c номерами k и p и столбцы с номерами k и q.

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

Существуют две более простые модификации метода Гаусса:

- с выбором главного элемента по столбцу;

- с выбором главного элемента по строке.

В первом случае в качестве главного элемента выбирается наибольший по абсолютной величине элемент k-й строки (среди элементов , i = ). Во втором - наибольший по абсолютной величине элемент k-го столбца (среди элементов , i = ). Наибольшее распространение получила первый подход, поскольку здесь не изменяется нумерация переменных.

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

LU-разложение. В современном математическом обеспечении ЭВМ метод Гаусса реализуется с использованием LU-разложения, под которым понимают представление матрицы коэффициентов A в виде произведения A = LU двух матриц L и U, где L - нижняя треугольная матрица, U - верхняя треугольная матрица

Если LU-разложение получено, то решение исходной системы уравнений (2) сводится к последовательному решению двух следующих систем уравнений с треугольными матрицами коэффициентов

L Y = B; (6)

U X = Y (7)

линейный алгебраический уравнение численный

где Y = - вектор вспомогательных переменных.

Такой подход позволяет многократно решать системы линейных уравнений с разными правыми частями B. При этом наиболее трудоемкая часть (LU-разложение матрицы A) выполняется только один раз. Эта процедура соответствует прямому ходу метода Гаусса и имеет оценку трудоемкости O(n³). Дальнейшее решение систем уравнений (6) и (7) может выполняться многократно (для различных B), причем решение каждой из них соответствует обратному ходу метода Гаусса и имеет оценку вычислительной сложности O(n²).

Для получения LU-разложения можно воспользоваться следующим алгоритмом.

1. Для исходной системы (1) выполнить прямой ход метода Гаусса и получить систему уравнений треугольного вида (5).

2. Определить элементы матрицы U по правилу

u_ij = C_ij (i = ; j = )

3. Вычислить элементы матрицы L по правилам

Расчетные формулы для решения системы (6) имеют следующий вид:

y₁ = b₁ / l₁₁;

Расчетные формулы для решения системы (7)

x_n = y_n;

(i = n - 1, n - 2, …, 1).

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

Метод прогонки представляет собой простой и эффективный алгоритм решения систем линейных алгебраических уравнений с трехдиагональными матрицами коэффициентов следующего вида

(8)

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

Преобразуем первое уравнение системы (8) к виду x₁ = ₁x₂ + ₁, где

₁ = -с₁ / b₁ и ₁ = -d₁ / b₁. Подставим полученное для x₁ выражение во второе уравнение системы (8)

a₂(₁x₂ + ₁) + b₂x₂ + c₂x₃ = d₂.

Представим это уравнение в виде x₂ = ₂x₃ + ₂, где ₂ = -с₂ / (b₂ + a₂₁) и ₂ = (d₂ - a₂₁) / (b₂ + a₂₁). Полученное для x₂ выражение подставим в третье уравнение системы (8) и т.д.

На i-м шаге (1 < i < n) процесса i-е уравнение системы принимает вид

x_i = _ix_i+1 + _i, (9)

где _i = -с_i / (b_i + a_ii-1) и _i = (d_i - a_ii-1) / (b_i + a_ii-1).

На последнем n-м шаге подстановка в последнее уравнение системы (8) выражения x_n-1 = _n-1x_n + _n-1 дает уравнение a_n(_n-1x_n + _n-1) + b_nx_n = d_n, из которого можно определить значение x_n = _n = (d_n - a_nn-1) / (b_n + a_nn-1).

Значения остальных неизвестных x_i (i = n-1, n-2, ..., 1) легко вычисляются по формуле (9).

Таким образом, алгоритм прогонки, подобно методу Гаусса, включает два этапа - прямой ход (прямая прогонка) и обратный ход (обратная прогонка).

Прямой ход метода прогонки состоит в вычислении прогоночных коэффициентов

_i (i = ) и _i (i = ).

При i = 1 эти коэффициенты вычисляются по формулам:

₁ = -с₁ / ₁; ₁ = -d₁ / ₁; ₁ = b₁.

Для i = используются следующие рекуррентные формулы:

_i = -с_i / _i; _i = (d_i - a_ii-1) / _i; _i = b_i + a_ii-1.

Прямая прогонка завершается при i = n:

_n = (d_n - a_nn-1) / _n; _n = b_n + a_nn-1.

Обратный ход метода прогонки позволяет вычислить значения неизвестных. Сначала полагают x_n = _n. Затем в обратном порядке по формуле (9) определяют значения неизвестных x_n-1, x_n-2, ..., x₁.

Свойства метода прогонки. Трудоемкость метода прогонки оценивается примерно как 8n арифметических операций, что существенно меньше метода Гаусса. Существование решения системы (8) и его единственность гарантируются при выполнении достаточных условий, задаваемых следующей теоремой.

Теорема [2]. Пусть коэффициенты системы (8) удовлетворяют следующим неравенствам

b_ka_k+c_k; b_k>a_k; k = , где a₁ = 0; b_n = 0. Тогда _i 0 и _i

1 для всех i =

Заметим, что при всех _i 0 вычисления по формулам прямой прогонки могут быть доведены до конца (ни один из знаменателей не обратится в нуль). Одновременно все коэффициенты _i, такие, что _i 1, обеспечивают устойчивость по входным данным этапа обратной прогонки по формуле (9).

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

Идея последовательного исключения переменных, реализованная в методе Гаусса, может быть использована при вычислении определителей. При этом используются следующие свойства определителей:

1) перестановка двух строк или столбцов определителя не изменяет его абсолютной величины, но меняет знак на противоположный;

2) умножение всех элементов одной строки или одного столбца на любое число равносильно умножению определителя на это число;

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

Пусть задан определитель

Выберем главный элемент a₁₁ 0. Если a₁₁ = 0, то выполним перестановку двух строк или столбцов этого определителя, чтобы получить a₁₁ 0.

Вынесем главный элемент a₁₁ из первой строки за знак определителя

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

Разложим полученный определитель по элементам первого столбца, что даст понижение его порядка определителя на единицу

Повторим указанную процедуру (n - 1) раз и окончательно получим

Если при вычислении определителя производилась перестановка строк или столбцов (для выбора главного элемента), то

где s - количество выполненных перестановок.

Таким образом, вычисление определителя detA некоторой матрицы A сводится к выполнению прямого хода метода Гаусса. Абсолютная величина этого определителя равна произведению главных элементов , k = , используемых на каждом шаге прямого хода. Знак определителя зависит от числа перестановок строк и столбцов, выполненных при выборе главных элементов.

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

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

Обратную матрицу А^-1 имеет любая квадратная матрица А, для которой detA 0. Пусть дана матрица А = [a_ij]_nn. Для вычисления элементов обратной матрицы используется соотношение

A A^-1 = A^-1 A = E,

где E - единичная матрица.

Обозначим обратную матрицу A^-1 = X = [x_ij]_nn. Тогда получим

A X = E.