НГУ

Форумы НГУ
Текущее время: Вс ноя 17, 2019 8:35 pm

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




Начать новую тему Ответить на тему  [ Сообщений: 26 ]  На страницу Пред.  1, 2
Автор Сообщение
 Заголовок сообщения:
СообщениеДобавлено: Ср апр 20, 2011 1:50 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Сб янв 07, 2006 3:05 am
Сообщения: 1041
Откуда: ага
Ага-ага.

http://ru.wikipedia.org/wiki/%D0%9C%D0% ... 0%BD%D1%82


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

Зарегистрирован: Сб сен 01, 2001 7:00 am
Сообщения: 1577
Откуда: Александр Фенстер
В.П. писал(а):
Формула Крамера рулит? :)

Ну там получается 48 умножений, три деления и ни единого цикла и условия на каждую систему. Рискну ошибиться, но мне кажется, что для 3x3 таки да, рулит.

Хотя нужно просто написать честно и Крамера, и LU-разложение, запустить в цикле 10000 раз подряд и посмотреть, что быстрее :)

_________________
АФ


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

Зарегистрирован: Ср июн 15, 2005 4:00 pm
Сообщения: 1155
fnz писал(а):
Если обращать блочную матрицу с помощью итерационных методов, очевидно найдется некоторый порог точности, при котором итерационный метод для одной большой матрицы будет работать быстрее, чем точный метод для множества маленьких.
Очевидно, имеет смысл сравнивать только сравнимые вещи. Поэтому для "одной большой" и "множества маленьких" сравнивайте одинаковые методы (итерационные приближённые или прямые "точные"). Пока Вы не привели ни одного аргумента в пользу того, что сооружение одной большой и работа с ней дадут хоть какую-то экономию.

В плоском (двумерном случае) для оценки градиентов требуется решать систему из двух (а не трёх!) уравнений.


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

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
Я тоже ни разу не специалист, но если окажется, что для матриц 3x3 что-то будет работать быстрее, чем прямые формулы, это будет поразительно.

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


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

Зарегистрирован: Сб сен 01, 2001 7:00 am
Сообщения: 1577
Откуда: Александр Фенстер
Pavel E. Alaev писал(а):
Я тоже ни разу не специалист, но если окажется, что для матриц 3x3 что-то будет работать быстрее, чем прямые формулы, это будет поразительно.

В качестве оффтопика замечу, что современные компиляторы творят чудеса. Одним из таких чудес является loop unrolling (раскрутка цикла), при котором циклы, выполняющие небольшое число итераций, заменяются нециклическими последовательными вычислениями. Конкретно в случае LU-разложения матриц 3x3 там все циклы for будут с константными и очень маленькими границами, так что раскрутка почти наверное будет применена. Грамотный компилятор почти полностью избавится от накладных расходов, связанных с организацией циклов (таких как увеличение индексных переменных и проверка условий окончания).

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

_________________
АФ


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

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


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

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
fenster писал(а):
В качестве оффтопика замечу, что современные компиляторы творят чудеса. Одним из таких чудес является loop unrolling (раскрутка цикла), при котором циклы, выполняющие небольшое число итераций, заменяются нециклическими последовательными вычислениями. ...

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

Звучит завлекательно, но очевидно, что как бы крут не был метод для больших матриц, он должен использовать данные из исходной матрицы хотя бы одному разу (а на деле, очевидно, будет использовать по нескольку раз). То есть линейная зависимость от числа маленьких матриц никуда не денется. В матрице 3x3 девять элементов, по три раза каждый из них поучаствует в сложении-умножении - уже получим сравнимый с формулой Крамера объём вычислений.


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

Зарегистрирован: Сб янв 07, 2006 3:05 am
Сообщения: 1041
Откуда: ага
А я по-прежнему считаю, что нужно не систему решать, а искать собственные числа и собственные векторы.
Алгоритм такой:
1. Ищем центроид = среднее арифметическое радиус-векторов набора точек
2. Центрируем радиус-векторы = вычитаем из них центроид
3. Ищем сумму матриц, полученных -произведением (вектор-столбец умножаем на вектор-строку) центрированных радиус-векторов
Эта матрица симметричная и вещественнозначная => её собственные числа будут вещественными
4. Пользуемся формулой Кордано, чтобы найти собственные значения
5. Ищем собственные векторы
Нормированный собственный вектор, соответствующий наименьшему собственному значению и будет нормалью плоскости наименьших квадратов к набору точек (с точностью до знака)
6*. При помощи Riemannian Graph (хз как оно по-русски называется) эти нормали согласовываются (или выравниваются, хз) - строится граф, ищется минимальное остовное дерево, делается обход этого дерева для того, чтобы если соседние нормали торчат в разные стороны - у одной из них меняем знак. Т.к. в данном случае триангуляция уже дана, то городить этот граф не нужно, а просто смотрим нормали соседних треугольников.

Лично я таким способом ищу нормали в точках выборки с некоторой поверхности.

Про решения симметричных матрицы с оценками читать тут (3x3) и тут (NxN) + какие-то исходники, а про выравнивание вот тут неплохо написано


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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт апр 22, 2011 11:43 am 
Не в сети
Начинающий автор

Зарегистрирован: Вт окт 17, 2006 11:34 pm
Сообщения: 389
Николай Ш писал(а):
Пользуемся формулой Кордано


Колабе-Яо, плин.


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

Зарегистрирован: Чт июл 27, 2006 1:28 am
Сообщения: 54
Я думал что Eviews или stata справятся с такой задачей. :-? Если тут речь об МНК.


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

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


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

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


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

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