Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Статистика
На русском, статей
Улучшено за 24 ч.
Добавлено за 24 ч.
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

Метод сопряжённых градиентов (для решения СЛАУ)

Из Википедии — свободной энциклопедии

Сравнение методов градиентного спуска(зеленый) и метода сопряженных градиентов для  n = 2 {\displaystyle n=2}
Сравнение методов градиентного спуска(зеленый) и метода сопряженных градиентов для

Метод сопряженных градиентов — численный метод решения систем линейных алгебраических уравнений, является итерационным методом Крыловского типа.

Постановка задачи

Пусть дана система линейных уравнений: . Причём матрица системы — это действительная матрица, обладающая следующими свойствами: , то есть это симметричная положительно определённая матрица. Тогда процесс решения СЛАУ можно представить как минимизацию следующего функционала:

За обозначено скалярное произведение. Минимизируя данный функционал, используя подпространства Крылова, получаем алгоритм метода сопряженных градиентов.

Алгоритм

Подготовка перед итерационным процессом
  1. Выберем начальное приближение
-я итерация метода[1]
Критерий остановки

Поскольку минимизируемый функционал квадратичный, то процесс должен дать ответ на -й итерации, однако при реализации метода на компьютере существует погрешность представления вещественных чисел, в результате чего может потребоваться и больше итераций. Так же оценивать точность можно по относительной невязке , и прекращать итерационный процесс, когда невязка станет меньше заданного числа.

Алгоритм для предобусловленной системы

Пусть предобусловленная система имеет вид: , тогда алгоритм метода для такой системы можно записать следующим образом:

Подготовка перед итерационным процессом
  1. Выберем начальное приближение
-я итерация метода
После итерационного процесса
  1. , где  — приближенное решение системы,  — общее число итераций метода.
Критерий остановки

В данном случае можно использовать те же критерии остановки, что и для обычной системы, только с учётом предобуславливания. Например относительная невязка станет вычисляться как: , однако можно пользоваться и невязкой исходной системы, которая вычисляется следующим образом:

Особенности и обобщения

Как и все методы на подпространствах Крылова, метод сопряженных градиентов от матрицы требует только возможность умножать её на вектор, что приводит к возможности использовать специальные форматы хранения матрицы(такие, как разреженный) и сэкономить память на хранении матрицы.
Метод часто используется для решения конечноэлементых СЛАУ.
У метода есть обобщения: метод бисопряженных градиентов, для работы с несимметричными матрицами. И комплексный метод сопряженных градиентов, где матрица может содержать комплексные числа, но должна удовлетворять условию: , то есть быть самосопряженной-положительно определённой матрицей.

Примечания

  1. Henk A. van der Vorst. Iterative Krylov Methods for Large Linear System. — Cambridge University Press, 2003. — 221 с. — ISBN 9780521818285.
Эта страница в последний раз была отредактирована 7 декабря 2020 в 07:09.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).