2014-02-09
693
Основная классификация численных методов решения систем линейных алгебраических уравнений
Численные методы решения систем линейных алгебраических уравнений (СЛАУ), общий вид которых
, (5)
где 
- матрица системы, 
- вектор неизвестных и правой части соответственно, делятся на два больших класса: прямые (или точные) и итерационные (или приближенные).
Далее будем рассматривать неоднородные системы с квадратными вещественными матрицами: 
, 
.
Точные методы – это методы, которые в предположении отсутствия округлений дают точное решение СЛАУ после конечного, определяемого заранее числа арифметических операций.
Итерационные методы – это методы, которые в предположении отсутствия округлений дают, в общем случае, точное решение СЛАУ после бесконечного числа операций. Их общая идея заключается в следующем: по заданной матрице системы , вектору правой части 
и некоторому начальному приближению 
к решению СЛАУ находится следующее приближение 
, по которому на следующем шаге строится приближение 
к решению и т.д. Получаем бесконечную векторную последовательность 
приближений к решению: , ,...,
,.... Итерационный процесс строится таким образом, чтобы 
. В этом случае говорят о сходящемся итерационном процессе. Таким образом, искомое решение – это предел последовательности приближений, а значит может быть получен только за бесконечное число шагов.
Более подробно отличия прямых и итерационных методов будут рассмотрены в теме «Итерационные методы решения СЛАУ».
Определение. Величину
(10)
называют числом обусловленности матрицы по отношению к используемой матричной норме 
.
Для невырожденной матрицы 
.
Определение. Матрица называется хорошо обусловленной, если 
, и плохо обусловленной, если 
.
Замечание. Из (10) вытекает, что значение числа обусловленности матрицы зависит от выбранной для его вычисления матричной нормы, но если матрица будет хорошо (плохо) обусловленной в какой-либо матричной норме, то она сохранит это свойство и в любой другой матричной норме.
В силу наличия погрешностей при решении СЛАУ, можно считать, что получаемое приближенное решение 
для СЛАУ (5) является точным решением, но некоторой другой – возмущенной – СЛАУ:
,
где матрица 
и вектор 
- малые ошибки в начальных данных. можно показать, что относительная погрешность решения СЛАУ (5) может быть оценена выражением:
.
Таким образом, число обусловленности матрицы системы является мерой чувствительности задачи о решении СЛАУ к погрешностям в начальных данных.
Определение. Пусть приближенное решения СЛАУ (5), тогда в общем случае 
. Назовем вектором невязки вектор 
, определяемый в соответствии с формулой:
.
Вопрос: Если элементы вектора невязки близки к нулю, следует ли из этого, что близко к точному решению 
СЛАУ (5)?
В общем случае ответ на поставленный вопрос – НЕТ. Покажем это:
.
Поскольку равны векторы 
, то равны и их нормы:
,
тогда
. (15)
Из (5) получаем, что
. (20)
Перемножим почленно неравенства (15) и (20):
. (25)
Поскольку СЛАУ является неоднородной, то 
и 
, а следовательно 
и 
. Разделим обе части неравенства (25) на 
:
. (30)
Из соотношения (30) вытекает, что из «малости» нормы вектора невязки малая относительная погрешность решения СЛАУ следует только тогда, когда матрица СЛАУ является хорошо обусловленной. В противном случае, даже когда 
выводов о качестве полученного приближенного решения 
сделать нельзя: за счет большого значения 
может быть далеко от истинного решения даже при .
Вопросы
