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




Скачать 127.13 Kb.
НазваниеМетодические указания к выполнению лабораторной работе
Дата конвертации26.05.2013
Размер127.13 Kb.
ТипМетодические указания
Методические указания к выполнению лабораторной работе

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


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


ВВЕДЕНИЕ


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

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


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


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 с.

Добавить в свой блог или на сайт

Похожие:

Методические указания к выполнению лабораторной работе iconМаятник обербека для определения характеристик вращательного движения твёрдого тела методические указания к лабораторной работе по физике Минск 2 0 0 8 удк 531. 38 (075. 8) Ббк 22. 213я7 и 98
Методические указания предназначены для самостоятельной подготовки студентов к выполнению лабораторной работы

Методические указания к выполнению лабораторной работе iconМетодические указания к лабораторной работе по физике для студентов строительных специальностей Минск 2007
Методические указания предназначены для самостоятельной подготовки студентов к выполнению лабораторной работы

Методические указания к выполнению лабораторной работе iconМетодические указания к лабораторной работе
Выбор задачи для решения в курсовом проекте: Методические указания к лабораторной работе / О. Е. Александров Екатеринбург: угту-упи,...

Методические указания к выполнению лабораторной работе iconМетодические указания к лабораторной работе
Поиск литературных источников по теме курсового проектирования: Методические указания к лабораторной работе / О. Е. Александров...

Методические указания к выполнению лабораторной работе iconМетодические указания к лабораторной работе
Отладка реализации информационной системы для решения задачи курсового проекта: Методические указания к лабораторной работе / О....

Методические указания к выполнению лабораторной работе iconМетодические указания к лабораторной работе
Проектирование данных информационной системы: Методические указания к лабораторной работе / О. Е. Александров Екатеринбург: угту-упи,...

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

Методические указания к выполнению лабораторной работе iconМетодические указания к выполнению лабораторной работы
Х исследование процессов во влажном воздухе: методические указания к выполнению лабораторной работы / разраб. В. А. Халюткин. – Ставрополь:...

Методические указания к выполнению лабораторной работе iconМетодические указания к лабораторной работе Рязань
Изучение эллиптически поляризованного света: Методические указания к лабораторной работе /Рязан гос радиотехн акад. Сост.: И. В....

Методические указания к выполнению лабораторной работе iconМетодические указания к лабораторной работе №93 составлены на ка­федре «Физика»
Определение отношения методом адиабатического расширения : методические указания к лабораторной работе №93 по физике для студен­тов...


Разместите кнопку на своём сайте:
lib.convdocs.org


База данных защищена авторским правом ©lib.convdocs.org 2012
обратиться к администрации
lib.convdocs.org
Главная страница