🗊Презентация Метод наименьших квадратов

ЧИСЛЕННЫЕ МЕТОДЫ ОПТИМИЗАЦИИ Константин Ловецкий Октябрь 2012

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

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

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

Карл Фридрих Гаусс

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

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

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

Метод наименьших квадратов Минимизировать отыскав оптимальные значения параметров Здесь весовые коэффициенты задаются диагональной матрицей

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

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

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

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

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

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

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

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

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

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