Метод наименьших квадратов

Метод наименьших квадратов (МНК, OLS, Ordinary Least Squares ) - один из базовых методов регрессионного анализа для оценки неизвестных параметров регрессионных моделей по выборочным данным. Метод основан на минимизации суммы квадратов остатков регрессии.

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

Сущность МНК

Пусть задана некоторая (параметрическая) модель вероятностной (регрессионной) зависимости между (объясняемой) переменной y и множеством факторов (объясняющих переменных) x

где - вектор неизвестных параметров модели

- случайная ошибка модели.

Пусть также имеются выборочные наблюдения значений указанных переменных. Пусть - номер наблюдения (). Тогда - значения переменных в -м наблюдении. Тогда при заданных значениях параметров b можно рассчитать теоретические (модельные) значения объясняемой переменной y:

Величина остатков зависит от значений параметров b.

Сущность МНК (обычного, классического) заключается в том, чтобы найти такие параметры b, при которых сумма квадратов остатков (англ. Residual Sum of Squares ) будет минимальной:

В общем случае решение этой задачи может осуществляться численными методами оптимизации (минимизации). В этом случае говорят о нелинейном МНК (NLS или NLLS - англ. Non-Linear Least Squares ). Во многих случаях можно получить аналитическое решение. Для решения задачи минимизации необходимо найти стационарные точки функции , продифференцировав её по неизвестным параметрам b, приравняв производные к нулю и решив полученную систему уравнений:

Если случайные ошибки модели имеют нормальное распределение , имеют одинаковую дисперсию и некоррелированы между собой, МНК-оценки параметров совпадают с оценками метода максимального правдоподобия (ММП) .

МНК в случае линейной модели

Пусть регрессионная зависимость является линейной:

Пусть y - вектор-столбец наблюдений объясняемой переменной, а - матрица наблюдений факторов (строки матрицы - векторы значений факторов в данном наблюдении, по столбцам - вектор значений данного фактора во всех наблюдениях). Матричное представление линейной модели имеет вид:

Тогда вектор оценок объясняемой переменной и вектор остатков регрессии будут равны

соответственно сумма квадратов остатков регрессии будет равна

Дифференцируя эту функцию по вектору параметров и приравняв производные к нулю, получим систему уравнений (в матричной форме):

.

Решение этой системы уравнений и дает общую формулу МНК-оценок для линейной модели:

Для аналитических целей оказывается полезным последнее представление этой формулы. Если в регрессионной модели данные центрированы , то в этом представлении первая матрица имеет смысл выборочной ковариационной матрицы факторов, а вторая - вектор ковариаций факторов с зависимой переменной. Если кроме того данные ещё и нормированы на СКО (то есть в конечном итоге стандартизированы ), то первая матрица имеет смысл выборочной корреляционной матрицы факторов, второй вектор - вектора выборочных корреляций факторов с зависимой переменной.

Немаловажное свойство МНК-оценок для моделей с константой - линия построенной регрессии проходит через центр тяжести выборочных данных, то есть выполняется равенство:

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

Пример: простейшая (парная) регрессия

В случае парной линейной регрессии формулы расчета упрощаются (можно обойтись без матричной алгебры):

Свойства МНК-оценок

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

1. математическое ожидание случайных ошибок равно нулю, и
2. факторы и случайные ошибки - независимые случайные величины.

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

Для того, чтобы кроме состоятельности и несмещенности , оценки (обычного) МНК были ещё и эффективными (наилучшими в классе линейных несмещенных оценок) необходимо выполнение дополнительных свойств случайной ошибки:

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

Линейная модель, удовлетворяющая таким условиям, называется классической . МНК-оценки для классической линейной регрессии являются несмещёнными , состоятельными и наиболее эффективными оценками в классе всех линейных несмещённых оценок (в англоязычной литературе иногда употребляют аббревиатуру BLUE (Best Linear Unbaised Estimator ) - наилучшая линейная несмещённая оценка; в отечественной литературе чаще приводится теорема Гаусса - Маркова). Как нетрудно показать, ковариационная матрица вектора оценок коэффициентов будет равна:

Обобщенный МНК

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

