к выполнению лабораторной работы

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

по дисциплине "Вычислительная математика"

на тему "Метод Гаусса"

(теория и варианты заданий) для студентов специальностей

230102, 230104, направления 230100

Форма обучения очная и заочная

Ижевск 2009

Рецензент:

Исенбаева Е.Н. Методические указания к выполнению лабораторной работы по дисциплине «Вычислительная математика» на тему «Метод Гаусса» (теория и варианты заданий).- Ижевск: Издательство ИжГТУ, 2009 г.-24с.

В методических указаниях приведено описание метода Гаусса. Описан алгоритм получения и уточнения корней системы линейных алгебраических уравнений (СЛАУ), вычисления определителя и обратной матрицы с помощью метода Гаусса с постолбцовым выбором главного элемента. Рассмотрен вопрос анализа чувствительности СЛАУ к погрешностям входных данных. Приведены примеры реализации указанных алгоритмов. Методические указания содержат варианты заданий на лабораторную работу.

Рекомендовано к изданию на заседании кафедры «Автоматизированные системы обработки информации и управления» ИжГТУ (протокол №6 от 23.10.2009).

Учебное пособие предназначено для студентов очной и заочной формы обучения специальностей 230102, 230104, направления 230100.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ. 4

1. Общая характеристика методов решения линейных алгебраических задач. 5

2. Метод Гаусса.. 6

3. Метод Гаусса с постолбцовым выбором главного элемента 8

4................... УТОЧНЕНИЕ КОРНЕЙ, ПОЛУЧЕННЫХ МЕТОДОМ ГАУССА.. 9

5. ПРИМЕНЕНИЕ МЕТОДА ГАУССА К ВЫЧИСЛЕНИЮ ОПРЕДЕЛИТЕЛЕЙ 12

6. ПРИМЕНЕНИЕ МЕТОДА ГАУССА К ВЫЧИСЛЕНИЮ ОБРАТНОЙ МАТРИЦЫ 13

7. ОБУСЛОВЛЕННОСТЬ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ СИСТЕМ.. 16

8. ЗАДАНИЕ НА ЛАБОРАТОРНУЮ РАБОТУ.. 19

СПИСОК ЛИТЕРАТУРЫ.. 24

ВВЕДЕНИЕ

Данные методического указания предназначены для использования студентами при выполнении лабораторной работы на тему «Метод Гаусса. Решение систем линейных алгебраических уравнений (СЛАУ). Нахождение обратной матрицы» В пособии дается описание метода Гаусса с постолбцовым выбором главного элемента. Описан алгоритм получения и уточнения корней, а также алгоритм вычисления определителя и обратной матрицы с помощью метода Гаусса. Изучен вопрос анализа чувствительности СЛАУ к погрешностям входных данных. Описан алгоритм расчета показателя чувствительности систем линейных уравнений - condA. Все алгоритмы реализованы на конкретных примерах.

В работе приведены варианты заданий на лабораторную работу.

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

1. Общая характеристика методов решения линейных алгебраических задач

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

1) прямые методы – методы, приводящие к решению за конечное число арифметических операций. Если операции реализуются точно, то и решение будет точным. Поэтому другое название этой группы методов – точные методы. К прямым методам относятся метод Гаусса и его модификации, метод Крамера, метод LU-разложения и др.

2) итерационные методы – методы, в которых решение может быть получено с заданной точностью путем бесконечного повторения единообразных действий. К итерационным (приближенным) методам относятся метод простых итераций, метод Зейделя, метод релаксации, Шульца.

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

Метод Гаусса оказывается гораздо более экономичным. Алгоритмическая сложность этого метода имеет порядок ³.

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

В данном методическом пособии рассматривается прямой метод решения – метод Гаусса и его модификация – метод Гаусса с постолбцовым выбором главного элемента.

2. Метод Гаусса

Пусть дана система линейных уравнений с неизвестными:

(1)

Запишем систему (1) в матричном виде:

(2)

где - - матрица;

- вектор – столбец неизвестных;

- вектор – столбец правых частей.

Метод Гаусса состоит в последовательном исключении неизвестных системы путем ее равносильного преобразования. При этом в численных методах с целью хорошей алгоритмизации задачи преобразованию подвергаются не сами уравнения, а исходные данные – матрица A и вектор правых частей b, соединенных в одну расширенную матрицу. Метод имеет прямой и обратный ход.

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

1) каждый элемент строки, в которой находится ведущий элемент (a₁₁– в первой строке на первом шаге, a₂₂ – во второй строке на втором шаге…) делится на ведущий элемент. При этом предполагается, что ведущие элементы отличны от нуля.

2) исключаются элементы столбцов, лежащие ниже ведущих строк. Для исключения элементов первого столбца используется первая ведущая строка, для элементов второго столбца – вторая…

Формулы пересчета прямого хода:

(3)

где k=1,2,…,n-1, k – номер шага,

i=k+1,…,n;

j=k+1,…,n.

