НГУ
http://forum.nsu.ru/

Быстрое решение системы из трех уравнений
http://forum.nsu.ru/viewtopic.php?f=18&t=22314
Страница 1 из 2

Автор:  fnz [ Вт апр 19, 2011 4:40 pm ]
Заголовок сообщения:  Быстрое решение системы из трех уравнений

Дано: несколько тысяч систем из трех уравнений с тремя неизвестными, определители у всех ненулевые
Надо: решить их все с наименьшими вычислительными затратами

Что выбрать? Метод Крамера? LU-разложение?

Что изменится, если число неизвестных (и, соответственно, уравнений) возрастет до 4?

Возможно кто-то уже сталкивался с подобной проблемой, буду очень признателен за совет.

Автор:  Гост_Я [ Вт апр 19, 2011 5:16 pm ]
Заголовок сообщения:  Re: Быстрое решение системы из трех уравнений

fnz писал(а):
Дано: несколько тысяч систем из трех уравнений с тремя неизвестными, определители у всех ненулевые
Надо: решить их все с наименьшими вычислительными затратами
Если бы их было не несколько тысяч, а всего одно, то наименее затратный способ был бы другим?

Автор:  fnz [ Вт апр 19, 2011 5:42 pm ]
Заголовок сообщения: 

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

Автор:  orlang [ Вт апр 19, 2011 9:59 pm ]
Заголовок сообщения: 

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

P.S. Метод Крамера - зло.
P.P.S. Если системы не связаны, то все равно обращать каждый блок отдельно

Автор:  fnz [ Вт апр 19, 2011 11:19 pm ]
Заголовок сообщения: 

Цитата:
Системы не связаны между собой, да?

Нет, не связаны.
Цитата:
А как они возникли, интересно, откуда берутся коэффициенты и т.п.

Есть плоская треугольная сетка, в центрах масс ее ячеек задана некоторая функция. Задача - построить линейное приближение этой функции в каждой ячейке. В качестве такого приближения выбирается плоскость, которая меньше всего отклоняется от значений функции в рассматриваемой ячейке и соседних с ней ячейках. Т.е. получаются 4 точки в трехмерной пространстве, нужно построить плоскость, сумма расстояний от которой до этих точек будет наименьшей -> метод наименьших квадратов -> решение системы из трех уравнений с тремя неизвестными. Если сетка четырехугольная, то соседей 4, если сетка тетраэдральная (т.е. в трехмерном пространстве), то и соседей 4 и неизвестных в системе тоже 4.
Цитата:
А Вы с какой целью минимизируете вычислительные затраты?

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

Автор:  Ferlon Wilder [ Ср апр 20, 2011 3:16 am ]
Заголовок сообщения: 

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

Если же речь идёт не буквально о времени, а об эффективности метода с точки зрения теории алгоритмов, то, строго говоря, асимптотика решения с обращением матриц по отдельности любым способом получается ведь просто линейной от числа матриц - сами-то матрицы константного размера (ну, если всё-таки три на три, а не четыре на четыре и так далее, конечно). А вот насчёт того, чтобы составить блочную и обращать её быстрее... ничего сказать не могу.

Автор:  fenster [ Ср апр 20, 2011 3:45 am ]
Заголовок сообщения: 

К.О. подсказывает, что если речь о численном решении СЛАУ, то надо задуматься ещё о точности исходных данных и потере точности при вычислениях (привет, ВМЛА и второй курс ММФ). С этой точки зрения не все йогурты одинаково полезны.

Если же потеря точности вещественных чисел Вас тут не волнует и количество матриц порядка тысячи, то я склонен согласиться с Ferlon Wilder: тысяча -- это мало. Если Вы уверены, что все матрицы у Вас невырожденные, и все они заранее известного размера 3x3, то можно вообще тупо формулы для x1, x2, x3 заранее на бумажке просчитать в общем виде по школьному методу Гаусса, а потом только коэффициентики подставлять в готовое выражение.

Автор:  Ferlon Wilder [ Ср апр 20, 2011 4:09 am ]
Заголовок сообщения: 

А точность легко сделать абсолютной, если использовать простые дроби :)

Автор:  fnz [ Ср апр 20, 2011 1:13 pm ]
Заголовок сообщения: 

Цитата:
Несколько тысяч - это очень мало, решать можно как угодно

Решать эти несколько десятков тысяч систем нужно на каждом шаге по времени, которых тоже несколько десятков тысяч.

Ладно, время на раздумья у меня все равно истекло, попробую LU-разложение.

Автор:  fenster [ Ср апр 20, 2011 1:23 pm ]
Заголовок сообщения: 

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

Автор:  В.П. [ Ср апр 20, 2011 1:27 pm ]
Заголовок сообщения: 

fenster писал(а):
Ещё раз напишу мысль: ничего быстрее подстановки чисел в заранее выведенные формулы для корней Вы не придумаете.
Формула Крамера рулит? :)

Автор:  Коба [ Ср апр 20, 2011 1:33 pm ]
Заголовок сообщения: 

fenster писал(а):
Ещё раз напишу мысль: ничего быстрее подстановки чисел в заранее выведенные формулы для корней Вы не придумаете.

Метод научного тыка побыстрее будет :)

Автор:  fnz [ Ср апр 20, 2011 1:44 pm ]
Заголовок сообщения: 

Цитата:
Ещё раз напишу мысль: ничего быстрее подстановки чисел в заранее выведенные формулы для корней Вы не придумаете.

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

Цитата:
Реализация LU-разложения через три вложенных фора в любом случае будет медленнее за счёт кучи лишних операций.

Во-первых, для с помощью LU-разложения можно выписать явные выражения для корней. Во-вторых, даже если не выписывать их, откуда возьмутся три вложенных цикла? В-третьих, неужели вы хотите сказать, что LU-разложение в скорости будет уступать методу Крамера для матриц 3х3 и 4х4? ))

Автор:  Николай Ш [ Ср апр 20, 2011 1:45 pm ]
Заголовок сообщения: 

Если я правильно понимаю, аппроксимируется градиент неизвестной функции нормалью плоскости наименьших квадратов? Но там же собственные числа/векторы искать надо, или я что-то путаю?

Автор:  fnz [ Ср апр 20, 2011 1:47 pm ]
Заголовок сообщения: 

http://ru.wikipedia.org/wiki/%CC%CD%CA

Страница 1 из 2 Часовой пояс: UTC + 7 часов
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/