Поиск линейной комбинации векторов

@Mirmik · Регистрация: 27.02.2014

Студворк — интернет-сервис помощи студентам

Задача. Есть единичный 6-вектор. Назовем его target.
Есть набор, состоящий из больее чем одного единичного 6-вектора. Назовем этот набор component.

Задача найти такую единичную линейную комбинацию (combination) векторов из набора component, что скалярное произведение (combination, target) окажется максимально возможным (Совсем уж прямо максимум, на самом деле, необязательно).

Как бы это можно было бы решить?

@kabenyuk · 25.12.2018, 07:54

Mirmik, единичный вектор - вектор длины 1? А единичная линейная комбинации - сумма квадратов коэффициентов комбинации равна 1?

@woldemas · 25.12.2018, 11:14

Mirmik
Единичная линейная комбинация - это выпуклая линейная комбинация?
Все скалярные произведения целевого вектора и векторов набора заранее просчитываем получаем числа $https://www.cyberforum.ru/cgi-bin/latex.cgi?s_i$ .
Задача сводится к:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\\ \sum \alpha_i s_i \rightarrow max\\ \sum \alpha_i = 1\\ \alpha_i \geq 0$
Это задача линейного программирования и она, наверное, очень просто решается.

@Mirmik · 25.12.2018, 17:02 **[ТС]**

@kabenyuk
Некоректно сформулировал. Из "единичную линейную комбинацию" слово "единичную" можно убрать.
Да, единичный вектор - это вектор длины один, но без потери общности это условие тоже можно убрать.

@woldemas
Ну таки да. Она самая. Я нашел решение каким-то подобием градиентного спуска, но уверен, все можно сделать гораздо оптимальнее.
Наверняка нужен какой-то симплекс метод...

@jogano · 25.12.2018, 17:19

Mirmik, если опираться на обозначения поста #3, то максимальная сумма будет равна $https://www.cyberforum.ru/cgi-bin/latex.cgi?s_{max}=\underset{i=\bar{1;n}}{max}s_i$ . Т.е наибольшее скалярное произведение с коэффициентом 1, остальные скалярные произведения с коэффициентами 0. Доказательство очень простое:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?s_i\leq s_{max}, \: i=\bar{1;n}\\\alpha _is_i\leq \alpha _is_{max}\\\sum_{i=1}^{n}\alpha _i s_i\leq \sum_{i=1}^{n}\alpha_i s_{max} = s_{max}\sum_{i=1}^{n}\alpha_i=s_{max}$ , причём это максимум достигается, если при этом скалярное произведении взять коэффициент 1.

@Mirmik · 25.12.2018, 18:12 **[ТС]**

Кажется мне нужно уточнить исходные.

Есть вектор target.
Есть набор векторов combination.

Необходимо найти такую линейную комбинацию векторов combination, которая в результате дает target.

Понятно, что надо навесить сюда какое-то ограничение....
Ну, незнаю. Пусть сумма коэффициентов линейной комбинации будет минимальной, чтоли...

@jogano · 25.12.2018, 18:34

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

@kabenyuk · 25.12.2018, 18:58

Сообщение от jogano

разложение вектора по базису.

Даже и не по базису, поскольку заранее неизвестно, что за система. Значит может быть много разных комбинаций или ни одной.

@Mirmik · 26.12.2018, 11:18 **[ТС]**

Ок. Возвращаемся на шаг назад.

Решаем задачу о переводе роборуки из текущего положения А в положение Б.

Есть робот-манипулятор или функционально подобное ему изделие, описанное своей кинематической схемой. Каждое звено схемы задаёт тензор перехода системы координат. Тензор звена может параметризоваться кинематической координатой или быть константным. Тензор перехода всего изделия в целом есть функция набора кинематических координат.

Рассматриваем возможные перемещения по кинематическим координатам. Приводя возможное перемещение к выходному звену через тензор перехода соответствующей части звеньев, получаем 6-вектор сформированный координатами линейного и углового перемещения $https://www.cyberforum.ru/cgi-bin/latex.cgi?(\mathbf{\varphi}(q_i), \mathbf{r}(q_i))$ в системе координат выходного звена. И так по всему набору координат.

Теперь возьмем некоторый целевой тензор перехода, соответствующий положению Б выходного звена. Ищем тензор перехода из положения А в положение Б. Раскладываем тензор на линейный сдвиг и вектор Эйлера. Формируем 6-вектор кратчайшего пути из положения А в положение Б.

