Пример.

Экспериментальные данные о значениях переменных х и у приведены в таблице.

В результате их выравнивания получена функция

Используя метод наименьших квадратов , аппроксимировать эти данные линейной зависимостью y=ax+b (найти параметры а и b ). Выяснить, какая из двух линий лучше (в смысле метода наименьших квадратов) выравнивает экспериментальные данные. Сделать чертеж.

Суть метода наименьших квадратов (МНК).

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

Таким образом, решение примера сводится к нахождению экстремума функции двух переменных.

Вывод формул для нахождения коэффициентов.

Составляется и решается система из двух уравнений с двумя неизвестными. Находим частные производные функции по переменным а и b , приравниваем эти производные к нулю.

Решаем полученную систему уравнений любым методом (например методом подстановки или ) и получаем формулы для нахождения коэффициентов по методу наименьших квадратов (МНК).

При данных а и b функция принимает наименьшее значение. Доказательство этого факта приведено .

Вот и весь метод наименьших квадратов. Формула для нахождения параметра a содержит суммы , , , и параметр n - количество экспериментальных данных. Значения этих сумм рекомендуем вычислять отдельно. Коэффициент b находится после вычисления a .

Пришло время вспомнить про исходый пример.

Решение.

В нашем примере n=5 . Заполняем таблицу для удобства вычисления сумм, которые входят в формулы искомых коэффициентов.

Значения в четвертой строке таблицы получены умножением значений 2-ой строки на значения 3-ей строки для каждого номера i .

Значения в пятой строке таблицы получены возведением в квадрат значений 2-ой строки для каждого номера i .

Значения последнего столбца таблицы – это суммы значений по строкам.

Используем формулы метода наименьших квадратов для нахождения коэффициентов а и b . Подставляем в них соответствующие значения из последнего столбца таблицы:

Следовательно, y = 0.165x+2.184 - искомая аппроксимирующая прямая.

Осталось выяснить какая из линий y = 0.165x+2.184 или лучше аппроксимирует исходные данные, то есть произвести оценку методом наименьших квадратов.

Оценка погрешности метода наименьших квадратов.

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

Так как , то прямая y = 0.165x+2.184 лучше приближает исходные данные.

Графическая иллюстрация метода наименьших квадратов (мнк).

На графиках все прекрасно видно. Красная линия – это найденная прямая y = 0.165x+2.184 , синяя линия – это , розовые точки – это исходные данные.

Для чего это нужно, к чему все эти аппроксимации?

Я лично использую для решения задач сглаживания данных, задач интерполяции и экстраполяции (в исходном примере могли бы попросить найти занчение наблюдаемой величины y при x=3 или при x=6 по методу МНК). Но подробнее поговорим об этом позже в другом разделе сайта.

Доказательство.

Чтобы при найденных а и b функция принимала наименьшее значение, необходимо чтобы в этой точке матрица квадратичной формы дифференциала второго порядка для функции была положительно определенной. Покажем это.

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

С помощью построения интерполяционного многочлена n-степени, который проходит непосредственно через все точки заданного массива данных. В данном случае аппроксимирующая функция представляется в виде: интерполяционного многочлена в форме Лагранжа или интерполяционного многочлена в форме Ньютона.

С помощью построения аппроксимирующего многочлена n-степени, который проходит в ближайшей близости от точек из заданного массива данных. Таким образом, аппроксимирующая функция сглаживает все случайные помехи (или погрешности), которые могут возникать при выполнении эксперимента: измеряемые значения в ходе опыта зависят от случайных факторов, которые колеблются по своим собственным случайным законам (погрешности измерений или приборов, неточность или ошибки опыта). В данном случае аппроксимирующая функция определяется по методу наименьших квадратов.

Метод наименьших квадратов (в англоязычной литературе Ordinary Least Squares, OLS) - математический метод, основанный на определении аппроксимирующей функции, которая строится в ближайшей близости от точек из заданного массива экспериментальных данных. Близость исходной и аппроксимирующей функции F(x) определяется числовой мерой, а именно: сумма квадратов отклонений экспериментальных данных от аппроксимирующей кривой F(x) должна быть наименьшей.

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

Метод наименьших квадратов используется:

Для решения переопределенных систем уравнений, когда количество уравнений превышает количество неизвестных;

Для поиска решения в случае обычных (не переопределенных) нелинейных систем уравнений;

Для аппроксимации точечных значений некоторой аппроксимирующей функцией.

Аппроксимирующая функция по методу наименьших квадратов определяется из условия минимума суммы квадратов отклонений расчетной аппроксимирующей функции от заданного массива экспериментальных данных. Данный критерий метода наименьших квадратов записывается в виде следующего выражения:

Значения расчетной аппроксимирующей функции в узловых точках ,

Заданный массив экспериментальных данных в узловых точках .

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

В зависимости от условий задачи аппроксимирующая функция представляет собой многочлен степени m

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

∙ В случае если степень аппроксимирующей функции m=1, то мы аппроксимируем табличную функцию прямой линией (линейная регрессия).

∙ В случае если степень аппроксимирующей функции m=2, то мы аппроксимируем табличную функцию квадратичной параболой (квадратичная аппроксимация).

∙ В случае если степень аппроксимирующей функции m=3, то мы аппроксимируем табличную функцию кубической параболой (кубическая аппроксимация).

В общем случае, когда требуется построить аппроксимирующий многочлен степени m для заданных табличных значений, условие минимума суммы квадратов отклонений по всем узловым точкам переписывается в следующем виде:

- неизвестные коэффициенты аппроксимирующего многочлена степени m;

Количество заданных табличных значений.

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

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

Данная система линейных алгебраических выражений может быть переписана в матричном виде:

В результате была получена система линейных уравнений размерностью m+1, которая состоит из m+1 неизвестных. Данная система может быть решена с помощью любого метода решения линейных алгебраических уравнений (например, методом Гаусса). В результате решения будут найдены неизвестные параметры аппроксимирующей функции, обеспечивающие минимальную сумму квадратов отклонений аппроксимирующей функции от исходных данных, т.е. наилучшее возможное квадратичное приближение. Следует помнить, что при изменении даже одного значения исходных данных все коэффициенты изменят свои значения, так как они полностью определяются исходными данными.

Аппроксимация исходных данных линейной зависимостью

(линейная регрессия)

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

Координаты узловых точек таблицы;

Неизвестные коэффициенты аппроксимирующей функции, которая задана в виде линейной зависимости.

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

Преобразуем полученную линейную систему уравнений.

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

Данные коэффициенты обеспечивают построение линейной аппроксимирующей функции в соответствии с критерием минимизации суммы квадратов аппроксимирующей функции от заданных табличных значений (экспериментальные данные).

Алгоритм реализации метода наименьших квадратов

1. Начальные данные:

Задан массив экспериментальных данных с количеством измерений N

Задана степень аппроксимирующего многочлена (m)

2. Алгоритм вычисления:

2.1. Определяются коэффициенты для построения системы уравнений размерностью

Коэффициенты системы уравнений (левая часть уравнения)

- индекс номера столбца квадратной матрицы системы уравнений

Свободные члены системы линейных уравнений (правая часть уравнения)

- индекс номера строки квадратной матрицы системы уравнений

2.2. Формирование системы линейных уравнений размерностью .

2.3. Решение системы линейных уравнений с целью определения неизвестных коэффициентов аппроксимирующего многочлена степени m.

2.4.Определение суммы квадратов отклонений аппроксимирующего многочлена от исходных значений по всем узловым точкам

Найденное значение суммы квадратов отклонений является минимально-возможным.

Аппроксимация с помощью других функций

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

Логарифмическая аппроксимация

Рассмотрим случай, когда аппроксимирующая функция задана логарифмической функцией вида:

Выбрав вид функции регрессии, т.е. вид рассматриваемой модели зависимости Y от Х (или Х от У), например, линейную модель y x =a+bx, необходимо определить конкретные значения коэффициентов модели.

При различных значениях а и b можно построить бесконечное число зависимостей вида y x =a+bx т.е на координатной плоскости имеется бесконечное количество прямых, нам же необходима такая зависимость, которая соответствует наблюдаемым значениям наилучшим образом. Таким образом, задача сводится к подбору наилучших коэффициентов.

Линейную функцию a+bx ищем, исходя лишь из некоторого количества имеющихся наблюдений. Для нахождения функции с наилучшим соответствием наблюдаемым значениям используем метод наименьших квадратов.

Обозначим: Y i - значение, вычисленное по уравнению Y i =a+bx i . y i - измеренное значение, ε i =y i -Y i - разность между измеренными и вычисленными по уравнению значениям, ε i =y i -a-bx i .

