Метод наименьших квадратов в Excel. Регрессионный анализ. Метод наименьших квадратов примеры решения задач

Приблизим функцию многочленом 2-ой степени. Для этого вычислим коэффициенты нормальной системы уравнений:

, ,

Составим нормальную систему наименьших квадратов, которая имеет вид:

Решение системы легко находится:, , .

Таким образом, многочлен 2-ой степени найден: .

Теоретическая справка

Вернуться на страницу <Введение в вычислительную математику. Примеры>

Пример 2 . Нахождение оптимальной степени многочлена.

Вернуться на страницу <Введение в вычислительную математику. Примеры>

Пример 3 . Вывод нормальной системы уравнений для нахождения параметров эмпирической зависимости.

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

Тогда нормальная система примет вид:

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

Теоретическая справка

Вернуться на страницу <Введение в вычислительную математику. Примеры>

Пример.

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

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

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

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

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

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

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

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

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

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

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

Коэффициент b находится после вычисления a .

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

Решение.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

К началу страницы

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

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

Дифференциал второго порядка имеет вид:

То есть

Следовательно, матрица квадратичной формы имеет вид

причем значения элементов не зависят от а и b .

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

Угловой минор первого порядка . Неравенство строгое, так как точки несовпадающие. В дальнейшем это будем подразумевать.

Угловой минор второго порядка

Докажем, что методом математической индукции.

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

Некогда разбираться?
Закажите решение

К началу страницы

Разработка прогноза с помощью метода наименьших квадратов. Пример решения задачи

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

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

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

Рабочая формула метода наименьших квадратов : У t+1 = а*Х + b , где t + 1 – прогнозный период; Уt+1 – прогнозируемый показатель; a и b — коэффициенты; Х — условное обозначение времени.

Расчет коэффициентов a и b осуществляется по следующим формулам:

где, Уф – фактические значения ряда динамики; n – число уровней временного ряда;

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

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

Правильно установить тип кривой, тип аналитической зависимости от времени – одна из самых сложных задач предпрогнозного анализа .

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

где Уф – фактические значения ряда динамики; Ур – расчетные (сглаженные) значения ряда динамики; n – число уровней временного ряда; р – число параметров, определяемых в формулах, описывающих тренд (тенденцию развития).

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

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

Пример применения метода наименьших квадратов для разработки прогноза

Задача . Имеются данные, характеризующие уровень безработицы в регионе, %

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

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

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

ε = 28,63/10 = 2,86% точность прогноза высокая.

Вывод : Сравнивая результаты, полученные при расчетах методом скользящей средней , методом экспоненциального сглаживания и методом наименьших квадратов, можно сказать, что средняя относительная ошибка при расчетах методом экспоненциального сглаживания попадает в пределы 20-50%. Это значит, что точность прогноза в данном случае является лишь удовлетворительной.

В первом и третьем случае точность прогноза является высокой, поскольку средняя относительная ошибка менее 10%. Но метод скользящих средних позволил получить более достоверные результаты (прогноз на ноябрь – 1,52%, прогноз на декабрь – 1,53%, прогноз на январь – 1,49%), так как средняя относительная ошибка при использовании этого метода наименьшая – 1,13%.

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

Другие статьи по данной теме:

Список использованных источников

1. Научно-методические рекомендации по вопросам диагностики социальных рисков и прогнозирования вызовов, угроз и социальных последствий. Российский государственный социальный университет. Москва. 2010;
2. Владимирова Л.П. Прогнозирование и планирование в условиях рынка: Учеб. пособие. М.: Издательский Дом «Дашков и Ко», 2001;
3. Новикова Н.В., Поздеева О.Г. Прогнозирование национальной экономики: Учебно-методическое пособие. Екатеринбург: Изд-во Урал. гос. экон. ун-та, 2007;
4. Слуцкин Л.Н. Курс МБА по прогнозированию в бизнесе. М.: Альпина Бизнес Букс, 2006.

Программа МНК

Введите данные

Данные и аппроксимация y = a + b·x

