Материал: Larin_Anton_8383_cm_21_11

Цель работы.

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

Основные теоретические положения.

Методы решения систем линейных алгебраических уравнений (СЛАУ)

делятся на две группы. К первой группе принадлежат так называемые точные,

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

Решение систем линейных алгебраических уравнений методом Гаусса Рассматривается СЛАУ -го порядка

11 1 + 12 2 + + 1 = 1,

{21 1 + 22 2 + + 2 = 2, ,

…… … … … … … … … … … … … … … …

1 1 + 2 2 + + =

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

Суть метода исключения по главным элементам (метод Гаусса)

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

уравнений и т.д. В результате система уравнений приводится к треугольному виду

2

из которого легко находятся неизвестные 1, … , . Процесс приведения системы к треугольному виду называется прямым ходом, а нахождение неизвестных

1, … , – обратным ходом метода Гаусса.

Следует отметить, что если матрица заданной системы вырожденная, то перед исключением некоторой неизвестной главный элемент окажется равным нулю, что и будет свидетельствовать о равенстве нулю определителя системы. Мерой обусловленности матрицы называют величину ( ) =− 1 , где – норма матрицы . Мера обусловленности равна максимально возможному коэффициенту усиления относительной погрешности от правой части к решению СЛАУ. Если матрица симметричная и выбрана вторая норма,

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

Решение систем линейных алгебраических уравнений методом простой итерации. Рассматривается система уравнений вида = + , где – заданная числовая квадратная матрица -го порядка, а – заданный вектор (свободный член). Метод простой итерации состоит в следующем. Выбирается произвольный вектор x (начальное приближение), и строится итерационная последовательность векторов по формуле ( ) = ( − 1) + , где = 1,2, …

Доказана теорема, что если норма < 1, то система уравнений имеет единственное решение и итерации сходятся к решению со скоростью геометрической прогрессии. Для оценки погрешности -го приближения широко применяется неравенство − ( ) 1− ( ) − ( −1) , которое может быть использовано для принятия решения об останове итерационного процесса

3

при выполнении условия 1− ( ) − ( −1) , где – некоторая заданная погрешность вычислений.

Постановка задачи.

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

вектором свободных членов b, методом Гаусса и/или методом простых итераций.

Порядок выполнения работы следующий:

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

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

3.Для метода Гаусса: провести вычисления с использованием разработанной программы и исследовать обусловленность задачи с использованием пакета MATLAB, при этом для определения числа обусловленности матрицы A рекомендуется использовать функцию cond(A).

Кроме того, для проверки получаемых результатов можно провести вычисления

спомощью пакета MATLAB.

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

Выполнение работы.

Возьмем в качестве примера систему

0.8143 0.1966 0.3517 0.9172 0.3804

(0.2435 0.2511 0.8308 0.2858 0.5678) 0.9293 0.6160 0.5853 0.7572 0.0759

0.3500 0.4700 0.5497 0.7537 0.0540

Программа разработана на языке Python, с live скриптом matlab для

удобства и проверки.

4

Для решения СЛАУ методом Гаусса разработана ф-я gauss, принимающая на вход матрицу вместе со столбцом свободных членов.

Была разработана программа на языке m, обеспечивающая ввод-вывод данных,

служащая оберткой над кодом на языке Python, и помогающая контролировать правильность работы основной программы путем решения идентичной СЛАУ методами среды matlab. Данная программа состоит из нескольких модулей.

Среди них:

Ввод данных из файла

Ручной ввод данных

Случайная генерация данных

Решение СЛАУ методами matlab

Решение СЛАУ при помощи программы на Python и сравнение результатов.

Также методами matlab осуществляется расчет числа обусловленности матрицы

A.

0.3064

Получаем вектор = (−1.33460.9785 ). Число обусловленности = 8.5669 0.0537

Код программы на Python представлен а приложении А, на m в приложении Б Было проведено исследование обусловленности метода Гаусса. В таб. 1.

приведены погрешность входных значений Delta и порядок погрешности результата Eps. Более подробные результаты можно получить при помощи программы приведенной в приложении Б.

Таблица 1 – Зависимость порядка точности результата от точности входных данных.