Лабораторная работа решение системы линейных алгебраических уравнений

Лабораторная_работа «Решение системы линейных уравнений»

Обращаем Ваше внимание, что в соответствии с Федеральным законом N 273-ФЗ «Об образовании в Российской Федерации» в организациях, осуществляющих образовательную деятельность, организовывается обучение и воспитание обучающихся с ОВЗ как совместно с другими обучающимися, так и в отдельных классах или группах.

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

Цель работы: приобрести навыки решения линейных алгебраических уравнений в среде Excel .

1. Изучить представленный ниже материал, повторить приведенные примеры

В общем виде система линейных алгебраических уравнений записывается следующим образом:

Эту систему можно представить в матричном виде: AX = b , где

— матрица коэффициентов системы уравнений;

— вектор неизвестных; — вектор правых частей.

Метод обратной матрицы

Систему линейных алгебраических уравнений AX = b умножим слева на матрицу, обратную к матрице А . Система уравнений примет вид:

Вектор неизвестных вычисляется по формуле X=A -1 b .

В этом случае неизвестные x ₁ , x 2 ,…, x _n вычисляются по формуле:

где  – определитель матрицы A ;

 _I – определитель матрицы, получаемой из матрицы А путем замены i -го столбца вектором b.

Рассмотрим решение системы линейных уравнений методом обратной матрицы и методом Крамера на следующих примерах.

Решить систему линейных уравнений методом обратной матрицы:

Матрица коэффициентов А и вектор свободных коэффициентов b имеют вид:

.

Введем эти данные в рабочий лист Excel (рисунок 12).

Рисунок 12 – Шаг 1 решения системы линейных уравнений

Для решения системы методом обратной матрицы необходимо вычислить матрицу, обратную к A . Для этого определим ячейки для хранения обратной матрицы, пусть это будут ячейки B6:E9.

Обратимся к мастеру функций, и выберем функцию МОБР , щелкнув по кнопке OK, перейдём ко второму шагу мастера функций. В диалоговом окне, появляющемся на следующем шаге мастера функций, необходимо заполнить поле ввода Массив . Это поле должно содержать диапазон ячеек, в котором хранится исходная матрица — в нашем случае B1:E4. Данные в поле ввода Массив можно ввести, используя клавиатуру или выделив их на рабочем листе, удерживая левую кнопку мыши.

Если поле Массив заполнено, нажать кнопку OK. В первой ячейке, выделенного под обратную матрицу диапазона, появится некое число. Для того чтобы получить всю обратную матрицу, необходимо нажать клавишу F2, а затем одновременно клавиши Ctrl+Shift+Enter. Рабочий лист Excel примет вид, изображенный на рисунке 13.

Р
исунок 13 – Шаг 2 решения системы линейных уравнений

Теперь необходимо умножить полученную обратную матрицу на вектор b . Выделим ячейки для хранения результирующего вектора, например H6:H9. Обратимся к мастеру функций, и выберем функцию МУМНОЖ , предназначенную для умножения матриц. На втором шаге мастера функций в диалоговом окне введем в поле Массив1 необходимо ввести диапазон ячеек, в котором содержится первая из перемножаемых матриц, в нашем случае B6:E9 (обратная матрица), а в поле Массив2 ячейки, содержащие вторую матрицу, в нашем случае G1:G4 (вектор b ).

Для того чтобы проверить, правильно ли решена система уравнений, необходимо умножить матрицу A на вектор х и получить в результате вектор b . Умножение матрицы A на вектор x осуществляется при помощи функции = МУМНОЖ (В1:Е4;Н6:Н9), так как было описанной выше.

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

Рисунок 13 – Шаг 3 решения системы линейных уравнений матричным методом

Решим пример методом Крамера.

Введём матрицу А и вектор b на рабочий лист. Сформируем четыре вспомогательные матрицы, заменяя последовательно столбцы матрицы A на столбец вектора b (рисунок 14).

Для дальнейшего решения необходимо вычислить определитель матрицы A. Установим курсор в ячейку I10 и обратимся к мастеру функций. В категории Математические выберем функцию МОПРЕД, предназначенную для вычисления определителя матрицы, и перейдём ко второму шагу мастера функций. Диалоговое окно, появляющееся на втором шаге содержит поле ввода Массив. В этом поле указывают диапазон матрицы, определитель которой вычисляют. В нашем случае это ячейки B1:E4.

Для вычисления вспомогательных определителей введем формулы:

I12= МОПРЕД (B11:E14) ,

I13= МОПРЕД (B16:E19),

