Прямые методы решения систем ЛАУ.

Пусть задана система линейных алгебраических уравнений (ЛАУ) в стандартной форме:

,

где - матрица , , , .

Если - то решение системы существует и единственно.

Формальное решение системы можно записать по известным формулам Крамера

,

где определители вычисляются по известному правилу.

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

Прямые методы основаны на последовательном исключении неизвестных и приведении матрицы A к треугольному виду (метод Гаусса и его модификации, основанные на определенном правиле выбора главного элемента). Эти методы дают решение СЛАУ за конечное число арифметических операций – это их основное преимущество. Число операций, затрачиваемых на приведение системы к треугольному виду и последующее решение пропорционально . Основной недостаток прямых методов – возможно сильное накопление ошибок округлений при делении на малые числа. Кроме того, возможно возникновение так называемой неустранимой погрешности, если система (и соответственно матрица ) плохо обусловлена. Это свойство систем обсуждается далее в п.п.3.4.2.

Итерационные методы более эффективны в вычислении и применяются для разреженных (слабо заполненных) систем порядка и более.

Метод Гаусса обычно изучается в курсе линейной алгебры, и мы его рассматривать не будем. Более подробно рассмотрим итерационные методы. Для тех или иных оценок решения понадобится понятие нормы вектора и нормы матрицы, которые мы и обсудим в следующем параграфе.

3.4.2. Нормы векторов и матриц.

Пусть - вектор-столбец, . Приведем некоторые известные нормы векторов:

1. - эклидова норма вектора;

2. - так называемая - норма, или норма Гильберта-Шмидта (при совпадает с эвклидовой нормой, а при совпадает с так называемой 1-нормой).

3. - чебышевская норма.

Все эти нормы в эквивалентны: сходимость в одной из этих норм влечет за собой сходимость в другой (следствие конечности ).

Перейдем к понятию матричной нормы. Пусть - множество квадратных вещественных матриц порядка . Пусть каждой матрице поставлено в соответствие число . Это число называется нормой матрицы A, если выполняются следующие аксиомы:

1. ;

2. ;

3. - неравенство треугольника;

4. - кольцевое свойство.

Определение 1. Норма называется мультипликативной, если выполняются все четыре аксиомы, и аддитивной, если выполняются только первые три аксиомы.

Определение 2. Если матричная норма удовлетворяет условию

, где ,

(1)

то такая норма называется согласованной с нормой вектора.

Большинство используемых в численном анализе матричных норм согласованы с той или иной векторной нормой.

Определим некоторые наиболее употребительные на практике матричные нормы.

-

- евклидова норма или норма Фробениуса (norm (a,‘ fro ’) - в MATLAB).

-

- спектральная норма (norm (a)= norm (a,2) в MATLAB),

где - собственные значения симметричной матрицы (сингулярные числа матрицы А). Обе указанные нормы согласованы с эвклидовой нормой вектора .

-

- столбцовая норма (norm (a,1)). (Согласована с векторной нормой ).

-

- строчная норма (norm (a, inf)). (Согласована с ).

Замечание. Из всех приведенных матричных норм, согласованных с евклидовой нормой вектора, спектральная норма принимает минимальное значение.

Определение 3. Число (вообще говоря, комплексное) называется собственным значением матрицы А, соответствующим собственному вектору x, если выполняется условие:

.

(20)

Определение 4. Множество всех собственных чисел матрицы А , записанных с учетом их кратности, называется спектром матрицы А и обозначается S (A).

Определение 5. Спектральным радиусом r(A) квадратной матрицы А называется максимальное по модулю собственное значение матрицы A.

Система (20) эквивалентна следующей однородной системе уравнений:

.

(21)

Как известно из курса линейной алгебры, система (21) имеет нетривиальные решения тогда и только тогда, когда

.

(22)

Уравнение (22) - алгебраическое уравнение n -ой степени относительно . Все его корни – собственные значения матрицы А.

Определение 6. Сингулярным числом матрицы А называется собственное значение матрицы .

Определение 7. Матрица А называется положительно (неотрицательно) определенной (пишут: или ), если соответствующая квадратичная форма

.

Простейшие следствия из определений.

Следствие 1. (Критерий Сильвестра). все ведущие угловые миноры матрицы А положительны. доказывается в курсе линейной алгебры

Следствие 2. , причем .

следует из критерия Сильвестра.

Следствие 3. все собственные значения . (Для ).

