8. РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ
Системы линейных алгебраических уравнений (СЛАУ) появляется почти в каждой области прикладной математики. В некоторых случаях эти СЛАУ непосредственно составляют ту задачу, которую необходимо решить, в других случаях задача сводится к решению такой системы. Примерами таких задач являются системы нелинейных уравнений, дифференциальных уравнений в частных производных, задачи аппроксимации и интерполяции и др. Решение СЛАУ является одной из самых распространенных и важных задач вычислительной математики.
Систему n линейных алгебраических уравнений с n неизвестными
запишем как:
a11.x1+a12.x2+...+a1n.xn=b1 ; a21.x1+a22.x2+...+a2n.xn=b2 ;
………………………… |
(8.1) |
an1.x1+an2.x2+...+ann.xn=bn .
Коэффициенты ai,j (i=1, 2,...,n; j=1,2,...,n) этой СЛАУ можно представить в виде квадратной матрицы n × n:
a11 a12 ... a1n
A = a21 a22 ... a2n . (8.2)
…………...
an1 an2 ... ann
Систему (8.1) можно записать в матричном виде A X=B, где X – вектор-столбец неизвестных; B – вектор-столбец правых частей.
Рассмотрим некоторые специальные виды матриц :
|
1 2 3 |
|
|
|
1 2 3 |
|
|
||
С = |
2 7 4 |
, |
T = |
0 5 7 |
, |
|
|||
|
3 4 8 |
|
|
|
0 0 9 |
|
|
||
|
1 2 0 |
0 |
|
|
|
|
2 3 0 0 0 |
|
|
|
|
|
|
|
|||||
|
|
|
|
||||||
|
|
|
|
|
1 2 3 0 0 |
|
|||
K = |
3 4 0 0 |
|
, Д = |
|
|
. |
|||
|
|
|
0 3 4 5 0 |
||||||
|
0 0 5 |
6 |
|
|
|
|
0 0 4 5 6 |
|
|
|
0 0 7 |
8 |
|
|
|
|
|
||
|
|
|
|
|
0 0 0 1 2 |
|
|||
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
Здесь С – симметричная матрица (ее элементы расположены симметрично относительно главной диагонали, т. е. aij=aji); T – верхняя тре-
62
угольная матрица с равными нулю элементами, расположенными ниже диагонали; К – клеточная матрица (ее ненулевые элементы составляют отдельные группы-клетки); Д – ленточная матрица (ее ненулевые элементы составляют «ленту», параллельную диагонали; в данном случае данная матрица Д одновременно является также трехдиагональной).
Методы решения СЛАУ делятся на две группы – прямые и итерационные.
8.1. Прямые методы
Прямые методы используют заранее известное, зависящее от n, количество соотношений (формул) для вычисления неизвестных. К ним относятся правило Крамера, метод Гаусса (или метод последовательного исключения неизвестных), метод Гаусса с выбором главного элемента, метод прогонки (частный случай метода Гаусса для СЛАУ с трехдиагональной матрицей), метод Жордана (часто используется для нахождения обратной матрицы), метод квадратного корня (применяется тогда, когда матрица системы является симметричной), клеточные методы (используются для решения больших СЛАУ, когда матрица и вектор правых частей целиком не помещаются в оперативной памяти ЭВМ) и др. Алгоритмы этих методов сравнительно просты и наиболее универсальны, т. е. пригодны для решения широкого класса СЛАУ. К недостаткам таких методов относится требование хранения в оперативной памяти ЭВМ сразу всей исходной матрицы, и, следовательно, при больших значениях n используется большой объем памяти. Прямые методы не учитывают конкретный вид матрицы или ее структуру, т. е. при большом числе нулевых элементов в ленточных или клеточных матрицах эти элементы занимают место в памяти ЭВМ, и над ними проводятся практически бесполезные арифметические операции. Кроме того, существенным недостатком прямых методов является увеличение погрешностей в процессе получения решения, т. к. вычисления на последующем этапе используют результаты предыдущих операций, полученных, в свою очередь, с какой-то погрешностью. Особенно актуальным становится вышеуказанное обстоятельство для больших СЛАУ вследствие резкого увеличения общего количества числа арифметических действий, а также для плохо обусловленных СЛАУ из-за их чувствительности к погрешностям.
Поэтому прямые методы применяются для относительно небольших (n < 200) СЛАУ с плотно заполненной матрицей и не близким к нулю определителем.
63