Алгоритм метода наименьших квадратов

From

Evgenij Masherov (2:5020/175.2)

To

Slava Rad

Date

2003-01-08T19:24:51Z

Area

RU.ALGORITHMS

From: "Evgenij Masherov" <EMasherow@nsi.ru>

Mon Jan 06 2003 22:37, Slava Rad wrote to All:

 
 SR> Подскажите сабж, для решения СЛУ.

 Метод наименьших квадратов применяется для решения переопределенной системы
линейных уравнений, когда уравнений больше, чем неизвестных, причем они
несовместны. Тогда вводится невязка - разность между правой и левой частями
уравнений и минимизируется сумма квадратов невязок. При этом минимизируемая
функция квадратична, ее производные по Х-ам линейны, и решение задачи сводится
к решению некоторой системы линейных уравнений - уже совместной и с числом
неизвестных, равным числу уравнений.
Если наша СЛАУ имеет вид
Ax=y,
то решение МНК будет
x=inv(A#A)A# y
# - транспонирование
inv -обращение матриц.
Однако обращаемая матрица может быть плохо обусловлена.
Более радикальный путь в этом случае состоит в регуляризации, то есть
умышленном загрублении решения с повышением его численной устойчивости.
Особенно полезен этот подход, если мы не уверены в точности наших исходных
данных. Можно, например, получить решение в виде:
x=inv(A#A+kI)A# y
k - произвольный, выбираемый решающим уравнения коэффициент
I - единичная матрица
Чем больше к - тем дальше будет решение от точного, но тем меньше влияние
погрешностей (далее можно искать на ридж-регрессия - ridge-regression)
Менее радикальный путь состоит в решении без получения произведения
(A#A), обусловленность которого будет ниже, чем у матрицы А. Можно
воспользоваться сингулярным разложением или разложением QR. В этом случае
решение будет точным, однако при очень плохой обусловленности лучше все же
загрубление.
Два этих подхода можно соединить.

Евгений Машеров АКА СанитарЖеня

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)