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

Количество строк (исходных данных)

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

1. выбор формы связи (вида аналитического уравнения регрессии);
2. оценку параметров уравнения;
3. оценку качества аналитического уравнения регрессии.

Наиболее часто для описания статистической связи признаков используется линейная форма. Внимание к линейной связи объясняется четкой экономической интерпретацией ее параметров, ограниченной вариацией переменных и тем, что в большинстве случаев нелинейные формы связи для выполнения расчетов преобразуют (путем логарифмирования или замены переменных) в линейную форму.
В случае линейной парной связи уравнение регрессии примет вид: y i =a+b·x i +u i . Параметры данного уравнения а и b оцениваются по данным статистического наблюдения x и y . Результатом такой оценки является уравнение: , где , - оценки параметров a и b , - значение результативного признака (переменной), полученное по уравнению регрессии (расчетное значение).

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

Задача оценивания параметров линейного парного уравнения методом наименьших квадратов состоит в следующем: получить такие оценки параметров , , при которых сумма квадратов отклонений фактических значений результативного признака - y i от расчетных значений – минимальна.
Формально критерий МНК можно записать так: .

Классификация методов наименьших квадратов

1. Метод наименьших квадратов.
2. Метод максимального правдоподобия (для нормальной классической линейной модели регрессии постулируется нормальность регрессионных остатков).
3. Обобщенный метод наименьших квадратов ОМНК применяется в случае автокорреляции ошибок и в случае гетероскедастичности.
4. Метод взвешенных наименьших квадратов (частный случай ОМНК с гетероскедастичными остатками).

Проиллюстрируем суть классического метода наименьших квадратов графически . Для этого построим точечный график по данным наблюдений (x i , y i , i=1;n) в прямоугольной системе координат (такой точечный график называют корреляционным полем). Попытаемся подобрать прямую линию, которая ближе всего расположена к точкам корреляционного поля. Согласно методу наименьших квадратов линия выбирается так, чтобы сумма квадратов расстояний по вертикали между точками корреляционного поля и этой линией была бы минимальной.

Математическая запись данной задачи: .
Значения y i и x i =1...n нам известны, это данные наблюдений. В функции S они представляют собой константы. Переменными в данной функции являются искомые оценки параметров - , . Чтобы найти минимум функции 2-ух переменных необходимо вычислить частные производные данной функции по каждому из параметров и приравнять их нулю, т.е. .
В результате получим систему из 2-ух нормальных линейных уравнений:
Решая данную систему, найдем искомые оценки параметров:

Правильность расчета параметров уравнения регрессии может быть проверена сравнением сумм (возможно некоторое расхождение из-за округления расчетов).
Для расчета оценок параметров , можно построить таблицу 1.
Знак коэффициента регрессии b указывает направление связи (если b >0, связь прямая, если b <0, то связь обратная). Величина b показывает на сколько единиц изменится в среднем признак-результат -y при изменении признака-фактора - х на 1 единицу своего измерения.
Формально значение параметра а – среднее значение y при х равном нулю. Если признак-фактор не имеет и не может иметь нулевого значения, то вышеуказанная трактовка параметра а не имеет смысла.

Оценка тесноты связи между признаками осуществляется с помощью коэффициента линейной парной корреляции - r x,y . Он может быть рассчитан по формуле: . Кроме того, коэффициент линейной парной корреляции может быть определен через коэффициент регрессии b: .
Область допустимых значений линейного коэффициента парной корреляции от –1 до +1. Знак коэффициента корреляции указывает направление связи. Если r x, y >0, то связь прямая; если r x, y <0, то связь обратная.
Если данный коэффициент по модулю близок к единице, то связь между признаками может быть интерпретирована как довольно тесная линейная. Если его модуль равен единице ê r x , y ê =1, то связь между признаками функциональная линейная. Если признаки х и y линейно независимы, то r x,y близок к 0.
Для расчета r x,y можно использовать также таблицу 1.

Таблица 1

N наблюдения	x i	y i	x i ∙y i
1	x 1	y 1	x 1 ·y 1
2	x 2	y 2	x 2 ·y 2
...
n	x n	y n	x n ·y n
Сумма по столбцу	∑x	∑y	∑x·y
Среднее значение

Для оценки качества полученного уравнения регрессии рассчитывают теоретический коэффициент детерминации – R 2 yx:

,
где d 2 – объясненная уравнением регрессии дисперсия y ;
e 2 - остаточная (необъясненная уравнением регрессии) дисперсия y ;
s 2 y - общая (полная) дисперсия y .
Коэффициент детерминации характеризует долю вариации (дисперсии) результативного признака y , объясняемую регрессией (а, следовательно, и фактором х), в общей вариации (дисперсии) y . Коэффициент детерминации R 2 yx принимает значения от 0 до 1. Соответственно величина 1-R 2 yx характеризует долю дисперсии y , вызванную влиянием прочих неучтенных в модели факторов и ошибками спецификации.
При парной линейной регрессии R 2 yx =r 2 yx .

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

Характеристика МНК

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

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

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

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

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

