Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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




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

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

Требуется найти решение системы

(4.1)

Пусть . В противном случае уравнения переставляются так, чтобы это условие выполнялось. Разделим первое уравнение системы (4.1) на коэффициент , который будем называть «ведущим» элементом. Получим уравнение

, (4.2)

где

.

Пользуясь уравнением (4.2), можно исключить переменную х1 из второго и третьего уравнений системы (4.1). Для этого из второго уравнения системы (4.1) вычитаем уравнение (4.2), умноженное на , а из третьего уравнения системы (4.1) вычитаем уравнение (4.2), умноженное на .

Приходим к системе

(4.3)

где

.

К полученной системе (4.3) применим те же преобразования, что и к системе (4.1). Делим первое уравнение системы на «ведущий» элемент . Получаем уравнение

, (4.4)

где

.

Исключаем переменную х2 из второго уравнения системы (4.4). Для этого умножаем уравнение (4.4) на и вычитаем из второго уравнения системы (4.3). Получаем

, (4.5)

где .

Наконец, разделив уравнение (4.5) на , имеем

. (4.6)

Объединив уравнения (4.2), (4.4) и (4.6) с коэффициентами b, получим треугольную систему, эквивалентную данной:

(4.7)

Решение системы (4.7) и, следовательно, системы (4.1) записывается в виде

(4.8)

Итак, для решения системы (4.1) сначала строим вспомогательную треугольную систему (4.7), а затем по формулам (4.8) записываем решение системы. Процесс нахождения коэффициентов треугольной системы называется прямым ходом, а процесс получения ее решения – обратным ходом. Во избежание накопления погрешностей округления весь расчет ведем с двумя запасными знаками, которые при записи решения системы отбрасываем.

Расчетные формулы метода Гаусса в общем виде можно записать следующим образом. На некотором k-м этапе (k = 1,…,n-1) исключаем хk с помощью преобразований, причем предполагаем, что :

( , ).

Отметим, что А = { } – расширенная матрица коэффициентов (образуется из матрицы коэффициентов добавлением столбца свободных членов).



Обратный ход для нахождения неизвестных задается формулой

, .

Применение метода Гаусса для вычисления определителя. Доказано, что определитель матрицы А равен произведению «ведущих» (или главных) элементов в соответствующей схеме Гаусса, т.е.

.

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

Применение метода Гаусса для вычисления обратной матрицы. Обратной к матрице А называют такую матрицу , для которой выполняется условие

, (4.9)

где I – единичная матрица,

.

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

Для вычисления элементов обратной матрицы используем соотношение (4.9). Умножая матрицу А на матрицу и приравнивая каждый элемент произведения соответствующему элементу единичной матрицы I, получаем систему из n2 уравнений с n2 неизвестными. Все эти системы имеют одну и ту же матрицу коэффициентов А и отличаются только свободными членами. Так как при решении системы по методу Гаусса основные вычисления приходится производить над матрицей коэффициентов, решение всех этих систем можно объединить в одной схеме, рассматривая одновременно n столбцов свободных членов.

Число арифметических операций N, необходимых для реализации метода Гаусса, определяется следующей формулой:



,

где n – число неизвестных. Таким образом, число арифметических операций примерно пропорционально кубу числа неизвестных.

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


mylektsii.ru - Мои Лекции - 2015-2019 год. (0.01 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал