Численные методы алгебры

Основные задачи

Решение СЛУ

Вычисление определителя

Нахождение обратной матрицы

Определение собственных значений

Вероятностные, (большое число неизвестных )

Итерационные (с числом неизвестных )

Точные (с малым

Недостатки:
Требуют хранения в ОП сразу всей матрицы.
Не учитывают структуру

Такое число называют нормой вектора x.

Итерационные, (число неизвестных )

Норма вектора:
Пусть

Примеры норм.

Евклидова норма

Норма матрицы, согласованная с нормой вектора:

Геометрическая интерпретация нормы матрицы –

Итерационные методы (общие принципы)

С их помощью строится последовательность такая, что

где

ШАГ 2. Расстановка индексов (номеров приближений) в системе
и задание нулевого

Метод простой итерации. (МПИ)

ШАГ 1. Матрица , т.е.

ШАГ 2. Составим

ШАГ 3. Выбираем начальное приближение из каких-либо условий.

По рекуррентной формуле

Если , то система имеет единственное решение и итерационный процесс по

Пусть система имеет единственное решение и итерационный процесс по формуле сходится

Это неравенство гарантирует сходимость МПИ только если

Пусть . Тогда при любом

Замечание 1

Априорная оценка позволяет подсчитать заранее число итераций k, достаточное для

3. Построим рекуррентную формулу

Метод Зейделя

Решаем систему

2. Важно – в матрице A

Если уменьшается, то метод сходится.

Геометрическая интерпретация метода

Формула равносильна формуле

Итерационный

y

x

L2

y

L1

L2

x

y

L1

L2

x

Метод сходится

Метод расходится

зацикливание

L1

Пример. Решить систему

методом простых итераций.

Решение.

Не выполняется достаточное условие сходимости (доминирование диагональных элементов)

Оценка погрешности найденных по формуле

даёт значение корня с погрешностью

Следующий шаг итерации. Находим и

Точное

Методы вариационного типа

Построим квадратичный функционал

где С – const

Где вещественная положительно

В силу самосопряжённости и положительности ,

Решение СЛАУ можно заменить задачей поиска

Метод покоординатного спуска

x2

x1

x*

(x10, x20)

Метод градиентного спуска

(x10, x20)

x1

x2

x*

Как выбирается параметр ?

Например выбирают из условия

метод наискорейшего спуска

Популярный метод сопряжённых градиентов

Нач. вектор