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

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

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

Ага-ага.

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

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

В.П. писал(а):
Формула Крамера рулит? :)

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

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

Автор:  Гост_Я [ Ср апр 20, 2011 2:14 pm ]
Заголовок сообщения: 

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

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

Автор:  Pavel E. Alaev [ Ср апр 20, 2011 10:21 pm ]
Заголовок сообщения: 

Я тоже ни разу не специалист, но если окажется, что для матриц 3x3 что-то будет работать быстрее, чем прямые формулы, это будет поразительно.

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

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

Pavel E. Alaev писал(а):
Я тоже ни разу не специалист, но если окажется, что для матриц 3x3 что-то будет работать быстрее, чем прямые формулы, это будет поразительно.

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

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

Автор:  Гост_Я [ Чт апр 21, 2011 1:10 pm ]
Заголовок сообщения: 

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

Автор:  Pavel E. Alaev [ Чт апр 21, 2011 9:28 pm ]
Заголовок сообщения: 

fenster писал(а):
В качестве оффтопика замечу, что современные компиляторы творят чудеса. Одним из таких чудес является loop unrolling (раскрутка цикла), при котором циклы, выполняющие небольшое число итераций, заменяются нециклическими последовательными вычислениями. ...

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

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

Автор:  Николай Ш [ Пт апр 22, 2011 3:02 am ]
Заголовок сообщения: 

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

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

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

Автор:  Гост_Я [ Пт апр 22, 2011 11:21 am ]
Заголовок сообщения: 

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

Автор:  ХОЗЯИН_КЛЕЯ [ Пт апр 22, 2011 11:43 am ]
Заголовок сообщения: 

Николай Ш писал(а):
Пользуемся формулой Кордано


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

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

Я думал что Eviews или stata справятся с такой задачей. :-? Если тут речь об МНК.

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