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

Лекция 3

Метод простой итерации.

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

Пусть известно начальное приближение корня . Подставляя это зна­чение в правую часть уравнения , получаем новое приближение

.

Далее подставляя каждый раз новое значение корня в уравнение , получаем последо­вательность значений , .

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

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

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

Запишем систему линейных алгебраических уравнений с неизвест­ными:

Совокупность коэффициентов этой системы запишем в виде таблицы:

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

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

.

Специальные виды матриц:

-симметрическая матрица (се элементы расположены симметрично относительно главной диагонали ());

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

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

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

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

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

Определителем (детерминантом)матрицы -го порядка называется число , равное:

Здесь индексы пробегают все возможные перестановок номеров ; - число инверсий в данной перестановке.

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

2.О методах решении линейных систем.

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

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

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

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

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

Определитель треугольной матрицы равен произведению ее элементов, расположенных на главной диагонали: . Определитель единичной матрицы равен единице(), а нулевой нулю().

Матрица называется обратной по отношению к квадратной матри­це , если их произведение равно единичной матрице:

.

Всякая невырожденная матрица (т.е. с отличным от нуля определителем ) имеет обратную матрице. При этом:

Запишем исходную матрицу:

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

Алгебраическим дополнением элемента называется его минор, взятый со знаком плюс, если сумма - четная, и со знаком минус, если эта сумма нечетная, т. е. .

Каждый элемент обратной матрицы равен отношению алгебраического дополнения элемента (а не ) исход­ной матрицы к значению ее определителя :