Нормы векторов и матриц ~ Погрешности векторов и матриц ~ Обусловленность
задачи решения системы уравнений ~ Относительное
число обусловленности ~ Метод Гаусса
(схема единственного деления) ~ LU-разложение
матрицы
Нормы векторов и матриц. Обозначим
через - точное решение системы, а через -
приближенное решение системы. Для
количественной характеристики вектора
погрешности введем понятие нормы.
Нормой вектора называется число , удовлетворяющее
трем аксиомам:
1)
причем
= 0 тогда и только тогда, когда = 0;
2) для
любого вектора и любого числа ;
3) для
любых векторов и .
Наиболее употребительными являются следующие
три нормы:
, , .
Абсолютная и относительная погрешности
вектора вводятся с помощью формул:
и .
Нормой матрицы называется величина . Введенная норма
обладает свойствами, аналогичными свойствам
нормы вектора:
1)
причем
= 0 тогда и только тогда, когда A = 0;
2) для
любой матрицы A и любого числа ;
3) для
любых матриц A и B;
4) .
Каждой из векторных норм соответствует своя
подчиненная норма матрицы:
, , .
В оценках вместо нормы используется
евклидова норма матрицы
,
так как .
Абсолютная и относительная погрешности
матрицы вводятся аналогично погрешностям
вектора с помощью формул:
, .
ПРИМЕР 1. Вычисление норм
вектора и матрицы.
ПРИМЕР 2. Вычисление норм
матрицы.
Пусть рассматривается система линейных
алгебраических уравнений
В матричной форме записи она имеет вид .
Будем предполагать, что матрица системы
задана и является невырожденной. Известно, что в
этом случае решение системы существует,
единственно и устойчиво по входным данным.
Обусловленность задачи. Так же как
и другие задачи, задача вычисления решения
системы может быть как хорошо обусловленной, так
и плохо обусловленной.
Теорема об оценке погрешности
решения по погрешностям входных данных.
Пусть решение системы , а x* - решение
системы A*x*=b*, тогда , где -
относительное число обусловленности системы.
Если число обусловленности больше 10, то система
является плохо обусловленной, так как возможен
сильный рост погрешности результата.
ПРИМЕР 3. Оценка числа
обусловленности и эксперимент.
Метод Гаусса. Рассмотрим метод
Гаусса (схему единственного деления) решения
системы уравнений. Прямой ход состоит из m-1
шагов исключения.
1 Шаг. Исключим неизвестное из уравнений
с номерами i = 2,3,..m. Предположим, что .
Будем называть его ведущим элементом 1-го шага.
Найдем величины , i=2,3,...m , называемые
множителями 1-го шага. Вычтем последовательно из
второго, третьего, ...m vго уравнений системы
первое уравнение, умноженное соответственно на . В
результате 1-го шага получим эквивалентную
систему уравнений:
Аналогично проводятся остальные шаги. Опишем
очередной k-ый шаг. Предположим, что ведущий
элемент . Вычислим множители к-го шага:, i=k+1,...m
и вычтем последовательно из (k+1)-го, ...m v го
уравнений системы k-ое уравнение, умноженное
соответственно на
.После
(m-1)-го шага исключения получим систему
уравнений
,
матрица которой является верхней треугольной.
На этом вычисления прямого хода заканчиваются.
Обратный ход. Из последнего уравнения системы
находим . Подставляя найденное значение в
предпоследнее уравнение, получим . Далее
последовательно находим неизвестные .
LU разложение матрицы.
Представим матрицу A в виде произведения
нижней треугольной матрицы L и верхней
треугольной U.
Введем в рассмотрение матрицы
и
Можно показать, что A = LU. Это и есть
разложение матрицы на множители.
ПРИМЕР 4. Разложение матрицы A
на множители.
ПРИМЕР 5. Решение системы
уравнений с помощью LU - разложения матрицы.
|