3. Численные методы алгебры

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

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

К решению систем линейных алгебраических уравнений (СЛАУ) сводятся многочисленные практические задачи. Можно с полным основание утверждать, что решение линейных систем является одной из самых распространенных и важных задач вычислительной математики. У нас уже была возможность увидеть при рассмотрении сплайн-интерполяции.

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

a₁₁X₁+a₁₂X₂+…+a_1nX_n=b₁,

a₂₁X₁+a₂₂X₂+…+a_2nX_n=b₂,

--------------------------------

a_n1X₁+a_n2X₂+…+a_nnX_n=b_n,

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

a₁₁ a₁₂ … a_1n

A = a₂₁ a₂₂ … a_2n

---------------

a_n1 a_n2 … a_nn

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

Используя понятие матрицы А, СЛАУ можно записать в матричном виде

АХ=В,

где Х и В – вектор-столбец неизвестных и вектор-столбец правых частей соответственно

X₁ b₁

X = X₂ , B = b₁ .

--- ---

X_n b₁

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

Симметрическая матрица 2 1 –1 1 3 2 –1 2 4	Верхняя треугольная матрица 1 2 3 0 –1 1 0 0 2	Единичная матрица (частный случай – диагональная) 1 0 0 E = 0 1 0 0 0 1
Клеточная матрица 1 2 1 0 0 0 2 –1 2 0 0 0 3 1 –1 0 0 0 0 0 0 1 2 3 0 0 0 4 5 6 0 0 0 7 8 9	Нулевая матрица 0 0 0 0 0 = 0 0 0 0 0 0 0 0 0 0 0 0	Ленточная матрица (частный случай – трех диагональная) 1 2 0 0 0 2 1 3 0 0 0 3 –1 2 0 0 0 2 1 5 0 0 0 2 1

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

a₁₁ a₁₂ … a_1n

D = a₂₁ a₂₂ … a_2n = .

---------------

a_n1 a_n2 … a_nn

Здесь индексы пробегают все возможные n! Перестановок номеров 1,2,…,n; k – число инверсий в данной перестановке (иногда говорят о числе беспорядков) всего должно быть n! слагаемых (в нашем случае 6).

a₁₁ a₁₂ a₁₃

a₂₁ a₂₂ a₂₃ = a₁₁ a₂₂ a₃₃ – a₁₂ a₂₁ a₃₃ – a₁₁ a₂₃ a₃₂ – a₁₃ a₂₂ a₃₁ + a₁₂ a₂₃ a₃₁ +

a₃₁ a₃₂ a₃₃ + a₁₃ a₂₁ a₃₂.

Видно, что определитель треугольной матрицы равен произведению диагональных элементов.

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

Все эти случаи легко проиллюстрировать для системы

a₁X+b₁Y=c₁,

a₂X+b₂Y=c₂.

Каждое из этих уравнений описывает прямую на плоскости; координаты точки пересечения указанных прямых являются решением системы. Рассмотрим три возможных случая взаимного расположения двух прямых на плоскости:

1. прямые пересекаются – коэффициенты системы не пропорциональны a₁/a₂ b₁/b₂;

2. прямые параллельны – коэффициенты системы подчиняются условиям a₁/a₂ = b₁/b₂ c₁/c₂;

3. прямые совпадают – все коэффициенты пропорциональны

a₁/a₂ = b₁/b₂ = c₁/c₂.

Отметим, что при выполнении первого условия , и система имеет единственное решение. В двух других случаях D=0 (во втором случае – отсутствие решения, в третьем – бесчисленное множество решений).

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

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

Заметим, что условие является необходимым, но не достаточным для плохой обусловленности системы линейных уравнений. Например, система уравнений n-го порядка с диагональной матрицей с элементами a_ii=0,1 не является плохо обусловленной, хотя ее определитель мал (D=10^-n).

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

2. Методы решения слау.

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

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

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

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

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

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

Рассмотрим прямые методы. Одним из способов решения СЛАУ является правило Крамера, согласно которому каждое неизвестное представляется в виде отношения определителей. Так, для системы

a₁₁X₁+a₁₂X₂=b₁,

a₂₁X₁+a₂₂X₂=b₂,

неизвестные находятся следующим образом

X₁=D₁/D, X₂=D₂/D,

г де D= a₁₁ a₁₂ , D₁= b₁ a₁₂ , D₂= a₁₁ b₁ .

a₂₁ a₂₂ b₂ a₂₂ a₂₁ b₂

В общем случае (без использования экономичных методов) для вычисления определителя порядка n требуется (n-1)n! умножений и n!-1 сложений, т.е. общее число арифметических операций равно

N_опр = (n–1)n!+n!–1 = nn!–1 nn!.

Нам нужно вычислить n+1 определитель, а затем произвести n делений, т.е. общее число операций для правила Крамера

N_Крам = (n+1)(nn!–1)+n.

Оцените время вычислений для ЭВМ с числом операций 10⁶ в секунду при n=100.

Известен также метод решения линейной системы с использованием обратной матрицы.

Матрица А^-1 называется обратной по отношению к квадратной матрице А, если их произведение равно единичной матрице АА^-1=А^-1А=Е. в линейной алгебре доказывается, что всякая невырожденная матрица А (т.е. с отличным от нуля определителем D) имеет обратную. При этом det A^-1=1/D.

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

a₁₁ --- a_1j --- a_1n

-----------------

A = a_i1 --- a_ij --- a_in .

-----------------

a_ni --- a_nj --- a_nn

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

Алгебраическим дополнением A_ij элемента a_ij называется его минор, взятый со знаком плюс, если сумма i+j номеров строки i и столбца j четная, и со знаком минус если эта сумма нечетная, т.е.

a₁₁ --- a_1,j-1 a_1,j+1 ---- a_1n

----------------------------------

A_ij = (–1)^i+j a_i-1,1 --- a_i-1,j-1 a_i-1,j+1 --- a_i-1,n

a_i+1,1 --- a_i+1,j-1 a_i+1,j+1 --- a_i+1,n

----------------------------------

a_n1 ---- a_n,j-1 a_n,j+1 --- a_nn

Каждый элемент b_ij (i,j=1,…,n) обратной матрицы В=А^-1 равен отношению алгебраического дополнения A_ij элемента a_ji (не a_ij) исходной матрицы А к значению ее определителя D:

A₁₁/D A₂₁/D --- A_n1/D

B = A^-1 = A₁₂/D A₂₂/D --- A_n2/D

---------------------------

A_1n/D A_2n/D --- A_nn/D

Система записывается как АХ=В. умножая обе части слева на обратную матрицу А^-1, получим Х=А^-1В. этот метод также мало пригоден при больших n из-за большого объема вычислений (N=[(n–1)(n–1)!–1]n²+n²+nn!-1=n²n!-1).