В методе наименьших квадратов требуется, чтобы ε i , разность между измеренными y i и вычисленными по уравнению значениям Y i , была минимальной. Следовательно, находим коэффициенты а и b так, чтобы сумма квадратов отклонений наблюдаемых значений от значений на прямой линии регрессии оказалась наименьшей:

Исследуя на экстремум эту функцию аргументов а и с помощью производных, можно доказать, что функция принимает минимальное значение, если коэффициенты а и b являются решениями системы:

(2)

Если разделить обе части нормальных уравнений на n, то получим:

Учитывая, что (3)

Получим , отсюда , подставляя значение a в первое уравнение, получим:

При этом b называют коэффициентом регрессии; a называют свободным членом уравнения регрессии и вычисляют по формуле:

Полученная прямая является оценкой для теоретической линии регрессии. Имеем:

Итак, является уравнением линейной регрессии.

Регрессия может быть прямой (b>0) и обратной (b Пример 1. Результаты измерения величин X и Y даны в таблице:

x i	-2	0	1	2	4
y i	0.5	1	1.5	2	3

Предполагая, что между X и Y существует линейная зависимость y=a+bx, способом наименьших квадратов определить коэффициенты a и b.

Решение. Здесь n=5
x i =-2+0+1+2+4=5;
x i 2 =4+0+1+4+16=25
x i y i =-2 0.5+0 1+1 1.5+2 2+4 3=16.5
y i =0.5+1+1.5+2+3=8

и нормальная система (2) имеет вид

Решая эту систему, получим: b=0.425, a=1.175. Поэтому y=1.175+0.425x.

Пример 2. Имеется выборка из 10 наблюдений экономических показателей (X) и (Y).

x i	180	172	173	169	175	170	179	170	167	174
y i	186	180	176	171	182	166	182	172	169	177

Требуется найти выборочное уравнение регрессии Y на X. Построить выборочную линию регрессии Y на X.

Решение. 1. Проведем упорядочивание данных по значениям x i и y i . Получаем новую таблицу:

x i	167	169	170	170	172	173	174	175	179	180
y i	169	171	166	172	180	176	177	182	182	186

Для упрощения вычислений составим расчетную таблицу, в которую занесем необходимые численные значения.

x i	y i	x i 2	x i y i
167	169	27889	28223
169	171	28561	28899
170	166	28900	28220
170	172	28900	29240
172	180	29584	30960
173	176	29929	30448
174	177	30276	30798
175	182	30625	31850
179	182	32041	32578
180	186	32400	33480
∑x i =1729	∑y i =1761	∑x i 2 299105	∑x i y i =304696
x=172.9	y=176.1	x i 2 =29910.5	xy=30469.6

Согласно формуле (4), вычисляем коэффициента регрессии

а по формуле (5)

Таким образом, выборочное уравнение регрессии имеет вид y=-59.34+1.3804x.
Нанесем на координатной плоскости точки (x i ; y i) и отметим прямую регрессии.

Рис 4

На рис.4 видно, как располагаются наблюдаемые значения относительно линии регрессии. Для численной оценки отклонений y i от Y i , где y i наблюдаемые, а Y i определяемые регрессией значения, составим таблицу:

x i	y i	Y i	Y i -y i
167	169	168.055	-0.945
169	171	170.778	-0.222
170	166	172.140	6.140
170	172	172.140	0.140
172	180	174.863	-5.137
173	176	176.225	0.225
174	177	177.587	0.587
175	182	178.949	-3.051
179	182	184.395	2.395
180	186	185.757	-0.243

Значения Y i вычислены согласно уравнению регрессии.

Заметное отклонение некоторых наблюдаемых значений от линии регрессии объясняется малым числом наблюдений. При исследовании степени линейной зависимости Y от X число наблюдений учитывается. Сила зависимости определяется величиной коэффициента корреляции.

Которое находит самое широкое применение в различных областях науки и практической деятельности. Это может быть физика, химия, биология, экономика, социология, психология и так далее, так далее. Волею судьбы мне часто приходится иметь дело с экономикой, и поэтому сегодня я оформлю вам путёвку в удивительную страну под названием Эконометрика =) …Как это не хотите?! Там очень хорошо – нужно только решиться! …Но вот то, что вы, наверное, определённо хотите – так это научиться решать задачи методом наименьших квадратов . И особо прилежные читатели научатся решать их не только безошибочно, но ещё и ОЧЕНЬ БЫСТРО;-) Но сначала общая постановка задачи + сопутствующий пример:

