Войти
Числовая линейная алгебра, иногда называемая прикладной линейной алгеброй, - это исследование того, как матричные операции могут использоваться для создания компьютерных алгоритмов, которые эффективно и точно дают приблизительные ответы на вопросы непрерывной математики. Это подполе численного анализа и разновидность линейной алгебры. Компьютеры используют арифметику с плавающей запятой и не могут точно представить иррациональные данные, поэтому, когда компьютерный алгоритм применяется к матрице данных, он иногда может увеличить разницу между числом, хранящимся в компьютере, и истинным числом, которое оно является приближением. Численная линейная алгебра использует свойства векторов и матриц для разработки компьютерных алгоритмов, которые минимизируют ошибку, вносимую компьютером, а также заботятся о том, чтобы алгоритм был как можно более эффективным.
Численная линейная алгебра направлена на решение задач непрерывной математики с использованием компьютеров конечной точности, поэтому ее приложения в естественных и социальных науках столь же обширны, как и приложения непрерывной математики. Часто это фундаментальная часть инженерных и вычислительных задач, таких как обработка изображений и сигналов, телекоммуникации, вычислительные финансы, моделирование материаловедения, структурная биология, интеллектуальный анализ данных, биоинформатика и гидродинамика. Матричные методы особенно используется в конечных разностных методах, методах конечных элементов, и при моделировании дифференциальных уравнений. Отмечая широкое применение числовой линейной алгебры, Ллойд Н. Трефетен и Дэвид Бау, III утверждают, что она « столь же фундаментальна для математических наук, как исчисление и дифференциальные уравнения», хотя это сравнительно небольшая область. Поскольку многие свойства матриц и векторов также применимы к функциям и операторам, численную линейную алгебру также можно рассматривать как тип функционального анализа, в котором особое внимание уделяется практическим алгоритмам.
Общие проблемы в числовой линейной алгебре включают получение разложений матриц, таких как разложение по сингулярным числам, QR-факторизация, LU-факторизация или собственное разложение, которые затем могут использоваться для решения распространенных линейных алгебраических задач, таких как решение линейных систем уравнений, поиск собственных значений или оптимизация методом наименьших квадратов. Основная задача численной линейной алгебры при разработке алгоритмов, которые не вносят ошибок при применении к реальным данным на компьютере конечной точности, часто достигается итерационными методами, а не прямыми.
Числовая линейная алгебра была разработана пионерами компьютеров, такими как Джон фон Нейман, Алан Тьюринг, Джеймс Х. Уилкинсон, Алстон Скотт Хаусхолдер, Джордж Форсайт и Хайнц Рутисхаузер, чтобы применить самые первые компьютеры к задачам непрерывной математики, таким как задачи баллистики и т. Д. решения систем дифференциальных уравнений в частных производных. Первой серьезной попыткой свести к минимуму компьютерные ошибки при применении алгоритмов к реальным данным стала работа Джона фон Неймана и Германа Голдстайна в 1947 году. Эта область расширилась, поскольку технологии все больше позволяли исследователям решать сложные задачи на чрезвычайно больших высокоточных матрицах. и некоторые численные алгоритмы приобрели известность, поскольку такие технологии, как параллельные вычисления, сделали их практическими подходами к научным проблемам.
Для решения многих задач прикладной линейной алгебры полезно принять точку зрения на матрицу как на конкатенацию векторов-столбцов. Например, при решении линейной системы, а не понимание х как произведение с Ь, то полезно думать о х как вектор коэффициентов в линейном разложении Ь в основе, образованной столбцами A. Рассмотрение матриц как конкатенации столбцов также является практическим подходом для целей матричных алгоритмов. Это потому, что матричные алгоритмы часто содержат два вложенных цикла: один над столбцами матрицы А, а другой над рядами А. Например, для матриц и векторов и мы могли бы использовать перспективу разделения столбцов для вычисления Ax + y как
for j = 1:n for i = 1:m y(i) = A(i,j)x(j) + y(i) end end
Значение разложение по сингулярному матрице является, где U и V являются унитарными и является диагональным. Диагональные элементы матрицы называются сингулярные значения из A. Поскольку особые значения являются квадратными корнями из собственных значений из, существует тесная связь между сингулярным разложением на собственном значения и разложением. Это означает, что большинство методов вычисления разложения по сингулярным значениям аналогичны методам собственных значений; возможно, наиболее распространенный метод включает процедуры Хаусхолдера.
QR - разложение матрицы представляет собой матрицу и матрицу так, что А = QR -, где Q является ортогональной, и R является верхней треугольной. Двумя основными алгоритмами вычисления QR-факторизации являются процесс Грама – Шмидта и преобразование Хаусхолдера. QR-факторизация часто используется для решения линейных задач наименьших квадратов и задач на собственные значения (посредством итеративного QR-алгоритма ).
Факторизация LU матрицы A состоит из нижней треугольной матрицы L и верхней треугольной матрицы M, так что A = LU. Матрица U находится с помощью процедуры верхней треугольной формы, которая включает в себя умножение A слева на серию матриц для формирования продукта, что эквивалентно.
Собственное разложение матрицы является, где столбцы матрицы X являются собственными векторами А, и представляет собой диагональную матрицу, диагональные элементы которой являются соответствующие собственные значения А. Не существует прямого метода нахождения разложения произвольной матрицы по собственным значениям. Поскольку невозможно написать программу, которая находит точные корни произвольного многочлена за конечное время, любой общий решатель собственных значений обязательно должен быть итерационным.
С точки зрения численной линейной алгебры, гауссовское исключение - это процедура факторизации матрицы A в ее LU- факторизацию, которую выполняет гауссовское исключение путем умножения A слева на последовательность матриц до тех пор, пока U не станет верхнетреугольным, а L - нижнетреугольным, где. Наивные программы исключения Гаусса, как известно, крайне нестабильны и приводят к огромным ошибкам при применении к матрицам со многими значащими цифрами. Самое простое решение - ввести поворот, который дает модифицированный алгоритм исключения Гаусса, который является стабильным.
Числовая линейная алгебра обычно рассматривает матрицы как конкатенацию векторов-столбцов. Для решения линейной системы, традиционный алгебраический подход заключается в понимании х как произведение с б. Численная линейная алгебра вместо интерпретирует й как вектор коэффициентов линейного расширения Ь в базисе, образованных колоннами A.
Для решения линейной задачи можно использовать множество различных декомпозиций, в зависимости от характеристик матрицы A и векторов x и b, что может значительно облегчить получение одной факторизации по сравнению с другими. Если A = QR является QR-факторизацией A, то эквивалентно. Это легко вычислить как матричную факторизацию. Если - собственное разложение A, и мы стремимся найти b так, чтобы b = Ax, с и, то мы имеем. Это тесно связано с решением линейной системы с использованием разложения по сингулярным значениям, поскольку сингулярные значения матрицы являются квадратными корнями из ее собственных значений. И если A = LU является LU- факторизацией A, то Ax = b может быть решено с использованием треугольных матриц Ly = b и Ux = y.
Матричные разложения предлагают несколько способов решения линейной системы r = b - Ax, где мы стремимся минимизировать r, как в задаче регрессии. Алгоритм QR решает эту проблему, сначала определяя y = Ax, а затем вычисляя сокращенную QR-факторизацию A и перестраивая для получения. Затем эта верхнетреугольная система может быть решена относительно b. SVD также предлагает алгоритм для получения линейных наименьших квадратов. Вычисляя сокращенное разложение SVD, а затем вычисляя вектор, мы сводим задачу наименьших квадратов к простой диагональной системе. Тот факт, что решения наименьших квадратов могут быть получены с помощью факторизации QR и SVD, означает, что, помимо классического метода нормальных уравнений для решения задач наименьших квадратов, эти проблемы также могут быть решены методами, которые включают алгоритм Грама-Шмидта и методы Хаусхолдера..
Допустим, что проблема - это функция, где X - нормированное векторное пространство данных, а Y - нормированное векторное пространство решений. Для некоторой точки данных проблема считается плохо обусловленной, если небольшое возмущение x вызывает большое изменение значения f (x). Мы можем количественно оценить это, определив число условия, которое представляет, насколько хорошо обусловлена проблема, определяемое как
Нестабильность - это тенденция компьютерных алгоритмов, которые зависят от арифметики с плавающей запятой, давать результаты, резко отличающиеся от точного математического решения проблемы. Когда матрица содержит реальные данные с большим количеством значащих цифр, многие алгоритмы решения проблем, такие как линейные системы уравнений или оптимизация методом наименьших квадратов, могут давать очень неточные результаты. Создание стабильных алгоритмов для плохо обусловленных задач - центральная задача численной линейной алгебры. Одним из примеров является то, что стабильность триангуляризации домовладельцев делает ее особенно надежным методом решения для линейных систем, тогда как нестабильность метода нормальных уравнений для решения задач наименьших квадратов является причиной предпочтения методов разложения матриц, таких как разложение по сингулярным значениям. Некоторые методы разложения матриц могут быть нестабильными, но имеют простые модификации, которые делают их стабильными; одним из примеров является нестабильный Грам-Шмидт, который можно легко изменить, чтобы получить стабильный модифицированный Грама-Шмидта. Другой классической проблемой численной линейной алгебры является обнаружение того, что метод исключения Гаусса нестабилен, но становится устойчивым с введением поворота.
Итерационные алгоритмы являются важной частью численной линейной алгебры по двум причинам. Во-первых, многие важные численные задачи не имеют прямого решения; Чтобы найти собственные значения и собственные векторы произвольной матрицы, мы можем использовать только итерационный подход. Во-вторых, безытерационные алгоритмы для произвольной матрицы требуют времени, что является удивительно высоким пределом, учитывая, что матрицы содержат только числа. Итерационные подходы могут использовать преимущества некоторых функций некоторых матриц, чтобы сократить это время. Например, когда матрица разреженная, итерационный алгоритм может пропустить многие шаги, которые обязательно должны выполняться при прямом подходе, даже если они являются избыточными шагами при наличии хорошо структурированной матрицы.
Ядром многих итерационных методов в числовой линейной алгебре является проекция матрицы на подпространство Крылова меньшей размерности, что позволяет аппроксимировать характеристики многомерной матрицы путем итеративного вычисления эквивалентных характеристик аналогичных матриц, начиная с пространства низкой размерности. и переход к более высоким измерениям. Когда A является симметричным и мы хотим решить линейную задачу Ax = b, классическим итерационным подходом является метод сопряженных градиентов. Если A не является симметричным, то примерами итерационных решений линейной задачи являются обобщенный метод минимальных невязок и CGN. Если A является симметричным, то для решения проблемы собственных значений и собственных векторов мы можем использовать алгоритм Ланцоша, а если A несимметричный, то мы можем использовать итерацию Арнольди.
Некоторые языки программирования используют методы оптимизации числовой линейной алгебры и предназначены для реализации алгоритмов числовой линейной алгебры. Эти языки включают MATLAB, Analytica, Maple и Mathematica. Другие языки программирования, которые явно не предназначены для числовой линейной алгебры, имеют библиотеки, которые предоставляют процедуры числовой линейной алгебры и оптимизацию; У C и Fortran есть такие пакеты, как подпрограммы базовой линейной алгебры и LAPACK, у python есть библиотека NumPy, а у Perl есть язык данных Perl. Многие команды числовой линейной алгебры в R полагаются на такие более фундаментальные библиотеки, как LAPACK. Другие библиотеки можно найти в Списке числовых библиотек.
