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

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

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

1. Точные методы - представляющие собой конечные алгоритмы для вычисления корней системы.

2. Итерационные методы - позволяющие получить корни системы уравнений с заданной точночтью путём бесконечных сходящихся процессов.

Введём следующие обозначения:

Рекомендуемые материалы

 - матрица коэффициентов

 - столбец свободных членов

 - столбец неизвестных

Решение имеет место, если матрица  - неособенная, то есть

 - решение системы с помощью обратной матрицы

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

Это обстоятельство обходится с помощью правила Крамера

,

где  - определитель матрицы

 - определитель матрицы, полученный из матрицы  путём замещения -го столбца на столбец свободных членов .

Пример:

Прямой метод

, 

По правилу Крамера

Метод Гаусса. Схема единственного деления

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

Рассмотрим для простоты систему линейных алгебраических уравнений 4-го порядка:

1. Выбираем ведущий элемент

2. Поделив первое уравнение на , получаем

,               (2)

где , ,

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

,

где , ,

4. Выбираем ведущий элемент во втором уравнении

и так далее.

Если , то получим систему

,         (3)

то есть матрица  имеет диагональный вид:

Из системы 3 отыскиваем  следующим образом

,       (4)

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

Пример: прежний, но методом Гаусса. Приводит к системе уравнений:

 - прямой ход

 - обратный ход

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

То есть в нашем курсе мы ориентируемся на вычислительную технику и все методы интересуют как алгоритмы.

Трудоёмкость метода Гаусса

1. Прямой ход

2. Обратный ход

Общее число выполняемых арифметических действий

то есть для

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

Тогда применяют разновидность метод Гаусса -схема с выбором главного элемента:

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

1. Выбираем элемент  - наибольший по модулю и неявляющийся свободным членом.

2. Вычисляем коэффициенты

, для всех

-тая строка называется главной строкой.

3. Из каждой неглавной строки вычитаем главную строку, умноженную на . В результате получим матрицу, у которой в -ом столбце все коэффициенты нулевые.

4. Преобразуем матрицу следующим образом: отбрасываем - (главную) строку и -й столбец. Получим матрицу .

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

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

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

Пример:

Достоинства метода

1. Если матрица вырождения, то перед исключением неизвестной главный элемент считается равным нулю =>

2. С помощью метода Гаусса можно вычислить определитель  треугольной матрицы.

При большом числе неизвестных схема метода Гаусса, дающая точное решение, становится весьма сложной.

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

Метод итераций

Дана система уравнений

  

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

,                (2)

где , ,  или  при

, .

Тогда систему уравнений 2 можно записать в виде:

 - итерационная формула.

Таким образом, выбрав начальные значения

и так далее.

Итерации останавливаются, когда ,

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

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

Если для системы уравнений

выполнено хотя бы одно из условий:

1. ,

2. ,

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

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

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

Приведение линейной системы к виду, удобному для итерациию.

Теорема сходимости накладывает жёсткие условия к коэффициентам данной линейной системы.

Однако, если , то эту систему всегда можно привести к такому виду:

, чтобы удовлетворить условиям 1

Первый способ.

Дано:

Домножим это уравнение на матрицу , где

,

где

Второй способ.

Каждое -ое уравнение делится на

Тогда , , .

Тогда уравнение сходимости имеет вид

,

,

Эти неравенствабудут выполняться, если диагональные элементы будут удовлетворять условиям:

, ,

то есть если модули диагональных коэффициентов для которого уравнения системы больше суммы модулей всех остальных коэффициентов.

Достоинства метода итераций

1. Если итерации сходятся быстро, то есть для сходимости требуется менее  итераций, то выигрыш во времени по сравнению с методом Гаусса:

, - число итераций

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

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

4. Метод итераций легко программируется.

Метод Зейделя

Является модификацией метода итераций. Основная идея заключается в том, что при вычислении -го приближения -го корня используются уже вычисленные  приближённые корни .

Дано: ,

Выбираем начальное приближение:

Рекомендация для Вас - ERP системы.

На -том шаге, согласно Зейделю строим приближение по следующим формулам:

1. Метод Зейделя даёт полную сходимость по сравнению с методом итерации, но приводящий к громоздким вычислениям.

2. Теорема: Для существования единственного решения системы сходимости метода Зейделя достаточно выполнение хотя бы одного из двух условий:

1)  ,

2)  матрица  - симметричная положительно определённая (все её соответственно значения положительны)