Численная линейная алгебра

Область математики

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

Численная линейная алгебра направлена ​​на решение задач непрерывной математики с использованием компьютеров конечной точности, поэтому ее приложения в естественных и социальных науках столь же обширны, как и приложения непрерывной математики. Часто это фундаментальная часть инженерных и вычислительных задач, таких как обработка изображений и сигналов , телекоммуникации , вычислительные финансы , моделирование материалов , структурная биология , интеллектуальный анализ данных , биоинформатика и гидродинамика . Матричные методы особенно используются в методах конечных разностей , методах конечных элементов и моделировании дифференциальных уравнений . Отмечая широкое применение числовой линейной алгебры, Ллойд Н. Трефетен и Дэвид Бау III утверждают, что она «столь же фундаментальна для математических наук, как исчисление и дифференциальные уравнения», ^{[1] : x} , хотя это сравнительно небольшая область. ^[2] Поскольку многие свойства матриц и векторов также применимы к функциям и операторам, численную линейную алгебру также можно рассматривать как тип функционального анализа , в котором особое внимание уделяется практическим алгоритмам. ^{[1] : ix}

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

История

Численная линейная алгебра была разработана пионерами компьютеров, такими как Джон фон Нейман , Алан Тьюринг , Джеймс Х. Уилкинсон , Олстон Скотт Хаусхолдер , Джордж Форсайт и Хайнц Рутисхаузер , чтобы применить самые ранние компьютеры к проблемам непрерывной математики, таким как задачи баллистики и решения систем уравнений в частных производных . ^{[ 2]} Первой серьезной попыткой минимизировать компьютерные ошибки при применении алгоритмов к реальным данным стала работа Джона фон Неймана и Германа Голдстайна в 1947 году . чрезвычайно большие матрицы высокой точности, а некоторые численные алгоритмы приобрели известность, поскольку такие технологии, как параллельные вычисления , сделали их практическими подходами к научным проблемам. ^[2]

Матричное разложение

Разделенные матрицы

Для многих задач прикладной линейной алгебры полезно принять представление о матрице как о конкатенации вектор-столбцов. Например, при решении линейной системы вместо того, чтобы понимать x как произведение на b , полезно думать о x как о векторе коэффициентов линейного разложения b в базисе , образованном столбцами A. ^{[1] : 8} Представление о матрицах как о конкатенации столбцов также является практическим подходом для целей матричных алгоритмов. Это связано с тем, что матричные алгоритмы часто содержат два вложенных цикла: один над столбцами матрицы A , а другой над строками A. Например, для матриц и векторов и мы могли бы использовать перспективу разделения столбцов для вычисления y  := Ax + y как ${\displaystyle x=A^{-1}b}$ ${\displaystyle A^{-1}}$ ${\displaystyle A^{m\times n}}$ ${\displaystyle x^{n\times 1}}$ ${\displaystyle y^{m\times 1}}$

для q = 1 : n для p = 1 : m y ( p ) = A ( p , q ) * x ( q ) + y ( p ) конец конец             

Разложение по сингулярным значениям

Разложение по сингулярным значениям матрицы - это то , где U и V унитарны и диагональны . Диагональные элементы называются сингулярными значениями A . Поскольку сингулярные значения являются квадратными корнями собственных значений , существует тесная связь между разложением сингулярных значений и разложением собственных значений. Это означает, что большинство методов вычисления разложения по сингулярным значениям аналогичны методам собственных значений; ^{[1] : 36,} возможно, наиболее распространенный метод включает в себя процедуры домохозяина . ^{[1] : 253} ${\displaystyle A^{m\times n}}$ ${\displaystyle A=U\Sigma V^{\ast }}$ ${\displaystyle \Sigma }$ ${\displaystyle \Sigma }$ ${\displaystyle AA^{\ast }}$

QR-факторизация

