Как выбрать метод решения линейных уравнений

31

Насколько мне известно, есть 4 способа решения системы линейных уравнений (поправьте меня, если их больше):

  1. Если системная матрица является квадратной матрицей полного ранга, вы можете использовать правило Крамера;
  2. Вычислить обратную или псевдообратную матрицу системы;
  3. Используйте методы матричного разложения (гауссово или гауссово-жордановое исключение рассматривается как разложение LU);
  4. Используйте итерационные методы, такие как метод сопряженных градиентов.

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

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

Например, метод сопряженных градиентов используется для решения уравнений, в которых матрица является симметричной и положительно определенной, хотя его также можно применять к любым линейным уравнениям путем преобразования в . Также для положительно определенной матрицы вы можете использовать метод разложения Холецкого для поиска решения. Но я не знаю, когда выбрать метод CG, а когда выбрать разложение Холецкого. Мне кажется, нам лучше использовать метод CG для больших матриц.AИксзнак равнобATAИксзнак равноATб

Для прямоугольных матриц мы можем использовать QR-разложение или SVD, но, опять же, я не знаю, как выбрать одну из них.

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

chaohuang
источник
1
Привет @chaohuang, и добро пожаловать в SciComp! Возможно, вы захотите увидеть это обсуждение: scicomp.stackexchange.com/questions/81/…
Пол
Привет @Paul, спасибо за ваши комментарии, эта тема только о разреженных матрицах или любой матрице?
Chaohuang
6
Ваш вопрос имеет обширный охват и может быть слишком широким для формата вопросов и ответов, который мы имеем здесь на stackexchange ... Есть ли конкретный класс матричной системы, который вас интересует?
Павел
3
@chaohuang Есть множество книг на эту тему. Этот вопрос немного похож на вопрос врача, как они выбирают лечение «в целом». Если вы хотите задать вопрос, который не относится к определенному классу проблем, вы должны включить в работу, чтобы достаточно ознакомиться с полем, чтобы задать что-то точное. В противном случае объясните конкретную проблему, которая вас волнует.
Джед Браун
2
Из FAQ: Если вы можете представить себе целую книгу, которая отвечает на ваш вопрос, вы слишком много просите. С этим вопросом связаны целые журналы и сотни книг.
Дэвид Кетчон

Ответы:

45

Ваш вопрос немного похож на вопрос о том, какую отвертку выбрать в зависимости от привода (слот, Phillips, Torx, ...). Помимо того, что их слишком много , выбор также зависит от того, хотите ли вы просто затянуть один винт или собрать целый набор библиотечных полок. Тем не менее, в частичном ответе на ваш вопрос, вот некоторые из вопросов, которые вы должны учитывать при выборе метода решения линейной системы . Я также ограничусь обратимыми матрицами; случаи переопределенных или недоопределенных систем - это другой вопрос, и на самом деле это должны быть отдельные вопросы.AИксзнак равноб

Как вы правильно заметили, варианты 1 и 2 являются правильными: вычисление и применение обратной матрицы является чрезвычайно плохой идеей, поскольку она намного дороже и часто численно менее устойчива, чем применение одного из других алгоритмов. Это оставляет вам выбор между прямыми и итеративными методами. Первое , что нужно учитывать не матрица , но то , что вы ожидаете от численного решения ~ х :AИкс~

  1. Насколько точно это должно быть? Имеет ли необходимо решить систему до машинной точности, или вы удовлетворены ~ х , удовлетворяющих (скажем) ~ х - х * | | < 10 - 3 , где х * является точным решением?Икс~Икс~| |Икс~-Икс*| |<10-3Икс*
  2. Как быстро вам это нужно? Единственным важным показателем здесь является время на вашем компьютере - метод, который отлично масштабируется на огромном кластере, может быть не лучшим выбором, если у вас его нет, но у вас есть одна из этих новых блестящих карт Тесла.

Поскольку не существует такого понятия, как бесплатный обед, вам обычно приходится выбирать компромисс между ними. После этого вы начинаете смотреть на матрицу (и ваше оборудование), чтобы выбрать хороший метод (или, скорее, метод, для которого вы можете найти хорошую реализацию). (Обратите внимание, как я избегал писать «лучше» здесь ...) Наиболее важные свойства здесьA

  • Структура : Is симметричны? Это плотный или разреженный? Пластинчатые?A
  • Собственные значения : все ли они положительны (т Е. Определенно ли положительны)? Они сгруппированы? Некоторые из них имеют очень маленькую или очень большую величину?A

Имея это в виду, вам придется просмотреть (огромную) литературу и оценить различные методы, которые вы найдете для вашей конкретной проблемы. Вот некоторые общие замечания:

  • 1000О(N2)О(N3)A

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

    A

  • AA

  • Если вам неоднократно нужно решать линейные системы с одной и той же матрицей и разными правыми частями, прямые методы все равно могут быть быстрее, чем итерационные методы, поскольку вам нужно вычислить разложение только один раз. (Это предполагает последовательное решение; если у вас есть все правые стороны одновременно, вы можете использовать блочные методы Крылова.)

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

Поскольку вы просили ссылки в комментариях, вот несколько учебников и обзорных статей, чтобы вы могли начать. (Ни один из них - ни набор - не является исчерпывающим; этот вопрос слишком широк и слишком сильно зависит от вашей конкретной проблемы.)

Кристиан Клэйсон
источник
2
Мне нравится твоя аналогия с отверткой!
Павел
@chaohuang Если это ответило на ваш вопрос, вы должны принять его. (Если этого не произошло, не стесняйтесь указывать на то, чего не хватает.)
Кристиан Клэйсон,
@ChristianClason принял это. Я ждал и надеялся, что кто-нибудь сможет пролить свет на проблему прямоугольных матриц. Так как прошло много времени, я думаю, такого ответа никогда не будет :(
chaohuang
@chaohuang Спасибо. Если вы по-прежнему заинтересованы в прямоугольных матрицах, вы должны задать (связанный) вопрос на тему «Как выбрать метод для решения переопределенных систем».
Кристиан Клэйсон
Здесь ссылка на использование итерационных методов для решения больших разреженных систем линейных уравнений.
chaohuang