Системы линейных уравнений
Системы линейных уравнений
Одной из центральных проблем вычислительной линейной алгебры является решение систем линейных уравнений (см. разд. 8.1 и 8.2), отыскание собственных векторов и собственных значений (см. разд. 8.4), а также различные матричные разложения (см. разд. 8.3).Хорошо обусловленные системы с квадратной матрицей. Вычислительный блок Given/ Find.
С вычислительной точки зрения, решение СЛАУ с квадратной матрицей А не представляет трудностей, если размерность А не очень велика. С большой матрицей проблем также не возникает, если она не очень плохо обусловлена (конечно, надо учитывать, что объем вычислений возрастает с увеличением размерности матрицы).Функция lsolve
Альтернативой способу решения СЛАУ, введенному в предыдущем разделе, является применение встроенной функции isolve. Для этого система уравнений должна быть записана в матричной форме Аx=b: | isolve (А, b) – вектор решения системы линейных алгебраических уравнений:Произвольные системы линейных уравнений. Переопределенные системы.
Классические задачи решения СЛАУ, рассмотренные в предыдущем разделе, предполагают равное количество уравнений и неизвестных, т. е. квадратную матрицу А. Именно для таких систем доказано, что решение существует и единственно, если определитель матрицы |А| #0.Недоопределенные системы
Альтернативным рассмотренному в предыдущем разделе классу СЛАУ с прямоугольной матрицей размера MxN, (при M<N) является случай, когда количество уравнений меньше количества неизвестных. Как несложно сообразить, такие системы либо имеют бесконечное число решений, либо не имеют решения вовсе.Вырожденные и плохо обусловленные системы
Вернемся вновь к СЛАУ Aх=b с квадратной матрицей А размера MхN, которая, в отличие от рассмотренного выше "хорошего" случая (см. разд. 8.Г), требует специального подхода. Обратим внимание на два похожих типа СЛАУ: | вырожденная система (с нулевым определителем |А|=0);Матричные разложения. СЛАУ с треугольной матрицей.
Современная вычислительная линейная алгебра – бурно развивающаяся наука. Главная проблема линейной алгебры – это решение систем линейных уравнений. В настоящее время разработано множество методов, упрощающих эти задачи, которые, в частности, зависят от структуры матрицы СЛАУ.Разложение Холецкого
Разложением Холецкого симметричной (т. е. содержащей одинаковые элементы на местах, расположенных симметрично относительно главной диагонали) матрицы А является представление вида A=LLT, где L – треугольная матрица. Алгоритм Холецкого реализован во встроенной функции choiesky:LU-разложение
LU-разложением матрицы А, или треугольным разложением, называется матричное разложение вида PA=LU, где L и U – нижняя и верхняя треугольные матрицы соответственно, а р– (диагональная) матрица перестановок, P, А, L, и – квадратные матрицы одного порядка: | lu (A) – LU-разложение матрицы:QR-разложение
Среди матричных разложений особую роль играют ортогональные преобразования, обладающие свойством сохранения нормы вектора. Напомним из курса линейной алгебры, что матрица Q называется ортогональной, если QT Q=I, где I – единичная матрица.SVD-(сингулярное) разложение
Наиболее эффективными (но и ресурсоемкими) средствами решения произвольных СЛАУ (с матрицей А размера NxM) по методу наименьших квадратов являются так называемые полные ортогональные разложения, имеющие, по определению, вид A=UKVT.Собственные векторы и собственные значения матриц
Завершим главу, посвященную решению СЛАУ, еще одной задачей вычислительной линейной алгебры – задачей отыскания собственных векторов х и собственных значений А, матрицы А, т. е. решения матричного уравнения Ах=λх.