Теперь у нас есть целевой 6-вектор того, что мы хотим получить и набор 6-векторов компонент того, что мы можем выдать.
Составим целевой вектор из набора компонент. Получаем набор коэффициент, определяющий какое соотношение $https://www.cyberforum.ru/cgi-bin/latex.cgi?\dot{q_i}$ приведет выходное звено в движение согласованное с направлением целевого 6-вектора.

А с задачей поиска набора коэффициентов компонент я, собственно, сюда и пришел.

@Excalibur921 · 27.12.2018, 01:12

Сообщение от Mirmik

о переводе роборуки из текущего положения А в положение Б.

инверсная кинематика fabrik

@Mirmik · 27.12.2018, 10:29 **[ТС]**

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

@Excalibur921 · 27.12.2018, 13:25

Сообщение от Mirmik

на вопрос куда приеххать, а я решаю задачу о том, как туда ехать.

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

Сообщение от Mirmik

решает только поворотные шарниры.

Поэтому начинать нужно с кинематической схемы, задания типов шарниров и ограничений в первом посте. А затем слова типа я придумал решать это задачу так: …

Тут наверно 3 варианта:
1)попробуйте связаться с автором темы
Реализация инверсной кинематики методом Fabric
2)искать готовую либу решателей кинематики, неужели все пишут велик…
3)гуглить книги…это будет весь матан с нуля, типа
Инверсная кинематика
Многозвенные манипуляторы
Я бы искал как делали другие, возможно у манипулятора такими шарнирами по схеме есть общепринятое в мире название. Например Stanford Arm. Гуглить как решали. Попробуйте искать на eng либо форумах по робототехнике.

@Mirmik · 27.12.2018, 14:46 **[ТС]**

Еще раз ... Мне не нужен фабрик. Мне нужно разложить вектор по базису

.

Вопрос. Я правильно понимаю, что не могу применить симплекс метод в силу отсутствия ограничений на положительность коэффициентов разложения и сложность построения линейного функционала, или симплекс может быть применен к этой задаче?

Добавлено через 25 минут
Хотя... Это же просто уравнение...

Новые блоги и статьи Все статьи Все блоги /
Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .	Фото: Daniel Greenwood kumehtar 13.11.2025

@Mirmik techpriest 634 / 213 / 57 Регистрация: 27.02.2014 Сообщений: 1,180

	Поиск линейной комбинации векторов 24.12.2018, 16:11. Показов 1977. Ответов 12 Метки нет (Все метки) Задача. Есть единичный 6-вектор. Назовем его target. Есть набор, состоящий из больее чем одного единичного 6-вектора. Назовем этот набор component. Задача найти такую единичную линейную комбинацию (combination) векторов из набора component, что скалярное произведение (combination, target) окажется максимально возможным (Совсем уж прямо максимум, на самом деле, необязательно). Как бы это можно было бы решить? 0

@kabenyuk $Эксперт по математике/физике$ 4184 / 3052 / 918 Регистрация: 19.11.2012 Сообщений: 6,196
	25.12.2018, 07:54
	Mirmik, единичный вектор - вектор длины 1? А единичная линейная комбинации - сумма квадратов коэффициентов комбинации равна 1? 0

@woldemas 677 / 479 / 216 Регистрация: 06.09.2013 Сообщений: 1,312
	25.12.2018, 11:14
	Mirmik Единичная линейная комбинация - это выпуклая линейная комбинация? Все скалярные произведения целевого вектора и векторов набора заранее просчитываем получаем числа $https://www.cyberforum.ru/cgi-bin/latex.cgi?s_i$ . Задача сводится к: $https://www.cyberforum.ru/cgi-bin/latex.cgi?\\ \sum \alpha_i s_i \rightarrow max\\ \sum \alpha_i = 1\\ \alpha_i \geq 0$ Это задача линейного программирования и она, наверное, очень просто решается. 0

@Mirmik techpriest 634 / 213 / 57 Регистрация: 27.02.2014 Сообщений: 1,180
	25.12.2018, 17:02 [ТС]
	@kabenyuk Некоректно сформулировал. Из "единичную линейную комбинацию" слово "единичную" можно убрать. Да, единичный вектор - это вектор длины один, но без потери общности это условие тоже можно убрать. @woldemas Ну таки да. Она самая. Я нашел решение каким-то подобием градиентного спуска, но уверен, все можно сделать гораздо оптимальнее. Наверняка нужен какой-то симплекс метод... 0

