На первый взгляд задача нанесения размерных ограничений на рисунок кажется не более сложной, чем упражнение из школьного учебника.
Мне показалось то же самое, когда я впервые об этом узнал.
В то время я работал в компании, которая занималась разработкой программный комплекс для проектирования индивидуальных жилых домов с подготовкой проектной документации «под ключ».
В этом проекте я разрабатывал алгоритм генерации многоскатных крыш, а впоследствии и всего геометрического ядра на основе булевых операций, поэтому за дальнейшей историей следил издалека.
В какой-то момент заказчик захотел, чтобы проектировщики могли просто указать размеры комнат, углы наклона эркеров и ширину дверных проемов, а все остальные параметры внешней и внутренней конструкции программа автоматически рассчитывала.
дома.
Эта идея возникла у заказчика спонтанно, и поэтому нужно было срочно сделать «точно то же самое, что и в КАТИЯ «Наш руководитель группы с энтузиазмом подошел к задаче и приступил к разработке прототипа.
Он решил сотни уравнений в MathCAD, весь офис был завален графиками частичных решений для двух, трех, четырех точек… Его первоначальное предположение, что задача может Решить аналитически было фиаско: это был 2005 год, а это означало, что в Интернете невозможно было найти хоть какую-то информацию по этой теме.
В итоге, после двух месяцев интенсивных исследований, этот функционал пришлось реализовать.
исключать .
Часть 1: Введение Часть 2: Эскиз Часть 3: Степени свободы и уравнения ограничений Часть 4: «Таинственные пути решателя» или «Червоточины Ньютона» 
метод Ньютона Эта история закончилась печально, поскольку задача решения геометрических ограничений в общем случае сводится к решению системы нелинейных уравнений , которые современные математики решают в аналитической форме не знать как .
Поэтому все, что остается в условиях современных реалий, — это воспользоваться методом, названным в честь великого гения яблочных прозрений: метод Ньютона .
Этот метод позволяет найти ноль (корень) любой нелинейной функции (уравнения) итерационным методом с квадратичной сходимостью.
Это означает, что количество точных значащих цифр парный разряд с каждой итерацией метода.
Говоря простыми словами, вычисление нуля функции с высокой степенью точности достигается за сравнительно небольшое количество итераций.
В большинстве практических случаев достаточно 5–12 итераций.
При вынужденной необходимости использования метода Ньютона ситуация становится более драматичной: ведь этот метод не гарантирует нам сходимости даже при наличии решений, а успех нахождения решения во многом зависит от начального значения параметров при начало метода.
Кроме того, этот метод не позволяет найти все нули функции или корни уравнения, так как результат сходится к первому найденному корню.
Поэтому инженеру-конструктору все равно приходится чертить чертеж, максимально приближенный к конечному результату.
Если первоначальное предположение параметров слишком далеко от решения, метод Ньютона может не сходиться или может прийти к неожиданному решению.
Иллюстрация расхождения метода Ньютона , примененный к функции f(x)=x^{3}-2x+2. Давайте возьмем ноль в качестве первоначального предположения.
Первая итерация дает единицу в качестве приближения.
В свою очередь, второй снова дает ноль.
Метод зациклится и решение не будет найдено.
В общем случае построение последовательности аппроксимаций может быть очень запутанно .
Учитывая все обстоятельства, метод Ньютона можно рассматривать как волшебный черный ящик, который может сказать нам ответ, если он его найдет, но не может сказать нам, существует ли решение, если метод не сходится.
Решения непостижимы , как видно на следующих изображениях пути достижения решения (визуализируется след каждой точки на чертеже, координаты точек записываются на каждом из шагов метода Ньютона): 
Червоточины Ньютона
Как победить «Червей сомнения»?
Улучшение сходимости (декомпозиция задачи)
Для улучшения сходимости метода и скорости его работы обычно используют хитрые методы.методы разложения оригинальное задание.
Анализируя степени свободы и уравнения, можно разбить рисунок на различные независимые группы, чтобы эти части можно было решать по отдельности, а затем, зафиксировав значения уже полученных параметров, решить систему уравнений окончательно.
Методы декомпозиции позволяют значительно улучшить как сходимость, так и скорость работы алгоритма за счет того, что мы решаем не всю систему уравнений, а несколько небольших систем уравнений.
Алгоритмическая сложность метода Ньютона имеет полиномиальный характер, а это значит, что мы можем получить значительные преимущества, если решим систему «по частям».
Но реализация такой декомпозиции требует разработки алгоритма, который будет привязан к геометрической интерпретации исходных уравнений, то есть будет работать в терминах предметной области, а это ограничивает возможности решателя только геометрическими проблемы.
Например, декомпозиция для двумерного случая будет не очень эффективно работать для трехмерного случая, и, скорее всего, такую проблему придется решать отдельно.
Повышаем точность (обусловленность системы уравнений)
Реализация метода Ньютона решения систем нелинейных уравнений основана на метод линеаризации .Уравнение решается пошагово, причем на каждом шаге нелинейные функции представляются линейными, что позволяет решать систему линейных уравнений вместо системы нелинейных уравнений.
В результате сходимость метода Ньютона зависит от точности решения этой самой системы линейных уравнений.
Чем точнее решение на каждом шаге, тем быстрее и устойчивее сходится метод Ньютона и тем меньше других проблем, приводящих к тому, что решение не будет найдено.
В математике есть понятие обусловленность системы уравнений .
Говоря простыми словами, это некая величина, которая может сказать нам, насколько точным (достоверным) будет решение данной системы уравнений.
В качестве примера можно привести решение простейшего уравнения, которое в абстрактном мире математики можно рассматривать как частный случай системы уравнений: топор + б = 0. Его решение: х = -б/а Если воспользоваться геометрической интерпретацией, то топор+б представляет собой уравнение прямой, а ее пересечение с осью x является решением уравнения.
Теперь представьте, что исходные данные ( а , б ) для этого уравнения указаны с некоторой степенью точности.
В этом случае, чем меньше значение а , и чем линия ближе к параллельности оси x, тем больше будет неоднозначность решения.
Для небольших относительных изменений а ценности Икс существенно изменится.
Если рассматривать систему многих уравнений, то в процессе решения ошибка может накапливаться, и результат решения будет больше похож на характеристики погодных условий далеких планет , а не правильный результат решения системы линейных уравнений.
Поэтому очень важным моментом является контроль числа обусловленности системы уравнений и принятие ряда мер по приведению системы к виду, при котором можно получить наилучшую точность.
Примером того, где эта проблема может проявиться, является то, что уравнения несовместимы с точки зрения величин.
Например, используя геометрические ограничения, мы можем создать треугольник, зафиксировав длины двух сторон и угол между ними.
Уравнение ограничения длины записывается в миллиметрах, а ограничение угла, например, задается через равенство косинусов.
Несогласованность этих величин может быть причиной реализации различных сценариев потери точности: когда мы делаем небольшие треугольники размером порядка миллиметров, мы можем получить достаточно хорошую точность, но когда мы начинаем решать те же уравнения, но при длинах порядка километров мы получим совершенно другой результат относительной точности.
Это происходит потому, что значения длины существенно изменяются, а значения косинусов углов остаются в том же диапазоне значений.
я Я считаю что одним из вариантов решения проблемы несогласованности уравнений может быть формирование системы уравнений в однородная система координат , используя методы проективная геометрия , но этот вывод предчувствие , в силу моих весьма скромных познаний в области проективной геометрии в частности и всей математики в целом.
Есть вероятность, что эта тема уже освещалась, но, возможно, кто-то найдет способ защитить по ней диссертацию-другую.
Повышение производительности
Алгоритмическая сложность решения системы нелинейных уравнений методом Ньютона определяется главным образом сложностью решения системы линейных уравнений.Например, оригинал SolveSpace в соответствии с Джонатан Вестхью , автор SolveSpace , использует в качестве метода решения Гауссов метод , который имеет алгоритмическую сложность О(п^3) .
Это не очень быстро, если вам вдруг захочется решить большие эскизы, содержащие тысячи уравнений и неизвестных.
Но учитывая тот факт, что матрица системы линейных уравнений почти целиком состоит из нулей и сильно редкий для решения можно использовать алгоритмы с меньшей алгоритмической сложностью.
Дополнительным преимуществом записи уравнений в символьной форме является возможность их предварительной символьной оптимизации.
Такой операцией, например, является сокращение подобных.
Но существенного увеличения производительности можно добиться, если символически решить некоторые уравнения методом замены.
Например, в SolveSpace метод символьной замены решает такие ограничения, как сопоставление точек и горизонталь/вертикаль.
Использование этого метода позволяет существенно сократить количество уравнений и неизвестных, которые служат входными данными для метода Ньютона.
Вы можете узнать больше о том, как создаются символические выражения.
Заключение Несмотря на то, что тема решения систем нелинейных уравнений изначально кажется простой, она содержит множество подводных камней и фундаментальных проблем.
Я считаю, что в этой области еще есть над чем работать, поскольку помимо геометрических приложений решение систем нелинейных уравнений может быть полезно во многих областях: от решения задач оптимизации затрат до использования в системах искусственного интеллекта.
Часть 1: Введение Часть 2: Эскиз Часть 3: Степени свободы и уравнения ограничений Часть 4: «Таинственные пути решателя» или «Червоточины Ньютона» Теги: #CAD #CAD #Solver #SolveSpace #OpenSource #с открытым исходным кодом #C++ #CAD/CAM #математика #github
-
Выбрасывать Неудачный Опыт – Это Неправда
19 Oct, 24 -
Автомобильные Игры И Игры-Аватары
19 Oct, 24 -
Проституция
19 Oct, 24 -
2Гис - Отдельно, Спамеры - Отдельно
19 Oct, 24 -
Мой 286: От Покупки До Сегодняшнего Дня
19 Oct, 24
