скачать Методические указания к выполнению лабораторной работе «РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ»по курсу «Вычислительная математика» для студентов специальности АСОИУ ВВЕДЕНИЕ В ряде практических задач управления и оптимизации приходится решать системы линейных алгебраических уравнений (СЛУ). В настоящей лабораторной работе изучается наиболее распространенный метод решения СЛУ – метод Гаусса. Цель работы - ознакомление с методом Гаусса решения СЛУ. Краткие теоретические сведенияПусть имеется система линейных уравнений a ![]() ![]() ![]() ![]() ![]() ![]() ![]() a ![]() ![]() ![]() ![]() ![]() ![]() ![]() a ![]() ![]() ![]() ![]() ![]() ![]() ![]() Систему (1) можно записать в матричном виде Ax=d. (2) Здесь А – матрица коэффициентов левых частей системы (1), а x и d – два n-мерных вектора: d= ![]() ![]() Систему небольшого порядка (n < 5) с невырожденной матрицей А можно решить, пользуясь формулами Крамера x ![]() ![]() Здесь Δ – определитель матрицы А; ![]() Чем больше порядок системы, тем менее выгодны – в смысле количества вычислительной работы – формулы Крамера по сравнению с другим методом. Это метод Гаусса, или метод последовательного исключения неизвестных. Он состоит из двух этапов: прямого хода и обратной подстановки. При прямом ходе система приводится к специальному – треугольному – виду, либо выясняется, что она несовместна или имеет бесконечно много решений. Прямой ход выполняется как последовательность шагов, их не более п–1, где п – порядок системы. Задача каждого шага – исключение из системы очередного неизвестного. Предположим, что в системе (1) коэффициент a ![]() ![]() ![]() li1= ![]() называемые множителями 1-го шага; коэффициент a ![]() ![]() a ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() a ![]() ![]() ![]() ![]() ![]() ![]() ![]() a ![]() ![]() ![]() ![]() ![]() ![]() ![]() ……………………………… a ![]() ![]() ![]() ![]() ![]() ![]() ![]() имеющей те же решения, что и система (1) Коэффициенты новой системы вычисляются по формулам: a ![]() ![]() ![]() ![]() (3) d ![]() ![]() ![]() ![]() Первый шаг прямого хода закончен. Уравнения со 2-го по n-е составляют систему порядка п–1, в которой нет неизвестного x ![]() Может случиться, что в новой системе появилось уравнение, в котором все коэффициенты левой части равны нулю. Если правая часть такого уравнения ненулевая, то система, очевидно, несовместна. Если же и правая часть равна нулю, то такое уравнение можно удалить из системы; в результате число уравнений станет меньше n. Если несовместных уравнений в системе нет, то можно перейти ко второму шагу. Будем считать, что коэффициент a ![]() ![]() ![]() Составляем множители 2-го шага: l ![]() ![]() Коэффициент a ![]() ![]() ![]() a ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() a ![]() ![]() ![]() ![]() ![]() ![]() ![]() a ![]() ![]() ![]() ![]() ![]() …………………………… a ![]() ![]() ![]() ![]() ![]() Для коэффициентов справедливы соотношения, аналогичные формулам (3): a ![]() ![]() ![]() ![]() (4) d ![]() ![]() ![]() ![]() Уравнения новой системы, кроме первых двух, составляют систему порядка п–2, в которой нет неизвестных x ![]() ![]() ![]() a ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() a ![]() ![]() ![]() ![]() ![]() ![]() ![]() …………………………… (5) a ![]() ![]() ![]() ![]() ![]() a ![]() ![]() ![]() Прямой ход метода Гаусса закончен. Коэффициенты a ![]() ![]() ![]() ![]() Обратной подстановкой называется следующий этап – решение треугольной системы (5). Из последнего уравнения делением на a ![]() ![]() ![]() В методе Гаусса с выбором главного элемента среди элементов a ![]() Погрешность округления можно уменьшить, если выбирать в каждом цикле элемент, наибольший по модулю во всей матрице. Однако точность при этом возрастает не сильно по сравнению со случаем выбора главного элемента, а расчет заметно усложняется, так как требует не только перестановки строк, но и столбцов. Представим матрицу ^ в виде произведения нижней треугольной матрицы L и верхней U. Введем в рассмотрении матрицы L= ![]() ![]() Можно показать, что A=L∙U. Это и есть разложение матрицы на множители. Рассмотрим метод Гаусса на примере решения системы x ![]() ![]() ![]() –2 x ![]() ![]() ![]() 3 x ![]() ![]() ![]() Составим матрицу ![]() Множители первого шага равны l21=2; l31= – 3. Умножаем первую строчку матрицы на множитель l21 и складываем со второй строчкой. Получим матрицу ![]() Далее умножаем первую строчку матрицы на множитель l31 и складываем с третьей строчкой. В результате ![]() Второй шаг: l32= –11. ![]() Обратная подстановка дает x1= 0, x2= –1, x3= –1. Решение системы с помощью LU-разложения сводится к последовательному решению систем с треугольными матрицами Ly=b и Ux=y. Для примера рассмотрим систему 3x ![]() ![]() ![]() ![]() –15x ![]() ![]() ![]() ![]() –27x ![]() ![]() ![]() ![]() 9 x ![]() ![]() ![]() ![]() В матричном виде A= ![]() Первый шаг. Вычислим множители l21= ![]() ![]() ![]() и выполним преобразование матрицы ![]() Второй шаг. Вычислим множители l32= ![]() ![]() Второй шаг не изменяет матрицы. Третий шаг. l43= ![]() и выполним преобразование матрицы ![]() В результате получим матрицу U. U= ![]() Матрица L L= ![]() Легко вычислить решение системы Ly=b. y ![]() –5y ![]() ![]() –9 y ![]() ![]() 3 y ![]() ![]() ![]() ![]() y1= –14, y2= –26, y3= 16, y4= 0. Решением системы Ux=y является вектор x. 3x ![]() ![]() ![]() ![]() 8 x ![]() ![]() ![]() –8 x ![]() ![]() ![]() ![]() x1= –8, x2= –2, x3= –2, x4= 0. Решение системы методом Гаусса с выбором главного элемента по столбцу покажем на примере решения системы. 3x ![]() ![]() ![]() ![]() –15x ![]() ![]() ![]() ![]() –27x ![]() ![]() ![]() ![]() 9 x ![]() ![]() ![]() ![]() Максимальный по модулю элемент 1-го столбца a33=–27. Переставим первое и третье уравнения. –27 x ![]() ![]() ![]() ![]() –15 x ![]() ![]() ![]() ![]() 3 x ![]() ![]() ![]() ![]() 9 x ![]() ![]() ![]() ![]() В матричном виде A= ![]() Первый шаг. Вычислим множители l21= ![]() ![]() ![]() ![]() ![]() ![]() и выполним преобразование матрицы A= ![]() Второй шаг. Вычислим множители l32= ![]() ![]() Второй шаг не изменяет матрицы. Третий шаг. Максимальный по модулю элемент третьего столбца a43= ![]() A= ![]() l43= ![]() и выполним преобразование матрицы A= ![]() Обратный ход. Из последнего уравнения находим x4=0. Из третьего уравнения находим x3= ![]() Из второго уравнения находим x2= ![]() Неизвестное x1 находим из первого уравнения x1= ![]() Ответ x1= –8, x2= –2, x3= –2, x4= 0. ЗАДАНИЕ
^ Отчет должен содержать следующие обязательные части:
^
СПИСОК ЛИТЕРАТУРЫ
|