@jogano $Эксперт по математике/физике$ 6360 / 4067 / 1512 Регистрация: 09.10.2009 Сообщений: 7,550 Записей в блоге: 4
	25.12.2018, 17:19
	Mirmik, если опираться на обозначения поста #3, то максимальная сумма будет равна $https://www.cyberforum.ru/cgi-bin/latex.cgi?s_{max}=\underset{i=\bar{1;n}}{max}s_i$ . Т.е наибольшее скалярное произведение с коэффициентом 1, остальные скалярные произведения с коэффициентами 0. Доказательство очень простое: $https://www.cyberforum.ru/cgi-bin/latex.cgi?s_i\leq s_{max}, \: i=\bar{1;n}\\\alpha _is_i\leq \alpha _is_{max}\\\sum_{i=1}^{n}\alpha _i s_i\leq \sum_{i=1}^{n}\alpha_i s_{max} = s_{max}\sum_{i=1}^{n}\alpha_i=s_{max}$ , причём это максимум достигается, если при этом скалярное произведении взять коэффициент 1. 1

@Mirmik techpriest 634 / 213 / 57 Регистрация: 27.02.2014 Сообщений: 1,180
	25.12.2018, 18:12 [ТС]
	Кажется мне нужно уточнить исходные. Есть вектор target. Есть набор векторов combination. Необходимо найти такую линейную комбинацию векторов combination, которая в результате дает target. Понятно, что надо навесить сюда какое-то ограничение.... Ну, незнаю. Пусть сумма коэффициентов линейной комбинации будет минимальной, чтоли... 0

@jogano $Эксперт по математике/физике$ 6360 / 4067 / 1512 Регистрация: 09.10.2009 Сообщений: 7,550 Записей в блоге: 4
	25.12.2018, 18:34
	Mirmik, а давайте вы вернётесь на шаг назад и объясните, зачем вам всё это нужно, чтобы не было задачи вида "хочу найти не знаю что", так как вы только что поставили совершенно другую задачу - разложение вектора по базису. 0

@Mirmik techpriest 634 / 213 / 57 Регистрация: 27.02.2014 Сообщений: 1,180
	26.12.2018, 11:18 [ТС]
	Ок. Возвращаемся на шаг назад. Решаем задачу о переводе роборуки из текущего положения А в положение Б. Есть робот-манипулятор или функционально подобное ему изделие, описанное своей кинематической схемой. Каждое звено схемы задаёт тензор перехода системы координат. Тензор звена может параметризоваться кинематической координатой или быть константным. Тензор перехода всего изделия в целом есть функция набора кинематических координат. Рассматриваем возможные перемещения по кинематическим координатам. Приводя возможное перемещение к выходному звену через тензор перехода соответствующей части звеньев, получаем 6-вектор сформированный координатами линейного и углового перемещения $https://www.cyberforum.ru/cgi-bin/latex.cgi?(\mathbf{\varphi}(q_i), \mathbf{r}(q_i))$ в системе координат выходного звена. И так по всему набору координат. Теперь возьмем некоторый целевой тензор перехода, соответствующий положению Б выходного звена. Ищем тензор перехода из положения А в положение Б. Раскладываем тензор на линейный сдвиг и вектор Эйлера. Формируем 6-вектор кратчайшего пути из положения А в положение Б. Теперь у нас есть целевой 6-вектор того, что мы хотим получить и набор 6-векторов компонент того, что мы можем выдать. Составим целевой вектор из набора компонент. Получаем набор коэффициент, определяющий какое соотношение $https://www.cyberforum.ru/cgi-bin/latex.cgi?\dot{q_i}$ приведет выходное звено в движение согласованное с направлением целевого 6-вектора. А с задачей поиска набора коэффициентов компонент я, собственно, сюда и пришел. 0

@Mirmik techpriest 634 / 213 / 57 Регистрация: 27.02.2014 Сообщений: 1,180
	27.12.2018, 10:29 [ТС]
	Fabrik - это решение немного другой задачи. Fabrik отвечает на вопрос куда приеххать, а я решаю задачу о том, как туда ехать. Кроме того класический fabrik решает только поворотные шарниры. 0

@Mirmik techpriest 634 / 213 / 57 Регистрация: 27.02.2014 Сообщений: 1,180
	27.12.2018, 14:46 [ТС]
	Еще раз ... Мне не нужен фабрик. Мне нужно разложить вектор по базису . Вопрос. Я правильно понимаю, что не могу применить симплекс метод в силу отсутствия ограничений на положительность коэффициентов разложения и сложность построения линейного функционала, или симплекс может быть применен к этой задаче? Добавлено через 25 минут Хотя... Это же просто уравнение... 0