I14= МОПРЕД (B21:E24) .

В результате в ячейке I10 хранится главный определитель, а в ячейках I11:I14 — вспомогательные.

Воспользуемся формулами Крамера и разделим последовательно вспомогательные определители на главный. В ячейку K11 введём формулу=I11/$I$10. Затем скопируем её содержимое в ячейки K12, K13 и K14. Система решена.

Рисунок 14 — Решения системы линейных уравнений методом Крамера

2. Решить системы уравнений согласно вариантам с помощью обратной матрицы и методом Крамера.

При решении систем обязательно выполнить проверку.

Вариант 2 Вариант 3 Вариант 4 Вариант 5 Вариант 6 Вариант 7 Вариант 8 Вариант 9 Вариант 10 Вариант 11 Вариант 12 Вариант 13 Вариант 14 Вариант 15 Вариант 16 Вариант 17 Вариант 18 Вариант 19 Вариант 20

Обратите внимание на особенность работы с матричными формулами: необходимо предварительно выделять область, в которой будет храниться результат, а после получения результата преобразовывать его к матричному виду, нажав клавиши F2 и Ctrl+Shift+Enter.

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

Московский Государственный Технически Университет

«МАМИ»

Лабораторная работа №3 по курсу «Вычислительная Математика»

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

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

Справочная информация

Численные методы решения систем линейных алгебраических уравнений

,

записываемых в матричной форме в виде

,

,

делятся на точные и итерационные. Они используются для систем, у которых количество неизвестных равно количеству уравнений и матрица A — не вырождена (её определитель не равен нулю). Точными методами условно называют методы, которые дают решение задачи посредством конечного числа арифметических операций. Итерационные методы позволяют получить решение системы как предел бесконечной последовательности его приближений. При применении итерационных методов существенным вопросом является вопрос об их сходимости.

Точные методы, к которым относятся метод Гауссаи его разновидности, не имеют дополнительных ограничений на свойства матрицы системы.

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

.

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

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

,

которое на этом шаге считается ведущим, нормируется – делится на значение диагонального элемента a₁₁

,

.

Если в исходной системе a₁₁= 0, то в качестве первого уравнения следует взять любое другое с ненулевым первым коэффициентом, поменяв их местами. Полученное уравнение умножается на первый коэффициент второго уравнения a₂₁ и вычитается из него. В результате во втором уравнении пропадает слагаемое a₂₁x₁, содержащее первое неизвестное x₁. Такие же операции проводятся со всеми последующими уравнениями. В результате система уравнений принимает вид

.

Далее процесс повторяется. За ведущее берется второе уравнение и исключается неизвестное x₂ из всех уравнений, начиная с третьего

.

Таким образом, за n шагов система уравнений последовательно сводится к треугольному виду, при этом для последнего уравнения выполняется только операция нормирования:

.

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

.

Выполняя аналогичные подстановки найденных неизвестных в вышестоящие уравнения, удается определить все компоненты решения x_n–2. x₂, x₁.

Метод Гаусса даёт точное решение, если все исходные данные точны и все вычисления производятся точно. На практике, при выполнении вычислений, неизбежно проводятся округления. Ошибка округлений вносит погрешность в решение метода Гаусса. Таким образом, при операциях с округленными десятичными числами метод Гаусса даёт не точное решение x_т системы линейных алгебраических уравнений, а некоторое приближённое решение , где

, .

Степень отличия приближённого решения от точного определяется длиной разрядной сетки ЭВМ: чем больше разрядов в ней учитывается, тем это отличие меньше.

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

или или

,

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

Для определения величины погрешности полученного решения на практике используют следующий алгоритм вычисления её главной части. Сначала по имеющемуся решению пересчитывается вектор правых частей системы

,

а затем посредством повторного решения системы уравнений

находится вектор погрешностей . С его помощью определяется как реальная абсолютная погрешность полученного решения

или или ,

так и его относительная погрешность

.

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

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

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

В качестве примера применения метода Гаусса можно рассмотреть задачу отыскания решения следующей системы уравнений

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

Поставленная задача будет решаться методом Гаусса с выбором главного элемента по столбцу.

а. Выбор главного элемента среди элементов первого столбца

.

б. Нормировка первого уравнения

.

в. Исключение элементов первого столбца

.

г. Выбор главного элемента среди элементов второго столбца второго и третьего уравнений

.

д. Нормировка второго уравнения

.

е. Исключение элементов второго столбца

.

ё. Нормировка последнего уравнения

.

,

.

В итоге получено решение системы уравнений

.

3. Погрешность найденного решения.

