Добро пожаловать!

Войдите или зарегистрируйтесь сейчас!

Войти

Итерационный алгоритм конформного преобразования?

Тема в разделе "Программы для пересчета координат и поиска ключей", создана пользователем zvezdochiot, 29 сен 2020.

  1. zvezdochiot

    Форумчанин

    Регистрация:
    27 июн 2014
    Сообщения:
    6.011
    Симпатии:
    2.127
    Адрес:
    г. Москва
    Есть ли итерационный алгоритм конформного преобразования? Абсолютная сходимость с классическим способом не требуется. Просто возиться с нормальными уравнениями на каждой степени - конкретный напряг. Может кто то где то что то похожее видел?

    PS: Подразумевается что то типа приближение рядом Тейлора.
     
    #1
  2. ErnieBoyd

    Форумчанин

    Регистрация:
    10 июн 2014
    Сообщения:
    272
    Симпатии:
    161
    @zvezdochiot, классический способ и есть приближение рядом Тейлора. Вот базовое представление условного уравнения для k неизвестных:
    --- Сообщения объединены, 2 окт 2020, Оригинальное время сообщения: 2 окт 2020 ---
    form_2020-10-02_10-00-10.png
    Справа отброшены члены разложений второго и более высоких порядков, поэтому получаются линейные уравнения. Мы ищем (и называем неизвестными величинами) приращения аргументов (xj - x0j).

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

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

    А возиться с нормальными уравнениями не надо. Раз уж не хочется пользоваться готовыми библиотеками, напишите собственную процедуру МНК для произвольного числа уравнений и неизвестных. На основе матричной алгебры это совсем не сложно. Написав один раз, можешь потом использовать всегда как чёрный ящик, не думая о начинке.
     
    #2
    igor kruchkovskiy нравится это.
  3. igor kruchkovskiy

    Форумчанин

    Регистрация:
    10 июн 2012
    Сообщения:
    3.471
    Симпатии:
    1.860
    Адрес:
    Астрахань
    Что за матричный способ? Это метод Гаусса?
     
    #3
  4. ErnieBoyd

    Форумчанин

    Регистрация:
    10 июн 2014
    Сообщения:
    272
    Симпатии:
    161
    Пусть имеется система линейных уравнений:

    A x = y

    Здесь A — прямоугольная матрица коэффициентов размера k × n; y — вектор измерений; x — вектор неизвестных величин; k — число неизвестных; n — число уравнений, n > k.

    Дополним систему квадратной симметрической матрицей ковариаций измерений V(ε). При некоррелированных измерениях V(ε) диагональная, называется весовой матрицей W и содержит на диагонали значения 1/σj2.

    Cистема нормальных уравнений имеет вид:

    AT W A x = AT W y

    Обратим матрицу (AT W A):

    Q = (AT W A)−1

    Найдём вектор неизвестных:

    x = Q AT W y

    Получим вектор невязок:

    e = A x − y

    Вычислим сумму квадратов невязок:

    RSS = eT W e

    Вычислим дисперсию:

    s2 = RSS / (n − k)

    Получим матрицу ковариаций неизвестных:

    V(x) = s2 Q

    Диагональные элементы V(x) — оценки погрешности неизвестных sx2.
     
    #4
    Patron, zvezdochiot и igor kruchkovskiy нравится это.
  5. zvezdochiot

    Форумчанин

    Регистрация:
    27 июн 2014
    Сообщения:
    6.011
    Симпатии:
    2.127
    Адрес:
    г. Москва
    Как ты представляешь себе в таком виде получение элементов этих уравнений? Особенно в контексте конформного преобразования. Уже вторая степень показала, что никакой "универсальностью" здесь даже и не пахнет.
     
    #5
  6. ErnieBoyd

    Форумчанин

    Регистрация:
    10 июн 2014
    Сообщения:
    272
    Симпатии:
    161
    Сколько раз решал задачи конформного преобразования, и вдруг оказывается, что это невозможно ::blink.gif::
     
    #6
  7. zvezdochiot

    Форумчанин

    Регистрация:
    27 июн 2014
    Сообщения:
    6.011
    Симпатии:
    2.127
    Адрес:
    г. Москва
    Что именно оказывается? Я потерял нить.

    Хотя, может ты и прав. В матричном виде всё выглядит достаточно просто. Мож меня куда то унесло?
     
    #7
  8. manikala

    Форумчанин

    Регистрация:
    7 апр 2010
    Сообщения:
    227
    Симпатии:
    68
    ErnieBoyd, поделись алгоритмом обращения плохообусловленной матрицы
     
    #8
  9. zvezdochiot

    Форумчанин

    Регистрация:
    27 июн 2014
    Сообщения:
    6.011
    Симпатии:
    2.127
    Адрес:
    г. Москва
    Извиняюсь за вмешательство. Но. Не обязательно нужен SVD, чтобы обращать плохообусловленную матрицу. Можно недопускать составление плохообусловленной матрицы. Один из методов: Гауссова нормализация переменных подстановкой вида:

    t = (x - M(x)) / sqrt(2 * D(x) / n)

    После такой подстановки очень сложно получить плохообусловленную матрицу (нормализация проводится до составления нормальных уравнений). Только вот само решение уже не будет таким простым.

    y(x) = A * x
    y(t) = B * t

    Прийдётся выражать A из B повторной подстановкой.

    y(x) = B * (x - M(x)) / sqrt(2 * D(x) / n) = A * x
     
    #9
  10. zvezdochiot

    Форумчанин

    Регистрация:
    27 июн 2014
    Сообщения:
    6.011
    Симпатии:
    2.127
    Адрес:
    г. Москва
    Вот действительно жизнь - кривая дорожка. Попытался "упростить" и сам себя запутал. В то время как старый добрый "дедовский" способ работает как часы. Можно даже использовать такие "вкусности", как LL-разложение. В силу изложенного, признаю абсурдность данной "темы". Вот же умудрился сам себя так запутать. Осталось только как то автоматизировать повторную подстановку (https://geodesist.ru/threads/iteracionnyj-algoritm-konformnogo-preobrazovanija.85528/#post-972330) и "шах и мат".
     
    #10
  11. ErnieBoyd

    Форумчанин

    Регистрация:
    10 июн 2014
    Сообщения:
    272
    Симпатии:
    161
    Конформное преобразование есть частный случай аффинного. Аффинное преобразование линейное. Не нужна линеаризация уравнений в виде разложений в ряды с отбрасыванием «лишних» членов, оно линейное по определению.

    Одна из форм записи двумерного аффинного преобразования:
    A x1 + B x2 + C = y1
    D x1 + E x2 + F = y2
    Каждая пара координат в исходной системе (x1, x2) и в целевой системе (y1, y2) даёт два уравнения. Очевидно, получаются две системы системы уравнений, которые решаются независимо друг от друга. Решение первой даст вектор неизвестных (A, B, C), второй — (D, E, F).

    Прелесть линейного преобразования в том, что если перенести начала координат в исходной и в целевой системах в центры масс:
    ξij = xij − xi0 , где xi0 = ∑ xij wj / ∑ wj
    ηij = yij − yi0 , где yi0 = ∑ yij wj / ∑ wj
    то коэффициенты C, F выпадают из рассмотрения. Остаются неизвестные A, B, D, E. После их нахождения C, F вычисляются простой подстановкой.
    Перенос координат не только уменьшает порядок обращаемой матрицы, но и исключает ошибки округления, когда расстояния между пунктами много меньше значений координат.

    N. B. Поскольку преобразование линейное, задача всегда решается одной итерацией!

    Конформное преобразование накладывает ограничения. Каждая пара координат даёт два уравнения в одну систему:
    A x1 + B x2 + C = y1
    −B x1 + A x2 + F = y2
    При этом благодаря особенностям получаемой матрицы нормальных уравнений порядок решаемой системы можно уменьшить вдвое.

    С готовыми A, B получаем альтернативное представление — масштаб s и разворот θ:
    s2 = A2 + B2
    tg θ = B / A
     
    #11
  12. zvezdochiot

    Форумчанин

    Регистрация:
    27 июн 2014
    Сообщения:
    6.011
    Симпатии:
    2.127
    Адрес:
    г. Москва
    Да разобрался уже: https://geodesist.ru/threads/iteracionnyj-algoritm-konformnogo-preobrazovanija.85528/#post-972366 .

    Форма https://geodesist.ru/threads/iteracionnyj-algoritm-konformnogo-preobrazovanija.85528/#post-972558 кстати не так хороша как матричная: https://geodesist.ru/threads/iteracionnyj-algoritm-konformnogo-preobrazovanija.85528/#post-972309 . Матричная просто гениальна своей простотой. Каким чортом меня от неё унесло, самому не понятно.

    PS: Чтобы не было непоняток: Под итерацией я подразумевал рост степени преобразования (1-я - линейная, 2-я - квадратическая, 3-я - кубическая,...)
     
    #12
  13. zvezdochiot

    Форумчанин

    Регистрация:
    27 июн 2014
    Сообщения:
    6.011
    Симпатии:
    2.127
    Адрес:
    г. Москва
    Для 1ой степени (линейное преобразование) - да (матрица нормальных уравнений фактически "единичная"), но для больших степеней преобразования нужен не просто перенос, а нормализация вида: https://geodesist.ru/threads/iteracionnyj-algoritm-konformnogo-preobrazovanija.85528/#post-972330 . Без неё число обусловленности матрицы нормальных уравнений значительная. А чтобы не путаться, гауссову нормализацию стоит производить всегда.
     
    #13

Поделиться этой страницей

  1. Этот сайт использует файлы cookie. Продолжая пользоваться данным сайтом, Вы соглашаетесь на использование нами Ваших файлов cookie.
    Скрыть объявление