Некоторые приложения МНК

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

Если некоторая физическая величина зависит от другой величины, то эту зависимость можно исследовать, измеряя 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	–	–	–	–	–

Программирование

• 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

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

Код и картинки доступны

После выравнивания получим функцию следующего вида: g (x) = x + 1 3 + 1 .

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

Yandex.RTB R-A-339285-1

В чем именно заключается МНК (метод наименьших квадратов)

Главное, что нам нужно сделать, – это найти такие коэффициенты линейной зависимости, при которых значение функции двух переменных F (a , b) = ∑ i = 1 n (y i - (a x i + b)) 2 будет наименьшим. Иначе говоря, при определенных значениях a и b сумма квадратов отклонений представленных данных от получившейся прямой будет иметь минимальное значение. В этом и состоит смысл метода наименьших квадратов. Все, что нам надо сделать для решения примера – это найти экстремум функции двух переменных.

Как вывести формулы для вычисления коэффициентов

Для того чтобы вывести формулы для вычисления коэффициентов, нужно составить и решить систему уравнений с двумя переменными. Для этого мы вычисляем частные производные выражения F (a , b) = ∑ i = 1 n (y i - (a x i + b)) 2 по a и b и приравниваем их к 0 .

δ F (a , b) δ a = 0 δ F (a , b) δ b = 0 ⇔ - 2 ∑ i = 1 n (y i - (a x i + b)) x i = 0 - 2 ∑ i = 1 n (y i - (a x i + b)) = 0 ⇔ a ∑ i = 1 n x i 2 + b ∑ i = 1 n x i = ∑ i = 1 n x i y i a ∑ i = 1 n x i + ∑ i = 1 n b = ∑ i = 1 n y i ⇔ a ∑ i = 1 n x i 2 + b ∑ i = 1 n x i = ∑ i = 1 n x i y i a ∑ i = 1 n x i + n b = ∑ i = 1 n y i

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

n ∑ i = 1 n x i y i - ∑ i = 1 n x i ∑ i = 1 n y i n ∑ i = 1 n - ∑ i = 1 n x i 2 b = ∑ i = 1 n y i - a ∑ i = 1 n x i n

Мы вычислили значения переменных, при который функция
F (a , b) = ∑ i = 1 n (y i - (a x i + b)) 2 примет минимальное значение. В третьем пункте мы докажем, почему оно является именно таким.

Это и есть применение метода наименьших квадратов на практике. Его формула, которая применяется для поиска параметра a , включает в себя ∑ i = 1 n x i , ∑ i = 1 n y i , ∑ i = 1 n x i y i , ∑ i = 1 n x i 2 , а также параметр
n – им обозначено количество экспериментальных данных. Советуем вам вычислять каждую сумму отдельно. Значение коэффициента b вычисляется сразу после a .

Обратимся вновь к исходному примеру.

Пример 1

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

	i = 1	i = 2	i = 3	i = 4	i = 5	∑ i = 1 5
x i	0	1	2	4	5	12
y i	2 , 1	2 , 4	2 , 6	2 , 8	3	12 , 9
x i y i	0	2 , 4	5 , 2	11 , 2	15	33 , 8
x i 2	0	1	4	16	25	46

Решение

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

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

n ∑ i = 1 n x i y i - ∑ i = 1 n x i ∑ i = 1 n y i n ∑ i = 1 n - ∑ i = 1 n x i 2 b = ∑ i = 1 n y i - a ∑ i = 1 n x i n ⇒ a = 5 · 33 , 8 - 12 · 12 , 9 5 · 46 - 12 2 b = 12 , 9 - a · 12 5 ⇒ a ≈ 0 , 165 b ≈ 2 , 184

У нас получилось, что нужная аппроксимирующая прямая будет выглядеть как y = 0 , 165 x + 2 , 184 . Теперь нам надо определить, какая линия будет лучше аппроксимировать данные – g (x) = x + 1 3 + 1 или 0 , 165 x + 2 , 184 . Произведем оценку с помощью метода наименьших квадратов.

Чтобы вычислить погрешность, нам надо найти суммы квадратов отклонений данных от прямых σ 1 = ∑ i = 1 n (y i - (a x i + b i)) 2 и σ 2 = ∑ i = 1 n (y i - g (x i)) 2 , минимальное значение будет соответствовать более подходящей линии.

σ 1 = ∑ i = 1 n (y i - (a x i + b i)) 2 = = ∑ i = 1 5 (y i - (0 , 165 x i + 2 , 184)) 2 ≈ 0 , 019 σ 2 = ∑ i = 1 n (y i - g (x i)) 2 = = ∑ i = 1 5 (y i - (x i + 1 3 + 1)) 2 ≈ 0 , 096

Ответ: поскольку σ 1 < σ 2 , то прямой, наилучшим образом аппроксимирующей исходные данные, будет
y = 0 , 165 x + 2 , 184 .

Метод наименьших квадратов наглядно показан на графической иллюстрации. С помощью красной линии отмечена прямая g (x) = x + 1 3 + 1 , синей – y = 0 , 165 x + 2 , 184 . Исходные данные обозначены розовыми точками.