Доказано (теорема Айткена), что для обобщенной линейной регрессионной модели (в которой на ковариационную матрицу случайных ошибок не налагается никаких ограничений) наиболее эффективными (в классе линейных несмещенных оценок) являются оценки т. н. обобщенного МНК (ОМНК, GLS - Generalized Least Squares) - LS-метода с весовой матрицей, равной обратной ковариационной матрице случайных ошибок: .

Можно показать, что формула ОМНК-оценок параметров линейной модели имеет вид

Ковариационная матрица этих оценок соответственно будет равна

Фактически сущность ОМНК заключается в определенном (линейном) преобразовании (P) исходных данных и применении обычного МНК к преобразованным данным. Цель этого преобразования - для преобразованных данных случайные ошибки уже удовлетворяют классическим предположениям.

Взвешенный МНК

В случае диагональной весовой матрицы (а значит и ковариационной матрицы случайных ошибок) имеем так называемый взвешенный МНК (WLS - Weighted Least Squares). В данном случае минимизируется взвешенная сумма квадратов остатков модели, то есть каждое наблюдение получает «вес», обратно пропорциональный дисперсии случайной ошибки в данном наблюдении: . Фактически данные преобразуются взвешиванием наблюдений (делением на величину, пропорциональную предполагаемому стандартному отклонению случайных ошибок), а к взвешенным данным применяется обычный МНК.

Некоторые частные случаи применения МНК на практике

Аппроксимация линейной зависимости

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

Таблица. Результаты измерений.

№ измерения
1
2
3
4
5
6

Вопрос звучит так: какое значение коэффициента можно подобрать, чтобы наилучшим образом описать зависимость ? Согласно МНК это значение должно быть таким, чтобы сумма квадратов отклонений величин от величин

была минимальной

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

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

История

До начала XIX в. учёные не имели определённых правил для решения системы уравнений , в которой число неизвестных меньше, чем число уравнений; до этого времени употреблялись частные приёмы, зависевшие от вида уравнений и от остроумия вычислителей, и потому разные вычислители, исходя из тех же данных наблюдений, приходили к различным выводам. Гауссу (1795) принадлежит первое применение метода, а Лежандр (1805) независимо открыл и опубликовал его под современным названием (фр. Méthode des moindres quarrés ) . Лаплас связал метод с теорией вероятностей , а американский математик Эдрейн (1808) рассмотрел его теоретико-вероятностные приложения . Метод распространён и усовершенствован дальнейшими изысканиями Энке , Бесселя , Ганзена и других.

Альтернативное использование МНК

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

Одно из применений - «решение» систем линейных уравнений, в которых число уравнений больше числа переменных

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

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

Пример.

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

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

Используя метод наименьших квадратов , аппроксимировать эти данные линейной зависимостью 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 функция принимала наименьшее значение, необходимо чтобы в этой точке матрица квадратичной формы дифференциала второго порядка для функции была положительно определенной. Покажем это.

3. Аппроксимация функций с помощью метода

наименьших квадратов

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

и другие.

Сущность метода наименьших квадратов состоит в следующем. Пусть результаты измерений представлены таблицей:

Таблица 4
				x n
				y n

(3.1)

где f - известная функция, a 0 , a 1 , …, a m - неизвестные постоянные параметры, значения которых надо найти. В методе наименьших квадратов приближение функции (3.1) к экспериментальной зависимости считается наилучшим, если выполняется условие

(3.2)

то есть сумм a квадратов отклонений искомой аналитической функции от экспериментальной зависимости должна быть минимальна .

Заметим, что функция Q называется невязкой.

Так как невязка

то она имеет минимум. Необходимым условием минимума функции нескольких переменных является равенство нулю всех частных производных этой функции по параметрам. Таким образом, отыскание наилучших значений параметров аппроксимирующей функции (3.1), то есть таких их значений, при которых Q = Q (a 0 , a 1 , …, a m ) минимальна, сводится к решению системы уравнений:

(3.3)

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

Нахождение параметров линейной функции

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

Требуется подобрать такие значения a и b , для которых функция

(3.4)

будет минимальной. Необходимые условия минимума функции (3.4) сводятся к системе уравнений:

После преобразований получаем систему двух линейных уравнений с двумя неизвестными:

(3.5)

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

Нахождение параметров квадратичной функции

