Вычислить коэффициенты а и b, чтобы сумма наименьших расстояний от всех точек до прямой была наименьшей

@RenarYagafarov · Регистрация: 12.01.2018

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

Известно, что у линейно зависит от X, т.е. у=а*х+b. Вычислить коэффициенты а и b, чтобы сумма наименьших расстояний от всех точек до прямой была наименьшей.
например : y=0.3 ; x=1.1
0.3=a*1.1+b
как найти а и b при условии,что сумма наименьших расстояний от всех точек до прямой была наименьшей?

@wer1 · 30.01.2019, 09:05

Уважаемый RenarYagafarov
ваша задача давно решена и имеет название Метод Наименьших Квадратов.

@SSC · 30.01.2019, 11:31

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

как найти а и b

Если точка одна, то никак.
Если точек две, то решается система из 2-х уравнений с 2-умя неизвестными.
А если точек больше 2-х, то используется метод, указанный нтч в сообщении 2

@Symon · 30.01.2019, 12:34

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

как найти а и b

Вы, похоже, не поняли свою задачу. Пример ваш непонятен. Если данная точка лежит на искомой прямой, то расстояние от этой точки до данной прямой равно нулю (при любых a, b).

@САлександр · 31.01.2019, 08:04

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

@wer1 · 31.01.2019, 08:37

Уважаемый САлександр,
вот формулы вычисляющие коэффициенты a и b
Для всех сумм индекс i изменяется от 1 до n

$https://www.cyberforum.ru/cgi-bin/latex.cgi?a=\frac{n\sum x_iy_i-\sum x_i\sum y_i}{n\sum x^2_i-(\sum x_i)^2}$

$https://www.cyberforum.ru/cgi-bin/latex.cgi?b=\frac{\sum y_i-a\sum x_i}{n}$

@САлександр · 01.02.2019, 04:13

нтч,Спасибо!

Добавлено через 2 часа 1 минуту
нтч, Сразу не глянул, только сейчас посмотрел внимательней и опознал. К сожалению, приведенные Вами формулы определяют не совсем ту прямую. А для той прямой у Вас нет формул (ссылки)? У меня сейчас проблемы со временем, а я уже затратил, за несколько подходов, часа полтора-два на попытки получить их. Но что-то запутался с дифференцированием модуля - в каждой попытке получаю различные результаты!

@jogano · 01.02.2019, 05:16

САлександр, если вчитаться в ваше условие, то нужно найти прямую y=ax+b такую, чтобы $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sum_{i=1}^{n}\frac{\left|ax_i+b-y_i \right|}{\sqrt{a^2+1}} \to min \: by \: a,b$ . А нтч вас слегка сбил с толку, приведя обычный метод нахождения апроксимирующей прямой методом найменьших квадратов и написав, безусловно, правильные формулы для нахождения этой прямой.
Брать производные суммы модулей вещь не благодарная, честно говоря. Тем более с радикалом от а в знаменателе.

@jogano · 01.02.2019, 23:27

САлександр, метод такой: нужная прямая должна проходить через две данные точки и так, чтобы выше и ниже её было равное число точек (если общее количество точек чётное) либо это количество должно отличаться на 1. Значит, метод перебора:
1) Берёте точку с номером i от 1 до n-1 и перебираете точки с номерами от i+1 до n, вычисляете сумму $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sum_{k=1\\k\neq i, \: k\neq j}^{n}\frac{\left|\left( y_i-y_j\right)\left( x_i-x_k\right) -\left(x_i-x_j \right)\left(y_i-y_k \right)\right|}{\sqrt{\left(x_i-x_j \right)^2+\left(y_i-y_j \right)^2}}$ , запоминаете сами две точки и сумму.
2) берёте следующее j, делаете то же самое. Если эта большая сумма меньше предыдущей, переопределяете вторую точку на текущую и запоминаете новую минимальную сумму. И так, пока не переберёте для данной точки i все точки после неё.
3) далее увеличиваете номер точки i на 1 и обратно перебираете пары этой (i+1-й) точки со всеми последующими, находя минимальную сумму, которая была бы меньше ранее зафиксированной.
В результате получите пару точек, через которую проходит ваша прямая $https://www.cyberforum.ru/cgi-bin/latex.cgi?y=\frac{y_i-y_j}{x_i-x_j}\left(x-x_i \right)+y_i$
Либо, без программирования и Экселя, это можно делать в Геогебре, проведя какую-то прямую, опустив их каждой данной точки перпендикуляры на неё и в отдельной переменной посчитав сумму длин этих перпендикуляров. Меняя точки, через которые проходит прямая (пользуясь правилом, что количество сверху и снизу или одинаково, или отличается на 1), определяете минимальную сумму отрезков.

