Методические указания к выполнению лабораторной работе «решение систем линейных алгебраических уравнений» icon

Методические указания к выполнению лабораторной работе «решение систем линейных алгебраических уравнений»


Смотрите также:
Методические указания к выполнению лабораторной работы №5 «Исследование устойчивости линейных...
Методические указания к выполнению лабораторной работы №2 «Исследование частотных характеристик...
Решение систем линейных уравнений...
Решение систем линейных алгебраических уравнений...
Решение систем линейных алгебраических уравнений...
Решение систем линейных уравнений. Система линейных алгебраических уравнений (слау) имеет вид...
«О некоторых применениях алгебры матриц»...
Вопросы и билеты для государственного экзамена по специальности...
Прямые методы решения систем линейных алгебраических уравнений...
Методические материалы для студентов 1 2...
Методические указания к выполнению лабораторной работы по дисциплине...
Программа дисциплины ен. Ф. 01 «Математика. Численные методы» Специальность 032100 050201...



Загрузка...
скачать
Методические указания к выполнению лабораторной работе

«РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ»


по курсу «Вычислительная математика» для студентов специальности АСОИУ


ВВЕДЕНИЕ


В ряде практических задач управления и оптимизации приходится решать системы линейных алгебраических уравнений (СЛУ). В настоящей лабораторной работе изучается наиболее распространенный метод решения СЛУ – метод Гаусса.

Цель работы - ознакомление с методом Гаусса решения СЛУ.
Краткие теоретические сведения


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


ax+ax+…+ax=d,

ax+ax+...+ax=d, (1)

ax+ax+…+ax=d.

Систему (1) можно записать в матричном виде

Ax=d. (2)

Здесь А – матрица коэффициентов левых частей системы (1), а x и d – два n-мерных вектора:


d=, x=.


Систему небольшого порядка (n < 5) с невырожденной матрицей А можно решить, пользуясь формулами Крамера

x=, i=1, 2, …, n.

Здесь Δ – определитель матрицы А; – вспомогательный определитель, матрица которого получается из ^ А замещением i-го столбца столбцом d.

Чем больше порядок системы, тем менее выгодны – в смысле количества вычислительной работы – формулы Крамера по сравнению с другим методом. Это метод Гаусса, или метод последовательного исключения неизвестных. Он состоит из двух этапов: прямого хода и обратной подстановки. При прямом ходе система приводится к специальному – треугольному – виду, либо выясняется, что она несовместна или имеет бесконечно много решений. Прямой ход выполняется как последовательность шагов, их не более п–1, где п – порядок системы. Задача каждого шага – исключение из системы очередного неизвестного.

Предположим, что в системе (1) коэффициент aне равен нулю. Если бы это было не так, но зато a0, то мы поменяли бы местами 1-е и l-е уравнения. Составим отношения


li1=, i=2, 3, …, n,


называемые множителями 1-го шага; коэффициент aпри этом называется главным элементом 1-го шага. Умножая 1-е уравнение соответственно на l21, l31, …, ln1, вычтем его из 2-го, 3-го, ...., n-го. В результате придем к системе вида



ax+ax+ax+…+ax=d,

ax+ax+...+ax=d,

ax+ax+…+ax=d,

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

ax+ax+…+ax=d,


имеющей те же решения, что и система (1)

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


a=a-la, i, j=2, 3, …, n

(3)

d=d-ld, i=2, 3, …, n.


Первый шаг прямого хода закончен. Уравнения со 2-го по n-е составляют систему порядка п–1, в которой нет неизвестного xоно исключено, с чем и связано одно из названий метода.

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

Если несовместных уравнений в системе нет, то можно перейти ко второму шагу. Будем считать, что коэффициент a0; в противном случае мы переставили бы 2-е уравнение с одним из нижележащих, именно с тем, в котором присутствует x.

Составляем множители 2-го шага:


l=, i=3, 4, …, n.


Коэффициент a называется главным элементом второго шага. Вычитая из 3-го, 4-го, ..., n-го уравнений 2-е, умноженное соответственно на l,l,…,1п2, получим


ax+ ax+ ax+…+ ax=d ,

ax+ ax+…+ ax=d,

ax+…+ ax=d,

……………………………

ax+…+ax=d.


Для коэффициентов справедливы соотношения, аналогичные формулам (3):


a=a-la , i,j=3, 4, …, n,

(4)

d=d-ld, i=3, 4, …, n.


Уравнения новой системы, кроме первых двух, составляют систему порядка п–2, в которой нет неизвестных x и x; неизвестное x исключено на втором шаге. Продолжая таким образом, мы или установим, что система несовместна, или после исключения ko неизвестного (1< k< n) не найдем среди последних п–k уравнений ни одного с ненулевыми коэффициентами, и это означает, что решений у системы бесконечно много, или, наконец, после п–1 шагов получим треугольную систему уравнений:


ax+ax+…+ax+ax=d,

ax+…+ax+ax=d,

…………………………… (5)

a x+ax=d,

ax=d.


Прямой ход метода Гаусса закончен. Коэффициенты a, a,…, a, будучи главными элементами соответствующих шагов, не равны нулю согласно определению. Для невырожденной матрицы А не равен нулю и коэффициент a.

Обратной подстановкой называется следующий этап – решение треугольной системы (5). Из последнего уравнения делением на aполучаем значение неизвестного x. Подставляя его в (п–1)-е уравнение, можем определить значение x. Поднимаясь таким образом по системе, последовательно найдем значения всех неизвестных.