Если аппроксимирующей функцией является квадратичная зависимость

то её параметры a , b , c находят из условия минимума функции:

(3.6)

Условия минимума функции (3.6) сводятся к системе уравнений:

После преобразований получаем систему трёх линейных уравнений с тремя неизвестными:

(3.7)

при решении которой находим искомые значения параметров a , b и c .

Пример . Пусть в результате эксперимента получена следующая таблица значений x и y :

Таблица 5
y i	0,705	0,495	0,426	0,357	0,368	0,406	0,549	0,768

Требуется аппроксимировать экспериментальные данные линейной и квадратичной функциями.

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

1. Сначала сцепим листы 1 и 2. Занесём экспериментальные значения x i и y i в столбцы А и В, начиная со второй строки (в первой строке поместим заголовки столбцов). Затем для этих столбцов вычислим суммы и поместим их в десятой строке.

В столбцах C – G разместим соответственно вычисление и суммирование

2. Расцепим листы.Дальнейшие вычисления проведём аналогичным образом для линейной зависимости на Листе 1и для квадратичной зависимости на Листе 2.

3. Под полученной таблицей сформируем матрицу коэффициентов и вектор-столбец свободных членов. Решим систему линейных уравнений по следующему алгоритму:

Для вычисления обратной матрицы и перемножения матриц воспользуемся Мастером функций и функциями МОБР и МУМНОЖ .

4. В блоке ячеек H2: H 9 на основе полученных коэффициентов вычислим значенияаппроксимирующего полинома y i выч ., в блоке I 2: I 9 – отклонения D y i = y i эксп . - y i выч .,в столбце J – невязку:

Полученные таблицы и построенные с помощью Мастера диаграмм графики приведёны на рисунках6, 7, 8.

Рис. 6. Таблица вычисления коэффициентов линейной функции,

аппроксимирующей экспериментальные данные.

Рис. 7. Таблица вычисления коэффициентов квадратичной функции,

аппроксимирующей экспериментальные данные.

Рис. 8. Графическое представление результатов аппроксимации

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

Ответ. Аппроксимировали экспериментальные данные линейной зависимостью y = 0,07881 x + 0,442262 c невязкой Q = 0,165167 и квадратичной зависимостью y = 3,115476 x 2 – 5,2175 x + 2,529631 c невязкой Q = 0,002103 .

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

Таблица 6
№0	x	0,1	0,2	0,3	0,4	0,5	0,6	0,7	0,8
	y	3,030	3,142	3,358	3,463	3,772	3,251	3,170	3,665
№ 1
		3,314	3,278	3,262	3,292	3,332	3,397	3,487	3,563
№ 2
		1,045	1,162	1,264	1,172	1,070	0,898	0,656	0,344
№ 3
		6,715	6,735	6,750	6,741	6,645	6,639	6,647	6,612
№ 4
		2,325	2,515	2,638	2,700	2,696	2,626	2,491	2,291
№ 5
		1.752	1,762	1,777	1,797	1,821	1,850	1,884	1,944
№ 6
		1,924	1,710	1,525	1,370	1,264	1,190	1,148	1,127
№ 7
		1,025	1,144	1,336	1,419	1,479	1,530	1,568	1,248
№ 8
		5,785	5,685	5,605	5,545	5,505	5,480	5,495	5,510
