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

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

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

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

История

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

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

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

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

for q = 1:n
  for p = 1:m
    y(p) = A(p,q)*x(q) + y(p)
  end
end

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

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

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

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

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

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

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

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

Алгоритмы

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

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

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

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

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

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

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

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

Допустить, что проблема — это функция $f:X\to Y$ , где X — нормированное векторное пространство данных, а Y — нормированное векторное пространство решений. Для некоторой точки данных $x\in X$ , проблема называется плохо обусловленной, если небольшое возмущение x приводит к большому изменению значения f ( x ). Мы можем количественно оценить это, определив число обусловленности , которое показывает, насколько хорошо обусловлена проблема, определяемое как ${\widehat {\kappa }}=\lim _{\delta \to 0}\sup _{\|\delta x\|\leq \delta }{\frac {\|\delta f\|}{\|\delta x\|}}.$

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

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

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

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

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

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

Ссылки

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

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

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

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

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

[tb397-1] Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п ^д Трефетен, Ллойд; Бау III, Дэвид (1997). Численная линейная алгебра (1-е изд.). Филадельфия: СИАМ. ISBN 978-0-89871-361-9 .

[golubhist-2] Перейти обратно: Перейти обратно: ^а ^б ^с ^д Голуб, Джин Х. «История современной числовой линейной алгебры» (PDF) . Статистический факультет Чикагского университета . Проверено 17 февраля 2019 г.

[3] фон Нейман, Джон; Голдстайн, Герман Х. (1947). «Численное обращение матриц высокого порядка» . Бюллетень Американского математического общества . 53 (11): 1021–1099. дои : 10.1090/s0002-9904-1947-08909-6 . S2CID 16174165 .

[gvl96-4] Перейти обратно: Перейти обратно: ^а ^б ^с Голуб, Джин Х.; Ван Лоан, Чарльз Ф. (1996). Матричные вычисления (3-е изд.). Балтимор: Издательство Университета Джона Хопкинса. ISBN 0-8018-5413-Х .

[5] Рикерт, Джозеф (29 августа 2013 г.). «R и линейная алгебра» . R-блогеры . Проверено 17 февраля 2019 г.

[1]

[2]

[3]

[4]

[5]

v т и Численная линейная алгебра
Key concepts	Floating point Numerical stability
Problems	System of linear equations Matrix decompositions Matrix multiplication (algorithms) Matrix splitting Sparse problems
Hardware	CPU cache TLB Cache-oblivious algorithm SIMD Multiprocessing
Software	ATLAS MATLAB Basic Linear Algebra Subprograms (BLAS) LAPACK Specialized libraries General purpose software