Лабораторная работа
Решение систем линейных алгебраических уравнений (СЛАУ)
1. Краткое описание используемых методов
Прямые (точные) методы
Метод Гаусса
Данный метод также называется методом последовательного исключения неизвестных. Он относится к группе прямых методов и основан на преобразовании исходной системы к эквивалентной форме с треугольной матрицей коэффициентов.
Исходная система
(1)
или A*x=B
При использовании метода Гаусса задача решается в два этапа:
1) прямой ход;
2) обратный ход.
Прямой ход заключается в преобразовании системы к треугольному виду.
При обратном ходе производится вычисление значений неизвестных.
Прямой ход метода Гаусса. Для получения расчетных формул прямого хода преобразуем исходную систему (1), заменив элементы bi (
) на ai,n+1. В результате система (1) будет иметь следующий вид
(2)
Прямой ход выполняется за (n-1) шагов, причем на каждом шаге из уравнений с номерами k + 1, k + 2, …, n исключается неизвестное xk.
На первом шаге сначала первое уравнение делится на a11 ¹ 0. Получим
(3)
где 
Затем из каждого оставшегося уравнения вида
(
)
вычитается полученное уравнение (3), умноженное на коэффициент ai1. В итоге, после выполнения первого шага прямого хода система уравнений примет следующий вид
(4)
где
На втором шаге указанные выше действия повторяются над (n - 1) уравнениями системы (4), всеми кроме первого, с целью исключения переменной x2, где 
.
В итоге получим
где
Повторяя шаги прямого хода (n - 1) раз, окончательно получим систему уравнений треугольного вида
(5)
где
При программной реализации прямого хода используется расширенная матрица коэффициентов A¢
,
для которой элементы имеют следующий смысл
1) 
- начальные значения;
2) 
- промежуточные значения;
3) 
- конечные значения.
Для определения элементов 
матрицы A¢ на некотором k-ом шаге
(
)
используются следующие расчетные формулы
Обратный ход метода Гаусса. После приведения исходной системы уравнений (1) к треугольному виду (5) вычисляются значения корней по следующим формулам
Таким образом, расчетные формулы обратного хода имеют вид
Итерационные методы
При решении систем уравнений высокого порядка 
с разреженными матрицами коэффициентов, которые характерны для большинства задач автоматизации проектирования сложных систем, наиболее эффективно применение итерационных методов. Такие методы (например, последовательных приближений и Зейделя) позволяют получать значения корней системы с заданной точностью в виде последовательности
некоторых векторов, сходящихся к точному решению X*. Эффективность применения итерационных методов зависит от удачного выбора начального приближения 
и скорости сходимости.
Для реализации итерационных методов требуется меньшее количество вычислительных операций (около n2) и соответствующих затрат машинного времени. Важным преимуществом итерационных методов также является несущественное влияние погрешностей вычислений, так как любое ошибочное приближение может рассматриваться как новый начальный вектор.
Метод Якоби (итераций)
Пусть дана система линейных уравнений, для которой диагональные элементы
.
Тогда переменную x1 можно выразить через первое уравнение, 
- через второе уравнение и т. д.
(6)
где 
и 
Система (6) называется системой линейных уравнений, приведенной к нормальному виду. Матричная форма записи такой системы представляется как
(7)
где
При решении системы (11) за нулевое приближение корней может быть принят столбец свободных членов, т.е. 
. Любое k-е приближение (
вычисляется по формуле
Если последовательность приближений , 
, 
,..., 
,... имеет предел 
, то этот предел является точным решением системы уравнений (1). Вычисления продолжаются до тех пор, пока значения 
не станут достаточно близкими к 
для всех 
или невязки 
не станут близкими к нулю. Формальное условие прекращения итерационного процесса записывается как
(12)
где e - некоторое малое положительное число, характеризующее точность (погрешность) определения корней системы уравнений или, с использованием невязок,
(13)
Метод Зейделя
Метод Зейделя представляет собой модификацию метода Якоби. При определении значения переменной 
на некоторой (k+1)-й итерации используются уже вычисленные (k+1)-е приближения неизвестных 
, 
,..., 
, а также значения 
полученные на предыдущей k-й итерации.
Пусть дана линейная система уравнений (10). Выбранные начальные приближения корней 
подставляются в первое уравнение
Для определения 
полученное значение 
сразу же подставляется во второе уравнение системы
Аналогично определяются приближения корней 
. Значение 
вычисляется с использованием первых приближений всех переменных 
как
В общем случае получение значений неизвестных 
по методу Зейделя на некоторой k-ой итерации производится по следующей формуле
При использовании обозначений исходной системы уравнений (1) итерационная формула обычно записывается как
Условия завершения итерационного процесса по методу Зейделя также формулируется в виде соотношений (12) или (13). При этом, как правило, процесс сходится к единственному решению быстрее, чем при использовании метода Якоби.
Условия сходимости итерационных процессов. Пусть дана приведенная к нормальному виду система (11) линейных уравнений. Итерационные процессы последовательных приближений и Зейделя для системы (11) сходятся к единственному решению независимо от выбора начального приближения, если выполняется хотя бы одно из следующих условий
Приведенные соотношения означают, что сумма модулей элементов любой строки или любого столбца матрицы a должна быть меньше единицы.
Таким образом, для сходимости указанных итерационных процессов достаточно, чтобы значения элементов aij матрицы a при i ¹ j были небольшими по абсолютной величине. Можно показать, что для линейной системы вида (2) итерационные процессы последовательных приближений и Зейделя сходятся к точному решению X*, если для всех уравнений системы модули диагональных коэффициентов исходной системы удовлетворяют условиям
и по крайней мере для одного из уравнений выполняется соотношение
Для обеспечения сходимости систему (2) всегда можно заменить такой эквивалентной системой нормального вида (11), которая удовлетворяет условиям сходимости итерационных процессов. Для этого используются следующие элементарные преобразования:
1) перестановка двух строк или столбцов;
2) умножение всех элементов какой-либо строки на одно и то же число, отличное от нуля;
3) сложение элементов какой-либо строки с соответствующими элементами другой строки, умноженными на одно и то же число.
Метод релаксации
Простейшее объяснение метода релаксации следующее. Практически все итерационные методы характеризуются следующим рекуррентным соотношением
,
где 
, 
-результаты последующей и предыдущей итераций;
-некоторые приращения, зависящие от применяемого метода. В методе релаксации эти приращения умножаются на некоторую константу 
, называемую параметр релаксации, то есть
. (14)
Теоретически изменяется от 0 до 2, при >1-это метод верхней релаксации, при 
<1-соответственно метод нижней релаксации.
В неявном виде методы Якоби и Зейделя описываются выражением
Для явного выражения приращений вычтем из обеих частей
. Тогда
Или
(15)
Тогда
(15)
Подставив (15) в (14) после преобразований окончательно получим
В большинстве случаев параметр определяется опытным путем из условия минимума итераций.
2. Указания по выполнению работы
1). Ознакомиться с методами решения СЛАУ;
2). Ввести документ Mathcad;
4). Согласно своему номеру варианта из таблицы вариантов ввести коэффициенты матрицы и столбец свободных членов;
5). Получить корни прямыми методами;
6). Перед применением итерационных методов проверить условие сходимости. При его невыполнении поменять местами строки матрицы согласно примеру;
7). Получить решение итерационными методами с невязками 10-5 , 10-10 ,
10-15 , выведя значения корней и количество итераций.
8). Проанализировать скорости методов.
Текст документа Mathcad
Исходная система в матричной форме Ax=B
