Решение систем линейных алгебраических уравнений

 

Методы решения систем линейных алгебраических уравнений делятся на две группы. К первой группе принадлежат так называемые точные, или прямые, методы - алгоритмы, позволяющие получить решение системы за конечное число арифметических действий. Сюда относятся известное правило Крамера нахождения решения с помощью определителей, метод Гаусса (метод исключений) и метод прогонки [13]. Правило Крамера при реализации на ЭВМ не применяется ввиду значительно большего по сравнению с методом Гаусса числа арифметических действий. Метод Гаусса используется при решении систем до порядка 10³. Метод прогонки применяется для решения важного класса специальных систем линейных уравнений с трехдиагональной матрицей, часто возникающей в практических приложениях.

Вторую группу составляют приближенные методы, в частности, итерационные методы решения систем линейных алгебраических уравнений, позволяющие решать системы до порядка 10⁶ [1], [4], [7], [13].

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

 

 

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

 

Рассматривается система линейных уравнений n -го порядка

(2.1)

.....

,

что в векторном виде записывается как .

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

(2.2)

......

,

из которого легко находятся неизвестные . Процесс приведения системы к виду (2.2) называется прямым ходом, а нахождение неизвестных - обратным ходом метода Гаусса.

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

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

,

где - i -е собственное число матрицы . Если большая, то матрица (система (2.1)) называется плохо обусловленной, в противном случае - хорошо обусловленной.

Лабораторная работа № 11

 

В ходе выполнения работы студенты должны найти решение системы линейных уравнений с n неизвестными, заданной матрицей коэффициентов и вектором свободных членов , методом Гаусса. Выполнение работы состоит из следующих этапов:

1) с помощью преподавателя определить систему уравнений, которую нужно решить;

2) для решения системы уравнений разработать программу на языке C, использующую подпрограмму-функцию GAUSS из файла GAUSS.CPP. Данная функция имеет следующие параметры:

- a - матрица коэффициентов системы уравнений размера , тип ;

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

- - выходной вектор результата решения размера , тип ;

- - размер системы (матрицы a и вектора свободных членов ), тип .

В разрабатываемой программе должна быть описана константа n max, равная максимальным размерам используемых матриц и векторов. Функция GAUSS в качестве значения типа возвращает:

а) 0 - в случае нормального завершения процесса вычисления;

б) 1 - в случае вырожденности матрицы а;

в) 2 - если ;

г) 3 - если .

Провести вычисления с использованием разработанной программы и исследовать обусловленность задачи с использованием пакета Matlab, при этом для определения числа обусловленности матрицы A рекомендуется использовать функцию cond(A) [14]. Кроме того, для проверки получаемых результатов можно провести вычисления с помощью пакетов Matlab и Derive [15].

 

 

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

Итерации

 

Рассматривается система уравнений вида

, (2.3)

где - заданная числовая квадратная матрица n -го порядка, а b - заданный вектор (свободный член). Метод простой итерации состоит в следующем. Выбирается произвольный вектор x (начальное приближение), и строится итерационная последовательность векторов по формуле

, (2.4)

где k =1, 2, …

Доказана теорема, что если норма , то система уравнений (2.3) имеет единственное решение и итерации (2.4) сходятся к решению со скоростью геометрической прогрессии [13]. Для оценки погрешности k -го приближения широко применяется неравенство

, (2.5)

которое может быть использовано для принятия решения об останове итерационного процесса при выполнении условия

,

где - некоторая заданная погрешность вычислений.

 

 

Лабораторная работа № 12

 

В работе студенты должны найти решение системы линейных уравнений с n неизвестными, заданной матрицей коэффициентов и вектором свободных членов b, методом простых итераций. Выполнение работы включает следующие этапы:

1) с помощью преподавателя определить систему уравнений, которую нужно решить. Привести исходную систему к виду (2.3), пригодному для использования метода простых итераций;

2) задать необходимую точность получения результата (количество знаков мантиссы числа);

3) разработать программу решения задачи на языке С с использованием подпрограммы-функции MITER из файла MITER.CPP. Функция MITER имеет следующие параметры:

- - матрица коэффициентов преобразованной к виду (2.3) системы уравнений размера , тип ;

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

- - полученный в результате проведения итераций вектор решения размера , тип ;

- - размер системы уравнений, тип ;

- - количество знаков после запятой в мантиссе результата, остающихся после округления, тип , ;

- it - выходной параметр, равный количеству произведенных итераций, тип int.

В качестве значения функции типа возвращается одно из следующих значений:

а) 0 - все нормально, получено решение ;

б) 1 - не выполняются условия сходимости итерационного процесса;

в) 2 - размер ;

г) 3 - значение .

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

4) произвести вычисления с использованием разработанной программы и построить график зависимости числа итераций от задаваемой точности.