а. Пересчёт вектора правых частей системы

б. Формирование системы уравнений, определяющей погрешности решения

,

в. Решение системы относительно погрешностей оно выполняется аналогично пунктам 1 и 2. Прямой ход (пункт 1) даёт следующую систему с верхней треугольной матрицей

,

а обратный ход позволяет получить решение

.

г. Оценка абсолютной и относительной погрешностей решения системы линейных алгебраических уравнений

,

,

.

Реализация описанного метода без нахождения погрешности решения в рамках программы Excel приведена на рис.1.

О выборе метода решения систем уравнений

Каждый из рассмотренных методов имеет свои достоинства и недостатки. В частности, метод Гаусса позволяет получить решение за конечное число шагов. Для этого требуется выполнить n(n 2 + 3n – 1)/3 операций умножения и деления и n(n – 1)(2n + 5)/6 операций сложения и вычитания, количество которых при больших порядках системы (n > 100) можно принять равным n 3 /3 в обоих случаях. Однако его методические ошибки, связанные с размером разрядной сетки вычислений, резко нарастают с увеличением порядка системы и не позволяют применять его для систем высоких порядков без использования специальных приёмов.

Итерационные методы позволяют получать решение систем бóльшего порядка. Для выполнения каждой итерации с их помощью необходимо выполнить n(n + 1) операций умножения и деления и столько же операций сложения и вычитания. При больших порядках системы уравнений (n > 100) их количество можно принять равным n 2 . Из сравнения трудоёмкости итерационных методов и метода Гаусса следует оценка, которой можно руководствоваться при окончательном выборе метода решения системы при необходимости его многократного нахождения. Если количество итераций, требуемое для получения решения системы итерационными методами, не превышает n/3, то выгоднее применять их, а не методы типа Гаусса. Однако здесь следует помнить, что итерационные методы требуют, чтобы матрица системы обладала определёнными свойствами, обеспечивающими их сходимость. Необходимо также отметить, что выполнение этих требований часто не гарантирует высокой скорости их сходимости.

Решение систем линейных алгебраических уравнений

Страницы работы

Содержание работы

Лабораторная работа №3

Решение систем линейных алгебраических уравнений

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

Решить систему линейных алгебраических уравнений (САУ)

, , ,

итерационными методами Зейделя и наискорейшего спуска с точностью до e = 0,001. Для сравнения с истинными значениями корней выполнить решение указанной САУ методом Гаусса.

Общий вид алгоритма Зейделя и наискорейшего спуска

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

Расчетные соотношения метода Зейделя для подготовленной системы уравнений (4.13) имеют вид

,(4.18)

.

При составлении программы для вычислений на ЭВМ вместо соотношения (4.18) удобнее использовать выражение, в котором фигурируют элементы исходной системы уравнений

,

.

Если матрица симметрическая и положительно определенная, а подготовленная к итерациям система определяется в виде

(4.13)

где то метод Зейделя сходится. Если же диагональные элементы симметрической матрицы не отрицательны, то условие положительной определенности матрицы является и необходимым.

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

.

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

, (4.19)

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

, (4.20)

. (4.21)

Чтобы упростить процедуру определения вектора невязки, особенно при больших порядках матрицы системы уравнений, рекомендуется вычислять его по формуле

.

Однако из-за наличия вычислительных погрешностей векторы после нескольких итераций могут отклоняться от истинных невязок и потому время от времени их следует корректировать по выражению (4.20).

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

SUBROUTINE N1YMGS (A,B,N,G,X),

SUBROUTINE N1YMNS (A,B,N,G,X)

реализуют алгоритмы решения САУ методами Зейделя и наискорейшего спуска (одна итерация) соответственно.

Входные параметры подпрограмм:

А(N,N) — (N ´ N)-мерная матрица САУ;

B(N) — N-мерный вектор правой части САУ;

N — мерность САУ;

G(N) — N-мерный вектор невязки (g = b — Ax);

X(N) — N-мерный вектор начальных условий решения САУ.

Выходные параметры подпрограммы:

X(N) — N-мерный вектор уточненных значений решения САУ.

Окончание итерационной процедуры производиться при выполнении условия , где , i[1, n], k = 1, 2, 3, …,

SUBROUTINE N1YGAU (A,B,X,N)

реализует алгоритм метода Гаусса с выбором главного элемента.

Входные A, B, N и выходной X параметры подпрограммы N1YGAU совпадают по описанию с аналогичными параметрами в подпрограммах N1YMGS, N1YMNS.

В подпрограмме N1YGAU матрица A приводится к треугольной.