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

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

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

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

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

История

Численная линейная алгебра была разработана пионерами компьютерной науки, такими как Джон фон Нейман , Алан Тьюринг , Джеймс Х. Уилкинсон , Олстон Скотт Хаусхолдер , Джордж Форсайт и Хайнц Рутисхаузер , с целью применения самых первых компьютеров к задачам непрерывной математики, таким как задачи баллистики и решения систем уравнений в частных производных . ^[2] Первой серьезной попыткой минимизировать компьютерную ошибку при применении алгоритмов к реальным данным была работа Джона фон Неймана и Германа Голдстайна в 1947 году. ^[3] Область развивалась по мере того, как технологии все больше позволяли исследователям решать сложные задачи на чрезвычайно больших высокоточных матрицах, а некоторые числовые алгоритмы приобрели известность, поскольку такие технологии, как параллельные вычисления, сделали их практическими подходами к научным проблемам. ^[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 имеют такие пакеты, как Basic Linear Algebra Subprograms и LAPACK , python имеет библиотеку NumPy , а Perl имеет Perl Data Language . Многие команды числовой линейной алгебры в R полагаются на эти более фундаментальные библиотеки, такие как LAPACK . ^[5] Больше библиотек можно найти в Списке числовых библиотек .

Ссылки

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

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

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

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

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