Пусть в некоторой предметной области исследуются показатели , которые имеют количественное выражение. При этом есть все основания полагать, что показатель зависит от показателя . Это полагание может быть как научной гипотезой, так и основываться на элементарном здравом смысле. Оставим, однако, науку в сторонке и исследуем более аппетитные области – а именно, продовольственные магазины. Обозначим через:

– торговую площадь продовольственного магазина, кв.м.,
– годовой товарооборот продовольственного магазина, млн. руб.

Совершенно понятно, что чем больше площадь магазина, тем в большинстве случаев будет больше его товарооборот.

Предположим, что после проведения наблюдений/опытов/подсчётов/танцев с бубном в нашем распоряжении оказываются числовые данные:

С гастрономами, думаю, всё понятно: – это площадь 1-го магазина, – его годовой товарооборот, – площадь 2-го магазина, – его годовой товарооборот и т.д. Кстати, совсем не обязательно иметь доступ к секретным материалам – довольно точную оценку товарооборота можно получить средствами математической статистики . Впрочем, не отвлекаемся, курс коммерческого шпионажа – он уже платный =)

Табличные данные также можно записать в виде точек и изобразить в привычной для нас декартовой системе .

Ответим на важный вопрос: сколько точек нужно для качественного исследования?

Чем больше, тем лучше. Минимально допустимый набор состоит из 5-6 точек. Кроме того, при небольшом количестве данных в выборку нельзя включать «аномальные» результаты. Так, например, небольшой элитный магазин может выручать на порядки больше «своих коллег», искажая тем самым общую закономерность, которую и требуется найти!

Если совсем просто – нам нужно подобрать функцию , график которой проходит как можно ближе к точкам . Такую функцию называют аппроксимирующей (аппроксимация – приближение) или теоретической функцией . Вообще говоря, тут сразу появляется очевидный «претендент» – многочлен высокой степени, график которого проходит через ВСЕ точки. Но этот вариант сложен, а зачастую и просто некорректен (т.к. график будет всё время «петлять» и плохо отражать главную тенденцию) .

Таким образом, разыскиваемая функция должна быть достаточно простА и в то же время отражать зависимость адекватно. Как вы догадываетесь, один из методов нахождения таких функций и называется методом наименьших квадратов . Сначала разберём его суть в общем виде. Пусть некоторая функция приближает экспериментальные данные :


Как оценить точность данного приближения? Вычислим и разности (отклонения) между экспериментальными и функциональными значениями (изучаем чертёж) . Первая мысль, которая приходит в голову – это оценить, насколько великА сумма , но проблема состоит в том, что разности могут быть и отрицательны (например, ) и отклонения в результате такого суммирования будут взаимоуничтожаться. Поэтому в качестве оценки точности приближения напрашивается принять сумму модулей отклонений:

или в свёрнутом виде: (вдруг кто не знает: – это значок суммы, а – вспомогательная переменная-«счётчик», которая принимает значения от 1 до ) .

Приближая экспериментальные точки различными функциями, мы будем получать разные значения , и очевидно, где эта сумма меньше – та функция и точнее.

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

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

И сейчас мы возвращаемся к другому важному моменту: как отмечалось выше, подбираемая функция должна быть достаточно простА – но ведь и таких функций тоже немало: линейная , гиперболическая , экспоненциальная , логарифмическая , квадратичная и т.д. И, конечно же, тут сразу бы хотелось «сократить поле деятельности». Какой класс функций выбрать для исследования? Примитивный, но эффективный приём:

– Проще всего изобразить точки на чертеже и проанализировать их расположение. Если они имеют тенденцию располагаться по прямой, то следует искать уравнение прямой с оптимальными значениями и . Иными словами, задача состоит в нахождении ТАКИХ коэффициентов – чтобы сумма квадратов отклонений была наименьшей.

Если же точки расположены, например, по гиперболе , то заведомо понятно, что линейная функция будет давать плохое приближение. В этом случае ищем наиболее «выгодные» коэффициенты для уравнения гиперболы – те, которые дают минимальную сумму квадратов .

А теперь обратите внимание, что в обоих случаях речь идёт о функции двух переменных , аргументами которой являются параметры разыскиваемых зависимостей :

И по существу нам требуется решить стандартную задачу – найти минимум функции двух переменных .