По определению полагаем

, .

Обратный ход позволяет последовательно одно за другим вычислять значения неизвестных, начиная с последнего. Для этого переходим к системе, включающей х₁, х₂,…,х_n.

(4)

3. Метод Гаусса с постолбцовым выбором главного элемента

Реальные математические расчеты производятся с приближенными числами, т.е. неизбежны ошибки округлений. Знаменатель дроби в формуле (3) может оказаться равным нулю или очень маленьким числом. В результате выполнение алгоритма может прекратиться или будет получен результат, далекий от реального. Чтобы избежать этой ситуации, на каждом шаге прямого хода строки рассматриваемой матрицы переставляют так, чтобы деление производилось на наибольший по модулю в обрабатываемом подстолбце элемент. Числа, на которые производится деление, называются ведущими или главными элементами. Соответственно, метод Гаусса, исключающий деление на ноль и уменьшающий влияние ошибок округлений, - это метод Гаусса с постолбцовым выбором главного элемента.

4. УТОЧНЕНИЕ КОРНЕЙ, ПОЛУЧЕННЫХ МЕТОДОМ ГАУССА

Пусть для системы найдено приближенное решение х₀.

Полагая

для уточнения корня будем иметь уравнение:

(5)

где - (6)

невязка для приближенного решения х₀.

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

Пример 1. Найти решение СЛАУ методом Гаусса с постолбцовым выбором главного элемента. Произвести уточнение решения.

; .

Решение произведем в табличном виде:

a_i1	a_i2	a_i3	b_i
2,6 3,0	-4,5 3,0 3,5	-2,0 4,3 3,0	19,07 3,21 -18,25	-0,007 -0,011 0,016
3,0 2,6	3,5 3,0 -4,5	3,0 4,3 -2,0	-18,25 3,21 19,07	0,016 -0,011 -0,007
	-0,583 -2,983	-0,5 5,8 -0,7	3,042 -5,915 11,162	-0,0027 -0,003 -0,0001
	-0,583	-0,5 1,221	3,042 1,245 7,447	-0,0027 0,0006 -0,002
	-0,583	-0,5 1,221	3,042 -1,245 2,531	-0,0027 -0,0006 -0,0007

Для обратного хода перейдем к системе, включающей неизвестные х_i, и последовательно одно за другим вычисляем их значения, начиная с х₃.

Итак, вектор решения:

Уточним решение. Для этого полученный вектор решения х будем считать начальным приближение х₀. Подставим его в исходную схему и найдем невязку по формуле (6).

Полученный вектор невязок используем как новый свободный член системы Аδ= ε, приписывая его как столбец к основной схеме вычислений. Решая СЛАУ с прежней матрицей А и новым свободным членом , получаем вектор поправок неизвестных:

Уточняем решение по формуле

Уточненный вектор решения:

5. ПРИМЕНЕНИЕ МЕТОДА ГАУССА К ВЫЧИСЛЕНИЮ ОПРЕДЕЛИТЕЛЕЙ

Метод Гаусса может быть использован при вычислении определителей. Преобразования прямого хода, приводящие матрицу А к верхнетреугольному виду, не изменяют определителя матрицы А. Учитывая, что определитель треугольной матрицы равен произведению диагональных элементов, имеем:

Таким образом, detA равен произведению всех ведущих элементов.

При использовании модификации метода Гаусса с постолбцовым выбором главного элемента производится перестановка строк матрицы, что может изменить знак detА. Поэтому в результате нужно учесть четность количества перестановок:

где - количество перестановок строк.

Найдем определитель для матрицы А из Примера 1 главы 4:

det A = (-1)¹*(-6,0)*4,75*2,942= 83,847

6. ПРИМЕНЕНИЕ МЕТОДА ГАУССА К ВЫЧИСЛЕНИЮ ОБРАТНОЙ МАТРИЦЫ

Пусть дана матрица Для нахождения обратной матрицы будем использовать основное соотношение , где Е – единичная матрица n -го порядка. Т.е. будем исходить из того, что обратная матрица является решением матричного уравнения:

(7)

Представляя искомую матрицу , как набор векторов-столбцов:

а единичную матрицу Е как набор единичных векторов:

…,

матричное уравнение (7) в соответствии с правилами умножения матриц заменяем эквивалентной системой векторно-матричных уравнений:

…, . (8)

Каждое из последних уравнений имеет вид (1) и может быть решено методом Гаусса. Все СЛАУ (8) имеют одну и ту же матрицу коэффициентов, но разные правые части, составляющие единичную матрицу. В результате завершения работы алгоритма будут получаться столбец за столбцом элементы обратной матрицы . Заметим, что элементы строк обратной матрицы получаются в обратном порядке.

Пример 2. Решить систему линейных уравнений методом Гаусса. Уточнить решение. Найти определитель и обратную матрицу , включив процесс в общий алгоритм метода Гаусса.

НАХОЖДЕНИЕ ОБРАТНОЙ МАТРИЦЫ МЕТОДОМ ГАУССА.

