Выбрав вид функции регрессии, т.е. вид рассматриваемой модели зависимости 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 и 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).

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

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

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

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

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

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

Рис 4

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

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

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

Слободянюк А.И. Метод наименьших квадратов в школьном физическом эксперименте // Фiзiка: праблемы. выкладання.– 1995. – Вып. 1. – С. 88-99.

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

В статье излагается суть метода наименьших квадратов, условия его применимости. Авторы предлагают примеры использования метода МНК.

Как правило, все физические эксперименты сводятся к измерению зависимости некоторой величины u от одной или нескольких других величин z 1 , z 2 , …, z n .

Необходимость получения зависимости (а не проведения «точечного» измерения при фиксированных значениях параметров) оправдывается следующими преимуществами:

• возможностью проверки теоретических построений;

• возможностью исключения трудноопределяемых параметров;

• в некоторых случаях более простым способом оценки погрешностей.

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

1. Суть метода наименьших квадратов, условия его применимости

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

МНК утверждает, что «наилучшей» кривой будет такая, для которой сумма квадратов отклонений экспериментальных значений u i от значений функции минимальна. Таким образом, для определения параметров a , b , c ,... необходимо найти минимум функции

. (1)

Отметим, что Φ рассматривается здесь как функция параметров a , b , c ,..., так как величины u i , z i известны из экспериментальных данных.

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

для которого реализация МНК наиболее проста. Примеры преобразований такого типа приведены в табл. 1. Некоторые преобразования будут рассмотрены ниже при изложении конкретных примеров.

Подставим выражение (2) в выражение (1)

(3)

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

(4)

Данная система является линейной и легко решается:

(5)

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

(6)

(угловые скобки означают среднее арифметическое по экспериментальным данным) и запишем

(7)

Из второго уравнения системы (4) выразим .

Выражения (6), (7) позволяют достаточно быстро с помощью непрограммируемого калькулятора рассчитать параметры линейной зависимости (2).

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

1. Результаты измерений являются независимыми.

2. Погрешности измерений подчиняются нормальному распределению.

3. Величины х i , известны точно.

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

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

(8)

где , остальные обозначения сохраняем прежними:

(9)

Таким образом, формулы (6) – (9) полностью исчерпывают МНК для анализа линейной зависимости. Формулы (7) – (8) дают оценки только случайных погрешностей измерений. Их использование полностью оправдано, если этот тип погрешностей преобладает, что чаще всего бывает на практике. Свидетельством такого преобладания является заметный разброс точек (у i , х i ) на графике, когда эти точки не ложатся точно на прямую. Отметим, что постоянная систематическая приборная погрешность не влияет на определение параметра а и является аддитивной добавкой к погрешности параметра b , т.е. если приборная погрешность измерения величин у i равна , то .

Отметим также, что в некоторых случаях необходимо проводить несколько измерений величины u при одном и том же значении z . В этом случае никаких модификаций МНК не требуется. Достаточно рассматривать эти значения как независимые, т.е. включать в расчеты пары z i , u i ·с одними и теми же значениями z i . Иными словами, одному значению z может соответствовать несколько значений u . Естественно, не могут быть все z одинаковыми, иначе в формуле (5) в знаменателе окажется нуль.

2. Практическая реализация МНК для линейной зависимости на непрограммируемом калькуляторе

Как показывает опыт, лучше всего для расчетов параметров линейной зависимости и их погрешностей воспользоваться заранее приготовленным бланком (табл. 2). В колонке 1 записываются номера проведенных измерений (i = 1, 2, ..., Ν ); в колонках 2, 3 – результаты измерений величин z i , u i .

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

Расчетные формулы, представленные в колонке 6, допускают вычисления на калькуляторе без записи промежуточных результатов. Любой, даже самый простейший калькулятор, имеет одну ячейку памяти, в которой можно накапливать значения сумм. Расчеты следует проводить в такой последовательности:

1) вычислить – для этого последовательно ввести в память все значения х i , записанные в колонке 4, и после этого содержимое разделить на число пар измерений N, результат записать в колонке 7;

2) вычислить , последовательно набирая значения x i , накопить в памяти сумму их квадратов (набрать значения – «умножить» – «равно» – «в память +») и разделить на N , от полученного результата вычесть квадрат среднего, результат записать в колонке 7;

3 – 4) аналогично вычислить и ;

5) в памяти накопить сумму произведений , разделить на N , вычесть произведение средних и разделить на – получить значение параметра а .

Дальнейшие расчеты вполне очевидны.

3. Пример использования МНК

Задача . С помощью математического маятника измерить ускорение свободного падения.

Оборудование : нить, грузик, штатив, линейка, секундомер.

Решение . Период малых колебаний математического маятника Т определяется по формуле . Эту формулу можно преобразовать к виду .

Иными словами, между длиной маятника l и квадратом периода существует линейная связь, которую мы запишем в виде: , где (преобразование к линейному виду). Введение параметра b в данном случае не является обязательным, так как теоретически b = 0. Однако запись линейной зависимости в общем виде позволяет учесть автоматически погрешность в определении длины маятника, более того, в этом случае можно измерять не длину маятника, а только ее изменение. Если же все измерения проведены корректно, то МНК должен привести к результату , что и будет свидетельствовать о том, что .