Вспомним про наш пример: предположим, что «магазинные» точки имеют тенденцию располагаться по прямой линии и есть все основания полагать наличие линейной зависимости товарооборота от торговой площади. Найдём ТАКИЕ коэффициенты «а» и «бэ», чтобы сумма квадратов отклонений была наименьшей. Всё как обычно – сначала частные производные 1-го порядка . Согласно правилу линейности дифференцировать можно прямо под значком суммы:

Если хотите использовать данную информацию для реферата или курсовика – буду очень благодарен за поставленную ссылку в списке источников, такие подробные выкладки найдёте мало где:

Составим стандартную систему:

Сокращаем каждое уравнение на «двойку» и, кроме того, «разваливаем» суммы:

Примечание : самостоятельно проанализируйте, почему «а» и «бэ» можно вынести за значок суммы. Кстати, формально это можно проделать и с суммой

Перепишем систему в «прикладном» виде:

после чего начинает прорисовываться алгоритм решения нашей задачи:

Координаты точек мы знаем? Знаем. Суммы найти можем? Легко. Составляем простейшую систему двух линейных уравнений с двумя неизвестными («а» и «бэ»). Систему решаем, например, методом Крамера , в результате чего получаем стационарную точку . Проверяя достаточное условие экстремума , можно убедиться, что в данной точке функция достигает именно минимума . Проверка сопряжена с дополнительными выкладками и поэтому оставим её за кадром (при необходимости недостающий кадр можно посмотреть ) . Делаем окончательный вывод:

Функция наилучшим образом (по крайне мере, по сравнению с любой другой линейной функцией) приближает экспериментальные точки . Грубо говоря, её график проходит максимально близко к этим точкам. В традициях эконометрики полученную аппроксимирующую функцию также называют уравнением пАрной линейной регрессии .

Рассматриваемая задача имеет большое практическое значение. В ситуации с нашим примером, уравнение позволяет прогнозировать, какой товарооборот («игрек») будет у магазина при том или ином значении торговой площади (том или ином значении «икс») . Да, полученный прогноз будет лишь прогнозом, но во многих случаях он окажется достаточно точным.

Я разберу всего лишь одну задачу с «реальными» числами, поскольку никаких трудностей в ней нет – все вычисления на уровне школьной программы 7-8 класса. В 95 процентов случаев вам будет предложено отыскать как раз линейную функцию, но в самом конце статьи я покажу, что ничуть не сложнее отыскать уравнения оптимальной гиперболы, экспоненты и некоторых других функций.

По сути, осталось раздать обещанные плюшки – чтобы вы научились решать такие примеры не только безошибочно, но ещё и быстро. Внимательно изучаем стандарт:

Задача

В результате исследования взаимосвязи двух показателей, получены следующие пары чисел:

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

Заметьте, что «иксовые» значения – натуральные, и это имеет характерный содержательный смысл, о котором я расскажу чуть позже; но они, разумеется, могут быть и дробными. Кроме того, в зависимости от содержания той или иной задачи как «иксовые», так и «игрековые» значения полностью или частично могут быть отрицательными. Ну а у нас дана «безликая» задача, и мы начинаем её решение :

Коэффициенты оптимальной функции найдём как решение системы:

В целях более компактной записи переменную-«счётчик» можно опустить, поскольку и так понятно, что суммирование осуществляется от 1 до .

Расчёт нужных сумм удобнее оформить в табличном виде:


Вычисления можно провести на микрокалькуляторе, но гораздо лучше использовать Эксель – и быстрее, и без ошибок; смотрим короткий видеоролик:

Таким образом, получаем следующую систему :

Тут можно умножить второе уравнение на 3 и из 1-го уравнения почленно вычесть 2-е . Но это везение – на практике системы чаще не подарочны, и в таких случаях спасает метод Крамера :
, значит, система имеет единственное решение.

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

Получены правые части соответствующих уравнений, значит, система решена правильно.

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

В отличие от прямой зависимости товарооборота магазина от его площади, найденная зависимость является обратной (принцип «чем больше – тем меньше») , и этот факт сразу выявляется по отрицательному угловому коэффициенту . Функция сообщает нам о том, что с увеличение некоего показателя на 1 единицу значение зависимого показателя уменьшается в среднем на 0,65 единиц. Как говорится, чем выше цена на гречку, тем меньше её продано.

Для построения графика аппроксимирующей функции найдём два её значения:

и выполним чертёж:


