Аппроксимация опытных данных – это метод, основанный на замене экспериментально полученных данных аналитической функцией наиболее близко проходящей или совпадающей в узловых точках с исходными значениями (данными полученными в ходе опыта или эксперимента). В настоящее время существует два способа определения аналитической функции:
С помощью построения интерполяционного многочлена 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.Определение суммы квадратов отклонений аппроксимирующего многочлена от исходных значений по всем узловым точкам
Найденное значение суммы квадратов отклонений является минимально-возможным.
Аппроксимация с помощью других функций
Следует отметить, что при аппроксимации исходных данных в соответствии с методом наименьших квадратов в качестве аппроксимирующей функции иногда используют логарифмическую функцию, экспоненциальную функцию и степенную функцию.
Логарифмическая аппроксимация
Рассмотрим случай, когда аппроксимирующая функция задана логарифмической функцией вида:
Он имеет множество применений, так как позволяет осуществлять приближенное представление заданной функции другими более простыми. МНК может оказаться чрезвычайно полезным при обработке наблюдений, и его активно используют для оценки одних величин по результатам измерений других, содержащих случайные ошибки. Из этой статьи вы узнаете, как реализовать вычисления по методу наименьших квадратов в Excel.
Постановка задачи на конкретном примере
Предположим, имеются два показателя X и Y. Причем Y зависит от X. Так как МНК интересует нас с точки зрения регрессионного анализа (в Excel его методы реализуются с помощью встроенных функций), то стоит сразу же перейти к рассмотрению конкретной задачи.
Итак, пусть X — торговая площадь продовольственного магазина, измеряемая в квадратных метрах, а Y — годовой товарооборот, определяемый в миллионах рублей.
Требуется сделать прогноз, какой товарооборот (Y) будет у магазина, если у него та или иная торговая площадь. Очевидно, что функция Y = f (X) возрастающая, так как гипермаркет продает больше товаров, чем ларек.
Несколько слов о корректности исходных данных, используемых для предсказания
Допустим, у нас есть таблица, построенная по данным для n магазинов.
Согласно математической статистике, результаты будут более-менее корректными, если исследуются данные по хотя бы 5-6 объектам. Кроме того, нельзя использовать «аномальные» результаты. В частности, элитный небольшой бутик может иметь товарооборот в разы больший, чем товарооборот больших торговых точек класса «масмаркет».
Суть метода
Данные таблицы можно изобразить на декартовой плоскости в виде точек M 1 (x 1 , y 1), … M n (x n , y n). Теперь решение задачи сведется к подбору аппроксимирующей функции y = f (x), имеющей график, проходящий как можно ближе к точкам M 1, M 2, .. M n .
Конечно, можно использовать многочлен высокой степени, но такой вариант не только труднореализуем, но и просто некорректен, так как не будет отражать основную тенденцию, которую и нужно обнаружить. Самым разумным решением является поиск прямой у = ax + b, которая лучше всего приближает экспериментальные данные, a точнее, коэффициентов - a и b.
Оценка точности
При любой аппроксимации особую важность приобретает оценка ее точности. Обозначим через e i разность (отклонение) между функциональными и экспериментальными значениями для точки x i , т. е. e i = y i - f (x i).
Очевидно, что для оценки точности аппроксимации можно использовать сумму отклонений, т. е. при выборе прямой для приближенного представления зависимости X от Y нужно отдавать предпочтение той, у которой наименьшее значение суммы e i во всех рассматриваемых точках. Однако, не все так просто, так как наряду с положительными отклонениями практически будут присутствовать и отрицательные.
Решить вопрос можно, используя модули отклонений или их квадраты. Последний метод получил наиболее широкое распространение. Он используется во многих областях, включая регрессионный анализ (в Excel его реализация осуществляется с помощью двух встроенных функций), и давно доказал свою эффективность.
Метод наименьших квадратов
В Excel, как известно, существует встроенная функция автосуммы, позволяющая вычислить значения всех значений, расположенных в выделенном диапазоне. Таким образом, ничто не помешает нам рассчитать значение выражения (e 1 2 + e 2 2 + e 3 2 + ... e n 2).
В математической записи это имеет вид:
Так как изначально было принято решение об аппроксимировании с помощью прямой, то имеем:
Таким образом, задача нахождения прямой, которая лучше всего описывает конкретную зависимость величин X и Y, сводится к вычислению минимума функции двух переменных:
Для этого требуется приравнять к нулю частные производные по новым переменным a и b, и решить примитивную систему, состоящую из двух уравнений с 2-мя неизвестными вида:
После нехитрых преобразований, включая деление на 2 и манипуляции с суммами, получим:
Решая ее, например, методом Крамера, получаем стационарную точку с некими коэффициентами a * и b * . Это и есть минимум, т. е. для предсказания, какой товарооборот будет у магазина при определенной площади, подойдет прямая y = a * x + b * , представляющая собой регрессионную модель для примера, о котором идет речь. Конечно, она не позволит найти точный результат, но поможет получить представление о том, окупится ли покупка в кредит магазина конкретной площади.
Как реализоавать метод наименьших квадратов в Excel
В "Эксель" имеется функция для расчета значения по МНК. Она имеет следующий вид: «ТЕНДЕНЦИЯ» (известн. значения Y; известн. значения X; новые значения X; конст.). Применим формулу расчета МНК в Excel к нашей таблице.
Для этого в ячейку, в которой должен быть отображен результат расчета по методу наименьших квадратов в Excel, введем знак «=» и выберем функцию «ТЕНДЕНЦИЯ». В раскрывшемся окне заполним соответствующие поля, выделяя:
- диапазон известных значений для Y (в данном случае данные для товарооборота);
- диапазон x 1 , …x n , т. е. величины торговых площадей;
- и известные, и неизвестные значения x, для которого нужно выяснить размер товарооборота (информацию об их расположении на рабочем листе см. далее).
Кроме того, в формуле присутствует логическая переменная «Конст». Если ввести в соответствующее ей поле 1, то это будет означать, что следует осуществить вычисления, считая, что b = 0.
Если нужно узнать прогноз для более чем одного значения x, то после ввода формулы следует нажать не на «Ввод», а нужно набрать на клавиатуре комбинацию «Shift» + «Control»+ «Enter» («Ввод»).
Некоторые особенности
Регрессионный анализ может быть доступен даже чайникам. Формула Excel для предсказания значения массива неизвестных переменных — «ТЕНДЕНЦИЯ» — может использоваться даже теми, кто никогда не слышал о методе наименьших квадратов. Достаточно просто знать некоторые особенности ее работы. В частности:
- Если расположить диапазон известных значений переменной y в одной строке или столбце, то каждая строка (столбец) с известными значениями x будет восприниматься программой в качестве отдельной переменной.
- Если в окне «ТЕНДЕНЦИЯ» не указан диапазон с известными x, то в случае использования функции в Excel программа будет рассматривать его как массив, состоящий из целых чисел, количество которых соответствует диапазону с заданными значениями переменной y.
- Чтобы получить на выходе массив «предсказанных» значений, выражение для вычисления тенденции нужно вводить как формулу массива.
- Если не указаны новые значения x, то функция «ТЕНДЕНЦИЯ» считает их равным известным. Если и они не заданы, то в качестве аргумента берется массив 1; 2; 3; 4;…, который соразмерен диапазону с уже заданными параметрами y.
- Диапазон, содержащий новые значения x должен состоять из такого же или большего количества строк или столбцов, как диапазон с заданными значениями y. Иными словами он должен быть соразмерным независимым переменным.
- В массиве с известными значениями x может содержаться несколько переменных. Однако если речь идет лишь об одной, то требуется, чтобы диапазоны с заданными значениями x и y были соразмерны. В случае нескольких переменных нужно, чтобы диапазон с заданными значениями y вмещался в одном столбце или в одной строке.
Функция «ПРЕДСКАЗ»
Реализуется с помощью нескольких функций. Одна из них называется «ПРЕДСКАЗ». Она аналогична «ТЕНДЕНЦИИ», т. е. выдает результат вычислений по методу наименьших квадратов. Однако только для одного X, для которого неизвестно значение Y.
Теперь вы знаете формулы в Excel для чайников, позволяющие спрогнозировать величину будущего значения того или иного показателя согласно линейному тренду.
Метод наименьших квадратов используется для оценки параметров уравнение регрессии.Одним из методов изучения стохастических связей между признаками является регрессионный анализ .
Регрессионный анализ представляет собой вывод уравнения регрессии, с помощью которого находится средняя величина случайной переменной (признака-результата), если величина другой (или других) переменных (признаков-факторов) известна. Он включает следующие этапы:
- выбор формы связи (вида аналитического уравнения регрессии);
- оценку параметров уравнения;
- оценку качества аналитического уравнения регрессии.
В случае линейной парной связи уравнение регрессии примет вид: y i =a+b·x i +u i . Параметры данного уравнения а и b оцениваются по данным статистического наблюдения x и y . Результатом такой оценки является уравнение: , где , - оценки параметров a и b , - значение результативного признака (переменной), полученное по уравнению регрессии (расчетное значение).
Наиболее часто для оценки параметров используют метод наименьших квадратов (МНК).
Метод наименьших квадратов дает наилучшие (состоятельные, эффективные и несмещенные) оценки параметров уравнения регрессии. Но только в том случае, если выполняются определенные предпосылки относительно случайного члена (u) и независимой переменной (x) (см. предпосылки МНК).
Задача оценивания параметров линейного парного уравнения методом наименьших квадратов
состоит в следующем: получить такие оценки параметров , , при которых сумма квадратов отклонений фактических значений результативного признака - y i от расчетных значений – минимальна.
Формально критерий МНК
можно записать так: 
.
Классификация методов наименьших квадратов
- Метод наименьших квадратов.
- Метод максимального правдоподобия (для нормальной классической линейной модели регрессии постулируется нормальность регрессионных остатков).
- Обобщенный метод наименьших квадратов ОМНК применяется в случае автокорреляции ошибок и в случае гетероскедастичности.
- Метод взвешенных наименьших квадратов (частный случай ОМНК с гетероскедастичными остатками).
Проиллюстрируем суть классического метода наименьших квадратов графически
. Для этого построим точечный график по данным наблюдений (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 | ||
| Среднее значение |
 |
 |
,
где 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 .
Метод наименьших квадратов - это математическая процедура составления линейного уравнения, максимально соответствующего набору упорядоченных пар, путем нахождения значений для a и b, коэффициентов в уравнении прямой. Цель метода наименьших квадратов состоит в минимизации общей квадратичной ошибки между значениями y и ŷ. Если для каждой точки мы определяем ошибку ŷ, метод наименьших квадратов минимизирует:
где n = число упорядоченных пар вокруг линии. максимально соответствующей данным.
Это понятие проиллюстрировано на рисунке
Судя по рисунку, линия, максимально соответствующая данным, линия регрессии, минимизирует общую квадратичную ошибку четырех точек на графике. Я покажу вам, как определять это с помощью метода наименьших квадратов на следующем примере.
Представьте себе молодую пару, которые, с недавних пор, живут вместе и совместно делят столик для косметических принадлежностей в ванной. Молодой человек начал замечать, что половина его столика неумолимо сокращается, сдавая свои позиции муссам для волос и соевым комплексам. За последние несколько месяцев парень внимательно следил за тем, с какой скоростью увеличивается число предметов на ее части стола. В таблице ниже представлено число предметов девушки на столике в ванной, накопившихся за последние несколько месяцев.
Поскольку своей целью мы определили задачу узнать, увеличивается ли со временем число предметов, «Месяц» будет независимой переменной, а «Число предметов» - зависимой.
С помощью метода наименьших квадратов определяем уравнение, максимально соответствующее данным, путем вычисления значений a, отрезка на оси y, и b, наклона линии:
a = y ср — bx ср
где x ср — среднее значение x, независимой переменной, y ср — среднее значение y, независимой переменной.
В таблице ниже суммированы необходимые для этих уравнений вычисления.
Кривая эффекта для нашего примера с ванной будет определяться следующим уравнением:
Поскольку наше уравнение имеет положительный наклон - 0.976, парень имеет доказательство того, что число предметов на столике со временем увеличивается со средней скоростью 1 предмет в месяц. На графике представлена кривая эффекта с упорядоченными парами.
Ожидание в отношении числа предметов в течение следующего полугода (месяца 16) будет вычисляться так:
ŷ = 5.13 + 0.976x = 5.13 + 0.976(16) ~ 20.7 = 21 предмет
Так что, пора нашему герою предпринимать какие-нибудь действия.
Функция ТЕНДЕНЦИЯ в Excel
Как вы уже, наверное, догадались в Excel имеется функция для расчета значения по методу наименьших квадратов. Это функция называется ТЕНДЕНЦИЯ. Синтаксис у нее следующий:
ТЕНДЕНЦИЯ (известные значения Y; известные значения X; новые значения X; конст)
известные значения Y – массив зависимых переменных, в нашем случае, количество предметов на столике
известные значения X – массив независимых переменных, в нашем случае это месяц
новые значения X – новые значения X (месяца) для которого функция ТЕНДЕНЦИЯ возвращает ожидаемое значение зависимых переменных (количество предметов)
конст — необязательный. Логическое значение, которое указывает, требуется ли, чтобы константа b была равна 0.
Например, на рисунке показана функция ТЕНДЕНЦИЯ, используемая для определения ожидаемого количества предметов на столике в ванной для 16-го месяца.
- 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
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 Вот результат: Код и картинки доступны