№ 9
		4,052	4,092	4,152	4,234	4,338	4,468	4,599	Tutorial Введение Я математик-программист. Самый большой скачок в своей карьере я совершил, когда научился говорить:«Я ничего не понимаю!» Сейчас мне не стыдно сказать светилу науки, что мне читает лекцию, что я не понимаю, о чём оно, светило, мне говорит. И это очень сложно. Да, признаться в своём неведении сложно и стыдно. Кому понравится признаваться в том, что он не знает азов чего-то-там. В силу своей профессии я должен присутствовать на большом количестве презентаций и лекций, где, признаюсь, в подавляющем большинстве случаев мне хочется спать, потому что я ничего не понимаю. А не понимаю я потому, что огромная проблема текущей ситуации в науке кроется в математике. Она предполагает, что все слушатели знакомы с абсолютно всеми областями математики (что абсурдно). Признаться в том, что вы не знаете, что такое производная (о том, что это - чуть позже) - стыдно. Но я научился говорить, что я не знаю, что такое умножение. Да, я не знаю, что такое подалгебра над алгеброй Ли. Да, я не знаю, зачем нужны в жизни квадратные уравнения. К слову, если вы уверены, что вы знаете, то нам есть над чем поговорить! Математика - это серия фокусов. Математики стараются запутать и запугать публику; там, где нет замешательства, нет репутации, нет авторитета. Да, это престижно говорить как можно более абстрактным языком, что есть по себе полная чушь. Знаете ли вы, что такое производная? Вероятнее всего вы мне скажете про предел разностного отношения. На первом курсе матмеха СПбГУ Виктор Петрович Хавин мне определил производную как коэффициент первого члена ряда Тейлора функции в точке (это была отдельная гимнастика, чтобы определить ряд Тейлора без производных). Я долго смеялся над таким определением, покуда в итоге не понял, о чём оно. Производная не что иное, как просто мера того, насколько функция, которую мы дифференцируем, похожа на функцию 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 Вот результат: Код и картинки доступны Если некоторая физическая величина зависит от другой величины, то эту зависимость можно исследовать, измеряя y при различных значениях x . В результате измерений получается ряд значений: x 1 , x 2 , ..., x i , ... , x n ; y 1 , y 2 , ..., y i , ... , y n . По данным такого эксперимента можно построить график зависимости y = ƒ(x). Полученная кривая дает возможность судить о виде функции ƒ(x). Однако постоянные коэффициенты, которые входят в эту функцию, остаются неизвестными. Определить их позволяет метод наименьших квадратов. Экспериментальные точки, как правило, не ложатся точно на кривую. Метод наименьших квадратов требует, чтобы сумма квадратов отклонений экспериментальных точек от кривой, т.е. 2 была наименьшей. На практике этот метод наиболее часто (и наиболее просто) используется в случае линейной зависимости, т.е. когда y = kx или y = a + bx. Линейная зависимость очень широко распространена в физике. И даже когда зависимость нелинейная, обычно стараются строить график так, чтобы получить прямую линию. Например, если предполагают, что показатель преломления стекла n связан с длиной λ световой волны соотношением n = a + b/λ 2 , то на графике строят зависимость n от λ -2 . Рассмотрим зависимость y = kx (прямая, проходящая через начало координат). Составим величину φ – сумму квадратов отклонений наших точек от прямой Величина φ всегда положительна и оказывается тем меньше, чем ближе к прямой лежат наши точки. Метод наименьших квадратов утверждает, что для k следует выбирать такое значение, при котором φ имеет минимум или (19) Вычисление показывает, что среднеквадратичная ошибка определения величины k равна при этом , (20) где – n число измерений. Рассмотрим теперь несколько более трудный случай, когда точки должны удовлетворить формуле y = a + bx (прямая, не проходящая через начало координат). Задача состоит в том, чтобы по имеющемуся набору значений x i , y i найти наилучшие значения a и b. Снова составим квадратичную форму φ , равную сумме квадратов отклонений точек x i , y i от прямой и найдем значения a и b , при которых φ имеет минимум ; . . Совместное решение этих уравнений дает (21) Среднеквадратичные ошибки определения a и b равны (23) .  (24) При обработке результатов измерения этим методом удобно все данные сводить в таблицу, в которой предварительно подсчитываются все суммы, входящие в формулы (19)–(24). Формы этих таблиц приведены в рассматриваемых ниже примерах. Пример 1. Исследовалось основное уравнение динамики вращательного движения ε = M/J (прямая, проходящая через начало координат). При различных значениях момента M измерялось угловое ускорение ε некоторого тела. Требуется определить момент инерции этого тела. Результаты измерений момента силы и углового ускорения занесены во второй и третий столбцы таблицы 5 . Таблица 5 n M, Н · м ε, c -1 M 2 M · ε ε - kM (ε - kM) 2 1 1.44 0.52 2.0736 0.7488 0.039432 0.001555 2 3.12 1.06 9.7344 3.3072 0.018768 0.000352 3 4.59 1.45 21.0681 6.6555 -0.08181 0.006693 4 5.90 1.92 34.81 11.328 -0.049 0.002401 5 7.45 2.56 55.5025 19.072 0.073725 0.005435 ∑ – – 123.1886 41.1115 – 0.016436 По формуле (19) определяем: . Для определения среднеквадратичной ошибки воспользуемся формулой (20) 0.005775 кг -1 · м -2 . По формуле (18) имеем ; . S J = (2.996 · 0.005775)/0.3337 = 0.05185 кг · м 2 . Задавшись надежностью P = 0.95 , по таблице коэффициентов Стьюдента для n = 5, находим t = 2.78 и определяем абсолютную ошибку ΔJ = 2.78 · 0.05185 = 0.1441 ≈ 0.2 кг · м 2 . Результаты запишем в виде: J = (3.0 ± 0.2) кг · м 2 ; Пример 2. Вычислим температурный коэффициент сопротивления металла по методу наименьших квадратов. Сопротивление зависит от температуры по линейному закону R t = R 0 (1 + α t°) = R 0 + R 0 α t°. Свободный член определяет сопротивление R 0 при температуре 0° C , а угловой коэффициент – произведение температурного коэффициента α на сопротивление R 0 . Результаты измерений и расчетов приведены в таблице (см. таблицу 6 ). Таблица 6 n t°, c r, Ом t-¯ t (t-¯ t) 2 (t-¯ t)r r - bt - a (r - bt - a) 2 ,10 -6 1 23 1.242 -62.8333 3948.028 -78.039 0.007673 58.8722 2 59 1.326 -26.8333 720.0278 -35.581 -0.00353 12.4959 3 84 1.386 -1.83333 3.361111 -2.541 -0.00965 93.1506 4 96 1.417 10.16667 103.3611 14.40617 -0.01039 107.898 5 120 1.512 34.16667 1167.361 51.66 0.021141 446.932 6 133 1.520 47.16667 2224.694 71.69333 -0.00524 27.4556 ∑ 515 8.403 – 8166.833 21.5985 – 746.804 ∑/n 85.83333 1.4005 – – – – – По формулам (21), (22) определяем R 0 = ¯ R- α R 0 ¯ t = 1.4005 - 0.002645 · 85.83333 = 1.1735 Ом . Найдем ошибку в определении α. Так как , то по формуле (18) имеем: . Пользуясь формулами (23), (24) имеем ; 0.014126 Ом . Задавшись надежностью P = 0.95, по таблице коэффициентов Стьюдента для n = 6, находим t = 2.57 и определяем абсолютную ошибку Δα = 2.57 · 0.000132 = 0.000338 град -1 . α = (23 ± 4) · 10 -4 град -1 при P = 0.95. Пример 3. Требуется определить радиус кривизны линзы по кольцам Ньютона. Измерялись радиусы колец Ньютона r m и определялись номера этих колец m. Радиусы колец Ньютона связаны с радиусом кривизны линзы R и номером кольца уравнением r 2 m = mλR - 2d 0 R, где d 0 – толщина зазора между линзой и плоскопараллельной пластинкой (или деформация линзы), λ – длина волны падающего света. λ = (600 ± 6) нм; r 2 m = y; m = x; λR = b; -2d 0 R = a, тогда уравнение примет вид y = a + bx . . Результаты измерений и вычислений занесены в таблицу 7 . Таблица 7 n x = m y = r 2 , 10 -2 мм 2 m -¯ m (m -¯ m) 2 (m -¯ m)y y - bx - a, 10 -4 (y - bx - a) 2 , 10 -6 1 1 6.101 -2.5 6.25 -0.152525 12.01 1.44229 2 2 11.834 -1.5 2.25 -0.17751 -9.6 0.930766 3 3 17.808 -0.5 0.25 -0.08904 -7.2 0.519086 4 4 23.814 0.5 0.25 0.11907 -1.6 0.0243955 5 5 29.812 1.5 2.25 0.44718 3.28 0.107646 6 6 35.760 2.5 6.25 0.894 3.12 0.0975819 ∑ 21 125.129 – 17.5 1.041175 – 3.12176 ∑/n 3.5 20.8548333 – – – – – Предыдущая статья: Чему равна скорость света Следующая статья: Чувственное и рациональное в познавательном процессе © 2015 . О сайте | Контакты | Карта сайта