i - номер экспериментальной точки;
x i - значение фиксированного параметра в точке i ;
y i - значение измеряемого параметра в точке i ;
ω i - вес измерения в точке i ;
y i, расч. - разница между измеренным и вычисленным по регрессии значением y в точке i ;
S x i (x i) - оценка погрешности x i при измерении y в точке i .

Данные и аппроксимация y = k·x

i	x i	y i	ω i	y i, расч.	Δy i	S x i (x i)

Кликните по графику,

Инструкция пользователя онлайн-программы МНК.

В поле данных введите на каждой отдельной строке значения `x` и `y` в одной экспериментальной точке. Значения должны отделяться пробельным символом (пробелом или знаком табуляции).

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

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

Для расчета по методу наименьших квадратов необходимо не менее двух точек для определения двух коэффициентов `b` - тангенса угла наклона прямой и `a` - значения, отсекаемого прямой на оси `y`.

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

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

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

Получение значений в каждой экспериментальной точке часто сопряжено со значительными трудозатратами, поэтому часто проводят компромиссное число экспериментов, которые дает удобоваримую оценку и не привеодит к чрезмерным трудо затратам. Как правило число экспериментах точек для линейной МНК зависимости с двумя коэффицинетами выбирает в районе 5-7 точек.

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

Допустим у нас имеется набор экспериментальных данных в виде пар значений [`y_i`, `x_i`], где `i` - номер одного эксперементального измерения от 1 до `n`; `y_i` - значение измеренной величины в точке `i`; `x_i` - значение задаваемого нами параметра в точке `i`.

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

`I = U / R`,
где `I` - сила тока; `R` - сопротивление; `U` - напряжение.

В этом случае `y_i` у нас имеряемая величина тока, а `x_i` - значение напряжения.

В качестве другого примера рассмотрим поглощение света раствором вещества в растворе. Химия дает нам формулу:

`A = ε l C`,
где `A` - оптическая плотность раствора; `ε` - коэффициент пропускания растворенного вещества; `l` - длина пути при прохождении света через кювету с раствором; `C` - концентрация растворенного вещества.

В этом случае `y_i` у нас имеряемая величина отптической плотности `A`, а `x_i` - значение концентрации вещества, которое мы задаем.

Мы будем рассматривать случай, когда относительная погрешность в задании `x_i` значительно меньше, относительной погрешности измерения `y_i`. Так же мы будем предполагать, что все измеренные величины `y_i` случайные и нормально распределенные, т.е. подчиняются нормальному закону распределения.

В случае линейной зависимости `y` от `x`, мы можем написать теоретическую зависимость:
`y = a + b x`.

С геометрической точки зрения, коэффициент `b` обозначает тангенс угла наклона линии к оси `x`, а коэффициент `a` - значение `y` в точке пересечения линии с осью `y` (при `x = 0`).

Нахождение параметров линии регресии.

В эксперименте измеренные значения `y_i` не могут точно лечь на теоеретическую прямую из-за ошибок измерения, всегда присущих реальной жизни. Поэтому линейное уравнение, нужно представить системой уравнений:
`y_i = a + b x_i + ε_i` (1),
где `ε_i` - неизвестная ошибка измерения `y` в `i`-ом эксперименте.

Зависимость (1) так же называют регрессией , т.е. зависимостью двух величин друг от друга со статистической значимостью.

Задачей восстановления зависимости является нахождение коэффициентов `a` и `b` по экспериментальным точкам [`y_i`, `x_i`].

Для нахождения коэффициентов `a` и `b` обычно используется метод наименьших квадратов (МНК). Он является частным случаем принципа максимального правдоподобия.

Перепишем (1) в виде `ε_i = y_i — a — b x_i`.

Тогда сумма квадратов ошибок будет
`Φ = sum_(i=1)^(n) ε_i^2 = sum_(i=1)^(n) (y_i — a — b x_i)^2`. (2)

Принципом МНК (метода наименьших квадратов) является минимизация суммы (2) относительно параметров `a` и `b` .

