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

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

1. Линейная задача наименьших квадратов.

Пусть функция задана таблицей приближенных значений

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

Рис. 11.11

Предположим, что для аппроксимации функции используется линейная модель:

Здесь заданные базисные функции,

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

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

Отказываясь от требования выполнения в точках точных равенств (11.7), следует все же стремиться к тому, чтобы в этих точках выполнялись соответствующие приближенные равенства

Используя обозначения (11.9), запишем систему приближенных равенств (11.96) в матричном виде:

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

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

причем

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

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

2. Нормальная система.

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

Вычисляя частные производные функции и изменяя порядок суммирования, от равенства (11.98) переходим к системе линейных алгебраических уравнений

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

Как нетрудно видеть, нормальную систему можно записать в виде

или, используя матрицу Грама (см. § 11.2) и вводя вектор в виде

Лемма 11.1. Пусть решение системы (11.101). Тогда для любого а имеет место равенство

Имеем

Остается заметить, что второе слагаемое в правой части полученного равенства в силу (11.100) равно нулю.

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

В силу теоремы Поэтому решение с системы (11.101) существует и единственно. Таким образом, если многочлен существует, то его коэффициенты определяются единственным образом.

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

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

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

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

Так как в случае приближения алгебраическими многочленами то нормальная система (11.99) принимает следующий вид:

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

Бели же используется многочлен второй степени то нормальная система имеет вид

Пример 11.15. Пусть функция задана следующей таблицей:

Таблица 11.13 (см. скан)

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

Вычислим коэффициенты и правые части нормальных систем (11.103), (11.104):

Для многочлена первой степени нормальная система имеет вид

Решив ее, получим значения коэффициентов многочлена наилучшего среднеквадратичного приближения. Его график изображен на рис. 11.11, в.

Запишем теперь нормальную систему для многочлена второй степени:

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

Вычисления по формуле

для дают значения и 0.0486, и 0.0481.

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

3. Некоторые вычислительные аспекты задачи наименьших квадратов.

Метод вычисления параметров а с помощью решения нормальной системы (11.101) кажется весьма привлекательным. Действительно, задача сводится к стандартной проблеме линейной алгебры — решению системы линейных алгебраических уравнений с квадратной матрицей. Более того, можно показать, что в случае, когда функции линейно независимы в точках матрица системы является симметричной и положительно определенной. В частности, это означает, что при решении нормальной системы методом Гаусса не нужен выбор главных элементов; возможно также использование метода Холецкого (см. гл. 5).

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

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

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

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

Матрица Грама такой системы днатональна, а потому решение нормальной системы (11.101) вычисляется легко:

Хотя выбор ортогональной на множестве точек системы функций и желателен, он далеко не всегда возможен и удобен. Поэтому часто используются системы базисных функций, для которых матрица Грама лишь близка к диагональной. При аппроксимации на отрезке алгебраическими многочленами степени то пример такой системы дает система многочленов Чебышева Заметим, кстати, что найденный методом наименьших квадратов многочлен дает лишь иное, отличное от стандартного (11.95) представление многочлена наилучшего среднеквадратичного приближения. Однако задача определения параметров обладает существенно лучшей обусловленностью и поэтому предпочтительнее с вычислительной точки зрения.

Существуют методы решения задачи наименьших квадратов, предваряющие решение нормальной системы численной ортогонализацией системы базисных функций (см., например, [50], [60]). Однако в настоящее время в серьезной вычислительной практике нормальная система, как правило, не используется. Применяются другие, более надежные методы (учитывающие, например, информацию об уровне

погрешности данных и относительной точности используемой ЭВМ). С одним из таких методов, основанном на сингулярном разложении матрицы можно познакомиться в [86].

4. Понятие о статистических свойствах метода наименьших квадратов.

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

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

т. е. измеренные значения осредняются так, как это принято в статистике.

Пусть ошибка оценки (11.107). Заметим, что а потому

Итак, математическое ожидание ошибки равно нулю, причем, как видно из равенства (11.108), ее дисперсия стремится к нулю при Аналогично усредняются случайные ошибки с ростом числа наблюдений и в общем случае.

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

вектору данных, не содержащих ошибок, а второй вектору данных, содержащих случайные ошибки.

Положим (где ). Рассмотрим многочлен

Так как векторы а и удовлетворяют системам уравнений то вектор является решением системы

Отсюда вытекает равенство

Заметим, что и — это случайные ошибки значения многочлена и его коэффициентов вызванные наличием случайных ошибок в исходных данных. Покажем, что эти ошибки имеют нулевое математическое ожидание.

Действительно, из формулы (11.110) следует, что

откуда в свою очередь имеем

Введем величину

равную среднеквадратичному значению ошибки Теорема 11.12. Справедливо равенство

Заметим, что

Из определения операции умножения матриц следует, что элемент матрицы имеет вид элементы матрицы элементы матрицы Поэтому

Здесь элементы матрицы

Замечание 1. Величина представляет собой среднее по точкам значение дисперсии случайной ошибки Из теоремы 11.12 следует, что при т. е. при неограниченном росте числа наблюдений среднее значение дисперсии ошибки стремится к нулю.

Замечание 2 Равенство (11.111) подтверждает представление о том, что статистические свойства метода наименьших квадратов проявляются при т. е. тогда, когда число наблюдений много больше числа параметров модели

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

Теорема 11.13. Справедливы равенства

В силу леммы 11.1 имеет место равенство

которое в принятых выше обозначениях примет вид Вычислив математическое ожидание и использовав теорему 11.12, получим равенство (11.112).

Заметим теперь, что в силу леммы Преобразуем левую часть этого равенства:

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

Учитывая, что

получим равенство (11.113).

5. О выборе степени обобщенного многочлена.

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

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

Заметим также, что в силу теоремы 11.13 и закона больших чисел справедливы следующие приближенные равенства:

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

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

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

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

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

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

либо же, начиная с некоторого увеличение степени многочлена в широком диапозоне значений практически не влияет на качество приближения (т. е. и для всех Согласно формуле (11.114) справедливо приближенное равенство

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

Пример 11.16. Найдем оптимальную степень алгебраического многочлена для аппроксимации функции, заданной табл. 11.13.

Заметим, что фактически оптимальная степень уже была найдена при решении примера 11.15. Основанием для такого вывода послужило сравнение среднеквадратичных уклонений и 0.0486 и 62 и 0.0481 с оценкой уровня "шума" таблицы — грубый аналог критерия (11.116).

Попробуем получить тот же вывод, используя значения величин (11.117). Найдем дополнительно и 60 и 0.162. Тогда и 0.00381. Так как то за оптимальное значение степени следует принять

6. Нелинейная задача наименьших квадратов.

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

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

Нелинейная задача наименьших квадратов (особенно при большом числе параметров) весьма трудна для решения. Обычно для вычисления параметров а применяются специальные методы минимизации [32].

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