|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergiy Kanilo 2:5020/400 30 Jul 2003 22:13:23
To : Valentin Davydov
Subject : Re: Линейная однородная система наименьших квадратов
--------------------------------------------------------------------------------
"Valentin Davydov" <val@sqdp.trc-net.co.jp> wrote in message
news:bg8q7j$1767$7@ddt.demos.su...
> Имеется избыточная однородная система линейных уравнений Ax=0,
> где размер матрицы A составляет n на m, вектор x имеет размер m
> и n >> m. Требуется найти нетривиальное решение x, которое при
> некоторой разумной нормировке (например, средний квадрат элементов
> x равен единице, а последний элемент положительный) доставляет
> минимум среднеквадратичной невязке.
ну вообще то никто не гарантирует, что удастся найти решение
с ненулевым последним элементом (A =0; A[n,m]=1;)
> Матрица A обладает специфическим свойством: Ai,j+1=Ai+1,j для всех
> осмысленных i,j, то есть она как бы ленточная, только наоборот,
> ленты тянутся слева снизу вправо вверх. Кроме того, все элементы
> матрицы неотрицательные.
т.е. если из коэффициентов матицы построить вектор размерности
n+m-1 (от верхнего угла вниз и потом вправо), то x максимально
ортогонален всем подвекторам длины m такого вектора
как первый шаг можно рассмотреть сужение поиска решения на
подпространство, оттогональное сумме этих подвекторов
(но это, наверное, очевидно (либо неверно:))
> Вопрос: можно ли использовать это свойство матрицы для оптимизации
> алгоритма решения задачи, или её надо решать каким-нибудь из
> стандартных алгоритмов (тогда каким?) для матриц общего вида?
свойство можно использовать хотя бы для хранения
такой матрицы в одномерном векторе (n+m-1 а не n*m)
Cheers,
Serge
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Линейная однородная система наименьших квадратов 