Поясним, для чего именно нужны приближения подобного вида.

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

Доказательство метода МНК

Чтобы функция приняла минимальное значение при вычисленных a и b , нужно, чтобы в данной точке матрица квадратичной формы дифференциала функции вида F (a , b) = ∑ i = 1 n (y i - (a x i + b)) 2 была положительно определенной. Покажем, как это должно выглядеть.

Пример 2

У нас есть дифференциал второго порядка следующего вида:

d 2 F (a ; b) = δ 2 F (a ; b) δ a 2 d 2 a + 2 δ 2 F (a ; b) δ a δ b d a d b + δ 2 F (a ; b) δ b 2 d 2 b

Решение

δ 2 F (a ; b) δ a 2 = δ δ F (a ; b) δ a δ a = = δ - 2 ∑ i = 1 n (y i - (a x i + b)) x i δ a = 2 ∑ i = 1 n (x i) 2 δ 2 F (a ; b) δ a δ b = δ δ F (a ; b) δ a δ b = = δ - 2 ∑ i = 1 n (y i - (a x i + b)) x i δ b = 2 ∑ i = 1 n x i δ 2 F (a ; b) δ b 2 = δ δ F (a ; b) δ b δ b = δ - 2 ∑ i = 1 n (y i - (a x i + b)) δ b = 2 ∑ i = 1 n (1) = 2 n

Иначе говоря, можно записать так: d 2 F (a ; b) = 2 ∑ i = 1 n (x i) 2 d 2 a + 2 · 2 ∑ x i i = 1 n d a d b + (2 n) d 2 b .

Мы получили матрицу квадратичной формы вида M = 2 ∑ i = 1 n (x i) 2 2 ∑ i = 1 n x i 2 ∑ i = 1 n x i 2 n .

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

Вычисляем угловой минор первого порядка: 2 ∑ i = 1 n (x i) 2 > 0 . Поскольку точки x i не совпадают, то неравенство является строгим. Будем иметь это в виду при дальнейших расчетах.

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

d e t (M) = 2 ∑ i = 1 n (x i) 2 2 ∑ i = 1 n x i 2 ∑ i = 1 n x i 2 n = 4 n ∑ i = 1 n (x i) 2 - ∑ i = 1 n x i 2

После этого переходим к доказательству неравенства n ∑ i = 1 n (x i) 2 - ∑ i = 1 n x i 2 > 0 с помощью математической индукции.

1. Проверим, будет ли данное неравенство справедливым при произвольном n . Возьмем 2 и подсчитаем:

2 ∑ i = 1 2 (x i) 2 - ∑ i = 1 2 x i 2 = 2 x 1 2 + x 2 2 - x 1 + x 2 2 = = x 1 2 - 2 x 1 x 2 + x 2 2 = x 1 + x 2 2 > 0

У нас получилось верное равенство (если значения x 1 и x 2 не будут совпадать).

1. Сделаем предположение, что данное неравенство будет верным для n , т.е. n ∑ i = 1 n (x i) 2 - ∑ i = 1 n x i 2 > 0 – справедливо.
2. Теперь докажем справедливость при n + 1 , т.е. что (n + 1) ∑ i = 1 n + 1 (x i) 2 - ∑ i = 1 n + 1 x i 2 > 0 , если верно n ∑ i = 1 n (x i) 2 - ∑ i = 1 n x i 2 > 0 .

Вычисляем:

(n + 1) ∑ i = 1 n + 1 (x i) 2 - ∑ i = 1 n + 1 x i 2 = = (n + 1) ∑ i = 1 n (x i) 2 + x n + 1 2 - ∑ i = 1 n x i + x n + 1 2 = = n ∑ i = 1 n (x i) 2 + n · x n + 1 2 + ∑ i = 1 n (x i) 2 + x n + 1 2 - - ∑ i = 1 n x i 2 + 2 x n + 1 ∑ i = 1 n x i + x n + 1 2 = = ∑ i = 1 n (x i) 2 - ∑ i = 1 n x i 2 + n · x n + 1 2 - x n + 1 ∑ i = 1 n x i + ∑ i = 1 n (x i) 2 = = ∑ i = 1 n (x i) 2 - ∑ i = 1 n x i 2 + x n + 1 2 - 2 x n + 1 x 1 + x 1 2 + + x n + 1 2 - 2 x n + 1 x 2 + x 2 2 + . . . + x n + 1 2 - 2 x n + 1 x 1 + x n 2 = = n ∑ i = 1 n (x i) 2 - ∑ i = 1 n x i 2 + + (x n + 1 - x 1) 2 + (x n + 1 - x 2) 2 + . . . + (x n - 1 - x n) 2 > 0

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

Ответ: найденные a и b будут соответствовать наименьшему значению функции F (a , b) = ∑ i = 1 n (y i - (a x i + b)) 2 , значит, они являются искомыми параметрами метода наименьших квадратов (МНК).

Если вы заметили ошибку в тексте, пожалуйста, выделите её и нажмите Ctrl+Enter