a_i1	a_i2	a_i3	b_i	E_i	e₁	e₂	e₃
1,15 1,00	0,42 0,55 0,35	100,71 0,32 3,00	-198,70 2,29 -0,65	0,00035 0,00014 -0,00000
	0,46218 -0,11151	0,26891 100,40076 2,73109	1,92437 -200,91303 -2,57437	0,00012 0,00021 -0,00012		0,84034 -0,96639 -0,84034
	0,46218	0,26891 -24,34141	1,92437 22,94486 -198,35474	0,00012 0,00107 0,00033		0,84034 7,49100 -0,13107	-8,91424 -0,99403
	0,46218	0,26891 -24,34561	1,92437 22,94856 -2,03053	0,00012 0,00107 0,00000	0,01024	0,84034 7,49100 -0,00134	-8,91424 -0,01018

*Используя постолбцовый выбор главного элемента:

- на первом шаге меняем строки 1 и 2;

- на втором шаге меняем строки 2 и 3.

Решение:

Определитель:

Вектор поправок:

Уточненное решение:

Находим обратную матрицу :

Обратная матрица :

7. ОБУСЛОВЛЕННОСТЬ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ СИСТЕМ

Рассмотрим СЛАУ в векторно-матричной форме:

, (9)

где А – невырожденная - матрица коэффициентов данной системы;

b – ненулевой n -мерный вектор свободных членов;

– n -мерный вектор неизвестных.

Пусть правая часть (9) получила приращение Реакцией решения х на возмущение будет вектор поправок , т.е. если х – решение (9), то - решение уравнения

. (10)

Понимая под абсолютной погрешностью приближенного вектора норму разности между точным и приближенным векторами, а под относительной погрешностью – отношение абсолютной погрешности к норме вектора (точного или приближенного), найдем связь между относительными погрешностями вектора свободных членов и вектора – решения. Т.е. получим оценку вида: ,

где - какая-либо векторная норма,

К – неизвестный коэффициент связи.

Подставляя (9) в (10), получаем, что поправка связана с возмущением аналогичным (9) равенством: , из которого находим ее явное выражение:

(11)

Нормируя равенства (9) и (11), получим

где матричная норма должна быть согласованной с выбранной векторной нормой. Подробно о нормах рассказывается в методических указаниях по выполнению лабораторной работы «Итерационные методы решения СЛАУ».

Перемножим полученные неравенства (9), (11)

Разделив полученное неравенство на получим искомый коэффициент связи К:

(12)

Положительный коэффициент называют числом обусловленности матрицы А и обозначают .

Аналогично, можно показать, что то же самое число служит коэффициентом роста относительных погрешностей при неточном задании элементов матрицы А в (9).

Итак, неравенство (12) показывает, что чем больше число обусловленности, тем сильнее сказывается на решении СЛАУ ошибка в исходных данных. Если число велико, то система считается плохо обусловленной. На величину влияет размерность задачи, точность, с которой должно быть найдено ее решение, точность предоставления чисел в ЭВМ и т.д. Для современных ЭВМ диапазон хорошо обусловленных СЛАУ находится в диапазоне: .

Поясним понятие обусловленности на примере двумерной задачи.

Решением этой задачи будет вектор , компоненты которого определяются координатами точки пересечения двух прямых.

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

Пример 3.

Исследовать обусловленность СЛАУ:

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

Найдем обратную матрицу А^-1. Одновременно найдем решение СЛАУ в рамках алгоритма метода Гаусса.

a_i1	a_i2	b_i	e₁	e₂
	-5 -4,9999
	-2,50 0,0001	0,5	0,5 -1
		0,5	-10000 -24999,5

Найдем норму-максимум матриц и : . , следовательно, СЛАУ плохо обусловлена и будет чутко реагировать на небольшие погрешности входных данных. Этот вывод можно подтвердить, придав небольшое возмущение правой части второго уравнения СЛАУ:

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

ЗАДАНИЕ НА ЛАБОРАТОРНУЮ РАБОТУ

Написать программу, реализующую алгоритм метода Гаусса. В программе требуется:

1. решить систему Ax=b. Решить систему методом Гаусса. Предусмотреть постолбцовый выбор главного элемента;

2. произвести итерационное уточнение решения до достижения точности Е= 10^-12 по евклидовой норме невязки в рамках применяемой схемы реализации метода;

3. найти определитель матрицы А;

4. найти обратную матрицу X= A^-1, решая подсистемы Ах ^j =е ^j системы АХ=Е;

5. вычислить condA в различных простых нормах и охарактеризовать чувствительность данной системы к погрешностям исходных данных.

В отчете по лабораторной работе должны быть представлены следующие разделы:

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

2. Математическая модель.

3. Текст программы.

4. Результаты работы.

5. Выводы.

Лабораторная работа выполняется на любом языке высокого уровня.

Варианты заданий на лабораторную работу

1. ; .