Построенная прямая называется линией тренда (а именно – линией линейного тренда, т.е. в общем случае тренд – это не обязательно прямая линия) . Всем знакомо выражение «быть в тренде», и, думаю, что этот термин не нуждается в дополнительных комментариях.

Вычислим сумму квадратов отклонений между эмпирическими и теоретическими значениями. Геометрически – это сумма квадратов длин «малиновых» отрезков (два из которых настолько малы, что их даже не видно) .

Вычисления сведём в таблицу:


Их можно опять же провести вручную, на всякий случай приведу пример для 1-й точки:

но намного эффективнее поступить уже известным образом:

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

Найдем соответствующую сумму квадратов отклонений – чтобы различать, я обозначу их буквой «эпсилон». Техника точно такая же:


И снова на всякий пожарный вычисления для 1-й точки:

В Экселе пользуемся стандартной функцией EXP (синтаксис можно посмотреть в экселевской Справке) .

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

Но тут следует отметить, что «хуже» – это ещё не значит , что плохо. Сейчас построил график этой экспоненциальной функции – и он тоже проходит близко к точкам – да так, что без аналитического исследования и сказать трудно, какая функция точнее.

На этом решение закончено, и я возвращаюсь к вопросу о натуральных значениях аргумента. В различных исследованиях, как правило, экономических или социологических, натуральными «иксами» нумеруют месяцы, годы или иные равные временнЫе промежутки. Рассмотрим, например, такую задачу.

Я математик-программист. Самый большой скачок в своей карьере я совершил, когда научился говорить:«Я ничего не понимаю!» Сейчас мне не стыдно сказать светилу науки, что мне читает лекцию, что я не понимаю, о чём оно, светило, мне говорит. И это очень сложно. Да, признаться в своём неведении сложно и стыдно. Кому понравится признаваться в том, что он не знает азов чего-то-там. В силу своей профессии я должен присутствовать на большом количестве презентаций и лекций, где, признаюсь, в подавляющем большинстве случаев мне хочется спать, потому что я ничего не понимаю. А не понимаю я потому, что огромная проблема текущей ситуации в науке кроется в математике. Она предполагает, что все слушатели знакомы с абсолютно всеми областями математики (что абсурдно). Признаться в том, что вы не знаете, что такое производная (о том, что это - чуть позже) - стыдно.

Но я научился говорить, что я не знаю, что такое умножение. Да, я не знаю, что такое подалгебра над алгеброй Ли. Да, я не знаю, зачем нужны в жизни квадратные уравнения. К слову, если вы уверены, что вы знаете, то нам есть над чем поговорить! Математика - это серия фокусов. Математики стараются запутать и запугать публику; там, где нет замешательства, нет репутации, нет авторитета. Да, это престижно говорить как можно более абстрактным языком, что есть по себе полная чушь.

Знаете ли вы, что такое производная? Вероятнее всего вы мне скажете про предел разностного отношения. На первом курсе матмеха СПбГУ Виктор Петрович Хавин мне определил производную как коэффициент первого члена ряда Тейлора функции в точке (это была отдельная гимнастика, чтобы определить ряд Тейлора без производных). Я долго смеялся над таким определением, покуда в итоге не понял, о чём оно. Производная не что иное, как просто мера того, насколько функция, которую мы дифференцируем, похожа на функцию y=x, y=x^2, y=x^3.

Я сейчас имею честь читать лекции студентам, которые боятся математики. Если вы боитесь математики - нам с вами по пути. Как только вы пытаетесь прочитать какой-то текст, и вам кажется, что он чрезмерно сложен, то знайте, что он хреново написан. Я утверждаю, что нет ни одной области математики, о которой нельзя говорить «на пальцах», не теряя при этом точности.

Задача на ближайшее время: я поручил своим студентам понять, что такое линейно-квадратичный регулятор . Не постесняйтесь, потратьте три минуты своей жизни, сходите по ссылке. Если вы ничего не поняли, то нам с вами по пути. Я (профессиональный математик-программист) тоже ничего не понял. И я уверяю, в этом можно разобраться «на пальцах». На данный момент я не знаю, что это такое, но я уверяю, что мы сумеем разобраться.

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

Итак, даны две точки (x0, y0), (x1, y1), например, (1,1) и (3,2), задача найти уравнение прямой, проходящей через эти две точки:

иллюстрация

Эта прямая должна иметь уравнение типа следующего:

Здесь альфа и бета нам неизвестны, но известны две точки этой прямой:

Можно записать это уравнение в матричном виде:

Тут следует сделать лирическое отступление: что такое матрица? Матрица это не что иное, как двумерный массив. Это способ хранения данных, более никаких значений ему придавать не стоит. Это зависит от нас, как именно интерпретировать некую матрицу. Периодически я буду её интерпретировать как линейное отображение, периодически как квадратичную форму, а ещё иногда просто как набор векторов. Это всё будет уточнено в контексте.

Давайте заменим конкретные матрицы на их символьное представление:

Тогда (alpha, beta) может быть легко найдено:

Более конкретно для наших предыдущих данных:

Что ведёт к следующему уравнению прямой, проходящей через точки (1,1) и (3,2):

Окей, тут всё понятно. А давайте найдём уравнение прямой, проходящей через три точки: (x0,y0), (x1,y1) и (x2,y2):

Ой-ой-ой, а ведь у нас три уравнения на две неизвестных! Стандартный математик скажет, что решения не существует. А что скажет программист? А он для начала перепишет предыдующую систему уравнений в следующем виде:

В нашем случае векторы i,j,b трёхмерны, следовательно, (в общем случае) решения этой системы не существует. Любой вектор (alpha\*i + beta\*j) лежит в плоскости, натянутой на векторы (i, j). Если b не принадлежит этой плоскости, то решения не существует (равенства в уравнении не достичь). Что делать? Давайте искать компромисс. Давайте обозначим через e(alpha, beta) насколько именно мы не достигли равенства:

И будем стараться минимизировать эту ошибку:

Почему квадрат?

Мы ищем не просто минимум нормы, а минимум квадрата нормы. Почему? Сама точка минимума совпадает, а квадрат даёт гладкую функцию (квадратичную функцию от агрументов (alpha,beta)), в то время как просто длина даёт функцию в виде конуса, недифференцируемую в точке минимума. Брр. Квадрат удобнее.

Очевидно, что ошибка минимизируется, когда вектор e ортогонален плоскости, натянутой на векторы i и j .

Иллюстрация

Иными словами: мы ищем такую прямую, что сумма квадратов длин расстояний от всех точек до этой прямой минимальна:

UPDATE: тут у меня косяк, расстояние до прямой должно измеряться по вертикали, а не ортогональной проекцией. комментатор прав.

Иллюстрация

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

Иллюстрация

Иное объяснение на пальцах: мы прикрепляем пружинку между всеми точками данных (тут у нас три) и прямой, что мы ищем, и прямая равновесного состояния есть именно то, что мы ищем.

Минимум квадратичной формы

Итак, имея данный вектор b и плоскость, натянутую на столбцы-векторы матрицы A (в данном случае (x0,x1,x2) и (1,1,1)), мы ищем вектор e с минимум квадрата длины. Очевидно, что минимум достижим только для вектора e , ортогонального плоскости, натянутой на столбцы-векторы матрицы A :

Иначе говоря, мы ищем такой вектор x=(alpha, beta), что:

Напоминаю, что этот вектор x=(alpha, beta) является минимумом квадратичной функции ||e(alpha, beta)||^2:

Тут нелишним будет вспомнить, что матрицу можно интерпретирвать в том числе как и квадратичную форму, например, единичная матрица ((1,0),(0,1)) может быть интерпретирована как функция x^2 + y^2:

квадратичная форма

Вся эта гимнастика известна под именем линейной регрессии .

Уравнение Лапласа с граничным условием Дирихле

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

Изначальный коммит доступен . Для минимизации внешних зависимостей я взял код своего софтверного рендерера, уже на хабре. Для решения линейной системы я пользуюсь OpenNL , это отличный солвер, который, правда, очень сложно установить: нужно скопировать два файла (.h+.c) в папку с вашим проектом. Всё сглаживание делается следующим кодом:

For (int d=0; d<3; d++) { nlNewContext(); nlSolverParameteri(NL_NB_VARIABLES, verts.size()); nlSolverParameteri(NL_LEAST_SQUARES, NL_TRUE); nlBegin(NL_SYSTEM); nlBegin(NL_MATRIX); for (int i=0; i<(int)verts.size(); i++) { nlBegin(NL_ROW); nlCoefficient(i, 1); nlRightHandSide(verts[i][d]); nlEnd(NL_ROW); } for (unsigned int i=0; i &face = faces[i]; for (int j=0; j<3; j++) { nlBegin(NL_ROW); nlCoefficient(face[ j ], 1); nlCoefficient(face[(j+1)%3], -1); nlEnd(NL_ROW); } } nlEnd(NL_MATRIX); nlEnd(NL_SYSTEM); nlSolve(); for (int i=0; i<(int)verts.size(); i++) { verts[i][d] = nlGetVariable(i); } }