Минимум достигается, когда частные производные от суммы (2) по коэффициентам `a` и `b` равны нулю:
`frac(partial Φ)(partial a) = frac(partial sum_(i=1)^(n) (y_i — a — b x_i)^2)(partial a) = 0`
`frac(partial Φ)(partial b) = frac(partial sum_(i=1)^(n) (y_i — a — b x_i)^2)(partial b) = 0`

Раскрывая производные, получаем систему из двух уравнений с двумя неизвестными:
`sum_(i=1)^(n) (2a + 2bx_i — 2y_i) = sum_(i=1)^(n) (a + bx_i — y_i) = 0`
`sum_(i=1)^(n) (2bx_i^2 + 2ax_i — 2x_iy_i) = sum_(i=1)^(n) (bx_i^2 + ax_i — x_iy_i) = 0`

Раскрываем скобки и переносим независящие от искомых коэффициентов суммы в другую половину, получим систему линейных уравнений:
`sum_(i=1)^(n) y_i = a n + b sum_(i=1)^(n) bx_i`
`sum_(i=1)^(n) x_iy_i = a sum_(i=1)^(n) x_i + b sum_(i=1)^(n) x_i^2`

Решая, полученную систему, находим формулы для коэффициентов `a` и `b`:

`a = frac(sum_(i=1)^(n) y_i sum_(i=1)^(n) x_i^2 — sum_(i=1)^(n) x_i sum_(i=1)^(n) x_iy_i) (n sum_(i=1)^(n) x_i^2 — (sum_(i=1)^(n) x_i)^2)` (3.1)

`b = frac(n sum_(i=1)^(n) x_iy_i — sum_(i=1)^(n) x_i sum_(i=1)^(n) y_i) (n sum_(i=1)^(n) x_i^2 — (sum_(i=1)^(n) x_i)^2)` (3.2)

Эти формулы имеют решения, когда `n > 1` (линию можно построить не менее чем по 2-м точкам) и когда детерминант `D = n sum_(i=1)^(n) x_i^2 — (sum_(i=1)^(n) x_i)^2 != 0`, т.е. когда точки `x_i` в эксперименте различаются (т.е. когда линия не вертикальна).

Оценка погрешностей коэффициентов линии регресии

Для более точной оценки погрешности вычисления коэффициентов `a` и `b` желательно большое количество экспериментальных точек. При `n = 2`, оценить погрешность коэффициентов невозможно, т.к. аппроксимирующая линия будет однозначно проходить через две точки.

Погрешность случайной величины `V` определяется законом накопления ошибок
`S_V^2 = sum_(i=1)^p (frac(partial f)(partial z_i))^2 S_(z_i)^2`,
где `p` - число параметров `z_i` с погрешностью `S_(z_i)`, которые влияют на погрешность `S_V`;
`f` - функция зависимости `V` от `z_i`.

Распишем закон накопления ошибок для погрешности коэффициентов `a` и `b`
`S_a^2 = sum_(i=1)^(n)(frac(partial a)(partial y_i))^2 S_(y_i)^2 + sum_(i=1)^(n)(frac(partial a)(partial x_i))^2 S_(x_i)^2 = S_y^2 sum_(i=1)^(n)(frac(partial a)(partial y_i))^2 `,
`S_b^2 = sum_(i=1)^(n)(frac(partial b)(partial y_i))^2 S_(y_i)^2 + sum_(i=1)^(n)(frac(partial b)(partial x_i))^2 S_(x_i)^2 = S_y^2 sum_(i=1)^(n)(frac(partial b)(partial y_i))^2 `,
т.к. `S_(x_i)^2 = 0` (мы ранее сделали оговорку, что погрешность `x` пренебрежительно мала).

`S_y^2 = S_(y_i)^2` - погрешность (дисперсия, квадрат стандартного отклонения) в измерении `y` в предположении, что погрешность однородна для всех значений `y`.

Подставляя в полученные выражения формулы для расчета `a` и `b` получим

