Магистратура
  1. Введение в математический анализ  1.1. Теория множеств и логика в реальном анализе  1.1.1. Множества и операции в теории множеств и логике в реальном анализе  1.1.2. Отношения и функции  1.1.3. Логика и кванторы  1.1.4. Мощность множеств  1.2. Метрика  1.2.1. Введение в открытые и замкнутые множества в метрических пространствах  1.2.2. Сходимость последовательностей в метрическом пространстве  1.2.3. Непрерывная функция в метрическом пространстве  1.2.4. Компактность и полнота в метрических пространствах в реальном анализе  1.3. Последовательности и ряды  1.3.1. Сходимость последовательностей  1.3.2. Бесконечные ряды  1.3.3. Равномерная сходимость  1.3.4. Ряды степеней  1.4. Дискриминация  1.4.1. Теорема о среднем значении  1.4.2. Ряд Тейлора  1.4.3. Функции нескольких переменных  1.4.4. Частная производная  1.5. Интеграция  1.5.1. Интегрирование Римана и Лебега  1.5.2. Неправильные интегралы  1.5.3. Теория меры: фундаментальный инструмент в интеграции  1.5.4. Теорема Фубини  1.6. Функциональный анализ  1.6.1. Понимание пространства Банака  1.6.2. Пространства Гильберта  1.6.3. Операторы на пространствах  1.6.4. Спектральная теория
  2. Абстрактная алгебра  2.1. Понимание групп в абстрактной алгебре  2.1.1. Определения и примеры групп в абстрактной алгебре  2.1.2. Гомоморфизмы групп  2.1.3. Введение в нормальные подгруппы  2.1.4. Теорема Силова  2.2. Кольца и поля  2.2.1. Идеалы и фактор-кольца  2.2.2. Расширения полей  2.2.3. Теория Галуа  2.2.4. Полиномиальные кольца  2.3. Введение в модули в абстрактной алгебре  2.3.1. Гомоморфизм модуля  2.3.2. Свободные модули  2.3.3. Введение в тензорные произведения  2.3.4. Точная последовательность в модулях  2.4. Линейная алгебра  2.4.1. Векторное пространство  2.4.2. Собственные значения и собственные векторы  2.4.3. Векторное пространство с внутренним произведением  2.4.4. Диагонализация
  3. Топология  3.1. Общая топология  3.1.1. Открытые и закрытые множества  3.1.2. Компактность и связность  3.1.3. Непрерывные отображения  3.1.4. Аксиома отделимости  3.2. Алгебраическая топология  3.2.1. Понимание фундаментальных групп в алгебраической топологии  3.2.2. Гомотопия и гомология  3.2.3. Симплициальный комплекс  3.2.4. Точные последовательности в гомологии  3.3. Дифференциальная топология  3.3.1. Понимание многообразий в дифференциальной топологии  3.3.2. Гладкие функции  3.3.3. Тангенциальное и котангенциальное пространство  3.3.4. Векторные расслоения
  4. Дифференциальные уравнения  4.1. Обыкновенные дифференциальные уравнения  4.1.1. Дифференциальные уравнения первого порядка  4.1.2. Линейные уравнения второго порядка  4.1.3. Системы дифференциальных уравнений  4.1.4. Анализ устойчивости в обыкновенных дифференциальных уравнениях  4.2. Частные дифференциальные уравнения  4.2.1. Классификация уравнений с частными производными  4.2.2. Понимание рядов Фурье в уравнениях с частными производными  4.2.3. Введение в функции Грина  4.2.4. Метод характеристик  4.3. Динамические системы в дифференциальных уравнениях  4.3.1. Теория устойчивости  4.3.2. Предельные циклы в динамических системах  4.3.3. Теория хаоса  4.3.4. Теория бифуркаций
  5. Теория вероятностей и статистика  5.1. Теория вероятностей  5.1.1. Случайные переменные  5.1.2. Распределения вероятностей  5.1.3. Закон больших чисел  5.1.4. Центральная предельная теорема  5.2. Статистическое вывод  5.2.1. Проверка гипотез  5.2.2. Доверительный интервал  5.2.3. Байесовские методы  5.2.4. Метод максимального правдоподобия  5.3. Стохастические процессы  5.3.1. Цепи Маркова  5.3.2. Броуновское движение  5.3.3. Понимание процессов Пуассона  5.3.4. Мартингейлы: всестороннее исследование в вероятности и статистике
  6. Численный анализ  6.1. Численное решение уравнений  6.1.1. Оригинальное открытие  6.1.2. Итерационные методы  6.1.3. Анализ сходимости  6.1.4. Границы ошибок в численных решениях уравнений  6.2. Численная линейная алгебра  6.2.1. Факторизация матриц  6.2.2. Вычисление собственных значений  6.2.3. Разреженные матрицы  6.2.4. Методы предобработки  6.3. Численное интегрирование и дифференцирование  6.3.1. Методы квадратур  6.3.2. Введение в конечные разности  6.3.3. Анализ ошибок в численном интегрировании и дифференцировании  6.3.4. Адаптивные методы в численном интегрировании и дифференцировании
  7. Комплексный анализ  7.1. Комплексные числа  7.1.1. Полярная форма  7.1.2. Комплексные сопряженные  7.1.3. Экспоненциальная форма комплексных чисел  7.1.4. Корни из единицы  7.2. Аналитические функции  7.2.1. Уравнения Коши — Римана  7.2.2. Степенные ряды  7.2.3. Конформное отображение  7.2.4. Гармонические функции  7.3. Интегрирование на комплексной плоскости  7.3.1. Теорема Коши  7.3.2. Теорема о вычетах  7.3.3. Контурное интегрирование  7.3.4. Интегральные преобразования
  8. Математическая логика и основания  8.1. Пропозициональная логика  8.1.1. Таблицы истинности  8.1.2. Логическая эквивалентность в пропозициональной логике  8.1.3. Техники доказательства в пропозициональной логике  8.1.4. Решение в пропозициональной логике  8.2. Логика предикатов  8.2.1. Кванторы в предикатной логике  8.2.2. Формальные системы в предикатной логике  8.2.3. Полнота и правильность  8.2.4. Модельная теория  8.3. Теория множеств  8.3.1. Кардинальность и ординальность  8.3.2. Аксиоматические системы  8.3.3. Понимание теории множеств Цермело-Френкеля  8.3.4. Силы в теории множества
  9. Настройка  9.1. Линейное программирование  9.1.1. Метод симплекс  9.1.2. Двойственность в линейном программировании  9.1.3. Анализ чувствительности в линейном программировании  9.1.4. Методы внутренних точек  9.2. Нелинейное программирование  9.2.1. Градиентный спуск  9.2.2. Множители Лагранжа  9.2.3. Выпуклая оптимизация  9.2.4. Квадратичное программирование  9.3. Комбинаторная оптимизация  9.3.1. Алгоритмы графов  9.3.2. Целочисленное программирование  9.3.3. Сетевой поток  9.3.4. Алгоритмы аппроксимации
  10. Дискретная математика  10.1. Теория графов  10.1.1. Представление графов  10.1.2. Плоскость и цвет  10.1.3. Алгоритм поиска кратчайшего пути  10.1.4. Сетевой поток  10.2. Компаньонство  10.2.1. Перестановка и сочетание  10.2.2. Порождающая функция  10.2.3. Рекуррентные соотношения  10.2.4. Понимание принципа включения-исключения  10.3. Криптография  10.3.1. Применение теории чисел в криптографии  10.3.2. Симметричное и асимметричное шифрование  10.3.3. RSA и криптография на эллиптических кривых  10.3.4. Постквантовая криптография