@wer1 · 02.02.2019, 08:45

Уважаемый САлександр,
тут уважаемый jogano предложил неплохой способ решения вашей
задачи. Но гладко было на бумаге, да забыли про овраги! Может оказаться,
что одна или несколько точек сильно отклоняются от прямой. Тут следует
либо выкинуть эти точки, либо оценить отдельно ту погрешность, которую они
вносят в решение. И с учётом этой погрешности решать задачу тем методом,
который предложил уважаемый jogano, но уже без этих точек.
...
примечание
обратите внимание, что перемещая прямую параллельно себе, можно
сильно сократить число вычислений... - сумма модулей не меняется до тех пор,
пока прямая не "перешагнула" одну из точек.

@САлександр · 02.02.2019, 17:33

jogano, нтч, Спасибо за участие, но это уже (с большой вероятностью) для меня не актуально. Поясню: когда я прочитал задачу предложенную RenarYagafarov, то у меня мелькнула мысль, что ее решение может быть полезно мне для моих задач. Поэтому я заинтересовался и сильно обрадовался получив ответ от нтч, но это происходило буквально на бегу и я сразу не понял, что это решение не совсем той задачи. Потом озадачил пару знакомых математиков и вот что получил в ответ (обобщенно):
1. это сильно не по специализации, потому ответить сразу точно не могу, но поспрашиваю коллег,
2. предварительно - вроде бы аналитического решения нет (или не известно), но доказано (вроде бы?), что такая прямая обязана проходить через 2 заданных точки,
3. решение можно находить просто перебором - прямая через все (в общем случае) пары точек, с определением соответствующей суммы, если использовать не все пары, то можно попасть в локальный минимум, а мне надо абсолютный.
Т. к. у меня количество точек от 10⁵ и больше, то в реальном времени, например за 10 мс, таким методом я ничего рассчитать не успеваю. Жаль.
Но все равно всем спасибо!

@SSC · 07.02.2019, 13:55

САлександр, возможно Вы все таки не правильно ставите задачу и Вам нужно искать не минимальное линейное отклонение (МЛО), а минимальное квадратичное отклонение, которое решается методом предложенным нтч и имеющем единственное решение.
Решения для МЛО очень часто имеют бесконечное число решений, причем бесконечное число решений при абсолютных минимумах. Это легко понимается при решении этой задачи для 4 точек, расположенных в вершинах прямоугольника. Порассуждайте над этим простейшим примером, и может быть Вы решите, что Вам лучше подходит МНК, к тому же он имеет аналитическое решение.

@САлександр · 08.02.2019, 09:50

SSC, Спасибо, но мне интересна была именно минимальная сумма расстояний S₀, уравнение самой прямой (т.е. A,B) вообще-то не особо и нужно. К сожалению аналитического решения похоже нет, а перебор слишком медленно. Но обходился же ранее без этого. Так что жаль, но не трагично.
// По Вашему примеру с прямоугольником - вижу только 2 решения (продолжение диагоналей) с совпадающей S₀.

@SSC · 08.02.2019, 14:06

Сообщение от САлександр

По Вашему примеру с прямоугольником - вижу только 2 решения (продолжение диагоналей)

Да, я немного другую задачу представлял, не сумма кратчайших расстояний, а сумма отклонений.
Но и для Вашей задачи есть пример
На окружности равномерно расположены 2n точек (n>1). Имеем n решений

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД 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 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .

@RenarYagafarov 1 / 1 / 0 Регистрация: 12.01.2018 Сообщений: 101

	Вычислить коэффициенты а и b, чтобы сумма наименьших расстояний от всех точек до прямой была наименьшей 29.01.2019, 19:55. Показов 1978. Ответов 13 Метки нет (Все метки) Известно, что у линейно зависит от X, т.е. у=ах+b. Вычислить коэффициенты а и b, чтобы сумма наименьших расстояний от всех точек до прямой была наименьшей. например : y=0.3 ; x=1.1 0.3=a1.1+b как найти а и b при условии,что сумма наименьших расстояний от всех точек до прямой была наименьшей? 0

@wer1 1104 / 480 / 33 Регистрация: 05.07.2018 Сообщений: 1,870 Записей в блоге: 7
	30.01.2019, 09:05
	Уважаемый RenarYagafarov ваша задача давно решена и имеет название Метод Наименьших Квадратов. 0

@САлександр 483 / 275 / 57 Регистрация: 08.10.2015 Сообщений: 1,184
	31.01.2019, 08:04
	Уважаемый нтч, поделитесь, пожалуйста решением или дайте ссылку на решение задачи при количестве точек большем трех. 0

@wer1 1104 / 480 / 33 Регистрация: 05.07.2018 Сообщений: 1,870 Записей в блоге: 7
	31.01.2019, 08:37
	Уважаемый САлександр, вот формулы вычисляющие коэффициенты a и b Для всех сумм индекс i изменяется от 1 до n $https://www.cyberforum.ru/cgi-bin/latex.cgi?a=\frac{n\sum x_iy_i-\sum x_i\sum y_i}{n\sum x^2_i-(\sum x_i)^2}$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?b=\frac{\sum y_i-a\sum x_i}{n}$ 1

@САлександр 483 / 275 / 57 Регистрация: 08.10.2015 Сообщений: 1,184
	01.02.2019, 04:13
	нтч,Спасибо! Добавлено через 2 часа 1 минуту нтч, Сразу не глянул, только сейчас посмотрел внимательней и опознал. К сожалению, приведенные Вами формулы определяют не совсем ту прямую. А для той прямой у Вас нет формул (ссылки)? У меня сейчас проблемы со временем, а я уже затратил, за несколько подходов, часа полтора-два на попытки получить их. Но что-то запутался с дифференцированием модуля - в каждой попытке получаю различные результаты! 0

@jogano $Эксперт по математике/физике$ 6360 / 4067 / 1512 Регистрация: 09.10.2009 Сообщений: 7,550 Записей в блоге: 4
	01.02.2019, 05:16
	САлександр, если вчитаться в ваше условие, то нужно найти прямую y=ax+b такую, чтобы $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sum_{i=1}^{n}\frac{\left\|ax_i+b-y_i \right\|}{\sqrt{a^2+1}} \to min \: by \: a,b$ . А нтч вас слегка сбил с толку, приведя обычный метод нахождения апроксимирующей прямой методом найменьших квадратов и написав, безусловно, правильные формулы для нахождения этой прямой. Брать производные суммы модулей вещь не благодарная, честно говоря. Тем более с радикалом от а в знаменателе. 1

@jogano $Эксперт по математике/физике$ 6360 / 4067 / 1512 Регистрация: 09.10.2009 Сообщений: 7,550 Записей в блоге: 4
	01.02.2019, 23:27
	САлександр, метод такой: нужная прямая должна проходить через две данные точки и так, чтобы выше и ниже её было равное число точек (если общее количество точек чётное) либо это количество должно отличаться на 1. Значит, метод перебора: 1) Берёте точку с номером i от 1 до n-1 и перебираете точки с номерами от i+1 до n, вычисляете сумму $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sum_{k=1\\k\neq i, \: k\neq j}^{n}\frac{\left\|\left( y_i-y_j\right)\left( x_i-x_k\right) -\left(x_i-x_j \right)\left(y_i-y_k \right)\right\|}{\sqrt{\left(x_i-x_j \right)^2+\left(y_i-y_j \right)^2}}$ , запоминаете сами две точки и сумму. 2) берёте следующее j, делаете то же самое. Если эта большая сумма меньше предыдущей, переопределяете вторую точку на текущую и запоминаете новую минимальную сумму. И так, пока не переберёте для данной точки i все точки после неё. 3) далее увеличиваете номер точки i на 1 и обратно перебираете пары этой (i+1-й) точки со всеми последующими, находя минимальную сумму, которая была бы меньше ранее зафиксированной. В результате получите пару точек, через которую проходит ваша прямая $https://www.cyberforum.ru/cgi-bin/latex.cgi?y=\frac{y_i-y_j}{x_i-x_j}\left(x-x_i \right)+y_i$ Либо, без программирования и Экселя, это можно делать в Геогебре, проведя какую-то прямую, опустив их каждой данной точки перпендикуляры на неё и в отдельной переменной посчитав сумму длин этих перпендикуляров. Меняя точки, через которые проходит прямая (пользуясь правилом, что количество сверху и снизу или одинаково, или отличается на 1), определяете минимальную сумму отрезков. 1

@wer1 1104 / 480 / 33 Регистрация: 05.07.2018 Сообщений: 1,870 Записей в блоге: 7
	02.02.2019, 08:45
	Уважаемый САлександр, тут уважаемый jogano предложил неплохой способ решения вашей задачи. Но гладко было на бумаге, да забыли про овраги! Может оказаться, что одна или несколько точек сильно отклоняются от прямой. Тут следует либо выкинуть эти точки, либо оценить отдельно ту погрешность, которую они вносят в решение. И с учётом этой погрешности решать задачу тем методом, который предложил уважаемый jogano, но уже без этих точек. ... примечание обратите внимание, что перемещая прямую параллельно себе, можно сильно сократить число вычислений... - сумма модулей не меняется до тех пор, пока прямая не "перешагнула" одну из точек. 0

@САлександр 483 / 275 / 57 Регистрация: 08.10.2015 Сообщений: 1,184
	02.02.2019, 17:33
	jogano, нтч, Спасибо за участие, но это уже (с большой вероятностью) для меня не актуально. Поясню: когда я прочитал задачу предложенную RenarYagafarov, то у меня мелькнула мысль, что ее решение может быть полезно мне для моих задач. Поэтому я заинтересовался и сильно обрадовался получив ответ от нтч, но это происходило буквально на бегу и я сразу не понял, что это решение не совсем той задачи. Потом озадачил пару знакомых математиков и вот что получил в ответ (обобщенно): 1. это сильно не по специализации, потому ответить сразу точно не могу, но поспрашиваю коллег, 2. предварительно - вроде бы аналитического решения нет (или не известно), но доказано (вроде бы?), что такая прямая обязана проходить через 2 заданных точки, 3. решение можно находить просто перебором - прямая через все (в общем случае) пары точек, с определением соответствующей суммы, если использовать не все пары, то можно попасть в локальный минимум, а мне надо абсолютный. Т. к. у меня количество точек от 10⁵ и больше, то в реальном времени, например за 10 мс, таким методом я ничего рассчитать не успеваю. Жаль. Но все равно всем спасибо! 0

@SSC $Эксперт по математике/физике$ 3390 / 1913 / 571 Регистрация: 09.04.2015 Сообщений: 5,365
	07.02.2019, 13:55
	САлександр, возможно Вы все таки не правильно ставите задачу и Вам нужно искать не минимальное линейное отклонение (МЛО), а минимальное квадратичное отклонение, которое решается методом предложенным нтч и имеющем единственное решение. Решения для МЛО очень часто имеют бесконечное число решений, причем бесконечное число решений при абсолютных минимумах. Это легко понимается при решении этой задачи для 4 точек, расположенных в вершинах прямоугольника. Порассуждайте над этим простейшим примером, и может быть Вы решите, что Вам лучше подходит МНК, к тому же он имеет аналитическое решение. 0

@САлександр 483 / 275 / 57 Регистрация: 08.10.2015 Сообщений: 1,184
	08.02.2019, 09:50
	SSC, Спасибо, но мне интересна была именно минимальная сумма расстояний S₀, уравнение самой прямой (т.е. A,B) вообще-то не особо и нужно. К сожалению аналитического решения похоже нет, а перебор слишком медленно. Но обходился же ранее без этого. Так что жаль, но не трагично. // По Вашему примеру с прямоугольником - вижу только 2 решения (продолжение диагоналей) с совпадающей S₀. 0