19.1. Основные понятия и определения

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

Задача отыскания решения СЛАУ с n неизвестными - одна из наиболее часто встречающихся в практике вычислительных задач, так как большинство методов решения сложных задач основано на сведении их к решению некото­рой последовательности СЛАУ.

Обычно СЛАУ записывается в виде

n

^ciyXj = b_i ;1 < i < n, или коротко

j=1

AX = b,

A =

x =

b =

(19.1)

Xi

^a\\^a\2---^a\n

x

a_lxa₂₁...a_ln

^anl^an 2^...ann

Здесь А и b заданы, требуется найти X *, удовлетворяющий (19.1).

Известно, что если определитель матри-

— цы \A ф 0, то СЛАУ имеет единственное ре-^xi

Р_ис 19 1 шение. В противном случае решение либо от-

сутствует (если b ф 0), либо имеется беско­нечное множество решений (если b = 0). При решении систем, кроме условия |A| ф 0, важно

чтобы задача была корректной, т.е. чтобы при малых погрешностях правой части Ab и (или) коэффициентов Aa^ погрешность решения AX * также оста­валась малой. Признаком некорректности, или плохой обусловленности, яв­ляется близость к нулю определителя матрицы.

Плохо обусловленная система двух уравнений геометрически соответ­ствует почти параллельным прямым (рис.19.1). Точка пересечения таких пря­мых (решение) при малейшей погрешности коэффициентов резко сдвигается. Обусловленность (корректность) СЛАУ характеризуется числом

^{X = |AI • A-1 > 1. Чем дальше х от 1, тем хуже обусловлена система. Обычно}

при х > 10 система некорректна и требует специальных методов решения -методов регуляризации. Приведенные ниже методы применимы только для корректных систем.

Методы решения СЛАУ делятся на прямые и итерационные.

Прямые методы дают в принципе точное решение (если не учитывать ошибок округления) за конечное число арифметических операций. Для хоро­шо обусловленных СЛАУ небольшого порядка n < 200 применяются практи­чески только прямые методы.

Наибольшее распространение среди прямых методов получили метод Гаусса для СЛАУ общего вида, его модификация для трехдиагональной мат­рицы - метод прогонки и метод квадратного корня для СЛАУ с симметрич­ной матрицей.

Итерационные методы основаны на построении сходящейся к точно-

му решению

X

рекуррентной

последовательности

векторов

x ■ x ■

-> x . Итерации выполняют до тех пор, пока норма < s. (г- заданная малая величина).

Итерационные методы выгодны для систем большого порядка n>100, а также для решения плохо обусловленных систем. Многообразие итерацион­ных методов решения СЛАУ объясняется возможностью большого выбора рекуррентных последовательностей, определяющих метод. Наибольшее рас­пространение среди итерационных методов получили одношаговые методы простой итерации и Зейделя с использованием релаксации.

Для контроля полезно найти невязку полученного решения х:

max

1<к <n

_I

^aM^xi

если А велико, то это указывает на грубую ошибку в расчете.

Ниже приведено описание алгоритмов указанных методов решения

СЛАУ.