QR-факторизация матрицы — это матрица и матрица , так что A = QR , где Q ортогональна , а R — верхнетреугольная . ^{[1] : 50  [4] : 223} Двумя основными алгоритмами вычисления QR-факторизации являются процесс Грама-Шмидта и преобразование Хаусхолдера . QR-факторизация часто используется для решения линейных задач наименьших квадратов и задач на собственные значения (с помощью итерационного алгоритма QR ). ${\displaystyle A^{m\times n}}$ ${\displaystyle Q^{m\times m}}$ ${\displaystyle R^{m\times n}}$

LU-факторизация

LU-факторизация матрицы A состоит из нижней треугольной матрицы L и верхней треугольной матрицы U, так что A = LU . Матрица U находится с помощью процедуры верхней триангуляризации, которая включает умножение A слева на ряд матриц для формирования произведения , так что эквивалентно . ^{[1] : 147  [4] : 96} ${\displaystyle M_{1},\ldots ,M_{n-1}}$ ${\displaystyle M_{n-1}\cdots M_{1}A=U}$ ${\displaystyle L=M_{1}^{-1}\cdots M_{n-1}^{-1}}$

Разложение по собственным значениям

Разложение матрицы по собственным значениям — это , где столбцы X являются собственными векторами матрицы A , и является диагональной матрицей , диагональные элементы которой являются соответствующими собственными значениями матрицы A. ^{[1] : 33} Не существует прямого метода нахождения разложения по собственным значениям произвольной матрицы. Поскольку невозможно написать программу, которая находит точные корни произвольного многочлена за конечное время, любой общий решатель собственных значений обязательно должен быть итеративным. ^{[1] : 192} ${\displaystyle A^{m\times m}}$ ${\displaystyle A=X\Lambda X^{-1}}$ ${\displaystyle \Lambda }$

Алгоритмы

Исключение по Гауссу

С точки зрения числовой линейной алгебры, исключение Гаусса - это процедура факторизации матрицы A в ее LU- факторизацию, которую исключение Гаусса выполняет путем умножения слева A на последовательность матриц до тех пор, пока U не станет верхнетреугольным, а L не станет нижним треугольным, где . ^{[1] : 148} Наивные программы исключения Гаусса, как известно, очень нестабильны и производят огромные ошибки при применении к матрицам со многими значащими цифрами. ^[2] Самое простое решение — ввести поворот , который создает модифицированный стабильный алгоритм исключения Гаусса. ^{[1] : 151} ${\displaystyle L_{m-1}\cdots L_{2}L_{1}A=U}$ ${\displaystyle L\equiv L_{1}^{-1}L_{2}^{-1}\cdots L_{m-1}^{-1}}$

Решения линейных систем

Численная линейная алгебра обычно приближается к матрицам как к объединению векторов-столбцов. Чтобы решить линейную систему , традиционный алгебраический подход состоит в том, чтобы понимать x как произведение на b . Вместо этого численная линейная алгебра интерпретирует x как вектор коэффициентов линейного разложения b в базисе, образованном столбцами A . ^{[1] : 8} ${\displaystyle x=A^{-1}b}$ ${\displaystyle A^{-1}}$

Для решения линейной задачи можно использовать множество различных разложений, в зависимости от характеристик матрицы A и векторов x и b , что может значительно упростить получение одной факторизации, чем других. Если A = QR является QR-факторизацией A , то эквивалентно . Это так же легко вычислить, как и матричную факторизацию. ^{[1] : 54} Если является собственным разложением A , и мы стремимся найти b так, чтобы b = Ax , с и , то мы имеем . ^{[1] : 33} Это тесно связано с решением линейной системы с использованием разложения по сингулярным значениям, поскольку сингулярные значения матрицы — это абсолютные значения ее собственных значений, которые также эквивалентны квадратным корням из абсолютных значений матрицы. собственные значения матрицы Грама . И если A = LU является LU- факторизацией A , то Ax = b можно решить, используя треугольные матрицы Ly = b и Ux = y . ^{[1] : 147  [4] : 99} ${\displaystyle Rx=Q^{\ast }b}$ ${\displaystyle A=X\Lambda X^{-1}}$ ${\displaystyle b'=X^{-1}b}$ ${\displaystyle x'=X^{-1}x}$ ${\displaystyle b'=\Lambda x'}$ ${\displaystyle X^{*}X}$