Пусть - собственное значение, соответствующее собственному вектору v. По условию

.

Следствие 4. Пусть А – вещественная матрица матрица .

Имеем: {по свойству скалярного произведения} .

Следствие 5. Сингулярные числа вещественной матрицы А – неотрицательны.

Следует из С.3 и С.4.

Следствие 6. Пусть А – вещественная и симметрическая матрица .

Имеем: .

Следствие 7. Если А – невырожденная матрица собственные значения матриц А и A ^-1 взаимообратны.

Пусть результат.

3.4.3. Обусловленность матриц и систем уравнений.

Пусть дана система ЛАУ с невырожденной матрицей А :

Ax = b,

(23)

и пусть вектор правой части b вычисляется с ошибкой .

Заменим правую часть “возмущенным” значением , тогда решение приобретет ошибку и система примет вид:

.

(24)

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

Из (23) и (24) следует: или .

Из совокупности равенств

{согласованность матриц} .

(25)

С другой стороны, из (23) следует

.

Последнее неравенство подставим в (25)

.

(26)

Определение 6. Число называется числом обусловленности матрицы А.

Таким образом, из (26) следует, что относительная ошибка решения пропорциональна числу обусловленности матрицы А:

.

Если (система уравнений плохо обусловлена), то небольшие погрешности вычисления правой части (небольшие “возмущения”) могут приводить к весьма большим отклонениям от точного решения.

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

Примеры плохо обусловленных систем рекомендуется рассмотреть на семинаре и лабораторной работе.

3.4.4. Итерационные методы решения систем ЛАУ.

Рассмотрим вначале систему ЛАУ специального вида

x = Tx + d, , , T - матрица .

(27)

Назовем эту систему системой второго рода, в отличие от вида системы (23) из параграфа 3.4.3. – системы первого рода.

Систему второго рода (27) естественно пытаться решать итерационным методом

(28)

В этом методе используются лишь операции сложения и умножения, и не используется операция обращения матрицы – наиболее опасная для накопления ошибок.

Теорема 3.6. Для любой согласованной матричной нормы имеет место неравенство .

Пусть - собственный вектор матрицы , - соответствующее собственное значение. Тогда справедлива следующая цепочка равенств и неравенств:

, в силу согласованности норм. Отсюда получаем

. В силу произвольности собственного значения , получаем требуемый результат .

Теорема 3.7. (Достаточное условие сходимости).Пусть система (1) невырождена, т.е. имеет единственное решение , матрица - вещественная, причем (в какой-либо матричной форме), тогда итерационная процедура (28) сходится к решению при со скоростью геометрической прогрессии.

.Поскольку - решение системы (27), то . Найдем разность

.

Обозначим - вектор ошибки k- ого шага. Тогда получаем итерационную процедуру

(29)

Оператор - линейный и отображает в себя. Согласно основному принципу сжатых отображений (теорема 3.1, замечание 2) для банахова пространства): если оператор T удовлетворяет условию Липшица с константой

то оператор T в уравнении (29) – сжимающий и выполняется принцип сжатых отображений.

В нашем случае имеем:

.

Т.к. по условию оператор - сжимающий и, следовательно, существует единственная неподвижная точка уравнения

(30)

Обозначим эту точку . Таким образом, выполняются уравнения:

и, кроме того, по определентю . Отсюда

,

Откуда получаем: . Из единственности решения системы (27) получаем:

, т.е. и итерационная процедура (28) сходится к единственной неподвижной точке со скоростью геометрической прогрессии .

Теорема 3.8. (Спектральный признак сходимости).Для сходимости метода простых итераций СЛАУ второго рода необходимо и достаточно, чтобы .

Необходимость. Заметим, что если оператор удовлетворяет условию сжатости, то согласно теореме 3.6 .

Пусть теперь известно, что итерационная процедура (28) сходится при . От противного: пусть и - соответствующий собственный вектор. Выберем начальное приближение и запустим итерационную процедуру (29).

что противоречит сходимости при начальном приближении .

Достаточность. Докажем для частного случая, когда - вещественная и симметрическая матрица.

Выберем спектральную норму (норму -2):

, где - сингулярные числа матрицы .

Согласно свойству 6) , где - собственные значения матрицы . - т.е. получили достаточное условие сходимости согласно теореме 3.7. в норме -2.

Т.к. все матричные нормы эквивалентны, то сходимость в норме -2 влечет за собой сходимость и в остальных нормах.

Дата добавления: 2015-07-16