- •Часть I
- •Введение
- •1. Метод Гаусса
- •1.1. Описание метода Гаусса
- •1.2. Норма матриц и обусловленность
- •1.4. Задание
- •1.5. Порядок выполнения работы на компьютере
- •Порядок выполнения работы
- •1.5. Содержание отчета
- •2. Метод lu-разложения и метод Холесского для решения слау
- •2.1. Алгоритм lu-разложения
- •2.2. Алгоритм треугольного разложения положительно определенных симметричных матриц и его применение для решения слау
- •2.4. Задание
- •2.5. Порядок выполнения работы на компьютере
- •Порядок выполнения работы
- •2.5.2. Разложение Холесского
- •2.6. Содержание отчета
- •3. Метод прогонки
- •3.1. Описание метода прогонки
- •3.3. Задание
- •3.4. Порядок выполнения работы на компьютере
- •Порядок выполнения работы
- •3.5. Содержание отчета
- •Библиографический список
№ 3225
Министерство образования Российской Федерации
Таганрогский государственный радиотехнический университет
РУКОВОДСТВО
К ЛАБОРАТОРНЫМ РАБОТАМ
по численным методам курса высшей математики
Часть I
Прямые методы
решения систем линейных алгебраических уравнений
Таганрог 2002
518.12(076.5)
УДК 512.64
Составители: Сухинов А.И., Афонин А.А., Тетруашвили Е.В., Марченко А.Г.
Руководство к лабораторным работам по численным методам курса высшей математики. /Часть 1. Таганрог: Изд-во ТРТУ, 2002. 47 с.
Методическое руководство предназначено для студентов второго курса всех специальностей, изучающих численные методы. Целью работы является обучение студентов работе с задачами, требующими большого объема вычислительной работы, с использованием универсальных решающих программ типа MathCAD. Руководство содержит описание методов, варианты заданий и порядок работы на ПЭВМ, а также контрольные вопросы для самопроверки.
Рецензент: В.К. Гадельшин, канд. техн. наук, доцент кафедры ВМ ТРТУ
Введение
Весь материал разбит на 3 лабораторные работы. На каждом занятии студент получает индивидуальное задание, которое выполняет самостоятельно под руководством преподавателя. Варианты заданий приведены в конце каждой лабораторной работы. Там же приведен порядок выполнения работы, показаны соответствующие способы решения поставленных задач с помощью пакета MathCAD, даны содержание отчета и контрольные вопросы. После выполнения каждой лабораторной работы студент должен сделать выводы.
Методы решения систем линейных алгебраических уравнений делятся на две группы: прямые (точные) и итерационные. Прямые методы теоретически позволяют за конечное число операций (действий) найти “точное” решение системы. Однако в условиях вычислений на компьютерах, имеющих конечную разрядную сетку, прямые методы позволяют найти реально лишь приближенное решение системы, ввиду наличия погрешностей округления. Примерами прямых методов, рассматриваемых ниже, является метод Гаусса и его модификации.
Другая группа методов – итерационных методов позволяет найти последовательность приближений , сходящихся к точному решению при , т.е. . Поскольку бесконечные процессы нереализуемы на практике, то обычно выполняется конечное число итераций, т.е. строится конечное множество векторов x(1), x(2),… x(k), причем, задаваясь некоторым малым числом (погрешностью решения), добиваются, чтобы , где некоторая норма вектора.
1. Метод Гаусса
1.1. Описание метода Гаусса
Рассмотрим систему линейных алгебраических уравнений
Ax=b, (1.1)
где – вектор неизвестных; – вектор свободных членов; , – невырожденная матрица размерами .
В силу невырожденности матрицы A для однородной системы уравнений с вектором правых частей имеем единственное тривиальное решение . Для неоднородной системы имеем единственное решение , где A-1 – матрица, обратная A.
В курсе высшей математики решение СЛАУ (1.1) обычно выражают по формулам Крамера в виде отношений определителей. Для решения СЛАУ больших порядков эти формулы непригодны, т.к. требуют вычисления (n+1) определителей, а вычисление каждого определителя требует числа арифметических действий порядка n!. В силу того, что n! чрезвычайно быстро растет с увеличением n, решение СЛАУ, например, порядка 100 по формулам Крамера не может быть получено за приемлемое время ни на одной из существующих ЭВМ. На практике требуется решать СЛАУ порядка n=103 и выше. Другая причина неприменимости формул Крамера на ЭВМ – катастрофический рост ошибок округления, называемый численной неустойчивостью. Алгоритм метода исключения неизвестных был изобретен в 3 веке до нашей эры, хотя и носит имя Гаусса. Идея алгоритма состоит в приведении СЛАУ к эквивалентной ей системе с треугольной матрицей (прямой ход исключения), а затем к нахождению неизвестных последовательными подстановками (обратный ход). Данный метод требует числа арифметических операций порядка . Он используется для решения СЛАУ с . Объединим матрицу А и вектор b в расширенную матрицу размерами n(n+1), которая содержит всю известную информацию о системе (1.1).
.
Опишем вначале прямой ход, первый шаг которого состоит в обнулении всех элементов первого столбца матрицы , кроме того, что находится в первой строке.
Введем обозначение для i-й строки матрицы
.
C матрицей можно обращаться так же, как с исходной системой (1.1), например, осуществлять элементарные преобразования. В качестве последних будем использовать перестановки строк, прибавление к элементам данной строки элементов какой-либо другой строки, умноженных на одно и то же число. Найдем ненулевой элемент в первом столбце матрицы . Такой элемент найдется всегда ибо, в противном случае, весь первый столбец состоит из нулей и матрица – вырожденная. Пусть , тогда поменяем местами строки номера r и 1. Если , то, естественно, перестановка не требуется. Затем вычтем из каждой строки номера i, первую строку, умноженную на число , где
.
В результате все элементы i-ой строки изменят свои значения и эта строка принимает следующий вид:
.
В итоге матрица принимает вид
. (1.2)
Тот же алгоритм может быть применен на втором шаге к - матрице, которая получается из , если убрать в ней первую строку и первый столбец.
Применение этого алгоритма j раз приводит к матрице
.
В матрице полученные нули располагаются в столбцах с номерами от 1 до j ниже диагонали. Эти нули сохраняются во время следующих шагов алгоритма.
В результате применения алгоритма n раз система (1.1), в конечном счете, преобразуется в
Rx=C, (1.3)
где R – верхняя (правая) треугольная матрица, т.е.
. (1.4)
Значения неизвестных можно вычислить из (1.4) по формулам
,
, . (1.5)
Процесс приведения системы (1.1) к треугольному виду (1.3) называется прямым ходом, а нахождение неизвестных по формулам (1.5) называется обратным ходом.
Произведем подсчет числа арифметических операций в методе Гаусса. Число арифметических операций, необходимое для реализации прямого хода в методе Гаусса для решения систем уравнений порядка n, равно
. (1.6)
При обратном ходе
. (1.7)
Из формул (1.6) и (1.7) получаем оценку общего числа арифметических действий
.
Если имеется p систем вида (1.1) с одинаковыми матрицами A и разными правыми частями b1, b2, …, bp, то целесообразно прямой ход осуществлять для всех систем одновременно, для чего следует вместо одной правой части, задаваемой вектором-столбцом, производить операции над p правыми частями (матрицей порядка ). Количество арифметических операций, необходимое для реализации прямого хода метода Гаусса с учетом (1.6) и (1.7), есть
.
Количество арифметических операций, необходимое для реализации p обратных ходов (для p систем) методом Гаусса, есть , откуда следует, что общее количество арифметических операций, необходимое для реализации p систем с разными правыми частями, равно
.