Численные методы линейного метода наименьших квадратов

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

Введение

Общий подход к задаче наименьших квадратов можно описать следующим образом. Предположим, что мы можем найти матрицу S размера n на m такую, что XS является ортогональной проекцией на образ X . Тогда решение нашей задачи минимизации имеет вид ${\displaystyle \operatorname {\,min} \,{\big \|}\mathbf {y} -X{\boldsymbol {\beta }}{\big \|}^{2}}$

${\displaystyle {\boldsymbol {\beta }}=S\mathbf {y} }$

просто потому что

${\displaystyle X{\boldsymbol {\beta }}=X(S\mathbf {y} )=(XS)\mathbf {y} }$

является в точности искомой ортогональной проекцией на изображение X (см. рисунок ниже и обратите внимание, что, как объясняется в следующем разделе, изображение X — это просто подпространство, порожденное векторами-столбцами X ). Ниже описаны несколько популярных способов найти такую ​​матрицу S. ${\displaystyle \mathbf {y} }$

Обращение матрицы нормальных уравнений

Это уравнение известно как нормальное уравнение. Алгебраическое решение нормальных уравнений с матрицей X ^T X полного ранга можно записать в виде ${\displaystyle (\mathbf {X} ^{\rm {T}}\mathbf {X} )\beta =\mathbf {X} ^{\rm {T}}y}$

${\displaystyle {\hat {\boldsymbol {\beta }}}=(\mathbf {X} ^{\rm {T}}\mathbf {X} )^{-1}\mathbf {X} ^{\rm {T}}\mathbf {y} =\mathbf {X} ^{+}\mathbf {y} }$

где X ⁺ — псевдообратная величина Мура–Пенроуза X . Хотя это уравнение корректно и может работать во многих приложениях, инвертировать матрицу нормальных уравнений ( матрицу Грама ) неэффективно с вычислительной точки зрения . Исключение составляет числовое сглаживание и дифференцирование , где требуется аналитическое выражение.

Если матрица X ^T X хорошо обусловлена ​​и положительно определена , что означает, что она имеет полный ранг , нормальные уравнения могут быть решены непосредственно с помощью разложения Холецкого R ^T R , где R — верхняя треугольная матрица , что дает:

${\displaystyle R^{\rm {T}}R{\hat {\boldsymbol {\beta }}}=X^{\rm {T}}\mathbf {y} .}$

Решение получается в два этапа: шаг прямой замены , решение для z :

${\displaystyle R^{\rm {T}}\mathbf {z} =X^{\rm {T}}\mathbf {y} ,}$

с последующей обратной заменой, решающей : ${\displaystyle {\hat {\boldsymbol {\beta }}}}$

${\displaystyle R{\hat {\boldsymbol {\beta }}}=\mathbf {z} .}$

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

Методы ортогонального разложения

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

Остатки записываются в матричной записи как

${\displaystyle \mathbf {r} =\mathbf {y} -X{\hat {\boldsymbol {\beta }}}.}$

Матрица X подвергается ортогональному разложению, например QR-разложению, следующим образом.

${\displaystyle X=Q{\begin{pmatrix}R\\0\end{pmatrix}}\ }$,

где Q — ортогональная матрица размера m × m ( Q ^T Q=I ), а R — верхняя треугольная матрица размера n × n с . ${\displaystyle r_{ii}>0}$

Вектор остатка умножается слева на Q ^T .

${\displaystyle Q^{\rm {T}}\mathbf {r} =Q^{\rm {T}}\mathbf {y} -\left(Q^{\rm {T}}Q\right){\begin{pmatrix}R\\0\end{pmatrix}}{\hat {\boldsymbol {\beta }}}={\begin{bmatrix}\left(Q^{\rm {T}}\mathbf {y} \right)_{n}-R{\hat {\boldsymbol {\beta }}}\\\left(Q^{\rm {T}}\mathbf {y} \right)_{m-n}\end{bmatrix}}={\begin{bmatrix}\mathbf {u} \\\mathbf {v} \end{bmatrix}}}$

Поскольку Q ортогонально , сумма квадратов остатков s может быть записана как:

${\displaystyle s=\|\mathbf {r} \|^{2}=\mathbf {r} ^{\rm {T}}\mathbf {r} =\mathbf {r} ^{\rm {T}}QQ^{\rm {T}}\mathbf {r} =\mathbf {u} ^{\rm {T}}\mathbf {u} +\mathbf {v} ^{\rm {T}}\mathbf {v} }$

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