Оптимизация методом наименьших квадратов

Матричное разложение предлагает несколько способов решения линейной системы r = b − Ax , где мы стремимся минимизировать r , как в задаче регрессии . Алгоритм QR решает эту проблему, вычисляя уменьшенную QR-факторизацию A и переставляя ее для получения . Затем эту верхнюю треугольную систему можно решить относительно x . SVD также предлагает алгоритм получения линейных наименьших квадратов. Вычисляя приведенное SVD-разложение, а затем вычисляя вектор , мы сводим задачу наименьших квадратов к простой диагональной системе. ^{[1] : 84} Тот факт, что решения методом наименьших квадратов могут быть получены с помощью факторизаций QR и SVD, означает, что, в дополнение к классическому методу нормальных уравнений для решения задач наименьших квадратов, эти проблемы также могут быть решены методами, включающими грамматический метод. Алгоритм Шмидта и методы Хаусхолдера. ${\displaystyle {\widehat {R}}x={\widehat {Q}}^{\ast }b}$ ${\displaystyle A={\widehat {U}}{\widehat {\Sigma }}V^{\ast }}$ ${\displaystyle {\widehat {U}}^{\ast }b}$

Кондиционирование и стабильность

Допустим, что проблема — это функция , где X — нормированное векторное пространство данных, а Y — нормированное векторное пространство решений. Для некоторой точки данных проблема считается плохо обусловленной, если небольшое возмущение x приводит к большому изменению значения f ( x ). Мы можем количественно оценить это, определив число обусловленности , которое показывает, насколько хорошо обусловлена ​​проблема, определяемое как ${\displaystyle f:X\to Y}$ ${\displaystyle x\in X}$

$${\displaystyle {\widehat {\kappa }}=\lim _{\delta \to 0}\sup _{\|\delta x\|\leq \delta }{\frac {\|\delta f\|}{\|\delta x\|}}.}$$

Нестабильность — это тенденция компьютерных алгоритмов, основанных на арифметике с плавающей запятой , выдавать результаты, резко отличающиеся от точного математического решения проблемы. Когда матрица содержит реальные данные со многими значащими цифрами , многие алгоритмы решения таких задач, как линейные системы уравнений или оптимизация методом наименьших квадратов, могут давать весьма неточные результаты. Создание стабильных алгоритмов для плохо обусловленных задач является центральной задачей числовой линейной алгебры. Одним из примеров является то, что стабильность триангуляризации домохозяина делает его особенно надежным методом решения для линейных систем, тогда как нестабильность метода нормальных уравнений для решения задач наименьших квадратов является причиной отдавать предпочтение методам матричного разложения, таким как использование разложения по сингулярным значениям. Некоторые методы матричной декомпозиции могут быть нестабильными, но имеют простые модификации, которые делают их стабильными; Одним из примеров является нестабильный вариант Грама-Шмидта, который можно легко изменить, чтобы получить стабильный модифицированный вариант Грама-Шмидта . ^{[1] : 140} Другая классическая проблема числовой линейной алгебры — обнаружение того, что метод исключения Гаусса неустойчив, но становится устойчивым с введением поворота.

Итерационные методы