X, Y и Z координаты отделимы, я их сглаживаю по отдельности. То есть, я решаю три системы линейных уравнений, каждое имеет количество переменных равным количеству вершин в моей модели. Первые n строк матрицы A имеют только одну единицу на строку, а первые n строк вектора b имеют оригинальные координаты модели. То есть, я привязываю по пружинке между новым положением вершины и старым положением вершины - новые не должны слишком далеко уходить от старых.

Все последующие строки матрицы A (faces.size()*3 = количеству рёбер всех треугольников в сетке) имеют одно вхождение 1 и одно вхождение -1, причём вектор b имеет нулевые компоненты напротив. Это значит, я вешаю пружинку на каждое ребро нашей треугольной сетки: все рёбра стараются получить одну и ту же вершину в качестве отправной и финальной точки.

Ещё раз: переменными являются все вершины, причём они не могут далеко отходить от изначального положения, но при этом стараются стать похожими друг на друга.

Вот результат:

Всё бы было хорошо, модель действительно сглажена, но она отошла от своего изначального края. Давайте чуть-чуть изменим код:

For (int i=0; i<(int)verts.size(); i++) { float scale = border[i] ? 1000: 1; nlBegin(NL_ROW); nlCoefficient(i, scale); nlRightHandSide(scale*verts[i][d]); nlEnd(NL_ROW); }

В нашей матрице A я для вершин, что находятся на краю, добавляю не строку из разряда v_i = verts[i][d], а 1000*v_i = 1000*verts[i][d]. Что это меняет? А меняет это нашу квадратичную форму ошибки. Теперь единичное отклонение от вершины на краю будет стоить не одну единицу, как раньше, а 1000*1000 единиц. То есть, мы повесили более сильную пружинку на крайние вершины, решение предпочтёт сильнее растянуть другие. Вот результат:

Давайте вдвое усилим пружинки между вершинами:
nlCoefficient(face[ j ], 2); nlCoefficient(face[(j+1)%3], -2);

Логично, что поверхность стала более гладкой:

А теперь ещё в сто раз сильнее:

Что это? Представьте, что мы обмакнули проволочное кольцо в мыльную воду. В итоге образовавшаяся мыльная плёнка будет стараться иметь наименьшую кривизну, насколько это возможно, касаясь-таки границы - нашего проволочного кольца. Именно это мы и получили, зафиксировав границу и попросив получить гладкую поверхность внутри. Поздравляю вас, мы только что решили уравнение Лапласа с граничными условиями Дирихле. Круто звучит? А на деле всего-навсего одну систему линейных уравнений решить.

Уравнение Пуассона

Давайте ещё крутое имя вспомним.

Предположим, что у меня есть такая картинка:

Всем хороша, только стул мне не нравится.

Разрежу картинку пополам:

И выделю руками стул:

Затем всё, что белое в маске, притяну к левой части картинки, а заодно по всей картинке скажу, что разница между двумя соседними пикселями должна равняться разнице между двумя соседними пикселями правой картинки:

For (int i=0; i

Вот результат:

Пример из жизни

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

У меня есть некоторое количество фотографий образцов ткани типа вот такой:

Моя задача сделать бесшовные текстуры из фотографий вот такого качества. Для начала я (автоматически) ищу повторяющийся паттерн:

Если я вырежу прямо вот этот четырёхугольник, то из-за искажений у меня края не сойдутся, вот пример четыре раза повторённого паттерна:

Скрытый текст

Вот фрагмент, где чётко видно шов:

Поэтому я вырезать буду не по ровной линии, вот линия разреза:

Скрытый текст

А вот повторённый четыре раза паттерн:

Скрытый текст

И его фрагмент, чтобы было виднее:

Уже лучше, рез шёл не по прямой линии, обойдя всякие завитушки, но всё же шов виден из-за неравномерности освещения на оригинальной фотографии. Вот тут-то и приходит на помощь метод наименьших квадратов для уравнения Пуассона. Вот конечный результат после выравнивания освещения:

Текстура получилась отлично бесшовной, и всё это автоматически из фотографии весьма посредственного качества. Не бойтесь математики, ищите простые объяснения, и будет вам инженерное счастье.