${\displaystyle R{\hat {\boldsymbol {\beta }}}=\left(Q^{\rm {T}}\mathbf {y} \right)_{n}.}$

Эти уравнения легко решаются, поскольку R является верхнетреугольным.

Альтернативным разложением X является разложение по сингулярным значениям (SVD) ^[1]

${\displaystyle X=U\Sigma V^{\rm {T}}\ }$,

где U - ортогональная матрица размером m на m , V - ортогональная матрица размером n на n и представляет собой матрицу размером m на n , все ее элементы за пределами главной диагонали равны 0 . Псевдообратное легко получить путем инвертирования ненулевых диагональных элементов и транспонирования. Следовательно, ${\displaystyle \Sigma }$ ${\displaystyle \Sigma }$

${\displaystyle \mathbf {X} \mathbf {X} ^{+}=U\Sigma V^{\rm {T}}V\Sigma ^{+}U^{\rm {T}}=UPU^{\rm {T}},}$

где P получается заменой ненулевых диагональных элементов единицами. Поскольку (свойство псевдообратности) матрица является ортогональной проекцией на изображение (пространство-столбец) X . В соответствии с общим подходом, описанным во введении выше (найти XS , который является ортогональной проекцией), ${\displaystyle \Sigma }$ ${\displaystyle (\mathbf {X} \mathbf {X} ^{+})^{*}=\mathbf {X} \mathbf {X} ^{+}}$ ${\displaystyle UPU^{\rm {T}}}$

${\displaystyle S=\mathbf {X} ^{+}}$,

и поэтому,

${\displaystyle \beta =V\Sigma ^{+}U^{\rm {T}}\mathbf {y} }$

является решением задачи наименьших квадратов. Этот метод является наиболее вычислительно интенсивным, но он особенно полезен, если матрица нормальных уравнений X ^TX очень плохо обусловлена ​​(т. е. если ее число обусловленности , умноженное на относительную ошибку округления машины, значительно велико). В этом случае включение наименьших сингулярных значений в инверсию просто добавляет численный шум к решению. Это можно исправить с помощью подхода усеченного SVD, дающего более стабильный и точный ответ, путем явного обнуления всех сингулярных значений ниже определенного порога и, таким образом, их игнорирования - процесса, тесно связанного с факторным анализом .

Обсуждение

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

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

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

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

На матричные вычисления, как и на любые другие, влияют ошибки округления . Ранний обзор этих эффектов, касающихся выбора методов вычислений для обращения матрицы, был предоставлен Уилкинсоном. ^[2]

Смотрите также

• Численная линейная алгебра
• Численные методы нелинейного метода наименьших квадратов

Рекомендации

1. Лоусон, CL; Хэнсон, Р.Дж. (1974). Решение задач наименьших квадратов . Энглвуд Клиффс, Нью-Джерси: Прентис-Холл. ISBN 0-13-822585-0.
2. Уилкинсон, Дж. Х. (1963) «Глава 3: Матричные вычисления», Ошибки округления в алгебраических процессах , Лондон: Канцелярия Ее Величества (Национальная физическая лаборатория, Заметки по прикладной науке, № 32)

дальнейшее чтение

• Эйк Бьорк, Численные методы решения задач наименьших квадратов , SIAM, 1996.
• Р. В. Фарбразер, Линейные вычисления наименьших квадратов , CRC Press, 1988.
• Барлоу, Джесси Л. (1993), «Глава 9: Численные аспекты решения линейных задач наименьших квадратов», в Рао, CR (ред.), Вычислительная статистика , Справочник по статистике, том. 9, Северная Голландия, ISBN 0-444-88096-8
• Бьорк, Оке (1996). Численные методы решения задач наименьших квадратов . Филадельфия: СИАМ. ISBN 0-89871-360-9.
• Гудолл, Колин Р. (1993), «Глава 13: Вычисления с использованием QR-разложения», в Рао, CR (ред.), Вычислительная статистика , Справочник по статистике, том. 9, Северная Голландия, ISBN 0-444-88096-8
• Национальная физическая лаборатория (1961), «Глава 1: Линейные уравнения и матрицы: прямые методы», Современные вычислительные методы , Заметки по прикладной науке, том. 16 (2-е изд.), Канцелярия Ее Величества
• Национальная физическая лаборатория (1961), «Глава 2: Линейные уравнения и матрицы: прямые методы на автоматических компьютерах», Современные вычислительные методы , Заметки по прикладной науке, том. 16 (2-е изд.), Канцелярия Ее Величества