Результаты измерений изменения длины маятника Δl (измерялось расстояние от точки подвеса до некоторой фиксированной точки на нити) и времени t двадцати колебаний (измерено с помощью ручных часов) приведены в табл. 3. Там же представлены результаты расчетов по изложенной методике.

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

Окончательный результат м/с.

Значение параметра b не использовалось (смысл полученной величины – расстояние от фиксированной точки на нити до центра масс груза). Использование этого параметра оправдано сложностью точного определения положения центра тяжести.

4. Экспериментальные задачи, предполагающие использование МНК

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

Задача 1 . Период колебаний математического маятника зависит от амплитуды j 0 (в радианах) по закону

(10)

Определите значение параметра β.

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

Указания к решению . Зависимость периода колебаний от амплитуды достаточно слабая. Чтобы ее обнаружить, необходимо проводить измерения с высокой точностью (–0,01 с), для чего требуется электронный секундомер.

Зависимость (10) представим в виде , где y = T ,b = Т 0 . По МНК для линейной зависимости можно найти значения параметров а и b , тогда искомый коэффициент определится по формуле (отметим, что теоретическое значение ).

Задача 2 . Определите фокусное расстояние собирающей линзы.

Оборудование : источник света, экран, линза, линейка.

Указания к решению . Воспользуемся формулой тонкой линзы

где d – расстояние от предмета до линзы, f – расстояние от линзы до изображения, F – фокусное расстояние линзы.

Обозначим , тогда . Если измерить несколько пар значений d i и f i и нанести на график точки , то эти точки должны лечь на прямую, которая отсекает на осях х , у отрезки, численно равные . Если обработать эту зависимость по МНК, можно получить и затем найти .

Задача 3 . Остывание воды описывается формулой , где Δ T –разность температур воды и воздуха в комнате, ΔT 0 – эта же разность в момент времени t = 0. Определите, сколько времени прошло с момента кипения воды.

Оборудование : горячая вода в сосуде, термометр, часы.

Указания к решению . Необходимо заранее закипятить воду и поставить ее остывать. Через некоторое время этот сосуд можно предоставить для выполнения задания. Следует иметь в виду, что время остывания стакана воды при комнатных условиях порядка 40 мин.

Для решения поставленной задачи необходимо измерить зависимость температуры воды T от времени t . Далее, перепишем приведенную формулу в виде , где T 0 – комнатная температура, T кип – температура кипения воды, t 0 – время, прошедшее от закипания до начала измерения. Так как в. формулу входят только разности температур, то можно пользоваться шкалой Цельсия. Прологарифмируем последнее выражение

(12)

и обозначим , x = t , получим линейную зависимость

Обрабатывая результаты измерений по МНК, найдем значения параметров а , b , из которых можно вычислить искомое значение времени t 0: .

Задача 4 . Исследуйте, как зависит сила сопротивления воздуха, действующая на падающие кусочки бумаги, от скорости последних.

Оборудование : кусочки бумаги, секундомер.

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

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

(требуется определить γ), при установившемся движении эта сила численно равна силе тяжести , следовательно, скорость установившегося движения , а время падения с высоты h :

(14)

Возьмем несколько (1, 2, 3, ..., 5) одинаковых тарелочек и измерим время падения t n сложенных вместе n тарелочек. Коэффициент с в формуле (13) будет одинаков (он зависит только от формы тарелочки), масса же падающих тел , где m 0 – масса одной тарелочки. Используем (14): , в логарифмической форме

(15)

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

Таким образом, измерив зависимость времени падения t n , от числа сложенных вместе n тарелочек и построив зависимость (15), по МНК можно найти значение параметра а и искомой величины .

При проведении эксперимента необходимо иметь в виду, что время падения кусочка бумаги см с высоты равно приблизительно 1,5 с, поэтому необходимо измерять время падения с погрешностью порядка 0,1 с. Следовательно, для каждого значения числа n нужно получить несколько значений t n . Подчеркнем, что в этой ситуации нет необходимости предварительно рассчитывать средние значения , можно (и нужно) рассматривать все результаты измерения как независимые и включать их в бланк расчета.

Еще одна задача подобного типа подробно рассмотрена в журнале «Фокус» .

5. Заключение

Рассмотренный алгоритм расчетов по МНК апробирован на летних сборах в лагере «Зубренок». Проведенные с победителями олимпиад занятия показали, что этот метод вполне доступен школьникам старших классов с углубленным изучением физики. После приобретения навыка работы на микрокалькуляторе расчеты занимают приблизительно 5–10 мин.

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

1. Тэйлор Дж. Введение в теорию ошибок. – М: Мир, 1985.

2. Большев Л.Н., Смирнов Н.В. Таблицы математической статистики. – М.: Наука, 1983.

3. Тимофеев А.. Проверим Стокса? – Фокус. – 1995. – №2. – С. 44-49.

Приведение к линейной зависимости

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

Определение параметров зависимости
периода колебаний маятника от его длины

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

По формуле (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

По формулам (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-степени, который проходит непосредственно через все точки заданного массива данных. В данном случае аппроксимирующая функция представляется в виде: интерполяционного многочлена в форме Лагранжа или интерполяционного многочлена в форме Ньютона.

С помощью построения аппроксимирующего многочлена 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=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: тут у меня косяк, расстояние до прямой должно измеряться по вертикали, а не ортогональной проекцией. комментатор прав.

Иллюстрация

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

Иллюстрация

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

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

Иначе говоря, мы ищем такой вектор 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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