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

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

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

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

История [ править ]

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

Матричные разложения [ править ]

Разделенные матрицы [ править ]

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

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

Разложение по сингулярным числам [ править ]

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

QR-факторизация [ править ]

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

Факторизация LU [ править ]

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

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

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

Алгоритмы [ править ]

Исключение Гаусса [ править ]

С точки зрения численной линейной алгебры, гауссовское исключение - это процедура факторизации матрицы A в ее LU- факторизацию, которую выполняет гауссовское исключение путем умножения A слева на последовательность матриц до тех пор, пока U не станет верхнетреугольным, а L - нижним треугольным, где . ^{[1] : 148} Наивные программы исключения Гаусса, как известно, крайне нестабильны и дают огромные ошибки при применении к матрицам со многими значащими цифрами. ^[2] Простейшим решением является введение поворота , которое дает модифицированный алгоритм исключения Гаусса, который является стабильным. ^[1]${\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}}$^{: 151}

Решения линейных систем [ править ]

Числовая линейная алгебра обычно рассматривает матрицы как конкатенацию векторов-столбцов. Для решения линейной системы , традиционный алгебраический подход заключается в понимании х как произведение с б . Численная линейная алгебра вместо интерпретирует й как вектор коэффициентов линейного расширения Ь в базисе , образованных колоннами 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}${\displaystyle Rx=Q^{\ast }b}$${\displaystyle A=X\Lambda X^{-1}}$${\displaystyle b^{\prime }=X^{-1}b}$${\displaystyle x^{\prime }=X^{-1}x}$${\displaystyle b^{\prime }=\Lambda x^{\prime }}$Это тесно связано с решением линейной системы с использованием разложения по сингулярным числам, поскольку сингулярные значения матрицы являются квадратными корнями из ее собственных значений. И если A = LU является LU- факторизацией A , то Ax = b может быть решено с использованием треугольных матриц Ly = b и Ux = y . ^{[1] : 147 [4] : 99}

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

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

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

Допустим, что проблема - это функция , где 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] Больше библиотек можно найти в Списке числовых библиотек .

Ссылки [ править ]

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

Викискладе есть медиафайлы, связанные с числовой линейной алгеброй .

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