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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$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 может быть записана как

$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 равен нулю. Поэтому параметры находятся путем решения:

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

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

Альтернативное разложение X - это разложение по сингулярным значениям (SVD).

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

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

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

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

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

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

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

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

Обсуждение

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

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

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

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

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

См. также

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

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

• Эйк Бьорк, Численные методы решения задач наименьших квадратов , 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-е изд.), Канцелярия Ее Величества