|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 31 Jul 2003 19:20:34
To : Valentin Davydov
Subject : Линейная однородная система наименьших квадратов
--------------------------------------------------------------------------------
Wed Jul 30 2003 20:03, Valentin Davydov wrote to All:
VD> Имеется избыточная однородная система линейных уравнений Ax=0,
VD> где размер матрицы A составляет n на m, вектор x имеет размер m
и n >>> m. Требуется найти нетривиальное решение x, которое при
VD> некоторой разумной нормировке (например, средний квадрат элементов
VD> x равен единице, а последний элемент положительный) доставляет
VD> минимум среднеквадратичной невязке.
VD> Матрица A обладает специфическим свойством: Ai,j+1=Ai+1,j для всех
VD> осмысленных i,j, то есть она как бы ленточная, только наоборот,
VD> ленты тянутся слева снизу вправо вверх. Кроме того, все элементы
VD> матрицы неотрицательные.
VD> Вопрос: можно ли использовать это свойство матрицы для оптимизации
VD> алгоритма решения задачи, или её надо решать каким-нибудь из
VD> стандартных алгоритмов (тогда каким?) для матриц общего вида?
1. Вектор, доставляющий такой минимум, является собственным вектором m x m
матрицы AtA, соответствующим минимальному собственному значению.
2. Гарантировать что последний элемент будет ненулевым, невозможно, но если он
ненулевой - можно, при необходимости домножить на -1.
3. Сумма квадратов вектора будет равна 1, поскольку это стандартная нормировка
для большинства алгоритмов.
4. Матрица произведения не будет обладать специфическими свойствами, но если
она не превышает, скажем 100х100, оно и не надо.
5. Для бОльших размеров можно подумать про Ланцоша или одновременные итерации,
но они более для максимального СЗ.
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Линейная однородная система наименьших квадратов