Некорректные задачи линейной алгебры

Глава 3. Некорректные задачи линейной алгебры

ля понимания влияния на устойчивость, рассмотрим систему с возмущенной правой частью Здесь через обо­
значено отклонение решения, вызванное возмущением правой части. Очевидно, что . Из определения числа обусловленности следу­ет, что

и — наименьшая константа, гарантирующая это неравенство. Та­ким образом, число обусловленности позволяет оценить относи­тельную погрешность решения через относительную погреш­ность правой части Плохо обусловленные системы — это си­стемы с очень большим числом обусловленности .
Решение системы линейных алгебраических уравнений может быть некорректной задачей для прямоугольных матриц А а также для квадратных вырожденных или плохо обусловленных матриц.
Методы решения систем линейных уравнений делятся на две основ­ные группы — прямые и итерационные. Прямые методы дают решение после выполнения заранее известного числа операций. Эти методы срав­нительно просты и универсальны, но требуют, как правило, большого объема памяти ЭВМ и накапливают погрешности в процессе решения, поскольку вычисления на любом этапе используют результаты преды­дущих операций. В связи с этим прямые методы применимы для срав­нительно небольших (п < 200) систем с плотно заполненной матрицей и не близким к нулю определителем. К прямым методам относятся, наг пример, метод Гаусса, метод Жордана, метод квадратного корня, метод сингулярного разложения и т. д. Прямые методы (иногда называемые точными, хотя в виду неизбежных погрешностей при численной реа­лизации это название является условным) также успешно применяются для решения систем линейных алгебраических уравнений.
Итерационные методы — это методы последовательных приближе­ний. Объем вычислений заранее определить трудно, но они требуют меньшего объема памяти, чем прямые методы. Итерационные методы часто используются при регуляризации некорректных систем линейных уравнений. Однако, стоит отметить, что часто наиболее эффективным способом решения линейной системы является сочетание итерационо- го подхода с прямыми методами. В таких смешанных алгоритмах ите­рационные методы используются для уточнения решений, полученных с помощью прямых методов.
В данной главе мы рассмотрим систему линейных алгебраических уравнений для прямоугольной матрицы А и опишем как итерационные (регуляризующие), так и некоторые прямые алгоритмы для ее решения.

1. 
   Обобщение понятия решения. Псевдорешение
   

Прежде чем перейти к изложению методов приближенного решения системы уравнений обсудим понятие решения этой системы, ко­торая в общем случае может быть переопределенной, недоопределенной или плохо обусловленной.
Здесь и далее , А — вещественная матрица размера , которую называем тхп-матрицей в случае, когда необходимо указать ее размер.
Вектор реализующий минимум нормы невязки
, (3.1.1)
называется псевдорешением системы (см. определение 2.9.1), т. е.
Поскольку для приращения функционала справедливо представ­ление
необходимым условием минимума будет
,
где — транспонированная матрица. Следовательно, вектор явля­ются решением системы уравнений
(3.1.2)