17.Арифметика чисел с плавающей точкой, фундаментальная аксиома арифметика с

18.Компьютерный алгоритм. Точность компьютерных алгоритмов . . . . . . . . . . . . . . . . 10

19.Устойчивость и обратная устойчивость компьютерных алгоритмов . . . . . . . . . . . . . 10

22.SVD-разложение и решение линейных систем . . . . . . . . . . . . . . . . . . . . . . . . . 11

23.Метод наименьших квадратов и SVD-разложение . . . . . . . . . . . . . . . . . . . . . . . 11

24.Псевдообратная матрица и SVD-разложение . . . . . . . . . . . . . . . . . . . . . . . . . . 12

25.Наилучшие аппроксимации матриц с понижением ранга . . . . . . . . . . . . . . . . . . . 12

26.Расстояние до множества вырожденных матриц . . . . . . . . . . . . . . . . . . . . . . . . 12

27.SVD и регуляризация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1

1. Нормированные пространства. Определение нормы. Эквивалентность норм

Пусть – линейное пространство, вещественное или комплексное. В дальнейшем под линейным пространством будем понимать R или C . Нормой в линейном пространстве называется отображение ‖ · ‖ : → R, ставящее в соответствие каждому вектору число ‖ ‖ R и удовлетворяющее аксиомам: , , R(C)

Линейное пространство с заданной на нем нормой ‖ · ‖ называется линейным нормированным пространством. Число ‖ ‖ называется нормой вектора .

Эквивалентность норм в конечномерном пространстве. Две нормы ‖ ‖1 и ‖ ‖2 в линейном пространстве называются эквивалентными, если существуют такие числа 1 > 0, 2 > 0, что для любого вектора выполняются неравенства

Теорема 1.1. В конечномерном пространстве любые две нормы эквивалентны.

2.Векторные нормы. Основные типы норм в арифметических пространствах

Наиболее употребительными в арифметических пространствах являются:

1)Октаэдрическая норма вектора (1-норма)

2) Евклидова или сферическая норма вектора (2-норма)

3) Кубическая норма вектора (∞-норма)

‖ ‖∞ = max | |.

16 6

4) Норма Гёльдера ( -норма)

Нетрудно заметить, что первые три векторные нормы являются частным случаем нормы Гёльдера, соответственно для = 1, 2, ∞.

3. Матричные нормы. Согласованные и индуцированные матричные нормы

Под нормой матрицы с действительными или комплексными элементами понимают действительное число ‖ ‖, т.е. отображение ‖ ‖ : R × (C × ) → R, и удовлетворяющее аксиомам:

2

3)‖ + ‖ 6 ‖ ‖ + ‖ ‖ (неравенство треугольника),

4)‖ ‖ 6 ‖ ‖ · ‖ ‖ (мультипликативность)

, R × (C × ) (согласованных относительно указанных операций матриц) и R(C). Иногда в определении нормы матрицы ограничиваются лишь первыми тремя аксиомами. В таком

случае норму матрицы называют обобщенной.

Примерами матричных норм матрицы = ( ) являются:

2)‖ ‖1 = max16 6 ∑ =1 | | – максимально столбцовая норма;

3)‖ ‖∞ = max16 6 ∑ =1 | | – максимально строковая норма;

2)Для евклидовой (сферической) нормы вектора ‖ ‖2, подчиненной матричной нормой является

спектральная матричная норма

где = ( * ), = 1, 2, . . . , .

3) Для кубической нормы вектора ‖ ‖∞, подчиненной матричной нормой является

4. Спектральная матричная норма

Для евклидовой (сферической) нормы вектора ‖ ‖2, подчиненной матричной нормой является

спектральная матричная норма

где = ( * ), = 1, 2, . . . , .

Для нормальных операторов спектральная норма оператора равна максимальному собственному значению. Сингулярные числа не изменяются при умножении оператора на унитарный. Спектральная норма оператора не изменяется при умножении оператора на унитарный.

3

5. Числа обусловленности матриц и СЛАУ

Величина ‖ ‖‖ −1‖ часто имеет другое название: ее называют числом обусловленности матрицы(относительно нормы ‖ · ‖) и определяется:

Так в этом случае термин «число обусловленности» относится к матрице, но не к задаче. Если ( ) мало, то говорят, что матрица хорошо обусловенная; если ( ) большое – плохо обусловленная.

в евклидовой векторной норме. Эта формула называется спектральным числом обусловленности матриц. Отношение 1/ можно интерпретировать как эксцентриситет гиперэллипсоида, являющегося образом единичной сферы из C на im .

6. Число обусловленности как мера чувствительности решения к возмущениям данных

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

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

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

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

Задача хорошо обусловленная если мало (например, 1, 10, 102), и плохо обусловленная если большое (например, 106, 1016).

7. Прямые и итерационные методы решения СЛАУ

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

Прямыми методами, к примеру, являются:

∙метод Гаусса

∙метод Крамера итерационными:

∙метод Якоби

∙метод Зейделя

4

8.Существование и единственность LU-разложения

Рассмотрим СЛАУ

где R × , R , = .

Пусть R × , × — соответственно нижняя и верхняя треугольные матрицы. Тогда справедлива теорема:

Теорема 8.1. Если все главные миноры матрицы отличны от нуля, то существуют такие нижняя и верхняя треугольные матрицы, что = . Если элементы диагонали одной из матриц или фиксированы (ненулевые), то такое разложение единственно.

Элементы матриц = ( ) и = ( ) могут быть найдены с помощью формул:

−1

9. Метод исключения Гаусса с выбором ведущего элемента

Выполнение алгоритма -разложения может прекратиться или привести к неверным результатам, если элементы (ведущие или главные) на каком-то этапе окажутся равными нулю или очень маленькими числами. Чтобы уменьшить влияние ошибок округления и исключить деление на нуль, на каждом -ом этапе ( = 1, 2, . . . , ) используется стратегия выбора ведущего элемента.

Различают стратегии выбора ведущего элемента по строке, столбцу, активной подматрице. Рассмотрим выбор ведущего элемента по строке на каждом -ом этапе ( = 1, 2, ..., ):

1) Находим > :

= max | |,6 6

если = 0, то матрица СЛАУ вырожденная (вся строка нулевая);

2) меняем местами в матрице А и частично сформированной матрице местами -й и -й столбцы.

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

Отсюда видно, что соответствующие перестановки необходимо делать и в полученном векторе .

10. Ортогональные методы решения СЛАУ (QR-разложение)

Разложение квадратной матрицы на множители

такие, что — верхняя треугольная матрица, — ортогональная, называется –разложением матрицы .

Построение –разложение сводится к преобразованию матрицы уножением на ортогональные матрицы 1, 2, . . . , так, что в результате = . . . 1 . Тогда, полагая = ( . . . 1)−1 = ( . . . 1)T получается представление 10.1. Двумя основными методами построения таких матриц являются метод отражений и метод вращений.

5