`S_a^2 = S_y^2 frac(sum_(i=1)^(n) (sum_(i=1)^(n) x_i^2 — x_i sum_(i=1)^(n) x_i)^2) (D^2) = S_y^2 frac((n sum_(i=1)^(n) x_i^2 — (sum_(i=1)^(n) x_i)^2) sum_(i=1)^(n) x_i^2) (D^2) = S_y^2 frac(sum_(i=1)^(n) x_i^2) (D)` (4.1)

`S_b^2 = S_y^2 frac(sum_(i=1)^(n) (n x_i — sum_(i=1)^(n) x_i)^2) (D^2) = S_y^2 frac(n (n sum_(i=1)^(n) x_i^2 — (sum_(i=1)^(n) x_i)^2)) (D^2) = S_y^2 frac(n) (D)` (4.2)

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

`S_y^2 = S_(y, ост)^2 = frac(sum_(i=1)^n (y_i — a — b x_i)^2) (n-2)`.

Делитель `n-2` появляется потому, что у нас снизилось число степеней свободы из-за расчета двух коэффициентов по этой же выборке экспериментальных данных.

Такую оценку еще называют остаточной дисперсией относительно линии регрессии `S_(y, ост)^2`.

Оценка значимости коэффициентов проводится по критерию Стьюдента

`t_a = frac(|a|) (S_a)`, `t_b = frac(|b|) (S_b)`

Если рассчитанные критерии `t_a`, `t_b` меньше табличных критериев `t(P, n-2)`, то считается, что соответсвующий коэффициент не значимо отличается от нуля с заданной вероятностью `P`.

Для оценки качества описания линейной зависимости, можно сравнить `S_(y, ост)^2` и `S_(bar y)` относительно среднего с использованием критерия Фишера.

`S_(bar y) = frac(sum_(i=1)^n (y_i — bar y)^2) (n-1) = frac(sum_(i=1)^n (y_i — (sum_(i=1)^n y_i) /n)^2) (n-1)` - выборочная оценка дисперсии `y` относительно среднего.

Для оценки эффективности уравнения регресии для описания зависимости расчитывают коэффициент Фишера
`F = S_(bar y) / S_(y, ост)^2`,
который сравнивают с табличным коэффициентом Фишера `F(p, n-1, n-2)`.

Если `F > F(P, n-1, n-2)`, считается статистически значимым с вероятностью `P` различие между описанием зависимости `y = f(x)` с помощью уравенения регресии и описанием с помощью среднего. Т.е. регрессия лучше описывает зависимость, чем разброс `y` относительно среднего.

Кликните по графику,
чтобы добавить значения в таблицу

Метод наименьших квадратов. Под методом наименьших квадратов понимается определение неизвестных параметров a, b, c, принятой функциональной зависимости

Под методом наименьших квадратов понимается определение неизвестных параметров a, b, c,… принятой функциональной зависимости

y = f(x,a,b,c,…) ,

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

, (24)

где x i , y i – совокупность пар чисел, полученных из эксперимента.

Так как условием экстремума функции нескольких переменных является условие равенства нулю ее частных производных, то параметры a, b, c,… определяются из системы уравнений:

; ; ; … (25)

Необходимо помнить, что метод наименьших квадратов применяется для подбора параметров после того, как вид функции y = f(x) определен.

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

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

1) линейная ;

2) квадратичная a .

Находит широкое применение в эконометрике в виде четкой экономической интерпретации ее параметров.

Линейная регрессия сводится к нахождению уравнения вида

или

Уравнение вида позволяет по заданным значениям параметра х иметь теоретические значения результативного признака, подставляя в него фактические значения фактора х .

Построение линейной регрессии сводится к оценке ее параметров — а и в. Оценки параметров линейной регрессии могут быть найдены разными методами.

Классический подход к оцениванию параметров линейной регрессии основан на методе наименьших квадратов (МНК).

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

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

Обозначим через S, тогда:

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

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

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

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

Как известно, линейный коэффициент корреляции находится в границах: -1 ≤ ≤ 1.

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

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

Соответственно величина 1 - характеризует долю диспер-сии у, вызванную влиянием остальных не учтенных в модели факторов.

Вопросы для самоконтроля

1. Суть метода наименьших квадратов?

2. Сколькими переменными предоставляется парная регрессия?

3. Каким коэффициентом определяется теснота связи между переменами?

4. В каких пределах определяется коэффициент детерминации?

5. Оценка параметра b в корреляционно-регрессионном анализе?

1. Кристофер Доугерти. Введение в эконометрию. - М.: ИНФРА - М, 2001 - 402 с.

2. С.А. Бородич. Эконометрика. Минск ООО «Новое знание» 2001.

3. Р.У. Рахметова Краткий курс по эконометрике. Учебное пособие. Алматы. 2004. -78с.

4. И.И. Елисеева.Эконометрика. - М.: «Финансы и статистика»,2002

5. Ежемесячный информационно-аналитический журнал.

Нелинейные экономические модели. Нелинейные модели регрессии. Преобразование переменных.

Нелинейные экономические модели..

Преобразование переменных.

Коэффициент эластичности.

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

Различают два класса нелинейных регрессий:

1. Регрессии, нелинейные относительно включенных в анализ объясняющих переменных, но линейные по оцениваемым параметрам, например:

Полиномы различных степеней - , ;

Равносторонняя гипербола - ;

Полулогарифмическая функция - .

2. Регрессии, нелинейные по оцениваемым параметрам, например:

Степенная - ;

Показательная - ;

Экспоненциальная - .

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

Если фактор не оказывает влияния на результат, то линия регрес-сии на графике параллельна оси ох и

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

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

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

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

Оценка значимости уравнения регрессии в целом дается с по-мощью F -критерия Фишера. При этом выдвигается нулевая ги-потеза, что коэффициент регрессии равен нулю, т. е. b = 0, и следовательно, фактор х не оказывает влияния на результат у.

Непосредственному расчету F-критерия предшествует анализ дисперсии. Центральное место в нем занимает разложе-ние общей суммы квадратов отклонений переменной у от средне го значения у на две части - «объясненную» и «необъясненную»:

- общая сумма квадратов отклонений;

- сумма квадратов отклонения объясненная регрессией;

- остаточная сумма квадратов отклонения.

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

Дисперсия на одну степень свободы D .

F-отношения (F-критерий):

Ecли нулевая гипотеза справедлива , то факторная и остаточная дисперсии не отличаются друг от друга. Для Н 0 необходимо опровержение,чтобы факторная дисперсия превышала остаточную в несколько раз. Английским статистиком Снедекором раз-работаны таблицы критических значений F -отношений при разных уровняхсущественности нулевой гипотезы и различном числе степенейсвободы. Табличное значение F -критерия — это максимальная величина отношения дисперсий, которая может иметь место прислучайном их расхождении для данного уровня вероятности наличия нулевой гипотезы. Вычисленное значение F -отношения признается достоверным, если о больше табличного.

В этом случае нулевая гипотеза об отсутствии связи признаков отклоняется и делается вывод о существенности этой связи: F факт > F табл Н 0 отклоняется.

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

Стандартная ошибка коэффициента регрессии

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

Стандартная ошибка параметра а :

Значимость линейного коэффициента корреляции проверя-ется на основе величины ошибки коэффициента корреляции т r:

Общая дисперсия признака х :

Множественная линейная регрессия

Построение модели

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

Регрессия может дать хороший результат при модели-ровании, если влиянием других факторов, воздействующих на объект исследования, можно пренебречь. Поведение отдельных экономи-ческих переменных контролировать нельзя, т. е. не удается обес-печить равенство всех прочих условий для оценки влияния одно-го исследуемого фактора. В этом случае следует попытаться выявить влияние других факторов, введя их в модель, т. е. пост-роить уравнение множественной регрессии: y = a+b 1 x 1 +b 2 +…+b p x p + .

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

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

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

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

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

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

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

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

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

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

• 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

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

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

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

• 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

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

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