Comments 16
Очень интересно, но ничего непонятно.
Спасибо за статью, к сожалению слабость математического аппарата, не позволяет оценить всю красоту статьи, но все равно спасибо.
По поводу пункта 1: извините, но как же задолбала эта хрень, распространяемая людьми скорее по привычке, чем от каких-то тайных знаний. Во-первых, утверждение "решать систему уравнений методом Гаусса проще, чем делать LU-разложение" -- это какой-то логический парадокс. Стандартный метод LU-разложения (например в LAPACK'е) -- это и есть метод Гаусса. Во-вторых, обращение матрицы -- это решение системы уравнений с правой частью равной единичной матрице. Поэтому, в-третьих, если матрица А не является почти вырожденной, а правая часть не отличается на много порядков от единичной матрицы, нет никакой разницы, решаете ли вы систему уравнений или сначала считаете обратную матрицу, а затем умножаете на правую часть. В-четвёртых, бывают ситуации, когда нужна именно обратная матрица, которая является конечным результатом, и тогда смотри пункт 2.
Не знаю, может и были когда-то времена, когда обратную матрицу считали методом Крамера (или бог его знает, какими ещё методами), и кто-то мудрый возвестил, что вместо обращения матрицы надо решать систему линейных уравнений, но в нынешнее время эти задачи решаются эквивалентными методами, и нет никакой разницы, как именно получать численное решение системы уравнений Ax = B.
которое в любом случае потребует LU-разложения матрицы
не знаю где вы увидели "проще, чем LU-разложение"
Во-первых, утверждение "решать систему уравнений методом Гаусса проще,
чем делать LU-разложение" -- это какой-то логический парадокс.
Стандартный метод LU-разложения (например в LAPACK'е) -- это и есть
метод Гаусса
Такого утверждения нет, виноват кривой перевод. В оригинале было: «it is faster and more accurate to solve a linear system by LU factorization (Gaussian elimination) with partial pivoting than by inverting A (which has, in any case, to be done by LU factorization)».
Во-вторых, обращение матрицы -- это решение системы уравнений с правой частью равной единичной матрице.
В статье речь идёт о системе, где правая часть — вектор. С точки зрения количества вычислений есть разница между решением системы, у которой правая часть матрица, и системы, у которой правая часть — вектор.
нет никакой разницы, решаете ли вы систему уравнений или сначала считаете обратную матрицу, а затем умножаете на правую часть
На практике разница есть. Я ради интереса попробовал решить систему с матрицей 10000x10000 на своём ноутбуке. Обращение матрицы с умножением в среднем заняло 20 с, а решение системы напрямую — в среднем 5 с. Так что разница очень даже ощутимая.
Если в правой части вектор, то понятно, что решать систему просто быстрее, но вся эта телега про "решайте систему, а не инвертируйте матрицу" обычно также повторяется для случая, когда в правой части стоит матрица. И аргументы идут именно как раз в духе того отрывка, что Вы привели: "it is faster and more accurate to solve a linear system than by inverting". Да, оно может быть "faster" (максимум в 4 раза по умножениям), но только в случае вектора в правой части, а про "more accurate" я как раз и писал, что это не так, кроме клинических случаев, в которых в любом случае LU-разложение не подходит.
Меня это задело, потому что я регулярно встречаю на форумах эти "лекции" (как правило вместо ответа на соврешенно другой вопрос) на тему того, как это плохо обращать матрицу, вместо этого надо решать систему уравнений. Но если в правой части тоже матрица, то просто так, в общем, нельзя сказать, что лучше. Выбор метода должен зависеть от того, что конкретно нужно посчитать, и нередко оказывается, что лучше сначала инвертировать матрицу.
"При этом задача наименьших квадратов решается, если строк больше, чем столбцов, или недоопределённая система, если столбцов больше, чем строк." -> "При этом, если строк больше, чем столбцов, то решение ищется по методу наименьших квадратов. А если столбцов больше, чем строк, то решается задача недоопределенной системы."
Просто адский гуглотранслейт, читать невозможно. Для практического использования все базовые алгоритмы реализованы в библиотеках и там же сделаны необходимые проверки на вырожденность матриц и прочее, а вот частные случаи чтобы решить, нужно знать теорию. Например, в библиотеке Python numpy предлагается реализация алгоритма наименьших квадратов (МНК), но нет взвешенного МНК, который часто бывает нужен. К счастью, это легко обходится с помощью нормирующей матрицы (которая постоянно нужна для реальных задач, но в статье выше о ней вообще не упомянули) - легко, при определенных ограничениях на коэффициенты. К примеру, я об этом писал в статье на хабре «Линейная алгебра для спутниковой интерферометрии» https://habr.com/ru/post/597227/
Я понимаю, что это перевод, но уж если вы переводите специализированную статью для широкой аудитории, то стоило хотя бы не самые базовые определения, вроде обусловленности, привести в начале статьи или в соответствующей части. А то это неуважение к аудитории просто.
Еще бы хорошо, написать про регуляризацию, когда на практике, если матрица может быть вырождена, заместо: M*b=a, стоит решать min ||M*b - a|| (если система имеет хотя бы одно решение, то будет 0, иначе ближайшая точка), (псевдо-инверсии тоже из этой оперы)
Ника Хигэма
ААААААА
перекрёстного произведения
Это шо за зверь?
определении произведения матриц
Называется "вычисление".
Библиотеки, конечно, хорошо. Но тот, кто использует численные методы, знает, что каждая задача особенная в том или ином смысле. Эти особенности могут испортить жизнь при стандартном подходе. С другой стороны, они же могут позволить что-то улучшить и ускорить, иногда существенно. По всем вопросам, затронутым в статье, есть давняя и обширная литература. Помню, на меня сильное впечатление произвела книжка Форсайта-Малькольма-Моулера "Машинные методы математических вычислений" издательства МИР 1980 г.
В противоположность этому решение задачи наименьших квадратов с разложением QR матрицы всегда численно устойчиво.
Очень сильные сомнения в верности этого утверждения.
По поводу пункта [2]:
Если теряется точность при выполнении операций над числами с плавающей запятой, то это проблема не линейной алгебры, а численных методов, которыми мы пользуемся. Ведь можно вычислять и без потери информации.
Семь грехов численной линейной алгебры