Магистратура → Численный анализ → Численная линейная алгебра ↓


Методы предобработки


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

Что такое предобработка?

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

Ax = b

Идея заключается в том, чтобы найти матрицу M, называемую предобработчиком, такую, что модифицированная система может быть решена:

M -1 Ax = M -1 b

Это ускоряет сходимость. Выбор M важен; он должен быть близок к A и легко обращаемым.

Зачем нужна предобработка?

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

Типы предобработки

Левая предобработка

При левой предобработке мы умножаем систему Ax = b слева на M -1, в результате чего получаем:

M -1 Ax = M -1 b

Цель этого подхода состоит в том, чтобы непосредственно решить матрицу коэффициентов A и попытаться эффективно решить преобразованную систему.

Правая предобработка

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

A(M -1 y) = b

Затем решаем для y = Mx. Этот метод сосредоточен на непосредственном преобразовании вектора решений.

Разделенная предобработка

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

M 1 -1 AM 2 -1 z = M 1 -1 b

Здесь мы решаем для z = M 2 x, применяя более сложные преобразования для повышения эффективности.

Общие предобработчики

1. Предобработка Якоби

Предобработка Якоби использует диагональные элементы A для создания матрицы предобработчика M:

M = diag(A)

Здесь diag(A) обозначает диагональную матрицу, сформированную из диагональных элементов A. Этот подход прост и легок в реализации.

