Методические указания к выполнению лабораторной работе «решение систем линейных алгебраических уравнений»
| скачать Методические указания к выполнению лабораторной работе «РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ»по курсу «Вычислительная математика» для студентов специальности АСОИУ ВВЕДЕНИЕ В ряде практических задач управления и оптимизации приходится решать системы линейных алгебраических уравнений (СЛУ). В настоящей лабораторной работе изучается наиболее распространенный метод решения СЛУ – метод Гаусса. Цель работы - ознакомление с методом Гаусса решения СЛУ. Краткие теоретические сведенияПусть имеется система линейных уравнений a  x +a x +…+a x =d,a  x+a x +...+a x=d, (1)a  x+a x+…+a x=d.Систему (1) можно записать в матричном виде Ax=d. (2) Здесь А – матрица коэффициентов левых частей системы (1), а x и d – два n-мерных вектора: d=  , x= .Систему небольшого порядка (n < 5) с невырожденной матрицей А можно решить, пользуясь формулами Крамера x  = , i=1, 2, …, n.Здесь Δ – определитель матрицы А;  – вспомогательный определитель, матрица которого получается из ^ замещением i-го столбца столбцом d. Чем больше порядок системы, тем менее выгодны – в смысле количества вычислительной работы – формулы Крамера по сравнению с другим методом. Это метод Гаусса, или метод последовательного исключения неизвестных. Он состоит из двух этапов: прямого хода и обратной подстановки. При прямом ходе система приводится к специальному – треугольному – виду, либо выясняется, что она несовместна или имеет бесконечно много решений. Прямой ход выполняется как последовательность шагов, их не более п–1, где п – порядок системы. Задача каждого шага – исключение из системы очередного неизвестного. Предположим, что в системе (1) коэффициент a не равен нулю. Если бы это было не так, но зато a  0, то мы поменяли бы местами 1-е и l-е уравнения. Составим отношенияli1=  , i=2, 3, …, n,называемые множителями 1-го шага; коэффициент a при этом называется главным элементом 1-го шага. Умножая 1-е уравнение соответственно на l21, l31, …, ln1, вычтем его из 2-го, 3-го, ...., n-го. В результате придем к системе вида a x+ax+a x +…+ax=d,a  x+a x+...+a x=d ,a  x +a x+…+a x=d ,……………………………… a  x+a x+…+a x=d ,имеющей те же решения, что и система (1) Коэффициенты новой системы вычисляются по формулам: a  =a -l a , i, j=2, 3, …, n(3) d  =d-ld, i=2, 3, …, n.Первый шаг прямого хода закончен. Уравнения со 2-го по n-е составляют систему порядка п–1, в которой нет неизвестного x оно исключено, с чем и связано одно из названий метода. Может случиться, что в новой системе появилось уравнение, в котором все коэффициенты левой части равны нулю. Если правая часть такого уравнения ненулевая, то система, очевидно, несовместна. Если же и правая часть равна нулю, то такое уравнение можно удалить из системы; в результате число уравнений станет меньше n. Если несовместных уравнений в системе нет, то можно перейти ко второму шагу. Будем считать, что коэффициент a 0; в противном случае мы переставили бы 2-е уравнение с одним из нижележащих, именно с тем, в котором присутствует x. Составляем множители 2-го шага: l  = , i=3, 4, …, n.Коэффициент a называется главным элементом второго шага. Вычитая из 3-го, 4-го, ..., n-го уравнений 2-е, умноженное соответственно на l ,l ,…,1п2, получим a x+ ax+ ax+…+ ax=d ,a x+ ax+…+ ax=d,a  x+…+ a x=d ,…………………………… a  x+…+a x=d .Для коэффициентов справедливы соотношения, аналогичные формулам (3): a  =a-la , i,j=3, 4, …, n, (4) d  =d-ld, i=3, 4, …, n.Уравнения новой системы, кроме первых двух, составляют систему порядка п–2, в которой нет неизвестных x и x; неизвестное x исключено на втором шаге. Продолжая таким образом, мы или установим, что система несовместна, или после исключения k-гo неизвестного (1< k< n) не найдем среди последних п–k уравнений ни одного с ненулевыми коэффициентами, и это означает, что решений у системы бесконечно много, или, наконец, после п–1 шагов получим треугольную систему уравнений: a x+ax+…+a x +ax=d,a x+…+a x+ax=d,…………………………… (5) a  x+a x=d ,a  x=d .Прямой ход метода Гаусса закончен. Коэффициенты a , a,…, a, будучи главными элементами соответствующих шагов, не равны нулю согласно определению. Для невырожденной матрицы А не равен нулю и коэффициент a.Обратной подстановкой называется следующий этап – решение треугольной системы (5). Из последнего уравнения делением на a получаем значение неизвестного x. Подставляя его в (п–1)-е уравнение, можем определить значение x. Поднимаясь таким образом по системе, последовательно найдем значения всех неизвестных.В методе Гаусса с выбором главного элемента среди элементов a  m≥k находят главный, то есть наибольший по модулю в k-м столбце и перестановкой строк переводят его на главную диагональ, после чего делают исключения. Такая схема метода Гаусса позволяет уменьшить погрешность округления. Метод Гаусса с выбором главного элемента надежен и прост.Погрешность округления можно уменьшить, если выбирать в каждом цикле элемент, наибольший по модулю во всей матрице. Однако точность при этом возрастает не сильно по сравнению со случаем выбора главного элемента, а расчет заметно усложняется, так как требует не только перестановки строк, но и столбцов. Представим матрицу ^ в виде произведения нижней треугольной матрицы L и верхней U. Введем в рассмотрении матрицы L=  и U= .Можно показать, что A=L∙U. Это и есть разложение матрицы на множители. Рассмотрим метод Гаусса на примере решения системы x – 3 x – x = 4,–2 x +7 x+2 x= –9, 3 x + 2 x–4 x = 2.Составим матрицу  .Множители первого шага равны l21=2; l31= – 3. Умножаем первую строчку матрицы на множитель l21 и складываем со второй строчкой. Получим матрицу  .Далее умножаем первую строчку матрицы на множитель l31 и складываем с третьей строчкой. В результате  .Второй шаг: l32= –11.  .Обратная подстановка дает x1= 0, x2= –1, x3= –1. Решение системы с помощью LU-разложения сводится к последовательному решению систем с треугольными матрицами Ly=b и Ux=y. Для примера рассмотрим систему 3x – 4 x – 9 x + 5 x = –14,–15x – 12 x + 50 x – 16 x= –16,–27x – 36 x + 73 x + 8 x= 8,9 x + 12 x – 10 x – 16 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 x – 9 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 x – 9 x + 5 x= –14,–15x – 12 x + 50 x – 16 x= 44,–27x – 36 x + 73 x + 8 x= 142,9 x + 12 x – 10 x – 16 x= –76.Максимальный по модулю элемент 1-го столбца a33=–27. Переставим первое и третье уравнения. –27 x – 36 x + 73 x + 8 x= 142,–15 x – 12 x + 50 x – 16 x= 44,3 x – 4 x – 9 x + 5 x= –14,9 x + 12 x – 10 x – 16 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. ЗАДАНИЕ
^ Отчет должен содержать следующие обязательные части:
^
СПИСОК ЛИТЕРАТУРЫ
|
Ваша оценка этого документа будет первой.
Ваша оценка: Разместите кнопку на своём сайте или блоге: