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

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

Содержание Введение Глава 1. Теоретические сведения

§ 1 Многочлен Лагранжа

1.1 Постановка задачи

1.2 Построение интерполяционного многочлена Лагранжа

1.3 Остаточный член

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

2.1 Постановка задачи

2.2 Нахождение приближающей функции в виде линейной функции и квадратного трехчлена

2.3 Нахождение приближающей функции в виде других элементарных функций Глава 2. Вычислительный эксперимент

§ 1 Листинг программы по МНК

§ 2 Листинг программы по многочлену Лагранжа

§ 3 Вывод Заключение Список использованной литературы

Введение

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

Глава 1. Теоретические сведения

§ 1 Многочлен Лагранжа

1.1 Постановка задачи Пусть задана функция y=f (x). Часто нахождение значений этой функции может оказаться трудоемкой задачей. Например, — параметр в некоторой сложной задаче, после решения которой определяется значение f (x), или f (x) измеряется в дорогостоящем эксперименте. В этих случаях можно получить небольшую таблицу значений функции, но прямое нахождение ее значений при большом количестве значений аргумента нереально. В такой ситуации f (x) заменяется приближенной функцией, которая в определенном смысле близка к функции f (x). Близость обеспечивается введением в функцию свободных параметров и их соответствующим выбором.

Итак, известны значения функции f (x) в точках,. Потребуем, чтобы для некоторой функции, где — свободные параметры, выполнялись равенства:

(1)

Если (1) рассматривать как систему для определения, то этот способ называется интерполяцией (Лагранжевой).

Если зависит от нелинейно, то интерполяция нелинейная, иначе интерполяция линейная. В случае линейной интерполяции можно записать

(2)

(где — система линейно-независимых функций)

Подставим (2) в (1). Относительно получаем линейную систему уравнений:

(3)

Для однозначной разрешимости системы должно быть .

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

(4)

Система функций, удовлетворяющая условию (4), называется чебышевской.

1.2 Построение интерполяционного многочлена Лагранжа Наиболее простой и (для многих случаев) удобной является система функций,. Функция при этом представляет собой многочлен степени (интерполяционный многочлен) с коэффициентами .

Система уравнений (3) в этом случае имеет вид:

(5)

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

Отсюда следует, что интерполяционный многочлен существует и единственен.

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

Если y С[a, b]- многочлен степени n, то — искомый интерполяционный многочлен степени, т.к.

Так как при, то y C[a, b] делится на для любых, то есть

. Так как, то .

Таким образом,

(6)

Такая форма записи интерполяционного многочлена называется многочленом Лагранжа и обозначается, как правило, .

Существуют и другие формы записи того же самого интерполяционного многочлена.

Если обозначить, то

(6) можно записать в виде

1.3 Остаточный член В узлах многочлен Лагранжа совпадает с заданной функцией, в остальных точках в общем случае не совпадает с (кроме случая, когда многочлен степени не выше). Разность остаточный член. Запишем ее в виде .

При. Найдем постоянную такую, чтобы в некоторой фиксированной точке, в которой мы рассматриваем погрешность.

Будем предполагать, что раз дифференцируема.

Значение c, при котором существует и равно. Тогда функция равна нулю по крайней мере в точках .

По теореме Ролля производная равна нулю по крайней мере в точках. Далее, равна нулю по крайней мере в n точках и т. д.

Для — производной получаем, что существует по крайней мере одна точка такая, что

Отсюда получаем при .

Значение зависит от — точки, в которой рассматривается погрешность.

В этом случае в точке, т. е. остаточный член в точке имеет вид:

Оценка остаточного члена:

где

§ 2 Метод наименьших квадратов для аппроксимации функций

2.1 Постановка задачи Пусть в результате измерений в процессе опыта получена таблица

Нужно найти формулу, выражающую эту зависимость аналитически.

Можно, разумеется, применить метод интерполяции: построить интерполяционный многочлен, значения которого в точках x1, x2, … xn будут совпадать с соответствующими значениями f (x) из таблицы. Однако совпадение значений в узлах иногда может вовсе не значить совпадения характеров поведения исходной и интерполирующей функций. Требование неукоснительного совпадения значений в узлах выглядит тем более неоправданным, если значения функции f (x) получены в результате измерений и являются приближенными.

Поставим задачу так, чтобы с самого начала учитывался характер исходной функции: найти функцию заданного вида y=F (x), которая в точках x1, x2, … xn принимает значения, как можно более близкие к табличным значениям y1, y2,… yn .(уточнение выражения «более близкие» будет приведено ниже). итерполяционный многочлен лагранж Практически вид приближающей функции F можно определить следующим образом. По данным таблицы строится точечный график функции, а затем как на рисунке проводится плавная кривая, по возможности наилучшим образом отражающая характер расположения точек. По полученной таким образом кривой устанавливается вид приближающей функции (обычно из числа простых по виду аналитических функций) Следует заметить, что строгая функциональная зависимость для экспериментально полученной таблицы наблюдается редко, так как каждая из участвующих величин может зависеть от многих случайных факторов. Приближающая функция (ее называют эмпирической формулой, или уравнением регрессии y на x) интересна тем, что позволяет находить значения функции f (x) для нетабличных значений x, «сглаживая» результаты измерений величины y. Оправданность такого подхода определяется, в конечном счете, практически полезностью полученной формулы.

Рассмотрим один из распространенных способов нахождения эмпирической формулы. Предположим, что приближающая функция F в точках x1, x2,. xn имеет значения

(1)

Требование близости табличных значений y1, y2,… yn .и значений (1) можно истолковать следующим образом. Будем рассматривать совокупность значений функции f (x) из таблицы как координаты двух точек nмерного пространства. С учетом этого задача приближения функции f может быть переформулирована следующим образом: найти такую функцию F заданного вида, чтобы расстояние между точками M (y1, y2,… yn) и было наименьшим. Если воспользоваться метрикой евклидова пространства, то это условие сводится к требованию, чтобы величина была наименьшей. Легко видеть, что это требование равносильно следующему: чтобы была наименьшей сумма квадратов

(2)

Итак, задача приближения функции f теперь формулируется следующим образом: для функции f, заданной таблицей, найти функцию F определенного вида, чтобы сумма квадратов (2) был наименьшей

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

В качестве приближающих функций в зависимости от характера точечного графика функции f часто используют следующие функции:

1)

2)

3)

4)

5)

6)

7)

8)

Здесь a, b, c, m — параметры. Когда вид приближающей функции установлен, задача сводится только к отысканию значений параметров.

Рассмотрим метод нахождения параметров приближающей функции в общем виде на примере приближающей функции с тремя параметрами

(3)

Итак, имеем i=1,2, …, n Сумма квадратов разностей соответствующих значений функций f и F будет иметь вид Эта сумма является функцией трех переменных (параметров a, b и c) Задача сводится к отысканию минимума этой функции. Используем необходимое условие экстремума функции трех переменных:

которое в данном случае примет вид:

(4)/

Решив эту систему из трех уравнений с тремя неизвестными относительно параметров a, b и с, мы получим конкретный вид искомый функции F (x, a, b, c). Как видно из рассмотренного примера, изменение параметров не приведет к сущности самого подхода, а выразится лишь в изменении количество уравнений в системе (4)

Естественно ожидать, что значения найденной функции F (x, a, b, c) в точках будут отличатся от табличных значений Значения разностей (i=1, 2, …, n) (5) называются отклонениями (или уклонениями) измеренных значений y от вычисленных по формуле (3) Для эмпирической формулы (3) в соответствии с исходной таблицей можно найти сумму квадратов отклонений, которая в соответствии с принципов наименьших квадратов для заданного вида приближающей функции (и найденных значений параметров) должна быть наименьшей. Из двух приближений одной и той же табличной функции, согласно принципу наименьших квадратов, лучшим является то, для которого у имеет наименьшее значение

2.2 Нахождение приближающей функции в виде линейной функции и квадратного трехчлена Будем искать приближающую функцию в виде:

(6)

Найдем частные производные по параметрам a и b: и составим систему вида (4)

Сумма здесь и далее берется по параметру i в пределах от 1 до n

Далее имеем:

деля каждое уравнение на n, получим:

(7)

Введем обозначения:

(8)

Тогда последняя система будет иметь следующий вид:

(9)

Коэффициенты этой системы — числа, которые в каждой конкретной задаче приближения могут быть легко вычислены по формулам (8), в которых — значения из исходной таблицы. Решив систему (9), получим значения параметров a и b и, следовательно, конкретный вид линейной функции (5)

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

(10)

Находим частные производные:

Составим систему вида (3)

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

(11)

Здесь использованы обозначения (8), а также

(12)

Решение системы (11) дает значения параметров a, b и c для приближающей функции (10)

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

2.3.1 Степенная функция

Будем искать приближающую функцию в виде

(13)

(так называемая геометрическая регрессия). Предполагая, что в исходной таблице значения аргумента и значения функции положительны, прологарифмируем (13) при условии a>0:

ln F = ln a+m ln x (14)

Так как функция F является приближающей для функции f, функция ln F будет приближающей для функции ln f. Введем новую переменную u = ln x, тогда, как следует из (14), ln F будет новой функцией от u: Ф (u). Примем обозначения:

m = A; ln a = B (15)

Теперь равенство (14) примет вид Ф (u, А, B)= Au+B (16), т. е. задача свелась к отысканию приближающей функции в виде линейной.

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

· по данной таблице вычислить новую таблицу, прологарифмировав значения x и y;

· по новой таблице найти параметры A и B приближающей функции вида (16)

· использую обозначения (15), найти значения параметров a и m и подставить их в выражение (13)

В некоторых случаях может оказаться, что характер точечного графика обещает хорошее приближение в виде степенной функции, но среди табличных значений x и y есть отрицательные, что делает невозможным их логарифмирование. Трудностей можно избежать, сделав параллельный перенос значений x и y; после нахождения значений параметров a и m надлежит снова вернуться к переменным x и y.

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

a>0 (17)

(так называемая экспоненциальная регрессия) Прологарифмируем равенство (16)

ln F = ln a + mx (18)

Приняв обозначения (15), перепишем (18) в виде

ln F = Ax + B (19)

Таким образом, для нахождения приближающей функции в виде (17) нужно логарифмировать значения функции в исходной таблице и, рассматривая их совместно с исходными значениями аргумента, построить для новой таблицы приближающую функцию вида (6). Вслед за этим в соответствии с обозначениями (15) останется получить значения искомых параметров a, m и подставить их в формулу (17)

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

2.3.3 Дробнолинейная функция Будем искать приближающую функцию в виде

(20)

Равенство (20) перепишем следующим образом:

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

2.3.4 Логарифмическая функция

Пусть приближающая функция имеет вид

(21)

Легко видеть, что для перехода к линейной функции достаточно сделать подстановку ln x = u. Отсюда следует, что для нахождения значений a и b нужно прологарифмировать значения аргумента в исходной таблице и, рассматривая полученные значения в совокупности с исходными значениями функции, найти для полученной таким образом таблицы приближающую функцию в виде линейной. Коэффициенты a и b найденной функции подставить в формулу (21)

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

(22)

Для перехода к линейной функции сделаем подстановку u=1/x:

Ф (u, a, b)=au+b (23)

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

2.3.6 Дробнорациональная функция Пусть приближающая функция ищется в виде

(24)

Имеем:, так что задача сводится к случаю, рассмотренному в предыдущем пункте.

Действительно, если в исходной таблице заменить значения x и y обратными величинами по формулам z=1/x, u=1/y и искать для новой таблицы приближающую функцию вида, то найденные значения a и b будут искомыми для формулы (24)

2.3.7 Пример нахождения приближающей функции методом наименьших квадратов

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

Точечный график изображен на рисунке

Для сравнения качества приближений рассмотрим параллельно два способа приближения заданной функции: в виде линейной функции и в виде степенной функции. После нахождения значений параметров a и b, c и m можно найти суммы квадратов отклонений (2) и установить какой из двух приближений лучше.

Значения параметров a и b линейной функции находятся из системы вида (9), коэффициенты которой вычисляются по данным табл. 1 в соответствиями с обозначениями (8). Для вычисления коэффициентов системы по табл. 1 составим вспомогательную табл. 2, в последней строке которой получены суммы значений по соответствующим столбцам. Разделив полученные суммы на число элементов в столбцах, имеем в соответствии с формулами (7)

Табл. 2

Табл. 3

Составим теперь систему вида (9)

Решив систему, получаем. Отсюда следует, что приближающая функция имеет вид (25)

Для нахождения параметров c и m степенной функции, по исходной таблице составляется новая таблица из логарифмов значений x и y. Обозначим значения новых переменных соответственно u и z, т. е.. По числовым данным из новой таблицы составляется система уравнений вида (9)

(26)/

коэффициенты которойэто числа, вычисляемые по данным из новой таблицы по формулам вида (8), а неизвестные A и B связаны с искомыми параметрами c и m соотношениями

Для нахождения коэффициентов системы (26) составляем вспомогательную табл. 3

Разделив элементы последней строки табл. 3 на 8 получаем:

Составляем систему вида (26)

Ее решение: Находим значения параметров c и m:. Следовательно, приближающая функция в виде степенной имеет вид

(27)

Для сравнения качества приближений (25) и (27) вычислим суммы квадратов уклонений (табл.4)

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

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

Глава 2. Вычислительный эксперимент

§ 1 Листинг программы по МНК

program MNK;

uses crt;

const

n=8; // Количество пар значений функции и аргумента

x:array[1.n] of real=(1.1, 1.7, 2.4, 3.0, 3.7, 4.5, 5.1, 5.8); // Значения аргумента

y:array[1.n] of real=(0.3, 0.6, 1.1, 1.7, 2.3, 3.0, 3.8, 4.6); // Значения функции

type mas=array[0.50] of real;

var v, u: mas; // Массивы, для составления новых таблиц значений аргумента и функции в соответствии с выбранной аппроксимирующей функцией

i, k, j:integer; // Счетчики циклов

s1,s2,s3,s4,s, a, b, c: real; // s1, s2,s3,s4- Промежуточные значения, необходимые для подсчета конечных коэффициентов, sотклонения, a, b — конечные коэффициенты аппроксимирующей функции

begin

clrscr;

Writeln ('Выберите вид приближающей функции 1. y=a*x+b, 2. y=a*x^b, ');

writeln ('3. y=a*exp (b*x) и введите номер этого уравнения ');

readln (k);

// В данном цикле идет пересчет значений аргумента и функции в соответствии с выбранной аппроксимирующей функцией

for i:=1 to n do

begin

if k=1 then begin

u[i]: =x[i];

v[i]: =y[i];

end;

if k=2 then begin

u[i]: =ln (x[i]);

v[i]: =ln (y[i]);

end;

if k=3 then begin

u[i]: =x[i];

v[i]: =ln (y[i]);

end;

// Вычисление значений промежуточных коэффициентов,, в соответствии с формулами пункта 2.2

s1:=s1+u[i];

s2:=s2+v[i];

s3:=s3+u[i]*v[i];

s4:=s4+sqr (u[i]);

end;

c:=n*s4-sqr (s1); // Конечные коэффициенты аппроксимирующей функции, в соответствии с формулами пункта 2.2

a:=(n*s3-s1*s2)/c;

b:=(s4*s2-s1*s3)/c;

for i:=1 to n do // Подсчет отклонения

begin

v[i]: =a*u[i]+b;

if (k=2) or (k=3) then v[i]: =exp (v[i]); // Экспонируем значения функции, т.к. для подсчета коэффициентов они были прологарифмированы

s:=s+sqr (y[i]-v[i]);

end;

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

if k=1 then begin

writeln ('Приближающая функция y=', a:5:5,'*x+(', b:5:5,')');

writeln ('Сумма квадратов отклонений s=', s:5:5);

writeln ('Значение аппроксимирующей функции в указанных точках');

writeln ('и значения самой функции');

for j:=1 to n do

writeln ((a*y[j]+b):5:5,' ', y[j]);

end;

if k=2 then begin

writeln ('Приближающая функция y=', exp (b):5:5,'*x^(', a:5:5,')');

writeln ('Сумма квадратов отклонений s=', s:5:5);

writeln ('Значение аппроксимирующей функции в указанных точках');

writeln ('и значения самой функции');

for j:=1 to n do

writeln (a*exp (ln (y[j])*b):5:5,' ', y[j]);

end;

if k=3 then begin

writeln ('Приближающая функция y=', exp (b):5:5,'*exp (', a:3:3,'*x)');

writeln ('Сумма квадратов отклонений s=', s:5:5); writeln (a); writeln (b);

writeln ('Значение аппроксимирующей функции в указанных точках');

writeln ('и значения самой функции');

for j:=1 to n do

writeln (a*exp (b*y[j]):5:5,' ', y[j]);

end;

end.

§ 2 Листинг программы по многочлену Лагранжа Программа по данному методу написана в среде Maple для удобства построения многочлена Лагранжа

> restart;

> Digits:=5:

> N:=8: // Количество пар значений функции и аргумента

> xk:=array ([1.1, 1.7, 2.4, 3.0, 3.7, 4.5, 5.1, 5.8]): // Значения аргумента

> yk:=array ([0.3, 0.6, 1.1, 1.7, 2.3, 3.0, 3.8, 4.6]): // Значения функции

> S:=0:

> for i from 1 to N do

> P:=1;

> for j from 1 to N do

> if j<>i then P:=P*(x-xk[j])/(xk[i]-xk[j]); fi; // Подсчет произведения в каждом из членов суммы многочлена

> od;

> S:=S+yk[i]*P; // Суммирование получившихся произведений

> od:

> Ln:=expand (S): // Раскрывает скобки в построенном многочлене Лагнранжа

> print (evalf (Ln, 6)); // Выводит многочлен Лагранжа

> pogr:=0:

> for i from 1 to N do // Вычисление погрешности. Функция subs: Синтаксическая подстановка одного выражения вместо другого

> pogr:=pogr+(yk[i]-subs (x=xk[i], Ln)):

> od:

> print (pogr);

// Вывод исходных значений функции и значения аппроксимирующей функции в тех же точках

> for i from 1 to N do

> print (subs (x=xk[i], Ln), ` `, yk[i]);

> od;

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

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

Заключение

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

1. Бахвалов Н. С. Численные методы. Решения задач и упражнения. / Н. С. Бахвалов — М.: Дрофа, 2008

2. Вержбицкий В. М. Численные методы. Линейная алгебра и нелинейные уравнения./ В. М. Вержбицкий — М.: Оникс 21 век, 2005

3. Лапчик М. П. Численные методы./ М. П. Лапчик, М. И. Рагулина, Е. К. Хеннер — М.: Академия, 2005

4. Самарский А. А Введение в численные методы: учеб. пособие / А. А. Самарский — М.: Лань, 2008

5. Фадеев Д. К., Фадеева В. Н. Вычислительные методы линейной алгебры./ Д. К. Фадеев, В.Н. ФадееваМ.: Лань, 2002