В методе Гаусса с выбором главного элемента среди элементов a mk находят главный, то есть наибольший по модулю в k-м столбце и перестановкой строк переводят его на главную диагональ, после чего делают исключения. Такая схема метода Гаусса позволяет уменьшить погрешность округления. Метод Гаусса с выбором главного элемента надежен и прост.

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

Представим матрицу ^ А в виде произведения нижней треугольной матрицы L и верхней U. Введем в рассмотрении матрицы

L= и U=.

Можно показать, что A=LU. Это и есть разложение матрицы на множители.


Рассмотрим метод Гаусса на примере решения системы


x 3 x – x = 4,

2 x+7 x+2 x= –9,

3 x+ 2 x4 x = 2.

Составим матрицу

.

Множители первого шага равны

l21=2; l31= – 3.

Умножаем первую строчку матрицы на множитель l21 и складываем со второй строчкой. Получим матрицу

.

Далее умножаем первую строчку матрицы на множитель l31 и складываем с третьей строчкой. В результате

.

Второй шаг:

l32= –11.

.

Обратная подстановка дает

x1= 0, x2= –1, x3= –1.


Решение системы с помощью LU-разложения сводится к последовательному решению систем с треугольными матрицами Ly=b и Ux=y.


Для примера рассмотрим систему

3x 4 x9 x + 5 x= –14,

–15x 12 x + 50 x16 x= –16,

–27x 36 x + 73 x + 8 x= 8,

9 x + 12 x10 x16 x= –16.

В матричном виде

A=.

Первый шаг. Вычислим множители

l21== – 5; l31== – 9, l41== 3

и выполним преобразование матрицы

.

Второй шаг. Вычислим множители

l32== 0; l42== 0.

Второй шаг не изменяет матрицы.

Третий шаг.

l43=.

и выполним преобразование матрицы

.

В результате получим матрицу U.

U=.

Матрица L

L=.

Легко вычислить решение системы Ly=b.

y = –14,

–5y + y = –16,

–9 y + y = 8,

3 y y + y = –16.


y1= –14, y2= –26, y3= 16, y4= 0.

Решением системы Ux=y является вектор x.

3x 4 x9 x + 5 x= –14,

8 x + 5 x + 9 x= –26,

–8 x + 53 x= 16,

x= 0.

x1= –8, x2= –2, x3= –2, x4= 0.

Решение системы методом Гаусса с выбором главного элемента по столбцу покажем на примере решения системы.

3x 4 x9 x + 5 x= –14,

–15x 12 x + 50 x16 x= 44,

–27x 36 x + 73 x + 8 x= 142,

9 x + 12 x10 x16 x= –76.

Максимальный по модулю элемент 1-го столбца a33=–27. Переставим первое и третье уравнения.

–27 x 36 x + 73 x + 8 x= 142,

–15 x 12 x + 50 x16 x= 44,

3 x 4 x9 x + 5 x= –14,

9 x + 12 x10 x16 x= –76.

В матричном виде

A=.

Первый шаг. Вычислим множители

l21== ; l31== , l41== .

и выполним преобразование матрицы

A=.

Второй шаг. Вычислим множители

l32== 0; l42== 0.

Второй шаг не изменяет матрицы.

Третий шаг. Максимальный по модулю элемент третьего столбца a43=. Переставим местами третье и четвертое уравнение.

A=.


l43=.

и выполним преобразование матрицы

A=.


Обратный ход. Из последнего уравнения находим

x4=0.

Из третьего уравнения находим

x3== – 2.

Из второго уравнения находим

x2== – 2.

Неизвестное x1 находим из первого уравнения

x1=∙(142 + 36∙( – 2) – 73∙( – 2) – 8∙0)= – 8.

Ответ

x1= –8, x2= –2, x3= –2, x4= 0.


ЗАДАНИЕ


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

  2. Ознакомиться по предлагаемой литературе с постановкой задачи решения СЛУ.

  3. Ознакомиться с алгоритмом решения СЛУ методом Гаусса.

  4. Ознакомиться с алгоритмом решения СЛУ методами, являющимися обобщениями метода Гаусса.

  5. Составить и отладить программу на языке высокого уровня, реализующую один из изученных алгоритмов (по указанию преподавателя).

  6. Оформить отчет по выполненной лабораторной работе.


^ СОДЕРЖАНИЕ ОТЧЕТА


Отчет должен содержать следующие обязательные части:

  1. Алгоритм решения задачи.

  2. Листинг текста программы на языке высокого уровня, реализующей один из построенных алгоритмов (по указанию преподавателя).

  3. Листинг протокола работы программы решения задачи, предложенной преподавателем.


^ КОНТРОЛЬНЫЕ ВОПРОСЫ


  1. Идея метода Гаусса.

  2. Последовательность действий прямого хода метода Гаусса.

  3. Содержание обратного хода метода Гаусса?

  4. Область применения и сущность метода прогонки.

  5. Необходимые условия устойчивости прогонки.


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


  1. Березин И.С. Методы вычислений / И.С. Березин, Н.П. Жидков. Т. 1. М.: Наука, 1966. Т. 2. М.: Физматгиз, 1962.

  2. Калиткин Н.Н. Численные методы / Н.Н. Калиткин. М.: Наука, 1978. 512 с.

  3. Демидович Б.П. Основы вычислительной математики / Б.П. Демидович, И.А. Марон. М.: Наука, 1970. 664 с.

  4. Икрамов Х.Д. Численные методы линейной алгебры / Х.Д. Икрамов. М.: Знание, 1987. 48 с.

  5. Волков Е.А. Численные методы / Е.А. Волков. М.: Наука, 1987. 248 с.




Скачать 136,49 Kb.
оставить комментарий
Дата03.10.2011
Размер136,49 Kb.
ТипМетодические указания, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

наверх