Читайте также:
|
|
Пусть задана система линейных алгебраических уравнений (ЛАУ) в стандартной форме:
,
где - матрица
,
,
,
.
Если - то решение системы существует и единственно.
Формальное решение системы можно записать по известным формулам Крамера
,
где определители вычисляются по известному правилу.
Однако с вычислительной точки зрения формальное решение не эффективно (хотя и устойчиво) – требует слишком много операций на вычисление определителей (для каждого определителя слагаемых). Это совершенно неприемлемо даже для современных компьютеров уже при
. Поэтому используются другие методы численного решения. Эти методы делятся на две большие группы: 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, ![]() ![]() ![]() | (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; просмотров: 152 | Нарушение авторских прав
<== предыдущая страница | | | следующая страница ==> |
Метод Ньютона в многомерном случае. | | | Стационарные итерационные процедуры. |