Вариационные методы решения СЛАУ (методы минимальных невязок, минимальных поправок, наискорейшего спуска, сопряженных градиентов)
Краткое сожержание материала:
Размещено на
Содержание
1. Введение. Постановка задачи.
2. Описание методов решения задачи
2.1 Метод минимальных невязок
2.2 Метод минимальных поправок
2.3 Метод скорейшего спуска
2.4 Метод сопряженных градиентов
3. Алгоритмы и блок-схемы решения
3.1 Метод минимальных невязок
3.2 Метод минимальных поправок
3.3 Метод скорейшего спуска
3.4 Метод сопряженных градиентов
4.Руководство пользователя.
5. Тестирование и оптимизация.
6. Выводы
Список использованных источников
Приложение 1. Контрольные примеры.
Приложение 2. Код программы.
1. Введение. Постановка задачи
Большое количество задач математики и физики сводится к решению дифференциальных уравнений в частных производных, решение которых, в свою очередь, приводит к решению систем линейных алгебраических уравнений (СЛАУ). Методы решения СЛАУ, можно разделить на прямые методы, позволяющие получить точное решение системы (к ним относится, например, метод Гаусса, метод Крамера и т. д.) и итерационные методы, позволяющие получить решение системы с заданным приближением. Среди итерационных методов особое место занимают методы вариационного типа, особенностью которых является то, что при их использовании нет необходимости знать границы спектра матрицы системы.
Итак, сформулируем задачу:
Дана система линейных уравнений
где A симметричная положительно определенная матрица.
Требуется решить данную СЛАУ следующими итерационными методами вариационного вида:
1. Метод минимальных невязок
2. Метод минимальных поправок
3. Метод скорейшего спуска
4. Метод сопряженных градиентов
Методы решения СЛАУ рассматриваются практически в каждой книге по численным методам. Общее описание алгоритмов для каждого метода дано, например, в книге Самарского А.А., Гулина А.В. «Численные методы» [3]. Также популярными книгами являются: М.Ю. Баландин, Э.П. Шурина “Методы решения СЛАУ большой размерности” [1], Y.Saad “Iterative Method for Sparse Linear System” [5]. В перечисленных книгах, описаны такие методы как CG (Conjugate Gradient - метод сопряжённых градиентов) и MinRES (Minimal Residual - метод минимальных невязок). В книге [5] изложены не только базовые алгоритмы данных методов, но и указания к их практической реализации.
2. Описание методов решения задачи
2.1 Метод минимальных невязок
Рассмотрим систему с матрицей A=AT>0. Обозначим через
(1)
невязку, которая получается при подстановке приближенного значения xk, полученного на k-й итерации, в уравнение (1). Заметим, что погрешность zk=xkх и невязка rk связаны равенством Azk=rk.
Рассмотрим явный итерационный метод
, (2) <=> (3)
где параметр k+l выбирается из условия минимума погрешности ||rk+1|| при заданной норме ||rk||. Метод (2) называется методом минимальных невязок.
Найдем явное выражение для параметра k+l. Из (3) получаем
, (4) => (5)
т. е. rk удовлетворяет тому же уравнению, что и погрешность zk=xkх. Возводя обе части уравнения (5) для невязки скалярно в квадрат, получаем
(6)
Отсюда видно, что |||rk+1|| достигает минимума, если
(7)
Таким образом, в методе минимальных невязок переход от k-й итерации к (k+1)-й осуществляется следующим образом. По найденному значению xk вычисляется вектор невязки rk=Axkf и по формуле (7) находится параметр k+l. Затем по формуле (3) досчитывается вектор xk+1.
Метод минимальных невязок (3), (7) сходится с той же скоростью, что и метод простой итерации с оптимальным параметром .
2.2 Метод минимальных поправок
Рассмотрим неявный итерационный метод вида
, (8)
Запишем этот метод в виде
. (9)
Вектор k =B1rk называется поправкой на (k+1)-й итерации. Она удовлетворяет тому же уравнению, что и погрешность zk=xkx неявного метода, т. е. уравнению
. (10)
Будем предполагать, что B=BT>0. Методом минимальных поправок называется неявный итерационный метод (8), в котором параметр k+l выбирается из условия минимума нормы ||k+1||B=(Bk+1,k+1)1/2 при заданном векторе k. В случае B=Е метод минимальных поправок совпадает с методом минимальных невязок.
Найдем выражение для итерационного параметра k+l. Перепишем (10) в виде
и вычислим
.
Отсюда следует, что минимум этого выражения достигается при
. (11)
Для реализации метода минимальных поправок требуется на каждой итерации решить две системы уравнений Bk= rk и Bvk=Ak, откуда найдем вектор vk = B1 Аk (воспользуемся формулой (9)) .
Скорость сходимости метода минимальных поправок определяется границами спектра обобщенной задачи на собственные значения
. (12)
2.3 Метод скорейшего спуска
Рассмотрим явный метод (2) и выберем итерационный параметр k+l из условия минимума ||zk+1||A при заданном векторе zk, где zk+1=xk+1x. Поскольку погрешность zk удовлетворяет уравнению
, то
.
Следовательно, это выражение достигает минимума, если
.
Величина zk=xkx здесь неизвестна (так как неизвестно точное решение х), поэтому надо учесть, что Azk=rk=Axkf, и вычислять k+l по формуле
. (13)
2.4 Метод сопряженных градиентов
Пусть A - матрица системы . Рассмотрим следующий класс неявных двухшаговых итерационных методов:
. (14)
Здесь , k+l, k+l - итерационные параметры, которые будут определены далее. Начальное приближение x0 будем задавать произвольно, а вектор x1 вычислять по одношаговой формуле, которая получается из (14) при k=0 и l=1,
. (15)
Вариационные методы решения систем линейных уравнений
Решение дифференциальных уравнений в частных производных. Метод минимальных невязок, минимальных поправок, скорейшего спуска, сопряженных градиентов....
Методы решения задач оптимального проектирования ВС
Методы решения задач безусловной оптимизации: Классический метод, метод Ньютона, метод градиентного спуска, метод сопряженных градиентов, метод случа...
Численные методы решения задач условной многомерной оптимизации
Рассмотрение эффективности применения методов штрафов, безусловной оптимизации, сопряженных направлений и наискорейшего градиентного спуска для решени...
Метод ортогонализации и метод сопряженных градиентов
Методы решения систем линейных алгебраических уравнений, их характеристика и отличительные черты, особенности и сферы применения. Структура метода орт...
Градиентные методы для решения систем линейных уравнений
Алгоритм минимизации функции нескольких переменных методами сопряженных градиентов и покоординатного спуска. Проведение сравнения их скорости работы,...