НГУ

Форумы НГУ
Текущее время: Пт ноя 15, 2019 7:51 pm

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 26 ]  На страницу 1, 2  След.
Автор Сообщение
СообщениеДобавлено: Вт апр 19, 2011 4:40 pm 
Не в сети
Редкий гость

Зарегистрирован: Вт апр 19, 2011 4:33 pm
Сообщения: 6
Дано: несколько тысяч систем из трех уравнений с тремя неизвестными, определители у всех ненулевые
Надо: решить их все с наименьшими вычислительными затратами

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

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вт апр 19, 2011 5:16 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Ср июн 15, 2005 4:00 pm
Сообщения: 1155
fnz писал(а):
Дано: несколько тысяч систем из трех уравнений с тремя неизвестными, определители у всех ненулевые
Надо: решить их все с наименьшими вычислительными затратами
Если бы их было не несколько тысяч, а всего одно, то наименее затратный способ был бы другим?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт апр 19, 2011 5:42 pm 
Не в сети
Редкий гость

Зарегистрирован: Вт апр 19, 2011 4:33 pm
Сообщения: 6
Неясно. Можно составить из набора матриц для этих систем одну блочную и обращать ее с помощью методов для разреженных матриц, которые в случае с одной маленькой матрицей работать не будут вообще.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт апр 19, 2011 9:59 pm 
Не в сети
Частый гость

Зарегистрирован: Ср янв 17, 2007 6:53 pm
Сообщения: 61
Системы не связаны между собой, да? А как они возникли, интересно, откуда берутся коэффициенты и т.п.
А Вы с какой целью минимизируете вычислительные затраты?

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт апр 19, 2011 11:19 pm 
Не в сети
Редкий гость

Зарегистрирован: Вт апр 19, 2011 4:33 pm
Сообщения: 6
Цитата:
Системы не связаны между собой, да?

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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср апр 20, 2011 3:16 am 
Не в сети
Опытный автор

Зарегистрирован: Вт авг 29, 2006 4:53 am
Сообщения: 443
Откуда: Кирилл Василевский
Простите, не вижу проблемы совершенно. Несколько тысяч - это очень мало, решать можно как угодно (если использовать нормальный язык программирования, конечно, тот же C++ хотя бы или Java). Было бы несколько десятков миллионов - тогда имело бы смысл как-то рассуждать об оптимальности, там время могло бы различаться уже на секунды.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср апр 20, 2011 3:45 am 
Не в сети
Весьма плодовитый автор

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

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

_________________
АФ


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср апр 20, 2011 4:09 am 
Не в сети
Опытный автор

Зарегистрирован: Вт авг 29, 2006 4:53 am
Сообщения: 443
Откуда: Кирилл Василевский
А точность легко сделать абсолютной, если использовать простые дроби :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср апр 20, 2011 1:13 pm 
Не в сети
Редкий гость

Зарегистрирован: Вт апр 19, 2011 4:33 pm
Сообщения: 6
Цитата:
Несколько тысяч - это очень мало, решать можно как угодно

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср апр 20, 2011 1:23 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Сб сен 01, 2001 7:00 am
Сообщения: 1577
Откуда: Александр Фенстер
Ещё раз напишу мысль: ничего быстрее подстановки чисел в заранее выведенные формулы для корней Вы не придумаете. Реализация LU-разложения через три вложенных фора в любом случае будет медленнее за счёт кучи лишних операций.

_________________
АФ


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср апр 20, 2011 1:27 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Пт окт 01, 2004 6:27 pm
Сообщения: 1869
fenster писал(а):
Ещё раз напишу мысль: ничего быстрее подстановки чисел в заранее выведенные формулы для корней Вы не придумаете.
Формула Крамера рулит? :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср апр 20, 2011 1:33 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
fenster писал(а):
Ещё раз напишу мысль: ничего быстрее подстановки чисел в заранее выведенные формулы для корней Вы не придумаете.

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

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср апр 20, 2011 1:44 pm 
Не в сети
Редкий гость

Зарегистрирован: Вт апр 19, 2011 4:33 pm
Сообщения: 6
Цитата:
Ещё раз напишу мысль: ничего быстрее подстановки чисел в заранее выведенные формулы для корней Вы не придумаете.

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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср апр 20, 2011 1:45 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Сб янв 07, 2006 3:05 am
Сообщения: 1041
Откуда: ага
Если я правильно понимаю, аппроксимируется градиент неизвестной функции нормалью плоскости наименьших квадратов? Но там же собственные числа/векторы искать надо, или я что-то путаю?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср апр 20, 2011 1:47 pm 
Не в сети
Редкий гость

Зарегистрирован: Вт апр 19, 2011 4:33 pm
Сообщения: 6
http://ru.wikipedia.org/wiki/%CC%CD%CA


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 26 ]  На страницу 1, 2  След.

Часовой пояс: UTC + 7 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: MSN [Bot] и гости: 5


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB