Прямые методы

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

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

Основные понятия

Запишем систему из линейных уравнений с неизвестными:

(5.1)

Совокупность коэффициентов этой системы запишем в виде квадратной матрицы A порядка

(5.2).

Совокупность неизвестных и совокупность правых частей запишем в виде векторов и соответственно

,

Т.о. систему (5.1) можно записать в векторно-матричном виде

(5.3)

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

- симметричная матрица, ее элементы расположены симметрично относительно главной диагонали, .

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

- клеточная матрица, ее нулевые элементы составляют отдельные группы (клетки).

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

- единичная матрица, единичная диагональная матрица (частный случай ленточной матрицы)

Специальный вид может иметь вектор

- нулевой вектор , при котором систему линейных уравнений называют однородной.

С квадратной матрицей A связан определитель (детерминант)

где α, β, ω пробегают все возможные n! перестановок номеров 1,2,…,n

k - число инверсий в данной перестановке:

k=0, если перестановка четная,

k=1, если перестановка нечетная.

Не следует отождествлять два понятия A и det A. A - упорядоченная в виде таблицы система чисел, а det A – число, определяемое по формуле.

Если det A≠0 то матрица называется неособенной, система уравнений невырожденной, иначе (det A=0) – особенной или сингулярной, а система уравнений вырожденной.

Необходимым и достаточным условием существования единственного решения системы линейных уравнений является условие det A≠0 (система называется совместной и определенной). Если же

det A=0, то система либо не имеет решений, либо имеет их бесконечное множество (система называется несовместной или противоречивой).

Если det A≈0, то система уравнений называется плохо обусловленной.

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

- прямые (точные)

- итерационные

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

Достоинства:

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

Недостатки:

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

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

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

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

Достоинства:

- требуют меньше оперативной памяти ЭВМ;

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

Недостатки:

- алгоритмы решения обычно более сложны по сравнению с прямыми методами;

- объем вычислений заранее определить трудно;

- сходимость итераций может быть очень медленной;

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

Прямые методы

Поиск по сайту: