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

(Carl Friedrich Gauss) приписывают создание основ метода наименьших квадратов в

1795 году (18-ти лет от роду). Однако впервые (в 1805) результаты были опубликованы Лежандром (Legendre).
Наиболее ранняя демонстрация мощи метода была продемонстрирована в 1801 году, когда был снова обнаружен астероид Ceres на основе расчетов Гаусса по методу наименьших квадратов.
Гаусс опубликовал метод в работе 1809 года. Независимо от него метод опубликован также американцем Robert Adrain в 1808.

История метода наименьших квадратов

16.10.2012

http://en.wikipedia.org/wiki/Least_squares

китайской книге «Девять глав арифметики», предположительно написанной за 200 лет

до нашей эры. В самом начале VIII-ой главы формулируется следующая задача.
Три меры хорошего зерна, две меры посредственного и одна плохая продаются за 39 доу. Две меры хорошего, три меры посредственного и одна плохая продаются за 34 доу; одна мера хорошего, две посредственного и три плохого зерна продаются за 26 доу. Требуется определить, сколько стоит одна мера хорошего, посредственного и плохого зерна соответственно.
Сегодня задача может быть переформулирована следующим образом: Найти решение системы линейных алгебраических уравнений



где x, y и z представляют собой цены мер хорошего, посредственного и плохого зерна соответственно.

История метода наименьших квадратов

16.10.2012

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

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

История метода наименьших квадратов

16.10.2012

and Joseph Fourier (right) by French artist Julien-Leopold Boilly, watercolor

portrait numbers 29 and 30 of Album de 73 Portraits-Charge Aquarelle’s des Membres de I’Institute.

Jensen

данных. Простой
набор данных состоит из n точек (пар данных),

,
где - независимые переменные и - зависимые,
полученные в результате наблюдений. Целевая функция
задается в виде f(x,β), где m параметров подгонки
сосредоточены в векторе β.
Цель состоит в отыскании таких параметров модели, которые
«наилучшим» образом аппроксимируют набор данных. Метод
наименьших квадратов минимизирует сумму, S, квадратов
невязок
Пример. Аппроксимация с помощью линейной функции.

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

16.10.2012

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

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

Обобщенная полная проблема наименьших квадратов

16.10.2012

Generalized Total Least Squares
CHENGXIAN XU
Xian Jiaotong University, Xian, China

явление:
и хотим подобрать параметры

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

Обобщенная полная проблема наименьших квадратов

16.10.2012

квадратов
16.10.2012

и

, минимизировав




Весовые коэффициенты задаются диагональными
матрицами

Обобщенный метод наименьших квадратов

16.10.2012

нелинейной функции по
(n+m)

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

Решение по методу Ньютона

16.10.2012

с элементами


Метод Ньютона решения этой задачи приводит к
решению системы

линейных уравнений



для определения очередного приближения

Решение по методу Ньютона

16.10.2012

учитывать специфическую структуру целевой функции

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

Приближенные методы Ньютона

16.10.2012

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

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

где , - множество ортогональных полиномов.

Приближенные методы Ньютона

16.10.2012

обращаются в ноль и обе матрицы

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

Решение системы метода Ньютона имеет вид:

16.10.2012

Приближенные методы Ньютона

,ортогональные на множестве

,
могут быть получены по рекуррентным формулам


где

Приближенные методы Ньютона

16.10.2012

и

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

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

Приближенные методы Ньютона

16.10.2012