WikiDer > Метод двусопряженного градиента

Biconjugate gradient method

В математика, более конкретно в числовая линейная алгебра, то метод двусопряженных градиентов является алгоритм решать системы линейных уравнений

в отличие от метод сопряженных градиентов, этот алгоритм не требует матрица быть самосопряженный, но вместо этого нужно выполнить умножение на сопряженный транспонировать А*.

Алгоритм

  1. Выберите первоначальное предположение , два других вектора и и предварительный кондиционер
  2. за делать

В приведенной выше формулировке вычисленное и удовлетворить

и, таким образом, соответствующие остатки соответствующий и , как приближенные решения систем

это прилегающий, и это комплексно сопряженный.

Безусловная версия алгоритма

  1. Выберите первоначальное предположение ,
  2. за делать

Обсуждение

Метод двусопряженных градиентов численно нестабильный[нужна цитата] (сравните с метод двусопряженной градиентной стабилизации), но очень важный с теоретической точки зрения. Определите шаги итерации с помощью

куда используя соответствующие проекция

с

Эти связанные прогнозы могут быть повторены как

Отношение к Квазиньютоновские методы дан кем-то и , куда

Новые направления

тогда ортогональны остаткам:

которые сами удовлетворяют

куда .

Метод двусопряженного градиента теперь делает особый выбор и использует настройку

При этом конкретном выборе явные оценки и А−1 избегаются, и алгоритм принимает форму, указанную выше.

Характеристики

  • Если является самосопряженный, и , тогда , , а метод сопряженных градиентов производит ту же последовательность за половину вычислительных затрат.
  • Последовательности, производимые алгоритмом: биортогональный, т.е. за .
  • если является многочленом с , тогда . Таким образом, алгоритм производит проекции на Крыловское подпространство.
  • если является многочленом с , тогда .

Смотрите также

Рекомендации

  • Флетчер Р. (1976). Уотсон, Г. Алистер (ред.). «Методы сопряженных градиентов для неопределенных систем». Числовой анализ. Конспект лекций по математике. Springer Berlin / Heidelberg. 506: 73–89. Дои:10.1007 / BFb0080109. ISBN 978-3-540-07610-0. ISSN 1617-9692.
  • Нажмите, WH; Теукольский С.А.; Феттерлинг, штат Вашингтон; Фланнери, ВР (2007). «Раздел 2.7.6». Числовые рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN 978-0-521-88068-8.