Дана СЛАУ:
Предполагаем, что - невырожденная ( задача корректна). - приближенное решение задачи.
Погрешность . Невязка
Определение. называется нормой вектора , если обладает свойствами:
- ,
Три варианта задания нормы:
Скалярное произведение: . Погрешности: ,
Определение. Сходимость по норме: - последовательность векторов при , если при .
Норма матрицы . Свойства:
Это подчиненные нормы
Обусловленность задачи решения СЛАУ
[править]
Лемма. , где
Доказательство.
Теорема. . Факты:
Теорема. - точное решение. - приближено заданная матрица . Тогда , где
Доказательство.
Прямой ход:
1-й шаг - пусть . Найдем . Из уравнений вычитаем первое, домноженное на . Получаем:
2-й шаг - пусть
k-й шаг:
За (m-1) шаг получаем:
Обратный ход:
Из последнего уравнения находим , подставляем в предпоследнее, находим .
Трудоемкость:
1. m-1 деление, (m-1)m умножений, (m-1)m вычитаний
k.
Обратный ход: операций.
Необходимость выбора главных элементов: главный элемент не должен быть равен нулю. Если он близок к нулю, растет погрешность (это для ЭВМ).
Матричная форма метода Гаусса. (LU - разложение)
[править]
После первого шага получаем . Введем:
Начальная система: .
- верхняя треугольная матрица .
Свойства элементарных матриц:
- - нижние треугольные матрицы
- - тоже, только у вместо "-" стоит "+"
Теорема. Если все главные миноры матрицы , то нижняя треугольная матрица вида и верхняя треугольная матрица такие, что .
Использование:
- преобразуем в
- Решаем систему
Количество действий:
- на k-м шаге в качестве главного элемента выбираем максимальный по модулю коэффициент и переставляем строки.
- на каждом шаге выбираем максимальный по модулю коэффициент из строк с номерами и переставляем строки (столбцы)
Масштабирование - делим каждое уравнение на наибольший по модулю коэффициент.
, - симметричная (), положительно определенная ( - скалярное произведение на )
Проверка:
- Все главные миноры положительны
- - диагональное преобладание
- - столбцовое преобладание
Специальное - разложение: .
После получения этого разложения решаем . Это решение требует действий
Вывод:
Алгоритм
Прямой ход:
Обратный ход:
Количество операций: .
Теорема. Пусть . Тогда и