Прямые методы решения систем линейных алгебраических уравнений

Материал из Викиверситета

Постановка задачи[править]

Дана СЛАУ:

Предполагаем, что - невырожденная ( задача корректна). - приближенное решение задачи. Погрешность . Невязка

Определение. называется нормой вектора , если обладает свойствами:
  1. ,


Три варианта задания нормы:

Скалярное произведение: . Погрешности: ,

Определение. Сходимость по норме: - последовательность векторов при , если при .


Норма матрицы . Свойства:

Это подчиненные нормы

Обусловленность задачи решения СЛАУ[править]

Лемма. , где


Доказательство.


Теорема. - точное решение системы , где - приближенное к .

Тогда верно: , где

Доказательство. Здесь . Из леммы: . Разделим на :

- абсолютное число обусловленности для . - естественное число обусловленности (относительное). - число обусловленности.


Теорема. . Факты:
Теорема. - точное решение. - приближено заданная матрица . Тогда , где
Доказательство.


Методы решения[править]

Метод Гаусса[править]

Прямой ход:

1-й шаг - пусть . Найдем . Из уравнений вычитаем первое, домноженное на . Получаем:

2-й шаг - пусть

k-й шаг:

За (m-1) шаг получаем:

Обратный ход:

Из последнего уравнения находим , подставляем в предпоследнее, находим .

Трудоемкость:

1. m-1 деление, (m-1)m умножений, (m-1)m вычитаний

k.

Обратный ход: операций. Необходимость выбора главных элементов: главный элемент не должен быть равен нулю. Если он близок к нулю, растет погрешность (это для ЭВМ).

Матричная форма метода Гаусса. (LU - разложение)[править]

После первого шага получаем . Введем:

Начальная система: .

- верхняя треугольная матрица .

Свойства элементарных матриц:

  1. - нижние треугольные матрицы
  2. - тоже, только у вместо "-" стоит "+"

Теорема. Если все главные миноры матрицы , то нижняя треугольная матрица вида и верхняя треугольная матрица такие, что .

Использование:

  1. преобразуем в
  2. Решаем систему

Количество действий:

Модификации Гаусса[править]

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

Масштабирование - делим каждое уравнение на наибольший по модулю коэффициент.

Метод Холецкого[править]

, - симметричная (), положительно определенная ( - скалярное произведение на ) Проверка:

  1. Все главные миноры положительны
  2. - диагональное преобладание
  3. - столбцовое преобладание

Специальное - разложение: .

После получения этого разложения решаем . Это решение требует действий

Метод Прогонки[править]

Вывод:

Алгоритм

Прямой ход:

Обратный ход:

Количество операций: .

Теорема. Пусть . Тогда и
Доказательство.

Пусть и для некоторого . Тогда , и