Численные методы линейной алгебры (стр. 2 из 3)
3. Вычислить элементы матрицы L по правилам
Расчетные формулы для решения системы (6) имеют следующий вид:
y1 = b1 / l11;
Расчетные формулы для решения системы (7)
xn = yn;
(i = n - 1, n - 2, …, 1).3. Метод прогонки
Метод прогонки представляет собой простой и эффективный алгоритм решения систем линейных алгебраических уравнений с трехдиагональными матрицами коэффициентов следующего вида
(8)Системы такого вида часто возникают при решении различных инженерных задач, например, при интерполяции функций сплайнами.
Преобразуем первое уравнение системы (8) к виду x1 = a1x2 + b1, где
a1 = -с1 / b1 и b1 = -d1 / b1. Подставим полученное для x1 выражение во второе уравнение системы (8)
a2(a1x2 + b1) + b2x2 + c2x3 = d2.
Представим это уравнение в виде x2 = a2x3 + b2, где a2 = -с2 / (b2 + a2a1) иb2 = (d2 - a2b1) / (b2 + a2a1). Полученное для x2 выражение подставим в третье уравнение системы (8) и т.д.
На i-м шаге (1 < i < n) процесса i-е уравнение системы принимает вид
xi = aixi+1 + bi, (9)
гдеai = -сi / (bi + aiai-1) иbi = (di - aibi-1) / (bi + aiai-1).
На последнем n-м шаге подстановка в последнее уравнение системы (8) выражения xn-1 = an-1xn + bn-1 дает уравнение an(an-1xn + bn-1) + bnxn = dn, из которого можно определить значение xn = bn = (dn – anbn-1) / (bn + anan-1).
Значения остальных неизвестных xi (i = n-1, n-2, ..., 1) легко вычисляются по формуле (9).
Таким образом, алгоритм прогонки, подобно методу Гаусса, включает два этапа – прямой ход (прямая прогонка) и обратный ход (обратная прогонка).
Прямой ход метода прогонки состоит в вычислении прогоночных коэффициентов
ai (i =
) и bi (i = 
).При i = 1 эти коэффициенты вычисляются по формулам:
a1 = -с1 / g1; b1 = -d1 / g1; g1 = b1.
Для i =
используются следующие рекуррентные формулы:ai = -сi / gi; bi = (di - aibi-1) / gi; gi = bi + aiai-1.
Прямая прогонка завершается при i = n:
bn = (dn – anbn-1) / gn; gn = bn + anan-1.
Обратный ход метода прогонки позволяет вычислить значения неизвестных. Сначала полагают xn = bn. Затем в обратном порядке по формуле (9) определяют значения неизвестных xn-1, xn-2, ..., x1.
Свойства метода прогонки. Трудоемкость метода прогонки оценивается примерно как 8n арифметических операций, что существенно меньше метода Гаусса. Существование решения системы (8) и его единственность гарантируются при выполнении достаточных условий, задаваемых следующей теоремой.
Теорема [2]. Пусть коэффициенты системы (8) удовлетворяют следующим неравенствам
ïbkï³ïakï+ïckï; ïbkï>ïakï; k =
, где a1 = 0; bn = 0. Тогда gi¹ 0 и ïaiï£1 для всех i =
Заметим, что при всех gi¹ 0 вычисления по формулам прямой прогонки могут быть доведены до конца (ни один из знаменателей не обратится в нуль). Одновременно все коэффициенты ai, такие, что ïaiï£ 1, обеспечивают устойчивость по входным данным этапа обратной прогонки по формуле (9).
4. Вычисление определителей
Идея последовательного исключения переменных, реализованная в методе Гаусса, может быть использована при вычислении определителей. При этом используются следующие свойства определителей:
1) перестановка двух строк или столбцов определителя не изменяет его абсолютной величины, но меняет знак на противоположный;
2) умножение всех элементов одной строки или одного столбца на любое число равносильно умножению определителя на это число;
3) если к элементам некоторой строки (столбца) определителя прибавить соответствующие элементы другой строки (столбца), умноженные на любой общий множитель, то величина определителя не изменится.
Пусть задан определитель
Выберем главный элемент a11 ¹ 0. Если a11 = 0, то выполним перестановку двух строк или столбцов этого определителя, чтобы получить a11 ¹ 0.
Вынесем главный элемент a11 из первой строки за знак определителя
Используя процедуру прямого хода метода Гаусса, преобразуем полученный определитель таким образом, чтобы в первом столбце под единицей были бы все нули. При этом величина определителя не изменится.
Разложим полученный определитель по элементам первого столбца, что даст понижение его порядка определителя на единицу
Повторим указанную процедуру (n - 1) раз и окончательно получим
Если при вычислении определителя производилась перестановка строк или столбцов (для выбора главного элемента), то
где s – количество выполненных перестановок.
Таким образом, вычисление определителя detA некоторой матрицы A сводится к выполнению прямого хода метода Гаусса. Абсолютная величина этого определителя равна произведению главных элементов
, k = 
, используемых на каждом шаге прямого хода. Знак определителя зависит от числа перестановок строк и столбцов, выполненных при выборе главных элементов.Если такие перестановки не производились, то величина определителя также может быть вычислена как произведение диагональных элементов матрицы L, формируемой в процессе LU-разложения исходной матрицы А
5. Вычисление обратных матриц
Обратную матрицу А-1 имеет любая квадратная матрица А, для которой detA ¹ 0. Пусть дана матрица А = [aij]n´n. Для вычисления элементов обратной матрицы используется соотношение
A A-1 = A-1 A= E,
где E – единичная матрица.
Обозначим обратную матрицу A-1 = X = [xij]n´n. Тогда получим
A X= E.
Будем рассматривать столбцы матрицы X как векторы
… 
Аналогично выделим столбцы единичной матрицы E
…; 
Тогда система линейных уравнений вида
A
= 
позволяет определить элементы k-го столбца обратной матрицы X = A-1. Всего потребуется решить n таких систем с одинаковой матрицей A, но разными правыми частями
для k = . Это можно сделать с использованием LU-разложения матрицы коэффициентов A, либо непосредственно с помощью метода Гаусса.6. Итерационные методы
При решении систем уравнений высокого порядка
с разреженными матрицами коэффициентов, которые характерны для большинства задач автоматизации проектирования сложных систем, наиболее эффективно применение итерационных методов. Такие методы (например, последовательных приближений и Зейделя) позволяют получать значения корней системы с заданной точностью в виде последовательности 
некоторых векторов, сходящихся к точному решению X*. Эффективность применения итерационных методов зависит от удачного выбора начального приближения
и скорости сходимости процесса вычислений.