Есть две причины, по которым итеративные алгоритмы являются важной частью числовой линейной алгебры. Во-первых, многие важные численные задачи не имеют прямого решения; чтобы найти собственные значения и собственные векторы произвольной матрицы, мы можем использовать только итерационный подход. Во-вторых, неитеративные алгоритмы для произвольной матрицы требуют времени, которое является удивительно большим, учитывая, что матрицы содержат только числа. Итеративные подходы могут использовать некоторые особенности некоторых матриц, чтобы сократить это время. Например, когда матрица разрежена , итерационный алгоритм может пропустить многие шаги, которые обязательно выполняются при прямом подходе, даже если они являются избыточными шагами для высокоструктурированной матрицы. ${\displaystyle m\times m}$ ${\displaystyle O(m^{3})}$ ${\displaystyle m^{2}}$

Ядром многих итерационных методов в числовой линейной алгебре является проекция матрицы на подпространство Крылова меньшей размерности , что позволяет аппроксимировать характеристики многомерной матрицы путем итеративного вычисления эквивалентных характеристик аналогичных матриц, начиная с пространства малой размерности. и переход к последовательно более высоким измерениям. Когда A симметричен и мы хотим решить линейную задачу Ax = b , классическим итеративным подходом является метод сопряженных градиентов . Если A не симметричен, то примерами итерационных решений линейной задачи являются обобщенный метод минимальной невязки и CGN . Если A симметричен, то для решения проблемы собственных значений и собственных векторов мы можем использовать алгоритм Ланцоша , а если A несимметричен, то мы можем использовать итерацию Арнольди .

Программное обеспечение

Некоторые языки программирования используют методы оптимизации числовой линейной алгебры и предназначены для реализации алгоритмов числовой линейной алгебры. К этим языкам относятся MATLAB , Analytica , Maple и Mathematica . Другие языки программирования, которые явно не предназначены для числовой линейной алгебры, имеют библиотеки, которые предоставляют процедуры числовой линейной алгебры и оптимизацию; C и Fortran имеют такие пакеты, как базовые подпрограммы линейной алгебры и LAPACK , у python есть библиотека NumPy , а у Perl есть язык данных Perl . Многие команды числовой линейной алгебры в R полагаются на такие более фундаментальные библиотеки, как LAPACK . ^[5] Дополнительные библиотеки можно найти в Списке числовых библиотек .

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

1. Трефетен, Ллойд; Бау III, Дэвид (1997). Численная линейная алгебра (1-е изд.). Филадельфия: СИАМ. ISBN 978-0-89871-361-9.
2. Голуб, Джин Х. «История современной числовой линейной алгебры» (PDF) . Статистический факультет Чикагского университета . Проверено 17 февраля 2019 г.
3. фон Нейман, Джон; Голдстайн, Герман Х. (1947). «Численное обращение матриц высокого порядка». Бюллетень Американского математического общества . 53 (11): 1021–1099. дои : 10.1090/s0002-9904-1947-08909-6 . S2CID  16174165.
4. Голуб, Джин Х.; Ван Лоан, Чарльз Ф. (1996). Матричные вычисления (3-е изд.). Балтимор: Издательство Университета Джона Хопкинса. ISBN 0-8018-5413-Х.
5. Рикерт, Джозеф (29 августа 2013 г.). «R и линейная алгебра». R-блогеры . Проверено 17 февраля 2019 г.

дальнейшее чтение

• Донгарра, Джек ; Хаммарлинг, Свен (1990). «Эволюция численного программного обеспечения для плотной линейной алгебры». В Коксе, Миннесота; Хаммарлинг, С. (ред.). Надежные численные вычисления . Оксфорд: Кларендон Пресс. стр. 297–327. ISBN 0-19-853564-3.

Внешние ссылки

• Свободно доступное в Интернете программное обеспечение для числовой алгебры, созданное Джеком Донгаррой и Хатемом Лтаифом, Университет Теннесси.
• NAG Библиотека числовых процедур линейной алгебры
• Группа числовой линейной алгебры в Твиттере (исследовательская группа в Великобритании)
• siagla в Твиттере (Группа активности по числовой линейной алгебре в Обществе промышленной и прикладной математики )
• Группа деятельности GAMM по прикладной и числовой линейной алгебре