2. Предобработка Гаусса-Зейделя

Предобработка Гаусса-Зейделя похожа, но также учитывает нижнюю треугольную часть A:

M = (D + L)

Где D - диагональная часть, а L - нижняя треугольная часть A.

3. Предобработка неполным LU-разложением (ILU)

Предобработка ILU использует приближенное LU-разложение матрицы A. Вместо вычисления полного LU-разложения, ILU вычисляет приближение:

A ≈ LU

где L и U являются нижними и верхними треугольными матрицами соответственно. ILU особенно подходит для разреженных матриц, потому что сохраняет их разреженность.

4. Предобработка неполным разложением Холецкого

Подобно ILU, неполное разложение Холецкого используется для симметричных положительно определенных матриц:

A ≈ LL T

Где L - нижняя треугольная матрица.

5. Предобработка аддитивным методом Шварца

Этот метод делит исходную область на перекрывающиеся подобласти, применяет предобработчик к каждой подобласти и комбинирует их эффекты аддитивным образом. Он популярен в средах параллельного программирования.

Визуальные изображения

A M M - 1A

На иллюстрации синяя коробка представляет матрицу A, зеленая коробка представляет предобработчик M, а красная коробка представляет предобработанную матрицу M -1 A, которая легче и быстрее для решения.

Выбор предобработчика

Выбор эффективного предобработчика требует балансировки между преимуществами лучшей сходимости и вычислительным усилием, необходимым для применения предобработчика на каждой итерации. Идеальный предобработчик должен обладать следующими свойствами:

  • Легко вычисляется и применяется (не требует значительных дополнительных вычислительных ресурсов).
  • Эффективен в снижении числа обусловленности системы.
  • Применим к определенным свойствам матрицы (например, разреженность, однородность).

Практические соображения

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

Кейсы и примеры применения

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

Заключение

Предобработка является ключевым шагом в том, чтобы сделать итерационные решатели практически применимыми для больших и сложных систем линейных уравнений. Это превращает иначе сложную задачу в вычислительно разрешимую. Используя подходящий предобработчик, такой как Якоби, Гаусса-Зейделя, ILU или Неполный разложение Холецкого, эффективность вычислений может быть значительно улучшена. По мере развития исследований методы предобработки продолжают развиваться, предоставляя более эффективные решения реальных численных задач.


Магистратура → 6.2.4


U
username
0%
завершено в Магистратура

← предыдущая (6.2.3)
Разреженные матрицы
следующая (6.3) →
Численное интегрирование и дифференцирование

комментарии 



Методы предобработки

https://www.buddymath.com/g/6.2.4?bmal=ru